001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 2002, 2003 Søren Bak
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019: package bak.pcj.set;
020:
021: import bak.pcj.ByteIterator;
022: import bak.pcj.ByteCollection;
023: import bak.pcj.util.Exceptions;
024: import java.util.NoSuchElementException;
025:
026: import java.io.Serializable;
027:
028: /**
029: * This class represents bit array based sets of byte values. When a
030: * bit in the underlying array is set, the value having the same
031: * number as the bit is contained in the array. This implies that
032: * bit sets cannot contain negative values.
033: *
034: * <p>Implementation of
035: * ByteSortedSet is supported from PCJ 1.2. Prior to 1.2, only ByteSet
036: * was implemented.
037: *
038: * <p>Note: There is no growth policy involved with bit sets. The number
039: * of bits to use depends on the value of the largest element and not
040: * the size of the set. While sizes are predictable (they grow), a
041: * new maximum element is generally not predictable making it
042: * meaningless to grow the array at a specific rate.
043: *
044: * @author Søren Bak
045: * @version 1.3 21-08-2003 19:54
046: * @since 1.0
047: */
048: public class ByteBitSet extends AbstractByteSet implements
049: ByteSortedSet, Cloneable, Serializable {
050:
051: private static final int BITS_PER_LONG = 64;
052: private static final int BIT_MASK = 0x0000003F;
053: private static final int BIT_MASK_BITS = 6;
054: private static final int DEFAULT_CAPACITY = BITS_PER_LONG;
055:
056: /**
057: * The array of bits backing up this set.
058: * @serial
059: */
060: private long[] data;
061:
062: /**
063: * The size of this set.
064: * @serial
065: */
066: private int size;
067:
068: /**
069: * Creates a new bit set with a specified maximum value.
070: *
071: * @param maximum
072: * the maximum value representable by the new bitset.
073: *
074: * @throws IllegalArgumentException
075: * if <tt>capacity</tt> is negative.
076: */
077: public ByteBitSet(byte maximum) {
078: if (maximum < 0)
079: Exceptions.negativeArgument("maximum", String
080: .valueOf(maximum));
081: data = new long[1 + longIndex(maximum)];
082: size = 0;
083: }
084:
085: /**
086: * Creates a new empty bit set with a capacity of 64.
087: */
088: public ByteBitSet() {
089: this ((byte) DEFAULT_CAPACITY);
090: }
091:
092: /**
093: * Creates a new bit set with the same elements as the specified
094: * collection.
095: *
096: * @param c
097: * the collection whose elements to add to the new
098: * bit set.
099: *
100: * @throws NullPointerException
101: * if <tt>c</tt> is <tt>null</tt>.
102: *
103: * @throws IllegalArgumentException
104: * if any of the elements of the specified collection
105: * is negative.
106: */
107: public ByteBitSet(ByteCollection c) {
108: this ();
109: addAll(c);
110: }
111:
112: /**
113: * Creates a new bit set with the same elements as the specified
114: * array.
115: *
116: * @param a
117: * the array whose elements to add to the new
118: * bit set.
119: *
120: * @throws NullPointerException
121: * if <tt>a</tt> is <tt>null</tt>.
122: *
123: * @throws IllegalArgumentException
124: * if any of the elements of the specified array
125: * is negative.
126: *
127: * @since 1.1
128: */
129: public ByteBitSet(byte[] a) {
130: // Find max element n order to avoid repeated capacity increases
131: this (amax(a));
132: // Add all elements
133: for (int i = 0; i < a.length; i++)
134: add(a[i]);
135: }
136:
137: private static byte amax(byte[] a) {
138: byte max = (byte) 0;
139: for (int i = 0; i < a.length; i++)
140: if (a[i] > max)
141: max = a[i];
142: return max;
143: }
144:
145: // ---------------------------------------------------------------
146: // Bit management
147: // ---------------------------------------------------------------
148:
149: private static int longIndex(int index) {
150: return index >> BIT_MASK_BITS;
151: }
152:
153: private static int bitIndex(int index) {
154: return index & BIT_MASK;
155: }
156:
157: private static long bit(int bitno) {
158: return 1L << bitno;
159: }
160:
161: private static int largestBitIndexOf(long v) {
162: if (v == 0L)
163: throw new IllegalArgumentException("No elements left");
164: int bitIndex = BITS_PER_LONG - 1;
165: long bit = 1L << bitIndex;
166: while ((v & bit) == 0L) {
167: bitIndex--;
168: bit >>= 1;
169: }
170: return bitIndex;
171: }
172:
173: private static int smallestBitIndexOf(long v) {
174: if (v == 0L)
175: throw new IllegalArgumentException("No elements left");
176: int bitIndex = 0;
177: long bit = 1L;
178: while ((v & bit) == 0L) {
179: bitIndex++;
180: bit <<= 1;
181: }
182: return bitIndex;
183: }
184:
185: private static int countBits(long v) {
186: int count = 0;
187: int bitIndex = 0;
188: long bit = 1L;
189: do {
190: if ((v & bit) != 0L)
191: count++;
192: bitIndex++;
193: bit <<= 1;
194: } while (bitIndex < BITS_PER_LONG);
195: return count;
196: }
197:
198: private static long lowMask(int n) {
199: long v = 0L;
200: for (int i = 0; i < n; i++)
201: v = (v << 1) | 1L;
202: return v;
203: }
204:
205: private static long highMask(int n) {
206: return ~lowMask(n);
207: }
208:
209: /**
210: * Ensures that this bit set can contain a specified maximum
211: * element without increasing the capacity. If many elements are
212: * added, and the maximum element among those is known before
213: * they are added, this method may improve performance.
214: *
215: * @param maximum
216: * the maximum element that this set should be able
217: * to contain without increasing the capacity.
218: *
219: * @throws IllegalArgumentException
220: * if <tt>maximum</tt> is negative.
221: */
222: public void ensureCapacity(int maximum) {
223: if (maximum < 0)
224: Exceptions.negativeArgument("maximum", String
225: .valueOf(maximum));
226: int newcapacity = 1 + longIndex(maximum);
227: if (data.length < newcapacity) {
228: long[] newdata = new long[newcapacity];
229: System.arraycopy(data, 0, newdata, 0, data.length);
230: data = newdata;
231: }
232: }
233:
234: // ---------------------------------------------------------------
235: // Operations not supported by abstract implementation
236: // ---------------------------------------------------------------
237:
238: /**
239: * @throws IllegalArgumentException
240: * if <tt>value</tt> is negative.
241: */
242: public boolean add(byte value) {
243: if (value < 0)
244: Exceptions.negativeArgument("value", String.valueOf(value));
245: int longIndex = longIndex(value);
246: if (data.length < 1 + longIndex)
247: ensureCapacity(value);
248: long bit = bit(bitIndex(value));
249: boolean result = (data[longIndex] & bit) == 0;
250: if (result)
251: size++;
252: data[longIndex] |= bit;
253: return result;
254: }
255:
256: public ByteIterator iterator() {
257: if (size == 0)
258: return new ByteIterator() {
259: public boolean hasNext() {
260: return false;
261: }
262:
263: public byte next() {
264: Exceptions.endOfIterator();
265: throw new RuntimeException();
266: }
267:
268: public void remove() {
269: Exceptions.noElementToRemove();
270: }
271: };
272: return new ByteIterator() {
273: int nextLongIndex = nextLongIndex(0);
274: int nextBitIndex = nextLongIndex < data.length ? nextBitIndex(
275: nextLongIndex, 0)
276: : 0;
277: int lastValue = -1;
278:
279: int nextLongIndex(int index) {
280: while (index < data.length && data[index] == 0)
281: index++;
282: return index;
283: }
284:
285: int nextBitIndex(int longIndex, int bitIndex) {
286: long v = data[longIndex];
287: long bit = 1L << bitIndex;
288: while (bitIndex < BITS_PER_LONG && (v & bit) == 0) {
289: bitIndex++;
290: bit <<= 1;
291: }
292: return bitIndex;
293: }
294:
295: public boolean hasNext() {
296: return nextLongIndex < data.length;
297: }
298:
299: public byte next() {
300: if (!hasNext())
301: Exceptions.endOfIterator();
302: lastValue = (byte) (nextLongIndex * BITS_PER_LONG + nextBitIndex);
303:
304: // Advance pointers
305: nextBitIndex = nextBitIndex(nextLongIndex,
306: nextBitIndex + 1);
307: if (nextBitIndex == BITS_PER_LONG) {
308: nextLongIndex = nextLongIndex(nextLongIndex + 1);
309: if (nextLongIndex < data.length)
310: nextBitIndex = nextBitIndex(nextLongIndex, 0);
311: }
312: return (byte) lastValue;
313: }
314:
315: public void remove() {
316: if (lastValue < 0)
317: Exceptions.noElementToRemove();
318: ByteBitSet.this .remove((byte) lastValue);
319: lastValue = -1;
320: }
321:
322: };
323: }
324:
325: /**
326: * Minimizes the memory used by this bit set. The underlying
327: * array is replaced by an array whose size corresponds to
328: * the maximum elements in this bit set. The method can be used to
329: * free up memory after many removals.
330: */
331: public void trimToSize() {
332: // Find maximum element
333: int n = data.length - 1;
334: while (n >= 0 && data[n] == 0L)
335: n--;
336: // Trim
337: if (n < data.length - 1) {
338: long[] newdata = new long[1 + n];
339: System.arraycopy(data, 0, newdata, 0, newdata.length);
340: data = newdata;
341: }
342: }
343:
344: /**
345: * Returns a clone of this bit set.
346: *
347: * @return a clone of this bit set.
348: *
349: * @since 1.1
350: */
351: public Object clone() {
352: try {
353: ByteBitSet c = (ByteBitSet) super .clone();
354: c.data = new long[data.length];
355: System.arraycopy(data, 0, c.data, 0, data.length);
356: return c;
357: } catch (CloneNotSupportedException e) {
358: Exceptions.cloning();
359: throw new RuntimeException();
360: }
361: }
362:
363: // ---------------------------------------------------------------
364: // Operations overwritten for efficiency
365: // ---------------------------------------------------------------
366:
367: public void clear() {
368: for (int i = 0; i < data.length; i++)
369: data[i] = 0;
370: size = 0;
371: }
372:
373: public boolean contains(byte value) {
374: if (value < 0)
375: return false;
376: int longIndex = longIndex(value);
377: if (longIndex >= data.length)
378: return false;
379: long bit = bit(bitIndex(value));
380: return (data[longIndex] & bit) != 0;
381: }
382:
383: public boolean isEmpty() {
384: return size == 0;
385: }
386:
387: public boolean remove(byte value) {
388: if (value < 0)
389: return false;
390: int longIndex = longIndex(value);
391: if (longIndex >= data.length)
392: return false;
393: long bit = bit(bitIndex(value));
394: boolean result = (data[longIndex] & bit) != 0;
395: if (result)
396: size--;
397: data[longIndex] &= ~bit;
398: return result;
399: }
400:
401: public int size() {
402: return size;
403: }
404:
405: // ---------------------------------------------------------------
406: // Sorted set operations
407: // ---------------------------------------------------------------
408:
409: private byte firstFrom(byte from) {
410: if (size == 0)
411: Exceptions.setNoFirst();
412: int longIndex = longIndex(from);
413: if (longIndex >= data.length)
414: Exceptions.setNoFirst();
415: long v = data[longIndex];
416: // Mask out all bits less than from
417: v &= highMask(bitIndex(from));
418:
419: try {
420: for (;;) {
421: if (v != 0L) {
422: int bitIndex = smallestBitIndexOf(v);
423: return (byte) (BITS_PER_LONG * longIndex + bitIndex);
424: }
425: v = data[++longIndex];
426: }
427: } catch (IndexOutOfBoundsException e) {
428: Exceptions.setNoFirst();
429: throw new RuntimeException();
430: }
431: }
432:
433: /**
434: * @since 1.2
435: */
436: public byte first() {
437: return firstFrom((byte) 0);
438: }
439:
440: private byte lastFrom(byte from) {
441: if (size == 0)
442: Exceptions.setNoLast();
443: int longIndex = Math.min(longIndex(from), data.length - 1);
444: long v = data[longIndex];
445: // Mask out all bits greater than from
446: v &= lowMask(bitIndex(from) + 1);
447: try {
448: for (;;) {
449: if (v != 0L) {
450: int bitIndex = largestBitIndexOf(v);
451: return (byte) (BITS_PER_LONG * longIndex + bitIndex);
452: }
453: v = data[--longIndex];
454: }
455: } catch (IndexOutOfBoundsException e) {
456: Exceptions.setNoLast();
457: throw new RuntimeException();
458: }
459: }
460:
461: /**
462: * @since 1.2
463: */
464: public byte last() {
465: if (size == 0)
466: Exceptions.setNoLast();
467: int longIndex = data.length - 1;
468: // Find last non-zero long
469: while (data[longIndex] == 0)
470: longIndex--;
471: long v = data[longIndex];
472: int bitIndex = BITS_PER_LONG - 1;
473: long bit = 1L << bitIndex;
474: while ((v & bit) == 0) {
475: bitIndex--;
476: bit >>= 1;
477: }
478: return (byte) (BITS_PER_LONG * longIndex + bitIndex);
479: }
480:
481: /**
482: * @since 1.2
483: */
484: public ByteSortedSet headSet(byte to) {
485: return new SubSet(false, (byte) 0, true, to);
486: }
487:
488: /**
489: * @since 1.2
490: */
491: public ByteSortedSet tailSet(byte from) {
492: return new SubSet(true, from, false, (byte) 0);
493: }
494:
495: /**
496: * @since 1.2
497: */
498: public ByteSortedSet subSet(byte from, byte to) {
499: return new SubSet(true, from, true, to);
500: }
501:
502: private class SubSet extends AbstractByteSet implements
503: ByteSortedSet, java.io.Serializable {
504:
505: private boolean hasLowerBound;
506: private boolean hasUpperBound;
507: private byte lowerBound;
508: private byte upperBound;
509:
510: SubSet(boolean hasLowerBound, byte lowerBound,
511: boolean hasUpperBound, byte upperBound) {
512: if (hasLowerBound) {
513: if (lowerBound < 0)
514: Exceptions.negativeArgument("lower bound", String
515: .valueOf(lowerBound));
516: if (hasUpperBound)
517: if (upperBound < lowerBound)
518: Exceptions.invalidSetBounds(String
519: .valueOf(lowerBound), String
520: .valueOf(upperBound));
521: }
522: this .hasLowerBound = hasLowerBound;
523: this .lowerBound = lowerBound;
524: this .hasUpperBound = hasUpperBound;
525: this .upperBound = upperBound;
526: }
527:
528: public boolean add(byte v) {
529: if (!inSubRange(v))
530: Exceptions.valueNotInSubRange(String.valueOf(v));
531: return ByteBitSet.this .add(v);
532: }
533:
534: public boolean remove(byte v) {
535: if (!inSubRange(v))
536: Exceptions.valueNotInSubRange(String.valueOf(v));
537: return ByteBitSet.this .remove(v);
538: }
539:
540: public boolean contains(byte v) {
541: return inSubRange(v) && ByteBitSet.this .contains(v);
542: }
543:
544: class SubSetIterator implements ByteIterator {
545: int longIndexLow;
546: int longIndexHigh;
547: long vLow;
548: long vHigh;
549: boolean isEmpty;
550:
551: int nextLongIndex;
552: int nextBitIndex;
553: int lastValue;
554:
555: SubSetIterator() {
556: lastValue = -1;
557: isEmpty = false;
558: try {
559: longIndexLow = longIndex(first());
560: } catch (NoSuchElementException e) {
561: isEmpty = true;
562: }
563: if (!isEmpty) {
564: longIndexHigh = longIndex(last());
565: if (longIndexLow == longIndexHigh) {
566: long v = data[longIndexLow];
567: // Mask out all bits less than the lower bound
568: if (hasLowerBound)
569: v &= highMask(bitIndex(lowerBound));
570: // Mask out all bits greater than or equal to the upper bound
571: if (hasUpperBound)
572: v &= lowMask(bitIndex(upperBound));
573: size = countBits(v);
574: vLow = vHigh = v;
575: } else {
576: // Mask out all bits less than the lower bound
577: vLow = data[longIndexLow];
578: if (hasLowerBound)
579: vLow &= highMask(bitIndex(lowerBound));
580:
581: // Mask out all bits greater than or equal to the upper bound
582: vHigh = data[longIndexHigh];
583: if (hasUpperBound)
584: vHigh &= lowMask(bitIndex(upperBound));
585: }
586: nextLongIndex = longIndexLow;
587: nextBitIndex = smallestBitIndexOf(vLow);
588: }
589: }
590:
591: long data(int longIndex) {
592: if (longIndex == longIndexLow)
593: return vLow;
594: if (longIndex == longIndexHigh)
595: return vHigh;
596: return data[longIndex];
597: }
598:
599: int nextLongIndex(int index) {
600: while (index <= longIndexHigh && data(index) == 0)
601: index++;
602: return index;
603: }
604:
605: int nextBitIndex(int longIndex, int bitIndex) {
606: long v = data(longIndex);
607: long bit = 1L << bitIndex;
608: while (bitIndex < BITS_PER_LONG && (v & bit) == 0) {
609: bitIndex++;
610: bit <<= 1;
611: }
612: return bitIndex;
613: }
614:
615: public boolean hasNext() {
616: return (!isEmpty) && (nextLongIndex <= longIndexHigh);
617: }
618:
619: public byte next() {
620: if (!hasNext())
621: Exceptions.endOfIterator();
622: lastValue = (byte) (nextLongIndex * BITS_PER_LONG + nextBitIndex);
623:
624: // Advance pointers
625: nextBitIndex = nextBitIndex(nextLongIndex,
626: nextBitIndex + 1);
627: if (nextBitIndex == BITS_PER_LONG) {
628: nextLongIndex = nextLongIndex(nextLongIndex + 1);
629: if (nextLongIndex < data.length)
630: nextBitIndex = nextBitIndex(nextLongIndex, 0);
631: }
632: return (byte) lastValue;
633: }
634:
635: public void remove() {
636: if (lastValue < 0)
637: Exceptions.noElementToRemove();
638: ByteBitSet.this .remove((byte) lastValue);
639: lastValue = -1;
640: }
641: }
642:
643: public ByteIterator iterator() {
644: return new SubSetIterator();
645: }
646:
647: public int size() {
648: if (ByteBitSet.this .size() == 0)
649: return 0;
650: int size;
651: int longIndexLow;
652: try {
653: longIndexLow = longIndex(first());
654: } catch (NoSuchElementException e) {
655: return 0;
656: }
657: int longIndexHigh = longIndex(last());
658: if (longIndexLow == longIndexHigh) {
659: long v = data[longIndexLow];
660: // Mask out all bits less than the lower bound
661: if (hasLowerBound)
662: v &= highMask(bitIndex(lowerBound));
663: // Mask out all bits greater than or equal to the upper bound
664: if (hasUpperBound)
665: v &= lowMask(bitIndex(upperBound));
666: size = countBits(v);
667: } else {
668: // Mask out all bits less than the lower bound
669: long vLow = data[longIndexLow];
670: if (hasLowerBound)
671: vLow &= highMask(bitIndex(lowerBound));
672:
673: // Mask out all bits greater than or equal to the upper bound
674: long vHigh = data[longIndexHigh];
675: if (hasUpperBound)
676: vHigh &= lowMask(bitIndex(upperBound));
677:
678: size = countBits(vLow) + countBits(vHigh);
679: for (int i = longIndexLow + 1; i < longIndexHigh; i++)
680: size += countBits(data[i]);
681: }
682: return size;
683: }
684:
685: public byte first() {
686: byte first = firstFrom(hasLowerBound ? lowerBound : 0);
687: if (hasUpperBound && first >= upperBound)
688: Exceptions.setNoFirst();
689: return first;
690: }
691:
692: public byte last() {
693: byte last = lastFrom(hasUpperBound ? (byte) (upperBound - 1)
694: : ByteBitSet.this .last());
695: if (hasLowerBound && last < lowerBound)
696: Exceptions.setNoLast();
697: return last;
698: }
699:
700: public ByteSortedSet headSet(byte to) {
701: if (!inSubRange(to))
702: Exceptions.invalidUpperBound(String.valueOf(to));
703: return new SubSet(hasLowerBound, lowerBound, true, to);
704: }
705:
706: public ByteSortedSet tailSet(byte from) {
707: if (!inSubRange(from))
708: Exceptions.invalidLowerBound(String.valueOf(from));
709: return new SubSet(true, from, hasUpperBound, upperBound);
710: }
711:
712: public ByteSortedSet subSet(byte from, byte to) {
713: if (!inSubRange(from))
714: Exceptions.invalidLowerBound(String.valueOf(from));
715: if (!inSubRange(to))
716: Exceptions.invalidUpperBound(String.valueOf(to));
717: return new SubSet(true, from, true, to);
718: }
719:
720: private boolean inSubRange(byte v) {
721: if (hasLowerBound && v < lowerBound)
722: return false;
723: if (hasUpperBound && v >= upperBound)
724: return false;
725: return true;
726: }
727:
728: }
729:
730: }
|