714cd8314bce30cdafb65d9b7b914bbd5c38b3f9
[sbp.git] / src / edu / berkeley / sbp / util / Range.java
1 // Taken from com.onionnetworks.util (BSD license)
2 // Many thanks, Justin and Ry4an!
3
4 /*
5  * Common Java Utilities
6  *
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
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
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.
21  *
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
33  * OF SUCH DAMAGE.
34  */
35 package edu.berkeley.sbp.util;
36 import java.util.*;
37 import java.text.*;
38
39 /**
40  * This class represents a range of integers (incuding positive and negative 
41  * infinity).
42  */
43 public class Range {
44
45     private boolean negInf, posInf;
46     private long min,max;
47    
48     /**
49      * Creates a new Range that is only one number, both min and max will
50      * equal that number.
51      * @param num The number that this range will encompass.
52      */
53     public Range(long num) {
54         this(num,num,false,false);
55     }
56
57     /**
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.
61      */
62     public Range(long min, long max) {
63         this(min,max,false,false);
64     }
65
66     /**
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
70      */
71     public Range(long min, boolean posInf) {
72         this(min,Long.MAX_VALUE,false,posInf);
73         if (!posInf) {
74             throw new IllegalArgumentException("posInf must be true");
75         }
76     }
77
78     /**
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.
82      */
83     public Range(boolean negInf, long max) {
84         this(Long.MIN_VALUE,max,negInf,false);
85         if (!negInf) {
86             throw new IllegalArgumentException("negInf must be true");
87         }
88     }
89
90     /**
91      * Creates a new Range from negative infinity to positive infinity.
92      * @param negInf must be true.
93      * @param posInf must be true.
94      */
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");
100         }
101     }
102
103     private Range(long min, long max, boolean negInf, boolean posInf) {
104         if (min > max) {
105             throw new IllegalArgumentException
106               ("min cannot be greater than max");
107         }
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();
113         }
114         this.min = min;
115         this.max = max;
116         this.negInf = negInf;
117         this.posInf = posInf;
118     }
119     
120     /**
121      * @return true if min is negative infinity.
122      */
123     public boolean isMinNegInf() {
124         return negInf;
125     }
126
127     /**
128      * @return true if max is positive infinity.
129      */
130     public boolean isMaxPosInf() {
131         return posInf;
132     }
133
134     /**
135      * @return the min value of the range.
136      */
137     public long getMin() {
138         return min;
139     }
140     
141     /**
142      * @return the max value of the range.
143      */
144     public long getMax() {
145         return max;
146     }
147     
148     /**
149      * @return The size of the range (min and max inclusive) or -1 if the range
150      * is infinitly long.
151      */
152     public long size() {
153         if (negInf || posInf) {
154             return -1;
155         }
156         return max-min+1;
157     }
158
159     /**
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)
162      */
163     public boolean contains(long i) {
164         return i >= min && i <= max;
165     }
166     
167     /**
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.
170      */
171     public boolean contains(Range r) {
172         return r.min >= min && r.max <= max;
173     }
174     
175     
176     public int hashCode() {
177         return (int) (min + 23 * max);
178     }
179     
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) {
184             return true;
185         } else {
186             return false;
187         }
188     }
189     
190     public String toString() {
191         if (!negInf && !posInf && min == max) {
192             return new Long(min).toString();
193         } else {
194             return (negInf ? "(" : ""+min) + "-" + (posInf ? ")" : ""+max);
195         }
196     }
197     
198     /**
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.
202      * <pre>
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.
210      * </pre>
211      * @param s The String to parse
212      * @return The resulting range
213      * @throws ParseException, 
214      */
215
216     public static final Range parse(String s) throws ParseException {
217         try {
218             long min=0,max=0;
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);
224             } else {
225                 if (s.indexOf("(") != -1) {
226                     negInf = true;
227                 } else {
228                     min = Long.parseLong(s.substring(0,dashPos));
229                 }
230                 if (s.indexOf(")") != -1) {
231                     posInf = true;
232                 } else {
233                     max = Long.parseLong(s.substring(dashPos+1,s.length()));
234                 }
235             }
236             if (negInf) {
237                 if (posInf) {
238                     return new Range(true,true);
239                 } else {
240                     return new Range(true,max);
241                 }
242             } else if (posInf) {
243                 return new Range(min,true);
244             } else {
245                 return new Range(min,max);
246             }
247         } catch (RuntimeException e) {
248             throw new ParseException(e.getMessage(),-1);
249         }
250     }    
251
252
253     /**
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.
258      *
259      * This class is similar in flavor to Perl's IntSpan at 
260      * http://world.std.com/~swmcd/steven/perl/lib/Set/IntSpan/
261      *
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.
265      *
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.
269      *
270      * @author Justin F. Chapweske
271      */
272     public static class Set implements Iterable<Range> {
273  
274         public static final int DEFAULT_CAPACITY = 16;
275     
276         boolean posInf, negInf;
277         int rangeCount;
278         long[] ranges;
279     
280         /**
281          * Creates a new empty Range.Set
282          */
283         public Set() {
284             ranges = new long[DEFAULT_CAPACITY * 2];
285         }
286
287         /**
288          * Creates a new Range.Set and adds the provided Range
289          * @param r The range to add.
290          */
291         public Set(Range r) {
292             this();
293             add(r);
294         }
295
296         public Set(Range[] ranges) {
297             this();
298             for(Range r : ranges) add(r);
299         }
300     
301         public Set(Iterable<Range> it) {
302             this();
303             for(Range r : it) add(r);
304         }
305     
306         /**
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.
309          */
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();
314             result.add(this);
315             result.add(rs);
316             return result;
317         }
318     
319         /**
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.
322          */
323         public Range.Set intersect(Range.Set rs) {
324             Range.Set result = complement();
325             result.add(rs.complement());
326             return result.complement();
327         }
328     
329         /**
330          * @return The complement of this set, make sure to check for positive
331          * and negative infinity on the returned set.
332          */
333         public Range.Set complement() {
334             Range.Set rs = new Range.Set();
335             if (isEmpty()) {
336                 rs.add(new Range(true,true));
337             } else {
338                 if (!negInf) {
339                     rs.add(new Range(true,ranges[0]-1));
340                 }
341                 for (int i=0;i<rangeCount-1;i++) {
342                     rs.add(ranges[i*2+1]+1,ranges[i*2+2]-1);
343                 }
344                 if (!posInf) {
345                     rs.add(new Range(ranges[(rangeCount-1)*2+1]+1,true));
346                 }
347             }
348             return rs;
349         }
350         
351         /**
352          * @param i The integer to check to see if it is in this set..
353          * @return true if i is in the set.
354          */
355         public boolean contains(long i) {
356             int pos = binarySearch(i);
357             if (pos > 0) {
358                 return true;
359             }
360             pos = -(pos+1);
361             if (pos % 2 == 0) {
362                 return false;
363             } else {
364                 return true;
365             }
366         }
367  
368         /**
369          * //FIX unit test
370          * Checks to see if this set contains all of the elements of the Range.
371          *
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.
374          */
375         public boolean contains(Range r) {
376             Range.Set rs = new Range.Set();
377             rs.add(r);
378             return intersect(rs).equals(rs);
379         }
380
381         /**
382          * Add all of the passed set's elements to this set.
383          *
384          * @param rs The set whose elements should be added to this set.
385          */
386         public void add(Range.Set rs) {
387             for (Iterator it=rs.iterator();it.hasNext();) {
388                 add((Range) it.next());
389             }
390         }
391     
392
393         /**
394          * Add this range to the set.
395          *
396          * @param r The range to add
397          */
398         public void add(Range r) {
399             if (r.isMinNegInf()) {
400                 negInf = true;
401             }
402             if (r.isMaxPosInf()) {
403                 posInf = true;
404             }
405             add(r.getMin(),r.getMax());
406         }
407
408         /**
409          * Add a single integer to this set.
410          *
411          * @param i The int to add.
412          */
413         public void add(long i) {
414             add(i,i);
415         }
416     
417         /**
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)
421          */
422         public void add(long min, long max) {
423
424             if (min > max) {
425                 throw new IllegalArgumentException
426                     ("min cannot be greater than max");
427             }
428
429             if (rangeCount == 0) { // first value.
430                 insert(min,max,0);
431                 return;
432             }
433         
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
437             // the long.
438             if (min != Long.MIN_VALUE && min-1 > ranges[(rangeCount-1)*2+1]) {
439                 insert(min,max,rangeCount);
440                 return;
441             } 
442
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);
448         
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);
455                 } else {
456                     // completely inside a range, nop
457                 }
458             } else {
459                 combine(min,max,minPos/2,maxPos/2);
460             }
461
462         }
463     
464         public void remove(Range.Set r) {
465             for (Iterator it=r.iterator();it.hasNext();) {
466                 remove((Range) it.next());
467             }
468         }
469
470         public void remove(Range r) {
471             //FIX absolutely horrible implementation.
472             Range.Set rs = new Range.Set();
473             rs.add(r);
474             rs = intersect(rs.complement());
475             ranges = rs.ranges;
476             rangeCount = rs.rangeCount;
477             posInf = rs.posInf;
478             negInf = rs.negInf;
479         }
480
481         public void remove(long i) {
482             remove(new Range(i,i));
483         }
484
485         public void remove(long min, long max) {
486             remove(new Range(min,max));
487         }
488
489         /**
490          * @return An iterator of Range objects that this Range.Set contains.
491          */
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));
501                 } else {
502                     l.add(new Range(ranges[i*2],ranges[i*2+1]));
503                 }
504             }
505             return l.iterator();
506         }
507
508         /**
509          * @return The number of integers in this set, -1 if infinate.
510          */
511         public long size() {
512             if (negInf || posInf) {
513                 return -1;
514             }
515             long result = 0;
516             for (Iterator it=iterator();it.hasNext();) {
517                 result+=((Range) it.next()).size();
518             }
519             return result;
520         }
521
522         /**
523          * @return true If the set doesn't contain any integers or ranges.
524          */
525         public boolean isEmpty() {
526             return rangeCount == 0;
527         }
528     
529         /**
530          * Parse a set of ranges seperated by commas.
531          *
532          * @see Range
533          *
534          * @param s The String to parse
535          * @return The resulting range
536          * @throws ParseException
537          */
538
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()));
544             }
545             return rs;
546         }
547
548         public int hashCode() {
549             int result = 0;
550             for (int i = 0; i < rangeCount*2; i++) {
551                 result = (int) (91*result + ranges[i]);
552             }
553             return result;
554         }
555
556         public boolean equals(Object obj) {
557             if (obj instanceof Range.Set) {
558                 Range.Set rs = (Range.Set) obj;
559                 if (negInf == rs.negInf &&
560                     posInf == rs.posInf &&
561                     rangeCount == rs.rangeCount &&
562                     arraysEqual(ranges,0,rs.ranges,0,rangeCount*2)) {
563                     return true;
564                 }
565             }
566             return false;
567         }
568
569         public static boolean arraysEqual(int[] arr1, int start1, 
570                                           int[] arr2, int start2, int len) {
571             if (arr1 == arr2 && start1 == start2) {
572                 return true;
573             }
574             for (int i=len-1;i>=0;i--) {
575                 if (arr1[start1+i] != arr2[start2+i]) {
576                     return false;
577                 }
578             }
579             return true;
580         }    
581
582         public static boolean arraysEqual(long[] arr1, int start1, 
583                                           long[] arr2, int start2, int len) {
584             if (arr1 == arr2 && start1 == start2) {
585                 return true;
586             }
587             for (int i=len-1;i>=0;i--) {
588                 if (arr1[start1+i] != arr2[start2+i]) {
589                     return false;
590                 }
591             }
592             return true;
593         }    
594
595         public static boolean arraysEqual(char[] arr1, int start1, 
596                                           char[] arr2, int start2, int len) {
597             if (arr1 == arr2 && start1 == start2) {
598                 return true;
599             }
600             for (int i=len-1;i>=0;i--) {
601                 if (arr1[start1+i] != arr2[start2+i]) {
602                     return false;
603                 }
604             }
605             return true;
606         }
607
608         public static boolean arraysEqual(byte[] arr1, int start1, 
609                                           byte[] arr2, int start2, int len) {
610             if (arr1 == arr2 && start1 == start2) {
611                 return true;
612             }
613             for (int i=len-1;i>=0;i--) {
614                 if (arr1[start1+i] != arr2[start2+i]) {
615                     return false;
616                 }
617             }
618             return true;
619         }
620
621             
622         /**
623          * Outputs the Range in a manner that can be used to directly create
624          * a new range with the "parse" method.
625          */
626         public String toString() {
627             StringBuffer sb = new StringBuffer();
628             for (Iterator it=iterator();it.hasNext();) {
629                 sb.append(it.next().toString());
630                 if (it.hasNext()) {
631                     sb.append(",");
632                 }
633             }
634             return sb.toString();
635         }
636
637         public Object clone() {
638             Range.Set rs = new Range.Set();
639             rs.ranges = new long[ranges.length];
640             System.arraycopy(ranges,0,rs.ranges,0,ranges.length);
641             rs.rangeCount = rangeCount;
642             rs.posInf = posInf;
643             rs.negInf = negInf;
644             return rs;
645         }
646
647         private void combine(long min, long max, int minRange, int maxRange) {
648             // Fill in the new values into the "leftmost" range.
649             ranges[minRange*2] = Math.min(min,ranges[minRange*2]);
650             ranges[minRange*2+1] = Math.max(max,ranges[maxRange*2+1]);
651         
652             // shrink if necessary.
653             if (minRange != maxRange && maxRange != rangeCount-1) {
654                 System.arraycopy(ranges,(maxRange+1)*2,ranges,(minRange+1)*2,
655                                  (rangeCount-1-maxRange)*2);
656             }
657         
658             rangeCount -= maxRange-minRange;
659         }
660     
661     
662         /**
663          * @return the position of the min element within the ranges.
664          */
665         private int getMinPos(long min) {
666             // Search for min-1 so that adjacent ranges are included.
667             int pos = binarySearch(min == Long.MIN_VALUE ? min : min-1);
668             return pos >= 0 ? pos : -(pos+1);
669         }
670     
671         /**
672          * @return the position of the max element within the ranges.
673          */
674         private int getMaxPos(long max) {
675             // Search for max+1 so that adjacent ranges are included.
676             int pos = binarySearch(max == Long.MAX_VALUE ? max : max+1);
677             // Return pos-1 if there isn't a direct hit because the max
678             // pos is inclusive.
679             return pos >= 0 ? pos : (-(pos+1))-1;
680         }
681     
682         /**
683          * @see java.util.Arrays#binarySearch
684          */
685         private int binarySearch(long key) {
686             int low = 0;
687             int high = (rangeCount*2)-1;
688         
689             while (low <= high) {
690                 int mid =(low + high)/2;
691                 long midVal = ranges[mid];
692             
693                 if (midVal < key) {
694                     low = mid + 1;
695                 } else if (midVal > key) {
696                     high = mid - 1;
697                 } else {
698                     return mid; // key found
699                 }
700             }
701             return -(low + 1);  // key not found.
702         }
703     
704         private void insert(long min, long max, int rangeNum) {
705         
706             // grow the array if necessary.
707             if (ranges.length == rangeCount*2) {
708                 long[] newRanges = new long[ranges.length*2];
709                 System.arraycopy(ranges,0,newRanges,0,ranges.length);
710                 ranges = newRanges;
711             }
712         
713             if (rangeNum != rangeCount) {
714                 System.arraycopy(ranges,rangeNum*2,ranges,(rangeNum+1)*2,
715                                  (rangeCount-rangeNum)*2);
716             }
717             ranges[rangeNum*2] = min;
718             ranges[rangeNum*2+1] = max;
719             rangeCount++;
720         }
721
722         /*
723         public static final void main(String[] args) throws Exception {
724             Range.Set rs = Range.Set.parse("5-10,15-20,25-30");
725             BufferedReader br = new BufferedReader(new InputStreamReader
726                                                    (System.in));
727             while (true) {
728                 System.out.println(rs.toString());
729                 String s = br.readLine();
730                 if (s.charAt(0) == '~') {
731                     rs = rs.complement();
732                 } else if (s.charAt(0) == 'i') {
733                     rs = rs.intersect(Range.Set.parse(br.readLine()));
734                 } else {
735                     rs.add(Range.Set.parse(s));
736                 }
737             }
738         }
739         */
740     }
741 }
742