KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * Primitive Collections for Java.
3  * Copyright (C) 2002 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.ByteIterator;
22 import bak.pcj.ByteCollection;
23 import bak.pcj.util.Exceptions;
24
25 import java.util.ArrayList JavaDoc;
26 import java.util.NoSuchElementException JavaDoc;
27 import java.io.Serializable JavaDoc;
28
29 /**
30  * This class represents range based sets of byte values.
31  * The implementation is optimized for cases where most set elements
32  * fall into ranges of consecutive byte values.
33  *
34  * <p>Implementation of
35  * ByteSortedSet is supported from PCJ 1.2. Prior to 1.2, only ByteSet
36  * was implemented.
37  *
38  * @see ByteRange
39  *
40  * @author S&oslash;ren Bak
41  * @version 1.3 20-08-2003 22:24
42  * @since 1.0
43  */

44 public class ByteRangeSet extends AbstractByteSet implements ByteSortedSet, Cloneable JavaDoc, Serializable JavaDoc {
45
46     /**
47      * The ranges of this set. Must always be sorted and normalized (non-adjacent and non-overlapping).
48      * @serial
49      */

50     private ArrayList JavaDoc ranges;
51
52     /**
53      * The size of this set.
54      * @serial
55      */

56     private int size;
57
58     /**
59      * Creates a new empty range set.
60      */

61     public ByteRangeSet() {
62         ranges = new ArrayList JavaDoc();
63         size = 0;
64     }
65
66     /**
67      * Creates a new empty range set containing specified values.
68      *
69      * @param a
70      * the values that the new set should contain.
71      *
72      * @throws NullPointerException
73      * if <tt>a</tt> is <tt>null</tt>.
74      */

75     public ByteRangeSet(byte[] a) {
76         this();
77         addAll(a);
78     }
79
80     /**
81      * Creates a new range set with the same elements as a specified
82      * collection.
83      *
84      * @param c
85      * the collection whose elements to add to the new
86      * set.
87      *
88      * @throws NullPointerException
89      * if <tt>c</tt> is <tt>null</tt>.
90      */

91     public ByteRangeSet(ByteCollection c) {
92         this();
93         addAll(c);
94     }
95
96     // ---------------------------------------------------------------
97
// Range management
98
// ---------------------------------------------------------------
99

100     /**
101      * Returns a specified range.
102      *
103      * @param index
104      * the index of the range to return.
105      *
106      * @throws IndexOutOfBoundsException
107      * if <tt>index/tt> does not denote a valid range
108      * number.
109      */

110     private ByteRange range(int index) {
111         return (ByteRange)ranges.get(index);
112     }
113
114     /**
115      * Returns the range of a specified value.
116      *
117      * @param v
118      * the value to search for.
119      *
120      * @return the range containing the specified value; returns
121      * <tt>null</tt> if no range contains the specified
122      * value.
123      */

124     private ByteRange getRangeOf(byte v) {
125         int index = getRangeIndexOf(v);
126         return index >= 0 ? range(index) : null;
127     }
128
129     /**
130      * Returns the range index of a specified value.
131      *
132      * @param v
133      * the value to search for.
134      *
135      * @return the index of the range containing the specified
136      * value; returns <tt>(-(<i>insertion point</i>) - 1)</tt>
137      * if no range contains the specified value.
138      */

139     private int getRangeIndexOf(byte v) {
140         if (size == 0)
141             return -1;
142         // Binary search
143
ByteRange r;
144         int lo = 0;
145         int hi = ranges.size()-1;
146         int mid;
147         while (lo <= hi) {
148             mid = (lo+hi)/2;
149             r = (ByteRange)ranges.get(mid);
150             if (r.contains(v))
151                 return mid;
152             if (v < r.first()) {
153                 hi = mid-1;
154             } else { // v > r.last()
155
lo = mid+1;
156             }
157         }
158         return -(lo+1);
159     }
160
161     /**
162      * Inserts a range at the sorted position in the ranges.
163      *
164      * @param range
165      * the range to insert.
166      *
167      * @return the insertion index; returns <tt>-1</tt> if an
168      * equal range existed in the ranges.
169      */

170     private int insertRange(ByteRange range) {
171         // Binary search
172
ByteRange r;
173         int lo = 0;
174         int hi = ranges.size()-1;
175         int mid;
176         while (lo <= hi) {
177             mid = (lo+hi)/2;
178             r = range(mid);
179             int compare = range.compareTo(r);
180             if (compare == 0)
181                 return -1;
182             if (compare < 0) {
183                 hi = mid-1;
184             } else { // compare > 0
185
lo = mid+1;
186             }
187         }
188         ranges.add(lo, range);
189         return lo;
190     }
191
192     /**
193      * Normalizes the ranges after the insertion of a new range and
194      * recalculates the size of this set. The range list must be
195      * sorted when this method is invoked.
196      *
197      * @param index
198      * the index at which to start the normalization.
199      * Usually the index before a new range was inserted.
200      */

201     private void normalize(int index) {
202         while (index < ranges.size()-1) {
203             ByteRange r1 = range(index);
204             ByteRange r2 = range(index+1);
205             ByteRange r3 = r1.tryMergeWith(r2);
206             if (r3 == null)
207                 break;
208             ranges.set(index, r3);
209             ranges.remove(index+1);
210             size -= r1.intersectionLength(r2);
211         }
212     }
213
214
215     /**
216      * Normalizes all ranges and recalculates the size of this set.
217      * The method is usually called when the whole range list has
218      * changed. The range list must be sorted when this method is
219      * invoked.
220      */

221     private void normalize() {
222         int index = 0;
223         size = 0;
224         ByteRange r1, r2, r3;
225         while (index < ranges.size()-1) {
226             r1 = range(index);
227             r2 = range(index+1);
228             r3 = r1.tryMergeWith(r2);
229             if (r3 != null) {
230                 ranges.set(index, r3);
231                 ranges.remove(index+1);
232             } else {
233                 size += r1.length();
234                 index++;
235             }
236         }
237         r3 = range(ranges.size()-1);
238         size += r3.length();
239     }
240
241     // ---------------------------------------------------------------
242
// Operations not supported by abstract implementation
243
// ---------------------------------------------------------------
244

245     public boolean add(byte v) {
246         int index = getRangeIndexOf(v);
247         if (index >= 0)
248             return false;
249         int insertionIndex = -index-1;
250         ranges.add(insertionIndex, new ByteRange(v, v));
251         if (insertionIndex > 0)
252             insertionIndex--;
253         size++;
254         normalize(insertionIndex);
255         return true;
256     }
257
258     public ByteIterator iterator() {
259         return new ByteIterator() {
260             int nextIndex = 0;
261             int lastIndex = -1;
262             int currRange = 0;
263             int currOffset = 0;
264             byte lastValue;
265
266             public boolean hasNext() {
267                 return nextIndex < size;
268             }
269
270             public byte next() {
271                 if (nextIndex >= size)
272                     Exceptions.endOfIterator();
273                 lastIndex = nextIndex;
274                 lastValue = curr();
275                 nextIndex++;
276                 if (nextIndex < size) {
277                     if (currOffset == range(currRange).length()-1) {
278                         currRange++;
279                         currOffset = 0;
280                     } else {
281                         currOffset++;
282                     }
283                 }
284                 return lastValue;
285             }
286
287             public void remove() {
288                 if (lastIndex == -1)
289                     Exceptions.noElementToRemove();
290                 ByteRangeSet.this.remove(lastValue);
291                 nextIndex--;
292                 if (nextIndex < size)
293                     recalc();
294                 lastIndex = -1;
295             }
296
297             private byte curr() {
298                 return (byte)(range(currRange).first() + currOffset);
299             }
300
301             private void recalc() {
302                 currRange = 0;
303                 currOffset = nextIndex;
304                 for (;;) {
305                     int rs = range(currRange).length();
306                     if (currOffset < rs)
307                         break;
308                     currOffset -= rs;
309                     currRange++;
310                 }
311             }
312
313         };
314     }
315
316     /**
317      * @since 1.2
318      */

319     public byte first() {
320         if (size == 0)
321             Exceptions.setNoFirst();
322         return range(0).first();
323     }
324
325     private byte firstFrom(byte v) {
326         int index = getRangeIndexOf(v);
327         if (index >= 0)
328             return v;
329         // Get first range after calculated insertion point.
330
// index is now (-(insertion point)-1), so the insertion point
331
// is -index-1
332
index = -index - 1;
333         if (index >= ranges.size())
334             Exceptions.setNoFirst();
335         return range(index).first();
336     }
337
338     /**
339      * @since 1.2
340      */

341     public byte last() {
342         if (size == 0)
343             Exceptions.setNoLast();
344         return range(ranges.size()-1).last();
345     }
346
347     private byte lastFrom(byte v) {
348         int index = getRangeIndexOf(v);
349         if (index >= 0)
350             return v;
351         // Get first range before calculated insertion point.
352
// index is now (-(insertion point)-1), so the insertion point
353
// is -index-1
354
index = -index - 1;
355         index--;
356         if (index < 0 || index >= ranges.size())
357             Exceptions.setNoLast();
358         return range(index).last();
359     }
360
361     /**
362      * @since 1.2
363      */

364     public ByteSortedSet headSet(byte to) {
365         return new SubSet(false, (byte)0, true, to);
366     }
367
368     /**
369      * @since 1.2
370      */

371     public ByteSortedSet tailSet(byte from) {
372         return new SubSet(true, from, false, (byte)0);
373     }
374
375     /**
376      * @since 1.2
377      */

378     public ByteSortedSet subSet(byte from, byte to) {
379         return new SubSet(true, from, true, to);
380     }
381
382     private class SubSet extends AbstractByteSet implements ByteSortedSet, java.io.Serializable JavaDoc {
383
384         private boolean hasLowerBound;
385         private boolean hasUpperBound;
386         private byte lowerBound;
387         private byte upperBound;
388
389         SubSet(boolean hasLowerBound, byte lowerBound, boolean hasUpperBound, byte upperBound) {
390             if (hasLowerBound) {
391                 if (lowerBound < 0)
392                     Exceptions.negativeArgument("lower bound", String.valueOf(lowerBound));
393                 if (hasUpperBound)
394                     if (upperBound < lowerBound)
395                         Exceptions.invalidSetBounds(String.valueOf(lowerBound), String.valueOf(upperBound));
396             }
397             this.hasLowerBound = hasLowerBound;
398             this.lowerBound = lowerBound;
399             this.hasUpperBound = hasUpperBound;
400             this.upperBound = upperBound;
401         }
402
403         public boolean add(byte v) {
404             if (!inSubRange(v))
405                 Exceptions.valueNotInSubRange(String.valueOf(v));
406             return ByteRangeSet.this.add(v);
407         }
408
409         public boolean remove(byte v) {
410             if (!inSubRange(v))
411                 Exceptions.valueNotInSubRange(String.valueOf(v));
412             return ByteRangeSet.this.remove(v);
413         }
414
415         public boolean contains(byte v) {
416             return inSubRange(v) && ByteRangeSet.this.contains(v);
417         }
418
419         class EmptySubSetIterator implements ByteIterator {
420             public boolean hasNext()
421             { return false; }
422             
423             public byte next()
424             { Exceptions.endOfIterator(); throw new RuntimeException JavaDoc(); }
425             
426             public void remove()
427             { Exceptions.noElementToRemove(); }
428         }
429
430         class SimpleSubSetIterator implements ByteIterator {
431             int nextIndex;
432             int size;
433             int lastIndex;
434             byte lastValue;
435             byte from;
436             byte to;
437
438             SimpleSubSetIterator(byte from, byte to) {
439                 size = (int)(to-from+1);
440                 nextIndex = 0;
441                 lastIndex = -1;
442                 this.from = from;
443                 this.to = to;
444             }
445
446             public boolean hasNext() {
447                 return nextIndex < size;
448             }
449
450             public byte next() {
451                 if (!hasNext())
452                     Exceptions.endOfIterator();
453                 lastValue = (byte)(from + nextIndex);
454                 lastIndex = nextIndex;
455                 nextIndex++;
456                 return lastValue;
457             }
458
459             public void remove() {
460                 if (lastIndex == -1)
461                     Exceptions.noElementToRemove();
462                 ByteRangeSet.this.remove(lastValue);
463                 lastIndex = -1;
464             }
465
466         }
467
468         class NonEmptySubSetIterator implements ByteIterator {
469             byte first;
470             byte last;
471             int rangeIndexLow;
472             int rangeIndexHigh;
473             ByteRange rangeLow;
474             ByteRange rangeHigh;
475             byte previousValue;
476             ByteRange currRange;
477             int currRangeIndex;
478             int currOffset;
479             boolean valueAvailable;
480             int nextIndex;
481
482             NonEmptySubSetIterator(byte first, byte last, int rangeIndexLow, int rangeIndexHigh) {
483                 if (rangeIndexLow == rangeIndexHigh)
484                     throw new RuntimeException JavaDoc("Internal error");
485                 this.first = first;
486                 this.last = last;
487                 this.rangeIndexLow = rangeIndexLow;
488                 this.rangeIndexHigh = rangeIndexHigh;
489                 rangeLow = new ByteRange(first, range(rangeIndexLow).last());
490                 rangeHigh = new ByteRange(range(rangeIndexHigh).first(), last);
491                 currRangeIndex = rangeIndexLow;
492                 currRange = rangeLow;
493                 currOffset = 0;
494                 previousValue = first;
495                 valueAvailable = false;
496                 nextIndex = 0;
497             }
498
499             private ByteRange getRange(int rangeIndex) {
500                 if (rangeIndex == rangeIndexLow)
501                     return rangeLow;
502                 if (rangeIndex == rangeIndexHigh)
503                     return rangeHigh;
504                 return range(rangeIndex);
505             }
506
507             private void recalc() {
508                 first = first();
509                 last = last();
510
511                 rangeIndexLow = getRangeIndexOf(first);
512                 rangeIndexHigh = getRangeIndexOf(last);
513                 if (rangeIndexLow == rangeIndexHigh)
514                     rangeLow = rangeHigh = new ByteRange(first, last);
515                 else {
516                     rangeLow = new ByteRange(first, range(rangeIndexLow).last());
517                     rangeHigh = new ByteRange(range(rangeIndexHigh).first(), last);
518                 }
519                 currOffset = nextIndex;
520                 currRangeIndex = rangeIndexLow;
521                 currRange = rangeLow;
522                 for (;;) {
523                     int rs = currRange.length();
524                     if (currOffset < rs)
525                         break;
526                     currOffset -= rs;
527                     currRange = getRange(++currRangeIndex);
528                 }
529             }
530
531             public boolean hasNext() {
532                 return previousValue < last;
533             }
534
535             public byte next() {
536                 if (!hasNext())
537                     Exceptions.endOfIterator();
538                 previousValue = (byte)(currRange.first() + currOffset++);
539                 if (currOffset == currRange.length() && previousValue < last) {
540                     currOffset = 0;
541                     currRange = getRange(++currRangeIndex);
542                 }
543                 nextIndex++;
544                 valueAvailable = true;
545                 return previousValue;
546             }
547
548             public void remove() {
549                 if (!valueAvailable)
550                     Exceptions.noElementToRemove();
551                 ByteRangeSet.this.remove(previousValue);
552                 nextIndex--;
553                 recalc();
554                 valueAvailable = false;
555             }
556         }
557
558         public ByteIterator iterator() {
559             byte first;
560             byte last;
561             int rangeIndexLow;
562             int rangeIndexHigh;
563
564             try {
565                 first = first();
566             } catch (NoSuchElementException JavaDoc e) {
567                 return new EmptySubSetIterator();
568             }
569             last = last();
570             rangeIndexLow = getRangeIndexOf(first);
571             rangeIndexHigh = getRangeIndexOf(last);
572             if (rangeIndexLow == rangeIndexHigh)
573                 return new SimpleSubSetIterator(first, last);
574             return new NonEmptySubSetIterator(first, last, rangeIndexLow, rangeIndexHigh);
575         }
576
577         public int size() {
578             if (ByteRangeSet.this.size() == 0)
579                 return 0;
580             int size;
581             byte first;
582             int rangeIndexLow;
583             try {
584                 first = first();
585                 rangeIndexLow = getRangeIndexOf(first);
586             } catch (NoSuchElementException JavaDoc e) {
587                 return 0;
588             }
589             byte last = last();
590             int rangeIndexHigh = getRangeIndexOf(last);
591             if (rangeIndexLow == rangeIndexHigh) {
592                 size = (int)(last-first+1);
593             } else {
594                 ByteRange rangeLow = range(rangeIndexLow);
595                 ByteRange rangeHigh = range(rangeIndexHigh);
596                 int sizeLow = (int)(rangeLow.last()-first+1);
597                 int sizeHigh = (int)(last-rangeHigh.first()+1);
598
599                 size = sizeLow + sizeHigh;
600                 for (int i = rangeIndexLow+1; i < rangeIndexHigh; i++)
601                     size += range(i).length();
602             }
603             return size;
604         }
605
606         public byte first() {
607             byte first = firstFrom(hasLowerBound ? lowerBound : 0);
608             if (hasUpperBound && first >= upperBound)
609                 Exceptions.setNoFirst();
610             return first;
611         }
612
613         public byte last() {
614             byte last = lastFrom(hasUpperBound ? (byte)(upperBound-1) : ByteRangeSet.this.last());
615             if (hasLowerBound && last < lowerBound)
616                 Exceptions.setNoLast();
617             return last;
618         }
619
620         public ByteSortedSet headSet(byte to) {
621             if (!inSubRange(to))
622                 Exceptions.invalidUpperBound(String.valueOf(to));
623             return new SubSet(hasLowerBound, lowerBound, true, to);
624         }
625
626         public ByteSortedSet tailSet(byte from) {
627             if (!inSubRange(from))
628                 Exceptions.invalidLowerBound(String.valueOf(from));
629             return new SubSet(true, from, hasUpperBound, upperBound);
630         }
631
632         public ByteSortedSet subSet(byte from, byte to) {
633             if (!inSubRange(from))
634                 Exceptions.invalidLowerBound(String.valueOf(from));
635             if (!inSubRange(to))
636                 Exceptions.invalidUpperBound(String.valueOf(to));
637             return new SubSet(true, from, true, to);
638         }
639
640         private boolean inSubRange(byte v) {
641             if (hasLowerBound && v < lowerBound)
642                 return false;
643             if (hasUpperBound && v >= upperBound)
644                 return false;
645             return true;
646         }
647
648     }
649
650     public String JavaDoc toString() {
651         StringBuffer JavaDoc s = new StringBuffer JavaDoc();
652         s.append('[');
653         for (int i = 0, rsize = ranges.size(); i < rsize; i++) {
654             if (i > 0)
655                 s.append(',');
656             s.append(range(i));
657         }
658         s.append(']');
659         return s.toString();
660     }
661
662     public void trimToSize() {
663         //ranges.trimToSize();
664
}
665
666     /**
667      * Returns a clone of this range set.
668      *
669      * @return a clone of this range set.
670      *
671      * @since 1.1
672      */

673     public Object JavaDoc clone() {
674         try {
675             ByteRangeSet c = (ByteRangeSet)super.clone();
676             c.ranges = (ArrayList JavaDoc)ranges.clone();
677             return c;
678         } catch (CloneNotSupportedException JavaDoc e) {
679             Exceptions.cloning(); throw new RuntimeException JavaDoc();
680         }
681     }
682
683     // ---------------------------------------------------------------
684
// Operations overwritten for efficiency
685
// ---------------------------------------------------------------
686

687     public void clear() {
688         ranges.clear();
689         size = 0;
690     }
691
692     public boolean contains(byte v)
693     { return getRangeIndexOf(v) >= 0; }
694
695     public int hashCode() {
696         int h = 0;
697         for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) {
698             ByteRange r = range(i);
699             for (byte c = r.first(), last = r.last(); c <= last; c++)
700                 h += c;
701         }
702         return h;
703     }
704
705     public boolean isEmpty()
706     { return size == 0; }
707
708     public int size()
709     { return size; }
710
711     public boolean remove(byte v) {
712         int index = getRangeIndexOf(v);
713         if (index < 0)
714             return false;
715         // Treat end points special since we can avoid splitting a range
716
ByteRange r = range(index);
717         if (v == r.first()) {
718             if (r.length() == 1)
719                 ranges.remove(index);
720             else
721                 ranges.set(index, new ByteRange((byte)(r.first()+1), r.last()));
722         } else if (v == r.last()) {
723             // r.length() > 1
724
ranges.set(index, new ByteRange(r.first(), (byte)(r.last()-1)));
725         } else {
726             // Split the range
727
ByteRange r1 = new ByteRange(r.first(), (byte)(v-1));
728             ByteRange r2 = new ByteRange((byte)(v+1), r.last());
729             ranges.set(index, r1);
730             ranges.add(index+1, r2);
731         }
732         size--;
733         return true;
734     }
735
736     public byte[] toArray(byte[] a) {
737         if (a == null || a.length < size)
738             a = new byte[size];
739         for (int i = 0, index = 0, rsize = ranges.size(); i < rsize; i++) {
740             ByteRange r = range(i);
741             for (byte c = r.first(), last = r.last(); c <= last; c++)
742                 a[index++] = c;
743         }
744         return a;
745     }
746
747     // ---------------------------------------------------------------
748
// Extra operations
749
// ---------------------------------------------------------------
750

