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
-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final int
private final Automaton
private static final long
(package private) final int[]
private NFARunAutomaton.DState[]
private final Map
<NFARunAutomaton.DState, Integer> private static final int
state ordinal of "no such state"private static final int
private final int[]
private final StateSet
private final Operations.PointTransitionSet
Fields inherited from interface org.apache.lucene.util.Accountable
NULL_ACCOUNTABLE
-
Constructor Summary
ConstructorsConstructorDescriptionNFARunAutomaton
(Automaton automaton) Constructor, assuming alphabet size is the whole Unicode code point spaceNFARunAutomaton
(Automaton automaton, int alphabetSize) Constructor -
Method Summary
Modifier and TypeMethodDescriptionprivate int
findDState
(NFARunAutomaton.DState dState) return the ordinal of given DFA state, generate a new ordinal if the given DFA state is a new one(package private) final int
getCharClass
(int c) Gets character class of given codepointvoid
Iterate to the next transition after the provided oneint
getNumTransitions
(int state) How many transitions this state has.int
getSize()
Returns number of states this automaton has, note this may not be an accurate number in case of NFAvoid
getTransition
(int state, int index, Transition t) Fill the providedTransition
with the index'th transition leaving the specified state.int
initTransition
(int state, Transition t) Initialize the provided Transition to iterate through all transitions leaving the specified state.boolean
isAccept
(int state) Returns acceptance status for given state.long
Return the memory usage of this object in bytes.(package private) boolean
run
(int[] s) Run through a given codepoint array, return accepted or not, should only be used in testprivate void
int
step
(int state, int c) For a given state and an incoming character (codepoint), return the next stateprivate int
step
(NFARunAutomaton.DState dState, int c) From an existing DFA state, step to next DFA state given character c if the transition is previously tried then this operation will just use the cached result, otherwise it will callNFARunAutomaton.DState.step(int)
to get the next state and cache the resultMethods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.apache.lucene.util.Accountable
getChildResources
Methods inherited from interface org.apache.lucene.util.automaton.ByteRunnable
run
-
Field Details
-
MISSING
private static final int MISSINGstate ordinal of "no such state"- See Also:
-
NOT_COMPUTED
private static final int NOT_COMPUTED- See Also:
-
BASE_RAM_BYTES
private static final long BASE_RAM_BYTES -
automaton
-
points
private final int[] points -
dStateToOrd
-
dStates
-
alphabetSize
private final int alphabetSize -
classmap
final int[] classmap -
transitionSet
-
statesSet
-
-
Constructor Details
-
NFARunAutomaton
Constructor, assuming alphabet size is the whole Unicode code point space- Parameters:
automaton
- incoming automaton, should be NFA, for DFA please useRunAutomaton
for better efficiency
-
NFARunAutomaton
Constructor- Parameters:
automaton
- incoming automaton, should be NFA, for DFA please useRunAutomaton
* for better efficiencyalphabetSize
- 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 interfaceByteRunnable
- Parameters:
state
- incoming state, should either be 0 or some state that is returned previously by this functionc
- 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 interfaceByteRunnable
- 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 interfaceByteRunnable
- Returns:
- number of states
-
run
boolean run(int[] s) Run through a given codepoint array, return accepted or not, should only be used in test- Parameters:
s
- String represented by an int array- Returns:
- accept or not
-
step
From an existing DFA state, step to next DFA state given character c if the transition is previously tried then this operation will just use the cached result, otherwise it will callNFARunAutomaton.DState.step(int)
to get the next state and cache the result -
findDState
return the ordinal of given DFA state, generate a new ordinal if the given DFA state is a new one -
getCharClass
final int getCharClass(int c) Gets character class of given codepoint -
initTransition
Description copied from interface:TransitionAccessor
Initialize the provided Transition to iterate through all transitions leaving the specified state. You must callTransitionAccessor.getNextTransition(org.apache.lucene.util.automaton.Transition)
to get each transition. Returns the number of transitions leaving this state.- Specified by:
initTransition
in interfaceTransitionAccessor
-
getNextTransition
Description copied from interface:TransitionAccessor
Iterate to the next transition after the provided one- Specified by:
getNextTransition
in interfaceTransitionAccessor
-
setTransitionAccordingly
-
getNumTransitions
public int getNumTransitions(int state) Description copied from interface:TransitionAccessor
How many transitions this state has.- Specified by:
getNumTransitions
in interfaceTransitionAccessor
-
getTransition
Description copied from interface:TransitionAccessor
Fill the providedTransition
with the index'th transition leaving the specified state.- Specified by:
getTransition
in interfaceTransitionAccessor
-
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 interfaceAccountable
-