antlr/misc/IntervalSet.java

/*
 * [The "BSD license"]
 *  Copyright (c) 2010 Terence Parr
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *  1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *  3. The name of the author may not be used to endorse or promote products
 *      derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.antlr.misc;

import org.antlr.analysis.Label;
import org.antlr.tool.Grammar;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/** A set of integers that relies on ranges being common to do
 *  "run-length-encoded" like compression (if you view an IntSet like
 *  a BitSet with runs of 0s and 1s).  Only ranges are recorded so that
 *  a few ints up near value 1000 don't cause massive bitsets, just two
 *  integer intervals.
 *
 *  element values may be negative.  Useful for sets of EPSILON and EOF.
 *
 *  0..9 char range is index pair ['\u0030','\u0039'].
 *  Multiple ranges are encoded with multiple index pairs.  Isolated
 *  elements are encoded with an index pair where both intervals are the same.
 *
 *  The ranges are ordered and disjoint so that 2..6 appears before 101..103.
 */
public class IntervalSet implements IntSet {
	public static final IntervalSet COMPLETE_SET = IntervalSet.of(0,Label.MAX_CHAR_VALUE);

	/** The list of sorted, disjoint intervals. */
    protected List<Interval> intervals;

	/** Create a set with no elements */
    public IntervalSet() {
        intervals = new ArrayList<Interval>(2); // most sets are 1 or 2 elements
    }

	public IntervalSet(List<Interval> intervals) {
		this.intervals = intervals;
	}

	/** Create a set with a single element, el. */
    public static IntervalSet of(int a) {
		IntervalSet s = new IntervalSet();
        s.add(a);
        return s;
    }

    /** Create a set with all ints within range [a..b] (inclusive) */
    public static IntervalSet of(int a, int b) {
        IntervalSet s = new IntervalSet();
        s.add(a,b);
        return s;
    }

    /** Add a single element to the set.  An isolated element is stored
     *  as a range el..el.
     */
    public void add(int el) {
        add(el,el);
    }

    /** Add interval; i.e., add all integers from a to b to set.
     *  If b<a, do nothing.
     *  Keep list in sorted order (by left range value).
     *  If overlap, combine ranges.  For example,
     *  If this is {1..5, 10..20}, adding 6..7 yields
     *  {1..5, 6..7, 10..20}.  Adding 4..8 yields {1..8, 10..20}.
     */
    public void add(int a, int b) {
        add(Interval.create(a,b));
    }

	// copy on write so we can cache a..a intervals and sets of that
	protected void add(Interval addition) {
		//System.out.println("add "+addition+" to "+intervals.toString());
		if ( addition.b<addition.a ) {
			return;
		}
		// find position in list
		// Use iterators as we modify list in place
		for (ListIterator iter = intervals.listIterator(); iter.hasNext();) {
			Interval r = (Interval) iter.next();
			if ( addition.equals(r) ) {
				return;
			}
			if ( addition.adjacent(r) || !addition.disjoint(r) ) {
				// next to each other, make a single larger interval
				Interval bigger = addition.union(r);
				iter.set(bigger);
				// make sure we didn't just create an interval that
				// should be merged with next interval in list
				if ( iter.hasNext() ) {
					Interval next = (Interval) iter.next();
					if ( bigger.adjacent(next)||!bigger.disjoint(next) ) {
						// if we bump up against or overlap next, merge
						iter.remove();   // remove this one
						iter.previous(); // move backwards to what we just set
						iter.set(bigger.union(next)); // set to 3 merged ones
					}
				}
				return;
			}
			if ( addition.startsBeforeDisjoint(r) ) {
				// insert before r
				iter.previous();
				iter.add(addition);
				return;
			}
			// if disjoint and after r, a future iteration will handle it
		}
		// ok, must be after last interval (and disjoint from last interval)
		// just add it
		intervals.add(addition);
	}

