001 /*
002 // $Id: //open/mondrian/src/main/mondrian/rolap/BitKey.java#15 $
003 // This software is subject to the terms of the Common Public License
004 // Agreement, available at the following URL:
005 // http://www.opensource.org/licenses/cpl.html.
006 // Copyright (C) 2001-2002 Kana Software, Inc.
007 // Copyright (C) 2001-2008 Julian Hyde and others
008 // All Rights Reserved.
009 // You must accept the terms of that agreement to use this software.
010 //
011 // jhyde, 30 August, 2001
012 */
013
014 package mondrian.rolap;
015
016 import java.util.BitSet;
017 import 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 * @version $Id: //open/mondrian/src/main/mondrian/rolap/BitKey.java#15 $
040 */
041 public interface BitKey extends Comparable<BitKey>, Iterable<Integer> {
042
043 /**
044 * Sets the bit at the specified index to the specified value.
045 */
046 void set(int bitIndex, boolean value);
047
048 /**
049 * Sets the bit at the specified index to <code>true</code>.
050 */
051 void set(int bitIndex);
052
053 /**
054 * Returns the value of the bit with the specified index. The value
055 * is <code>true</code> if the bit with the index <code>bitIndex</code>
056 * is currently set in this <code>BitKey</code>; otherwise, the result
057 * is <code>false</code>.
058 */
059 boolean get(int bitIndex);
060
061 /**
062 * Sets the bit specified by the index to <code>false</code>.
063 */
064 void clear(int bitIndex);
065
066 /**
067 * Sets all of the bits in this BitKey to <code>false</code>.
068 */
069 void clear();
070
071 /**
072 * Is every bit set in the parameter <code>bitKey</code> also set in
073 * <code>this</code>.
074 * If one switches <code>this</code> with the parameter <code>bitKey</code>
075 * one gets the equivalent of isSubSetOf.
076 *
077 * @param bitKey
078 */
079 boolean isSuperSetOf(BitKey bitKey);
080
081 /**
082 * Or the parameter <code>BitKey</code> with <code>this</code>.
083 *
084 * @param bitKey
085 */
086 BitKey or(BitKey bitKey);
087
088 /**
089 * Returns the boolean AND of this bitkey and the given bitkey.
090 */
091 BitKey and(BitKey bitKey);
092
093 /**
094 * Returns a <code>BitKey</code> containing all of the bits in this
095 * <code>BitSet</code> whose corresponding
096 * bit is NOT set in the specified <code>BitSet</code>.
097 */
098 BitKey andNot(BitKey bitKey);
099
100 /**
101 * Returns a copy of this BitKey.
102 *
103 * @return copy of BitKey
104 */
105 BitKey copy();
106
107 /**
108 * Returns an empty BitKey of the same type. This is the same
109 * as calling {@link #copy} followed by {@link #clear()}.
110 *
111 * @return BitKey of same type
112 */
113 BitKey emptyCopy();
114
115 /**
116 * Returns true if this <code>BitKey</code> contains no bits that are set
117 * to <code>true</code>.
118 */
119 boolean isEmpty();
120
121 /**
122 * Returns whether this BitKey has any bits in common with a given BitKey.
123 */
124 boolean intersects(BitKey bitKey);
125
126 /**
127 * Returns a {@link BitSet} with the same contents as this BitKey.
128 */
129 BitSet toBitSet();
130
131 /**
132 * An Iterator over the bit positions.
133 * For example, if the BitKey had positions 3 and 4 set, then
134 * the Iterator would return the values 3 and then 4. The bit
135 * positions returned by the iterator are in the order, from
136 * smallest to largest, as they are set in the BitKey.
137 */
138 Iterator<Integer> iterator();
139
140 public abstract class Factory {
141
142 /**
143 * Creates a {@link BitKey} with a capacity for a given number of bits.
144 * @param size Number of bits in key
145 */
146 public static BitKey makeBitKey(int size) {
147 if (size < 0) {
148 String msg = "Negative size \"" + size + "\" not allowed";
149 throw new IllegalArgumentException(msg);
150 }
151 if (size < 64) {
152 return new BitKey.Small();
153 } else if (size < 128) {
154 return new BitKey.Mid128();
155 } else {
156 return new BitKey.Big(size);
157 }
158 /*
159 switch (AbstractBitKey.chunkCount(size)) {
160 case 0:
161 case 1:
162 return new BitKey.Small();
163 case 2:
164 return new BitKey.Mid128();
165 default:
166 return new BitKey.Big(size);
167 }
168 */
169 }
170
171 /**
172 * Creates a {@link BitKey} with the same contents as a {@link BitSet}.
173 */
174 public static BitKey makeBitKey(BitSet bitSet) {
175 BitKey bitKey = makeBitKey(bitSet.length());
176 for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
177 bitKey.set(i);
178 }
179 return bitKey;
180 }
181 }
182
183 /**
184 * Abstract implementation of {@link BitKey}.
185 */
186 abstract class AbstractBitKey implements BitKey {
187 protected AbstractBitKey() {
188 }
189
190 // chunk is a long, which has 64 bits
191 protected static final int ChunkBitCount = 6;
192 protected static final int Mask = 63;
193
194 /**
195 * Creates a chunk containing a single bit.
196 */
197 protected static long bit(int pos) {
198 return (1L << (pos & Mask));
199 }
200
201 /**
202 * Returns which chunk a given bit falls into.
203 * Bits 0 to 63 fall in chunk 0, bits 64 to 127 fall into chunk 1.
204 */
205 protected static int chunkPos(int size) {
206 return (size >> ChunkBitCount);
207 }
208
209 /**
210 * Returns the number of chunks required for a given number of bits.
211 *
212 * <p>0 bits requires 0 chunks; 1 - 64 bits requires 1 chunk; etc.
213 */
214 protected static int chunkCount(int size) {
215 return (size + 63) >> ChunkBitCount;
216 }
217
218 public final void set(int pos, boolean value) {
219 if (value) {
220 set(pos);
221 } else {
222 clear(pos);
223 }
224 }
225
226 protected static void copyFromByte(BitSet bitSet, int pos, byte x)
227 {
228 if (x == 0) {
229 return;
230 }
231 if ((x & 0x01) != 0) {
232 bitSet.set(pos, true);
233 }
234 ++pos;
235 if ((x & 0x02) != 0) {
236 bitSet.set(pos, true);
237 }
238 ++pos;
239 if ((x & 0x04) != 0) {
240 bitSet.set(pos, true);
241 }
242 ++pos;
243 if ((x & 0x08) != 0) {
244 bitSet.set(pos, true);
245 }
246 ++pos;
247 if ((x & 0x10) != 0) {
248 bitSet.set(pos, true);
249 }
250 ++pos;
251 if ((x & 0x20) != 0) {
252 bitSet.set(pos, true);
253 }
254 ++pos;
255 if ((x & 0x40) != 0) {
256 bitSet.set(pos, true);
257 }
258 ++pos;
259 if ((x & 0x80) != 0) {
260 bitSet.set(pos, true);
261 }
262 }
263
264 protected static void copyFromLong(
265 final BitSet bitSet,
266 int pos,
267 long x) {
268 while (x != 0) {
269 copyFromByte(bitSet, pos, (byte) (x & 0xff));
270 x >>>= 8;
271 pos += 8;
272 }
273 }
274
275 protected IllegalArgumentException createException(BitKey bitKey) {
276 final String msg = (bitKey == null)
277 ? "Null BitKey"
278 : "Bad BitKey type: " + bitKey.getClass().getName();
279 return new IllegalArgumentException(msg);
280 }
281 }
282
283 /**
284 * Implementation of {@link BitKey} for bit counts less than 64.
285 */
286 public class Small extends AbstractBitKey {
287 private long bits;
288
289 private Small() {
290 }
291 private Small(long bits) {
292 this.bits = bits;
293 }
294 public void set(int pos) {
295 if (pos < 64) {
296 bits |= bit(pos);
297 } else {
298 throw new IllegalArgumentException("pos " + pos + " exceeds capacity 64");
299 }
300 }
301 public boolean get(int pos) {
302 return pos < 64 && ((bits & bit(pos)) != 0);
303 }
304 public void clear(int pos) {
305 bits &= ~bit(pos);
306 }
307 public void clear() {
308 bits = 0;
309 }
310 private void or(long bits) {
311 this.bits |= bits;
312 }
313
314 private void and(long bits) {
315 this.bits &= bits;
316 }
317
318 public BitKey or(BitKey bitKey) {
319 if (bitKey instanceof BitKey.Small) {
320 final BitKey.Small other = (BitKey.Small) bitKey;
321 final BitKey.Small bk = (BitKey.Small) copy();
322 bk.or(other.bits);
323 return bk;
324
325 } else if (bitKey instanceof BitKey.Mid128) {
326 final BitKey.Mid128 other = (BitKey.Mid128) bitKey;
327 final BitKey.Mid128 bk = (BitKey.Mid128) other.copy();
328 bk.or(this.bits, 0);
329 return bk;
330
331 } else if (bitKey instanceof BitKey.Big) {
332 final BitKey.Big other = (BitKey.Big) bitKey;
333 final BitKey.Big bk = (BitKey.Big) other.copy();
334 bk.or(this.bits);
335 return bk;
336 }
337
338 throw createException(bitKey);
339 }
340
341 public BitKey and(BitKey bitKey) {
342 if (bitKey instanceof BitKey.Small) {
343 final BitKey.Small other = (BitKey.Small) bitKey;
344 final BitKey.Small bk = (BitKey.Small) copy();
345 bk.and(other.bits);
346 return bk;
347
348 } else if (bitKey instanceof BitKey.Mid128) {
349 final BitKey.Mid128 other = (BitKey.Mid128) bitKey;
350 final BitKey.Small bk = (BitKey.Small) copy();
351 bk.and(other.bits0);
352 return bk;
353
354 } else if (bitKey instanceof BitKey.Big) {
355 final BitKey.Big other = (BitKey.Big) bitKey;
356 final BitKey.Small bk = (BitKey.Small) copy();
357 bk.and(other.bits[0]);
358 return bk;
359 }
360
361 throw createException(bitKey);
362 }
363
364 public BitKey andNot(BitKey bitKey) {
365 if (bitKey instanceof BitKey.Small) {
366 final BitKey.Small other = (BitKey.Small) bitKey;
367 final BitKey.Small bk = (BitKey.Small) copy();
368 bk.andNot(other.bits);
369 return bk;
370
371 } else if (bitKey instanceof BitKey.Mid128) {
372 final BitKey.Mid128 other = (BitKey.Mid128) bitKey;
373 final BitKey.Small bk = (BitKey.Small) copy();
374 bk.andNot(other.bits0);
375 return bk;
376
377 } else if (bitKey instanceof BitKey.Big) {
378 final BitKey.Big other = (BitKey.Big) bitKey;
379 final BitKey.Small bk = (BitKey.Small) copy();
380 bk.andNot(other.bits[0]);
381 return bk;
382 }
383
384 throw createException(bitKey);
385 }
386
387 private void andNot(long bits) {
388 this.bits &= ~bits;
389 }
390
391 public boolean isSuperSetOf(BitKey bitKey) {
392 if (bitKey instanceof BitKey.Small) {
393 BitKey.Small other = (BitKey.Small) bitKey;
394 return ((this.bits | other.bits) == this.bits);
395
396 } else if (bitKey instanceof BitKey.Mid128) {
397 BitKey.Mid128 other = (BitKey.Mid128) bitKey;
398 return ((this.bits | other.bits0) == this.bits) &&
399 (other.bits1 == 0);
400
401 } else if (bitKey instanceof BitKey.Big) {
402 BitKey.Big other = (BitKey.Big) bitKey;
403 if ((this.bits | other.bits[0]) != this.bits) {
404 return false;
405 } else {
406 for (int i = 1; i < other.bits.length; i++) {
407 if (other.bits[i] != 0) {
408 return false;
409 }
410 }
411 return true;
412 }
413 }
414 return false;
415 }
416
417 public boolean intersects(BitKey bitKey) {
418 if (bitKey instanceof BitKey.Small) {
419 BitKey.Small other = (BitKey.Small) bitKey;
420 return (this.bits & other.bits) != 0;
421
422 } else if (bitKey instanceof BitKey.Mid128) {
423 BitKey.Mid128 other = (BitKey.Mid128) bitKey;
424 return (this.bits & other.bits0) != 0;
425
426 } else if (bitKey instanceof BitKey.Big) {
427 BitKey.Big other = (BitKey.Big) bitKey;
428 return (this.bits & other.bits[0]) != 0;
429 }
430 return false;
431 }
432
433 public BitSet toBitSet() {
434 final BitSet bitSet = new BitSet(64);
435 long x = bits;
436 int pos = 0;
437 while (x != 0) {
438 copyFromByte(bitSet, pos, (byte) (x & 0xff));
439 x >>>= 8;
440 pos += 8;
441 }
442 return bitSet;
443 }
444
445 /**
446 * To say that I am happy about this algorithm (or the variations
447 * of the algorithm used for the Mid128 and Big BitKey implementations)
448 * would be a stretch. It works but there has to be a more
449 * elegant and faster one but this is the best I could come up
450 * with in a couple of hours.
451 *
452 */
453 public Iterator<Integer> iterator() {
454 return new Iterator<Integer>() {
455 int pos = -1;
456 long bits = Small.this.bits;
457 public boolean hasNext() {
458 if (bits == 0) {
459 return false;
460 }
461 // This is a special case
462 // Long.MIN_VALUE == -9223372036854775808
463 if (bits == Long.MIN_VALUE) {
464 pos = 63;
465 bits = 0;
466 return true;
467 }
468 long b = (bits&-bits);
469 if (b == 0) {
470 // should never happen
471 return false;
472 }
473 int delta = 0;
474 while (b >= 256) {
475 b = (b >> 8);
476 delta += 8;
477 }
478 int p = bitPositionTable[(int) b];
479 if (p >= 0) {
480 p += delta;
481 } else {
482 p = delta;
483 }
484 if (pos < 0) {
485 // first time
486 pos = p;
487 } else if (p == 0) {
488 pos++;
489 } else {
490 pos += (p + 1);
491 }
492 bits = bits >>> (p + 1);
493 return true;
494 }
495 public Integer next() {
496 return Integer.valueOf(pos);
497 }
498 public void remove() {
499 throw new UnsupportedOperationException("remove");
500 }
501 };
502 }
503
504 public boolean equals(Object o) {
505 if (this == o) {
506 return true;
507 }
508 if (o instanceof BitKey.Small) {
509 BitKey.Small other = (BitKey.Small) o;
510 return (this.bits == other.bits);
511
512 } else if (o instanceof BitKey.Mid128) {
513 BitKey.Mid128 other = (BitKey.Mid128) o;
514 return (this.bits == other.bits0) && (other.bits1 == 0);
515
516 } else if (o instanceof BitKey.Big) {
517 BitKey.Big other = (BitKey.Big) o;
518 if (this.bits != other.bits[0]) {
519 return false;
520 } else {
521 for (int i = 1; i < other.bits.length; i++) {
522 if (other.bits[i] != 0) {
523 return false;
524 }
525 }
526 return true;
527 }
528 }
529 return false;
530 }
531 public int hashCode() {
532 return (int)(bits ^ (bits >>> 32));
533 }
534
535 // implement Comparable (in lazy, expensive fashion)
536 public int compareTo(BitKey bitKey) {
537 return toString().compareTo(bitKey.toString());
538 }
539
540 public String toString() {
541 StringBuilder buf = new StringBuilder(64);
542 buf.append("0x");
543 for (int i = 63; i >= 0; i--) {
544 buf.append((get(i)) ? '1' : '0');
545 }
546 return buf.toString();
547 }
548 public BitKey copy() {
549 return new Small(this.bits);
550 }
551 public BitKey emptyCopy() {
552 return new Small();
553 }
554
555 public boolean isEmpty() {
556 return bits == 0;
557 }
558 }
559
560 /**
561 * Implementation of {@link BitKey} good for sizes less than 128.
562 */
563 public class Mid128 extends AbstractBitKey {
564 private long bits0;
565 private long bits1;
566
567 private Mid128() {
568 }
569 private Mid128(Mid128 mid) {
570 this.bits0 = mid.bits0;
571 this.bits1 = mid.bits1;
572 }
573
574 public void set(int pos) {
575 if (pos < 64) {
576 bits0 |= bit(pos);
577 } else if (pos < 128) {
578 bits1 |= bit(pos);
579 } else {
580 throw new IllegalArgumentException("pos " + pos + " exceeds capacity 128");
581 }
582 }
583
584 public boolean get(int pos) {
585 if (pos < 64) {
586 return (bits0 & bit(pos)) != 0;
587 } else if (pos < 128) {
588 return (bits1 & bit(pos)) != 0;
589 } else {
590 return false;
591 }
592 }
593
594 public void clear(int pos) {
595 if (pos < 64) {
596 bits0 &= ~bit(pos);
597 } else if (pos < 128) {
598 bits1 &= ~bit(pos);
599 } else {
600 throw new IndexOutOfBoundsException(
601 "pos " + pos + " exceeds size " + 128);
602 }
603 }
604
605 public void clear() {
606 bits0 = 0;
607 bits1 = 0;
608 }
609
610 private void or(long bits0, long bits1) {
611 this.bits0 |= bits0;
612 this.bits1 |= bits1;
613 }
614
615 private void and(long bits0, long bits1) {
616 this.bits0 &= bits0;
617 this.bits1 &= bits1;
618 }
619
620 public BitKey or(BitKey bitKey) {
621 if (bitKey instanceof BitKey.Small) {
622 final BitKey.Small other = (BitKey.Small) bitKey;
623 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
624 bk.or(other.bits, 0);
625 return bk;
626
627 } else if (bitKey instanceof BitKey.Mid128) {
628 final BitKey.Mid128 other = (BitKey.Mid128) bitKey;
629 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
630 bk.or(other.bits0, other.bits1);
631 return bk;
632
633 } else if (bitKey instanceof BitKey.Big) {
634 final BitKey.Big other = (BitKey.Big) bitKey;
635 final BitKey.Big bk = (BitKey.Big) other.copy();
636 bk.or(this.bits0, this.bits1);
637 return bk;
638 }
639
640 throw createException(bitKey);
641 }
642
643 public BitKey and(BitKey bitKey) {
644 if (bitKey instanceof BitKey.Small) {
645 final BitKey.Small other = (BitKey.Small) bitKey;
646 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
647 bk.and(other.bits, 0);
648 return bk;
649
650 } else if (bitKey instanceof BitKey.Mid128) {
651 final BitKey.Mid128 other = (BitKey.Mid128) bitKey;
652 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
653 bk.and(other.bits0, other.bits1);
654 return bk;
655
656 } else if (bitKey instanceof BitKey.Big) {
657 final BitKey.Big other = (BitKey.Big) bitKey;
658 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
659 bk.and(other.bits[0], other.bits[1]);
660 return bk;
661 }
662
663 throw createException(bitKey);
664 }
665
666 public BitKey andNot(BitKey bitKey) {
667 if (bitKey instanceof BitKey.Small) {
668 final BitKey.Small other = (BitKey.Small) bitKey;
669 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
670 bk.andNot(other.bits, 0);
671 return bk;
672
673 } else if (bitKey instanceof BitKey.Mid128) {
674 final BitKey.Mid128 other = (BitKey.Mid128) bitKey;
675 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
676 bk.andNot(other.bits0, other.bits1);
677 return bk;
678
679 } else if (bitKey instanceof BitKey.Big) {
680 final BitKey.Big other = (BitKey.Big) bitKey;
681 final BitKey.Mid128 bk = (BitKey.Mid128) copy();
682 bk.andNot(other.bits[0], other.bits[1]);
683 return bk;
684 }
685
686 throw createException(bitKey);
687 }
688
689 private void andNot(long bits0, long bits1) {
690 this.bits0 &= ~bits0;
691 this.bits1 &= ~bits1;
692 }
693
694 public boolean isSuperSetOf(BitKey bitKey) {
695 if (bitKey instanceof BitKey.Small) {
696 BitKey.Small other = (BitKey.Small) bitKey;
697 return ((this.bits0 | other.bits) == this.bits0);
698
699 } else if (bitKey instanceof BitKey.Mid128) {
700 BitKey.Mid128 other = (BitKey.Mid128) bitKey;
701 return ((this.bits0 | other.bits0) == this.bits0) &&
702 ((this.bits1 | other.bits1) == this.bits1);
703
704 } else if (bitKey instanceof BitKey.Big) {
705 BitKey.Big other = (BitKey.Big) bitKey;
706 if ((this.bits0 | other.bits[0]) != this.bits0) {
707 return false;
708 } else if ((this.bits1 | other.bits[1]) != this.bits1) {
709 return false;
710 } else {
711 for (int i = 2; i < other.bits.length; i++) {
712 if (other.bits[i] != 0) {
713 return false;
714 }
715 }
716 return true;
717 }
718 }
719 return false;
720 }
721
722 public boolean intersects(BitKey bitKey) {
723 if (bitKey instanceof BitKey.Small) {
724 BitKey.Small other = (BitKey.Small) bitKey;
725 return (this.bits0 & other.bits) != 0;
726
727 } else if (bitKey instanceof BitKey.Mid128) {
728 BitKey.Mid128 other = (BitKey.Mid128) bitKey;
729 return (this.bits0 & other.bits0) != 0 ||
730 (this.bits1 & other.bits1) != 0;
731
732 } else if (bitKey instanceof BitKey.Big) {
733 BitKey.Big other = (BitKey.Big) bitKey;
734 if ((this.bits0 & other.bits[0]) != 0) {
735 return true;
736 } else if ((this.bits1 & other.bits[1]) != 0) {
737 return true;
738 } else {
739 return false;
740 }
741 }
742 return false;
743 }
744
745 public BitSet toBitSet() {
746 final BitSet bitSet = new BitSet(128);
747 copyFromLong(bitSet, 0, bits0);
748 copyFromLong(bitSet, 64, bits1);
749 return bitSet;
750 }
751 public Iterator<Integer> iterator() {
752 return new Iterator<Integer>() {
753 long bits0 = Mid128.this.bits0;
754 long bits1 = Mid128.this.bits1;
755 int pos = -1;
756 public boolean hasNext() {
757 if (bits0 != 0) {
758 if (bits0 == Long.MIN_VALUE) {
759 pos = 63;
760 bits0 = 0;
761 return true;
762 }
763 long b = (bits0&-bits0);
764 int delta = 0;
765 while (b >= 256) {
766 b = (b >> 8);
767 delta += 8;
768 }
769 int p = bitPositionTable[(int) b];
770 if (p >= 0) {
771 p += delta;
772 } else {
773 p = delta;
774 }
775 if (pos < 0) {
776 pos = p;
777 } else if (p == 0) {
778 pos++;
779 } else {
780 pos += (p + 1);
781 }
782 bits0 = bits0 >>> (p + 1);
783 return true;
784 } else {
785 if (pos < 63) {
786 pos = 63;
787 }
788 if (bits1 == Long.MIN_VALUE) {
789 pos = 127;
790 bits1 = 0;
791 return true;
792 }
793 long b = (bits1&-bits1);
794 if (b == 0) {
795 return false;
796 }
797 int delta = 0;
798 while (b >= 256) {
799 b = (b >> 8);
800 delta += 8;
801 }
802 int p = bitPositionTable[(int) b];
803 if (p >= 0) {
804 p += delta;
805 } else {
806 p = delta;
807 }
808 if (pos < 0) {
809 pos = p;
810 } else if (p == 63) {
811 pos++;
812 } else {
813 pos += (p + 1);
814 }
815 bits1 = bits1 >>> (p + 1);
816 return true;
817 }
818 }
819 public Integer next() {
820 return Integer.valueOf(pos);
821 }
822 public void remove() {
823 throw new UnsupportedOperationException("remove");
824 }
825 };
826 }
827
828 public boolean equals(Object o) {
829 if (this == o) {
830 return true;
831 }
832 if (o instanceof BitKey.Small) {
833 BitKey.Small other = (BitKey.Small) o;
834 return (this.bits0 == other.bits) && (this.bits1 == 0);
835
836 } else if (o instanceof BitKey.Mid128) {
837 BitKey.Mid128 other = (BitKey.Mid128) o;
838 return (this.bits0 == other.bits0) &&
839 (this.bits1 == other.bits1);
840
841 } else if (o instanceof BitKey.Big) {
842 BitKey.Big other = (BitKey.Big) o;
843 if (this.bits0 != other.bits[0]) {
844 return false;
845 } else if (this.bits1 != other.bits[1]) {
846 return false;
847 } else {
848 for (int i = 2; i < other.bits.length; i++) {
849 if (other.bits[i] != 0) {
850 return false;
851 }
852 }
853 return true;
854 }
855 }
856 return false;
857 }
858 public int hashCode() {
859 long h = 1234;
860 h ^= bits0;
861 h ^= bits1 * 2;
862 return (int)((h >> 32) ^ h);
863 }
864 public String toString() {
865 StringBuilder buf = new StringBuilder(64);
866 buf.append("0x");
867 for (int i = 127; i >= 0; i--) {
868 buf.append((get(i)) ? '1' : '0');
869 }
870 return buf.toString();
871 }
872 public BitKey copy() {
873 return new Mid128(this);
874 }
875 public BitKey emptyCopy() {
876 return new Mid128();
877 }
878
879 public boolean isEmpty() {
880 return bits0 == 0 &&
881 bits1 == 0;
882 }
883
884 // implement Comparable (in lazy, expensive fashion)
885 public int compareTo(BitKey bitKey) {
886 return toString().compareTo(bitKey.toString());
887 }
888 }
889
890 /**
891 * Implementation of {@link BitKey} with more than 64 bits. Similar to
892 * {@link java.util.BitSet}, but does not require dynamic resizing.
893 */
894 public class Big extends AbstractBitKey {
895 private long[] bits;
896
897 private Big(int size) {
898 bits = new long[chunkCount(size + 1)];
899 }
900 private Big(Big big) {
901 bits = (long[]) big.bits.clone();
902 }
903 private int size() {
904 return bits.length;
905 }
906 public void set(int pos) {
907 bits[chunkPos(pos)] |= bit(pos);
908 }
909
910 public boolean get(int pos) {
911 return (bits[chunkPos(pos)] & bit(pos)) != 0;
912 }
913 public void clear(int pos) {
914 bits[chunkPos(pos)] &= ~bit(pos);
915 }
916 public void clear() {
917 for (int i = 0; i < bits.length; i++) {
918 bits[i] = 0;
919 }
920 }
921 private void or(long bits0) {
922 this.bits[0] |= bits0;
923 }
924 private void or(long bits0, long bits1) {
925 this.bits[0] |= bits0;
926 this.bits[1] |= bits1;
927 }
928 private void or(long[] bits) {
929 for (int i = 0; i < bits.length; i++) {
930 this.bits[i] |= bits[i];
931 }
932 }
933 private void and(long[] bits) {
934 int length = Math.min(bits.length, this.bits.length);
935 for (int i = 0; i < length; i++) {
936 this.bits[i] &= bits[i];
937 }
938 for (int i = bits.length; i < this.bits.length; i++) {
939 this.bits[i] = 0;
940 }
941 }
942
943 public BitKey or(BitKey bitKey) {
944 if (bitKey instanceof BitKey.Small) {
945 final BitKey.Small other = (BitKey.Small) bitKey;
946 final BitKey.Big bk = (BitKey.Big) copy();
947 bk.or(other.bits);
948 return bk;
949
950 } else if (bitKey instanceof BitKey.Mid128) {
951 final BitKey.Mid128 other = (BitKey.Mid128) bitKey;
952 final BitKey.Big bk = (BitKey.Big) copy();
953 bk.or(other.bits0, other.bits1);
954 return bk;
955
956 } else if (bitKey instanceof BitKey.Big) {
957 final BitKey.Big other = (BitKey.Big) bitKey;
958 if (other.size() > size()) {
959 final BitKey.Big bk = (BitKey.Big) other.copy();
960 bk.or(bits);
961 return bk;
962 } else {
963 final BitKey.Big bk = (BitKey.Big) copy();
964 bk.or(other.bits);
965 return bk;
966 }
967 }
968
969 throw createException(bitKey);
970 }
971
972 public BitKey and(BitKey bitKey) {
973 if (bitKey instanceof BitKey.Small) {
974 final BitKey.Small bk = (BitKey.Small) bitKey.copy();
975 bk.and(bits[0]);
976 return bk;
977
978 } else if (bitKey instanceof BitKey.Mid128) {
979 final BitKey.Mid128 bk = (BitKey.Mid128) bitKey.copy();
980 bk.and(bits[0], bits[1]);
981 return bk;
982
983 } else if (bitKey instanceof BitKey.Big) {
984 final BitKey.Big other = (BitKey.Big) bitKey;
985 if (other.size() < size()) {
986 final BitKey.Big bk = (BitKey.Big) other.copy();
987 bk.and(bits);
988 return bk;
989 } else {
990 final BitKey.Big bk = (BitKey.Big) copy();
991 bk.and(other.bits);
992 return bk;
993 }
994 }
995
996 throw createException(bitKey);
997 }
998
999 public BitKey andNot(BitKey bitKey) {
1000 if (bitKey instanceof BitKey.Small) {
1001 final BitKey.Small other = (BitKey.Small) bitKey;
1002 final BitKey.Big bk = (BitKey.Big) copy();
1003 bk.andNot(other.bits);
1004 return bk;
1005
1006 } else if (bitKey instanceof BitKey.Mid128) {
1007 final BitKey.Mid128 other = (Mid128) bitKey;
1008 final BitKey.Big bk = (BitKey.Big) copy();
1009 bk.andNot(other.bits0, other.bits1);
1010 return bk;
1011
1012 } else if (bitKey instanceof BitKey.Big) {
1013 final BitKey.Big other = (BitKey.Big) bitKey;
1014 final BitKey.Big bk = (BitKey.Big) copy();
1015 bk.andNot(other.bits);
1016 return bk;
1017 }
1018
1019 throw createException(bitKey);
1020 }
1021
1022 private void andNot(long[] bits) {
1023 for (int i = 0; i < bits.length; i++) {
1024 this.bits[i] &= ~bits[i];
1025
1026 }
1027 }
1028
1029 private void andNot(long bits0, long bits1) {
1030 this.bits[0] &= ~bits0;
1031 this.bits[1] &= ~bits1;
1032 }
1033
1034 private void andNot(long bits) {
1035 this.bits[0] &= ~bits;
1036 }
1037
1038 public boolean isSuperSetOf(BitKey bitKey) {
1039 if (bitKey instanceof BitKey.Small) {
1040 BitKey.Small other = (BitKey.Small) bitKey;
1041 return ((this.bits[0] | other.bits) == this.bits[0]);
1042
1043 } else if (bitKey instanceof BitKey.Mid128) {
1044 BitKey.Mid128 other = (BitKey.Mid128) bitKey;
1045 return ((this.bits[0] | other.bits0) == this.bits[0]) &&
1046 ((this.bits[1] | other.bits1) == this.bits[1]);
1047
1048 } else if (bitKey instanceof BitKey.Big) {
1049 BitKey.Big other = (BitKey.Big) bitKey;
1050
1051 int len = Math.min(bits.length, other.bits.length);
1052 for (int i = 0; i < len; i++) {
1053 if ((this.bits[i] | other.bits[i]) != this.bits[i]) {
1054 return false;
1055 }
1056 }
1057 if (other.bits.length > this.bits.length) {
1058 for (int i = len; i < other.bits.length; i++) {
1059 if (other.bits[i] != 0) {
1060 return false;
1061 }
1062 }
1063 }
1064 return true;
1065 }
1066 return false;
1067 }
1068
1069 public boolean intersects(BitKey bitKey) {
1070 if (bitKey instanceof BitKey.Small) {
1071 BitKey.Small other = (BitKey.Small) bitKey;
1072 return (this.bits[0] & other.bits) != 0;
1073
1074 } else if (bitKey instanceof BitKey.Mid128) {
1075 BitKey.Mid128 other = (BitKey.Mid128) bitKey;
1076 return (this.bits[0] & other.bits0) != 0 ||
1077 (this.bits[1] & other.bits1) != 0;
1078
1079 } else if (bitKey instanceof BitKey.Big) {
1080 BitKey.Big other = (BitKey.Big) bitKey;
1081
1082 int len = Math.min(bits.length, other.bits.length);
1083 for (int i = 0; i < len; i++) {
1084 if ((this.bits[i] & other.bits[i]) != 0) {
1085 return true;
1086 }
1087 }
1088 return false;
1089 }
1090 return false;
1091 }
1092
1093 public BitSet toBitSet() {
1094 final BitSet bitSet = new BitSet(64);
1095 int pos = 0;
1096 for (int i = 0; i < bits.length; i++) {
1097 copyFromLong(bitSet, pos, bits[i]);
1098 pos += 64;
1099 }
1100 return bitSet;
1101 }
1102 public Iterator<Integer> iterator() {
1103 return new Iterator<Integer>() {
1104 long[] bits = Big.this.bits.clone();
1105 int pos = -1;
1106 int index = 0;
1107 public boolean hasNext() {
1108 if (index >= bits.length) {
1109 return false;
1110 }
1111 if (pos < 0) {
1112 while (bits[index] == 0) {
1113 index++;
1114 if (index >= bits.length) {
1115 return false;
1116 }
1117 }
1118 pos = (64 * index) - 1;
1119 }
1120 long bs = bits[index];
1121 if (bs == 0) {
1122 while (bits[index] == 0) {
1123 index++;
1124 if (index >= bits.length) {
1125 return false;
1126 }
1127 }
1128 pos = (64 * index) - 1;
1129 bs = bits[index];
1130 }
1131 if (bs != 0) {
1132 if (bs == Long.MIN_VALUE) {
1133 pos = (64 * index) + 63;
1134 bits[index] = 0;
1135 return true;
1136 }
1137 long b = (bs&-bs);
1138 int delta = 0;
1139 while (b >= 256) {
1140 b = (b >> 8);
1141 delta += 8;
1142 }
1143 int p = bitPositionTable[(int) b];
1144 if (p >= 0) {
1145 p += delta;
1146 } else {
1147 p = delta;
1148 }
1149 if (pos < 0) {
1150 pos = p;
1151 } else if (p == 0) {
1152 pos++;
1153 } else {
1154 pos += (p + 1);
1155 }
1156 bits[index] = bits[index] >>> (p + 1);
1157 return true;
1158 }
1159 return false;
1160 }
1161 public Integer next() {
1162 return Integer.valueOf(pos);
1163 }
1164 public void remove() {
1165 throw new UnsupportedOperationException("remove");
1166 }
1167 };
1168 }
1169 public boolean equals(Object o) {
1170 if (this == o) {
1171 return true;
1172 }
1173 if (o instanceof BitKey.Small) {
1174 BitKey.Small other = (BitKey.Small) o;
1175 if (this.bits[0] != other.bits) {
1176 return false;
1177 } else {
1178 for (int i = 1; i < this.bits.length; i++) {
1179 if (this.bits[i] != 0) {
1180 return false;
1181 }
1182 }
1183 return true;
1184 }
1185
1186 } else if (o instanceof BitKey.Mid128) {
1187 BitKey.Mid128 other = (BitKey.Mid128) o;
1188 if (this.bits[0] != other.bits0) {
1189 return false;
1190 } else if (this.bits[1] != other.bits1) {
1191 return false;
1192 } else {
1193 for (int i = 2; i < this.bits.length; i++) {
1194 if (this.bits[i] != 0) {
1195 return false;
1196 }
1197 }
1198 return true;
1199 }
1200
1201 } else if (o instanceof BitKey.Big) {
1202 BitKey.Big other = (BitKey.Big) o;
1203
1204 int len = Math.min(bits.length, other.bits.length);
1205 for (int i = 0; i < len; i++) {
1206 if (this.bits[i] != other.bits[i]) {
1207 return false;
1208 }
1209 }
1210 if (this.bits.length > other.bits.length) {
1211 for (int i = len; i < this.bits.length; i++) {
1212 if (this.bits[i] != 0) {
1213 return false;
1214 }
1215 }
1216 } else if (other.bits.length > this.bits.length) {
1217 for (int i = len; i < other.bits.length; i++) {
1218 if (other.bits[i] != 0) {
1219 return false;
1220 }
1221 }
1222 }
1223 return true;
1224 }
1225 return false;
1226 }
1227 public int hashCode() {
1228 long h = 1234;
1229 for (int i = bits.length; --i >= 0;) {
1230 h ^= bits[i] * (i + 1);
1231 }
1232 return (int)((h >> 32) ^ h);
1233 }
1234 public String toString() {
1235 StringBuilder buf = new StringBuilder(64);
1236 buf.append("0x");
1237 int start = bits.length * 64 - 1;
1238 for (int i = start; i >= 0; i--) {
1239 buf.append((get(i)) ? '1' : '0');
1240 }
1241 return buf.toString();
1242 }
1243
1244 public BitKey copy() {
1245 return new Big(this);
1246 }
1247
1248 public BitKey emptyCopy() {
1249 return new Big(bits.length << ChunkBitCount);
1250 }
1251
1252 public boolean isEmpty() {
1253 for (long bit : bits) {
1254 if (bit != 0) {
1255 return false;
1256 }
1257 }
1258 return true;
1259 }
1260
1261 // implement Comparable (in lazy, expensive fashion)
1262 public int compareTo(BitKey bitKey) {
1263 return toString().compareTo(bitKey.toString());
1264 }
1265 }
1266
1267 final static byte bitPositionTable[] = {
1268 -1, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1269 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1270 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1271 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1272 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1273 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1274 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1275 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1276 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1277 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1278 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1279 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1280 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1281 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1282 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1283 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
1284
1285
1286 }
1287
1288 // End BitKey.java