751     /**
752      * Indicates whether all elements of a specified
753      * range is contained in this set.
754      *
755      * @param range
756      * the range whose elements to test for
757      * containment.
758      *
759      * @return <tt>true</tt> if all the elements of <tt>range</tt>
760      * are contained in this collection; returns
761      * <tt>false</tt> otherwise.
762      *
763      * @throws NullPointerException
764      * if <tt>range</tt> is <tt>null</tt>.
765      *
766      * @see #containsAll(ByteCollection)
767      */

768     public boolean containsAll(ByteRange range) {
769         /*
770             In order for the set to contain the whole range
771             the two range ends must be represented by the same
772             range in the range list.
773          */

774         ByteRange r = getRangeOf(range.first());
775         return r != null ? r.contains(range.last()) : false;
776     }
777
778     /**
779      * Adds all the elements of a specified range set to
780      * this set.
781      *
782      * @param c
783      * the set whose elements to add to this
784      * set.
785      *
786      * @return <tt>true</tt> if this set was modified
787      * as a result of adding the elements of <tt>c</tt>;
788      * returns <tt>false</tt> otherwise.
789      *
790      * @throws NullPointerException
791      * if <tt>c</tt> is <tt>null</tt>.
792      *
793      * @see #add(byte)
794      * @see #addAll(ByteRange)
795      * @see #addAll(ByteCollection)
796      * @see #addAll(byte, byte)
797      * @see #addAll(byte[])
798      */