	/*
	protected void add(Interval addition) {
        //System.out.println("add "+addition+" to "+intervals.toString());
        if ( addition.b<addition.a ) {
            return;
        }
        // find position in list
        //for (ListIterator iter = intervals.listIterator(); iter.hasNext();) {
		int n = intervals.size();
		for (int i=0; i<n; i++) {
			Interval r = (Interval)intervals.get(i);
            if ( addition.equals(r) ) {
                return;
            }
            if ( addition.adjacent(r) || !addition.disjoint(r) ) {
                // next to each other, make a single larger interval
                Interval bigger = addition.union(r);
				intervals.set(i, bigger);
                // make sure we didn't just create an interval that
                // should be merged with next interval in list
				if ( (i+1)<n ) {
					i++;
					Interval next = (Interval)intervals.get(i);
                    if ( bigger.adjacent(next)||!bigger.disjoint(next) ) {
                        // if we bump up against or overlap next, merge
						intervals.remove(i); // remove next one
						i--;
						intervals.set(i, bigger.union(next)); // set to 3 merged ones
                    }
                }
                return;
            }
            if ( addition.startsBeforeDisjoint(r) ) {
                // insert before r
				intervals.add(i, addition);
                return;
            }
            // if disjoint and after r, a future iteration will handle it
        }
        // ok, must be after last interval (and disjoint from last interval)
        // just add it
        intervals.add(addition);
    }
*/

	public void addAll(IntSet set) {
		if ( set==null ) {
			return;
		}
        if ( !(set instanceof IntervalSet) ) {
            throw new IllegalArgumentException("can't add non IntSet ("+
											   set.getClass().getName()+
											   ") to IntervalSet");
        }
        IntervalSet other = (IntervalSet)set;
        // walk set and add each interval
		int n = other.intervals.size();
		for (int i = 0; i < n; i++) {
			Interval I = (Interval) other.intervals.get(i);
			this.add(I.a,I.b);
		}
    }

    public IntSet complement(int minElement, int maxElement) {
        return this.complement(IntervalSet.of(minElement,maxElement));
    }

    /** Given the set of possible values (rather than, say UNICODE or MAXINT),
     *  return a new set containing all elements in vocabulary, but not in
     *  this.  The computation is (vocabulary - this).
     *
     *  'this' is assumed to be either a subset or equal to vocabulary.
     */
    public IntSet complement(IntSet vocabulary) {
        if ( vocabulary==null ) {
            return null; // nothing in common with null set
        }
		if ( !(vocabulary instanceof IntervalSet ) ) {
			throw new IllegalArgumentException("can't complement with non IntervalSet ("+
											   vocabulary.getClass().getName()+")");
		}
		IntervalSet vocabularyIS = ((IntervalSet)vocabulary);
		int maxElement = vocabularyIS.getMaxElement();

		IntervalSet compl = new IntervalSet();
		int n = intervals.size();
		if ( n ==0 ) {
			return compl;
		}
		Interval first = (Interval)intervals.get(0);
		// add a range from 0 to first.a constrained to vocab
		if ( first.a > 0 ) {
			IntervalSet s = IntervalSet.of(0, first.a-1);
			IntervalSet a = (IntervalSet)s.and(vocabularyIS);
			compl.addAll(a);
		}
		for (int i=1; i<n; i++) { // from 2nd interval .. nth
			Interval previous = (Interval)intervals.get(i-1);
			Interval current = (Interval)intervals.get(i);
			IntervalSet s = IntervalSet.of(previous.b+1, current.a-1);
			IntervalSet a = (IntervalSet)s.and(vocabularyIS);
			compl.addAll(a);
		}
		Interval last = (Interval)intervals.get(n -1);
		// add a range from last.b to maxElement constrained to vocab
		if ( last.b < maxElement ) {
			IntervalSet s = IntervalSet.of(last.b+1, maxElement);
			IntervalSet a = (IntervalSet)s.and(vocabularyIS);
			compl.addAll(a);
		}
		return compl;
    }

	/** Compute this-other via this&~other.
	 *  Return a new set containing all elements in this but not in other.
	 *  other is assumed to be a subset of this;
     *  anything that is in other but not in this will be ignored.
	 */
	public IntSet subtract(IntSet other) {
		// assume the whole unicode range here for the complement
		// because it doesn't matter.  Anything beyond the max of this' set
		// will be ignored since we are doing this & ~other.  The intersection
		// will be empty.  The only problem would be when this' set max value
		// goes beyond MAX_CHAR_VALUE, but hopefully the constant MAX_CHAR_VALUE
		// will prevent this.
		return this.and(((IntervalSet)other).complement(COMPLETE_SET));
	}

