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