1 /* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.misc; 29 30 /** An immutable inclusive interval a..b */ 31 public class Interval { 32 public static final int INTERVAL_POOL_MAX_VALUE = 1000; 33 34 static Interval[] cache = new Interval[INTERVAL_POOL_MAX_VALUE+1]; 35 36 public int a; 37 public int b; 38 39 public static int creates = 0; 40 public static int misses = 0; 41 public static int hits = 0; 42 public static int outOfRange = 0; 43 44 public Interval(int a, int b) { this.a=a; this.b=b; } 45 46 /** Interval objects are used readonly so share all with the 47 * same single value a==b up to some max size. Use an array as a perfect hash. 48 * Return shared object for 0..INTERVAL_POOL_MAX_VALUE or a new 49 * Interval object with a..a in it. On Java.g, 218623 IntervalSets 50 * have a..a (set with 1 element). 51 */ 52 public static Interval create(int a, int b) { 53 //return new Interval(a,b); 54 // cache just a..a 55 if ( a!=b || a<0 || a>INTERVAL_POOL_MAX_VALUE ) { 56 return new Interval(a,b); 57 } 58 if ( cache[a]==null ) { 59 cache[a] = new Interval(a,a); 60 } 61 return cache[a]; 62 } 63 64 public boolean equals(Object o) { 65 if ( o==null ) { 66 return false; 67 } 68 Interval other = (Interval)o; 69 return this.a==other.a && this.b==other.b; 70 } 71 72 /** Does this start completely before other? Disjoint */ 73 public boolean startsBeforeDisjoint(Interval other) { 74 return this.a<other.a && this.b<other.a; 75 } 76 77 /** Does this start at or before other? Nondisjoint */ 78 public boolean startsBeforeNonDisjoint(Interval other) { 79 return this.a<=other.a && this.b>=other.a; 80 } 81 82 /** Does this.a start after other.b? May or may not be disjoint */ 83 public boolean startsAfter(Interval other) { return this.a>other.a; } 84 85 /** Does this start completely after other? Disjoint */ 86 public boolean startsAfterDisjoint(Interval other) { 87 return this.a>other.b; 88 } 89 90 /** Does this start after other? NonDisjoint */ 91 public boolean startsAfterNonDisjoint(Interval other) { 92 return this.a>other.a && this.a<=other.b; // this.b>=other.b implied 93 } 94 95 /** Are both ranges disjoint? I.e., no overlap? */ 96 public boolean disjoint(Interval other) { 97 return startsBeforeDisjoint(other) || startsAfterDisjoint(other); 98 } 99 100 /** Are two intervals adjacent such as 0..41 and 42..42? */ 101 public boolean adjacent(Interval other) { 102 return this.a == other.b+1 || this.b == other.a-1; 103 } 104 105 public boolean properlyContains(Interval other) { 106 return other.a >= this.a && other.b <= this.b; 107 } 108 109 /** Return the interval computed from combining this and other */ 110 public Interval union(Interval other) { 111 return Interval.create(Math.min(a,other.a), Math.max(b,other.b)); 112 } 113 114 /** Return the interval in common between this and o */ 115 public Interval intersection(Interval other) { 116 return Interval.create(Math.max(a,other.a), Math.min(b,other.b)); 117 } 118 119 /** Return the interval with elements from this not in other; 120 * other must not be totally enclosed (properly contained) 121 * within this, which would result in two disjoint intervals 122 * instead of the single one returned by this method. 123 */ 124 public Interval differenceNotProperlyContained(Interval other) { 125 Interval diff = null; 126 // other.a to left of this.a (or same) 127 if ( other.startsBeforeNonDisjoint(this) ) { 128 diff = Interval.create(Math.max(this.a,other.b+1), 129 this.b); 130 } 131 132 // other.a to right of this.a 133 else if ( other.startsAfterNonDisjoint(this) ) { 134 diff = Interval.create(this.a, other.a-1); 135 } 136 return diff; 137 } 138 139 public String toString() { 140 return a+".."+b; 141 } 142 } 143