	/** return a new set containing all elements in this but not in other.
     *  Intervals may have to be broken up when ranges in this overlap
     *  with ranges in other.  other is assumed to be a subset of this;
     *  anything that is in other but not in this will be ignored.
	 *
	 *  Keep around, but 10-20-2005, I decided to make complement work w/o
	 *  subtract and so then subtract can simply be a&~b
	 *
    public IntSet subtract(IntSet other) {
        if ( other==null || !(other instanceof IntervalSet) ) {
            return null; // nothing in common with null set
        }

        IntervalSet diff = new IntervalSet();

        // iterate down both interval lists
        ListIterator thisIter = this.intervals.listIterator();
        ListIterator otherIter = ((IntervalSet)other).intervals.listIterator();
        Interval mine=null;
        Interval theirs=null;
        if ( thisIter.hasNext() ) {
            mine = (Interval)thisIter.next();
        }
        if ( otherIter.hasNext() ) {
            theirs = (Interval)otherIter.next();
        }
        while ( mine!=null ) {
            //System.out.println("mine="+mine+", theirs="+theirs);
            // CASE 1: nothing in theirs removes a chunk from mine
            if ( theirs==null || mine.disjoint(theirs) ) {
                // SUBCASE 1a: finished traversing theirs; keep adding mine now
                if ( theirs==null ) {
                    // add everything in mine to difference since theirs done
                    diff.add(mine);
                    mine = null;
                    if ( thisIter.hasNext() ) {
                        mine = (Interval)thisIter.next();
                    }
                }
                else {
                    // SUBCASE 1b: mine is completely to the left of theirs
                    // so we can add to difference; move mine, but not theirs
                    if ( mine.startsBeforeDisjoint(theirs) ) {
                        diff.add(mine);
                        mine = null;
                        if ( thisIter.hasNext() ) {
                            mine = (Interval)thisIter.next();
                        }
                    }
                    // SUBCASE 1c: theirs is completely to the left of mine
                    else {
                        // keep looking in theirs
                        theirs = null;
                        if ( otherIter.hasNext() ) {
                            theirs = (Interval)otherIter.next();
                        }
                    }
                }
            }
            else {
                // CASE 2: theirs breaks mine into two chunks
                if ( mine.properlyContains(theirs) ) {
                    // must add two intervals: stuff to left and stuff to right
                    diff.add(mine.a, theirs.a-1);
                    // don't actually add stuff to right yet as next 'theirs'
                    // might overlap with it
                    // The stuff to the right might overlap with next "theirs".
                    // so it is considered next
                    Interval right = new Interval(theirs.b+1, mine.b);
                    mine = right;
                    // move theirs forward
                    theirs = null;
                    if ( otherIter.hasNext() ) {
                        theirs = (Interval)otherIter.next();
                    }
                }

                // CASE 3: theirs covers mine; nothing to add to diff
                else if ( theirs.properlyContains(mine) ) {
                    // nothing to add, theirs forces removal totally of mine
                    // just move mine looking for an overlapping interval
                    mine = null;
                    if ( thisIter.hasNext() ) {
                        mine = (Interval)thisIter.next();
                    }
                }

                // CASE 4: non proper overlap
                else {
                    // overlap, but not properly contained
                    diff.add(mine.differenceNotProperlyContained(theirs));
                    // update iterators
                    boolean moveTheirs = true;
                    if ( mine.startsBeforeNonDisjoint(theirs) ||
                         theirs.b > mine.b )
                    {
                        // uh oh, right of theirs extends past right of mine
                        // therefore could overlap with next of mine so don't
                        // move theirs iterator yet
                        moveTheirs = false;
                    }
                    // always move mine
                    mine = null;
                    if ( thisIter.hasNext() ) {
                        mine = (Interval)thisIter.next();
                    }
                    if ( moveTheirs ) {
                        theirs = null;
                        if ( otherIter.hasNext() ) {
                            theirs = (Interval)otherIter.next();
                        }
                    }
                }
            }
        }
        return diff;
    }
	 */

