1 /*
  2 * Copyright (c) 2012-2013 Nonki Takahashi. All rights reserved.
  3 *
  4 * History:
  5 *  0.5 2013-06-15 Supported JsDoc Toolkit.
  6 *  0.4 2013-03-16 Supported row vector.  Treated row vector as matrix.
  7 *  0.3 2012-05-17 Tuned mothod mul.
  8 *  0.2 2012-05-16 Corrected the other way around row and column in method toString
  9 *  0.1 2012-05-14 Created.  Ported from Java version.
 10 */
 11 
 12 /**
 13  * @fileOverview BMatrix - Binary Matrix Object
 14  * @name bmatrix05.js
 15  * @version 0.5
 16  * @author Nonki Takahashi
 17  *
 18  */
 19 
 20 /**
 21  * Binary Matrix Object
 22  * @example
 23  * bm = new BMatrix(2, 2);          // 2-row 2-column binary matrix (0 0 ↓ 0 0)
 24  * bm = new BMatrix(2, 2, 1, 1);    // 2-row 2-column binary matrix (1 0 ↓ 0 0)
 25  * bm = new BMatrix(2, 2, 2, 1);    // 2-row 2-column binary matrix (0 0 ↓ 1 0)
 26  * @class Represents Binary Matrix
 27  * @this {BMatrix}
 28  * @property {Number} init number of initial values
 29  * @property {Number} n number of rows
 30  * @property {Number} m number of columns
 31  * @property {BVector[]} colv substance of binary matrix
 32  * @since 0.1
 33  */
 34 BMatrix = function() {
 35     this.init = arguments.length - 2;
 36     if (this.init < 0)
 37         return null;
 38     this.n = arguments[0];
 39     this.m = arguments[1];
 40     this.colv = new Array(this.m);
 41     this.clear();
 42     for (var k = 1; k <= this.init; k++) {
 43         var i = arguments[k + 1][0];
 44         var j = arguments[k + 1][1];
 45         this.setValue(i, j, 1);
 46     }
 47 };
 48 
 49 BMatrix.prototype = {
 50     /**
 51      * Clears with zeroes with the binary matrix object
 52      * @since 0.1
 53      */
 54     clear : function() {
 55         for (var j = 0; j < this.m; j++) {
 56             if (this.colv[j] == undefined)
 57                 this.colv[j] = new BVector(this.n);
 58             this.colv[j].clear();
 59         }
 60     },
 61 
 62     /**
 63      * Sets a value (0 or 1) to the element i,j of the binary matrix object
 64      * @param {Number} i row number of the element to set (1 origin)
 65      * @param {Number} j column number of the element to set (1 origin)
 66      * @param {Number} value set value 0 or 1
 67      * @since 0.1
 68      */
 69     setValue : function(i, j, value) {
 70         // convert to 0 origin
 71         var j0 = j - 1;
 72         this.colv[j0].setValue(i, value);
 73     },
 74 
 75     /**
 76      * Returns the value (0 or 1) of the element i,j of the binary matrix object
 77      * @param {Number} i row number of the element to get (1 origin)
 78      * @param {Number} j column number of the element to get (1 origin)
 79      * @return {Number} value of the element i,j (0 or 1)
 80      * @since 0.1
 81      */
 82     getValue : function(i, j) {
 83         // convert to 0 origin
 84         var j0 = j - 1;
 85         return this.colv[j0].getValue(i);
 86     },
 87 
 88     /**
 89      * Copies binary matrix
 90      * @return {BMatrix} copy of the binary matrix
 91      * @since 0.1
 92      */
 93     clone : function() {
 94         var bm = new BMatrix(this.n, this.m);
 95         for (var j = 0; j < this.m; j++)
 96             bm.colv[j] = this.colv[j].clone();
 97         return bm;
 98     },
 99 
100     /**
101      * Counts value 1 in the binary matrix object
102      * @return {Number} number of elements that have value 1
103      * @since 0.1
104      */
105     abs : function() {
106         var n = 0;
107         for (var j = 0; j < this.m; j++)
108             n += this.colv[j].abs();
109         return n;
110     },
111 
112     /**
113      * Returns inverted binary matrix object
114      * @return {BMatrix} inverted binary matrix
115      * @since 0.1
116      */
117     inv : function() {
118         var bm = new BMatrix(this.n, this.m);
119         for (var j = 0; j < this.m; j++) {
120             bm.colv[j] = this.colv[j].inv();
121         }
122         return bm;
123     },
124 
125     /**
126      * Returns transposed binary matrix
127      * @return {BMatrix} transposed binary matrix
128      * @return {BVector} column vector for row vector
129      * @since 0.4
130      */
131     tran : function() {
132         if (this.n == 1) {
133             // row vector
134             var bv = new BVector(this.m);
135             for (var j = 1; j <= this.m; j++) {
136                 bv.setValue(j, this.getValue(1, j));
137             }
138             return bv;
139         } else {
140             var bm = new BMatrix(this.m, this.n);
141             for (var i = 1; i <= this.n; i++) {
142                 for (var j = 1; j <= this.m; j++) {
143                     bm.setValue(j, i, this.getValue(i, j));
144                 }
145             }
146             return bm;
147         }
148     },
149 
150     /**
151      * Returns true if two binary matrices are equal.  Returns false if error or different.
152      * @param {BMatrix} bm2 comparison target binary matrix
153      * @return {boolean} true if two matrices are equal.
154      * @since 0.1
155      */
156     equals : function(bm2) {
157         if (this.n != bm2.n || this.m != bm2.m) {
158             // different order
159             return false;
160         }
161         for (var j = 0; j < this.m; j++) {
162             if (!((this.colv[j]).equals(bm2.colv[j]))) {
163                 // different value
164                 return false;
165             }
166         }
167         return true;
168     },
169 
170     /**
171      * Logical or with binary matrix bm2
172      * @param {BMatrix} bm2 second operand for logocal or
173      * @return {BMatrix} logical or with bm2 (or null if error)
174      * @since 0.1
175      */
176     or : function(bm2) {
177         if (this.n != bm2.n || this.m != bm2.m) {
178             // different order
179             return null;
180         }
181         var bm = new BMatrix(this.n, this.m);
182         for (var j = 0; j < this.m; j++) {
183             bm.colv[j] = this.colv[j].or(bm2.colv[j]);
184         }
185         return bm;
186     },
187 
188     /**
189      * Logical and with binary matrix bm2
190      * @param {BMatrix} bm2 second operand for logocal and
191      * @return {BMatrix} logical and with bm2 (or null if error)
192      * @since 0.1
193      */
194     and : function(bm2) {
195         if (this.n != bm2.n || this.m != bm2.m) {
196             // different order
197             return null;
198         }
199         var bm = new BMatrix(this.n, this.m);
200         for (var j = 0; j < this.m; j++) {
201             bm.colv[j] = this.colv[j].and(bm2.colv[j]);
202         }
203         return bm;
204     },
205 
206     /**
207      * Logical difference with the binary matrix bm2
208      * @param {BMatrix} bm2 second operand for logical difference
209      * @return {BMatrix} logical difference with bm2 (or null if error)
210      * @since 0.1
211      */
212     diff : function(bm2) {
213         if (this.n != bm2.n || this.m != bm2.m) {
214             // different order
215             return null;
216         }
217         var bm = new BMatrix(this.n, this.m);
218         for (var j = 0; j < this.m; j++) {
219             bm.colv[j] = this.colv[j].diff(bm2.colv[j]);
220         }
221         return bm;
222     },
223 
224     /**
225      * Exclusive or with the binary matrix bm2
226      * @param {BMatrix} bm2 second operand for exclusive or
227      * @return {BMatrix} exclusive or with bm2 (or null if error)
228      * @since 0.1
229      */
230     xor : function(bm2) {
231         if (this.n != bm2.n || this.m != bm2.m) {
232             // different order
233             return null;
234         }
235         var bm = new BMatrix(this.n, this.m);
236         for (var j = 0; j < this.m; j++) {
237             bm.colv[j] = this.colv[j].xor(bm2.colv[j]);
238         }
239         return bm;
240     },
241 
242     /**
243      * Product with given binary matrix (or binary vector)
244      * @param {BMatrix | BVector} bx2 second operand for product
245      * @return {BMatrix} product with bx2 (or null if error)
246      * @since 0.1
247      */
248     mul : function(bx2) {
249         if (bx2.n == undefined) {
250             // bx2 is vector
251             if (this.m != bx2.order)
252                 return null;
253             var bv = new BVector(bx2.order);
254             for (var k = 0; k < this.m; k++) {
255                 if (bx2.getValue(k + 1) == 1)
256                     bv = bv.or(this.colv[k]);
257             }
258             return bv;
259         } else {
260             // bx2 is matrix
261             if (this.m != bx2.n)
262                 return null;
263             var bm = new BMatrix(bx2.n, bx2.m);
264             for (var j = 0; j < bx2.m; j++) {
265                 for (var k = 0; k < this.m; k++) {
266                     if (bx2.getValue(k + 1, j + 1) == 1)
267                         bm.colv[j] = bm.colv[j].or(this.colv[k]);
268                 }
269             }
270             return bm;
271         }
272     },
273 
274     /**
275      * Convert the binary matrix to a string
276      * @return {String} string
277      * @since 0.1
278      */
279     toString : function() {
280         var str = "";
281         for (var i = 1; i <= this.n; i++) {
282             for (var j = 1; j <= this.m; j++) {
283                 str = str + this.getValue(i, j);
284                 if (j < this.m)
285                     str = str + " ";
286             }
287             str = str + "\n";
288         }
289         return str;
290     },
291 
292     /**
293      * Convert the binary matrix to TeX string
294      * @return {String} TeX string
295      * @since 0.1
296      */
297     toTeX : function() {
298         var str = "\\begin{pmatrix}";
299         for (var i = 1; i <= this.n; i++) {
300             for (var j = 1; j <= this.m; j++) {
301                 str = str + this.getValue(i, j);
302                 if (j < this.m)
303                     str = str + " & ";
304             }
305             if (i < this.n)
306                 str = str + "\\\\";
307         }
308         str = str + "\\end{pmatrix}";
309         return str;
310     }
311 };
312