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