Package jflex.state

Class StateSet

  • All Implemented Interfaces:
    java.lang.Iterable<java.lang.Integer>

    public final class StateSet
    extends java.lang.Object
    implements java.lang.Iterable<java.lang.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:
    StateSetEnumerator
    • Field Summary

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

      Constructors 
      Constructor Description
      StateSet()
      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.
      StateSet​(StateSet set)
      Copy the specified StateSet to create a new one.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(StateSet set)
      Add all elements of the specified StateSet to this one.
      void addState​(int state)
      Add an element (a state) to the set.
      void clear()
      Remove all elements from this set.
      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.
      boolean contains​(StateSet set)
      Determine if the given set is a subset of this set.
      boolean containsElements()
      Determine if the State set contains elements.
      StateSet copy()
      Return a copy of this StateSet.
      void copy​(StateSet set)
      Copy specified StateSet into this.
      static StateSet emptySet​(int length)
      Return a new StateSet of the specified length.
      boolean equals​(java.lang.Object b)  
      int getAndRemoveElement()
      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 hashCode()  
      void intersect​(StateSet set)
      Remove all states from this that are not contained in the provided StateSet.
      java.util.Iterator<java.lang.Integer> iterator()
      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.
      StateSetEnumerator states()
      Construct an enumerator for this set.
      java.lang.String toString()  
      • 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 Detail

      • DEBUG

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

        public static final StateSet EMPTY
        The empty set of states
      • 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 Detail

      • 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 Detail

      • 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 && length <= 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​(java.lang.Object b)
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • 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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • iterator

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