intervalset.java

antlr最新版本V3源代码

/*
 [The "BSD licence"]
 Copyright (c) 2005-2006 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.*;

/** 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 {
	/** The list of sorted, disjoint intervals. */
    protected List intervals;

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

    /** 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));
    }

	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
        for (Iterator iter = other.intervals.iterator(); iter.hasNext();) {
            Interval I = (Interval) iter.next();
            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();
		if ( intervals.size()==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<intervals.size(); 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(intervals.size()-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(0,Label.MAX_CHAR_VALUE));
	}

    /** 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);