001/* 002// This software is subject to the terms of the Eclipse Public License v1.0 003// Agreement, available at the following URL: 004// http://www.eclipse.org/legal/epl-v10.html. 005// You must accept the terms of that agreement to use this software. 006// 007// Copyright (C) 2001-2005 Julian Hyde 008// Copyright (C) 2005-2011 Pentaho and others 009// All Rights Reserved. 010// 011// jhyde, 30 August, 2001 012*/ 013package mondrian.rolap; 014 015import java.io.Serializable; 016import java.util.BitSet; 017import java.util.Iterator; 018 019/** 020 * Represents a set of bits. 021 * 022 * <p>Unlike {@link java.util.BitSet}, the number of bits cannot be changed 023 * after the BitKey is created. This allows us to optimize. 024 * 025 * <p>If you have a collection of immutable objects, each of which has a unique 026 * positive number and you wish to do comparisons between subsets of those 027 * objects testing for equality, then encoding the subsets as BitKeys is very 028 * efficient. 029 * 030 * <p>There are two implementations that target groups of objects with maximum 031 * number less than 64 and less than 128; and there is one implements that is 032 * general for any positive number. 033 * 034 * <p>One caution: if the maximum number assigned to one of the 035 * objects is large, then this representation might be sparse and therefore 036 * not efficient. 037 * 038 * @author Richard M. Emberson 039 */ 040public interface BitKey 041 extends Serializable, Comparable<BitKey>, Iterable<Integer> 042{ 043 /** 044 * The BitKey with no bits set. 045 */ 046 BitKey EMPTY = Factory.makeBitKey(0); 047 048 /** 049 * Sets the bit at the specified index to the specified value. 050 */ 051 void set(int bitIndex, boolean value); 052 053 /** 054 * Sets the bit at the specified index to <code>true</code>. 055 */ 056 void set(int bitIndex); 057 058 /** 059 * Returns the value of the bit with the specified index. The value 060 * is <code>true</code> if the bit with the index <code>bitIndex</code> 061 * is currently set in this <code>BitKey</code>; otherwise, the result 062 * is <code>false</code>. 063 */ 064 boolean get(int bitIndex); 065 066 /** 067 * Sets the bit specified by the index to <code>false</code>. 068 */ 069 void clear(int bitIndex); 070 071 /** 072 * Sets all of the bits in this BitKey to <code>false</code>. 073 */ 074 void clear(); 075 076 /** 077 * Is every bit set in the parameter <code>bitKey</code> also set in 078 * <code>this</code>. 079 * If one switches <code>this</code> with the parameter <code>bitKey</code> 080 * one gets the equivalent of isSubSetOf. 081 * 082 * @param bitKey Bit key 083 */ 084 boolean isSuperSetOf(BitKey bitKey); 085 086 /** 087 * Or the parameter <code>BitKey</code> with <code>this</code>. 088 * 089 * @param bitKey Bit key 090 */ 091 BitKey or(BitKey bitKey); 092 093 /** 094 * XOr the parameter <code>BitKey</code> with <code>this</code>. 095 * 096 * @param bitKey Bit key 097 */ 098 BitKey orNot(BitKey bitKey); 099 100 /** 101 * Returns the boolean AND of this bitkey and the given bitkey. 102 * 103 * @param bitKey Bit key 104 */ 105 BitKey and(BitKey bitKey); 106 107 /** 108 * Returns a <code>BitKey</code> containing all of the bits in this 109 * <code>BitSet</code> whose corresponding 110 * bit is NOT set in the specified <code>BitSet</code>. 111 */ 112 BitKey andNot(BitKey bitKey); 113 114 /** 115 * Returns a copy of this BitKey. 116 * 117 * @return copy of BitKey 118 */ 119 BitKey copy(); 120 121 /** 122 * Returns an empty BitKey of the same type. This is the same 123 * as calling {@link #copy} followed by {@link #clear()}. 124 * 125 * @return BitKey of same type 126 */ 127 BitKey emptyCopy(); 128 129 /** 130 * Returns true if this <code>BitKey</code> contains no bits that are set 131 * to <code>true</code>. 132 */ 133 boolean isEmpty(); 134 135 /** 136 * Returns whether this BitKey has any bits in common with a given BitKey. 137 */ 138 boolean intersects(BitKey bitKey); 139 140 /** 141 * Returns a {@link BitSet} with the same contents as this BitKey. 142 */ 143 BitSet toBitSet(); 144 145 /** 146 * An Iterator over the bit positions. 147 * For example, if the BitKey had positions 3 and 4 set, then 148 * the Iterator would return the values 3 and then 4. The bit 149 * positions returned by the iterator are in the order, from 150 * smallest to largest, as they are set in the BitKey. 151 */ 152 Iterator<Integer> iterator(); 153 154 /** 155 * Returns the index of the first bit that is set to <code>true</code> 156 * that occurs on or after the specified starting index. If no such 157 * bit exists then -1 is returned. 158 * 159 * To iterate over the <code>true</code> bits in a <code>BitKey</code>, 160 * use the following loop: 161 * 162 * <pre> 163 * for (int i = bk.nextSetBit(0); i >= 0; i = bk.nextSetBit(i + 1)) { 164 * // operate on index i here 165 * }</pre> 166 * 167 * @param fromIndex the index to start checking from (inclusive) 168 * @return the index of the next set bit 169 * @throws IndexOutOfBoundsException if the specified index is negative 170 */ 171 int nextSetBit(int fromIndex); 172 173 /** 174 * Returns the number of bits set. 175 * 176 * @return Number of bits set 177 */ 178 int cardinality(); 179 180 public abstract class Factory { 181 182 /** 183 * Creates a {@link BitKey} with a capacity for a given number of bits. 184 * @param size Number of bits in key 185 */ 186 public static BitKey makeBitKey(int size) { 187 return makeBitKey(size, false); 188 } 189 190 /** 191 * Creates a {@link BitKey} with a capacity for a given number of bits. 192 * @param size Number of bits in key 193 * @param init The default value of all bits. 194 */ 195 public static BitKey makeBitKey(int size, boolean init) { 196 if (size < 0) { 197 String msg = "Negative size \"" + size + "\" not allowed"; 198 throw new IllegalArgumentException(msg); 199 } 200 final BitKey bk; 201 if (size < 64) { 202 bk = new BitKey.Small(); 203 } else if (size < 128) { 204 bk = new BitKey.Mid128(); 205 } else { 206 bk = new BitKey.Big(size); 207 } 208 if (init) { 209 for (int i = 0; i < size; i++) { 210 bk.set(i, init); 211 } 212 } 213 return bk; 214 } 215 216 /** 217 * Creates a {@link BitKey} with the same contents as a {@link BitSet}. 218 */ 219 public static BitKey makeBitKey(BitSet bitSet) { 220 BitKey bitKey = makeBitKey(bitSet.length()); 221 for (int i = bitSet.nextSetBit(0); 222 i >= 0; 223 i = bitSet.nextSetBit(i + 1)) 224 { 225 bitKey.set(i); 226 } 227 return bitKey; 228 } 229 } 230 231 /** 232 * Abstract implementation of {@link BitKey}. 233 */ 234 abstract class AbstractBitKey implements BitKey { 235 private static final long serialVersionUID = -2942302671676103450L; 236 // chunk is a long, which has 64 bits 237 protected static final int ChunkBitCount = 6; 238 protected static final int Mask = 63; 239 protected static final long WORD_MASK = 0xffffffffffffffffL; 240 241 /** 242 * Creates a chunk containing a single bit. 243 */ 244 protected static long bit(int pos) { 245 return (1L << (pos & Mask)); 246 } 247 248 /** 249 * Returns which chunk a given bit falls into. 250 * Bits 0 to 63 fall in chunk 0, bits 64 to 127 fall into chunk 1. 251 */ 252 protected static int chunkPos(int size) { 253 return (size >> ChunkBitCount); 254 } 255 256 /** 257 * Returns the number of chunks required for a given number of bits. 258 * 259 * <p>0 bits requires 0 chunks; 1 - 64 bits requires 1 chunk; etc. 260 */ 261 protected static int chunkCount(int size) { 262 return (size + 63) >> ChunkBitCount; 263 } 264 265 /** 266 * Returns the number of one-bits in the two's complement binary 267 * representation of the specified <tt>long</tt> value. This function 268 * is sometimes referred to as the <i>population count</i>. 269 * 270 * <p>(Copied from {@link java.lang.Long#bitCount(long)}, which was 271 * introduced in JDK 1.5, but we need the functionality in JDK 1.4.) 272 * 273 * @return the number of one-bits in the two's complement binary 274 * representation of the specified <tt>long</tt> value. 275 * @since 1.5 276 */ 277 protected static int bitCount(long i) { 278 i = i - ((i >>> 1) & 0x5555555555555555L); 279 i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L); 280 i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL; 281 i = i + (i >>> 8); 282 i = i + (i >>> 16); 283 i = i + (i >>> 32); 284 return (int)i & 0x7f; 285 } 286 287 public final void set(int pos, boolean value) { 288 if (value) { 289 set(pos); 290 } else { 291 clear(pos); 292 } 293 } 294 295 /** 296 * Copies a byte into a bit set at a particular position. 297 * 298 * @param bitSet Bit set 299 * @param pos Position 300 * @param x Byte 301 */ 302 protected static void copyFromByte(BitSet bitSet, int pos, byte x) 303 { 304 if (x == 0) { 305 return; 306 } 307 if ((x & 0x01) != 0) { 308 bitSet.set(pos, true); 309 } 310 ++pos; 311 if ((x & 0x02) != 0) { 312 bitSet.set(pos, true); 313 } 314 ++pos; 315 if ((x & 0x04) != 0) { 316 bitSet.set(pos, true); 317 } 318 ++pos; 319 if ((x & 0x08) != 0) { 320 bitSet.set(pos, true); 321 } 322 ++pos; 323 if ((x & 0x10) != 0) { 324 bitSet.set(pos, true); 325 } 326 ++pos; 327 if ((x & 0x20) != 0) { 328 bitSet.set(pos, true); 329 } 330 ++pos; 331 if ((x & 0x40) != 0) { 332 bitSet.set(pos, true); 333 } 334 ++pos; 335 if ((x & 0x80) != 0) { 336 bitSet.set(pos, true); 337 } 338 } 339 340 /** 341 * Copies a {@code long} value (interpreted as 64 bits) into a bit set. 342 * 343 * @param bitSet Bit set 344 * @param pos Position 345 * @param x Byte 346 */ 347 protected static void copyFromLong( 348 final BitSet bitSet, 349 int pos, 350 long x) 351 { 352 while (x != 0) { 353 copyFromByte(bitSet, pos, (byte) (x & 0xff)); 354 x >>>= 8; 355 pos += 8; 356 } 357 } 358 359 protected IllegalArgumentException createException(BitKey bitKey) { 360 final String msg = (bitKey == null) 361 ? "Null BitKey" 362 : "Bad BitKey type: " + bitKey.getClass().getName(); 363 return new IllegalArgumentException(msg); 364 } 365 366 /** 367 * Compares a pair of {@code long} arrays, using unsigned comparison 368 * semantics and padding to the left with 0s. 369 * 370 * <p>Values are treated as unsigned for the purposes of comparison. 371 * 372 * <p>If the arrays have different lengths, the shorter is padded with 373 * 0s. 374 * 375 * @param a1 First array 376 * @param a2 Second array 377 * @return -1 if a1 compares less to a2, 378 * 0 if a1 is equal to a2, 379 * 1 if a1 is greater than a2 380 */ 381 static int compareUnsignedArrays(long[] a1, long[] a2) { 382 int i1 = a1.length - 1; 383 int i2 = a2.length - 1; 384 if (i1 > i2) { 385 do { 386 if (a1[i1] != 0) { 387 return 1; 388 } 389 --i1; 390 } while (i1 > i2); 391 } else if (i2 > i1) { 392 do { 393 if (a2[i2] != 0) { 394 return -1; 395 } 396 --i2; 397 } while (i2 > i1); 398 } 399 assert i1 == i2; 400 for (; i1 >= 0; --i1) { 401 int c = compareUnsigned(a1[i1], a2[i1]); 402 if (c != 0) { 403 return c; 404 } 405 } 406 return 0; 407 } 408 409 /** 410 * Performs unsigned comparison on two {@code long} values. 411 * 412 * @param i1 First value 413 * @param i2 Second value 414 * @return -1 if i1 is less than i2, 415 * 1 if i1 is greater than i2, 416 * 0 if i1 equals i2 417 */ 418 static int compareUnsigned(long i1, long i2) { 419 // We want to do unsigned comparison. 420 // Signed comparison returns the correct result except 421 // if i1<0 & i2>=0 422 // or i1>=0 & i2<0 423 if (i1 == i2) { 424 return 0; 425 } else if ((i1 < 0) == (i2 < 0)) { 426 // Same signs, signed comparison gives the right result 427 return i1 < i2 ? -1 : 1; 428 } else { 429 // Different signs, use signed comparison and invert the result 430 return i1 < i2 ? 1 : -1; 431 } 432 } 433 } 434 435 /** 436 * Implementation of {@link BitKey} for bit counts less than 64. 437 */ 438 public class Small extends AbstractBitKey { 439 private static final long serialVersionUID = -7891880560056571197L; 440 private long bits; 441 442 /** 443 * Creates a Small with no bits set. 444 */ 445 private Small() { 446 } 447 448 /** 449 * Creates a Small and initializes it to the 64 bit value. 450 * 451 * @param bits 64 bit value 452 */ 453 private Small(long bits) { 454 this.bits = bits; 455 } 456 457 public void set(int pos) { 458 if (pos < 64) { 459 bits |= bit(pos); 460 } else { 461 throw new IllegalArgumentException( 462 "pos " + pos + " exceeds capacity 64"); 463 } 464 } 465 466 public boolean get(int pos) { 467 return pos < 64 && ((bits & bit(pos)) != 0); 468 } 469 470 public void clear(int pos) { 471 bits &= ~bit(pos); 472 } 473 474 public void clear() { 475 bits = 0; 476 } 477 478 public int cardinality() { 479 return bitCount(bits); 480 } 481 482 private void or(long bits) { 483 this.bits |= bits; 484 } 485 486 private void orNot(long bits) { 487 this.bits ^= bits; 488 } 489 490 private void and(long bits) { 491 this.bits &= bits; 492 } 493 494 public BitKey or(BitKey bitKey) { 495 if (bitKey instanceof BitKey.Small) { 496 final BitKey.Small other = (BitKey.Small) bitKey; 497 final BitKey.Small bk = (BitKey.Small) copy(); 498 bk.or(other.bits); 499 return bk; 500 501 } else if (bitKey instanceof BitKey.Mid128) { 502 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 503 final BitKey.Mid128 bk = (BitKey.Mid128) other.copy(); 504 bk.or(this.bits, 0); 505 return bk; 506 507 } else if (bitKey instanceof BitKey.Big) { 508 final BitKey.Big other = (BitKey.Big) bitKey; 509 final BitKey.Big bk = (BitKey.Big) other.copy(); 510 bk.or(this.bits); 511 return bk; 512 } 513 514 throw createException(bitKey); 515 } 516 517 public BitKey orNot(BitKey bitKey) { 518 if (bitKey instanceof BitKey.Small) { 519 final BitKey.Small other = (BitKey.Small) bitKey; 520 final BitKey.Small bk = (BitKey.Small) copy(); 521 bk.orNot(other.bits); 522 return bk; 523 524 } else if (bitKey instanceof BitKey.Mid128) { 525 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 526 final BitKey.Mid128 bk = (BitKey.Mid128) other.copy(); 527 bk.orNot(this.bits, 0); 528 return bk; 529 530 } else if (bitKey instanceof BitKey.Big) { 531 final BitKey.Big other = (BitKey.Big) bitKey; 532 final BitKey.Big bk = (BitKey.Big) other.copy(); 533 bk.orNot(this.bits); 534 return bk; 535 } 536 537 throw createException(bitKey); 538 } 539 540 public BitKey and(BitKey bitKey) { 541 if (bitKey instanceof BitKey.Small) { 542 final BitKey.Small other = (BitKey.Small) bitKey; 543 final BitKey.Small bk = (BitKey.Small) copy(); 544 bk.and(other.bits); 545 return bk; 546 547 } else if (bitKey instanceof BitKey.Mid128) { 548 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 549 final BitKey.Small bk = (BitKey.Small) copy(); 550 bk.and(other.bits0); 551 return bk; 552 553 } else if (bitKey instanceof BitKey.Big) { 554 final BitKey.Big other = (BitKey.Big) bitKey; 555 final BitKey.Small bk = (BitKey.Small) copy(); 556 bk.and(other.bits[0]); 557 return bk; 558 } 559 560 throw createException(bitKey); 561 } 562 563 public BitKey andNot(BitKey bitKey) { 564 if (bitKey instanceof BitKey.Small) { 565 final BitKey.Small other = (BitKey.Small) bitKey; 566 final BitKey.Small bk = (BitKey.Small) copy(); 567 bk.andNot(other.bits); 568 return bk; 569 570 } else if (bitKey instanceof BitKey.Mid128) { 571 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 572 final BitKey.Small bk = (BitKey.Small) copy(); 573 bk.andNot(other.bits0); 574 return bk; 575 576 } else if (bitKey instanceof BitKey.Big) { 577 final BitKey.Big other = (BitKey.Big) bitKey; 578 final BitKey.Small bk = (BitKey.Small) copy(); 579 bk.andNot(other.bits[0]); 580 return bk; 581 } 582 583 throw createException(bitKey); 584 } 585 586 private void andNot(long bits) { 587 this.bits &= ~bits; 588 } 589 590 public boolean isSuperSetOf(BitKey bitKey) { 591 if (bitKey instanceof BitKey.Small) { 592 BitKey.Small other = (BitKey.Small) bitKey; 593 return ((this.bits | other.bits) == this.bits); 594 595 } else if (bitKey instanceof BitKey.Mid128) { 596 BitKey.Mid128 other = (BitKey.Mid128) bitKey; 597 return ((this.bits | other.bits0) == this.bits) 598 && (other.bits1 == 0); 599 600 } else if (bitKey instanceof BitKey.Big) { 601 BitKey.Big other = (BitKey.Big) bitKey; 602 if ((this.bits | other.bits[0]) != this.bits) { 603 return false; 604 } else { 605 for (int i = 1; i < other.bits.length; i++) { 606 if (other.bits[i] != 0) { 607 return false; 608 } 609 } 610 return true; 611 } 612 } 613 return false; 614 } 615 616 public boolean intersects(BitKey bitKey) { 617 if (bitKey instanceof BitKey.Small) { 618 BitKey.Small other = (BitKey.Small) bitKey; 619 return (this.bits & other.bits) != 0; 620 621 } else if (bitKey instanceof BitKey.Mid128) { 622 BitKey.Mid128 other = (BitKey.Mid128) bitKey; 623 return (this.bits & other.bits0) != 0; 624 625 } else if (bitKey instanceof BitKey.Big) { 626 BitKey.Big other = (BitKey.Big) bitKey; 627 return (this.bits & other.bits[0]) != 0; 628 } 629 return false; 630 } 631 632 public BitSet toBitSet() { 633 final BitSet bitSet = new BitSet(64); 634 long x = bits; 635 int pos = 0; 636 while (x != 0) { 637 copyFromByte(bitSet, pos, (byte) (x & 0xff)); 638 x >>>= 8; 639 pos += 8; 640 } 641 return bitSet; 642 } 643 644 /** 645 * To say that I am happy about this algorithm (or the variations 646 * of the algorithm used for the Mid128 and Big BitKey implementations) 647 * would be a stretch. It works but there has to be a more 648 * elegant and faster one but this is the best I could come up 649 * with in a couple of hours. 650 * 651 */ 652 public Iterator<Integer> iterator() { 653 return new Iterator<Integer>() { 654 int pos = -1; 655 long bits = Small.this.bits; 656 public boolean hasNext() { 657 if (bits == 0) { 658 return false; 659 } 660 // This is a special case 661 // Long.MIN_VALUE == -9223372036854775808 662 if (bits == Long.MIN_VALUE) { 663 pos = 63; 664 bits = 0; 665 return true; 666 } 667 long b = (bits & -bits); 668 if (b == 0) { 669 // should never happen 670 return false; 671 } 672 int delta = 0; 673 while (b >= 256) { 674 b = (b >> 8); 675 delta += 8; 676 } 677 int p = bitPositionTable[(int) b]; 678 if (p >= 0) { 679 p += delta; 680 } else { 681 p = delta; 682 } 683 if (pos < 0) { 684 // first time 685 pos = p; 686 } else if (p == 0) { 687 pos++; 688 } else { 689 pos += (p + 1); 690 } 691 bits = bits >>> (p + 1); 692 return true; 693 } 694 public Integer next() { 695 return Integer.valueOf(pos); 696 } 697 public void remove() { 698 throw new UnsupportedOperationException("remove"); 699 } 700 }; 701 } 702 703 public int nextSetBit(int fromIndex) { 704 if (fromIndex < 0) { 705 throw new IndexOutOfBoundsException( 706 "fromIndex < 0: " + fromIndex); 707 } 708 709 if (fromIndex < 64) { 710 long word = bits & (WORD_MASK << fromIndex); 711 if (word != 0) { 712 return Long.numberOfTrailingZeros(word); 713 } 714 } 715 return -1; 716 } 717 718 public boolean equals(Object o) { 719 if (this == o) { 720 return true; 721 } 722 if (o instanceof BitKey.Small) { 723 BitKey.Small other = (BitKey.Small) o; 724 return (this.bits == other.bits); 725 726 } else if (o instanceof BitKey.Mid128) { 727 BitKey.Mid128 other = (BitKey.Mid128) o; 728 return (this.bits == other.bits0) && (other.bits1 == 0); 729 730 } else if (o instanceof BitKey.Big) { 731 BitKey.Big other = (BitKey.Big) o; 732 if (this.bits != other.bits[0]) { 733 return false; 734 } else { 735 for (int i = 1; i < other.bits.length; i++) { 736 if (other.bits[i] != 0) { 737 return false; 738 } 739 } 740 return true; 741 } 742 } 743 return false; 744 } 745 746 public int hashCode() { 747 return (int)(1234L ^ bits ^ (bits >>> 32)); 748 } 749 750 public int compareTo(BitKey bitKey) { 751 if (bitKey instanceof Small) { 752 Small that = (Small) bitKey; 753 return this.bits == that.bits ? 0 754 : this.bits < that.bits ? -1 755 : 1; 756 } else if (bitKey instanceof Mid128) { 757 Mid128 that = (Mid128) bitKey; 758 if (that.bits1 != 0) { 759 return -1; 760 } 761 return compareUnsigned(this.bits, that.bits0); 762 } else { 763 return compareToBig((Big) bitKey); 764 } 765 } 766 767 protected int compareToBig(Big that) { 768 int thatBitsLength = that.effectiveSize(); 769 switch (thatBitsLength) { 770 case 0: 771 return this.bits == 0 ? 0 : 1; 772 case 1: 773 return compareUnsigned(this.bits, that.bits[0]); 774 default: 775 return -1; 776 } 777 } 778 779 public String toString() { 780 StringBuilder buf = new StringBuilder(64); 781 buf.append("0x"); 782 for (int i = 63; i >= 0; i--) { 783 buf.append((get(i)) ? '1' : '0'); 784 } 785 return buf.toString(); 786 } 787 788 public BitKey copy() { 789 return new Small(this.bits); 790 } 791 792 public BitKey emptyCopy() { 793 return new Small(); 794 } 795 796 public boolean isEmpty() { 797 return bits == 0; 798 } 799 } 800 801 /** 802 * Implementation of {@link BitKey} good for sizes less than 128. 803 */ 804 public class Mid128 extends AbstractBitKey { 805 private static final long serialVersionUID = -8409143207943258659L; 806 private long bits0; 807 private long bits1; 808 809 private Mid128() { 810 } 811 812 private Mid128(Mid128 mid) { 813 this.bits0 = mid.bits0; 814 this.bits1 = mid.bits1; 815 } 816 817 public void set(int pos) { 818 if (pos < 64) { 819 bits0 |= bit(pos); 820 } else if (pos < 128) { 821 bits1 |= bit(pos); 822 } else { 823 throw new IllegalArgumentException( 824 "pos " + pos + " exceeds capacity 128"); 825 } 826 } 827 828 public boolean get(int pos) { 829 if (pos < 64) { 830 return (bits0 & bit(pos)) != 0; 831 } else if (pos < 128) { 832 return (bits1 & bit(pos)) != 0; 833 } else { 834 return false; 835 } 836 } 837 838 public void clear(int pos) { 839 if (pos < 64) { 840 bits0 &= ~bit(pos); 841 } else if (pos < 128) { 842 bits1 &= ~bit(pos); 843 } else { 844 throw new IndexOutOfBoundsException( 845 "pos " + pos + " exceeds size " + 128); 846 } 847 } 848 849 public void clear() { 850 bits0 = 0; 851 bits1 = 0; 852 } 853 854 public int cardinality() { 855 return bitCount(bits0) 856 + bitCount(bits1); 857 } 858 859 private void or(long bits0, long bits1) { 860 this.bits0 |= bits0; 861 this.bits1 |= bits1; 862 } 863 864 private void orNot(long bits0, long bits1) { 865 this.bits0 ^= bits0; 866 this.bits1 ^= bits1; 867 } 868 869 private void and(long bits0, long bits1) { 870 this.bits0 &= bits0; 871 this.bits1 &= bits1; 872 } 873 874 public BitKey or(BitKey bitKey) { 875 if (bitKey instanceof BitKey.Small) { 876 final BitKey.Small other = (BitKey.Small) bitKey; 877 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 878 bk.or(other.bits, 0); 879 return bk; 880 881 } else if (bitKey instanceof BitKey.Mid128) { 882 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 883 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 884 bk.or(other.bits0, other.bits1); 885 return bk; 886 887 } else if (bitKey instanceof BitKey.Big) { 888 final BitKey.Big other = (BitKey.Big) bitKey; 889 final BitKey.Big bk = (BitKey.Big) other.copy(); 890 bk.or(this.bits0, this.bits1); 891 return bk; 892 } 893 894 throw createException(bitKey); 895 } 896 897 public BitKey orNot(BitKey bitKey) { 898 if (bitKey instanceof BitKey.Small) { 899 final BitKey.Small other = (BitKey.Small) bitKey; 900 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 901 bk.orNot(other.bits, 0); 902 return bk; 903 904 } else if (bitKey instanceof BitKey.Mid128) { 905 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 906 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 907 bk.orNot(other.bits0, other.bits1); 908 return bk; 909 910 } else if (bitKey instanceof BitKey.Big) { 911 final BitKey.Big other = (BitKey.Big) bitKey; 912 final BitKey.Big bk = (BitKey.Big) other.copy(); 913 bk.orNot(this.bits0, this.bits1); 914 return bk; 915 } 916 917 throw createException(bitKey); 918 } 919 920 public BitKey and(BitKey bitKey) { 921 if (bitKey instanceof BitKey.Small) { 922 final BitKey.Small other = (BitKey.Small) bitKey; 923 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 924 bk.and(other.bits, 0); 925 return bk; 926 927 } else if (bitKey instanceof BitKey.Mid128) { 928 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 929 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 930 bk.and(other.bits0, other.bits1); 931 return bk; 932 933 } else if (bitKey instanceof BitKey.Big) { 934 final BitKey.Big other = (BitKey.Big) bitKey; 935 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 936 bk.and(other.bits[0], other.bits[1]); 937 return bk; 938 } 939 940 throw createException(bitKey); 941 } 942 943 public BitKey andNot(BitKey bitKey) { 944 if (bitKey instanceof BitKey.Small) { 945 final BitKey.Small other = (BitKey.Small) bitKey; 946 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 947 bk.andNot(other.bits, 0); 948 return bk; 949 950 } else if (bitKey instanceof BitKey.Mid128) { 951 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 952 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 953 bk.andNot(other.bits0, other.bits1); 954 return bk; 955 956 } else if (bitKey instanceof BitKey.Big) { 957 final BitKey.Big other = (BitKey.Big) bitKey; 958 final BitKey.Mid128 bk = (BitKey.Mid128) copy(); 959 bk.andNot(other.bits[0], other.bits[1]); 960 return bk; 961 } 962 963 throw createException(bitKey); 964 } 965 966 private void andNot(long bits0, long bits1) { 967 this.bits0 &= ~bits0; 968 this.bits1 &= ~bits1; 969 } 970 971 public boolean isSuperSetOf(BitKey bitKey) { 972 if (bitKey instanceof BitKey.Small) { 973 BitKey.Small other = (BitKey.Small) bitKey; 974 return ((this.bits0 | other.bits) == this.bits0); 975 976 } else if (bitKey instanceof BitKey.Mid128) { 977 BitKey.Mid128 other = (BitKey.Mid128) bitKey; 978 return ((this.bits0 | other.bits0) == this.bits0) 979 && ((this.bits1 | other.bits1) == this.bits1); 980 981 } else if (bitKey instanceof BitKey.Big) { 982 BitKey.Big other = (BitKey.Big) bitKey; 983 if ((this.bits0 | other.bits[0]) != this.bits0) { 984 return false; 985 } else if ((this.bits1 | other.bits[1]) != this.bits1) { 986 return false; 987 } else { 988 for (int i = 2; i < other.bits.length; i++) { 989 if (other.bits[i] != 0) { 990 return false; 991 } 992 } 993 return true; 994 } 995 } 996 return false; 997 } 998 999 public boolean intersects(BitKey bitKey) { 1000 if (bitKey instanceof BitKey.Small) { 1001 BitKey.Small other = (BitKey.Small) bitKey; 1002 return (this.bits0 & other.bits) != 0; 1003 1004 } else if (bitKey instanceof BitKey.Mid128) { 1005 BitKey.Mid128 other = (BitKey.Mid128) bitKey; 1006 return (this.bits0 & other.bits0) != 0 1007 || (this.bits1 & other.bits1) != 0; 1008 1009 } else if (bitKey instanceof BitKey.Big) { 1010 BitKey.Big other = (BitKey.Big) bitKey; 1011 if ((this.bits0 & other.bits[0]) != 0) { 1012 return true; 1013 } else if ((this.bits1 & other.bits[1]) != 0) { 1014 return true; 1015 } else { 1016 return false; 1017 } 1018 } 1019 return false; 1020 } 1021 1022 public BitSet toBitSet() { 1023 final BitSet bitSet = new BitSet(128); 1024 copyFromLong(bitSet, 0, bits0); 1025 copyFromLong(bitSet, 64, bits1); 1026 return bitSet; 1027 } 1028 public Iterator<Integer> iterator() { 1029 return new Iterator<Integer>() { 1030 long bits0 = Mid128.this.bits0; 1031 long bits1 = Mid128.this.bits1; 1032 int pos = -1; 1033 public boolean hasNext() { 1034 if (bits0 != 0) { 1035 if (bits0 == Long.MIN_VALUE) { 1036 pos = 63; 1037 bits0 = 0; 1038 return true; 1039 } 1040 long b = (bits0&-bits0); 1041 int delta = 0; 1042 while (b >= 256) { 1043 b = (b >> 8); 1044 delta += 8; 1045 } 1046 int p = bitPositionTable[(int) b]; 1047 if (p >= 0) { 1048 p += delta; 1049 } else { 1050 p = delta; 1051 } 1052 if (pos < 0) { 1053 pos = p; 1054 } else if (p == 0) { 1055 pos++; 1056 } else { 1057 pos += (p + 1); 1058 } 1059 bits0 = bits0 >>> (p + 1); 1060 return true; 1061 } else { 1062 if (pos < 63) { 1063 pos = 63; 1064 } 1065 if (bits1 == Long.MIN_VALUE) { 1066 pos = 127; 1067 bits1 = 0; 1068 return true; 1069 } 1070 long b = (bits1&-bits1); 1071 if (b == 0) { 1072 return false; 1073 } 1074 int delta = 0; 1075 while (b >= 256) { 1076 b = (b >> 8); 1077 delta += 8; 1078 } 1079 int p = bitPositionTable[(int) b]; 1080 if (p >= 0) { 1081 p += delta; 1082 } else { 1083 p = delta; 1084 } 1085 if (pos < 0) { 1086 pos = p; 1087 } else if (p == 63) { 1088 pos++; 1089 } else { 1090 pos += (p + 1); 1091 } 1092 bits1 = bits1 >>> (p + 1); 1093 return true; 1094 } 1095 } 1096 public Integer next() { 1097 return Integer.valueOf(pos); 1098 } 1099 public void remove() { 1100 throw new UnsupportedOperationException("remove"); 1101 } 1102 }; 1103 } 1104 1105 public int nextSetBit(int fromIndex) { 1106 if (fromIndex < 0) { 1107 throw new IndexOutOfBoundsException( 1108 "fromIndex < 0: " + fromIndex); 1109 } 1110 1111 int u = fromIndex >> 6; 1112 long word; 1113 switch (u) { 1114 case 0: 1115 word = bits0 & (WORD_MASK << fromIndex); 1116 if (word != 0) { 1117 return Long.numberOfTrailingZeros(word); 1118 } 1119 word = bits1; 1120 if (word != 0) { 1121 return 64 + Long.numberOfTrailingZeros(word); 1122 } 1123 return -1; 1124 case 1: 1125 word = bits1 & (WORD_MASK << fromIndex); 1126 if (word != 0) { 1127 return 64 + Long.numberOfTrailingZeros(word); 1128 } 1129 return -1; 1130 default: 1131 return -1; 1132 } 1133 } 1134 1135 public boolean equals(Object o) { 1136 if (this == o) { 1137 return true; 1138 } 1139 if (o instanceof BitKey.Small) { 1140 BitKey.Small other = (BitKey.Small) o; 1141 return (this.bits0 == other.bits) && (this.bits1 == 0); 1142 1143 } else if (o instanceof BitKey.Mid128) { 1144 BitKey.Mid128 other = (BitKey.Mid128) o; 1145 return (this.bits0 == other.bits0) 1146 && (this.bits1 == other.bits1); 1147 1148 } else if (o instanceof BitKey.Big) { 1149 BitKey.Big other = (BitKey.Big) o; 1150 if (this.bits0 != other.bits[0]) { 1151 return false; 1152 } else if (this.bits1 != other.bits[1]) { 1153 return false; 1154 } else { 1155 for (int i = 2; i < other.bits.length; i++) { 1156 if (other.bits[i] != 0) { 1157 return false; 1158 } 1159 } 1160 return true; 1161 } 1162 } 1163 return false; 1164 } 1165 1166 public int hashCode() { 1167 long h = 1234; 1168 h ^= bits0; 1169 h ^= bits1 * 2; 1170 return (int)((h >> 32) ^ h); 1171 } 1172 1173 public String toString() { 1174 StringBuilder buf = new StringBuilder(64); 1175 buf.append("0x"); 1176 for (int i = 127; i >= 0; i--) { 1177 buf.append((get(i)) ? '1' : '0'); 1178 } 1179 return buf.toString(); 1180 } 1181 1182 public BitKey copy() { 1183 return new Mid128(this); 1184 } 1185 1186 public BitKey emptyCopy() { 1187 return new Mid128(); 1188 } 1189 1190 public boolean isEmpty() { 1191 return bits0 == 0 1192 && bits1 == 0; 1193 } 1194 1195 // implement Comparable (in lazy, expensive fashion) 1196 public int compareTo(BitKey bitKey) { 1197 if (bitKey instanceof Mid128) { 1198 Mid128 that = (Mid128) bitKey; 1199 if (this.bits1 != that.bits1) { 1200 return compareUnsigned(this.bits1, that.bits1); 1201 } 1202 return compareUnsigned(this.bits0, that.bits0); 1203 } else if (bitKey instanceof Small) { 1204 Small that = (Small) bitKey; 1205 if (this.bits1 != 0) { 1206 return 1; 1207 } 1208 return compareUnsigned(this.bits0, that.bits); 1209 } else { 1210 return compareToBig((Big) bitKey); 1211 } 1212 } 1213 1214 int compareToBig(Big that) { 1215 int thatBitsLength = that.effectiveSize(); 1216 switch (thatBitsLength) { 1217 case 0: 1218 return this.bits1 == 0 1219 && this.bits0 == 0 1220 ? 0 1221 : 1; 1222 case 1: 1223 if (this.bits1 != 0) { 1224 return 1; 1225 } 1226 return compareUnsigned(this.bits0, that.bits[0]); 1227 case 2: 1228 if (this.bits1 != that.bits[1]) { 1229 return compareUnsigned(this.bits1, that.bits[1]); 1230 } 1231 return compareUnsigned(this.bits0, that.bits[0]); 1232 default: 1233 return -1; 1234 } 1235 } 1236 } 1237 1238 /** 1239 * Implementation of {@link BitKey} with more than 64 bits. Similar to 1240 * {@link java.util.BitSet}, but does not require dynamic resizing. 1241 */ 1242 public class Big extends AbstractBitKey { 1243 private static final long serialVersionUID = -3715282769845236295L; 1244 private long[] bits; 1245 1246 private Big(int size) { 1247 bits = new long[chunkCount(size + 1)]; 1248 } 1249 1250 private Big(Big big) { 1251 bits = big.bits.clone(); 1252 } 1253 1254 private int size() { 1255 return bits.length; 1256 } 1257 1258 /** 1259 * Returns the number of chunks, ignoring any chunks on the leading 1260 * edge that are all zero. 1261 * 1262 * @return number of chunks that are not on the leading edge 1263 */ 1264 private int effectiveSize() { 1265 int n = bits.length; 1266 while (n > 0 && bits[n - 1] == 0) { 1267 --n; 1268 } 1269 return n; 1270 } 1271 1272 public void set(int pos) { 1273 bits[chunkPos(pos)] |= bit(pos); 1274 } 1275 1276 public boolean get(int pos) { 1277 return (bits[chunkPos(pos)] & bit(pos)) != 0; 1278 } 1279 1280 public void clear(int pos) { 1281 bits[chunkPos(pos)] &= ~bit(pos); 1282 } 1283 1284 public void clear() { 1285 for (int i = 0; i < bits.length; i++) { 1286 bits[i] = 0; 1287 } 1288 } 1289 1290 public int cardinality() { 1291 int n = 0; 1292 for (int i = 0; i < bits.length; i++) { 1293 n += bitCount(bits[i]); 1294 } 1295 return n; 1296 } 1297 1298 private void or(long bits0) { 1299 this.bits[0] |= bits0; 1300 } 1301 1302 private void or(long bits0, long bits1) { 1303 this.bits[0] |= bits0; 1304 this.bits[1] |= bits1; 1305 } 1306 1307 private void or(long[] bits) { 1308 for (int i = 0; i < bits.length; i++) { 1309 this.bits[i] |= bits[i]; 1310 } 1311 } 1312 1313 private void orNot(long bits0) { 1314 this.bits[0] ^= bits0; 1315 } 1316 1317 private void orNot(long bits0, long bits1) { 1318 this.bits[0] ^= bits0; 1319 this.bits[1] ^= bits1; 1320 } 1321 1322 private void orNot(long[] bits) { 1323 for (int i = 0; i < bits.length; i++) { 1324 this.bits[i] ^= bits[i]; 1325 } 1326 } 1327 1328 private void and(long[] bits) { 1329 int length = Math.min(bits.length, this.bits.length); 1330 for (int i = 0; i < length; i++) { 1331 this.bits[i] &= bits[i]; 1332 } 1333 for (int i = bits.length; i < this.bits.length; i++) { 1334 this.bits[i] = 0; 1335 } 1336 } 1337 1338 public BitKey or(BitKey bitKey) { 1339 if (bitKey instanceof BitKey.Small) { 1340 final BitKey.Small other = (BitKey.Small) bitKey; 1341 final BitKey.Big bk = (BitKey.Big) copy(); 1342 bk.or(other.bits); 1343 return bk; 1344 1345 } else if (bitKey instanceof BitKey.Mid128) { 1346 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 1347 final BitKey.Big bk = (BitKey.Big) copy(); 1348 bk.or(other.bits0, other.bits1); 1349 return bk; 1350 1351 } else if (bitKey instanceof BitKey.Big) { 1352 final BitKey.Big other = (BitKey.Big) bitKey; 1353 if (other.size() > size()) { 1354 final BitKey.Big bk = (BitKey.Big) other.copy(); 1355 bk.or(bits); 1356 return bk; 1357 } else { 1358 final BitKey.Big bk = (BitKey.Big) copy(); 1359 bk.or(other.bits); 1360 return bk; 1361 } 1362 } 1363 1364 throw createException(bitKey); 1365 } 1366 1367 public BitKey orNot(BitKey bitKey) { 1368 if (bitKey instanceof BitKey.Small) { 1369 final BitKey.Small other = (BitKey.Small) bitKey; 1370 final BitKey.Big bk = (BitKey.Big) copy(); 1371 bk.orNot(other.bits); 1372 return bk; 1373 1374 } else if (bitKey instanceof BitKey.Mid128) { 1375 final BitKey.Mid128 other = (BitKey.Mid128) bitKey; 1376 final BitKey.Big bk = (BitKey.Big) copy(); 1377 bk.orNot(other.bits0, other.bits1); 1378 return bk; 1379 1380 } else if (bitKey instanceof BitKey.Big) { 1381 final BitKey.Big other = (BitKey.Big) bitKey; 1382 if (other.size() > size()) { 1383 final BitKey.Big bk = (BitKey.Big) other.copy(); 1384 bk.orNot(bits); 1385 return bk; 1386 } else { 1387 final BitKey.Big bk = (BitKey.Big) copy(); 1388 bk.orNot(other.bits); 1389 return bk; 1390 } 1391 } 1392 1393 throw createException(bitKey); 1394 } 1395 1396 public BitKey and(BitKey bitKey) { 1397 if (bitKey instanceof BitKey.Small) { 1398 final BitKey.Small bk = (BitKey.Small) bitKey.copy(); 1399 bk.and(bits[0]); 1400 return bk; 1401 1402 } else if (bitKey instanceof BitKey.Mid128) { 1403 final BitKey.Mid128 bk = (BitKey.Mid128) bitKey.copy(); 1404 bk.and(bits[0], bits[1]); 1405 return bk; 1406 1407 } else if (bitKey instanceof BitKey.Big) { 1408 final BitKey.Big other = (BitKey.Big) bitKey; 1409 if (other.size() < size()) { 1410 final BitKey.Big bk = (BitKey.Big) other.copy(); 1411 bk.and(bits); 1412 return bk; 1413 } else { 1414 final BitKey.Big bk = (BitKey.Big) copy(); 1415 bk.and(other.bits); 1416 return bk; 1417 } 1418 } 1419 1420 throw createException(bitKey); 1421 } 1422 1423 public BitKey andNot(BitKey bitKey) { 1424 if (bitKey instanceof BitKey.Small) { 1425 final BitKey.Small other = (BitKey.Small) bitKey; 1426 final BitKey.Big bk = (BitKey.Big) copy(); 1427 bk.andNot(other.bits); 1428 return bk; 1429 1430 } else if (bitKey instanceof BitKey.Mid128) { 1431 final BitKey.Mid128 other = (Mid128) bitKey; 1432 final BitKey.Big bk = (BitKey.Big) copy(); 1433 bk.andNot(other.bits0, other.bits1); 1434 return bk; 1435 1436 } else if (bitKey instanceof BitKey.Big) { 1437 final BitKey.Big other = (BitKey.Big) bitKey; 1438 final BitKey.Big bk = (BitKey.Big) copy(); 1439 bk.andNot(other.bits); 1440 return bk; 1441 } 1442 1443 throw createException(bitKey); 1444 } 1445 1446 private void andNot(long[] bits) { 1447 for (int i = 0; i < bits.length; i++) { 1448 this.bits[i] &= ~bits[i]; 1449 } 1450 } 1451 1452 private void andNot(long bits0, long bits1) { 1453 this.bits[0] &= ~bits0; 1454 this.bits[1] &= ~bits1; 1455 } 1456 1457 private void andNot(long bits) { 1458 this.bits[0] &= ~bits; 1459 } 1460 1461 public boolean isSuperSetOf(BitKey bitKey) { 1462 if (bitKey instanceof BitKey.Small) { 1463 BitKey.Small other = (BitKey.Small) bitKey; 1464 return ((this.bits[0] | other.bits) == this.bits[0]); 1465 1466 } else if (bitKey instanceof BitKey.Mid128) { 1467 BitKey.Mid128 other = (BitKey.Mid128) bitKey; 1468 return ((this.bits[0] | other.bits0) == this.bits[0]) 1469 && ((this.bits[1] | other.bits1) == this.bits[1]); 1470 1471 } else if (bitKey instanceof BitKey.Big) { 1472 BitKey.Big other = (BitKey.Big) bitKey; 1473 1474 int len = Math.min(bits.length, other.bits.length); 1475 for (int i = 0; i < len; i++) { 1476 if ((this.bits[i] | other.bits[i]) != this.bits[i]) { 1477 return false; 1478 } 1479 } 1480 if (other.bits.length > this.bits.length) { 1481 for (int i = len; i < other.bits.length; i++) { 1482 if (other.bits[i] != 0) { 1483 return false; 1484 } 1485 } 1486 } 1487 return true; 1488 } 1489 return false; 1490 } 1491 1492 public boolean intersects(BitKey bitKey) { 1493 if (bitKey instanceof BitKey.Small) { 1494 BitKey.Small other = (BitKey.Small) bitKey; 1495 return (this.bits[0] & other.bits) != 0; 1496 1497 } else if (bitKey instanceof BitKey.Mid128) { 1498 BitKey.Mid128 other = (BitKey.Mid128) bitKey; 1499 return (this.bits[0] & other.bits0) != 0 1500 || (this.bits[1] & other.bits1) != 0; 1501 1502 } else if (bitKey instanceof BitKey.Big) { 1503 BitKey.Big other = (BitKey.Big) bitKey; 1504 1505 int len = Math.min(bits.length, other.bits.length); 1506 for (int i = 0; i < len; i++) { 1507 if ((this.bits[i] & other.bits[i]) != 0) { 1508 return true; 1509 } 1510 } 1511 return false; 1512 } 1513 return false; 1514 } 1515 1516 public BitSet toBitSet() { 1517 final BitSet bitSet = new BitSet(64); 1518 int pos = 0; 1519 for (int i = 0; i < bits.length; i++) { 1520 copyFromLong(bitSet, pos, bits[i]); 1521 pos += 64; 1522 } 1523 return bitSet; 1524 } 1525 1526 public Iterator<Integer> iterator() { 1527 return new Iterator<Integer>() { 1528 long[] bits = Big.this.bits.clone(); 1529 int pos = -1; 1530 int index = 0; 1531 public boolean hasNext() { 1532 if (index >= bits.length) { 1533 return false; 1534 } 1535 if (pos < 0) { 1536 while (bits[index] == 0) { 1537 index++; 1538 if (index >= bits.length) { 1539 return false; 1540 } 1541 } 1542 pos = (64 * index) - 1; 1543 } 1544 long bs = bits[index]; 1545 if (bs == 0) { 1546 while (bits[index] == 0) { 1547 index++; 1548 if (index >= bits.length) { 1549 return false; 1550 } 1551 } 1552 pos = (64 * index) - 1; 1553 bs = bits[index]; 1554 } 1555 if (bs != 0) { 1556 if (bs == Long.MIN_VALUE) { 1557 pos = (64 * index) + 63; 1558 bits[index] = 0; 1559 return true; 1560 } 1561 long b = (bs&-bs); 1562 int delta = 0; 1563 while (b >= 256) { 1564 b = (b >> 8); 1565 delta += 8; 1566 } 1567 int p = bitPositionTable[(int) b]; 1568 if (p >= 0) { 1569 p += delta; 1570 } else { 1571 p = delta; 1572 } 1573 if (pos < 0) { 1574 pos = p; 1575 } else if (p == 0) { 1576 pos++; 1577 } else { 1578 pos += (p + 1); 1579 } 1580 bits[index] = bits[index] >>> (p + 1); 1581 return true; 1582 } 1583 return false; 1584 } 1585 1586 public Integer next() { 1587 return Integer.valueOf(pos); 1588 } 1589 1590 public void remove() { 1591 throw new UnsupportedOperationException("remove"); 1592 } 1593 }; 1594 } 1595 1596 public int nextSetBit(int fromIndex) { 1597 if (fromIndex < 0) { 1598 throw new IndexOutOfBoundsException( 1599 "fromIndex < 0: " + fromIndex); 1600 } 1601 1602 int u = chunkPos(fromIndex); 1603 if (u >= bits.length) { 1604 return -1; 1605 } 1606 long word = bits[u] & (WORD_MASK << fromIndex); 1607 1608 while (true) { 1609 if (word != 0) { 1610 return (u * 64) + Long.numberOfTrailingZeros(word); 1611 } 1612 if (++u == bits.length) { 1613 return -1; 1614 } 1615 word = bits[u]; 1616 } 1617 } 1618 1619 public boolean equals(Object o) { 1620 if (this == o) { 1621 return true; 1622 } 1623 if (o instanceof BitKey.Small) { 1624 BitKey.Small other = (BitKey.Small) o; 1625 if (this.bits[0] != other.bits) { 1626 return false; 1627 } else { 1628 for (int i = 1; i < this.bits.length; i++) { 1629 if (this.bits[i] != 0) { 1630 return false; 1631 } 1632 } 1633 return true; 1634 } 1635 1636 } else if (o instanceof BitKey.Mid128) { 1637 BitKey.Mid128 other = (BitKey.Mid128) o; 1638 if (this.bits[0] != other.bits0) { 1639 return false; 1640 } else if (this.bits[1] != other.bits1) { 1641 return false; 1642 } else { 1643 for (int i = 2; i < this.bits.length; i++) { 1644 if (this.bits[i] != 0) { 1645 return false; 1646 } 1647 } 1648 return true; 1649 } 1650 1651 } else if (o instanceof BitKey.Big) { 1652 BitKey.Big other = (BitKey.Big) o; 1653 1654 int len = Math.min(bits.length, other.bits.length); 1655 for (int i = 0; i < len; i++) { 1656 if (this.bits[i] != other.bits[i]) { 1657 return false; 1658 } 1659 } 1660 if (this.bits.length > other.bits.length) { 1661 for (int i = len; i < this.bits.length; i++) { 1662 if (this.bits[i] != 0) { 1663 return false; 1664 } 1665 } 1666 } else if (other.bits.length > this.bits.length) { 1667 for (int i = len; i < other.bits.length; i++) { 1668 if (other.bits[i] != 0) { 1669 return false; 1670 } 1671 } 1672 } 1673 return true; 1674 } 1675 return false; 1676 } 1677 1678 public int hashCode() { 1679 // It is important that leading 0s, and bits.length do not affect 1680 // the hash code. For instance, we want {1} to be equal to 1681 // {1, 0, 0}. This algorithm in fact ignores all 0s. 1682 // 1683 // It is also important that the hash code is the same as produced 1684 // by Small and Mid128. 1685 long h = 1234; 1686 for (int i = bits.length; --i >= 0;) { 1687 h ^= bits[i] * (i + 1); 1688 } 1689 return (int)((h >> 32) ^ h); 1690 } 1691 1692 public String toString() { 1693 StringBuilder buf = new StringBuilder(64); 1694 buf.append("0x"); 1695 int start = bits.length * 64 - 1; 1696 for (int i = start; i >= 0; i--) { 1697 buf.append((get(i)) ? '1' : '0'); 1698 } 1699 return buf.toString(); 1700 } 1701 1702 public BitKey copy() { 1703 return new Big(this); 1704 } 1705 1706 public BitKey emptyCopy() { 1707 return new Big(bits.length << ChunkBitCount); 1708 } 1709 1710 public boolean isEmpty() { 1711 for (long bit : bits) { 1712 if (bit != 0) { 1713 return false; 1714 } 1715 } 1716 return true; 1717 } 1718 1719 public int compareTo(BitKey bitKey) { 1720 if (bitKey instanceof Big) { 1721 return compareUnsignedArrays(this.bits, ((Big) bitKey).bits); 1722 } else if (bitKey instanceof Mid128) { 1723 Mid128 that = (Mid128) bitKey; 1724 return -that.compareToBig(this); 1725 } else { 1726 Small that = (Small) bitKey; 1727 return -that.compareToBig(this); 1728 } 1729 } 1730 } 1731 1732 static final byte bitPositionTable[] = { 1733 -1, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1734 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1735 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1736 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1737 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1738 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1739 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1740 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1741 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1742 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1743 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1744 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1745 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1746 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1747 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 1748 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 1749 }; 1750} 1751 1752// End BitKey.java