1 // Taken from com.onionnetworks.util (BSD license)
2 // Many thanks, Justin and Ry4an!
5 * Common Java Utilities
7 * Copyright (C) 2000-2001 Justin Chapweske (justin@chapweske.com)
8 * Copyright (C) 2000-2001 Ry4an Brase (ry4an@ry4an.org)
9 * Copyright (C) 2001 Onion Networks
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above
18 * copyright notice, this list of conditions and the following
19 * disclaimer in the documentation and/or other materials
20 * provided with the distribution.
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
24 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
25 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS
26 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
27 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
28 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
29 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
31 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
32 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
35 package edu.berkeley.sbp.util;
40 * This class represents a range of integers (incuding positive and negative
45 private boolean negInf, posInf;
49 * Creates a new Range that is only one number, both min and max will
51 * @param num The number that this range will encompass.
53 public Range(long num) {
54 this(num,num,false,false);
58 * Creates a new Range from min and max (inclusive)
59 * @param min The min value of the range.
60 * @param max The max value of the range.
62 public Range(long min, long max) {
63 this(min,max,false,false);
67 * Creates a new Range from min to postive infinity
68 * @param min The min value of the range.
69 * @param posInf Must be true to specify max == positive infinity
71 public Range(long min, boolean posInf) {
72 this(min,Long.MAX_VALUE,false,posInf);
74 throw new IllegalArgumentException("posInf must be true");
79 * Creates a new Range from negative infinity to max.
80 * @param negInf Must be true to specify min == negative infinity
81 * @param max The max value of the range.
83 public Range(boolean negInf, long max) {
84 this(Long.MIN_VALUE,max,negInf,false);
86 throw new IllegalArgumentException("negInf must be true");
91 * Creates a new Range from negative infinity to positive infinity.
92 * @param negInf must be true.
93 * @param posInf must be true.
95 public Range(boolean negInf, boolean posInf) {
96 this(Long.MIN_VALUE,Long.MAX_VALUE,negInf,posInf);
97 if (!negInf || !posInf) {
98 throw new IllegalArgumentException
99 ("negInf && posInf must be true");
103 private Range(long min, long max, boolean negInf, boolean posInf) {
105 throw new IllegalArgumentException
106 ("min cannot be greater than max");
108 // very common bug, its worth reporting for now.
109 if (min == 0 && max == 0) {
110 System.err.println("Range.debug: 0-0 range detected. "+
111 "Did you intend to this? :");
112 new Exception().printStackTrace();
116 this.negInf = negInf;
117 this.posInf = posInf;
121 * @return true if min is negative infinity.
123 public boolean isMinNegInf() {
128 * @return true if max is positive infinity.
130 public boolean isMaxPosInf() {
135 * @return the min value of the range.
137 public long getMin() {
142 * @return the max value of the range.
144 public long getMax() {
149 * @return The size of the range (min and max inclusive) or -1 if the range
153 if (negInf || posInf) {
160 * @param i The integer to check to see if it is in the range.
161 * @return true if i is in the range (min and max inclusive)
163 public boolean contains(long i) {
164 return i >= min && i <= max;
168 * @param r The range to check to see if it is in this range.
169 * @return true if this range contains the entirety of the passed range.
171 public boolean contains(Range r) {
172 return r.min >= min && r.max <= max;
176 public int hashCode() {
177 return (int) (min + 23 * max);
180 public boolean equals(Object obj) {
181 if (obj instanceof Range &&
182 ((Range) obj).min == min && ((Range) obj).max == max &&
183 ((Range) obj).negInf == negInf && ((Range) obj).posInf == posInf) {
190 public String toString() {
191 if (!negInf && !posInf && min == max) {
192 return new Long(min).toString();
194 return (negInf ? "(" : ""+min) + "-" + (posInf ? ")" : ""+max);
199 * This method creates a new range from a String.
200 * Allowable characters are all integer values, "-", ")", and "(". The
201 * open and closed parens indicate positive and negative infinity.
203 * Example strings would be:
204 * "11" is the range that only includes 11
205 * "-6" is the range that only includes -6
206 * "10-20" is the range 10 through 20 (inclusive)
207 * "-10--5" is the range -10 through -5
208 * "(-20" is the range negative infinity through 20
209 * "30-)" is the range 30 through positive infinity.
211 * @param s The String to parse
212 * @return The resulting range
213 * @throws ParseException,
216 public static final Range parse(String s) throws ParseException {
219 boolean negInf=false,posInf=false;
220 // search from the 1 pos because it may be a negative number.
221 int dashPos = s.indexOf("-",1);
222 if (dashPos == -1) { // no dash, one value.
223 min = max = Long.parseLong(s);
225 if (s.indexOf("(") != -1) {
228 min = Long.parseLong(s.substring(0,dashPos));
230 if (s.indexOf(")") != -1) {
233 max = Long.parseLong(s.substring(dashPos+1,s.length()));
238 return new Range(true,true);
240 return new Range(true,max);
243 return new Range(min,true);
245 return new Range(min,max);
247 } catch (RuntimeException e) {
248 throw new ParseException(e.getMessage(),-1);
254 * This class represents a set of integers in a compact form by using ranges.
255 * This is essentially equivilent to run length encoding of a bitmap-based
256 * set and thus works very well for sets with long runs of integers, but is
257 * quite poor for sets with very short runs.
259 * This class is similar in flavor to Perl's IntSpan at
260 * http://world.std.com/~swmcd/steven/perl/lib/Set/IntSpan/
262 * The Ranges use negative and positive infinity so there should be no
263 * border issues with standard set operations and they should behave
264 * exactly as you'd expect from your set identities.
266 * While the data structure itself should be quite efficient for its intended
267 * use, the actual implementation could be heavily optimized beyond what I've
268 * done, feel free to improve it.
270 * @author Justin F. Chapweske
272 public static class Set implements Iterable<Range> {
274 public static final int DEFAULT_CAPACITY = 16;
276 boolean posInf, negInf;
281 * Creates a new empty Range.Set
284 ranges = new long[DEFAULT_CAPACITY * 2];
288 * Creates a new Range.Set and adds the provided Range
289 * @param r The range to add.
291 public Set(Range r) {
296 public Set(Range[] ranges) {
298 for(Range r : ranges) add(r);
301 public Set(Iterable<Range> it) {
303 for(Range r : it) add(r);
307 * @param rs The set with which to union with this set.
308 * @return A new set that represents the union of this and the passed set.
310 public Range.Set union(Range.Set rs) {
311 // This should be rewritten to interleave the additions so that there
312 // is fewer midlist insertions.
313 Range.Set result = new Range.Set();
320 * @param rs The set with which to intersect with this set.
321 * @return new set that represents the intersct of this and the passed set.
323 public Range.Set intersect(Range.Set rs) {
324 Range.Set result = complement();
325 result.add(rs.complement());
326 return result.complement();
330 * @return The complement of this set, make sure to check for positive
331 * and negative infinity on the returned set.
333 public Range.Set complement() {
334 Range.Set rs = new Range.Set();
336 rs.add(new Range(true,true));
339 rs.add(new Range(true,ranges[0]-1));
341 for (int i=0;i<rangeCount-1;i++) {
342 rs.add(ranges[i*2+1]+1,ranges[i*2+2]-1);
345 rs.add(new Range(ranges[(rangeCount-1)*2+1]+1,true));
352 * @param i The integer to check to see if it is in this set..
353 * @return true if i is in the set.
355 public boolean contains(long i) {
356 int pos = binarySearch(i);
370 * Checks to see if this set contains all of the elements of the Range.
372 * @param r The Range to see if this Range.Set contains it.
373 * @return true If every element of the Range is within this set.
375 public boolean contains(Range r) {
376 Range.Set rs = new Range.Set();
378 return intersect(rs).equals(rs);
382 * Add all of the passed set's elements to this set.
384 * @param rs The set whose elements should be added to this set.
386 public void add(Range.Set rs) {
387 for (Iterator it=rs.iterator();it.hasNext();) {
388 add((Range) it.next());
394 * Add this range to the set.
396 * @param r The range to add
398 public void add(Range r) {
399 if (r.isMinNegInf()) {
402 if (r.isMaxPosInf()) {
405 add(r.getMin(),r.getMax());
409 * Add a single integer to this set.
411 * @param i The int to add.
413 public void add(long i) {
418 * Add a range to the set.
419 * @param min The min of the range (inclusive)
420 * @param max The max of the range (inclusive)
422 public void add(long min, long max) {
425 throw new IllegalArgumentException
426 ("min cannot be greater than max");
429 if (rangeCount == 0) { // first value.
434 // This case should be the most common (insert at the end) so we will
435 // specifically check for it. Its +1 so that we make sure its not
436 // adjacent. Do the MIN_VALUE check to make sure we don't overflow
438 if (min != Long.MIN_VALUE && min-1 > ranges[(rangeCount-1)*2+1]) {
439 insert(min,max,rangeCount);
443 // minPos and maxPos represent inclusive brackets around the various
444 // ranges that this new range encompasses. Anything within these
445 // brackets should be folded into the new range.
446 int minPos = getMinPos(min);
447 int maxPos = getMaxPos(max);
449 // minPos and maxPos will switch order if we are either completely
450 // within another range or completely outside of any ranges.
451 if (minPos > maxPos) {
452 if (minPos % 2 == 0) {
453 // outside of any ranges, insert.
454 insert(min,max,minPos/2);
456 // completely inside a range, nop
459 combine(min,max,minPos/2,maxPos/2);
464 public void remove(Range.Set r) {
465 for (Iterator it=r.iterator();it.hasNext();) {
466 remove((Range) it.next());
470 public void remove(Range r) {
471 //FIX absolutely horrible implementation.
472 Range.Set rs = new Range.Set();
474 rs = intersect(rs.complement());
476 rangeCount = rs.rangeCount;
481 public void remove(long i) {
482 remove(new Range(i,i));
485 public void remove(long min, long max) {
486 remove(new Range(min,max));
490 * @return An iterator of Range objects that this Range.Set contains.
492 public Iterator<Range> iterator() {
493 ArrayList l = new ArrayList(rangeCount);
494 for (int i=0;i<rangeCount;i++) {
495 if (rangeCount == 1 && negInf && posInf) {
496 l.add(new Range(true,true));
497 } else if (i == 0 && negInf) {
498 l.add(new Range(true,ranges[i*2+1]));
499 } else if (i == rangeCount-1 && posInf) {
500 l.add(new Range(ranges[i*2],true));
502 l.add(new Range(ranges[i*2],ranges[i*2+1]));
509 * @return The number of integers in this set, -1 if infinate.
512 if (negInf || posInf) {
516 for (Iterator it=iterator();it.hasNext();) {
517 result+=((Range) it.next()).size();
523 * @return true If the set doesn't contain any integers or ranges.
525 public boolean isEmpty() {
526 return rangeCount == 0;
530 * Parse a set of ranges seperated by commas.
534 * @param s The String to parse
535 * @return The resulting range
536 * @throws ParseException
539 public static Range.Set parse(String s) throws ParseException {
540 Range.Set rs = new Range.Set();
541 for (StringTokenizer st = new StringTokenizer(s,",");
542 st.hasMoreTokens();) {
543 rs.add(Range.parse(st.nextToken()));
548 public int hashCode() {
550 for (int i = 0; i < rangeCount*2; i++) {
551 result = (int) (91*result + ranges[i]);
556 public boolean containsAll(Range.Set rs) {
558 if (!contains(r)) return false;
562 public boolean equals(Object obj) {
563 if (obj instanceof Range.Set) {
564 Range.Set rs = (Range.Set) obj;
565 if (negInf == rs.negInf &&
566 posInf == rs.posInf &&
567 rangeCount == rs.rangeCount &&
568 arraysEqual(ranges,0,rs.ranges,0,rangeCount*2)) {
575 public static boolean arraysEqual(int[] arr1, int start1,
576 int[] arr2, int start2, int len) {
577 if (arr1 == arr2 && start1 == start2) {
580 for (int i=len-1;i>=0;i--) {
581 if (arr1[start1+i] != arr2[start2+i]) {
588 public static boolean arraysEqual(long[] arr1, int start1,
589 long[] arr2, int start2, int len) {
590 if (arr1 == arr2 && start1 == start2) {
593 for (int i=len-1;i>=0;i--) {
594 if (arr1[start1+i] != arr2[start2+i]) {
601 public static boolean arraysEqual(char[] arr1, int start1,
602 char[] arr2, int start2, int len) {
603 if (arr1 == arr2 && start1 == start2) {
606 for (int i=len-1;i>=0;i--) {
607 if (arr1[start1+i] != arr2[start2+i]) {
614 public static boolean arraysEqual(byte[] arr1, int start1,
615 byte[] arr2, int start2, int len) {
616 if (arr1 == arr2 && start1 == start2) {
619 for (int i=len-1;i>=0;i--) {
620 if (arr1[start1+i] != arr2[start2+i]) {
629 * Outputs the Range in a manner that can be used to directly create
630 * a new range with the "parse" method.
632 public String toString() {
633 StringBuffer sb = new StringBuffer();
634 for (Iterator it=iterator();it.hasNext();) {
635 sb.append(it.next().toString());
640 return sb.toString();
643 public Object clone() {
644 Range.Set rs = new Range.Set();
645 rs.ranges = new long[ranges.length];
646 System.arraycopy(ranges,0,rs.ranges,0,ranges.length);
647 rs.rangeCount = rangeCount;
653 private void combine(long min, long max, int minRange, int maxRange) {
654 // Fill in the new values into the "leftmost" range.
655 ranges[minRange*2] = Math.min(min,ranges[minRange*2]);
656 ranges[minRange*2+1] = Math.max(max,ranges[maxRange*2+1]);
658 // shrink if necessary.
659 if (minRange != maxRange && maxRange != rangeCount-1) {
660 System.arraycopy(ranges,(maxRange+1)*2,ranges,(minRange+1)*2,
661 (rangeCount-1-maxRange)*2);
664 rangeCount -= maxRange-minRange;
669 * @return the position of the min element within the ranges.
671 private int getMinPos(long min) {
672 // Search for min-1 so that adjacent ranges are included.
673 int pos = binarySearch(min == Long.MIN_VALUE ? min : min-1);
674 return pos >= 0 ? pos : -(pos+1);
678 * @return the position of the max element within the ranges.
680 private int getMaxPos(long max) {
681 // Search for max+1 so that adjacent ranges are included.
682 int pos = binarySearch(max == Long.MAX_VALUE ? max : max+1);
683 // Return pos-1 if there isn't a direct hit because the max
685 return pos >= 0 ? pos : (-(pos+1))-1;
689 * @see java.util.Arrays#binarySearch
691 private int binarySearch(long key) {
693 int high = (rangeCount*2)-1;
695 while (low <= high) {
696 int mid =(low + high)/2;
697 long midVal = ranges[mid];
701 } else if (midVal > key) {
704 return mid; // key found
707 return -(low + 1); // key not found.
710 private void insert(long min, long max, int rangeNum) {
712 // grow the array if necessary.
713 if (ranges.length == rangeCount*2) {
714 long[] newRanges = new long[ranges.length*2];
715 System.arraycopy(ranges,0,newRanges,0,ranges.length);
719 if (rangeNum != rangeCount) {
720 System.arraycopy(ranges,rangeNum*2,ranges,(rangeNum+1)*2,
721 (rangeCount-rangeNum)*2);
723 ranges[rangeNum*2] = min;
724 ranges[rangeNum*2+1] = max;
729 public static final void main(String[] args) throws Exception {
730 Range.Set rs = Range.Set.parse("5-10,15-20,25-30");
731 BufferedReader br = new BufferedReader(new InputStreamReader
734 System.out.println(rs.toString());
735 String s = br.readLine();
736 if (s.charAt(0) == '~') {
737 rs = rs.complement();
738 } else if (s.charAt(0) == 'i') {
739 rs = rs.intersect(Range.Set.parse(br.readLine()));
741 rs.add(Range.Set.parse(s));