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