1 Clazz.declarePackage ("JU");
\r
2 Clazz.load (["javajs.api.JSONEncodable"], "JU.BS", ["java.lang.IndexOutOfBoundsException", "$.NegativeArraySizeException", "JU.PT", "$.SB"], function () {
\r
3 c$ = Clazz.decorateAsClass (function () {
\r
6 this.sizeIsSticky = false;
\r
7 Clazz.instantialize (this, arguments);
\r
8 }, JU, "BS", null, [Cloneable, javajs.api.JSONEncodable]);
\r
9 c$.wordIndex = Clazz.defineMethod (c$, "wordIndex",
\r
10 function (bitIndex) {
\r
11 return bitIndex >> 5;
\r
13 Clazz.defineMethod (c$, "recalculateWordsInUse",
\r
16 for (i = this.wordsInUse - 1; i >= 0; i--) if (this.words[i] != 0) break;
\r
18 this.wordsInUse = i + 1;
\r
20 Clazz.makeConstructor (c$,
\r
22 this.initWords (32);
\r
23 this.sizeIsSticky = false;
\r
25 c$.newN = Clazz.defineMethod (c$, "newN",
\r
27 var bs = new JU.BS ();
\r
31 Clazz.defineMethod (c$, "init",
\r
33 if (nbits < 0) throw new NegativeArraySizeException ("nbits < 0: " + nbits);
\r
34 this.initWords (nbits);
\r
35 this.sizeIsSticky = true;
\r
37 Clazz.defineMethod (c$, "initWords",
\r
39 this.words = Clazz.newIntArray (JU.BS.wordIndex (nbits - 1) + 1, 0);
\r
41 Clazz.defineMethod (c$, "ensureCapacity",
\r
42 function (wordsRequired) {
\r
43 if (this.words.length < wordsRequired) {
\r
44 var request = Math.max (2 * this.words.length, wordsRequired);
\r
45 this.setLength (request);
\r
46 this.sizeIsSticky = false;
\r
48 Clazz.defineMethod (c$, "expandTo",
\r
49 function (wordIndex) {
\r
50 var wordsRequired = wordIndex + 1;
\r
51 if (this.wordsInUse < wordsRequired) {
\r
52 this.ensureCapacity (wordsRequired);
\r
53 this.wordsInUse = wordsRequired;
\r
55 Clazz.defineMethod (c$, "set",
\r
56 function (bitIndex) {
\r
57 if (bitIndex < 0) throw new IndexOutOfBoundsException ("bitIndex < 0: " + bitIndex);
\r
58 var wordIndex = JU.BS.wordIndex (bitIndex);
\r
59 this.expandTo (wordIndex);
\r
60 this.words[wordIndex] |= (1 << bitIndex);
\r
62 Clazz.defineMethod (c$, "setBitTo",
\r
63 function (bitIndex, value) {
\r
64 if (value) this.set (bitIndex);
\r
65 else this.clear (bitIndex);
\r
67 Clazz.defineMethod (c$, "setBits",
\r
68 function (fromIndex, toIndex) {
\r
69 if (fromIndex == toIndex) return;
\r
70 var startWordIndex = JU.BS.wordIndex (fromIndex);
\r
71 var endWordIndex = JU.BS.wordIndex (toIndex - 1);
\r
72 this.expandTo (endWordIndex);
\r
73 var firstWordMask = -1 << fromIndex;
\r
74 var lastWordMask = -1 >>> -toIndex;
\r
75 if (startWordIndex == endWordIndex) {
\r
76 this.words[startWordIndex] |= (firstWordMask & lastWordMask);
\r
78 this.words[startWordIndex] |= firstWordMask;
\r
79 for (var i = startWordIndex + 1; i < endWordIndex; i++) this.words[i] = -1;
\r
81 this.words[endWordIndex] |= lastWordMask;
\r
83 Clazz.defineMethod (c$, "clear",
\r
84 function (bitIndex) {
\r
85 if (bitIndex < 0) throw new IndexOutOfBoundsException ("bitIndex < 0: " + bitIndex);
\r
86 var wordIndex = JU.BS.wordIndex (bitIndex);
\r
87 if (wordIndex >= this.wordsInUse) return;
\r
88 this.words[wordIndex] &= ~(1 << bitIndex);
\r
89 this.recalculateWordsInUse ();
\r
91 Clazz.defineMethod (c$, "clearBits",
\r
92 function (fromIndex, toIndex) {
\r
93 if (fromIndex == toIndex) return;
\r
94 var startWordIndex = JU.BS.wordIndex (fromIndex);
\r
95 if (startWordIndex >= this.wordsInUse) return;
\r
96 var endWordIndex = JU.BS.wordIndex (toIndex - 1);
\r
97 if (endWordIndex >= this.wordsInUse) {
\r
98 toIndex = this.length ();
\r
99 endWordIndex = this.wordsInUse - 1;
\r
100 }var firstWordMask = -1 << fromIndex;
\r
101 var lastWordMask = -1 >>> -toIndex;
\r
102 if (startWordIndex == endWordIndex) {
\r
103 this.words[startWordIndex] &= ~(firstWordMask & lastWordMask);
\r
105 this.words[startWordIndex] &= ~firstWordMask;
\r
106 for (var i = startWordIndex + 1; i < endWordIndex; i++) this.words[i] = 0;
\r
108 this.words[endWordIndex] &= ~lastWordMask;
\r
109 }this.recalculateWordsInUse ();
\r
111 Clazz.defineMethod (c$, "clearAll",
\r
113 while (this.wordsInUse > 0) this.words[--this.wordsInUse] = 0;
\r
116 Clazz.defineMethod (c$, "get",
\r
117 function (bitIndex) {
\r
118 if (bitIndex < 0) throw new IndexOutOfBoundsException ("bitIndex < 0: " + bitIndex);
\r
119 var wordIndex = JU.BS.wordIndex (bitIndex);
\r
120 return (wordIndex < this.wordsInUse) && ((this.words[wordIndex] & (1 << bitIndex)) != 0);
\r
122 Clazz.defineMethod (c$, "nextSetBit",
\r
123 function (fromIndex) {
\r
124 if (fromIndex < 0) throw new IndexOutOfBoundsException ("fromIndex < 0: " + fromIndex);
\r
125 var u = JU.BS.wordIndex (fromIndex);
\r
126 if (u >= this.wordsInUse) return -1;
\r
127 var word = this.words[u] & (-1 << fromIndex);
\r
129 if (word != 0) return (u * 32) + Integer.numberOfTrailingZeros (word);
\r
130 if (++u == this.wordsInUse) return -1;
\r
131 word = this.words[u];
\r
134 Clazz.defineMethod (c$, "nextClearBit",
\r
135 function (fromIndex) {
\r
136 if (fromIndex < 0) throw new IndexOutOfBoundsException ("fromIndex < 0: " + fromIndex);
\r
137 var u = JU.BS.wordIndex (fromIndex);
\r
138 if (u >= this.wordsInUse) return fromIndex;
\r
139 var word = ~this.words[u] & (-1 << fromIndex);
\r
141 if (word != 0) return (u * 32) + Integer.numberOfTrailingZeros (word);
\r
142 if (++u == this.wordsInUse) return this.wordsInUse * 32;
\r
143 word = ~this.words[u];
\r
146 Clazz.defineMethod (c$, "length",
\r
148 if (this.wordsInUse == 0) return 0;
\r
149 return 32 * (this.wordsInUse - 1) + (32 - Integer.numberOfLeadingZeros (this.words[this.wordsInUse - 1]));
\r
151 Clazz.defineMethod (c$, "isEmpty",
\r
153 return this.wordsInUse == 0;
\r
155 Clazz.defineMethod (c$, "intersects",
\r
157 for (var i = Math.min (this.wordsInUse, set.wordsInUse) - 1; i >= 0; i--) if ((this.words[i] & set.words[i]) != 0) return true;
\r
161 Clazz.defineMethod (c$, "cardinality",
\r
164 for (var i = 0; i < this.wordsInUse; i++) sum += Integer.bitCount (this.words[i]);
\r
168 Clazz.defineMethod (c$, "and",
\r
170 if (this === set) return;
\r
171 while (this.wordsInUse > set.wordsInUse) this.words[--this.wordsInUse] = 0;
\r
173 for (var i = 0; i < this.wordsInUse; i++) this.words[i] &= set.words[i];
\r
175 this.recalculateWordsInUse ();
\r
177 Clazz.defineMethod (c$, "or",
\r
179 if (this === set) return;
\r
180 var wordsInCommon = Math.min (this.wordsInUse, set.wordsInUse);
\r
181 if (this.wordsInUse < set.wordsInUse) {
\r
182 this.ensureCapacity (set.wordsInUse);
\r
183 this.wordsInUse = set.wordsInUse;
\r
184 }for (var i = 0; i < wordsInCommon; i++) this.words[i] |= set.words[i];
\r
186 if (wordsInCommon < set.wordsInUse) System.arraycopy (set.words, wordsInCommon, this.words, wordsInCommon, this.wordsInUse - wordsInCommon);
\r
188 Clazz.defineMethod (c$, "xor",
\r
190 var wordsInCommon = Math.min (this.wordsInUse, set.wordsInUse);
\r
191 if (this.wordsInUse < set.wordsInUse) {
\r
192 this.ensureCapacity (set.wordsInUse);
\r
193 this.wordsInUse = set.wordsInUse;
\r
194 }for (var i = 0; i < wordsInCommon; i++) this.words[i] ^= set.words[i];
\r
196 if (wordsInCommon < set.wordsInUse) System.arraycopy (set.words, wordsInCommon, this.words, wordsInCommon, set.wordsInUse - wordsInCommon);
\r
197 this.recalculateWordsInUse ();
\r
199 Clazz.defineMethod (c$, "andNot",
\r
201 for (var i = Math.min (this.wordsInUse, set.wordsInUse) - 1; i >= 0; i--) this.words[i] &= ~set.words[i];
\r
203 this.recalculateWordsInUse ();
\r
205 Clazz.overrideMethod (c$, "hashCode",
\r
208 for (var i = this.wordsInUse; --i >= 0; ) h ^= this.words[i] * (i + 1);
\r
210 return ((h >> 32) ^ h);
\r
212 Clazz.defineMethod (c$, "size",
\r
214 return this.words.length * 32;
\r
216 Clazz.overrideMethod (c$, "equals",
\r
218 if (!(Clazz.instanceOf (obj, JU.BS))) return false;
\r
219 if (this === obj) return true;
\r
221 if (this.wordsInUse != set.wordsInUse) return false;
\r
222 for (var i = 0; i < this.wordsInUse; i++) if (this.words[i] != set.words[i]) return false;
\r
226 Clazz.overrideMethod (c$, "clone",
\r
228 if (!this.sizeIsSticky && this.wordsInUse != this.words.length) this.setLength (this.wordsInUse);
\r
229 return JU.BS.copy (this);
\r
231 Clazz.defineMethod (c$, "setLength",
\r
233 var a = Clazz.newIntArray (n, 0);
\r
234 System.arraycopy (this.words, 0, a, 0, Math.min (this.wordsInUse, n));
\r
237 Clazz.overrideMethod (c$, "toString",
\r
239 return JU.BS.escape (this, '{', '}');
\r
241 c$.copy = Clazz.defineMethod (c$, "copy",
\r
242 function (bitsetToCopy) {
\r
245 bs = Clazz.clone(bitsetToCopy);
\r
246 }var wordCount = bitsetToCopy.wordsInUse;
\r
247 if (wordCount == 0) {
\r
248 bs.words = JU.BS.emptyBitmap;
\r
250 bs.words = Clazz.newIntArray (bs.wordsInUse = wordCount, 0);
\r
251 System.arraycopy (bitsetToCopy.words, 0, bs.words, 0, wordCount);
\r
254 Clazz.defineMethod (c$, "cardinalityN",
\r
256 var n = this.cardinality ();
\r
257 for (var i = this.length (); --i >= max; ) if (this.get (i)) n--;
\r
261 Clazz.overrideMethod (c$, "toJSON",
\r
263 var numBits = (this.wordsInUse > 128) ? this.cardinality () : this.wordsInUse * 32;
\r
264 var b = JU.SB.newN (6 * numBits + 2);
\r
266 var i = this.nextSetBit (0);
\r
269 for (i = this.nextSetBit (i + 1); i >= 0; i = this.nextSetBit (i + 1)) {
\r
270 var endOfRun = this.nextClearBit (i);
\r
272 b.append (", ").appendI (i);
\r
273 } while (++i < endOfRun);
\r
276 return b.toString ();
\r
278 c$.escape = Clazz.defineMethod (c$, "escape",
\r
279 function (bs, chOpen, chClose) {
\r
280 if (bs == null) return chOpen + "{}" + chClose;
\r
281 var s = new JU.SB ();
\r
282 s.append (chOpen + "{");
\r
283 var imax = bs.length ();
\r
287 while (++i <= imax) {
\r
288 var isSet = bs.get (i);
\r
289 if (i == imax || iLast >= 0 && !isSet) {
\r
290 if (iLast >= 0 && iFirst != iLast) s.append ((iFirst == iLast - 1 ? " " : ":") + iLast);
\r
291 if (i == imax) break;
\r
295 s.append ((iFirst == -2 ? "" : " ") + i);
\r
299 s.append ("}").appendC (chClose);
\r
300 return s.toString ();
\r
302 c$.unescape = Clazz.defineMethod (c$, "unescape",
\r
306 if (str == null || (len = (str = str.trim ()).length) < 4 || str.equalsIgnoreCase ("({null})") || (ch = str.charAt (0)) != '(' && ch != '[' || str.charAt (len - 1) != (ch == '(' ? ')' : ']') || str.charAt (1) != '{' || str.indexOf ('}') != len - 2) return null;
\r
308 for (var i = len; --i >= 2; ) if (!JU.PT.isDigit (ch = str.charAt (i)) && ch != ' ' && ch != '\t' && ch != ':') return null;
\r
311 while (JU.PT.isDigit (str.charAt (--lastN))) {
\r
313 if (++lastN == len) lastN = 0;
\r
315 lastN = Integer.parseInt (str.substring (lastN, len));
\r
317 if (Clazz.exceptionOf (e, NumberFormatException)) {
\r
323 var bs = JU.BS.newN (lastN);
\r
327 for (var i = 2; i <= len; i++) {
\r
328 switch (ch = str.charAt (i)) {
\r
332 if (iThis < 0) break;
\r
333 if (iThis < lastN) return null;
\r
335 if (iPrev < 0) iPrev = iThis;
\r
336 bs.setBits (iPrev, iThis + 1);
\r
341 iPrev = lastN = iThis;
\r
345 if (JU.PT.isDigit (ch)) {
\r
346 if (iThis < 0) iThis = 0;
\r
347 iThis = (iThis * 10) + (ch.charCodeAt (0) - 48);
\r
350 return (iPrev >= 0 ? null : bs);
\r
352 Clazz.defineStatics (c$,
\r
353 "ADDRESS_BITS_PER_WORD", 5,
\r
354 "BITS_PER_WORD", 32,
\r
355 "WORD_MASK", 0xffffffff,
\r
356 "emptyBitmap", Clazz.newIntArray (0, 0));
\r