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 import java.io.*;
  39
  40 /**
  41  * This class represents a range of integers (incuding positive and negative
  42  * infinity).
  43  */
  44 public class Range implements Serializable {
  45
  46     private boolean negInf, posInf;
  47     private long min,max;
  48
  49     /**
  50      * Creates a new Range that is only one number, both min and max will
  51      * equal that number.
  52      * @param num The number that this range will encompass.
  53      */
  54     public Range(long num) {
  55         this(num,num,false,false);
  56     }
  57
  58     /**
  59      * Creates a new Range from min and max (inclusive)
  60      * @param min The min value of the range.
  61      * @param max The max value of the range.
  62      */
  63     public Range(long min, long max) {
  64         this(min,max,false,false);
  65     }
  66
  67     /**
  68      * Creates a new Range from min to postive infinity
  69      * @param min The min value of the range.
  70      * @param posInf Must be true to specify max == positive infinity
  71      */
  72     public Range(long min, boolean posInf) {
  73         this(min,Long.MAX_VALUE,false,posInf);
  74         if (!posInf) {
  75             throw new IllegalArgumentException("posInf must be true");
  76         }
  77     }
  78
  79     /**
  80      * Creates a new Range from negative infinity to max.
  81      * @param negInf Must be true to specify min == negative infinity
  82      * @param max The max value of the range.
  83      */
  84     public Range(boolean negInf, long max) {
  85         this(Long.MIN_VALUE,max,negInf,false);
  86         if (!negInf) {
  87             throw new IllegalArgumentException("negInf must be true");
  88         }
  89     }
  90
  91     /**
  92      * Creates a new Range from negative infinity to positive infinity.
  93      * @param negInf must be true.
  94      * @param posInf must be true.
  95      */
  96     public Range(boolean negInf, boolean posInf) {
  97         this(Long.MIN_VALUE,Long.MAX_VALUE,negInf,posInf);
  98         if (!negInf || !posInf) {
  99             throw new IllegalArgumentException
 100                 ("negInf && posInf must be true");
 101         }
 102     }
 103
 104     private Range(long min, long max, boolean negInf, boolean posInf) {
 105         if (min > max) {
 106             throw new IllegalArgumentException
 107               ("min cannot be greater than max");
 108         }
 109         // very common bug, its worth reporting for now.
 110         if (min == 0 && max == 0) {
 111             System.err.println("Range.debug: 0-0 range detected. "+
 112                                "Did you intend to this? :");
 113             new Exception().printStackTrace();
 114         }
 115         this.min = min;
 116         this.max = max;
 117         this.negInf = negInf;
 118         this.posInf = posInf;
 119     }
 120
 121     /**
 122      * @return true if min is negative infinity.
 123      */
 124     public boolean isMinNegInf() {
 125         return negInf;
 126     }
 127
 128     /**
 129      * @return true if max is positive infinity.
 130      */
 131     public boolean isMaxPosInf() {
 132         return posInf;
 133     }
 134
 135     /**
 136      * @return the min value of the range.
 137      */
 138     public long getMin() {
 139         return min;
 140     }
 141
 142     /**
 143      * @return the max value of the range.
 144      */
 145     public long getMax() {
 146         return max;
 147     }
 148
 149     /**
 150      * @return The size of the range (min and max inclusive) or -1 if the range
 151      * is infinitly long.
 152      */
 153     public long size() {
 154         if (negInf || posInf) {
 155             return -1;
 156         }
 157         return max-min+1;
 158     }
 159
 160     /**
 161      * @param i The integer to check to see if it is in the range.
 162      * @return true if i is in the range (min and max inclusive)
 163      */
 164     public boolean contains(long i) {
 165         return i >= min && i <= max;
 166     }
 167
 168     /**
 169      * @param r The range to check to see if it is in this range.
 170      * @return true if this range contains the entirety of the passed range.
 171      */
 172     public boolean contains(Range r) {
 173         return r.min >= min && r.max <= max;
 174     }
 175
 176
 177     public int hashCode() {
 178         return (int) (min + 23 * max);
 179     }
 180
 181     public boolean equals(Object obj) {
 182         if (obj instanceof Range &&
 183             ((Range) obj).min == min && ((Range) obj).max == max &&
 184             ((Range) obj).negInf == negInf && ((Range) obj).posInf == posInf) {
 185             return true;
 186         } else {
 187             return false;
 188         }
 189     }
 190
 191     public String toString() {
 192         if (!negInf && !posInf && min == max) {
 193             return new Long(min).toString();
 194         } else {
 195             return (negInf ? "(" : ""+min) + "-" + (posInf ? ")" : ""+max);
 196         }
 197     }
 198
 199     /**
 200      * This method creates a new range from a String.
 201      * Allowable characters are all integer values, "-", ")", and "(".  The
 202      * open and closed parens indicate positive and negative infinity.
 203      * <pre>
 204      * Example strings would be:
 205      * "11" is the range that only includes 11
 206      * "-6" is the range that only includes -6
 207      * "10-20" is the range 10 through 20 (inclusive)
 208      * "-10--5" is the range -10 through -5
 209      * "(-20" is the range negative infinity through 20
 210      * "30-)" is the range 30 through positive infinity.
 211      * </pre>
 212      * @param s The String to parse
 213      * @return The resulting range
 214      * @throws ParseException,
 215      */
 216
 217     public static final Range parse(String s) throws ParseException {
 218         try {
 219             long min=0,max=0;
 220             boolean negInf=false,posInf=false;
 221             // search from the 1 pos because it may be a negative number.
 222             int dashPos = s.indexOf("-",1);
 223             if (dashPos == -1) { // no dash, one value.
 224                 min = max = Long.parseLong(s);
 225             } else {
 226                 if (s.indexOf("(") != -1) {
 227                     negInf = true;
 228                 } else {
 229                     min = Long.parseLong(s.substring(0,dashPos));
 230                 }
 231                 if (s.indexOf(")") != -1) {
 232                     posInf = true;
 233                 } else {
 234                     max = Long.parseLong(s.substring(dashPos+1,s.length()));
 235                 }
 236             }
 237             if (negInf) {
 238                 if (posInf) {
 239                     return new Range(true,true);
 240                 } else {
 241                     return new Range(true,max);
 242                 }
 243             } else if (posInf) {
 244                 return new Range(min,true);
 245             } else {
 246                 return new Range(min,max);
 247             }
 248         } catch (RuntimeException e) {
 249             throw new ParseException(e.getMessage(),-1);
 250         }
 251     }
 252
 253
 254     /**
 255      * This class represents a set of integers in a compact form by using ranges.
 256      * This is essentially equivilent to run length encoding of a bitmap-based
 257      * set and thus works very well for sets with long runs of integers, but is
 258      * quite poor for sets with very short runs.
 259      *
 260      * This class is similar in flavor to Perl's IntSpan at
 261      * http://world.std.com/~swmcd/steven/perl/lib/Set/IntSpan/
 262      *
 263      * The Ranges use negative and positive infinity so there should be no
 264      * border issues with standard set operations and they should behave
 265      * exactly as you'd expect from your set identities.
 266      *
 267      * While the data structure itself should be quite efficient for its intended
 268      * use, the actual implementation could be heavily optimized beyond what I've
 269      * done, feel free to improve it.
 270      *
 271      * @author Justin F. Chapweske
 272      */
 273     public static class Set implements Iterable<Range>, Serializable {
 274
 275         public static final int DEFAULT_CAPACITY = 16;
 276
 277         boolean posInf, negInf;
 278         int rangeCount;
 279         long[] ranges;
 280
 281         /**
 282          * Creates a new empty Range.Set
 283          */
 284         public Set() {
 285             ranges = new long[DEFAULT_CAPACITY * 2];
 286         }
 287
 288         /**
 289          * Creates a new Range.Set and adds the provided Range
 290          * @param r The range to add.
 291          */
 292         public Set(Range r) {
 293             this();
 294             add(r);
 295         }
 296
 297         public Set(Range[] ranges) {
 298             this();
 299             for(Range r : ranges) add(r);
 300         }
 301
 302         public Set(Iterable<Range> it) {
 303             this();
 304             for(Range r : it) add(r);
 305         }
 306
 307         /**
 308          * @param rs The set with which to union with this set.
 309          * @return A new set that represents the union of this and the passed set.
 310          */
 311         public Range.Set union(Range.Set rs) {
 312             // This should be rewritten to interleave the additions so that there
 313             // is fewer midlist insertions.
 314             Range.Set result = new Range.Set();
 315             result.add(this);
 316             result.add(rs);
 317             return result;
 318         }
 319
 320         /**
 321          * @param rs The set with which to intersect with this set.
 322          * @return new set that represents the intersct of this and the passed set.
 323          */
 324         public Range.Set intersect(Range.Set rs) {
 325             Range.Set result = complement();
 326             result.add(rs.complement());
 327             return result.complement();
 328         }
 329
 330         /**
 331          * @return The complement of this set, make sure to check for positive
 332          * and negative infinity on the returned set.
 333          */
 334         public Range.Set complement() {
 335             Range.Set rs = new Range.Set();
 336             if (isEmpty()) {
 337                 rs.add(new Range(true,true));
 338             } else {
 339                 if (!negInf) {
 340                     rs.add(new Range(true,ranges[0]-1));
 341                 }
 342                 for (int i=0;i<rangeCount-1;i++) {
 343                     rs.add(ranges[i*2+1]+1,ranges[i*2+2]-1);
 344                 }
 345                 if (!posInf) {
 346                     rs.add(new Range(ranges[(rangeCount-1)*2+1]+1,true));
 347                 }
 348             }
 349             return rs;
 350         }
 351
 352         /**
 353          * @param i The integer to check to see if it is in this set..
 354          * @return true if i is in the set.
 355          */
 356         public boolean contains(long i) {
 357             int pos = binarySearch(i);
 358             if (pos > 0) {
 359                 return true;
 360             }
 361             pos = -(pos+1);
 362             if (pos % 2 == 0) {
 363                 return false;
 364             } else {
 365                 return true;
 366             }
 367         }
 368
 369         /**
 370          * //FIX unit test
 371          * Checks to see if this set contains all of the elements of the Range.
 372          *
 373          * @param r The Range to see if this Range.Set contains it.
 374          * @return true If every element of the Range is within this set.
 375          */
 376         public boolean contains(Range r) {
 377             Range.Set rs = new Range.Set();
 378             rs.add(r);
 379             return intersect(rs).equals(rs);
 380         }
 381
 382         /**
 383          * Add all of the passed set's elements to this set.
 384          *
 385          * @param rs The set whose elements should be added to this set.
 386          */
 387         public void add(Range.Set rs) {
 388             for (Iterator it=rs.iterator();it.hasNext();) {
 389                 add((Range) it.next());
 390             }
 391         }
 392
 393
 394         /**
 395          * Add this range to the set.
 396          *
 397          * @param r The range to add
 398          */
 399         public void add(Range r) {
 400             if (r.isMinNegInf()) {
 401                 negInf = true;
 402             }
 403             if (r.isMaxPosInf()) {
 404                 posInf = true;
 405             }
 406             add(r.getMin(),r.getMax());
 407         }
 408
 409         /**
 410          * Add a single integer to this set.
 411          *
 412          * @param i The int to add.
 413          */
 414         public void add(long i) {
 415             add(i,i);
 416         }
 417
 418         /**
 419          * Add a range to the set.
 420          * @param min The min of the range (inclusive)
 421          * @param max The max of the range (inclusive)
 422          */
 423         public void add(long min, long max) {
 424
 425             if (min > max) {
 426                 throw new IllegalArgumentException
 427                     ("min cannot be greater than max");
 428             }
 429
 430             if (rangeCount == 0) { // first value.
 431                 insert(min,max,0);
 432                 return;
 433             }
 434
 435             // This case should be the most common (insert at the end) so we will
 436             // specifically check for it.  Its +1 so that we make sure its not
 437             // adjacent.  Do the MIN_VALUE check to make sure we don't overflow
 438             // the long.
 439             if (min != Long.MIN_VALUE && min-1 > ranges[(rangeCount-1)*2+1]) {
 440                 insert(min,max,rangeCount);
 441                 return;
 442             }
 443
 444             // minPos and maxPos represent inclusive brackets around the various
 445             // ranges that this new range encompasses.  Anything within these
 446             // brackets should be folded into the new range.
 447             int minPos = getMinPos(min);
 448             int maxPos = getMaxPos(max);
 449
 450             // minPos and maxPos will switch order if we are either completely
 451             // within another range or completely outside of any ranges.
 452             if (minPos > maxPos) {
 453                 if (minPos % 2 == 0) {
 454                     // outside of any ranges, insert.
 455                     insert(min,max,minPos/2);
 456                 } else {
 457                     // completely inside a range, nop
 458                 }
 459             } else {
 460                 combine(min,max,minPos/2,maxPos/2);
 461             }
 462
 463         }
 464
 465         public void remove(Range.Set r) {
 466             for (Iterator it=r.iterator();it.hasNext();) {
 467                 remove((Range) it.next());
 468             }
 469         }
 470
 471         public void remove(Range r) {
 472             //FIX absolutely horrible implementation.
 473             Range.Set rs = new Range.Set();
 474             rs.add(r);
 475             rs = intersect(rs.complement());
 476             ranges = rs.ranges;
 477             rangeCount = rs.rangeCount;
 478             posInf = rs.posInf;
 479             negInf = rs.negInf;
 480         }
 481
 482         public void remove(long i) {
 483             remove(new Range(i,i));
 484         }
 485
 486         public void remove(long min, long max) {
 487             remove(new Range(min,max));
 488         }
 489
 490         /**
 491          * @return An iterator of Range objects that this Range.Set contains.
 492          */
 493         public Iterator<Range> iterator() {
 494             ArrayList l = new ArrayList(rangeCount);
 495             for (int i=0;i<rangeCount;i++) {
 496                 if (rangeCount == 1 && negInf && posInf) {
 497                     l.add(new Range(true,true));
 498                 } else if (i == 0 && negInf) {
 499                     l.add(new Range(true,ranges[i*2+1]));
 500                 } else if (i == rangeCount-1 && posInf) {
 501                     l.add(new Range(ranges[i*2],true));
 502                 } else {
 503                     l.add(new Range(ranges[i*2],ranges[i*2+1]));
 504                 }
 505             }
 506             return l.iterator();
 507         }
 508
 509         /**
 510          * @return The number of integers in this set, -1 if infinate.
 511          */
 512         public long size() {
 513             if (negInf || posInf) {
 514                 return -1;
 515             }
 516             long result = 0;
 517             for (Iterator it=iterator();it.hasNext();) {
 518                 result+=((Range) it.next()).size();
 519             }
 520             return result;
 521         }
 522
 523         /**
 524          * @return true If the set doesn't contain any integers or ranges.
 525          */
 526         public boolean isEmpty() {
 527             return rangeCount == 0;
 528         }
 529
 530         /**
 531          * Parse a set of ranges seperated by commas.
 532          *
 533          * @see Range
 534          *
 535          * @param s The String to parse
 536          * @return The resulting range
 537          * @throws ParseException
 538          */
 539
 540         public static Range.Set parse(String s) throws ParseException {
 541             Range.Set rs = new Range.Set();
 542             for (StringTokenizer st = new StringTokenizer(s,",");
 543                  st.hasMoreTokens();) {
 544                 rs.add(Range.parse(st.nextToken()));
 545             }
 546             return rs;
 547         }
 548
 549         public int hashCode() {
 550             int result = 0;
 551             for (int i = 0; i < rangeCount*2; i++) {
 552                 result = (int) (91*result + ranges[i]);
 553             }
 554             return result;
 555         }
 556
 557         public boolean containsAll(Range.Set rs) {
 558             for(Range r : rs)
 559                 if (!contains(r)) return false;
 560             return true;
 561         }
 562
 563         public boolean equals(Object obj) {
 564             if (obj instanceof Range.Set) {
 565                 Range.Set rs = (Range.Set) obj;
 566                 if (negInf == rs.negInf &&
 567                     posInf == rs.posInf &&
 568                     rangeCount == rs.rangeCount &&
 569                     arraysEqual(ranges,0,rs.ranges,0,rangeCount*2)) {
 570                     return true;
 571                 }
 572             }
 573             return false;
 574         }
 575
 576         public static boolean arraysEqual(int[] arr1, int start1,
 577                                           int[] arr2, int start2, int len) {
 578             if (arr1 == arr2 && start1 == start2) {
 579                 return true;
 580             }
 581             for (int i=len-1;i>=0;i--) {
 582                 if (arr1[start1+i] != arr2[start2+i]) {
 583                     return false;
 584                 }
 585             }
 586             return true;
 587         }
 588
 589         public static boolean arraysEqual(long[] arr1, int start1,
 590                                           long[] arr2, int start2, int len) {
 591             if (arr1 == arr2 && start1 == start2) {
 592                 return true;
 593             }
 594             for (int i=len-1;i>=0;i--) {
 595                 if (arr1[start1+i] != arr2[start2+i]) {
 596                     return false;
 597                 }
 598             }
 599             return true;
 600         }
 601
 602         public static boolean arraysEqual(char[] arr1, int start1,
 603                                           char[] arr2, int start2, int len) {
 604             if (arr1 == arr2 && start1 == start2) {
 605                 return true;
 606             }
 607             for (int i=len-1;i>=0;i--) {
 608                 if (arr1[start1+i] != arr2[start2+i]) {
 609                     return false;
 610                 }
 611             }
 612             return true;
 613         }
 614
 615         public static boolean arraysEqual(byte[] arr1, int start1,
 616                                           byte[] arr2, int start2, int len) {
 617             if (arr1 == arr2 && start1 == start2) {
 618                 return true;
 619             }
 620             for (int i=len-1;i>=0;i--) {
 621                 if (arr1[start1+i] != arr2[start2+i]) {
 622                     return false;
 623                 }
 624             }
 625             return true;
 626         }
 627
 628
 629         /**
 630          * Outputs the Range in a manner that can be used to directly create
 631          * a new range with the "parse" method.
 632          */
 633         public String toString() {
 634             StringBuffer sb = new StringBuffer();
 635             for (Iterator it=iterator();it.hasNext();) {
 636                 sb.append(it.next().toString());
 637                 if (it.hasNext()) {
 638                     sb.append(",");
 639                 }
 640             }
 641             return sb.toString();
 642         }
 643
 644         public Object clone() {
 645             Range.Set rs = new Range.Set();
 646             rs.ranges = new long[ranges.length];
 647             System.arraycopy(ranges,0,rs.ranges,0,ranges.length);
 648             rs.rangeCount = rangeCount;
 649             rs.posInf = posInf;
 650             rs.negInf = negInf;
 651             return rs;
 652         }
 653
 654         private void combine(long min, long max, int minRange, int maxRange) {
 655             // Fill in the new values into the "leftmost" range.
 656             ranges[minRange*2] = Math.min(min,ranges[minRange*2]);
 657             ranges[minRange*2+1] = Math.max(max,ranges[maxRange*2+1]);
 658
 659             // shrink if necessary.
 660             if (minRange != maxRange && maxRange != rangeCount-1) {
 661                 System.arraycopy(ranges,(maxRange+1)*2,ranges,(minRange+1)*2,
 662                                  (rangeCount-1-maxRange)*2);
 663             }
 664
 665             rangeCount -= maxRange-minRange;
 666         }
 667
 668
 669         /**
 670          * @return the position of the min element within the ranges.
 671          */
 672         private int getMinPos(long min) {
 673             // Search for min-1 so that adjacent ranges are included.
 674             int pos = binarySearch(min == Long.MIN_VALUE ? min : min-1);
 675             return pos >= 0 ? pos : -(pos+1);
 676         }
 677
 678         /**
 679          * @return the position of the max element within the ranges.
 680          */
 681         private int getMaxPos(long max) {
 682             // Search for max+1 so that adjacent ranges are included.
 683             int pos = binarySearch(max == Long.MAX_VALUE ? max : max+1);
 684             // Return pos-1 if there isn't a direct hit because the max
 685             // pos is inclusive.
 686             return pos >= 0 ? pos : (-(pos+1))-1;
 687         }
 688
 689         /**
 690          * @see java.util.Arrays#binarySearch
 691          */
 692         private int binarySearch(long key) {
 693             int low = 0;
 694             int high = (rangeCount*2)-1;
 695
 696             while (low <= high) {
 697                 int mid =(low + high)/2;
 698                 long midVal = ranges[mid];
 699
 700                 if (midVal < key) {
 701                     low = mid + 1;
 702                 } else if (midVal > key) {
 703                     high = mid - 1;
 704                 } else {
 705                     return mid; // key found
 706                 }
 707             }
 708             return -(low + 1);  // key not found.
 709         }
 710
 711         private void insert(long min, long max, int rangeNum) {
 712
 713             // grow the array if necessary.
 714             if (ranges.length == rangeCount*2) {
 715                 long[] newRanges = new long[ranges.length*2];
 716                 System.arraycopy(ranges,0,newRanges,0,ranges.length);
 717                 ranges = newRanges;
 718             }
 719
 720             if (rangeNum != rangeCount) {
 721                 System.arraycopy(ranges,rangeNum*2,ranges,(rangeNum+1)*2,
 722                                  (rangeCount-rangeNum)*2);
 723             }
 724             ranges[rangeNum*2] = min;
 725             ranges[rangeNum*2+1] = max;
 726             rangeCount++;
 727         }
 728
 729         /*
 730         public static final void main(String[] args) throws Exception {
 731             Range.Set rs = Range.Set.parse("5-10,15-20,25-30");
 732             BufferedReader br = new BufferedReader(new InputStreamReader
 733                                                    (System.in));
 734             while (true) {
 735                 System.out.println(rs.toString());
 736                 String s = br.readLine();
 737                 if (s.charAt(0) == '~') {
 738                     rs = rs.complement();
 739                 } else if (s.charAt(0) == 'i') {
 740                     rs = rs.intersect(Range.Set.parse(br.readLine()));
 741                 } else {
 742                     rs.add(Range.Set.parse(s));
 743                 }
 744             }
 745         }
 746         */
 747     }
 748 }
 749