1 /* 2 * Copyright (C) 2012-2013 Nonki Takahashi. All rights reserved. 3 * 4 * History: 5 * 0.7 2013-06-19 Changed comment. 6 * 0.6 2013-06-15 Supported JsDoc Toolkit. 7 * 0.5 2013-03-16 Supported row vector as BMatrix. 8 * 0.4 2012-05-17 Tuned methods getValue and cross. 9 * 0.3 2012-05-15 Added way 2. for initializing. Changed notation for prototype. 10 * 0.2 2012-05-10 Added methods abs, inv, equals, diff, xor, mul, dot, cross, and toTeX. 11 * 0.1 2012-05-10 Created. Ported from Java version. 12 */ 13 14 /** 15 * @fileOverview BVector - Binary Vector Object Definition 16 * @version 0.7 17 * @author Nonki Takahashi 18 */ 19 20 // define mask for bit manipulation 21 var mask = [ 22 // @formatter:off 23 0x80000000, 0x40000000, 0x20000000, 0x10000000, 24 0x08000000, 0x04000000, 0x02000000, 0x01000000, 25 0x00800000, 0x00400000, 0x00200000, 0x00100000, 26 0x00080000, 0x00040000, 0x00020000, 0x00010000, 27 0x00008000, 0x00004000, 0x00002000, 0x00001000, 28 0x00000800, 0x00000400, 0x00000200, 0x00000100, 29 0x00000080, 0x00000040, 0x00000020, 0x00000010, 30 0x00000008, 0x00000004, 0x00000002, 0x00000001 31 // @formatter:on 32 ]; 33 34 /** 35 * Define Binary Vector Object BVector. 36 * @example 37 * bv = new BVector(4); // order 4 binary vector (0, 0, 0, 0) 38 * bv = new BVector(4, 1); // order 4 binary vector (1, 1, 1, 1) 39 * bv = new BVector(1, 0, 1, 0); // order 4 binary vector (1, 0, 1, 0) 40 * @class Represents Binary Vector 41 * @this {BVector} 42 * @property {Number} order order of vector 43 * @property {Number[]} bits substance of binary vector 44 * @since 0.1 45 */ 46 BVector = function() { 47 this.order = arguments.length; 48 if (arguments.length == 1) 49 this.order = arguments[0]; 50 if (arguments.length == 2 && arguments[0] > 1) 51 this.order = arguments[0]; 52 this.bits = new Array(Math.ceil(this.order / 32.0)); 53 if (arguments.length == 1) 54 this.clear(); 55 else if (arguments.length == 2 && arguments[0] > 1 && arguments[1] == 1) 56 for (var i = 1; i <= this.order; i++) 57 this.setValue(i, 1); 58 else 59 for (var i = 1; i <= this.order; i++) 60 if (arguments[i - 1]) 61 this.setValue(i, 1); 62 }; 63 64 BVector.prototype = { 65 66 /** 67 * Clear binary vector 68 * @since 0.2 69 */ 70 clear : function() { 71 for (var i = 0; i < this.bits.length; i++) 72 this.bits[i] = 0; 73 }, 74 75 /** 76 * Method to set value 0 or 1 to element i of binary vector object 77 * @param {Number} i element number 78 * @param {Number} value value to set 79 * @since 0.1 80 */ 81 setValue : function(i, value) { 82 // convert to 0 origin 83 var i0 = i - 1; 84 // reminder of 32 85 var i1 = i0 & 0x1F; 86 // quotient of 32 87 var i2 = i0 >> 5; 88 if (value == 1) 89 this.bits[i2] |= mask[i1]; 90 else if (value == 0) 91 this.bits[i2] &= ~mask[i1]; 92 }, 93 94 /** 95 * Method to get element i of binary vector 96 * @param {Number} i element number 97 * @return {Number} value 98 * @since 0.1 99 */ 100 getValue : function(i) { 101 // convert to 0 origin 102 var i0 = i - 1; 103 // i0 & 0x1F means remainder of 32 104 // i0 >> 5 means quotent of 32 105 return (this.bits[i0 >> 5] & mask[i0 & 0x1F]) ? 1 : 0; 106 }, 107 108 /** 109 * Method to copy binary vector object 110 * @return {BVector} returns binary vector copy 111 * @since 0.1 112 */ 113 clone : function() { 114 var bv = new BVector(this.order); 115 for (var i = 0; i < this.bits.length; i++) 116 bv.bits[i] = this.bits[i]; 117 return bv; 118 }, 119 120 /** 121 * Count elements that values are 1 in binary vector 122 * @return {Number} number of 1 elements 123 * @since 0.2 124 */ 125 abs : function() { 126 var n = 0; 127 for (var i = 1; i <= this.order; i++) 128 if (this.getValue(i) == 1) 129 n++; 130 return n; 131 }, 132 133 /** 134 * Returns inverted binary vector 135 * @return {BVector} inverted binary vector 136 * @since 0.2 137 */ 138 inv : function() { 139 var bv = new BVector(this.order); 140 // remainder 141 var m1 = (this.order - 1) % 32; 142 var mask1 = mask[m1]; 143 for (var mask2 = 0; mask1 != 0; mask1 <<= 1) { 144 mask2 |= mask1; 145 for (var i = 0; i < this.bits.length - 1; i++) 146 bv.bits[i] = ~this.bits[i]; 147 bv.bits[i] = ~this.bits[i] & mask2; 148 } 149 return bv; 150 }, 151 152 /** 153 * Returns transposed binary vector as binary matrix 154 * @return {BMatrix} transeposed binary vector 155 * @since 0.5 156 */ 157 tran : function() { 158 var bm = new BMatrix(1, this.order); 159 for (var j = 1; j <= this.order; j++) 160 bm.setValue(1, j, this.getValue(j)); 161 return bm; 162 }, 163 164 /** 165 * Returns true if two vectors are equal. Returns false if error or different. 166 * @param bv2 comparison target binary vector 167 * @return {Boolean} returns true if two vectors are equal 168 * @since 0.2 169 */ 170 equals : function(bv2) { 171 if (this.order != bv2.order) { 172 // different order 173 return false; 174 } 175 for (var i = 0; i < this.bits.length; i++) 176 if (this.bits[i] != bv2.bits[i]) { 177 // different value 178 return false; 179 } 180 return true; 181 }, 182 183 /** 184 * Logical or with binary vector object bv2 185 * @param {BVector} bv2 second operand for logical or 186 * @return {BVector} logical or with bv2 (or null if error) 187 * @since 0.1 188 */ 189 or : function(bv2) { 190 if (this.order != bv2.order) 191 return null; 192 var bv = this.clone(); 193 for (var i = 0; i < this.bits.length; i++) 194 bv.bits[i] |= bv2.bits[i]; 195 return bv; 196 }, 197 198 /** 199 * Logical and with binary vector object bv2 200 * @param {BVector} bv2 second operand for logical and 201 * @return {BVector} logical and with bv2 (or null if error) 202 * @since 0.1 203 */ 204 and : function(bv2) { 205 if (this.order != bv2.order) 206 return null; 207 var bv = this.clone(); 208 for (var i = 0; i < this.bits.length; i++) 209 bv.bits[i] &= bv2.bits[i]; 210 return bv; 211 }, 212 213 /** 214 * Logical difference with binary vector object bv2 215 * @param {BVector} bv2 second operand for logical difference 216 * @return {BVector} logical difference with bv2 (or null if error) 217 * @since 0.2 218 */ 219 diff : function(bv2) { 220 if (this.order != bv2.order) 221 return null; 222 var bv = this.clone(); 223 for (var i = 0; i < this.bits.length; i++) 224 bv.bits[i] &= ~bv2.bits[i]; 225 return bv; 226 }, 227 228 /** 229 * Exclusive or with binary vector object bv2 230 * @param {BVector} bv2 second operand for exclusive or 231 * @return {BVector} exclusive or with bv2 (or null if error) 232 * @since 0.2 233 */ 234 xor : function(bv2) { 235 if (this.order != bv2.order) 236 return null; 237 var bv = this.clone(); 238 for (var i = 0; i < this.bits.length; i++) 239 bv.bits[i] ^=bv2.bits[i]; 240 return bv; 241 }, 242 243 /** 244 * Product with scalar (0 or 1) 245 * @param {Number} b2 second operand for product 246 * @return {BVector} product with b2 (or null if error) 247 * @since 0.2 248 */ 249 mul : function(b2) { 250 if (b2 != 0 && b2 != 1) 251 return null; 252 var bv = new BVector(this.order); 253 if (b2 == 0) { 254 // 0 vector 255 return bv; 256 } else 257 return this.clone(); 258 }, 259 260 /** 261 * Dot product with binary vector object bv2 262 * @param {BVector} bv2 second operand for dot product 263 * @return {Number} dot product with bv2 (or -1 if error) 264 * @since 0.2 265 */ 266 dot : function(bv2) { 267 if (this.order != bv2.order) 268 return -1; 269 var b = 0; 270 for (var i = 1; i <= this.order; i++) 271 b |= (this.getValue(i) & bv2.getValue(i)); 272 return b; 273 }, 274 275 /** 276 * Returns product of binary vector and transposed binary vector (cross product) 277 * @param {BVector} bv2 second operand for cross product 278 * @return {BMatrix} cross product (or null if error) 279 * @since 0.2 280 */ 281 cross : function(bv2) { 282 if (this.order != bv2.order) 283 return null; 284 var bm = new BMatrix(this.order, this.order); 285 for (var j = 0; j < this.order; j++) 286 if (bv2.getValue(j + 1) == 1) 287 bm.colv[j] = this.clone(); 288 return bm; 289 }, 290 291 /** 292 * Convert binary vector object to string 293 * @return {String} string e.g. "(0,1,...,1)" 294 * @since 0.1 295 */ 296 toString : function() { 297 var str = "("; 298 for (var i = 0; i < this.order; i++) { 299 // convert to 1 origin 300 str = str + this.getValue(i + 1); 301 if (i < this.order - 1) 302 str = str + ","; 303 } 304 str = str + ")"; 305 return str; 306 }, 307 308 /** 309 * Convert binary vector object to TeX format 310 * @return {String} TeX string 311 * @since 0.2 312 */ 313 toTeX : function() { 314 var str = "\\begin{pmatrix}"; 315 for (var i = 0; i < this.order; i++) { 316 // convert to 1 origin 317 str = str + this.getValue(i + 1); 318 if (i < this.order - 1) 319 str = str + "\\\\"; 320 } 321 str = str + "\\end{pmatrix}"; 322 return str; 323 }, 324 }; 325