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 Interval(int a, int b)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 */ create(int a, int b)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 @Override equals(Object o)65 public boolean equals(Object o) { 66 if ( o==null ) { 67 return false; 68 } 69 Interval other = (Interval)o; 70 return this.a==other.a && this.b==other.b; 71 } 72 73 /** Does this start completely before other? Disjoint */ startsBeforeDisjoint(Interval other)74 public boolean startsBeforeDisjoint(Interval other) { 75 return this.a<other.a && this.b<other.a; 76 } 77 78 /** Does this start at or before other? Nondisjoint */ startsBeforeNonDisjoint(Interval other)79 public boolean startsBeforeNonDisjoint(Interval other) { 80 return this.a<=other.a && this.b>=other.a; 81 } 82 83 /** Does this.a start after other.b? May or may not be disjoint */ startsAfter(Interval other)84 public boolean startsAfter(Interval other) { return this.a>other.a; } 85 86 /** Does this start completely after other? Disjoint */ startsAfterDisjoint(Interval other)87 public boolean startsAfterDisjoint(Interval other) { 88 return this.a>other.b; 89 } 90 91 /** Does this start after other? NonDisjoint */ startsAfterNonDisjoint(Interval other)92 public boolean startsAfterNonDisjoint(Interval other) { 93 return this.a>other.a && this.a<=other.b; // this.b>=other.b implied 94 } 95 96 /** Are both ranges disjoint? I.e., no overlap? */ disjoint(Interval other)97 public boolean disjoint(Interval other) { 98 return startsBeforeDisjoint(other) || startsAfterDisjoint(other); 99 } 100 101 /** Are two intervals adjacent such as 0..41 and 42..42? */ adjacent(Interval other)102 public boolean adjacent(Interval other) { 103 return this.a == other.b+1 || this.b == other.a-1; 104 } 105 properlyContains(Interval other)106 public boolean properlyContains(Interval other) { 107 return other.a >= this.a && other.b <= this.b; 108 } 109 110 /** Return the interval computed from combining this and other */ union(Interval other)111 public Interval union(Interval other) { 112 return Interval.create(Math.min(a,other.a), Math.max(b,other.b)); 113 } 114 115 /** Return the interval in common between this and o */ intersection(Interval other)116 public Interval intersection(Interval other) { 117 return Interval.create(Math.max(a,other.a), Math.min(b,other.b)); 118 } 119 120 /** Return the interval with elements from this not in other; 121 * other must not be totally enclosed (properly contained) 122 * within this, which would result in two disjoint intervals 123 * instead of the single one returned by this method. 124 */ differenceNotProperlyContained(Interval other)125 public Interval differenceNotProperlyContained(Interval other) { 126 Interval diff = null; 127 // other.a to left of this.a (or same) 128 if ( other.startsBeforeNonDisjoint(this) ) { 129 diff = Interval.create(Math.max(this.a,other.b+1), 130 this.b); 131 } 132 133 // other.a to right of this.a 134 else if ( other.startsAfterNonDisjoint(this) ) { 135 diff = Interval.create(this.a, other.a-1); 136 } 137 return diff; 138 } 139 140 @Override toString()141 public String toString() { 142 return a+".."+b; 143 } 144 } 145