BitKey


1   /*
2   // $Id: //open/mondrian/src/main/mondrian/rolap/BitKey.java#12 $
3   // This software is subject to the terms of the Common Public License
4   // Agreement, available at the following URL:
5   // http://www.opensource.org/licenses/cpl.html.
6   // Copyright (C) 2001-2002 Kana Software, Inc.
7   // Copyright (C) 2001-2007 Julian Hyde and others
8   // All Rights Reserved.
9   // You must accept the terms of that agreement to use this software.
10  //
11  // jhyde, 30 August, 2001
12  */
13  
14  package mondrian.rolap;
15  
16  import java.util.BitSet  ;
17  import java.util.Iterator  ;
18  
19  /**
20   * Represents a set of bits.
21   *
22   * <p>Unlike {@link java.util.BitSet}, the number of bits cannot be changed
23   * after the BitKey is created. This allows us to optimize.
24   *
25   * <p>If you have a collection of immutable objects, each of which has a unique
26   * positive number and you wish to do comparisons between subsets of those
27   * objects testing for equality, then encoding the subsets as BitKeys is very
28   * efficient.
29   *
30   * <p>There are two implementations that target groups of objects with maximum
31   * number less than 64 and less than 128; and there is one implements that is
32   * general for any positive number.
33   *
34   * <p>One caution: if the maximum number assigned to one of the
35   * objects is large, then this representation might be sparse and therefore
36   * not efficient.
37   *
38   * @author Richard M. Emberson
39   * @version $Id: //open/mondrian/src/main/mondrian/rolap/BitKey.java#12 $
40   */
41  public interface BitKey extends Comparable  <BitKey>, Iterable  <Integer  > {
42  
43      /**
44       * Sets the bit at the specified index to the specified value.
45       */
46      void set(int bitIndex, boolean value);
47  
48      /**
49       * Sets the bit at the specified index to <code>true</code>.
50       */
51      void set(int bitIndex);
52  
53      /**
54       * Returns the value of the bit with the specified index. The value
55       * is <code>true</code> if the bit with the index <code>bitIndex</code>
56       * is currently set in this <code>BitKey</code>; otherwise, the result
57       * is <code>false</code>.
58       */
59      boolean get(int bitIndex);
60  
61      /**
62       * Sets the bit specified by the index to <code>false</code>.
63       */
64      void clear(int bitIndex);
65  
66      /**
67       * Sets all of the bits in this BitKey to <code>false</code>.
68       */
69      void clear();
70  
71      /**
72       * Is every bit set in the parameter <code>bitKey</code> also set in
73       * <code>this</code>.
74       * If one switches <code>this</code> with the parameter <code>bitKey</code>
75       * one gets the equivalent of isSubSetOf.
76       *
77       * @param bitKey
78       */
79      boolean isSuperSetOf(BitKey bitKey);
80  
81      /**
82       * Or the parameter <code>BitKey</code> with <code>this</code>.
83       *
84       * @param bitKey
85       */
86      BitKey or(BitKey bitKey);
87  
88      /**
89       * Returns the boolean AND of this bitkey and the given bitkey.
90       */
91      BitKey and(BitKey bitKey);
92  
93      /**
94       * Returns a <code>BitKey</code> containing all of the bits in this
95       * <code>BitSet</code> whose corresponding
96       * bit is NOT set in the specified <code>BitSet</code>.
97       */
98      BitKey andNot(BitKey bitKey);
99  
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 new Integer  (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 new Integer  (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 new Integer  (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
1289
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags