Package jflex.state

Class StateSet

java.lang.Object
jflex.state.StateSet
All Implemented Interfaces:
Iterable<Integer>

public final class StateSet extends Object implements Iterable<Integer>
A set of NFA states (= ints).

Similar to BitSet, but tuned for sets of states. Can hold at most 2^64 elements, but is only useful for much smaller sets (ideally not more than tens of thousands).

Provides an Integer iterator and a native int enumerator.

Version:
JFlex 1.8.2
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) long[]
    Content of the StateSet, one bit per int, i.e.
    (package private) static final int
    2^BITS per word
    private final boolean
    Compile time DEBUG setting, local to StateSet
    static final StateSet
    The empty set of states
    (package private) static final int
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    Construct an empty StateSet with default memory backing.
    StateSet(int size)
    Construct an empty StateSet with specified memory backing.
    StateSet(int size, int state)
    Construct an StateSet with specified initial element and memory backing.
    Copy the specified StateSet to create a new one.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    Add all elements of the specified StateSet to this one.
    void
    addState(int state)
    Add an element (a state) to the set.
    void
    Remove all elements from this set.
    Returns the complement of this set with respect to the specified set, that is, the set of elements that are contained in the specified set but are not contained in this set.
    boolean
    Determine if the given set is a subset of this set.
    boolean
    Determine if the State set contains elements.
    Return a copy of this StateSet.
    void
    Copy specified StateSet into this.
    static StateSet
    emptySet(int length)
    Return a new StateSet of the specified length.
    boolean
     
    int
    Returns an element of the set and removes it.
    boolean
    hasElement(int state)
    Determine if a given state is an element of the set.
    int
     
    void
    Remove all states from this that are not contained in the provided StateSet.
    Construct an Integer iterator for this StateSet.
    (package private) static int
    nbits2size(int length)
    Compute a set size that will lead to an array of the given length.
    void
    remove(int state)
    Remove a given state from the set.
    private void
    resize(int size)
    Resize this set so it can hold at least size elements.
    (package private) static int
    size2nbits(int size)
    Compute the array size for a given set size.
    Construct an enumerator for this set.
     

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator
  • Field Details

    • DEBUG

      private final boolean DEBUG
      Compile time DEBUG setting, local to StateSet
      See Also:
    • EMPTY

      public static final StateSet EMPTY
      The empty set of states
    • BITS

      static final int BITS
      2^BITS per word
      See Also:
    • MASK

      static final int MASK
      See Also:
    • bits

      long[] bits
      Content of the StateSet, one bit per int, i.e. bit 0 of bits[0] stands for 0, bit 1 of bits[0] stands for 1, bit 1 of bits[1] stands for 65, etc.
  • Constructor Details

    • StateSet

      public StateSet()
      Construct an empty StateSet with default memory backing.
    • StateSet

      public StateSet(int size)
      Construct an empty StateSet with specified memory backing.
      Parameters:
      size - an int specifying the largest number this set will store. The StateSet will automatically resize of a larger number is added; specifying the size avoids re-allocation.
    • StateSet

      public StateSet(int size, int state)
      Construct an StateSet with specified initial element and memory backing.
      Parameters:
      size - an int specifying the largest number this set will store. The StateSet will automatically resize of a larger number is added; specifying the size avoids re-allocation.
      state - the element the set should contain.
    • StateSet

      public StateSet(StateSet set)
      Copy the specified StateSet to create a new one.
      Parameters:
      set - the StateSet object to copy.
  • Method Details

    • emptySet

      public static StateSet emptySet(int length)
      Return a new StateSet of the specified length.
    • addState

      public void addState(int state)
      Add an element (a state) to the set. Will automatically resize the set representation if necessary.
      Parameters:
      state - the element to add.
    • size2nbits

      static int size2nbits(int size)
      Compute the array size for a given set size.
      Parameters:
      size - the desired size of the set.
      Returns:
      an array size such that the set can hold at least size elements.
    • nbits2size

      static int nbits2size(int length)
      Compute a set size that will lead to an array of the given length.

      Precondition: length > 0 invalid input: '&'invalid input: '&' length invalid input: '<'= 2^58 (58=64-BITS)

      Parameters:
      length - desired length of the StateSet array
      Returns:
      an int val such that size2nbits(val) = length
    • resize

      private void resize(int size)
      Resize this set so it can hold at least size elements.
      Parameters:
      size - new maximum element
    • clear

      public void clear()
      Remove all elements from this set.
    • hasElement

      public boolean hasElement(int state)
      Determine if a given state is an element of the set.
      Parameters:
      state - the element to check for.
      Returns:
      true iff this set has the element state.
    • getAndRemoveElement

      public int getAndRemoveElement()
      Returns an element of the set and removes it.

      Precondition: the set is not empty.

      Returns:
      an element of the set.
    • remove

      public void remove(int state)
      Remove a given state from the set.
      Parameters:
      state - the element to remove.
    • intersect

      public void intersect(StateSet set)
      Remove all states from this that are not contained in the provided StateSet.
      Parameters:
      set - the StateSet object to intersect with.
    • complement

      public StateSet complement(StateSet univ)
      Returns the complement of this set with respect to the specified set, that is, the set of elements that are contained in the specified set but are not contained in this set.

      Does not change this set.

      Parameters:
      univ - the StateSet that determines which elements can at most be returned.
      Returns:
      the StateSet that contains all elements of univ that are not in this set.
    • add

      public void add(StateSet set)
      Add all elements of the specified StateSet to this one.
      Parameters:
      set - a StateSet object to be added.
    • equals

      public boolean equals(Object b)
      Overrides:
      equals in class Object
    • hashCode

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

      public StateSetEnumerator states()
      Construct an enumerator for this set.
      Returns:
      a StateSetEnumerator object for this set.
    • containsElements

      public boolean containsElements()
      Determine if the State set contains elements.
      Returns:
      true iff the set is not empty.
    • contains

      public boolean contains(StateSet set)
      Determine if the given set is a subset of this set.
      Parameters:
      set - the set to check containment of
      Returns:
      true iff set is contained in this set.
    • copy

      public StateSet copy()
      Return a copy of this StateSet.
      Returns:
      a StateSet object with the same content as this.
    • copy

      public void copy(StateSet set)
      Copy specified StateSet into this.
      Parameters:
      set - the state set to copy.
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • iterator

      public Iterator<Integer> iterator()
      Construct an Integer iterator for this StateSet.
      Specified by:
      iterator in interface Iterable<Integer>
      Returns:
      an iterator for this StateSet.