1 19 package bak.pcj.set; 20 21 import bak.pcj.ShortIterator; 22 import bak.pcj.ShortCollection; 23 import bak.pcj.util.Exceptions; 24 import java.util.NoSuchElementException ; 25 26 import java.io.Serializable ; 27 28 48 public class ShortBitSet extends AbstractShortSet implements ShortSortedSet, Cloneable , Serializable { 49 50 private static final int BITS_PER_LONG = 64; 51 private static final int BIT_MASK = 0x0000003F; 52 private static final int BIT_MASK_BITS = 6; 53 private static final int DEFAULT_CAPACITY = BITS_PER_LONG; 54 55 59 private long[] data; 60 61 65 private int size; 66 67 76 public ShortBitSet(short maximum) { 77 if (maximum < 0) 78 Exceptions.negativeArgument("maximum", String.valueOf(maximum)); 79 data = new long[1+longIndex(maximum)]; 80 size = 0; 81 } 82 83 86 public ShortBitSet() { 87 this((short)DEFAULT_CAPACITY); 88 } 89 90 105 public ShortBitSet(ShortCollection c) { 106 this(); 107 addAll(c); 108 } 109 110 127 public ShortBitSet(short[] a) { 128 this(amax(a)); 130 for (int i = 0; i < a.length; i++) 132 add(a[i]); 133 } 134 135 private static short amax(short[] a) { 136 short max = (short)0; 137 for (int i = 0; i < a.length; i++) 138 if (a[i] > max) max = a[i]; 139 return max; 140 } 141 142 146 private static int longIndex(int index) 147 { return index >> BIT_MASK_BITS; } 148 149 private static int bitIndex(int index) 150 { return index & BIT_MASK; } 151 152 private static long bit(int bitno) 153 { return 1L << bitno; } 154 155 private static int largestBitIndexOf(long v) { 156 if (v == 0L) 157 throw new IllegalArgumentException ("No elements left"); 158 int bitIndex = BITS_PER_LONG-1; 159 long bit = 1L << bitIndex; 160 while ((v & bit) == 0L) { 161 bitIndex--; 162 bit >>= 1; 163 } 164 return bitIndex; 165 } 166 167 private static int smallestBitIndexOf(long v) { 168 if (v == 0L) 169 throw new IllegalArgumentException ("No elements left"); 170 int bitIndex = 0; 171 long bit = 1L; 172 while ((v & bit) == 0L) { 173 bitIndex++; 174 bit <<= 1; 175 } 176 return bitIndex; 177 } 178 179 private static int countBits(long v) { 180 int count = 0; 181 int bitIndex = 0; 182 long bit = 1L; 183 do { 184 if ((v & bit) != 0L) 185 count++; 186 bitIndex++; 187 bit <<= 1; 188 } while (bitIndex < BITS_PER_LONG); 189 return count; 190 } 191 192 private static long lowMask(int n) { 193 long v = 0L; 194 for (int i = 0; i < n; i++) 195 v = (v << 1) | 1L; 196 return v; 197 } 198 199 private static long highMask(int n) { 200 return ~lowMask(n); 201 } 202 203 204 217 public void ensureCapacity(int maximum) { 218 if (maximum < 0) 219 Exceptions.negativeArgument("maximum", String.valueOf(maximum)); 220 int newcapacity = 1+longIndex(maximum); 221 if (data.length < newcapacity) { 222 long[] newdata = new long[newcapacity]; 223 System.arraycopy(data, 0, newdata, 0, data.length); 224 data = newdata; 225 } 226 } 227 228 232 236 public boolean add(short value) { 237 if (value < 0) 238 Exceptions.negativeArgument("value", String.valueOf(value)); 239 int longIndex = longIndex(value); 240 if (data.length < 1+longIndex) 241 ensureCapacity(value); 242 long bit = bit(bitIndex(value)); 243 boolean result = (data[longIndex] & bit) == 0; 244 if (result) 245 size++; 246 data[longIndex] |= bit; 247 return result; 248 } 249 250 public ShortIterator iterator() { 251 if (size == 0) 252 return new ShortIterator() { 253 public boolean hasNext() 254 { return false; } 255 public short next() 256 { Exceptions.endOfIterator(); throw new RuntimeException (); } 257 public void remove() 258 { Exceptions.noElementToRemove(); } 259 }; 260 return new ShortIterator() { 261 int nextLongIndex = nextLongIndex(0); 262 int nextBitIndex = nextLongIndex < data.length ? nextBitIndex(nextLongIndex, 0) : 0; 263 int lastValue = -1; 264 265 int nextLongIndex(int index) { 266 while (index < data.length && data[index] == 0) 267 index++; 268 return index; 269 } 270 271 int nextBitIndex(int longIndex, int bitIndex) { 272 long v = data[longIndex]; 273 long bit = 1L << bitIndex; 274 while (bitIndex < BITS_PER_LONG && (v & bit) == 0) { 275 bitIndex++; 276 bit <<= 1; 277 } 278 return bitIndex; 279 } 280 281 public boolean hasNext() { 282 return nextLongIndex < data.length; 283 } 284 285 public short next() { 286 if (!hasNext()) 287 Exceptions.endOfIterator(); 288 lastValue = (short)(nextLongIndex*BITS_PER_LONG + nextBitIndex); 289 290 nextBitIndex = nextBitIndex(nextLongIndex, nextBitIndex+1); 292 if (nextBitIndex == BITS_PER_LONG) { 293 nextLongIndex = nextLongIndex(nextLongIndex+1); 294 if (nextLongIndex < data.length) 295 nextBitIndex = nextBitIndex(nextLongIndex, 0); 296 } 297 return (short)lastValue; 298 } 299 300 public void remove() { 301 if (lastValue < 0) 302 Exceptions.noElementToRemove(); 303 ShortBitSet.this.remove((short)lastValue); 304 lastValue = -1; 305 } 306 307 }; 308 } 309 310 316 public void trimToSize() { 317 int n = data.length-1; 319 while (n >= 0 && data[n] == 0L) 320 n--; 321 if (n < data.length-1) { 323 long[] newdata = new long[1+n]; 324 System.arraycopy(data, 0, newdata, 0, newdata.length); 325 data = newdata; 326 } 327 } 328 329 336 public Object clone() { 337 try { 338 ShortBitSet c = (ShortBitSet)super.clone(); 339 c.data = new long[data.length]; 340 System.arraycopy(data, 0, c.data, 0, data.length); 341 return c; 342 } catch (CloneNotSupportedException e) { 343 Exceptions.cloning(); throw new RuntimeException (); 344 } 345 } 346 347 351 public void clear() { 352 for (int i = 0; i < data.length; i++) 353 data[i] = 0; 354 size = 0; 355 } 356 357 public boolean contains(short value) { 358 if (value < 0) 359 return false; 360 int longIndex = longIndex(value); 361 if (longIndex >= data.length) 362 return false; 363 long bit = bit(bitIndex(value)); 364 return (data[longIndex] & bit) != 0; 365 } 366 367 public boolean isEmpty() 368 { return size == 0; } 369 370 public boolean remove(short value) { 371 if (value < 0) 372 return false; 373 int longIndex = longIndex(value); 374 if (longIndex >= data.length) 375 return false; 376 long bit = bit(bitIndex(value)); 377 boolean result = (data[longIndex] & bit) != 0; 378 if (result) 379 size--; 380 data[longIndex] &= ~bit; 381 return result; 382 } 383 384 public int size() 385 { return size; } 386 387 391 private short firstFrom(short from) { 392 if (size == 0) 393 Exceptions.setNoFirst(); 394 int longIndex = longIndex(from); 395 if (longIndex >= data.length) 396 Exceptions.setNoFirst(); 397 long v = data[longIndex]; 398 v &= highMask(bitIndex(from)); 400 401 try { 402 for (;;) { 403 if (v != 0L) { 404 int bitIndex = smallestBitIndexOf(v); 405 return (short)(BITS_PER_LONG*longIndex + bitIndex); 406 } 407 v = data[++longIndex]; 408 } 409 } catch (IndexOutOfBoundsException e) { 410 Exceptions.setNoFirst(); throw new RuntimeException (); 411 } 412 } 413 414 417 public short first() { 418 return firstFrom((short)0); 419 } 420 421 private short lastFrom(short from) { 422 if (size == 0) 423 Exceptions.setNoLast(); 424 int longIndex = Math.min(longIndex(from), data.length-1); 425 long v = data[longIndex]; 426 v &= lowMask(bitIndex(from)+1); 428 try { 429 for (;;) { 430 if (v != 0L) { 431 int bitIndex = largestBitIndexOf(v); 432 return (short)(BITS_PER_LONG*longIndex + bitIndex); 433 } 434 v = data[--longIndex]; 435 } 436 } catch (IndexOutOfBoundsException e) { 437 Exceptions.setNoLast(); throw new RuntimeException (); 438 } 439 } 440 441 444 public short last() { 445 if (size == 0) 446 Exceptions.setNoLast(); 447 int longIndex = data.length-1; 448 while (data[longIndex] == 0) 450 longIndex--; 451 long v = data[longIndex]; 452 int bitIndex = BITS_PER_LONG-1; 453 long bit = 1L << bitIndex; 454 while ((v & bit) == 0) { 455 bitIndex--; 456 bit >>= 1; 457 } 458 return (short)(BITS_PER_LONG*longIndex + bitIndex); 459 } 460 461 464 public ShortSortedSet headSet(short to) { 465 return new SubSet(false, (short)0, true, to); 466 } 467 468 471 public ShortSortedSet tailSet(short from) { 472 return new SubSet(true, from, false, (short)0); 473 } 474 475 478 public ShortSortedSet subSet(short from, short to) { 479 return new SubSet(true, from, true, to); 480 } 481 482 private class SubSet extends AbstractShortSet implements ShortSortedSet, java.io.Serializable { 483 484 private boolean hasLowerBound; 485 private boolean hasUpperBound; 486 private short lowerBound; 487 private short upperBound; 488 489 SubSet(boolean hasLowerBound, short lowerBound, boolean hasUpperBound, short upperBound) { 490 if (hasLowerBound) { 491 if (lowerBound < 0) 492 Exceptions.negativeArgument("lower bound", String.valueOf(lowerBound)); 493 if (hasUpperBound) 494 if (upperBound < lowerBound) 495 Exceptions.invalidSetBounds(String.valueOf(lowerBound), String.valueOf(upperBound)); 496 } 497 this.hasLowerBound = hasLowerBound; 498 this.lowerBound = lowerBound; 499 this.hasUpperBound = hasUpperBound; 500 this.upperBound = upperBound; 501 } 502 503 public boolean add(short v) { 504 if (!inSubRange(v)) 505 Exceptions.valueNotInSubRange(String.valueOf(v)); 506 return ShortBitSet.this.add(v); 507 } 508 509 public boolean remove(short v) { 510 if (!inSubRange(v)) 511 Exceptions.valueNotInSubRange(String.valueOf(v)); 512 return ShortBitSet.this.remove(v); 513 } 514 515 public boolean contains(short v) { 516 return inSubRange(v) && ShortBitSet.this.contains(v); 517 } 518 519 class SubSetIterator implements ShortIterator { 520 int longIndexLow; 521 int longIndexHigh; 522 long vLow; 523 long vHigh; 524 boolean isEmpty; 525 526 int nextLongIndex; 527 int nextBitIndex; 528 int lastValue; 529 530 SubSetIterator() { 531 lastValue = -1; 532 isEmpty = false; 533 try { 534 longIndexLow = longIndex(first()); 535 } catch (NoSuchElementException e) { 536 isEmpty = true; 537 } 538 if (!isEmpty) { 539 longIndexHigh = longIndex(last()); 540 if (longIndexLow == longIndexHigh) { 541 long v = data[longIndexLow]; 542 if (hasLowerBound) 544 v &= highMask(bitIndex(lowerBound)); 545 if (hasUpperBound) 547 v &= lowMask(bitIndex(upperBound)); 548 size = countBits(v); 549 vLow = vHigh = v; 550 } else { 551 vLow = data[longIndexLow]; 553 if (hasLowerBound) 554 vLow &= highMask(bitIndex(lowerBound)); 555 556 vHigh = data[longIndexHigh]; 558 if (hasUpperBound) 559 vHigh &= lowMask(bitIndex(upperBound)); 560 } 561 nextLongIndex = longIndexLow; 562 nextBitIndex = smallestBitIndexOf(vLow); 563 } 564 } 565 566 long data(int longIndex) { 567 if (longIndex == longIndexLow) 568 return vLow; 569 if (longIndex == longIndexHigh) 570 return vHigh; 571 return data[longIndex]; 572 } 573 574 int nextLongIndex(int index) { 575 while (index <= longIndexHigh && data(index) == 0) 576 index++; 577 return index; 578 } 579 580 int nextBitIndex(int longIndex, int bitIndex) { 581 long v = data(longIndex); 582 long bit = 1L << bitIndex; 583 while (bitIndex < BITS_PER_LONG && (v & bit) == 0) { 584 bitIndex++; 585 bit <<= 1; 586 } 587 return bitIndex; 588 } 589 590 public boolean hasNext() { 591 return (!isEmpty) && (nextLongIndex <= longIndexHigh); 592 } 593 594 public short next() { 595 if (!hasNext()) 596 Exceptions.endOfIterator(); 597 lastValue = (short)(nextLongIndex*BITS_PER_LONG + nextBitIndex); 598 599 nextBitIndex = nextBitIndex(nextLongIndex, nextBitIndex+1); 601 if (nextBitIndex == BITS_PER_LONG) { 602 nextLongIndex = nextLongIndex(nextLongIndex+1); 603 if (nextLongIndex < data.length) 604 nextBitIndex = nextBitIndex(nextLongIndex, 0); 605 } 606 return (short)lastValue; 607 } 608 609 public void remove() { 610 if (lastValue < 0) 611 Exceptions.noElementToRemove(); 612 ShortBitSet.this.remove((short)lastValue); 613 lastValue = -1; 614 } 615 } 616 617 public ShortIterator iterator() { 618 return new SubSetIterator(); 619 } 620 621 public int size() { 622 if (ShortBitSet.this.size() == 0) 623 return 0; 624 int size; 625 int longIndexLow; 626 try { 627 longIndexLow = longIndex(first()); 628 } catch (NoSuchElementException e) { 629 return 0; 630 } 631 int longIndexHigh = longIndex(last()); 632 if (longIndexLow == longIndexHigh) { 633 long v = data[longIndexLow]; 634 if (hasLowerBound) 636 v &= highMask(bitIndex(lowerBound)); 637 if (hasUpperBound) 639 v &= lowMask(bitIndex(upperBound)); 640 size = countBits(v); 641 } else { 642 long vLow = data[longIndexLow]; 644 if (hasLowerBound) 645 vLow &= highMask(bitIndex(lowerBound)); 646 647 long vHigh = data[longIndexHigh]; 649 if (hasUpperBound) 650 vHigh &= lowMask(bitIndex(upperBound)); 651 652 size = countBits(vLow) + countBits(vHigh); 653 for (int i = longIndexLow+1; i < longIndexHigh; i++) 654 size += countBits(data[i]); 655 } 656 return size; 657 } 658 659 public short first() { 660 short first = firstFrom(hasLowerBound ? lowerBound : 0); 661 if (hasUpperBound && first >= upperBound) 662 Exceptions.setNoFirst(); 663 return first; 664 } 665 666 public short last() { 667 short last = lastFrom(hasUpperBound ? (short)(upperBound-1) : ShortBitSet.this.last()); 668 if (hasLowerBound && last < lowerBound) 669 Exceptions.setNoLast(); 670 return last; 671 } 672 673 public ShortSortedSet headSet(short to) { 674 if (!inSubRange(to)) 675 Exceptions.invalidUpperBound(String.valueOf(to)); 676 return new SubSet(hasLowerBound, lowerBound, true, to); 677 } 678 679 public ShortSortedSet tailSet(short from) { 680 if (!inSubRange(from)) 681 Exceptions.invalidLowerBound(String.valueOf(from)); 682 return new SubSet(true, from, hasUpperBound, upperBound); 683 } 684 685 public ShortSortedSet subSet(short from, short to) { 686 if (!inSubRange(from)) 687 Exceptions.invalidLowerBound(String.valueOf(from)); 688 if (!inSubRange(to)) 689 Exceptions.invalidUpperBound(String.valueOf(to)); 690 return new SubSet(true, from, true, to); 691 } 692 693 private boolean inSubRange(short v) { 694 if (hasLowerBound && v < lowerBound) 695 return false; 696 if (hasUpperBound && v >= upperBound) 697 return false; 698 return true; 699 } 700 701 } 702 703 } | Popular Tags |