1 /*
  2  * Copyright (C) 2012-2013 たかはしのんき. All rights reserved.
  3  *
  4  * History:
  5  *  0.7 2013-06-19 コメントの修正。
  6  *  0.6 2013-06-15 JsDoc Toolkit対応。
  7  *  0.5 2013-03-16 行ベクトルを  BMatrix としてサポート。
  8  *  0.4 2012-05-17 メソッド  getValue, cross の性能改善。
  9  *  0.3 2012-05-15 初期値の設定方法 2.を追加。prototype 設定の記法を変更。
 10  *  0.2 2012-05-10 メソッド  abs, inv, equals, diff, xor, mul, dot, cross, toTeX の追加。
 11  *  0.1 2012-05-10 新規作成。Java 版より移植。
 12  */
 13 
 14 /**
 15  * @fileOverview BVector - 2進ベクトルオブジェクトの定義
 16  * @version 0.7
 17  * @author たかはしのんき
 18  * 
 19  */
 20 
 21 // ビット操作のためのマスクを定義します。
 22 var mask = [
 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 	];
 32 
 33 /**
 34  * 2進ベクトルオブジェクト BVector を定義します。<br>
 35  * 1. bv = new BVector(4);				// 次数 4 の2進ベクトル、初期値は (0, 0, 0, 0)<br>
 36  * 2. bv = new BVector(4, 1);			// 次数 4 の2進ベクトル、初期値は (1, 1, 1, 1)<br>
 37  * 3. bv = new BVector(1, 0, 1, 0);		// 次数 4 の2進ベクトル、初期値は (1, 0, 1, 0)
 38  * @constructor
 39  * @this {BVector}
 40  * @since 0.1
 41  */
 42 BVector = function() {
 43 	this.order = arguments.length;
 44 	if (arguments.length == 1)
 45 		this.order = arguments[0];
 46 	if (arguments.length == 2 && arguments[0] > 1)
 47 		this.order = arguments[0];
 48 	this.bits = new Array(Math.ceil(this.order / 32.0));
 49 	if (arguments.length == 1)
 50 		this.clear();
 51 	else if (arguments.length == 2 && arguments[0] > 1 && arguments[1] == 1)
 52 		for (var i = 1; i <= this.order; i++)
 53 			this.setValue(i, 1);
 54 	else
 55 		for (var i = 1; i <= this.order; i++)
 56 			if (arguments[i - 1])
 57 				this.setValue(i, 1);
 58 };
 59 
 60 BVector.prototype = {
 61 
 62 	/**
 63 	 * 2進ベクトルをゼロクリアします。
 64 	 * @since 0.2
 65 	 */
 66 	clear : function() {
 67 		for (var i = 0; i < this.bits.length; i++)
 68 			this.bits[i] = 0;
 69 	},
 70 
 71 	/**
 72 	 * 2進ベクトルオブジェクト BVector の要素 i に 0 か 1 の value を設定するメソッド
 73 	 * BVector.setValue(i, value) を定義します。
 74 	 * @param i 要素番号
 75 	 * @param value 設定する値
 76 	 * @since 0.1
 77 	 */
 78 	setValue : function(i, value) {
 79 		var i0 = i - 1;		// 0 originに変換
 80 		var i1 = i0 & 0x1F;	// 32 の剰余
 81 		var i2 = i0 >> 5;	// 32 の商
 82 		if (value == 1)
 83 			this.bits[i2] |= mask[i1];
 84 		else if (value == 0)
 85 			this.bits[i2] &= ~mask[i1];
 86 	},
 87 
 88 	/**
 89 	 * 2進ベクトルオブジェクト BVector の要素 i の値を取り出すメソッド
 90 	 * BVector.getValue(i) を定義します。
 91 	 * @param i 要素番号
 92 	 * @return 値
 93 	 * @since 0.1
 94 	 */
 95 	getValue : function(i) {
 96 		var i0 = i - 1;		// 0 originに変換
 97 		// i0 & 0x1F は 32 の剰余
 98 		// i0 >> 5　は 32 の商
 99 		return (this.bits[i0 >> 5] & mask[i0 & 0x1F]) ? 1 : 0;
100 	},
101 
102 	/**
103 	 * 2進ベクトルオブジェクト BVector をコピーするメソッド
104 	 * BVector.clone() を定義します。
105 	 * @return 2進ベクトルのコピーを返します。
106 	 * @since 0.1
107 	 */
108 	clone : function() {
109 		var bv = new BVector(this.order);
110 		for (var i = 0; i < this.bits.length; i++)
111 			bv.bits[i] = this.bits[i];
112 		return bv;
113 	},
114 
115 	/**
116 	 * 2進ベクトルの値が1の要素を数え上げます。
117 	 * @return 値が1の要素を数え上げた数を返します。
118 	 * @since 0.2
119 	 */
120 	abs : function() {
121 		var n = 0;
122 		for (var i = 1; i <= this.order; i++)
123 			if (this.getValue(i) == 1)
124 				n++;
125 		return n;
126 	},
127 
128 	/**
129 	 * 2進ベクトルを反転して(invert)返します。
130 	 * @return ベクトルの反転を返します。
131 	 * @since 0.2
132 	 */
133 	inv : function() {
134 		var bv = new BVector(this.order);
135 		var m1 = (this.order - 1) % 32;			// 剰余
136 		var mask1 = mask[m1];
137 		for (var mask2 = 0; mask1 != 0; mask1 <<= 1) {
138 			mask2 |= mask1;
139 			for (var i = 0; i < this.bits.length - 1; i++)
140 				bv.bits[i] = ~this.bits[i];
141 			bv.bits[i] = ~this.bits[i] & mask2;
142 		}
143 		return bv;
144 	},
145 
146 	/**
147 	 * 2進ベクトルを転置して(transpose)2進行列として返します。
148 	 * @return ベクトルの転置を返します。
149 	 * @since 0.5
150 	 */
151 	tran : function() {
152 		var bm = new BMatrix(1, this.order);
153 		for (var j = 1; j <= this.order; j++)
154 			bm.setValue(1, j, this.getValue(j));
155 		return bm;
156 	},
157 
158 	/**
159 	 * 2つの2進ベクトルが等しければtrueを返します。同じでないかエラーの場合はfalseを返します。
160 	 * @param bv2 比較対象のベクトル
161 	 * @return 2つのベクトルが等しければtrueを返します。
162 	 * @since 0.2
163 	 */
164 	equals : function(bv2) {
165 		if (this.order != bv2.order)
166 			return false;				// 次元が異なる
167 		for (var i = 0; i < this.bits.length; i++)
168 			if (this.bits[i] != bv2.bits[i])
169 				return false;			// 値が異なる
170 		return true;
171 	},
172 
173 	/**
174 	 * 2進ベクトルオブジェクト bv2 との論理和をとるメソッド
175 	 * BVector.or(bv2) を定義します。
176 	 * @param bv2 論理和の第2オペランドを指定します。
177 	 * @return bv2 との論理和を返します。
178 	 * @since 0.1
179 	 */
180 	or : function(bv2) {
181 		if (this.order != bv2.order)
182 			return null;
183 		var bv = this.clone();
184 		for (var i = 0; i < this.bits.length; i++)
185 			bv.bits[i] |= bv2.bits[i];
186 		return bv;
187 	},	
188 
189 	/**
190 	 * 2進ベクトルオブジェクト bv2 との論理積をとるメソッド
191 	 * BVector.and(bv2) を定義します。
192 	 * @param bv2 論理積の第2オペランドを指定します。
193 	 * @return bv2 との論理積を返します。
194 	 * @since 0.1
195 	 */
196 	and : function(bv2) {
197 		if (this.order != bv2.order)
198 			return null;
199 		var bv = this.clone();
200 		for (var i = 0; i < this.bits.length; i++)
201 			bv.bits[i] &= bv2.bits[i];
202 		return bv;
203 	},	
204 
205 	/**
206 	 * 2進ベクトル同士の論理差を返します。エラーの場合はnullを返します。
207 	 * @param bv2 論理差の第2オペランド
208 	 * @return 2つのベクトルの論理差を返します。
209 	 * @since 0.2
210 	 */
211 	diff : function(bv2) {
212 		if (this.order != bv2.order)
213 			return null;
214 		var bv = this.clone();
215 		for (var i = 0; i < this.bits.length; i++)
216 			bv.bits[i] &= ~bv2.bits[i];
217 		return bv;
218 	},
219 
220 	/**
221 	 * 2進行列同士の排他的論理和を返します。エラーの場合はnullを返します。
222 	 * @param bv2 排他的論理和の第2オペランド
223 	 * @return 2つの行列の排他的論理和を返します。
224 	 * @since 0.2
225 	 */
226 	xor : function(bv2) {
227 		if (this.order != bv2.order)
228 			return null;
229 		var bv = this.clone();
230 		for (var i = 0; i < this.bits.length; i++)
231 			bv.bits[i] ^= bv2.bits[i];
232 		return bv;
233 	},
234 
235 	/**
236 	 * ベクトルとスカラ(0か1)の積を返します。エラーの場合はnullを返します。
237 	 * @param b2 積の第2オペランド
238 	 * @return ベクトルとスカラの積を返します。
239 	 * @since 0.2
240 	 */
241 	mul : function(b2) {
242 		if (b2 != 0 && b2 != 1)
243 			return null;
244 		var bv = new BVector(this.order);
245 		if (b2 == 0)
246 			return bv;	// 0 ベクトル
247 		else
248 			return this.clone();
249 	},
250 
251 	/**
252 	 * 2進ベクトル同士の積（ドット積）を返します。エラーの場合は-1を返します。
253 	 * @param bv2 積の第2オペランド
254 	 * @return 2つのベクトルのドット積を返します。
255 	 * @since 0.2
256 	 */
257 	dot : function(bv2) {
258 		if (this.order != bv2.order)
259 			return -1;
260 		var b = 0;
261 		for (var i = 1; i <= this.order; i++)
262 			b |= (this.getValue(i) & bv2.getValue(i));
263 		return b;
264 	},
265 
266 	/**
267 	 * 2進ベクトルと2進ベクトルの転置との積（クロス積）を返します。エラーの場合はnullを返します。
268 	 * @param bv2 積の第2オペランド
269 	 * @return 2つのベクトルのクロス積を返します。
270 	 * @since 0.2
271 	 */
272 	cross : function(bv2) {
273 		if (this.order != bv2.order)
274 			return null;
275 		var bm = new BMatrix(this.order, this.order);
276 		for (var j = 0; j < this.order; j++)
277 			if (bv2.getValue(j + 1) == 1)
278 				bm.colv[j] = this.clone();
279 		return bm;
280 	},
281 
282 	/**
283 	 * 2進ベクトルオブジェクト BVector を文字列に変換するメソッド
284 	 * BVector.toString() を定義します。
285 	 * @return 文字列を返します。
286 	 * @since 0.1
287 	 */
288 	toString : function() {
289 		var str = "(";
290 		for (var i = 0; i < this.order; i++) {
291 			str = str + this.getValue(i + 1);	// 1 origin に変換
292 			if (i < this.order - 1)
293 				str = str + ",";
294 		}
295 		str = str + ")";
296 		return str;
297 	},
298 
299 	/**
300 	 * 2進ベクトルオブジェクト BVector を TeX 形式に変換します。
301 	 * @since 0.2
302 	 */
303 	toTeX : function() {
304 		var str = "\\begin{pmatrix}";
305 		for (var i = 0; i < this.order; i++) {
306 			str = str + this.getValue(i + 1);	// 1 origin に変換
307 			if (i < this.order - 1)
308 				str = str + "\\\\";
309 		}
310 		str = str + "\\end{pmatrix}";
311 		return str;
312 	},
313 };
314