public class Automaton extends java.lang.Object implements Accountable
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).Modifier and Type | Class and Description |
---|---|
static class |
Automaton.Builder
Records new states and transitions and then
Automaton.Builder.finish() creates the Automaton . |
Modifier and Type | Field and Description |
---|---|
private int |
curState
Current state we are adding transitions to; the caller
must add all transitions for this state before moving
onto another state.
|
private Sorter |
destMinMaxSorter
Sorts transitions by dest, ascending, then min label ascending, then max label ascending
|
private boolean |
deterministic
True if no state has two transitions leaving with the same label.
|
private java.util.BitSet |
isAccept |
private Sorter |
minMaxDestSorter
Sorts transitions by min label, ascending, then max label ascending, then dest ascending
|
private int |
nextState
Where we next write to the int[] states; this increments by 2 for
each added state because we pack a pointer to the transitions
array and a count of how many transitions leave the state.
|
private int |
nextTransition
Where we next write to in int[] transitions; this
increments by 3 for each added transition because we
pack min, max, dest in sequence.
|
private int[] |
states
Index in the transitions array, where this states
leaving transitions are stored, or -1 if this state
has not added any transitions yet, followed by number
of transitions.
|
private int[] |
transitions
Holds toState, min, max for each transition.
|
Constructor and 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.
|
Modifier and Type | Method and Description |
---|---|
void |
addEpsilon(int source,
int dest)
Add a [virtual] epsilon transition between source and dest.
|
void |
addTransition(int source,
int dest,
int label)
Add a new transition with min = max = label.
|
void |
addTransition(int source,
int dest,
int min,
int max)
Add a new transition with the specified source, dest, min, max.
|
(package private) static void |
appendCharString(int c,
java.lang.StringBuilder b) |
void |
copy(Automaton other)
Copies over all states/transitions from other.
|
int |
createState()
Create a new state.
|
private void |
finishCurrentState()
Freezes the last state, sorting and reducing the transitions.
|
void |
finishState()
Finishes the current state; call this once you are done adding
transitions for a state.
|
(package private) java.util.BitSet |
getAcceptStates()
Returns accept states.
|
void |
getNextTransition(Transition t)
Iterate to the next transition after the provided one
|
int |
getNumStates()
How many states this automaton has.
|
int |
getNumTransitions()
How many transitions this automaton has.
|
int |
getNumTransitions(int state)
How many transitions this state has.
|
Transition[][] |
getSortedTransitions()
Sugar to get all transitions for all states.
|
(package private) int[] |
getStartPoints()
Returns sorted array of all interval start points.
|
void |
getTransition(int state,
int index,
Transition t)
Fill the provided
Transition with the index'th
transition leaving the specified state. |
private void |
growStates() |
private void |
growTransitions() |
int |
initTransition(int state,
Transition t)
Initialize the provided Transition to iterate through all transitions
leaving the specified state.
|
boolean |
isAccept(int state)
Returns true if this state is an accept state.
|
boolean |
isDeterministic()
Returns true if this automaton is deterministic (for ever state
there is only one transition for each label).
|
long |
ramBytesUsed()
Return the memory usage of this object in bytes.
|
void |
setAccept(int state,
boolean accept)
Set or clear this state as an accept state.
|
int |
step(int state,
int label)
Performs lookup in transitions, assuming determinism.
|
java.lang.String |
toDot()
Returns the dot (graphviz) representation of this automaton.
|
private boolean |
transitionSorted(Transition t) |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getChildResources
private int nextState
private int nextTransition
private int curState
private int[] states
private final java.util.BitSet isAccept
private int[] transitions
private boolean deterministic
private final Sorter destMinMaxSorter
private final Sorter minMaxDestSorter
public Automaton()
public Automaton(int numStates, int numTransitions)
numStates
- Number of states.numTransitions
- Number of transitions.public int createState()
public void setAccept(int state, boolean accept)
public Transition[][] getSortedTransitions()
java.util.BitSet getAcceptStates()
public boolean isAccept(int state)
public void addTransition(int source, int dest, int label)
public void addTransition(int source, int dest, int min, int max)
public void addEpsilon(int source, int dest)
public void copy(Automaton other)
private void finishCurrentState()
public boolean isDeterministic()
public void finishState()
public int getNumStates()
public int getNumTransitions()
public int getNumTransitions(int state)
private void growStates()
private void growTransitions()
public int initTransition(int state, Transition t)
getNextTransition(org.apache.lucene.util.automaton.Transition)
to
get each transition. Returns the number of transitions
leaving this state.public void getNextTransition(Transition t)
private boolean transitionSorted(Transition t)
public void getTransition(int state, int index, Transition t)
Transition
with the index'th
transition leaving the specified state.static void appendCharString(int c, java.lang.StringBuilder b)
public java.lang.String toDot()
int[] getStartPoints()
public int step(int state, int label)
state
- starting statelabel
- codepoint to look uppublic long ramBytesUsed()
Accountable
ramBytesUsed
in interface Accountable