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