0001: /*
0002: * Primitive Collections for Java.
0003: * Copyright (C) 2002 Søren Bak
0004: *
0005: * This library is free software; you can redistribute it and/or
0006: * modify it under the terms of the GNU Lesser General Public
0007: * License as published by the Free Software Foundation; either
0008: * version 2.1 of the License, or (at your option) any later version.
0009: *
0010: * This library is distributed in the hope that it will be useful,
0011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0013: * Lesser General Public License for more details.
0014: *
0015: * You should have received a copy of the GNU Lesser General Public
0016: * License along with this library; if not, write to the Free Software
0017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0018: */
0019: package bak.pcj.set;
0020:
0021: import bak.pcj.ByteIterator;
0022: import bak.pcj.ByteCollection;
0023: import bak.pcj.util.Exceptions;
0024:
0025: import java.util.ArrayList;
0026: import java.util.NoSuchElementException;
0027: import java.io.Serializable;
0028:
0029: /**
0030: * This class represents range based sets of byte values.
0031: * The implementation is optimized for cases where most set elements
0032: * fall into ranges of consecutive byte values.
0033: *
0034: * <p>Implementation of
0035: * ByteSortedSet is supported from PCJ 1.2. Prior to 1.2, only ByteSet
0036: * was implemented.
0037: *
0038: * @see ByteRange
0039: *
0040: * @author Søren Bak
0041: * @version 1.3 20-08-2003 22:24
0042: * @since 1.0
0043: */
0044: public class ByteRangeSet extends AbstractByteSet implements
0045: ByteSortedSet, Cloneable, Serializable {
0046:
0047: /**
0048: * The ranges of this set. Must always be sorted and normalized (non-adjacent and non-overlapping).
0049: * @serial
0050: */
0051: private ArrayList ranges;
0052:
0053: /**
0054: * The size of this set.
0055: * @serial
0056: */
0057: private int size;
0058:
0059: /**
0060: * Creates a new empty range set.
0061: */
0062: public ByteRangeSet() {
0063: ranges = new ArrayList();
0064: size = 0;
0065: }
0066:
0067: /**
0068: * Creates a new empty range set containing specified values.
0069: *
0070: * @param a
0071: * the values that the new set should contain.
0072: *
0073: * @throws NullPointerException
0074: * if <tt>a</tt> is <tt>null</tt>.
0075: */
0076: public ByteRangeSet(byte[] a) {
0077: this ();
0078: addAll(a);
0079: }
0080:
0081: /**
0082: * Creates a new range set with the same elements as a specified
0083: * collection.
0084: *
0085: * @param c
0086: * the collection whose elements to add to the new
0087: * set.
0088: *
0089: * @throws NullPointerException
0090: * if <tt>c</tt> is <tt>null</tt>.
0091: */
0092: public ByteRangeSet(ByteCollection c) {
0093: this ();
0094: addAll(c);
0095: }
0096:
0097: // ---------------------------------------------------------------
0098: // Range management
0099: // ---------------------------------------------------------------
0100:
0101: /**
0102: * Returns a specified range.
0103: *
0104: * @param index
0105: * the index of the range to return.
0106: *
0107: * @throws IndexOutOfBoundsException
0108: * if <tt>index/tt> does not denote a valid range
0109: * number.
0110: */
0111: private ByteRange range(int index) {
0112: return (ByteRange) ranges.get(index);
0113: }
0114:
0115: /**
0116: * Returns the range of a specified value.
0117: *
0118: * @param v
0119: * the value to search for.
0120: *
0121: * @return the range containing the specified value; returns
0122: * <tt>null</tt> if no range contains the specified
0123: * value.
0124: */
0125: private ByteRange getRangeOf(byte v) {
0126: int index = getRangeIndexOf(v);
0127: return index >= 0 ? range(index) : null;
0128: }
0129:
0130: /**
0131: * Returns the range index of a specified value.
0132: *
0133: * @param v
0134: * the value to search for.
0135: *
0136: * @return the index of the range containing the specified
0137: * value; returns <tt>(-(<i>insertion point</i>) - 1)</tt>
0138: * if no range contains the specified value.
0139: */
0140: private int getRangeIndexOf(byte v) {
0141: if (size == 0)
0142: return -1;
0143: // Binary search
0144: ByteRange r;
0145: int lo = 0;
0146: int hi = ranges.size() - 1;
0147: int mid;
0148: while (lo <= hi) {
0149: mid = (lo + hi) / 2;
0150: r = (ByteRange) ranges.get(mid);
0151: if (r.contains(v))
0152: return mid;
0153: if (v < r.first()) {
0154: hi = mid - 1;
0155: } else { // v > r.last()
0156: lo = mid + 1;
0157: }
0158: }
0159: return -(lo + 1);
0160: }
0161:
0162: /**
0163: * Inserts a range at the sorted position in the ranges.
0164: *
0165: * @param range
0166: * the range to insert.
0167: *
0168: * @return the insertion index; returns <tt>-1</tt> if an
0169: * equal range existed in the ranges.
0170: */
0171: private int insertRange(ByteRange range) {
0172: // Binary search
0173: ByteRange r;
0174: int lo = 0;
0175: int hi = ranges.size() - 1;
0176: int mid;
0177: while (lo <= hi) {
0178: mid = (lo + hi) / 2;
0179: r = range(mid);
0180: int compare = range.compareTo(r);
0181: if (compare == 0)
0182: return -1;
0183: if (compare < 0) {
0184: hi = mid - 1;
0185: } else { // compare > 0
0186: lo = mid + 1;
0187: }
0188: }
0189: ranges.add(lo, range);
0190: return lo;
0191: }
0192:
0193: /**
0194: * Normalizes the ranges after the insertion of a new range and
0195: * recalculates the size of this set. The range list must be
0196: * sorted when this method is invoked.
0197: *
0198: * @param index
0199: * the index at which to start the normalization.
0200: * Usually the index before a new range was inserted.
0201: */
0202: private void normalize(int index) {
0203: while (index < ranges.size() - 1) {
0204: ByteRange r1 = range(index);
0205: ByteRange r2 = range(index + 1);
0206: ByteRange r3 = r1.tryMergeWith(r2);
0207: if (r3 == null)
0208: break;
0209: ranges.set(index, r3);
0210: ranges.remove(index + 1);
0211: size -= r1.intersectionLength(r2);
0212: }
0213: }
0214:
0215: /**
0216: * Normalizes all ranges and recalculates the size of this set.
0217: * The method is usually called when the whole range list has
0218: * changed. The range list must be sorted when this method is
0219: * invoked.
0220: */
0221: private void normalize() {
0222: int index = 0;
0223: size = 0;
0224: ByteRange r1, r2, r3;
0225: while (index < ranges.size() - 1) {
0226: r1 = range(index);
0227: r2 = range(index + 1);
0228: r3 = r1.tryMergeWith(r2);
0229: if (r3 != null) {
0230: ranges.set(index, r3);
0231: ranges.remove(index + 1);
0232: } else {
0233: size += r1.length();
0234: index++;
0235: }
0236: }
0237: r3 = range(ranges.size() - 1);
0238: size += r3.length();
0239: }
0240:
0241: // ---------------------------------------------------------------
0242: // Operations not supported by abstract implementation
0243: // ---------------------------------------------------------------
0244:
0245: public boolean add(byte v) {
0246: int index = getRangeIndexOf(v);
0247: if (index >= 0)
0248: return false;
0249: int insertionIndex = -index - 1;
0250: ranges.add(insertionIndex, new ByteRange(v, v));
0251: if (insertionIndex > 0)
0252: insertionIndex--;
0253: size++;
0254: normalize(insertionIndex);
0255: return true;
0256: }
0257:
0258: public ByteIterator iterator() {
0259: return new ByteIterator() {
0260: int nextIndex = 0;
0261: int lastIndex = -1;
0262: int currRange = 0;
0263: int currOffset = 0;
0264: byte lastValue;
0265:
0266: public boolean hasNext() {
0267: return nextIndex < size;
0268: }
0269:
0270: public byte next() {
0271: if (nextIndex >= size)
0272: Exceptions.endOfIterator();
0273: lastIndex = nextIndex;
0274: lastValue = curr();
0275: nextIndex++;
0276: if (nextIndex < size) {
0277: if (currOffset == range(currRange).length() - 1) {
0278: currRange++;
0279: currOffset = 0;
0280: } else {
0281: currOffset++;
0282: }
0283: }
0284: return lastValue;
0285: }
0286:
0287: public void remove() {
0288: if (lastIndex == -1)
0289: Exceptions.noElementToRemove();
0290: ByteRangeSet.this .remove(lastValue);
0291: nextIndex--;
0292: if (nextIndex < size)
0293: recalc();
0294: lastIndex = -1;
0295: }
0296:
0297: private byte curr() {
0298: return (byte) (range(currRange).first() + currOffset);
0299: }
0300:
0301: private void recalc() {
0302: currRange = 0;
0303: currOffset = nextIndex;
0304: for (;;) {
0305: int rs = range(currRange).length();
0306: if (currOffset < rs)
0307: break;
0308: currOffset -= rs;
0309: currRange++;
0310: }
0311: }
0312:
0313: };
0314: }
0315:
0316: /**
0317: * @since 1.2
0318: */
0319: public byte first() {
0320: if (size == 0)
0321: Exceptions.setNoFirst();
0322: return range(0).first();
0323: }
0324:
0325: private byte firstFrom(byte v) {
0326: int index = getRangeIndexOf(v);
0327: if (index >= 0)
0328: return v;
0329: // Get first range after calculated insertion point.
0330: // index is now (-(insertion point)-1), so the insertion point
0331: // is -index-1
0332: index = -index - 1;
0333: if (index >= ranges.size())
0334: Exceptions.setNoFirst();
0335: return range(index).first();
0336: }
0337:
0338: /**
0339: * @since 1.2
0340: */
0341: public byte last() {
0342: if (size == 0)
0343: Exceptions.setNoLast();
0344: return range(ranges.size() - 1).last();
0345: }
0346:
0347: private byte lastFrom(byte v) {
0348: int index = getRangeIndexOf(v);
0349: if (index >= 0)
0350: return v;
0351: // Get first range before calculated insertion point.
0352: // index is now (-(insertion point)-1), so the insertion point
0353: // is -index-1
0354: index = -index - 1;
0355: index--;
0356: if (index < 0 || index >= ranges.size())
0357: Exceptions.setNoLast();
0358: return range(index).last();
0359: }
0360:
0361: /**
0362: * @since 1.2
0363: */
0364: public ByteSortedSet headSet(byte to) {
0365: return new SubSet(false, (byte) 0, true, to);
0366: }
0367:
0368: /**
0369: * @since 1.2
0370: */
0371: public ByteSortedSet tailSet(byte from) {
0372: return new SubSet(true, from, false, (byte) 0);
0373: }
0374:
0375: /**
0376: * @since 1.2
0377: */
0378: public ByteSortedSet subSet(byte from, byte to) {
0379: return new SubSet(true, from, true, to);
0380: }
0381:
0382: private class SubSet extends AbstractByteSet implements
0383: ByteSortedSet, java.io.Serializable {
0384:
0385: private boolean hasLowerBound;
0386: private boolean hasUpperBound;
0387: private byte lowerBound;
0388: private byte upperBound;
0389:
0390: SubSet(boolean hasLowerBound, byte lowerBound,
0391: boolean hasUpperBound, byte upperBound) {
0392: if (hasLowerBound) {
0393: if (lowerBound < 0)
0394: Exceptions.negativeArgument("lower bound", String
0395: .valueOf(lowerBound));
0396: if (hasUpperBound)
0397: if (upperBound < lowerBound)
0398: Exceptions.invalidSetBounds(String
0399: .valueOf(lowerBound), String
0400: .valueOf(upperBound));
0401: }
0402: this .hasLowerBound = hasLowerBound;
0403: this .lowerBound = lowerBound;
0404: this .hasUpperBound = hasUpperBound;
0405: this .upperBound = upperBound;
0406: }
0407:
0408: public boolean add(byte v) {
0409: if (!inSubRange(v))
0410: Exceptions.valueNotInSubRange(String.valueOf(v));
0411: return ByteRangeSet.this .add(v);
0412: }
0413:
0414: public boolean remove(byte v) {
0415: if (!inSubRange(v))
0416: Exceptions.valueNotInSubRange(String.valueOf(v));
0417: return ByteRangeSet.this .remove(v);
0418: }
0419:
0420: public boolean contains(byte v) {
0421: return inSubRange(v) && ByteRangeSet.this .contains(v);
0422: }
0423:
0424: class EmptySubSetIterator implements ByteIterator {
0425: public boolean hasNext() {
0426: return false;
0427: }
0428:
0429: public byte next() {
0430: Exceptions.endOfIterator();
0431: throw new RuntimeException();
0432: }
0433:
0434: public void remove() {
0435: Exceptions.noElementToRemove();
0436: }
0437: }
0438:
0439: class SimpleSubSetIterator implements ByteIterator {
0440: int nextIndex;
0441: int size;
0442: int lastIndex;
0443: byte lastValue;
0444: byte from;
0445: byte to;
0446:
0447: SimpleSubSetIterator(byte from, byte to) {
0448: size = (int) (to - from + 1);
0449: nextIndex = 0;
0450: lastIndex = -1;
0451: this .from = from;
0452: this .to = to;
0453: }
0454:
0455: public boolean hasNext() {
0456: return nextIndex < size;
0457: }
0458:
0459: public byte next() {
0460: if (!hasNext())
0461: Exceptions.endOfIterator();
0462: lastValue = (byte) (from + nextIndex);
0463: lastIndex = nextIndex;
0464: nextIndex++;
0465: return lastValue;
0466: }
0467:
0468: public void remove() {
0469: if (lastIndex == -1)
0470: Exceptions.noElementToRemove();
0471: ByteRangeSet.this .remove(lastValue);
0472: lastIndex = -1;
0473: }
0474:
0475: }
0476:
0477: class NonEmptySubSetIterator implements ByteIterator {
0478: byte first;
0479: byte last;
0480: int rangeIndexLow;
0481: int rangeIndexHigh;
0482: ByteRange rangeLow;
0483: ByteRange rangeHigh;
0484: byte previousValue;
0485: ByteRange currRange;
0486: int currRangeIndex;
0487: int currOffset;
0488: boolean valueAvailable;
0489: int nextIndex;
0490:
0491: NonEmptySubSetIterator(byte first, byte last,
0492: int rangeIndexLow, int rangeIndexHigh) {
0493: if (rangeIndexLow == rangeIndexHigh)
0494: throw new RuntimeException("Internal error");
0495: this .first = first;
0496: this .last = last;
0497: this .rangeIndexLow = rangeIndexLow;
0498: this .rangeIndexHigh = rangeIndexHigh;
0499: rangeLow = new ByteRange(first, range(rangeIndexLow)
0500: .last());
0501: rangeHigh = new ByteRange(
0502: range(rangeIndexHigh).first(), last);
0503: currRangeIndex = rangeIndexLow;
0504: currRange = rangeLow;
0505: currOffset = 0;
0506: previousValue = first;
0507: valueAvailable = false;
0508: nextIndex = 0;
0509: }
0510:
0511: private ByteRange getRange(int rangeIndex) {
0512: if (rangeIndex == rangeIndexLow)
0513: return rangeLow;
0514: if (rangeIndex == rangeIndexHigh)
0515: return rangeHigh;
0516: return range(rangeIndex);
0517: }
0518:
0519: private void recalc() {
0520: first = first();
0521: last = last();
0522:
0523: rangeIndexLow = getRangeIndexOf(first);
0524: rangeIndexHigh = getRangeIndexOf(last);
0525: if (rangeIndexLow == rangeIndexHigh)
0526: rangeLow = rangeHigh = new ByteRange(first, last);
0527: else {
0528: rangeLow = new ByteRange(first,
0529: range(rangeIndexLow).last());
0530: rangeHigh = new ByteRange(range(rangeIndexHigh)
0531: .first(), last);
0532: }
0533: currOffset = nextIndex;
0534: currRangeIndex = rangeIndexLow;
0535: currRange = rangeLow;
0536: for (;;) {
0537: int rs = currRange.length();
0538: if (currOffset < rs)
0539: break;
0540: currOffset -= rs;
0541: currRange = getRange(++currRangeIndex);
0542: }
0543: }
0544:
0545: public boolean hasNext() {
0546: return previousValue < last;
0547: }
0548:
0549: public byte next() {
0550: if (!hasNext())
0551: Exceptions.endOfIterator();
0552: previousValue = (byte) (currRange.first() + currOffset++);
0553: if (currOffset == currRange.length()
0554: && previousValue < last) {
0555: currOffset = 0;
0556: currRange = getRange(++currRangeIndex);
0557: }
0558: nextIndex++;
0559: valueAvailable = true;
0560: return previousValue;
0561: }
0562:
0563: public void remove() {
0564: if (!valueAvailable)
0565: Exceptions.noElementToRemove();
0566: ByteRangeSet.this .remove(previousValue);
0567: nextIndex--;
0568: recalc();
0569: valueAvailable = false;
0570: }
0571: }
0572:
0573: public ByteIterator iterator() {
0574: byte first;
0575: byte last;
0576: int rangeIndexLow;
0577: int rangeIndexHigh;
0578:
0579: try {
0580: first = first();
0581: } catch (NoSuchElementException e) {
0582: return new EmptySubSetIterator();
0583: }
0584: last = last();
0585: rangeIndexLow = getRangeIndexOf(first);
0586: rangeIndexHigh = getRangeIndexOf(last);
0587: if (rangeIndexLow == rangeIndexHigh)
0588: return new SimpleSubSetIterator(first, last);
0589: return new NonEmptySubSetIterator(first, last,
0590: rangeIndexLow, rangeIndexHigh);
0591: }
0592:
0593: public int size() {
0594: if (ByteRangeSet.this .size() == 0)
0595: return 0;
0596: int size;
0597: byte first;
0598: int rangeIndexLow;
0599: try {
0600: first = first();
0601: rangeIndexLow = getRangeIndexOf(first);
0602: } catch (NoSuchElementException e) {
0603: return 0;
0604: }
0605: byte last = last();
0606: int rangeIndexHigh = getRangeIndexOf(last);
0607: if (rangeIndexLow == rangeIndexHigh) {
0608: size = (int) (last - first + 1);
0609: } else {
0610: ByteRange rangeLow = range(rangeIndexLow);
0611: ByteRange rangeHigh = range(rangeIndexHigh);
0612: int sizeLow = (int) (rangeLow.last() - first + 1);
0613: int sizeHigh = (int) (last - rangeHigh.first() + 1);
0614:
0615: size = sizeLow + sizeHigh;
0616: for (int i = rangeIndexLow + 1; i < rangeIndexHigh; i++)
0617: size += range(i).length();
0618: }
0619: return size;
0620: }
0621:
0622: public byte first() {
0623: byte first = firstFrom(hasLowerBound ? lowerBound : 0);
0624: if (hasUpperBound && first >= upperBound)
0625: Exceptions.setNoFirst();
0626: return first;
0627: }
0628:
0629: public byte last() {
0630: byte last = lastFrom(hasUpperBound ? (byte) (upperBound - 1)
0631: : ByteRangeSet.this .last());
0632: if (hasLowerBound && last < lowerBound)
0633: Exceptions.setNoLast();
0634: return last;
0635: }
0636:
0637: public ByteSortedSet headSet(byte to) {
0638: if (!inSubRange(to))
0639: Exceptions.invalidUpperBound(String.valueOf(to));
0640: return new SubSet(hasLowerBound, lowerBound, true, to);
0641: }
0642:
0643: public ByteSortedSet tailSet(byte from) {
0644: if (!inSubRange(from))
0645: Exceptions.invalidLowerBound(String.valueOf(from));
0646: return new SubSet(true, from, hasUpperBound, upperBound);
0647: }
0648:
0649: public ByteSortedSet subSet(byte from, byte to) {
0650: if (!inSubRange(from))
0651: Exceptions.invalidLowerBound(String.valueOf(from));
0652: if (!inSubRange(to))
0653: Exceptions.invalidUpperBound(String.valueOf(to));
0654: return new SubSet(true, from, true, to);
0655: }
0656:
0657: private boolean inSubRange(byte v) {
0658: if (hasLowerBound && v < lowerBound)
0659: return false;
0660: if (hasUpperBound && v >= upperBound)
0661: return false;
0662: return true;
0663: }
0664:
0665: }
0666:
0667: public String toString() {
0668: StringBuffer s = new StringBuffer();
0669: s.append('[');
0670: for (int i = 0, rsize = ranges.size(); i < rsize; i++) {
0671: if (i > 0)
0672: s.append(',');
0673: s.append(range(i));
0674: }
0675: s.append(']');
0676: return s.toString();
0677: }
0678:
0679: public void trimToSize() {
0680: //ranges.trimToSize();
0681: }
0682:
0683: /**
0684: * Returns a clone of this range set.
0685: *
0686: * @return a clone of this range set.
0687: *
0688: * @since 1.1
0689: */
0690: public Object clone() {
0691: try {
0692: ByteRangeSet c = (ByteRangeSet) super .clone();
0693: c.ranges = (ArrayList) ranges.clone();
0694: return c;
0695: } catch (CloneNotSupportedException e) {
0696: Exceptions.cloning();
0697: throw new RuntimeException();
0698: }
0699: }
0700:
0701: // ---------------------------------------------------------------
0702: // Operations overwritten for efficiency
0703: // ---------------------------------------------------------------
0704:
0705: public void clear() {
0706: ranges.clear();
0707: size = 0;
0708: }
0709:
0710: public boolean contains(byte v) {
0711: return getRangeIndexOf(v) >= 0;
0712: }
0713:
0714: public int hashCode() {
0715: int h = 0;
0716: for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) {
0717: ByteRange r = range(i);
0718: for (byte c = r.first(), last = r.last(); c <= last; c++)
0719: h += c;
0720: }
0721: return h;
0722: }
0723:
0724: public boolean isEmpty() {
0725: return size == 0;
0726: }
0727:
0728: public int size() {
0729: return size;
0730: }
0731:
0732: public boolean remove(byte v) {
0733: int index = getRangeIndexOf(v);
0734: if (index < 0)
0735: return false;
0736: // Treat end points special since we can avoid splitting a range
0737: ByteRange r = range(index);
0738: if (v == r.first()) {
0739: if (r.length() == 1)
0740: ranges.remove(index);
0741: else
0742: ranges.set(index, new ByteRange((byte) (r.first() + 1),
0743: r.last()));
0744: } else if (v == r.last()) {
0745: // r.length() > 1
0746: ranges.set(index, new ByteRange(r.first(),
0747: (byte) (r.last() - 1)));
0748: } else {
0749: // Split the range
0750: ByteRange r1 = new ByteRange(r.first(), (byte) (v - 1));
0751: ByteRange r2 = new ByteRange((byte) (v + 1), r.last());
0752: ranges.set(index, r1);
0753: ranges.add(index + 1, r2);
0754: }
0755: size--;
0756: return true;
0757: }
0758:
0759: public byte[] toArray(byte[] a) {
0760: if (a == null || a.length < size)
0761: a = new byte[size];
0762: for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) {
0763: ByteRange r = range(i);
0764: for (byte c = r.first(), last = r.last(); c <= last; c++)
0765: a[index++] = c;
0766: }
0767: return a;
0768: }
0769:
0770: // ---------------------------------------------------------------
0771: // Extra operations
0772: // ---------------------------------------------------------------
0773:
0774: /**
0775: * Indicates whether all elements of a specified
0776: * range is contained in this set.
0777: *
0778: * @param range
0779: * the range whose elements to test for
0780: * containment.
0781: *
0782: * @return <tt>true</tt> if all the elements of <tt>range</tt>
0783: * are contained in this collection; returns
0784: * <tt>false</tt> otherwise.
0785: *
0786: * @throws NullPointerException
0787: * if <tt>range</tt> is <tt>null</tt>.
0788: *
0789: * @see #containsAll(ByteCollection)
0790: */
0791: public boolean containsAll(ByteRange range) {
0792: /*
0793: In order for the set to contain the whole range
0794: the two range ends must be represented by the same
0795: range in the range list.
0796: */
0797: ByteRange r = getRangeOf(range.first());
0798: return r != null ? r.contains(range.last()) : false;
0799: }
0800:
0801: /**
0802: * Adds all the elements of a specified range set to
0803: * this set.
0804: *
0805: * @param c
0806: * the set whose elements to add to this
0807: * set.
0808: *
0809: * @return <tt>true</tt> if this set was modified
0810: * as a result of adding the elements of <tt>c</tt>;
0811: * returns <tt>false</tt> otherwise.
0812: *
0813: * @throws NullPointerException
0814: * if <tt>c</tt> is <tt>null</tt>.
0815: *
0816: * @see #add(byte)
0817: * @see #addAll(ByteRange)
0818: * @see #addAll(ByteCollection)
0819: * @see #addAll(byte, byte)
0820: * @see #addAll(byte[])
0821: */
0822: public boolean addAll(ByteRangeSet c) {
0823: int oldSize = size;
0824: for (int i = 0, rsize = c.ranges.size(); i < rsize; i++)
0825: addAll(c.range(i));
0826: return size != oldSize;
0827: }
0828:
0829: /**
0830: * Adds a specified range to this set.
0831: *
0832: * @param range
0833: * the range to add to this set.
0834: *
0835: * @return <tt>true</tt> if this set was modified
0836: * as a result of adding the elements of
0837: * <tt>range</tt>; returns <tt>false</tt> otherwise.
0838: *
0839: * @throws NullPointerException
0840: * if <tt>range</tt> is <tt>null</tt>.
0841: *
0842: * @see #add(byte)
0843: * @see #addAll(ByteRangeSet)
0844: * @see #addAll(ByteCollection)
0845: * @see #addAll(byte, byte)
0846: * @see #addAll(byte[])
0847: */
0848: public boolean addAll(ByteRange range) {
0849: int oldSize = size;
0850: int index = insertRange(range);
0851: if (index != -1) {
0852: int nindex = index;
0853: if (nindex > 0)
0854: nindex--;
0855: size += range.length();
0856: normalize(nindex);
0857: }
0858: return size != oldSize;
0859: }
0860:
0861: /**
0862: * Adds a specified range to this set.
0863: *
0864: * @param first
0865: * the first value of the range to add to this set.
0866: *
0867: * @param last
0868: * the last value of the range to add to this set.
0869: *
0870: * @return <tt>true</tt> if this set was modified
0871: * as a result of adding the values <tt>first</tt>
0872: * to <tt>last</tt>; returns <tt>false</tt>
0873: * otherwise.
0874: *
0875: * @throws IllegalArgumentException
0876: * if <tt>first > last</tt>.
0877: */
0878: public boolean addAll(byte first, byte last) {
0879: return addAll(new ByteRange(first, last));
0880: }
0881:
0882: /**
0883: * Adds an array of byte values to this set.
0884: *
0885: * @param a
0886: * the array of byte values to add to this set.
0887: *
0888: * @throws NullPointerException
0889: * if <tt>a</tt> is <tt>null</tt>.
0890: *
0891: * @see #add(byte)
0892: * @see #addAll(ByteRange)
0893: * @see #addAll(ByteRangeSet)
0894: * @see #addAll(ByteCollection)
0895: * @see #addAll(byte, byte)
0896: */
0897: public boolean addAll(byte[] a) {
0898: if (a.length == 0)
0899: return false;
0900:
0901: // Sort a
0902: /*
0903: We can decide if the array is sorted in at most n steps
0904: (n being the length of chars).
0905: If it is not sorted, it is probably much less than n steps,
0906: and if it is sorted, we can skip the sorting operation
0907: and cloning of chars (thus effectively having sorted in
0908: linear time).
0909: */
0910: int oldSize = size;
0911: byte[] sa;
0912: if (!isSorted(a)) {
0913: sa = (byte[]) a.clone();
0914: java.util.Arrays.sort(sa);
0915: } else {
0916: sa = a;
0917: }
0918:
0919: // Add ranges of a to range list
0920: int index = 0;
0921: byte c0, c1;
0922: while (index < sa.length) {
0923: c0 = sa[index];
0924: index = range(sa, index);
0925: c1 = sa[index];
0926: ranges.add(new ByteRange(c0, c1));
0927: index++;
0928: }
0929:
0930: // Sort and normalize range list
0931: /*
0932: Is it better to sort and normalize once instead
0933: of inserting sorted and performing normalization at each step?
0934: */
0935: java.util.Collections.sort(ranges);
0936: normalize();
0937: return size != oldSize;
0938: }
0939:
0940: /**
0941: * Finds a range in an ordered array which may
0942: * contain duplicates.
0943: *
0944: * @param a
0945: * the array of values to search.
0946: *
0947: * @param index
0948: * the index from which to start the search.
0949: *
0950: * @return the index of the last value in the found
0951: * range.
0952: */
0953: private int range(byte[] a, int index) {
0954: byte c0 = a[index++];
0955: // Skip duplicates
0956: while (index < a.length && a[index] == c0)
0957: index++;
0958: // While in sequence
0959: while (index < a.length && a[index] == (byte) (c0 + 1)) {
0960: c0 = a[index++];
0961: // Skip duplicates
0962: while (index < a.length && a[index] == c0)
0963: index++;
0964: }
0965: return index - 1;
0966: }
0967:
0968: /**
0969: * Indicates whether the specified array is sorted in
0970: * ascending order.
0971: *
0972: * @param a
0973: * the array to examine.
0974: *
0975: * @return <tt>true</tt> if <tt>s</tt> is sorted; returns
0976: * <tt>false</tt> otherwise.
0977: *
0978: * @throws NullPointerException
0979: * if <tt>a</tt> is <tt>null</tt>.
0980: */
0981: private boolean isSorted(byte[] a) {
0982: for (int i = 1; i < a.length; i++)
0983: if (a[i] < a[i - 1])
0984: return false;
0985: return true;
0986: }
0987:
0988: /**
0989: * Returns the ranges of this set. None of the ranges returned
0990: * will overlap or be adjacent.
0991: *
0992: * @return the ranges of this set. The returned array is
0993: * a fresh copy that can be modified without
0994: * modifying this set.
0995: */
0996: public ByteRange[] ranges() {
0997: ByteRange[] a = new ByteRange[ranges.size()];
0998: ranges.toArray(a);
0999: return a;
1000: }
1001:
1002: }
|