Class IntervalSet

java.lang.Object
org.antlr.v4.runtime.misc.IntervalSet
All Implemented Interfaces:
IntSet

public class IntervalSet extends Object implements IntSet
This class implements the IntSet backed by a sorted array of non-overlapping intervals. It is particularly efficient for representing large collections of numbers, where the majority of elements appear as part of a sequential range of numbers that are all part of the set. For example, the set { 1, 2, 3, 4, 7, 8 } may be represented as { [1, 4], [7, 8] }.

This class is able to represent sets containing any combination of values in the range Integer.MIN_VALUE to Integer.MAX_VALUE (inclusive).

  • Field Details

    • COMPLETE_CHAR_SET

      public static final IntervalSet COMPLETE_CHAR_SET
    • EMPTY_SET

      public static final IntervalSet EMPTY_SET
    • intervals

      protected List<Interval> intervals
      The list of sorted, disjoint intervals.
    • readonly

      protected boolean readonly
  • Constructor Details

    • IntervalSet

      public IntervalSet(List<Interval> intervals)
    • IntervalSet

      public IntervalSet(IntervalSet set)
    • IntervalSet

      public IntervalSet(int... els)
  • Method Details

    • 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)
    • clear

      public void clear()
    • 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
      Parameters:
      el - the value to add
    • add

      public void add(int a, int b)
      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}.
    • add

      protected void add(Interval addition)
    • or

      public static IntervalSet or(IntervalSet[] sets)
      combine all sets in the array returned the or'd value
    • addAll

      public IntervalSet addAll(IntSet set)
      Description copied from interface: IntSet
      Modify the current IntSet object to contain all elements that are present in itself, the specified set, or both.
      Specified by:
      addAll in interface IntSet
      Parameters:
      set - The set to add to the current set. A null argument is treated as though it were an empty set.
      Returns:
      this (to support chained calls)
    • complement

      public IntervalSet complement(int minElement, int maxElement)
    • complement

      public IntervalSet complement(IntSet vocabulary)
      Return a new IntSet object containing all elements that are present in elements but not present in the current set. The following expressions are equivalent for input non-null IntSet instances x and y.
      • x.complement(y)
      • y.subtract(x)
      Specified by:
      complement in interface IntSet
      Parameters:
      vocabulary - The set to compare with the current set. A null argument is treated as though it were an empty set.
      Returns:
      A new IntSet instance containing the elements present in elements but not present in the current set. The value null may be returned in place of an empty result set.
    • subtract

      public IntervalSet subtract(IntSet a)
      Description copied from interface: IntSet
      Return a new IntSet object containing all elements that are present in the current set but not present in the input set a. The following expressions are equivalent for input non-null IntSet instances x and y.
      • y.subtract(x)
      • x.complement(y)
      Specified by:
      subtract in interface IntSet
      Parameters:
      a - The set to compare with the current set. A null argument is treated as though it were an empty set.
      Returns:
      A new IntSet instance containing the elements present in elements but not present in the current set. The value null may be returned in place of an empty result set.
    • subtract

      public static IntervalSet subtract(IntervalSet left, IntervalSet right)
      Compute the set difference between two interval sets. The specific operation is left - right. If either of the input sets is null, it is treated as though it was an empty set.
    • or

      public IntervalSet or(IntSet a)
      Description copied from interface: IntSet
      Return a new IntSet object containing all elements that are present in the current set, the specified set a, or both.

      This method is similar to IntSet.addAll(IntSet), but returns a new IntSet instance instead of modifying the current set.

      Specified by:
      or in interface IntSet
      Parameters:
      a - The set to union with the current set. A null argument is treated as though it were an empty set.
      Returns:
      A new IntSet instance containing the union of the current set and a. The value null may be returned in place of an empty result set.
    • and

      public IntervalSet and(IntSet other)
      Return a new IntSet object containing all elements that are present in both the current set and the specified set a.
      Specified by:
      and in interface IntSet
      Parameters:
      other - The set to intersect with the current set. A null argument is treated as though it were an empty set.
      Returns:
      A new IntSet instance containing the intersection of the current set and a. The value null may be returned in place of an empty result set.
    • contains

      public boolean contains(int el)
      Returns true if the set contains the specified element.
      Specified by:
      contains in interface IntSet
      Parameters:
      el - The element to check for.
      Returns:
      true if the set contains el; otherwise false.
    • isNil

      public boolean isNil()
      Returns true if this set contains no elements.
      Specified by:
      isNil in interface IntSet
      Returns:
      true if the current set contains no elements; otherwise, false.
    • getMaxElement

      public int getMaxElement()
      Returns the maximum value contained in the set if not isNil().
      Returns:
      the maximum value contained in the set.
      Throws:
      RuntimeException - if set is empty
    • getMinElement

      public int getMinElement()
      Returns the minimum value contained in the set if not isNil().
      Returns:
      the minimum value contained in the set.
      Throws:
      RuntimeException - if set is empty
    • getIntervals

      public List<Interval> getIntervals()
      Return a list of Interval objects.
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object
    • equals

      public boolean equals(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 Object
    • toString

      public String toString()
      Description copied from interface: IntSet
      Specified by:
      toString in interface IntSet
      Overrides:
      toString in class Object
    • toString

      public String toString(boolean elemAreChar)
    • toString

      @Deprecated public String toString(String[] tokenNames)
      Deprecated.
    • toString

      public String toString(Vocabulary vocabulary)
    • elementName

      @Deprecated protected String elementName(String[] tokenNames, int a)
      Deprecated.
    • elementName

      protected String elementName(Vocabulary vocabulary, int a)
    • size

      public int size()
      Description copied from interface: IntSet
      Return the total number of elements represented by the current set.
      Specified by:
      size in interface IntSet
      Returns:
      the total number of elements represented by the current set, regardless of the manner in which the elements are stored.
    • toIntegerList

      public IntegerList toIntegerList()
    • toList

      public List<Integer> toList()
      Description copied from interface: IntSet
      Return a list containing the elements represented by the current set. The list is returned in ascending numerical order.
      Specified by:
      toList in interface IntSet
      Returns:
      A list containing all element present in the current set, sorted in ascending numerical order.
    • toSet

      public Set<Integer> toSet()
    • 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()
    • remove

      public void remove(int el)
      Description copied from interface: IntSet
      Removes the specified value from the current set. If the current set does not contain the element, no changes are made.
      Specified by:
      remove in interface IntSet
      Parameters:
      el - the value to remove
    • isReadonly

      public boolean isReadonly()
    • setReadonly

      public void setReadonly(boolean readonly)