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);
302 * @param rs The set with which to union with this set.
303 * @return A new set that represents the union of this and the passed set.
305 public Range.Set union(Range.Set rs) {
306 // This should be rewritten to interleave the additions so that there
307 // is fewer midlist insertions.
308 Range.Set result = new Range.Set();
315 * @param rs The set with which to intersect with this set.
316 * @return new set that represents the intersct of this and the passed set.
318 public Range.Set intersect(Range.Set rs) {
319 Range.Set result = complement();
320 result.add(rs.complement());
321 return result.complement();
325 * @return The complement of this set, make sure to check for positive
326 * and negative infinity on the returned set.
328 public Range.Set complement() {
329 Range.Set rs = new Range.Set();
331 rs.add(new Range(true,true));
334 rs.add(new Range(true,ranges[0]-1));
336 for (int i=0;i<rangeCount-1;i++) {
337 rs.add(ranges[i*2+1]+1,ranges[i*2+2]-1);
340 rs.add(new Range(ranges[(rangeCount-1)*2+1]+1,true));
347 * @param i The integer to check to see if it is in this set..
348 * @return true if i is in the set.
350 public boolean contains(long i) {
351 int pos = binarySearch(i);
365 * Checks to see if this set contains all of the elements of the Range.
367 * @param r The Range to see if this Range.Set contains it.
368 * @return true If every element of the Range is within this set.
370 public boolean contains(Range r) {
371 Range.Set rs = new Range.Set();
373 return intersect(rs).equals(rs);
377 * Add all of the passed set's elements to this set.
379 * @param rs The set whose elements should be added to this set.
381 public void add(Range.Set rs) {
382 for (Iterator it=rs.iterator();it.hasNext();) {
383 add((Range) it.next());
389 * Add this range to the set.
391 * @param r The range to add
393 public void add(Range r) {
394 if (r.isMinNegInf()) {
397 if (r.isMaxPosInf()) {
400 add(r.getMin(),r.getMax());
404 * Add a single integer to this set.
406 * @param i The int to add.
408 public void add(long i) {
413 * Add a range to the set.
414 * @param min The min of the range (inclusive)
415 * @param max The max of the range (inclusive)
417 public void add(long min, long max) {
420 throw new IllegalArgumentException
421 ("min cannot be greater than max");
424 if (rangeCount == 0) { // first value.
429 // This case should be the most common (insert at the end) so we will
430 // specifically check for it. Its +1 so that we make sure its not
431 // adjacent. Do the MIN_VALUE check to make sure we don't overflow
433 if (min != Long.MIN_VALUE && min-1 > ranges[(rangeCount-1)*2+1]) {
434 insert(min,max,rangeCount);
438 // minPos and maxPos represent inclusive brackets around the various
439 // ranges that this new range encompasses. Anything within these
440 // brackets should be folded into the new range.
441 int minPos = getMinPos(min);
442 int maxPos = getMaxPos(max);
444 // minPos and maxPos will switch order if we are either completely
445 // within another range or completely outside of any ranges.
446 if (minPos > maxPos) {
447 if (minPos % 2 == 0) {
448 // outside of any ranges, insert.
449 insert(min,max,minPos/2);
451 // completely inside a range, nop
454 combine(min,max,minPos/2,maxPos/2);
459 public void remove(Range.Set r) {
460 for (Iterator it=r.iterator();it.hasNext();) {
461 remove((Range) it.next());
465 public void remove(Range r) {
466 //FIX absolutely horrible implementation.
467 Range.Set rs = new Range.Set();
469 rs = intersect(rs.complement());
471 rangeCount = rs.rangeCount;
476 public void remove(long i) {
477 remove(new Range(i,i));
480 public void remove(long min, long max) {
481 remove(new Range(min,max));
485 * @return An iterator of Range objects that this Range.Set contains.
487 public Iterator<Range> iterator() {
488 ArrayList l = new ArrayList(rangeCount);
489 for (int i=0;i<rangeCount;i++) {
490 if (rangeCount == 1 && negInf && posInf) {
491 l.add(new Range(true,true));
492 } else if (i == 0 && negInf) {
493 l.add(new Range(true,ranges[i*2+1]));
494 } else if (i == rangeCount-1 && posInf) {
495 l.add(new Range(ranges[i*2],true));
497 l.add(new Range(ranges[i*2],ranges[i*2+1]));
504 * @return The number of integers in this set, -1 if infinate.
507 if (negInf || posInf) {
511 for (Iterator it=iterator();it.hasNext();) {
512 result+=((Range) it.next()).size();
518 * @return true If the set doesn't contain any integers or ranges.
520 public boolean isEmpty() {
521 return rangeCount == 0;
525 * Parse a set of ranges seperated by commas.
529 * @param s The String to parse
530 * @return The resulting range
531 * @throws ParseException
534 public static Range.Set parse(String s) throws ParseException {
535 Range.Set rs = new Range.Set();
536 for (StringTokenizer st = new StringTokenizer(s,",");
537 st.hasMoreTokens();) {
538 rs.add(Range.parse(st.nextToken()));
543 public int hashCode() {
545 for (int i = 0; i < rangeCount*2; i++) {
546 result = (int) (91*result + ranges[i]);
551 public boolean equals(Object obj) {
552 if (obj instanceof Range.Set) {
553 Range.Set rs = (Range.Set) obj;
554 if (negInf == rs.negInf &&
555 posInf == rs.posInf &&
556 rangeCount == rs.rangeCount &&
557 arraysEqual(ranges,0,rs.ranges,0,rangeCount*2)) {
564 public static boolean arraysEqual(int[] arr1, int start1,
565 int[] arr2, int start2, int len) {
566 if (arr1 == arr2 && start1 == start2) {
569 for (int i=len-1;i>=0;i--) {
570 if (arr1[start1+i] != arr2[start2+i]) {
577 public static boolean arraysEqual(long[] arr1, int start1,
578 long[] arr2, int start2, int len) {
579 if (arr1 == arr2 && start1 == start2) {
582 for (int i=len-1;i>=0;i--) {
583 if (arr1[start1+i] != arr2[start2+i]) {
590 public static boolean arraysEqual(char[] arr1, int start1,
591 char[] arr2, int start2, int len) {
592 if (arr1 == arr2 && start1 == start2) {
595 for (int i=len-1;i>=0;i--) {
596 if (arr1[start1+i] != arr2[start2+i]) {
603 public static boolean arraysEqual(byte[] arr1, int start1,
604 byte[] arr2, int start2, int len) {
605 if (arr1 == arr2 && start1 == start2) {
608 for (int i=len-1;i>=0;i--) {
609 if (arr1[start1+i] != arr2[start2+i]) {
618 * Outputs the Range in a manner that can be used to directly create
619 * a new range with the "parse" method.
621 public String toString() {
622 StringBuffer sb = new StringBuffer();
623 for (Iterator it=iterator();it.hasNext();) {
624 sb.append(it.next().toString());
629 return sb.toString();
632 public Object clone() {
633 Range.Set rs = new Range.Set();
634 rs.ranges = new long[ranges.length];
635 System.arraycopy(ranges,0,rs.ranges,0,ranges.length);
636 rs.rangeCount = rangeCount;
642 private void combine(long min, long max, int minRange, int maxRange) {
643 // Fill in the new values into the "leftmost" range.
644 ranges[minRange*2] = Math.min(min,ranges[minRange*2]);
645 ranges[minRange*2+1] = Math.max(max,ranges[maxRange*2+1]);
647 // shrink if necessary.
648 if (minRange != maxRange && maxRange != rangeCount-1) {
649 System.arraycopy(ranges,(maxRange+1)*2,ranges,(minRange+1)*2,
650 (rangeCount-1-maxRange)*2);
653 rangeCount -= maxRange-minRange;
658 * @return the position of the min element within the ranges.
660 private int getMinPos(long min) {
661 // Search for min-1 so that adjacent ranges are included.
662 int pos = binarySearch(min == Long.MIN_VALUE ? min : min-1);
663 return pos >= 0 ? pos : -(pos+1);
667 * @return the position of the max element within the ranges.
669 private int getMaxPos(long max) {
670 // Search for max+1 so that adjacent ranges are included.
671 int pos = binarySearch(max == Long.MAX_VALUE ? max : max+1);
672 // Return pos-1 if there isn't a direct hit because the max
674 return pos >= 0 ? pos : (-(pos+1))-1;
678 * @see java.util.Arrays#binarySearch
680 private int binarySearch(long key) {
682 int high = (rangeCount*2)-1;
684 while (low <= high) {
685 int mid =(low + high)/2;
686 long midVal = ranges[mid];
690 } else if (midVal > key) {
693 return mid; // key found
696 return -(low + 1); // key not found.
699 private void insert(long min, long max, int rangeNum) {
701 // grow the array if necessary.
702 if (ranges.length == rangeCount*2) {
703 long[] newRanges = new long[ranges.length*2];
704 System.arraycopy(ranges,0,newRanges,0,ranges.length);
708 if (rangeNum != rangeCount) {
709 System.arraycopy(ranges,rangeNum*2,ranges,(rangeNum+1)*2,
710 (rangeCount-rangeNum)*2);
712 ranges[rangeNum*2] = min;
713 ranges[rangeNum*2+1] = max;
718 public static final void main(String[] args) throws Exception {
719 Range.Set rs = Range.Set.parse("5-10,15-20,25-30");
720 BufferedReader br = new BufferedReader(new InputStreamReader
723 System.out.println(rs.toString());
724 String s = br.readLine();
725 if (s.charAt(0) == '~') {
726 rs = rs.complement();
727 } else if (s.charAt(0) == 'i') {
728 rs = rs.intersect(Range.Set.parse(br.readLine()));
730 rs.add(Range.Set.parse(s));