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         /**
 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.
 304          */
 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();
 309             result.add(this);
 310             result.add(rs);
 311             return result;
 312         }
 313
 314         /**
 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.
 317          */
 318         public Range.Set intersect(Range.Set rs) {
 319             Range.Set result = complement();
 320             result.add(rs.complement());
 321             return result.complement();
 322         }
 323
 324         /**
 325          * @return The complement of this set, make sure to check for positive
 326          * and negative infinity on the returned set.
 327          */
 328         public Range.Set complement() {
 329             Range.Set rs = new Range.Set();
 330             if (isEmpty()) {
 331                 rs.add(new Range(true,true));
 332             } else {
 333                 if (!negInf) {
 334                     rs.add(new Range(true,ranges[0]-1));
 335                 }
 336                 for (int i=0;i<rangeCount-1;i++) {
 337                     rs.add(ranges[i*2+1]+1,ranges[i*2+2]-1);
 338                 }
 339                 if (!posInf) {
 340                     rs.add(new Range(ranges[(rangeCount-1)*2+1]+1,true));
 341                 }
 342             }
 343             return rs;
 344         }
 345
 346         /**
 347          * @param i The integer to check to see if it is in this set..
 348          * @return true if i is in the set.
 349          */
 350         public boolean contains(long i) {
 351             int pos = binarySearch(i);
 352             if (pos > 0) {
 353                 return true;
 354             }
 355             pos = -(pos+1);
 356             if (pos % 2 == 0) {
 357                 return false;
 358             } else {
 359                 return true;
 360             }
 361         }
 362
 363         /**
 364          * //FIX unit test
 365          * Checks to see if this set contains all of the elements of the Range.
 366          *
 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.
 369          */
 370         public boolean contains(Range r) {
 371             Range.Set rs = new Range.Set();
 372             rs.add(r);
 373             return intersect(rs).equals(rs);
 374         }
 375
 376         /**
 377          * Add all of the passed set's elements to this set.
 378          *
 379          * @param rs The set whose elements should be added to this set.
 380          */
 381         public void add(Range.Set rs) {
 382             for (Iterator it=rs.iterator();it.hasNext();) {
 383                 add((Range) it.next());
 384             }
 385         }
 386
 387
 388         /**
 389          * Add this range to the set.
 390          *
 391          * @param r The range to add
 392          */
 393         public void add(Range r) {
 394             if (r.isMinNegInf()) {
 395                 negInf = true;
 396             }
 397             if (r.isMaxPosInf()) {
 398                 posInf = true;
 399             }
 400             add(r.getMin(),r.getMax());
 401         }
 402
 403         /**
 404          * Add a single integer to this set.
 405          *
 406          * @param i The int to add.
 407          */
 408         public void add(long i) {
 409             add(i,i);
 410         }
 411
 412         /**
 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)
 416          */
 417         public void add(long min, long max) {
 418
 419             if (min > max) {
 420                 throw new IllegalArgumentException
 421                     ("min cannot be greater than max");
 422             }
 423
 424             if (rangeCount == 0) { // first value.
 425                 insert(min,max,0);
 426                 return;
 427             }
 428
 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
 432             // the long.
 433             if (min != Long.MIN_VALUE && min-1 > ranges[(rangeCount-1)*2+1]) {
 434                 insert(min,max,rangeCount);
 435                 return;
 436             }
 437
 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);
 443
 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);
 450                 } else {
 451                     // completely inside a range, nop
 452                 }
 453             } else {
 454                 combine(min,max,minPos/2,maxPos/2);
 455             }
 456
 457         }
 458
 459         public void remove(Range.Set r) {
 460             for (Iterator it=r.iterator();it.hasNext();) {
 461                 remove((Range) it.next());
 462             }
 463         }
 464
 465         public void remove(Range r) {
 466             //FIX absolutely horrible implementation.
 467             Range.Set rs = new Range.Set();
 468             rs.add(r);
 469             rs = intersect(rs.complement());
 470             ranges = rs.ranges;
 471             rangeCount = rs.rangeCount;
 472             posInf = rs.posInf;
 473             negInf = rs.negInf;
 474         }
 475
 476         public void remove(long i) {
 477             remove(new Range(i,i));
 478         }
 479
 480         public void remove(long min, long max) {
 481             remove(new Range(min,max));
 482         }
 483
 484         /**
 485          * @return An iterator of Range objects that this Range.Set contains.
 486          */
 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));
 496                 } else {
 497                     l.add(new Range(ranges[i*2],ranges[i*2+1]));
 498                 }
 499             }
 500             return l.iterator();
 501         }
 502
 503         /**
 504          * @return The number of integers in this set, -1 if infinate.
 505          */
 506         public long size() {
 507             if (negInf || posInf) {
 508                 return -1;
 509             }
 510             long result = 0;
 511             for (Iterator it=iterator();it.hasNext();) {
 512                 result+=((Range) it.next()).size();
 513             }
 514             return result;
 515         }
 516
 517         /**
 518          * @return true If the set doesn't contain any integers or ranges.
 519          */
 520         public boolean isEmpty() {
 521             return rangeCount == 0;
 522         }
 523
 524         /**
 525          * Parse a set of ranges seperated by commas.
 526          *
 527          * @see Range
 528          *
 529          * @param s The String to parse
 530          * @return The resulting range
 531          * @throws ParseException
 532          */
 533
 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()));
 539             }
 540             return rs;
 541         }
 542
 543         public int hashCode() {
 544             int result = 0;
 545             for (int i = 0; i < rangeCount*2; i++) {
 546                 result = (int) (91*result + ranges[i]);
 547             }
 548             return result;
 549         }
 550
 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)) {
 558                     return true;
 559                 }
 560             }
 561             return false;
 562         }
 563
 564         public static boolean arraysEqual(int[] arr1, int start1,
 565                                           int[] arr2, int start2, int len) {
 566             if (arr1 == arr2 && start1 == start2) {
 567                 return true;
 568             }
 569             for (int i=len-1;i>=0;i--) {
 570                 if (arr1[start1+i] != arr2[start2+i]) {
 571                     return false;
 572                 }
 573             }
 574             return true;
 575         }
 576
 577         public static boolean arraysEqual(long[] arr1, int start1,
 578                                           long[] arr2, int start2, int len) {
 579             if (arr1 == arr2 && start1 == start2) {
 580                 return true;
 581             }
 582             for (int i=len-1;i>=0;i--) {
 583                 if (arr1[start1+i] != arr2[start2+i]) {
 584                     return false;
 585                 }
 586             }
 587             return true;
 588         }
 589
 590         public static boolean arraysEqual(char[] arr1, int start1,
 591                                           char[] arr2, int start2, int len) {
 592             if (arr1 == arr2 && start1 == start2) {
 593                 return true;
 594             }
 595             for (int i=len-1;i>=0;i--) {
 596                 if (arr1[start1+i] != arr2[start2+i]) {
 597                     return false;
 598                 }
 599             }
 600             return true;
 601         }
 602
 603         public static boolean arraysEqual(byte[] arr1, int start1,
 604                                           byte[] arr2, int start2, int len) {
 605             if (arr1 == arr2 && start1 == start2) {
 606                 return true;
 607             }
 608             for (int i=len-1;i>=0;i--) {
 609                 if (arr1[start1+i] != arr2[start2+i]) {
 610                     return false;
 611                 }
 612             }
 613             return true;
 614         }
 615
 616
 617         /**
 618          * Outputs the Range in a manner that can be used to directly create
 619          * a new range with the "parse" method.
 620          */
 621         public String toString() {
 622             StringBuffer sb = new StringBuffer();
 623             for (Iterator it=iterator();it.hasNext();) {
 624                 sb.append(it.next().toString());
 625                 if (it.hasNext()) {
 626                     sb.append(",");
 627                 }
 628             }
 629             return sb.toString();
 630         }
 631
 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;
 637             rs.posInf = posInf;
 638             rs.negInf = negInf;
 639             return rs;
 640         }
 641
 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]);
 646
 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);
 651             }
 652
 653             rangeCount -= maxRange-minRange;
 654         }
 655
 656
 657         /**
 658          * @return the position of the min element within the ranges.
 659          */
 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);
 664         }
 665
 666         /**
 667          * @return the position of the max element within the ranges.
 668          */
 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
 673             // pos is inclusive.
 674             return pos >= 0 ? pos : (-(pos+1))-1;
 675         }
 676
 677         /**
 678          * @see java.util.Arrays#binarySearch
 679          */
 680         private int binarySearch(long key) {
 681             int low = 0;
 682             int high = (rangeCount*2)-1;
 683
 684             while (low <= high) {
 685                 int mid =(low + high)/2;
 686                 long midVal = ranges[mid];
 687
 688                 if (midVal < key) {
 689                     low = mid + 1;
 690                 } else if (midVal > key) {
 691                     high = mid - 1;
 692                 } else {
 693                     return mid; // key found
 694                 }
 695             }
 696             return -(low + 1);  // key not found.
 697         }
 698
 699         private void insert(long min, long max, int rangeNum) {
 700
 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);
 705                 ranges = newRanges;
 706             }
 707
 708             if (rangeNum != rangeCount) {
 709                 System.arraycopy(ranges,rangeNum*2,ranges,(rangeNum+1)*2,
 710                                  (rangeCount-rangeNum)*2);
 711             }
 712             ranges[rangeNum*2] = min;
 713             ranges[rangeNum*2+1] = max;
 714             rangeCount++;
 715         }
 716
 717         /*
 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
 721                                                    (System.in));
 722             while (true) {
 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()));
 729                 } else {
 730                     rs.add(Range.Set.parse(s));
 731                 }
 732             }
 733         }
 734         */
 735     }
 736 }
 737