799     public boolean addAll(ByteRangeSet c) {
800         int oldSize = size;
801         for (int i = 0, rsize = c.ranges.size(); i < rsize; i++)
802             addAll(c.range(i));
803         return size != oldSize;
804     }
805
806     /**
807      * Adds a specified range to this set.
808      *
809      * @param range
810      * the range to add to this set.
811      *
812      * @return <tt>true</tt> if this set was modified
813      * as a result of adding the elements of
814      * <tt>range</tt>; returns <tt>false</tt> otherwise.
815      *
816      * @throws NullPointerException
817      * if <tt>range</tt> is <tt>null</tt>.
818      *
819      * @see #add(byte)
820      * @see #addAll(ByteRangeSet)
821      * @see #addAll(ByteCollection)
822      * @see #addAll(byte, byte)
823      * @see #addAll(byte[])
824      */

825     public boolean addAll(ByteRange range) {
826         int oldSize = size;
827         int index = insertRange(range);
828         if (index != -1) {
829             int nindex = index;
830             if (nindex > 0)
831                 nindex--;
832             size += range.length();
833             normalize(nindex);
834         }
835         return size != oldSize;
836     }
837
838     /**
839      * Adds a specified range to this set.
840      *
841      * @param first
842      * the first value of the range to add to this set.
843      *
844      * @param last
845      * the last value of the range to add to this set.
846      *
847      * @return <tt>true</tt> if this set was modified
848      * as a result of adding the values <tt>first</tt>
849      * to <tt>last</tt>; returns <tt>false</tt>
850      * otherwise.
851      *
852      * @throws IllegalArgumentException
853      * if <tt>first &gt; last</tt>.
854      */

