org.apache.lucene.util.automaton

## Class Automaton

- java.lang.Object
- - org.apache.lucene.util.automaton.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.

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `Automaton.Builder` Records new states and transitions and then `Automaton.Builder.finish()` creates the `Automaton`.

  - ### Field Summary

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

      `NULL_ACCOUNTABLE`

  - ### Constructor Summary

    Constructors
    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.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    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.
    `void` | `copy(Automaton other)` Copies over all states/transitions from other.
    `int` | `createState()` Create a new state.
    `void` | `finishState()` Finishes the current state; call this once you are done adding transitions for a state.
    `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.
    `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 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).
    `int` | `next(Transition transition, int label)` Looks for the next transition that matches the provided label, assuming determinism.
    `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.
    `String` | `toDot()` Returns the dot (graphviz) representation of this automaton.

    - ### 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`

- - ### 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.

    - #### initTransition

          public int initTransition(int state,
                                    Transition t)

      Initialize the provided Transition to iterate through all transitions leaving the specified state. You must call `getNextTransition(org.apache.lucene.util.automaton.Transition)` to get each transition. Returns the number of transitions leaving this state.

    - #### 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

    - #### next

          public int next(Transition transition,
                          int label)

      Looks for the next transition that matches the provided label, assuming determinism.

      This method is similar to `step(int, int)` but is used more efficiently when iterating over multiple transitions from the same source state. It keeps the latest reached transition index in `transition.transitionUpto` so the next call to this method can continue from there instead of restarting from the first transition.

      Parameters:
        `transition` - The transition to start the lookup from (inclusive, using its `Transition.source` and `Transition.transitionUpto`). It is updated with the matched transition; or with `Transition.dest` = -1 if no match.
        `label` - The codepoint to look up.
      Returns:
        The destination state; or -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`

Copyright © 2000-2024 Apache Software Foundation. All Rights Reserved.