Package org.apache.lucene.util.automaton

Class NFARunAutomaton

java.lang.Object
org.apache.lucene.util.automaton.NFARunAutomaton
All Implemented Interfaces:
Accountable, ByteRunnable, TransitionAccessor
public class NFARunAutomaton extends Object implements ByteRunnable, TransitionAccessor, Accountable
A RunAutomaton that does not require DFA. It will lazily determinize on-demand, memorizing the generated DFA states that has been explored. Note: the current implementation is NOT thread-safe

implemented based on: https://swtch.com/~rsc/regexp/regexp1.html

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

  • Constructor Details

    • NFARunAutomaton

      public NFARunAutomaton(Automaton automaton)
      Constructor, assuming alphabet size is the whole Unicode code point space
      Parameters:
      automaton - incoming automaton, should be NFA, for DFA please use RunAutomaton for better efficiency

    • NFARunAutomaton

      public NFARunAutomaton(Automaton automaton, int alphabetSize)
      Constructor
      Parameters:
      automaton - incoming automaton, should be NFA, for DFA please use RunAutomaton * for better efficiency
      alphabetSize - alphabet size

  • Method Details

    • step

      public int step(int state, int c)
      For a given state and an incoming character (codepoint), return the next state
      Specified by:
      step in interface ByteRunnable
      Parameters:
      state - incoming state, should either be 0 or some state that is returned previously by this function
      c - codepoint
      Returns:
      the next state or MISSING if the transition doesn't exist

    • isAccept

      public boolean isAccept(int state)
      Description copied from interface: ByteRunnable
      Returns acceptance status for given state.
      Specified by:
      isAccept in interface ByteRunnable
      Parameters:
      state - the state
      Returns:
      whether the state is accepted

    • getSize

      public int getSize()
      Description copied from interface: ByteRunnable
      Returns number of states this automaton has, note this may not be an accurate number in case of NFA
      Specified by:
      getSize in interface ByteRunnable
      Returns:
      number of states

    • initTransition

      public int initTransition(int state, Transition t)
      Description copied from interface: TransitionAccessor
      Initialize the provided Transition to iterate through all transitions leaving the specified state. You must call TransitionAccessor.getNextTransition(org.apache.lucene.util.automaton.Transition) to get each transition. Returns the number of transitions leaving this state.
      Specified by:
      initTransition in interface TransitionAccessor

    • getNextTransition

      public void getNextTransition(Transition t)
      Description copied from interface: TransitionAccessor
      Iterate to the next transition after the provided one
      Specified by:
      getNextTransition in interface TransitionAccessor

    • getNumTransitions

      public int getNumTransitions(int state)
      Description copied from interface: TransitionAccessor
      How many transitions this state has.
      Specified by:
      getNumTransitions in interface TransitionAccessor

    • getTransition

      public void getTransition(int state, int index, Transition t)
      Description copied from interface: TransitionAccessor
      Fill the provided Transition with the index'th transition leaving the specified state.
      Specified by:
      getTransition in interface TransitionAccessor

    • 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