Package org.apache.lucene.util.automaton

Class Automaton

  • All Implemented Interfaces:
    Accountable
    public class Automaton
extends Object
implements Accountable
    Represents an automaton and all its states and transitions. States are integers and must be created using createState(). Mark a state as an accept state using setAccept(int, boolean). Add transitions using addTransition(int, int, int). Each state must have all of its transitions added at once; if this is too restrictive then use Automaton.Builder instead. State 0 is always the initial state. Once a state is finished, either because you've starting adding transitions to another state or you call finishState(), then that states transitions are sorted (first by min, then max, then dest) and reduced (transitions with adjacent labels going to the same dest are combined).
    WARNING: This API is experimental and might change in incompatible ways in the next release.

    • Constructor Summary

      Constructors 
      Constructor Description
      Automaton()
      Sole constructor; creates an automaton with no states.
      Automaton​(int numStates, int numTransitions)
      Constructor which creates an automaton with enough space for the given number of states and transitions.

    • Constructor Detail

      • Automaton

        public Automaton()
        Sole constructor; creates an automaton with no states.

      • Automaton

        public Automaton​(int numStates,
                 int numTransitions)
        Constructor which creates an automaton with enough space for the given number of states and transitions.
        Parameters:
        numStates - Number of states.
        numTransitions - Number of transitions.

    • Method Detail

      • createState

        public int createState()
        Create a new state.

      • setAccept

        public void setAccept​(int state,
                      boolean accept)
        Set or clear this state as an accept state.

      • getSortedTransitions

        public Transition[][] getSortedTransitions()
        Sugar to get all transitions for all states. This is object-heavy; it's better to iterate state by state instead.

      • isAccept

        public boolean isAccept​(int state)
        Returns true if this state is an accept state.

      • addTransition

        public void addTransition​(int source,
                          int dest,
                          int label)
        Add a new transition with min = max = label.

      • addTransition

        public void addTransition​(int source,
                          int dest,
                          int min,
                          int max)
        Add a new transition with the specified source, dest, min, max.

      • addEpsilon

        public void addEpsilon​(int source,
                       int dest)
        Add a [virtual] epsilon transition between source and dest. Dest state must already have all transitions added because this method simply copies those same transitions over to source.

      • copy

        public void copy​(Automaton other)
        Copies over all states/transitions from other. The states numbers are sequentially assigned (appended).

      • isDeterministic

        public boolean isDeterministic()
        Returns true if this automaton is deterministic (for ever state there is only one transition for each label).

      • finishState

        public void finishState()
        Finishes the current state; call this once you are done adding transitions for a state. This is automatically called if you start adding transitions to a new source state, but for the last state you add you need to this method yourself.

      • getNumStates

        public int getNumStates()
        How many states this automaton has.

      • getNumTransitions

        public int getNumTransitions()
        How many transitions this automaton has.

      • getNumTransitions

        public int getNumTransitions​(int state)
        How many transitions this state has.

      • getNextTransition

        public void getNextTransition​(Transition t)
        Iterate to the next transition after the provided one

      • getTransition

        public void getTransition​(int state,
                          int index,
                          Transition t)
        Fill the provided Transition with the index'th transition leaving the specified state.

      • toDot

        public String toDot()
        Returns the dot (graphviz) representation of this automaton. This is extremely useful for visualizing the automaton.

      • step

        public int step​(int state,
                int label)
        Performs lookup in transitions, assuming determinism.
        Parameters:
        state - starting state
        label - codepoint to look up
        Returns:
        destination state, -1 if no matching outgoing transition

      • ramBytesUsed

        public long ramBytesUsed()
        Description copied from interface: Accountable
        Return the memory usage of this object in bytes. Negative values are illegal.
        Specified by:
        ramBytesUsed in interface Accountable