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;
41 * This class represents a range of integers (incuding positive and negative
44 public class Range implements Serializable {
46 private boolean negInf, posInf;
50 * Creates a new Range that is only one number, both min and max will
52 * @param num The number that this range will encompass.
54 public Range(long num) {
55 this(num,num,false,false);
59 * Creates a new Range from min and max (inclusive)
60 * @param min The min value of the range.
61 * @param max The max value of the range.
63 public Range(long min, long max) {
64 this(min,max,false,false);
68 * Creates a new Range from min to postive infinity
69 * @param min The min value of the range.
70 * @param posInf Must be true to specify max == positive infinity
72 public Range(long min, boolean posInf) {
73 this(min,Long.MAX_VALUE,false,posInf);
75 throw new IllegalArgumentException("posInf must be true");
80 * Creates a new Range from negative infinity to max.
81 * @param negInf Must be true to specify min == negative infinity
82 * @param max The max value of the range.
84 public Range(boolean negInf, long max) {
85 this(Long.MIN_VALUE,max,negInf,false);
87 throw new IllegalArgumentException("negInf must be true");
92 * Creates a new Range from negative infinity to positive infinity.
93 * @param negInf must be true.
94 * @param posInf must be true.
96 public Range(boolean negInf, boolean posInf) {
97 this(Long.MIN_VALUE,Long.MAX_VALUE,negInf,posInf);
98 if (!negInf || !posInf) {
99 throw new IllegalArgumentException
100 ("negInf && posInf must be true");
104 private Range(long min, long max, boolean negInf, boolean posInf) {
106 throw new IllegalArgumentException
107 ("min cannot be greater than max");
109 // very common bug, its worth reporting for now.
110 if (min == 0 && max == 0) {
111 System.err.println("Range.debug: 0-0 range detected. "+
112 "Did you intend to this? :");
113 new Exception().printStackTrace();
117 this.negInf = negInf;
118 this.posInf = posInf;
122 * @return true if min is negative infinity.
124 public boolean isMinNegInf() {
129 * @return true if max is positive infinity.
131 public boolean isMaxPosInf() {
136 * @return the min value of the range.
138 public long getMin() {
143 * @return the max value of the range.
145 public long getMax() {
150 * @return The size of the range (min and max inclusive) or -1 if the range
154 if (negInf || posInf) {
161 * @param i The integer to check to see if it is in the range.
162 * @return true if i is in the range (min and max inclusive)
164 public boolean contains(long i) {
165 return i >= min && i <= max;
169 * @param r The range to check to see if it is in this range.
170 * @return true if this range contains the entirety of the passed range.
172 public boolean contains(Range r) {
173 return r.min >= min && r.max <= max;
177 public int hashCode() {
178 return (int) (min + 23 * max);
181 public boolean equals(Object obj) {
182 if (obj instanceof Range &&
183 ((Range) obj).min == min && ((Range) obj).max == max &&
184 ((Range) obj).negInf == negInf && ((Range) obj).posInf == posInf) {
191 public String toString() {
192 if (!negInf && !posInf && min == max) {
193 return new Long(min).toString();
195 return (negInf ? "(" : ""+min) + "-" + (posInf ? ")" : ""+max);
200 * This method creates a new range from a String.
201 * Allowable characters are all integer values, "-", ")", and "(". The
202 * open and closed parens indicate positive and negative infinity.
204 * Example strings would be:
205 * "11" is the range that only includes 11
206 * "-6" is the range that only includes -6
207 * "10-20" is the range 10 through 20 (inclusive)
208 * "-10--5" is the range -10 through -5
209 * "(-20" is the range negative infinity through 20
210 * "30-)" is the range 30 through positive infinity.
212 * @param s The String to parse
213 * @return The resulting range
214 * @throws ParseException,
217 public static final Range parse(String s) throws ParseException {
220 boolean negInf=false,posInf=false;
221 // search from the 1 pos because it may be a negative number.
222 int dashPos = s.indexOf("-",1);
223 if (dashPos == -1) { // no dash, one value.
224 min = max = Long.parseLong(s);
226 if (s.indexOf("(") != -1) {
229 min = Long.parseLong(s.substring(0,dashPos));
231 if (s.indexOf(")") != -1) {
234 max = Long.parseLong(s.substring(dashPos+1,s.length()));
239 return new Range(true,true);
241 return new Range(true,max);
244 return new Range(min,true);
246 return new Range(min,max);
248 } catch (RuntimeException e) {
249 throw new ParseException(e.getMessage(),-1);
255 * This class represents a set of integers in a compact form by using ranges.
256 * This is essentially equivilent to run length encoding of a bitmap-based
257 * set and thus works very well for sets with long runs of integers, but is
258 * quite poor for sets with very short runs.
260 * This class is similar in flavor to Perl's IntSpan at
261 * http://world.std.com/~swmcd/steven/perl/lib/Set/IntSpan/
263 * The Ranges use negative and positive infinity so there should be no
264 * border issues with standard set operations and they should behave
265 * exactly as you'd expect from your set identities.
267 * While the data structure itself should be quite efficient for its intended
268 * use, the actual implementation could be heavily optimized beyond what I've
269 * done, feel free to improve it.
271 * @author Justin F. Chapweske
273 public static class Set implements Iterable<Range>, Serializable {
275 public static final int DEFAULT_CAPACITY = 16;
277 boolean posInf, negInf;
282 * Creates a new empty Range.Set
285 ranges = new long[DEFAULT_CAPACITY * 2];
289 * Creates a new Range.Set and adds the provided Range
290 * @param r The range to add.
292 public Set(Range r) {
297 public Set(Range[] ranges) {
299 for(Range r : ranges) add(r);
302 public Set(Iterable<Range> it) {
304 for(Range r : it) add(r);
308 * @param rs The set with which to union with this set.
309 * @return A new set that represents the union of this and the passed set.
311 public Range.Set union(Range.Set rs) {
312 // This should be rewritten to interleave the additions so that there
313 // is fewer midlist insertions.
314 Range.Set result = new Range.Set();
321 * @param rs The set with which to intersect with this set.
322 * @return new set that represents the intersct of this and the passed set.
324 public Range.Set intersect(Range.Set rs) {
325 Range.Set result = complement();
326 result.add(rs.complement());
327 return result.complement();
331 * @return The complement of this set, make sure to check for positive
332 * and negative infinity on the returned set.
334 public Range.Set complement() {
335 Range.Set rs = new Range.Set();
337 rs.add(new Range(true,true));
340 rs.add(new Range(true,ranges[0]-1));
342 for (int i=0;i<rangeCount-1;i++) {
343 rs.add(ranges[i*2+1]+1,ranges[i*2+2]-1);
346 rs.add(new Range(ranges[(rangeCount-1)*2+1]+1,true));
353 * @param i The integer to check to see if it is in this set..
354 * @return true if i is in the set.
356 public boolean contains(long i) {
357 int pos = binarySearch(i);
371 * Checks to see if this set contains all of the elements of the Range.
373 * @param r The Range to see if this Range.Set contains it.
374 * @return true If every element of the Range is within this set.
376 public boolean contains(Range r) {
377 Range.Set rs = new Range.Set();
379 return intersect(rs).equals(rs);
383 * Add all of the passed set's elements to this set.
385 * @param rs The set whose elements should be added to this set.
387 public void add(Range.Set rs) {
388 for (Iterator it=rs.iterator();it.hasNext();) {
389 add((Range) it.next());
395 * Add this range to the set.
397 * @param r The range to add
399 public void add(Range r) {
400 if (r.isMinNegInf()) {
403 if (r.isMaxPosInf()) {
406 add(r.getMin(),r.getMax());
410 * Add a single integer to this set.
412 * @param i The int to add.
414 public void add(long i) {
419 * Add a range to the set.
420 * @param min The min of the range (inclusive)
421 * @param max The max of the range (inclusive)
423 public void add(long min, long max) {
426 throw new IllegalArgumentException
427 ("min cannot be greater than max");
430 if (rangeCount == 0) { // first value.
435 // This case should be the most common (insert at the end) so we will
436 // specifically check for it. Its +1 so that we make sure its not
437 // adjacent. Do the MIN_VALUE check to make sure we don't overflow
439 if (min != Long.MIN_VALUE && min-1 > ranges[(rangeCount-1)*2+1]) {
440 insert(min,max,rangeCount);
444 // minPos and maxPos represent inclusive brackets around the various
445 // ranges that this new range encompasses. Anything within these
446 // brackets should be folded into the new range.
447 int minPos = getMinPos(min);
448 int maxPos = getMaxPos(max);
450 // minPos and maxPos will switch order if we are either completely
451 // within another range or completely outside of any ranges.
452 if (minPos > maxPos) {
453 if (minPos % 2 == 0) {
454 // outside of any ranges, insert.
455 insert(min,max,minPos/2);
457 // completely inside a range, nop
460 combine(min,max,minPos/2,maxPos/2);
465 public void remove(Range.Set r) {
466 for (Iterator it=r.iterator();it.hasNext();) {
467 remove((Range) it.next());
471 public void remove(Range r) {
472 //FIX absolutely horrible implementation.
473 Range.Set rs = new Range.Set();
475 rs = intersect(rs.complement());
477 rangeCount = rs.rangeCount;
482 public void remove(long i) {
483 remove(new Range(i,i));
486 public void remove(long min, long max) {
487 remove(new Range(min,max));
491 * @return An iterator of Range objects that this Range.Set contains.
493 public Iterator<Range> iterator() {
494 ArrayList l = new ArrayList(rangeCount);
495 for (int i=0;i<rangeCount;i++) {
496 if (rangeCount == 1 && negInf && posInf) {
497 l.add(new Range(true,true));
498 } else if (i == 0 && negInf) {
499 l.add(new Range(true,ranges[i*2+1]));
500 } else if (i == rangeCount-1 && posInf) {
501 l.add(new Range(ranges[i*2],true));
503 l.add(new Range(ranges[i*2],ranges[i*2+1]));
510 * @return The number of integers in this set, -1 if infinate.
513 if (negInf || posInf) {
517 for (Iterator it=iterator();it.hasNext();) {
518 result+=((Range) it.next()).size();
524 * @return true If the set doesn't contain any integers or ranges.
526 public boolean isEmpty() {
527 return rangeCount == 0;
531 * Parse a set of ranges seperated by commas.
535 * @param s The String to parse
536 * @return The resulting range
537 * @throws ParseException
540 public static Range.Set parse(String s) throws ParseException {
541 Range.Set rs = new Range.Set();
542 for (StringTokenizer st = new StringTokenizer(s,",");
543 st.hasMoreTokens();) {
544 rs.add(Range.parse(st.nextToken()));
549 public int hashCode() {
551 for (int i = 0; i < rangeCount*2; i++) {
552 result = (int) (91*result + ranges[i]);
557 public boolean containsAll(Range.Set rs) {
559 if (!contains(r)) return false;
563 public boolean equals(Object obj) {
564 if (obj instanceof Range.Set) {
565 Range.Set rs = (Range.Set) obj;
566 if (negInf == rs.negInf &&
567 posInf == rs.posInf &&
568 rangeCount == rs.rangeCount &&
569 arraysEqual(ranges,0,rs.ranges,0,rangeCount*2)) {
576 public static boolean arraysEqual(int[] arr1, int start1,
577 int[] arr2, int start2, int len) {
578 if (arr1 == arr2 && start1 == start2) {
581 for (int i=len-1;i>=0;i--) {
582 if (arr1[start1+i] != arr2[start2+i]) {
589 public static boolean arraysEqual(long[] arr1, int start1,
590 long[] arr2, int start2, int len) {
591 if (arr1 == arr2 && start1 == start2) {
594 for (int i=len-1;i>=0;i--) {
595 if (arr1[start1+i] != arr2[start2+i]) {
602 public static boolean arraysEqual(char[] arr1, int start1,
603 char[] arr2, int start2, int len) {
604 if (arr1 == arr2 && start1 == start2) {
607 for (int i=len-1;i>=0;i--) {
608 if (arr1[start1+i] != arr2[start2+i]) {
615 public static boolean arraysEqual(byte[] arr1, int start1,
616 byte[] arr2, int start2, int len) {
617 if (arr1 == arr2 && start1 == start2) {
620 for (int i=len-1;i>=0;i--) {
621 if (arr1[start1+i] != arr2[start2+i]) {
630 * Outputs the Range in a manner that can be used to directly create
631 * a new range with the "parse" method.
633 public String toString() {
634 StringBuffer sb = new StringBuffer();
635 for (Iterator it=iterator();it.hasNext();) {
636 sb.append(it.next().toString());
641 return sb.toString();
644 public Object clone() {
645 Range.Set rs = new Range.Set();
646 rs.ranges = new long[ranges.length];
647 System.arraycopy(ranges,0,rs.ranges,0,ranges.length);
648 rs.rangeCount = rangeCount;
654 private void combine(long min, long max, int minRange, int maxRange) {
655 // Fill in the new values into the "leftmost" range.
656 ranges[minRange*2] = Math.min(min,ranges[minRange*2]);
657 ranges[minRange*2+1] = Math.max(max,ranges[maxRange*2+1]);
659 // shrink if necessary.
660 if (minRange != maxRange && maxRange != rangeCount-1) {
661 System.arraycopy(ranges,(maxRange+1)*2,ranges,(minRange+1)*2,
662 (rangeCount-1-maxRange)*2);
665 rangeCount -= maxRange-minRange;
670 * @return the position of the min element within the ranges.
672 private int getMinPos(long min) {
673 // Search for min-1 so that adjacent ranges are included.
674 int pos = binarySearch(min == Long.MIN_VALUE ? min : min-1);
675 return pos >= 0 ? pos : -(pos+1);
679 * @return the position of the max element within the ranges.
681 private int getMaxPos(long max) {
682 // Search for max+1 so that adjacent ranges are included.
683 int pos = binarySearch(max == Long.MAX_VALUE ? max : max+1);
684 // Return pos-1 if there isn't a direct hit because the max
686 return pos >= 0 ? pos : (-(pos+1))-1;
690 * @see java.util.Arrays#binarySearch
692 private int binarySearch(long key) {
694 int high = (rangeCount*2)-1;
696 while (low <= high) {
697 int mid =(low + high)/2;
698 long midVal = ranges[mid];
702 } else if (midVal > key) {
705 return mid; // key found
708 return -(low + 1); // key not found.
711 private void insert(long min, long max, int rangeNum) {
713 // grow the array if necessary.
714 if (ranges.length == rangeCount*2) {
715 long[] newRanges = new long[ranges.length*2];
716 System.arraycopy(ranges,0,newRanges,0,ranges.length);
720 if (rangeNum != rangeCount) {
721 System.arraycopy(ranges,rangeNum*2,ranges,(rangeNum+1)*2,
722 (rangeCount-rangeNum)*2);
724 ranges[rangeNum*2] = min;
725 ranges[rangeNum*2+1] = max;
730 public static final void main(String[] args) throws Exception {
731 Range.Set rs = Range.Set.parse("5-10,15-20,25-30");
732 BufferedReader br = new BufferedReader(new InputStreamReader
735 System.out.println(rs.toString());
736 String s = br.readLine();
737 if (s.charAt(0) == '~') {
738 rs = rs.complement();
739 } else if (s.charAt(0) == 'i') {
740 rs = rs.intersect(Range.Set.parse(br.readLine()));
742 rs.add(Range.Set.parse(s));