1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD license"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2010 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.misc; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.analysis.Label; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.Grammar; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.ArrayList; 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Iterator; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.List; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.ListIterator; 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** A set of integers that relies on ranges being common to do 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * "run-length-encoded" like compression (if you view an IntSet like 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a BitSet with runs of 0s and 1s). Only ranges are recorded so that 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a few ints up near value 1000 don't cause massive bitsets, just two 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * integer intervals. 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * element values may be negative. Useful for sets of EPSILON and EOF. 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 0..9 char range is index pair ['\u0030','\u0039']. 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Multiple ranges are encoded with multiple index pairs. Isolated 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * elements are encoded with an index pair where both intervals are the same. 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The ranges are ordered and disjoint so that 2..6 appears before 101..103. 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class IntervalSet implements IntSet { 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final IntervalSet COMPLETE_SET = IntervalSet.of(0,Label.MAX_CHAR_VALUE); 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The list of sorted, disjoint intervals. */ 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected List<Interval> intervals; 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Create a set with no elements */ 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntervalSet() { 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intervals = new ArrayList<Interval>(2); // most sets are 1 or 2 elements 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntervalSet(List<Interval> intervals) { 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.intervals = intervals; 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Create a set with a single element, el. */ 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static IntervalSet of(int a) { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet s = new IntervalSet(); 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.add(a); 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Create a set with all ints within range [a..b] (inclusive) */ 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static IntervalSet of(int a, int b) { 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet s = new IntervalSet(); 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.add(a,b); 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Add a single element to the set. An isolated element is stored 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as a range el..el. 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void add(int el) { 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver add(el,el); 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Add interval; i.e., add all integers from a to b to set. 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If b<a, do nothing. 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Keep list in sorted order (by left range value). 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If overlap, combine ranges. For example, 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If this is {1..5, 10..20}, adding 6..7 yields 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * {1..5, 6..7, 10..20}. Adding 4..8 yields {1..8, 10..20}. 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void add(int a, int b) { 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver add(Interval.create(a,b)); 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // copy on write so we can cache a..a intervals and sets of that 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void add(Interval addition) { 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("add "+addition+" to "+intervals.toString()); 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.b<addition.a ) { 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // find position in list 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Use iterators as we modify list in place 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (ListIterator iter = intervals.listIterator(); iter.hasNext();) { 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval r = (Interval) iter.next(); 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.equals(r) ) { 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.adjacent(r) || !addition.disjoint(r) ) { 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // next to each other, make a single larger interval 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval bigger = addition.union(r); 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iter.set(bigger); 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make sure we didn't just create an interval that 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // should be merged with next interval in list 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( iter.hasNext() ) { 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval next = (Interval) iter.next(); 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( bigger.adjacent(next)||!bigger.disjoint(next) ) { 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if we bump up against or overlap next, merge 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iter.remove(); // remove this one 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iter.previous(); // move backwards to what we just set 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iter.set(bigger.union(next)); // set to 3 merged ones 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.startsBeforeDisjoint(r) ) { 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // insert before r 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iter.previous(); 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iter.add(addition); 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if disjoint and after r, a future iteration will handle it 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // ok, must be after last interval (and disjoint from last interval) 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // just add it 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intervals.add(addition); 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void add(Interval addition) { 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("add "+addition+" to "+intervals.toString()); 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.b<addition.a ) { 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // find position in list 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //for (ListIterator iter = intervals.listIterator(); iter.hasNext();) { 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=0; i<n; i++) { 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval r = (Interval)intervals.get(i); 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.equals(r) ) { 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.adjacent(r) || !addition.disjoint(r) ) { 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // next to each other, make a single larger interval 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval bigger = addition.union(r); 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intervals.set(i, bigger); 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make sure we didn't just create an interval that 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // should be merged with next interval in list 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( (i+1)<n ) { 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval next = (Interval)intervals.get(i); 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( bigger.adjacent(next)||!bigger.disjoint(next) ) { 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if we bump up against or overlap next, merge 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intervals.remove(i); // remove next one 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i--; 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intervals.set(i, bigger.union(next)); // set to 3 merged ones 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( addition.startsBeforeDisjoint(r) ) { 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // insert before r 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intervals.add(i, addition); 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if disjoint and after r, a future iteration will handle it 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // ok, must be after last interval (and disjoint from last interval) 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // just add it 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intervals.add(addition); 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver*/ 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void addAll(IntSet set) { 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( set==null ) { 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !(set instanceof IntervalSet) ) { 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalArgumentException("can't add non IntSet ("+ 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set.getClass().getName()+ 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ") to IntervalSet"); 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet other = (IntervalSet)set; 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk set and add each interval 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = other.intervals.size(); 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) other.intervals.get(i); 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.add(I.a,I.b); 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet complement(int minElement, int maxElement) { 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.complement(IntervalSet.of(minElement,maxElement)); 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given the set of possible values (rather than, say UNICODE or MAXINT), 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * return a new set containing all elements in vocabulary, but not in 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this. The computation is (vocabulary - this). 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 'this' is assumed to be either a subset or equal to vocabulary. 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet complement(IntSet vocabulary) { 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( vocabulary==null ) { 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; // nothing in common with null set 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !(vocabulary instanceof IntervalSet ) ) { 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalArgumentException("can't complement with non IntervalSet ("+ 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver vocabulary.getClass().getName()+")"); 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet vocabularyIS = ((IntervalSet)vocabulary); 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int maxElement = vocabularyIS.getMaxElement(); 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet compl = new IntervalSet(); 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( n ==0 ) { 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return compl; 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval first = (Interval)intervals.get(0); 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add a range from 0 to first.a constrained to vocab 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( first.a > 0 ) { 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet s = IntervalSet.of(0, first.a-1); 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet a = (IntervalSet)s.and(vocabularyIS); 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver compl.addAll(a); 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=1; i<n; i++) { // from 2nd interval .. nth 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval previous = (Interval)intervals.get(i-1); 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval current = (Interval)intervals.get(i); 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet s = IntervalSet.of(previous.b+1, current.a-1); 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet a = (IntervalSet)s.and(vocabularyIS); 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver compl.addAll(a); 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval last = (Interval)intervals.get(n -1); 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add a range from last.b to maxElement constrained to vocab 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( last.b < maxElement ) { 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet s = IntervalSet.of(last.b+1, maxElement); 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet a = (IntervalSet)s.and(vocabularyIS); 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver compl.addAll(a); 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return compl; 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Compute this-other via this&~other. 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Return a new set containing all elements in this but not in other. 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * other is assumed to be a subset of this; 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * anything that is in other but not in this will be ignored. 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet subtract(IntSet other) { 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // assume the whole unicode range here for the complement 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // because it doesn't matter. Anything beyond the max of this' set 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // will be ignored since we are doing this & ~other. The intersection 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // will be empty. The only problem would be when this' set max value 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // goes beyond MAX_CHAR_VALUE, but hopefully the constant MAX_CHAR_VALUE 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // will prevent this. 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.and(((IntervalSet)other).complement(COMPLETE_SET)); 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** return a new set containing all elements in this but not in other. 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Intervals may have to be broken up when ranges in this overlap 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with ranges in other. other is assumed to be a subset of this; 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * anything that is in other but not in this will be ignored. 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Keep around, but 10-20-2005, I decided to make complement work w/o 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * subtract and so then subtract can simply be a&~b 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet subtract(IntSet other) { 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( other==null || !(other instanceof IntervalSet) ) { 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; // nothing in common with null set 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet diff = new IntervalSet(); 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // iterate down both interval lists 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ListIterator thisIter = this.intervals.listIterator(); 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ListIterator otherIter = ((IntervalSet)other).intervals.listIterator(); 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval mine=null; 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval theirs=null; 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( thisIter.hasNext() ) { 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = (Interval)thisIter.next(); 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( otherIter.hasNext() ) { 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs = (Interval)otherIter.next(); 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( mine!=null ) { 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("mine="+mine+", theirs="+theirs); 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // CASE 1: nothing in theirs removes a chunk from mine 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( theirs==null || mine.disjoint(theirs) ) { 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // SUBCASE 1a: finished traversing theirs; keep adding mine now 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( theirs==null ) { 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add everything in mine to difference since theirs done 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver diff.add(mine); 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = null; 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( thisIter.hasNext() ) { 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = (Interval)thisIter.next(); 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // SUBCASE 1b: mine is completely to the left of theirs 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // so we can add to difference; move mine, but not theirs 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( mine.startsBeforeDisjoint(theirs) ) { 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver diff.add(mine); 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = null; 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( thisIter.hasNext() ) { 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = (Interval)thisIter.next(); 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // SUBCASE 1c: theirs is completely to the left of mine 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // keep looking in theirs 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs = null; 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( otherIter.hasNext() ) { 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs = (Interval)otherIter.next(); 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // CASE 2: theirs breaks mine into two chunks 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( mine.properlyContains(theirs) ) { 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // must add two intervals: stuff to left and stuff to right 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver diff.add(mine.a, theirs.a-1); 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't actually add stuff to right yet as next 'theirs' 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // might overlap with it 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // The stuff to the right might overlap with next "theirs". 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // so it is considered next 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval right = new Interval(theirs.b+1, mine.b); 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = right; 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // move theirs forward 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs = null; 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( otherIter.hasNext() ) { 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs = (Interval)otherIter.next(); 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // CASE 3: theirs covers mine; nothing to add to diff 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( theirs.properlyContains(mine) ) { 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // nothing to add, theirs forces removal totally of mine 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // just move mine looking for an overlapping interval 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = null; 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( thisIter.hasNext() ) { 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = (Interval)thisIter.next(); 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // CASE 4: non proper overlap 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // overlap, but not properly contained 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver diff.add(mine.differenceNotProperlyContained(theirs)); 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // update iterators 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean moveTheirs = true; 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( mine.startsBeforeNonDisjoint(theirs) || 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs.b > mine.b ) 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // uh oh, right of theirs extends past right of mine 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // therefore could overlap with next of mine so don't 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // move theirs iterator yet 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver moveTheirs = false; 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // always move mine 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = null; 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( thisIter.hasNext() ) { 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver mine = (Interval)thisIter.next(); 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( moveTheirs ) { 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs = null; 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( otherIter.hasNext() ) { 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver theirs = (Interval)otherIter.next(); 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return diff; 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** TODO: implement this! */ 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet or(IntSet a) { 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet o = new IntervalSet(); 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver o.addAll(this); 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver o.addAll(a); 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //throw new NoSuchMethodError(); 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return o; 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a new set with the intersection of this set with other. Because 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the intervals are sorted, we can use an iterator for each list and 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * just walk them together. This is roughly O(min(n,m)) for interval 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * list lengths n and m. 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet and(IntSet other) { 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( other==null ) { //|| !(other instanceof IntervalSet) ) { 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; // nothing in common with null set 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ArrayList myIntervals = (ArrayList)this.intervals; 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ArrayList theirIntervals = (ArrayList)((IntervalSet)other).intervals; 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet intersection = null; 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int mySize = myIntervals.size(); 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int theirSize = theirIntervals.size(); 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int i = 0; 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int j = 0; 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // iterate down both interval lists looking for nondisjoint intervals 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( i<mySize && j<theirSize ) { 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval mine = (Interval)myIntervals.get(i); 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval theirs = (Interval)theirIntervals.get(j); 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("mine="+mine+" and theirs="+theirs); 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( mine.startsBeforeDisjoint(theirs) ) { 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // move this iterator looking for interval that might overlap 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( theirs.startsBeforeDisjoint(mine) ) { 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // move other iterator looking for interval that might overlap 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver j++; 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( mine.properlyContains(theirs) ) { 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // overlap, add intersection, get next theirs 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( intersection==null ) { 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intersection = new IntervalSet(); 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intersection.add(mine.intersection(theirs)); 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver j++; 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( theirs.properlyContains(mine) ) { 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // overlap, add intersection, get next mine 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( intersection==null ) { 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intersection = new IntervalSet(); 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intersection.add(mine.intersection(theirs)); 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( !mine.disjoint(theirs) ) { 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // overlap, add intersection 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( intersection==null ) { 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intersection = new IntervalSet(); 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intersection.add(mine.intersection(theirs)); 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Move the iterator of lower range [a..b], but not 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the upper range as it may contain elements that will collide 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // with the next iterator. So, if mine=[0..115] and 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // theirs=[115..200], then intersection is 115 and move mine 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // but not theirs as theirs may collide with the next range 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // in thisIter. 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // move both iterators to next ranges 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( mine.startsAfterNonDisjoint(theirs) ) { 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver j++; 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( theirs.startsAfterNonDisjoint(mine) ) { 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( intersection==null ) { 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new IntervalSet(); 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return intersection; 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Is el in any range of this set? */ 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean member(int el) { 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) intervals.get(i); 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int a = I.a; 477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int b = I.b; 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( el<a ) { 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver break; // list is sorted and el is before this interval; not here 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( el>=a && el<=b ) { 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; // found in this interval 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (ListIterator iter = intervals.listIterator(); iter.hasNext();) { 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) iter.next(); 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( el<I.a ) { 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver break; // list is sorted and el is before this interval; not here 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( el>=I.a && el<=I.b ) { 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; // found in this interval 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** return true if this set has no members */ 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isNil() { 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return intervals==null || intervals.size()==0; 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** If this set is a single integer, return it otherwise Label.INVALID */ 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int getSingleElement() { 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( intervals!=null && intervals.size()==1 ) { 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval)intervals.get(0); 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( I.a == I.b ) { 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return I.a; 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Label.INVALID; 514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int getMaxElement() { 517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isNil() ) { 518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Label.INVALID; 519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval last = (Interval)intervals.get(intervals.size()-1); 521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return last.b; 522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return minimum element >= 0 */ 525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int getMinElement() { 526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isNil() ) { 527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Label.INVALID; 528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) intervals.get(i); 532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int a = I.a; 533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int b = I.b; 534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int v=a; v<=b; v++) { 535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( v>=0 ) return v; 536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Label.INVALID; 539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a list of Interval objects. */ 542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public List<Interval> getIntervals() { 543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return intervals; 544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Are two IntervalSets equal? Because all intervals are sorted 547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and disjoint, equals is a simple linear walk over both lists 548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to make sure they are the same. Interval.equals() is used 549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * by the List.equals() method to check the ranges. 550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean equals(Object obj) { 552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( obj==null || !(obj instanceof IntervalSet) ) { 553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet other = (IntervalSet)obj; 556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.intervals.equals(other.intervals); 557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString() { 560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return toString(null); 561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString(Grammar g) { 564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this.intervals==null || this.intervals.size()==0 ) { 566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return "{}"; 567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this.intervals.size()>1 ) { 569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append("{"); 570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator iter = this.intervals.iterator(); 572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (iter.hasNext()) { 573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) iter.next(); 574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int a = I.a; 575324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int b = I.b; 576324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( a==b ) { 577324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( g!=null ) { 578324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(g.getTokenDisplayName(a)); 579324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 580324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 581324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(a); 582324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 583324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 584324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 585324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( g!=null ) { 586324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(g.getTokenDisplayName(a)+".."+g.getTokenDisplayName(b)); 587324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 588324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 589324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(a+".."+b); 590324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 591324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 592324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( iter.hasNext() ) { 593324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(", "); 594324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 595324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 596324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this.intervals.size()>1 ) { 597324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append("}"); 598324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 599324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 600324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 601324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 602324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int size() { 603324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = 0; 604324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numIntervals = intervals.size(); 605324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( numIntervals==1 ) { 606324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval firstInterval = this.intervals.get(0); 607324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return firstInterval.b-firstInterval.a+1; 608324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 609324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numIntervals; i++) { 610324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) intervals.get(i); 611324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n += (I.b-I.a+1); 612324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 613324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return n; 614324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 615324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 616324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public List toList() { 617324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List values = new ArrayList(); 618324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 619324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 620324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) intervals.get(i); 621324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int a = I.a; 622324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int b = I.b; 623324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int v=a; v<=b; v++) { 624324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver values.add(Utils.integer(v)); 625324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 626324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 627324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return values; 628324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 629324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 630324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Get the ith element of ordered set. Used only by RandomPhrase so 631324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * don't bother to implement if you're not doing that for a new 632324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ANTLR code gen target. 633324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 634324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int get(int i) { 635324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 636324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int index = 0; 637324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int j = 0; j < n; j++) { 638324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) intervals.get(j); 639324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int a = I.a; 640324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int b = I.b; 641324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int v=a; v<=b; v++) { 642324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( index==i ) { 643324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return v; 644324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 645324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver index++; 646324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 647324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 648324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return -1; 649324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 650324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 651324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int[] toArray() { 652324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int[] values = new int[size()]; 653324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 654324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int j = 0; 655324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 656324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) intervals.get(i); 657324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int a = I.a; 658324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int b = I.b; 659324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int v=a; v<=b; v++) { 660324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver values[j] = v; 661324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver j++; 662324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 663324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 664324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return values; 665324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 666324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 667324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public org.antlr.runtime.BitSet toRuntimeBitSet() { 668324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver org.antlr.runtime.BitSet s = 669324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new org.antlr.runtime.BitSet(getMaxElement()+1); 670324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = intervals.size(); 671324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 672324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Interval I = (Interval) intervals.get(i); 673324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int a = I.a; 674324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int b = I.b; 675324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int v=a; v<=b; v++) { 676324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.add(v); 677324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 678324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 679324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return s; 680324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 681324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 682324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void remove(int el) { 683324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new NoSuchMethodError("IntervalSet.remove() unimplemented"); 684324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 685324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 686324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 687324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void finalize() throws Throwable { 688324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver super.finalize(); 689324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("size "+intervals.size()+" "+size()); 690324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 691324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 692324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 693