    /** TODO: implement this! */
	public IntSet or(IntSet a) {
		IntervalSet o = new IntervalSet();
		o.addAll(this);
		o.addAll(a);
		//throw new NoSuchMethodError();
		return o;
	}

    /** Return a new set with the intersection of this set with other.  Because
     *  the intervals are sorted, we can use an iterator for each list and
     *  just walk them together.  This is roughly O(min(n,m)) for interval
     *  list lengths n and m.
     */
	public IntSet and(IntSet other) {
		if ( other==null ) { //|| !(other instanceof IntervalSet) ) {
			return null; // nothing in common with null set
		}

		ArrayList myIntervals = (ArrayList)this.intervals;
		ArrayList theirIntervals = (ArrayList)((IntervalSet)other).intervals;
		IntervalSet intersection = null;
		int mySize = myIntervals.size();
		int theirSize = theirIntervals.size();
		int i = 0;
		int j = 0;
		// iterate down both interval lists looking for nondisjoint intervals
		while ( i<mySize && j<theirSize ) {
			Interval mine = (Interval)myIntervals.get(i);
			Interval theirs = (Interval)theirIntervals.get(j);
			//System.out.println("mine="+mine+" and theirs="+theirs);
			if ( mine.startsBeforeDisjoint(theirs) ) {
				// move this iterator looking for interval that might overlap
				i++;
			}
			else if ( theirs.startsBeforeDisjoint(mine) ) {
				// move other iterator looking for interval that might overlap
				j++;
			}
			else if ( mine.properlyContains(theirs) ) {
				// overlap, add intersection, get next theirs
				if ( intersection==null ) {
					intersection = new IntervalSet();
				}
				intersection.add(mine.intersection(theirs));
				j++;
			}
			else if ( theirs.properlyContains(mine) ) {
				// overlap, add intersection, get next mine
				if ( intersection==null ) {
					intersection = new IntervalSet();
				}
				intersection.add(mine.intersection(theirs));
				i++;
			}
			else if ( !mine.disjoint(theirs) ) {
				// overlap, add intersection
				if ( intersection==null ) {
					intersection = new IntervalSet();
				}
				intersection.add(mine.intersection(theirs));
				// Move the iterator of lower range [a..b], but not
				// the upper range as it may contain elements that will collide
				// with the next iterator. So, if mine=[0..115] and
				// theirs=[115..200], then intersection is 115 and move mine
				// but not theirs as theirs may collide with the next range
				// in thisIter.
				// move both iterators to next ranges
				if ( mine.startsAfterNonDisjoint(theirs) ) {
					j++;
				}
				else if ( theirs.startsAfterNonDisjoint(mine) ) {
					i++;
				}
			}
		}
		if ( intersection==null ) {
			return new IntervalSet();
		}
		return intersection;
	}

    /** Is el in any range of this set? */
    public boolean member(int el) {
		int n = intervals.size();
		for (int i = 0; i < n; i++) {
			Interval I = (Interval) intervals.get(i);
			int a = I.a;
			int b = I.b;
			if ( el<a ) {
				break; // list is sorted and el is before this interval; not here
			}
			if ( el>=a && el<=b ) {
				return true; // found in this interval
			}
		}
		return false;
/*
		for (ListIterator iter = intervals.listIterator(); iter.hasNext();) {
            Interval I = (Interval) iter.next();
            if ( el<I.a ) {
                break; // list is sorted and el is before this interval; not here
            }
            if ( el>=I.a && el<=I.b ) {
                return true; // found in this interval
            }
        }
        return false;
        */
    }

    /** return true if this set has no members */
    public boolean isNil() {
        return intervals==null || intervals.size()==0;
    }

    /** If this set is a single integer, return it otherwise Label.INVALID */
    public int getSingleElement() {
        if ( intervals!=null && intervals.size()==1 ) {
            Interval I = (Interval)intervals.get(0);
            if ( I.a == I.b ) {
                return I.a;
            }
        }
        return Label.INVALID;
    }

