site/j2s/JU/BS.js

   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 () {
   4 this.words = null;
   5 this.wordsInUse = 0;
   6 this.sizeIsSticky = false;
   7 Clazz.instantialize (this, arguments);
   8 }, JU, "BS", null, [Cloneable, javajs.api.JSONEncodable]);
   9 c$.wordIndex = Clazz.defineMethod (c$, "wordIndex",
  10  function (bitIndex) {
  11 return bitIndex >> 5;
  12 }, "~N");
  13 Clazz.defineMethod (c$, "recalculateWordsInUse",
  14  function () {
  15 var i;
  16 for (i = this.wordsInUse - 1; i >= 0; i--) if (this.words[i] != 0) break;
  17
  18 this.wordsInUse = i + 1;
  19 });
  20 Clazz.makeConstructor (c$,
  21 function () {
  22 this.initWords (32);
  23 this.sizeIsSticky = false;
  24 });
  25 c$.newN = Clazz.defineMethod (c$, "newN",
  26 function (nbits) {
  27 var bs =  new JU.BS ();
  28 bs.init (nbits);
  29 return bs;
  30 }, "~N");
  31 Clazz.defineMethod (c$, "init",
  32  function (nbits) {
  33 if (nbits < 0) throw  new NegativeArraySizeException ("nbits < 0: " + nbits);
  34 this.initWords (nbits);
  35 this.sizeIsSticky = true;
  36 }, "~N");
  37 Clazz.defineMethod (c$, "initWords",
  38  function (nbits) {
  39 this.words =  Clazz.newIntArray (JU.BS.wordIndex (nbits - 1) + 1, 0);
  40 }, "~N");
  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;
  47 }}, "~N");
  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;
  54 }}, "~N");
  55 Clazz.defineMethod (c$, "set",
  56 function (bitIndex) {
  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);
  61 }, "~N");
  62 Clazz.defineMethod (c$, "setBitTo",
  63 function (bitIndex, value) {
  64 if (value) this.set (bitIndex);
  65  else this.clear (bitIndex);
  66 }, "~N,~B");
  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);
  77 } else {
  78 this.words[startWordIndex] |= firstWordMask;
  79 for (var i = startWordIndex + 1; i < endWordIndex; i++) this.words[i] = -1;
  80
  81 this.words[endWordIndex] |= lastWordMask;
  82 }}, "~N,~N");
  83 Clazz.defineMethod (c$, "clear",
  84 function (bitIndex) {
  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 ();
  90 }, "~N");
  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);
 104 } else {
 105 this.words[startWordIndex] &= ~firstWordMask;
 106 for (var i = startWordIndex + 1; i < endWordIndex; i++) this.words[i] = 0;
 107
 108 this.words[endWordIndex] &= ~lastWordMask;
 109 }this.recalculateWordsInUse ();
 110 }, "~N,~N");
 111 Clazz.defineMethod (c$, "clearAll",
 112 function () {
 113 while (this.wordsInUse > 0) this.words[--this.wordsInUse] = 0;
 114
 115 });
 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);
 121 }, "~N");
 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);
 128 while (true) {
 129 if (word != 0) return (u * 32) + Integer.numberOfTrailingZeros (word);
 130 if (++u == this.wordsInUse) return -1;
 131 word = this.words[u];
 132 }
 133 }, "~N");
 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);
 140 while (true) {
 141 if (word != 0) return (u * 32) + Integer.numberOfTrailingZeros (word);
 142 if (++u == this.wordsInUse) return this.wordsInUse * 32;
 143 word = ~this.words[u];
 144 }
 145 }, "~N");
 146 Clazz.defineMethod (c$, "length",
 147 function () {
 148 if (this.wordsInUse == 0) return 0;
 149 return 32 * (this.wordsInUse - 1) + (32 - Integer.numberOfLeadingZeros (this.words[this.wordsInUse - 1]));
 150 });
 151 Clazz.defineMethod (c$, "isEmpty",
 152 function () {
 153 return this.wordsInUse == 0;
 154 });
 155 Clazz.defineMethod (c$, "intersects",
 156 function (set) {
 157 for (var i = Math.min (this.wordsInUse, set.wordsInUse) - 1; i >= 0; i--) if ((this.words[i] & set.words[i]) != 0) return true;
 158
 159 return false;
 160 }, "JU.BS");
 161 Clazz.defineMethod (c$, "cardinality",
 162 function () {
 163 var sum = 0;
 164 for (var i = 0; i < this.wordsInUse; i++) sum += Integer.bitCount (this.words[i]);
 165
 166 return sum;
 167 });
 168 Clazz.defineMethod (c$, "and",
 169 function (set) {
 170 if (this === set) return;
 171 while (this.wordsInUse > set.wordsInUse) this.words[--this.wordsInUse] = 0;
 172
 173 for (var i = 0; i < this.wordsInUse; i++) this.words[i] &= set.words[i];
 174
 175 this.recalculateWordsInUse ();
 176 }, "JU.BS");
 177 Clazz.defineMethod (c$, "or",
 178 function (set) {
 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];
 185
 186 if (wordsInCommon < set.wordsInUse) System.arraycopy (set.words, wordsInCommon, this.words, wordsInCommon, this.wordsInUse - wordsInCommon);
 187 }, "JU.BS");
 188 Clazz.defineMethod (c$, "xor",
 189 function (set) {
 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];
 195
 196 if (wordsInCommon < set.wordsInUse) System.arraycopy (set.words, wordsInCommon, this.words, wordsInCommon, set.wordsInUse - wordsInCommon);
 197 this.recalculateWordsInUse ();
 198 }, "JU.BS");
 199 Clazz.defineMethod (c$, "andNot",
 200 function (set) {
 201 for (var i = Math.min (this.wordsInUse, set.wordsInUse) - 1; i >= 0; i--) this.words[i] &= ~set.words[i];
 202
 203 this.recalculateWordsInUse ();
 204 }, "JU.BS");
 205 Clazz.overrideMethod (c$, "hashCode",
 206 function () {
 207 var h = 1234;
 208 for (var i = this.wordsInUse; --i >= 0; ) h ^= this.words[i] * (i + 1);
 209
 210 return ((h >> 32) ^ h);
 211 });
 212 Clazz.defineMethod (c$, "size",
 213 function () {
 214 return this.words.length * 32;
 215 });
 216 Clazz.overrideMethod (c$, "equals",
 217 function (obj) {
 218 if (!(Clazz.instanceOf (obj, JU.BS))) return false;
 219 if (this === obj) return true;
 220 var set = obj;
 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;
 223
 224 return true;
 225 }, "~O");
 226 Clazz.overrideMethod (c$, "clone",
 227 function () {
 228 if (!this.sizeIsSticky && this.wordsInUse != this.words.length) this.setLength (this.wordsInUse);
 229 return JU.BS.copy (this);
 230 });
 231 Clazz.defineMethod (c$, "setLength",
 232  function (n) {
 233 var a =  Clazz.newIntArray (n, 0);
 234 System.arraycopy (this.words, 0, a, 0, Math.min (this.wordsInUse, n));
 235 this.words = a;
 236 }, "~N");
 237 Clazz.overrideMethod (c$, "toString",
 238 function () {
 239 return JU.BS.escape (this, '{', '}');
 240 });
 241 c$.copy = Clazz.defineMethod (c$, "copy",
 242 function (bitsetToCopy) {
 243 var bs;
 244 {
 245 bs = Clazz.clone(bitsetToCopy);
 246 }var wordCount = bitsetToCopy.wordsInUse;
 247 if (wordCount == 0) {
 248 bs.words = JU.BS.emptyBitmap;
 249 } else {
 250 bs.words =  Clazz.newIntArray (bs.wordsInUse = wordCount, 0);
 251 System.arraycopy (bitsetToCopy.words, 0, bs.words, 0, wordCount);
 252 }return bs;
 253 }, "JU.BS");
 254 Clazz.defineMethod (c$, "cardinalityN",
 255 function (max) {
 256 var n = this.cardinality ();
 257 for (var i = this.length (); --i >= max; ) if (this.get (i)) n--;
 258
 259 return n;
 260 }, "~N");
 261 Clazz.overrideMethod (c$, "toJSON",
 262 function () {
 263 var numBits = (this.wordsInUse > 128) ? this.cardinality () : this.wordsInUse * 32;
 264 var b = JU.SB.newN (6 * numBits + 2);
 265 b.appendC ('[');
 266 var i = this.nextSetBit (0);
 267 if (i != -1) {
 268 b.appendI (i);
 269 for (i = this.nextSetBit (i + 1); i >= 0; i = this.nextSetBit (i + 1)) {
 270 var endOfRun = this.nextClearBit (i);
 271 do {
 272 b.append (", ").appendI (i);
 273 } while (++i < endOfRun);
 274 }
 275 }b.appendC (']');
 276 return b.toString ();
 277 });
 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 ();
 284 var iLast = -1;
 285 var iFirst = -2;
 286 var i = -1;
 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;
 292 iLast = -1;
 293 }if (bs.get (i)) {
 294 if (iLast < 0) {
 295 s.append ((iFirst == -2 ? "" : " ") + i);
 296 iFirst = i;
 297 }iLast = i;
 298 }}
 299 s.append ("}").appendC (chClose);
 300 return s.toString ();
 301 }, "JU.BS,~S,~S");
 302 c$.unescape = Clazz.defineMethod (c$, "unescape",
 303 function (str) {
 304 var ch;
 305 var len;
 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;
 307 len -= 2;
 308 for (var i = len; --i >= 2; ) if (!JU.PT.isDigit (ch = str.charAt (i)) && ch != ' ' && ch != '\t' && ch != ':') return null;
 309
 310 var lastN = len;
 311 while (JU.PT.isDigit (str.charAt (--lastN))) {
 312 }
 313 if (++lastN == len) lastN = 0;
 314  else try {
 315 lastN = Integer.parseInt (str.substring (lastN, len));
 316 } catch (e) {
 317 if (Clazz.exceptionOf (e, NumberFormatException)) {
 318 return null;
 319 } else {
 320 throw e;
 321 }
 322 }
 323 var bs = JU.BS.newN (lastN);
 324 lastN = -1;
 325 var iPrev = -1;
 326 var iThis = -2;
 327 for (var i = 2; i <= len; i++) {
 328 switch (ch = str.charAt (i)) {
 329 case '\t':
 330 case ' ':
 331 case '}':
 332 if (iThis < 0) break;
 333 if (iThis < lastN) return null;
 334 lastN = iThis;
 335 if (iPrev < 0) iPrev = iThis;
 336 bs.setBits (iPrev, iThis + 1);
 337 iPrev = -1;
 338 iThis = -2;
 339 break;
 340 case ':':
 341 iPrev = lastN = iThis;
 342 iThis = -2;
 343 break;
 344 default:
 345 if (JU.PT.isDigit (ch)) {
 346 if (iThis < 0) iThis = 0;
 347 iThis = (iThis * 10) + (ch.charCodeAt (0) - 48);
 348 }}
 349 }
 350 return (iPrev >= 0 ? null : bs);
 351 }, "~S");
 352 Clazz.defineStatics (c$,
 353 "ADDRESS_BITS_PER_WORD", 5,
 354 "BITS_PER_WORD", 32,
 355 "WORD_MASK", 0xffffffff,
 356 "emptyBitmap",  Clazz.newIntArray (0, 0));
 357 });