KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > bak > pcj > set > ShortBitSet


1 /*
2  * Primitive Collections for Java.
3  * Copyright (C) 2002, 2003 Søren Bak
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */

19 package bak.pcj.set;
20
21 import bak.pcj.ShortIterator;
22 import bak.pcj.ShortCollection;
23 import bak.pcj.util.Exceptions;
24 import java.util.NoSuchElementException JavaDoc;
25
26 import java.io.Serializable JavaDoc;
27
28 /**
29  * This class represents bit array based sets of short values. When a
30  * bit in the underlying array is set, the value having the same
31  * number as the bit is contained in the array. This implies that
32  * bit sets cannot contain negative values.
33  *
34  * <p>Implementation of
35  * ShortSortedSet is supported from PCJ 1.2. Prior to 1.2, only ShortSet
36  * was implemented.
37  *
38  * <p>Note: There is no growth policy involved with bit sets. The number
39  * of bits to use depends on the value of the largest element and not
40  * the size of the set. While sizes are predictable (they grow), a
41  * new maximum element is generally not predictable making it
42  * meaningless to grow the array at a specific rate.
43  *
44  * @author S&oslash;ren Bak
45  * @version 1.3 21-08-2003 19:54
46  * @since 1.0
47  */

48 public class ShortBitSet extends AbstractShortSet implements ShortSortedSet, Cloneable JavaDoc, Serializable JavaDoc {
49
50     private static final int BITS_PER_LONG = 64;
51     private static final int BIT_MASK = 0x0000003F;
52     private static final int BIT_MASK_BITS = 6;
53     private static final int DEFAULT_CAPACITY = BITS_PER_LONG;
54
55     /**
56      * The array of bits backing up this set.
57      * @serial
58      */

59     private long[] data;
60
61     /**
62      * The size of this set.
63      * @serial
64      */

65     private int size;
66
67     /**
68      * Creates a new bit set with a specified maximum value.
69      *
70      * @param maximum
71      * the maximum value representable by the new bitset.
72      *
73      * @throws IllegalArgumentException
74      * if <tt>capacity</tt> is negative.
75      */

76     public ShortBitSet(short maximum) {
77         if (maximum < 0)
78             Exceptions.negativeArgument("maximum", String.valueOf(maximum));
79         data = new long[1+longIndex(maximum)];
80         size = 0;
81     }
82
83     /**
84      * Creates a new empty bit set with a capacity of 64.
85      */

86     public ShortBitSet() {
87         this((short)DEFAULT_CAPACITY);
88     }
89
90     /**
91      * Creates a new bit set with the same elements as the specified
92      * collection.
93      *
94      * @param c
95      * the collection whose elements to add to the new
96      * bit set.
97      *
98      * @throws NullPointerException
99      * if <tt>c</tt> is <tt>null</tt>.
100      *
101      * @throws IllegalArgumentException
102      * if any of the elements of the specified collection
103      * is negative.
104      */

105     public ShortBitSet(ShortCollection c) {
106         this();
107         addAll(c);
108     }
109
110     /**
111      * Creates a new bit set with the same elements as the specified
112      * array.
113      *
114      * @param a
115      * the array whose elements to add to the new
116      * bit set.
117      *
118      * @throws NullPointerException
119      * if <tt>a</tt> is <tt>null</tt>.
120      *
121      * @throws IllegalArgumentException
122      * if any of the elements of the specified array
123      * is negative.
124      *
125      * @since 1.1
126      */

127     public ShortBitSet(short[] a) {
128         // Find max element n order to avoid repeated capacity increases
129
this(amax(a));
130         // Add all elements
131
for (int i = 0; i < a.length; i++)
132             add(a[i]);
133     }
134
135     private static short amax(short[] a) {
136         short max = (short)0;
137         for (int i = 0; i < a.length; i++)
138             if (a[i] > max) max = a[i];
139         return max;
140     }
141
142     // ---------------------------------------------------------------
143
// Bit management
144
// ---------------------------------------------------------------
145

146     private static int longIndex(int index)
147     { return index >> BIT_MASK_BITS; }
148
149     private static int bitIndex(int index)
150     { return index & BIT_MASK; }
151
152     private static long bit(int bitno)
153     { return 1L << bitno; }
154
155     private static int largestBitIndexOf(long v) {
156         if (v == 0L)
157             throw new IllegalArgumentException JavaDoc("No elements left");
158         int bitIndex = BITS_PER_LONG-1;
159         long bit = 1L << bitIndex;
160         while ((v & bit) == 0L) {
161             bitIndex--;
162             bit >>= 1;
163         }
164         return bitIndex;
165     }
166
167     private static int smallestBitIndexOf(long v) {
168         if (v == 0L)
169             throw new IllegalArgumentException JavaDoc("No elements left");
170         int bitIndex = 0;
171         long bit = 1L;
172         while ((v & bit) == 0L) {
173             bitIndex++;
174             bit <<= 1;
175         }
176         return bitIndex;
177     }
178
179     private static int countBits(long v) {
180         int count = 0;
181         int bitIndex = 0;
182         long bit = 1L;
183         do {
184             if ((v & bit) != 0L)
185                 count++;
186             bitIndex++;
187             bit <<= 1;
188         } while (bitIndex < BITS_PER_LONG);
189         return count;
190     }
191
192     private static long lowMask(int n) {
193         long v = 0L;
194         for (int i = 0; i < n; i++)
195             v = (v << 1) | 1L;
196         return v;
197     }
198
199     private static long highMask(int n) {
200         return ~lowMask(n);
201     }
202
203
204     /**
205      * Ensures that this bit set can contain a specified maximum
206      * element without increasing the capacity. If many elements are
207      * added, and the maximum element among those is known before
208      * they are added, this method may improve performance.
209      *
210      * @param maximum
211      * the maximum element that this set should be able
212      * to contain without increasing the capacity.
213      *
214      * @throws IllegalArgumentException
215      * if <tt>maximum</tt> is negative.
216      */

217     public void ensureCapacity(int maximum) {
218         if (maximum < 0)
219             Exceptions.negativeArgument("maximum", String.valueOf(maximum));
220         int newcapacity = 1+longIndex(maximum);
221         if (data.length < newcapacity) {
222             long[] newdata = new long[newcapacity];
223             System.arraycopy(data, 0, newdata, 0, data.length);
224             data = newdata;
225         }
226     }
227
228     // ---------------------------------------------------------------
229
// Operations not supported by abstract implementation
230
// ---------------------------------------------------------------
231

232     /**
233      * @throws IllegalArgumentException
234      * if <tt>value</tt> is negative.
235      */

236     public boolean add(short value) {
237         if (value < 0)
238             Exceptions.negativeArgument("value", String.valueOf(value));
239         int longIndex = longIndex(value);
240         if (data.length < 1+longIndex)
241             ensureCapacity(value);
242         long bit = bit(bitIndex(value));
243         boolean result = (data[longIndex] & bit) == 0;
244         if (result)
245             size++;
246         data[longIndex] |= bit;
247         return result;
248     }
249
250     public ShortIterator iterator() {
251         if (size == 0)
252             return new ShortIterator() {
253                 public boolean hasNext()
254                 { return false; }
255                 public short next()
256                 { Exceptions.endOfIterator(); throw new RuntimeException JavaDoc(); }
257                 public void remove()
258                 { Exceptions.noElementToRemove(); }
259             };
260         return new ShortIterator() {
261             int nextLongIndex = nextLongIndex(0);
262             int nextBitIndex = nextLongIndex < data.length ? nextBitIndex(nextLongIndex, 0) : 0;
263             int lastValue = -1;
264
265             int nextLongIndex(int index) {
266                 while (index < data.length && data[index] == 0)
267                     index++;
268                 return index;
269             }
270
271             int nextBitIndex(int longIndex, int bitIndex) {
272                 long v = data[longIndex];
273                 long bit = 1L << bitIndex;
274                 while (bitIndex < BITS_PER_LONG && (v & bit) == 0) {
275                     bitIndex++;
276                     bit <<= 1;
277                 }
278                 return bitIndex;
279             }
280
281             public boolean hasNext() {
282                 return nextLongIndex < data.length;
283             }
284
285             public short next() {
286                 if (!hasNext())
287                     Exceptions.endOfIterator();
288                 lastValue = (short)(nextLongIndex*BITS_PER_LONG + nextBitIndex);
289
290                 // Advance pointers
291
nextBitIndex = nextBitIndex(nextLongIndex, nextBitIndex+1);
292                 if (nextBitIndex == BITS_PER_LONG) {
293                     nextLongIndex = nextLongIndex(nextLongIndex+1);
294                     if (nextLongIndex < data.length)
295                         nextBitIndex = nextBitIndex(nextLongIndex, 0);
296                 }
297                 return (short)lastValue;
298             }
299
300             public void remove() {
301                 if (lastValue < 0)
302                     Exceptions.noElementToRemove();
303                 ShortBitSet.this.remove((short)lastValue);
304                 lastValue = -1;
305             }
306
307         };
308     }
309
310     /**
311      * Minimizes the memory used by this bit set. The underlying
312      * array is replaced by an array whose size corresponds to
313      * the maximum elements in this bit set. The method can be used to
314      * free up memory after many removals.
315      */

316     public void trimToSize() {
317         // Find maximum element
318
int n = data.length-1;
319         while (n >= 0 && data[n] == 0L)
320             n--;
321         // Trim
322
if (n < data.length-1) {
323             long[] newdata = new long[1+n];
324             System.arraycopy(data, 0, newdata, 0, newdata.length);
325             data = newdata;
326         }
327     }
328
329     /**
330      * Returns a clone of this bit set.
331      *
332      * @return a clone of this bit set.
333      *
334      * @since 1.1
335      */

336     public Object JavaDoc clone() {
337         try {
338             ShortBitSet c = (ShortBitSet)super.clone();
339             c.data = new long[data.length];
340             System.arraycopy(data, 0, c.data, 0, data.length);
341             return c;
342         } catch (CloneNotSupportedException JavaDoc e) {
343             Exceptions.cloning(); throw new RuntimeException JavaDoc();
344         }
345     }
346
347     // ---------------------------------------------------------------
348
// Operations overwritten for efficiency
349
// ---------------------------------------------------------------
350

351     public void clear() {
352         for (int i = 0; i < data.length; i++)
353             data[i] = 0;
354         size = 0;
355     }
356
357     public boolean contains(short value) {
358         if (value < 0)
359             return false;
360         int longIndex = longIndex(value);
361         if (longIndex >= data.length)
362             return false;
363         long bit = bit(bitIndex(value));
364         return (data[longIndex] & bit) != 0;
365     }
366
367     public boolean isEmpty()
368     { return size == 0; }
369
370     public boolean remove(short value) {
371         if (value < 0)
372             return false;
373         int longIndex = longIndex(value);
374         if (longIndex >= data.length)
375             return false;
376         long bit = bit(bitIndex(value));
377         boolean result = (data[longIndex] & bit) != 0;
378         if (result)
379             size--;
380         data[longIndex] &= ~bit;
381         return result;
382     }
383
384     public int size()
385     { return size; }
386
387     // ---------------------------------------------------------------
388
// Sorted set operations
389
// ---------------------------------------------------------------
390

391     private short firstFrom(short from) {
392         if (size == 0)
393             Exceptions.setNoFirst();
394         int longIndex = longIndex(from);
395         if (longIndex >= data.length)
396             Exceptions.setNoFirst();
397         long v = data[longIndex];
398         // Mask out all bits less than from
399
v &= highMask(bitIndex(from));
400         
401         try {
402             for (;;) {
403                 if (v != 0L) {
404                     int bitIndex = smallestBitIndexOf(v);
405                     return (short)(BITS_PER_LONG*longIndex + bitIndex);
406                 }
407                 v = data[++longIndex];
408             }
409         } catch (IndexOutOfBoundsException JavaDoc e) {
410             Exceptions.setNoFirst(); throw new RuntimeException JavaDoc();
411         }
412     }
413
414     /**
415      * @since 1.2
416      */

417     public short first() {
418         return firstFrom((short)0);
419     }
420
421     private short lastFrom(short from) {
422         if (size == 0)
423             Exceptions.setNoLast();
424         int longIndex = Math.min(longIndex(from), data.length-1);
425         long v = data[longIndex];
426         // Mask out all bits greater than from
427
v &= lowMask(bitIndex(from)+1);
428         try {
429             for (;;) {
430                 if (v != 0L) {
431                     int bitIndex = largestBitIndexOf(v);
432                     return (short)(BITS_PER_LONG*longIndex + bitIndex);
433                 }
434                 v = data[--longIndex];
435             }
436         } catch (IndexOutOfBoundsException JavaDoc e) {
437             Exceptions.setNoLast(); throw new RuntimeException JavaDoc();
438         }
439     }
440
441     /**
442      * @since 1.2
443      */

444     public short last() {
445         if (size == 0)
446             Exceptions.setNoLast();
447         int longIndex = data.length-1;
448         // Find last non-zero long
449
while (data[longIndex] == 0)
450             longIndex--;
451         long v = data[longIndex];
452         int bitIndex = BITS_PER_LONG-1;
453         long bit = 1L << bitIndex;
454         while ((v & bit) == 0) {
455             bitIndex--;
456             bit >>= 1;
457         }
458         return (short)(BITS_PER_LONG*longIndex + bitIndex);
459     }
460
461     /**
462      * @since 1.2
463      */

464     public ShortSortedSet headSet(short to) {
465         return new SubSet(false, (short)0, true, to);
466     }
467
468     /**
469      * @since 1.2
470      */

471     public ShortSortedSet tailSet(short from) {
472         return new SubSet(true, from, false, (short)0);
473     }
474
475     /**
476      * @since 1.2
477      */

478     public ShortSortedSet subSet(short from, short to) {
479         return new SubSet(true, from, true, to);
480     }
481
482     private class SubSet extends AbstractShortSet implements ShortSortedSet, java.io.Serializable JavaDoc {
483
484         private boolean hasLowerBound;
485         private boolean hasUpperBound;
486         private short lowerBound;
487         private short upperBound;
488
489         SubSet(boolean hasLowerBound, short lowerBound, boolean hasUpperBound, short upperBound) {
490             if (hasLowerBound) {
491                 if (lowerBound < 0)
492                     Exceptions.negativeArgument("lower bound", String.valueOf(lowerBound));
493                 if (hasUpperBound)
494                     if (upperBound < lowerBound)
495                         Exceptions.invalidSetBounds(String.valueOf(lowerBound), String.valueOf(upperBound));
496             }
497             this.hasLowerBound = hasLowerBound;
498             this.lowerBound = lowerBound;
499             this.hasUpperBound = hasUpperBound;
500             this.upperBound = upperBound;
501         }
502
503         public boolean add(short v) {
504             if (!inSubRange(v))
505                 Exceptions.valueNotInSubRange(String.valueOf(v));
506             return ShortBitSet.this.add(v);
507         }
508
509         public boolean remove(short v) {
510             if (!inSubRange(v))
511                 Exceptions.valueNotInSubRange(String.valueOf(v));
512             return ShortBitSet.this.remove(v);
513         }
514
515         public boolean contains(short v) {
516             return inSubRange(v) && ShortBitSet.this.contains(v);
517         }
518
519         class SubSetIterator implements ShortIterator {
520             int longIndexLow;
521             int longIndexHigh;
522             long vLow;
523             long vHigh;
524             boolean isEmpty;
525
526             int nextLongIndex;
527             int nextBitIndex;
528             int lastValue;
529
530             SubSetIterator() {
531                 lastValue = -1;
532                 isEmpty = false;
533                 try {
534                     longIndexLow = longIndex(first());
535                 } catch (NoSuchElementException JavaDoc e) {
536                     isEmpty = true;
537                 }
538                 if (!isEmpty) {
539                     longIndexHigh = longIndex(last());
540                     if (longIndexLow == longIndexHigh) {
541                         long v = data[longIndexLow];
542                         // Mask out all bits less than the lower bound
543
if (hasLowerBound)
544                             v &= highMask(bitIndex(lowerBound));
545                         // Mask out all bits greater than or equal to the upper bound
546
if (hasUpperBound)
547                             v &= lowMask(bitIndex(upperBound));
548                         size = countBits(v);
549                         vLow = vHigh = v;
550                     } else {
551                         // Mask out all bits less than the lower bound
552
vLow = data[longIndexLow];
553                         if (hasLowerBound)
554                             vLow &= highMask(bitIndex(lowerBound));
555                         
556                         // Mask out all bits greater than or equal to the upper bound
557
vHigh = data[longIndexHigh];
558                         if (hasUpperBound)
559                             vHigh &= lowMask(bitIndex(upperBound));
560                     }
561                     nextLongIndex = longIndexLow;
562                     nextBitIndex = smallestBitIndexOf(vLow);
563                 }
564             }
565
566             long data(int longIndex) {
567                 if (longIndex == longIndexLow)
568                     return vLow;
569                 if (longIndex == longIndexHigh)
570                     return vHigh;
571                 return data[longIndex];
572             }
573
574             int nextLongIndex(int index) {
575                 while (index <= longIndexHigh && data(index) == 0)
576                     index++;
577                 return index;
578             }
579
580             int nextBitIndex(int longIndex, int bitIndex) {
581                 long v = data(longIndex);
582                 long bit = 1L << bitIndex;
583                 while (bitIndex < BITS_PER_LONG && (v & bit) == 0) {
584                     bitIndex++;
585                     bit <<= 1;
586                 }
587                 return bitIndex;
588             }
589
590             public boolean hasNext() {
591                 return (!isEmpty) && (nextLongIndex <= longIndexHigh);
592             }
593
594             public short next() {
595                 if (!hasNext())
596                     Exceptions.endOfIterator();
597                 lastValue = (short)(nextLongIndex*BITS_PER_LONG + nextBitIndex);
598
599                 // Advance pointers
600
nextBitIndex = nextBitIndex(nextLongIndex, nextBitIndex+1);
601                 if (nextBitIndex == BITS_PER_LONG) {
602                     nextLongIndex = nextLongIndex(nextLongIndex+1);
603                     if (nextLongIndex < data.length)
604                         nextBitIndex = nextBitIndex(nextLongIndex, 0);
605                 }
606                 return (short)lastValue;
607             }
608
609             public void remove() {
610                 if (lastValue < 0)
611                     Exceptions.noElementToRemove();
612                 ShortBitSet.this.remove((short)lastValue);
613                 lastValue = -1;
614             }
615         }
616
617         public ShortIterator iterator() {
618             return new SubSetIterator();
619         }
620
621         public int size() {
622             if (ShortBitSet.this.size() == 0)
623                 return 0;
624             int size;
625             int longIndexLow;
626             try {
627                 longIndexLow = longIndex(first());
628             } catch (NoSuchElementException JavaDoc e) {
629                 return 0;
630             }
631             int longIndexHigh = longIndex(last());
632             if (longIndexLow == longIndexHigh) {
633                 long v = data[longIndexLow];
634                 // Mask out all bits less than the lower bound
635
if (hasLowerBound)
636                     v &= highMask(bitIndex(lowerBound));
637                 // Mask out all bits greater than or equal to the upper bound
638
if (hasUpperBound)
639                     v &= lowMask(bitIndex(upperBound));
640                 size = countBits(v);
641             } else {
642                 // Mask out all bits less than the lower bound
643
long vLow = data[longIndexLow];
644                 if (hasLowerBound)
645                     vLow &= highMask(bitIndex(lowerBound));
646                 
647                 // Mask out all bits greater than or equal to the upper bound
648
long vHigh = data[longIndexHigh];
649                 if (hasUpperBound)
650                     vHigh &= lowMask(bitIndex(upperBound));
651                 
652                 size = countBits(vLow) + countBits(vHigh);
653                 for (int i = longIndexLow+1; i < longIndexHigh; i++)
654                     size += countBits(data[i]);
655             }
656             return size;
657         }
658
659         public short first() {
660             short first = firstFrom(hasLowerBound ? lowerBound : 0);
661             if (hasUpperBound && first >= upperBound)
662                 Exceptions.setNoFirst();
663             return first;
664         }
665
666         public short last() {
667             short last = lastFrom(hasUpperBound ? (short)(upperBound-1) : ShortBitSet.this.last());
668             if (hasLowerBound && last < lowerBound)
669                 Exceptions.setNoLast();
670             return last;
671         }
672
673         public ShortSortedSet headSet(short to) {
674             if (!inSubRange(to))
675                 Exceptions.invalidUpperBound(String.valueOf(to));
676             return new SubSet(hasLowerBound, lowerBound, true, to);
677         }
678
679         public ShortSortedSet tailSet(short from) {
680             if (!inSubRange(from))
681                 Exceptions.invalidLowerBound(String.valueOf(from));
682             return new SubSet(true, from, hasUpperBound, upperBound);
683         }
684
685         public ShortSortedSet subSet(short from, short to) {
686             if (!inSubRange(from))
687                 Exceptions.invalidLowerBound(String.valueOf(from));
688             if (!inSubRange(to))
689                 Exceptions.invalidUpperBound(String.valueOf(to));
690             return new SubSet(true, from, true, to);
691         }
692
693         private boolean inSubRange(short v) {
694             if (hasLowerBound && v < lowerBound)
695                 return false;
696             if (hasUpperBound && v >= upperBound)
697                 return false;
698             return true;
699         }
700
701     }
702
703 }
Popular Tags