	public int getMaxElement() {
		if ( isNil() ) {
			return Label.INVALID;
		}
		Interval last = (Interval)intervals.get(intervals.size()-1);
		return last.b;
	}

	/** Return minimum element >= 0 */
	public int getMinElement() {
		if ( isNil() ) {
			return Label.INVALID;
		}
		int n = intervals.size();
		for (int i = 0; i < n; i++) {
			Interval I = (Interval) intervals.get(i);
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				if ( v>=0 ) return v;
			}
		}
		return Label.INVALID;
	}

    /** Return a list of Interval objects. */
    public List<Interval> getIntervals() {
        return intervals;
    }

    /** Are two IntervalSets equal?  Because all intervals are sorted
     *  and disjoint, equals is a simple linear walk over both lists
     *  to make sure they are the same.  Interval.equals() is used
     *  by the List.equals() method to check the ranges.
     */
    public boolean equals(Object obj) {
        if ( obj==null || !(obj instanceof IntervalSet) ) {
            return false;
        }
        IntervalSet other = (IntervalSet)obj;
        return this.intervals.equals(other.intervals);
    }

    public String toString() {
        return toString(null);
    }

    public String toString(Grammar g) {
        StringBuffer buf = new StringBuffer();
		if ( this.intervals==null || this.intervals.size()==0 ) {
			return "{}";
		}
        if ( this.intervals.size()>1 ) {
            buf.append("{");
        }
        Iterator iter = this.intervals.iterator();
        while (iter.hasNext()) {
            Interval I = (Interval) iter.next();
            int a = I.a;
            int b = I.b;
            if ( a==b ) {
                if ( g!=null ) {
                    buf.append(g.getTokenDisplayName(a));
                }
                else {
                    buf.append(a);
                }
            }
            else {
                if ( g!=null ) {
                    buf.append(g.getTokenDisplayName(a)+".."+g.getTokenDisplayName(b));
                }
                else {
                    buf.append(a+".."+b);
                }
            }
            if ( iter.hasNext() ) {
                buf.append(", ");
            }
        }
        if ( this.intervals.size()>1 ) {
            buf.append("}");
        }
        return buf.toString();
    }

    public int size() {
		int n = 0;
		int numIntervals = intervals.size();
		if ( numIntervals==1 ) {
			Interval firstInterval = this.intervals.get(0);
			return firstInterval.b-firstInterval.a+1;
		}
		for (int i = 0; i < numIntervals; i++) {
			Interval I = (Interval) intervals.get(i);
			n += (I.b-I.a+1);
		}
		return n;
    }

    public List toList() {
		List values = new ArrayList();
		int n = intervals.size();
		for (int i = 0; i < n; i++) {
			Interval I = (Interval) intervals.get(i);
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				values.add(Utils.integer(v));
			}
		}
		return values;
    }

	/** Get the ith element of ordered set.  Used only by RandomPhrase so
	 *  don't bother to implement if you're not doing that for a new
	 *  ANTLR code gen target.
	 */
	public int get(int i) {
		int n = intervals.size();
		int index = 0;
		for (int j = 0; j < n; j++) {
			Interval I = (Interval) intervals.get(j);
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				if ( index==i ) {
					return v;
				}
				index++;
			}
		}
		return -1;
	}

	public int[] toArray() {
		int[] values = new int[size()];
		int n = intervals.size();
		int j = 0;
		for (int i = 0; i < n; i++) {
			Interval I = (Interval) intervals.get(i);
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				values[j] = v;
				j++;
			}
		}
		return values;
	}

	public org.antlr.runtime.BitSet toRuntimeBitSet() {
		org.antlr.runtime.BitSet s =
			new org.antlr.runtime.BitSet(getMaxElement()+1);
		int n = intervals.size();
		for (int i = 0; i < n; i++) {
			Interval I = (Interval) intervals.get(i);
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				s.add(v);
			}
		}
		return s;
	}

	public void remove(int el) {
        throw new NoSuchMethodError("IntervalSet.remove() unimplemented");
    }

	/*
	protected void finalize() throws Throwable {
		super.finalize();
		System.out.println("size "+intervals.size()+" "+size());
	}
	*/
}