intervalset.java

antlr最新版本V3源代码

                    // 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) {
		throw new NoSuchMethodError();
    }

    /** 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) {
        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;
		}
		Iterator iter = this.intervals.iterator();
		while (iter.hasNext()) {
			Interval I = (Interval) iter.next();
			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 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;
		Iterator iter = this.intervals.iterator();
		while (iter.hasNext()) {
			Interval I = (Interval) iter.next();
			int a = I.a;
			int b = I.b;
			n += (b-a+1);
		}
		return n;
    }

    public List toList() {
		List values = new ArrayList();
		Iterator iter = this.intervals.iterator();
		while (iter.hasNext()) {
			Interval I = (Interval) iter.next();
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				values.add(Utils.integer(v));
			}
		}
		return values;
    }

	public int[] toArray() {
		int[] values = new int[size()];
		Iterator iter = this.intervals.iterator();
		int i = 0;
		while (iter.hasNext()) {
			Interval I = (Interval) iter.next();
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				values[i] = v;
				i++;
			}
		}
		return values;
	}

	public org.antlr.runtime.BitSet toRuntimeBitSet() {
		org.antlr.runtime.BitSet s =
			new org.antlr.runtime.BitSet(getMaxElement()+1);
		Iterator iter = this.intervals.iterator();
		int i = 0;
		while (iter.hasNext()) {
			Interval I = (Interval) iter.next();
			int a = I.a;
			int b = I.b;
			for (int v=a; v<=b; v++) {
				s.add(v);
				i++;
			}
		}
		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());
	}
	*/
}