855     public boolean addAll(byte first, byte last) {
856         return addAll(new ByteRange(first, last));
857     }
858
859     /**
860      * Adds an array of byte values to this set.
861      *
862      * @param a
863      * the array of byte values to add to this set.
864      *
865      * @throws NullPointerException
866      * if <tt>a</tt> is <tt>null</tt>.
867      *
868      * @see #add(byte)
869      * @see #addAll(ByteRange)
870      * @see #addAll(ByteRangeSet)
871      * @see #addAll(ByteCollection)
872      * @see #addAll(byte, byte)
873      */

874     public boolean addAll(byte[] a) {
875         if (a.length == 0)
876             return false;
877
878         // Sort a
879
/*
880             We can decide if the array is sorted in at most n steps
881             (n being the length of chars).
882             If it is not sorted, it is probably much less than n steps,
883             and if it is sorted, we can skip the sorting operation
884             and cloning of chars (thus effectively having sorted in
885             linear time).
886         */

887         int oldSize = size;
888         byte[] sa;
889         if (!isSorted(a)) {
890             sa = (byte[])a.clone();
891             java.util.Arrays.sort(sa);
892         } else {
893             sa = a;
894         }
895
896         // Add ranges of a to range list
897
int index = 0;
898         byte c0, c1;
899         while (index < sa.length) {
900             c0 = sa[index];
901             index = range(sa, index);
902             c1 = sa[index];
903             ranges.add(new ByteRange(c0, c1));
904             index++;
905         }
906
907         // Sort and normalize range list
908
/*
909             Is it better to sort and normalize once instead
910             of inserting sorted and performing normalization at each step?
911          */

912         java.util.Collections.sort(ranges);
913         normalize();
914         return size != oldSize;
915     }
916
917     /**
918      * Finds a range in an ordered array which may
919      * contain duplicates.
920      *
921      * @param a
922      * the array of values to search.
923      *
924      * @param index
925      * the index from which to start the search.
926      *
927      * @return the index of the last value in the found
928      * range.
929      */

