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