001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.misc;
029:
030: /** An immutable inclusive interval a..b */
031: public class Interval {
032: public static final int INTERVAL_POOL_MAX_VALUE = 1000;
033: static Interval[] intervals = new Interval[INTERVAL_POOL_MAX_VALUE + 1];
034:
035: public int a;
036: public int b;
037:
038: public Interval(int a, int b) {
039: this .a = a;
040: this .b = b;
041: }
042:
043: /** Interval objects are used readonly so share all with the
044: * same single value a==b up to some max size. Use an array as a perfect hash.
045: * Return shared object for 0..INTERVAL_POOL_MAX_VALUE or a new
046: * Interval object with a..a in it. On Java.g, 218623 IntervalSets
047: * have a..a (set with 1 element).
048: public static Interval create(int a, int b) {
049: if ( a!=b || a<0 || a>INTERVAL_POOL_MAX_VALUE ) {
050: return new Interval(a,b);
051: }
052: if ( intervals[a]==null ) {
053: intervals[a] = new Interval(a,a);
054: }
055: return intervals[a];
056: }
057: ACK! Fuond out that add() actually modifies intervals. :(
058: */
059:
060: public static Interval create(int a, int b) {
061: return new Interval(a, b);
062: }
063:
064: public boolean equals(Object o) {
065: if (o == null) {
066: return false;
067: }
068: Interval other = (Interval) o;
069: return this .a == other.a && this .b == other.b;
070: }
071:
072: /** Does this start completely before other? Disjoint */
073: public boolean startsBeforeDisjoint(Interval other) {
074: return this .a < other.a && this .b < other.a;
075: }
076:
077: /** Does this start at or before other? Nondisjoint */
078: public boolean startsBeforeNonDisjoint(Interval other) {
079: return this .a <= other.a && this .b >= other.a;
080: }
081:
082: /** Does this.a start after other.b? May or may not be disjoint */
083: public boolean startsAfter(Interval other) {
084: return this .a > other.a;
085: }
086:
087: /** Does this start completely after other? Disjoint */
088: public boolean startsAfterDisjoint(Interval other) {
089: return this .a > other.b;
090: }
091:
092: /** Does this start after other? NonDisjoint */
093: public boolean startsAfterNonDisjoint(Interval other) {
094: return this .a > other.a && this .a <= other.b; // this.b>=other.b implied
095: }
096:
097: /** Are both ranges disjoint? I.e., no overlap? */
098: public boolean disjoint(Interval other) {
099: return startsBeforeDisjoint(other)
100: || startsAfterDisjoint(other);
101: }
102:
103: /** Are two intervals adjacent such as 0..41 and 42..42? */
104: public boolean adjacent(Interval other) {
105: return this .a == other.b + 1 || this .b == other.a - 1;
106: }
107:
108: public boolean properlyContains(Interval other) {
109: return other.a >= this .a && other.b <= this .b;
110: }
111:
112: /** Return the interval computed from combining this and other */
113: public Interval union(Interval other) {
114: return new Interval(Math.min(a, other.a), Math.max(b, other.b));
115: }
116:
117: /** Return the interval in common between this and o */
118: public Interval intersection(Interval other) {
119: return new Interval(Math.max(a, other.a), Math.min(b, other.b));
120: }
121:
122: /** Return the interval with elements from this not in other;
123: * other must not be totally enclosed (properly contained)
124: * within this, which would result in two disjoint intervals
125: * instead of the single one returned by this method.
126: */
127: public Interval differenceNotProperlyContained(Interval other) {
128: Interval diff = null;
129: // other.a to left of this.a (or same)
130: if (other.startsBeforeNonDisjoint(this )) {
131: diff = new Interval(Math.max(this .a, other.b + 1), this .b);
132: }
133:
134: // other.a to right of this.a
135: else if (other.startsAfterNonDisjoint(this )) {
136: diff = new Interval(this .a, other.a - 1);
137: }
138: return diff;
139: }
140:
141: public String toString() {
142: return a + ".." + b;
143: }
144: }
|