org.antlr.misc
Class IntervalSet

java.lang.Object
  extended by org.antlr.misc.IntervalSet
All Implemented Interfaces:
IntSet

public class IntervalSet
extends java.lang.Object
implements IntSet

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 ['0','9']. 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.


Field Summary
static IntervalSet COMPLETE_SET
           
protected  java.util.List<Interval> intervals
          The list of sorted, disjoint intervals.
 
Constructor Summary
IntervalSet()
          Create a set with no elements
IntervalSet(java.util.List<Interval> intervals)
           
 
Method Summary
 void add(int el)
          Add a single element to the set.
protected  void add(Interval addition)
           
 void add(int a, int b)
          Add interval; i.e., add all integers from a to b to set.
 void addAll(IntSet set)
          Add all elements from incoming set to this set.
 IntSet and(IntSet other)
          Return a new set with the intersection of this set with other.
 IntSet complement(int minElement, int maxElement)
           
 IntSet complement(IntSet vocabulary)
          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.
 boolean equals(java.lang.Object obj)
          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.
 int get(int i)
          Get the ith element of ordered set.
 java.util.List<Interval> getIntervals()
          Return a list of Interval objects.
 int getMaxElement()
           
 int getMinElement()
          Return minimum element >= 0
 int getSingleElement()
          If this set is a single integer, return it otherwise Label.INVALID
 boolean isNil()
          return true if this set has no members
 boolean member(int el)
          Is el in any range of this set?
static IntervalSet of(int a)
          Create a set with a single element, el.
static IntervalSet of(int a, int b)
          Create a set with all ints within range [a..b] (inclusive)
 IntSet or(IntSet a)
          TODO: implement this!
 void remove(int el)
          remove this element from this set
 int size()
          Return the size of this set (not the underlying implementation's allocated memory size, for example).
 IntSet subtract(IntSet other)
          Compute this-other via this&~other.
 int[] toArray()
           
 java.util.List toList()
           
 BitSet toRuntimeBitSet()
           
 java.lang.String toString()
           
 java.lang.String toString(Grammar g)
           
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

COMPLETE_SET

public static final IntervalSet COMPLETE_SET

intervals

protected java.util.List<Interval> intervals
The list of sorted, disjoint intervals.

Constructor Detail

IntervalSet

public IntervalSet()
Create a set with no elements


IntervalSet

public IntervalSet(java.util.List<Interval> intervals)
Method Detail

of

public static IntervalSet of(int a)
Create a set with a single element, el.


of

public static IntervalSet of(int a,
                             int b)
Create a set with all ints within range [a..b] (inclusive)


add

public void add(int el)
Add a single element to the set. An isolated element is stored as a range el..el.

Specified by:
add in interface IntSet

add

public void add(int a,
                int b)
Add interval; i.e., add all integers from a to b to set. If b

add

protected void add(Interval addition)

addAll

public void addAll(IntSet set)
Description copied from interface: IntSet
Add all elements from incoming set to this set. Can limit to set of its own type.

Specified by:
addAll in interface IntSet

complement

public IntSet complement(int minElement,
                         int maxElement)

complement

public IntSet complement(IntSet vocabulary)
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.

Specified by:
complement in interface IntSet

subtract

public IntSet subtract(IntSet other)
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.

Specified by:
subtract in interface IntSet

or

public IntSet or(IntSet a)
TODO: implement this!

Specified by:
or in interface IntSet

and

public IntSet and(IntSet other)
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.

Specified by:
and in interface IntSet

member

public boolean member(int el)
Is el in any range of this set?

Specified by:
member in interface IntSet

isNil

public boolean isNil()
return true if this set has no members

Specified by:
isNil in interface IntSet

getSingleElement

public int getSingleElement()
If this set is a single integer, return it otherwise Label.INVALID

Specified by:
getSingleElement in interface IntSet

getMaxElement

public int getMaxElement()

getMinElement

public int getMinElement()
Return minimum element >= 0


getIntervals

public java.util.List<Interval> getIntervals()
Return a list of Interval objects.


equals

public boolean equals(java.lang.Object obj)
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.

Specified by:
equals in interface IntSet
Overrides:
equals in class java.lang.Object

toString

public java.lang.String toString()
Specified by:
toString in interface IntSet
Overrides:
toString in class java.lang.Object

toString

public java.lang.String toString(Grammar g)
Specified by:
toString in interface IntSet

size

public int size()
Description copied from interface: IntSet
Return the size of this set (not the underlying implementation's allocated memory size, for example).

Specified by:
size in interface IntSet

toList

public java.util.List toList()
Specified by:
toList in interface IntSet

get

public int get(int i)
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.


toArray

public int[] toArray()

toRuntimeBitSet

public BitSet toRuntimeBitSet()

remove

public void remove(int el)
Description copied from interface: IntSet
remove this element from this set

Specified by:
remove in interface IntSet


Copyright © 2013. All Rights Reserved.