Module org.apache.lucene.core

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	NFARunAutomaton.DState

Field Summary

Fields

Modifier and Type	Field	Description
private final int	alphabetSize
private final Automaton	automaton
private static final long	BASE_RAM_BYTES
(package private) final int[]	classmap
private NFARunAutomaton.DState[]	dStates
private final Map<NFARunAutomaton.DState,Integer>	dStateToOrd
private static final int	MISSING	state ordinal of "no such state"
private static final int	NOT_COMPUTED
private final int[]	points
private final StateSet	statesSet
private final Operations.PointTransitionSet	transitionSet

Fields inherited from interface org.apache.lucene.util.Accountable

NULL_ACCOUNTABLE

Constructor Summary

Constructors

Constructor	Description
NFARunAutomaton(Automaton automaton)	Constructor, assuming alphabet size is the whole Unicode code point space
NFARunAutomaton(Automaton automaton, int alphabetSize)	Constructor

Method Summary

Modifier and Type	Method	Description
private 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 codepoint
void	getNextTransition(Transition t)	Iterate to the next transition after the provided one
int	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 NFA
void	getTransition(int state, int index, Transition t)	Fill the provided Transition 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	ramBytesUsed()	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 test
private void	setTransitionAccordingly(Transition t)
int	step(int state, int c)	For a given state and an incoming character (codepoint), return the next state
private 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 call NFARunAutomaton.DState.step(int) to get the next state and cache the result

Methods 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 MISSING

state ordinal of "no such state"

See Also:

• Constant Field Values

NOT_COMPUTED

private static final int NOT_COMPUTED

See Also:

• Constant Field Values

BASE_RAM_BYTES

private static final long BASE_RAM_BYTES

automaton

private final Automaton automaton

points

private final int[] points

dStateToOrd

private final Map<NFARunAutomaton.DState,Integer> dStateToOrd

dStates

private NFARunAutomaton.DState[] dStates

alphabetSize

private final int alphabetSize

classmap

final int[] classmap

transitionSet

private final Operations.PointTransitionSet transitionSet

statesSet

private final StateSet statesSet

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

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

private 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 call NFARunAutomaton.DState.step(int) to get the next state and cache the result

findDState

private 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

getCharClass

final int getCharClass(int c)

Gets character class of given codepoint

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

setTransitionAccordingly

private void setTransitionAccordingly(Transition t)

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