930     private int range(byte[] a, int index) {
931         byte c0 = a[index++];
932         // Skip duplicates
933
while (index < a.length && a[index] == c0)
934             index++;
935         // While in sequence
936
while (index < a.length && a[index] == (byte)(c0+1)) {
937             c0 = a[index++];
938             // Skip duplicates
939
while (index < a.length && a[index] == c0)
940                 index++;
941         }
942         return index-1;
943     }
944
945     /**
946      * Indicates whether the specified array is sorted in
947      * ascending order.
948      *
949      * @param a
950      * the array to examine.
951      *
952      * @return <tt>true</tt> if <tt>s</tt> is sorted; returns
953      * <tt>false</tt> otherwise.
954      *
955      * @throws NullPointerException
956      * if <tt>a</tt> is <tt>null</tt>.
957      */

958     private boolean isSorted(byte[] a) {
959         for (int i = 1; i < a.length; i++)
960             if (a[i] < a[i-1])
961                 return false;
962         return true;
963     }
964
965     /**
966      * Returns the ranges of this set. None of the ranges returned
967      * will overlap or be adjacent.
968      *
969      * @return the ranges of this set. The returned array is
970      * a fresh copy that can be modified without
971      * modifying this set.
972      */

973     public ByteRange[] ranges() {
974         ByteRange[] a = new ByteRange[ranges.size()];
975         ranges.toArray(a);
976         return a;
977     }
978
979 }
980
Popular Tags