org.apache.lucene.util.automaton

## Class Automaton

- java.lang.Object
- - org.apache.lucene.util.automaton.Automaton

All Implemented Interfaces:
  Cloneable

    public class Automaton
    extends Object
    implements Cloneable

Finite-state automaton with regular expression operations.

Class invariants:

- An automaton is either represented explicitly (with `State` and `Transition` objects) or with a singleton string (see `getSingleton()` and `expandSingleton()`) in case the automaton is known to accept exactly one string. (Implicitly, all states and transitions of an automaton are reachable from its initial state.)
- Automata are always reduced (see `reduce()`) and have no transitions to dead states (see `removeDeadTransitions()`).
- If an automaton is nondeterministic, then `isDeterministic()` returns false (but the converse is not required).
- Automata provided as input to operations are generally assumed to be disjoint.

If the states or transitions are manipulated manually, the `restoreInvariant()` and `setDeterministic(boolean)` methods should be used afterwards to restore representation invariants that are assumed by the built-in automata operations.

Note: This class has internal mutable state and is not thread safe. It is the caller's responsibility to ensure any necessary synchronization if you wish to use the same Automaton from multiple threads. In general it is instead recommended to use a `RunAutomaton` for multithreaded matching: it is immutable, thread safe, and much faster.

WARNING: This API is experimental and might change in incompatible ways in the next release.

### Field Summary

Fields
`static int` `MINIMIZE_HOPCROFT` Minimize using Hopcroft's O(n log n) algorithm.

### Constructor Summary

Constructors
Constructor and Description
`Automaton()`
`Automaton(State initial)` Constructs a new automaton that accepts the empty language.

### Method Summary

Methods
`void` `clearNumberedStates()`
`Automaton` `clone()` Returns a clone of this automaton.
`Automaton` `complement()` See `BasicOperations.complement(Automaton)`.
`Automaton` `concatenate(Automaton a)` See `BasicOperations.concatenate(Automaton, Automaton)`.
`static Automaton` `concatenate(List<Automaton> l)` See `BasicOperations.concatenate(List)`.
`void` `determinize()` See `BasicOperations.determinize(Automaton)`.
`boolean` `equals(Object obj)`
`void` `expandSingleton()` Expands singleton representation to normal representation.
`Set<State>` `getAcceptStates()` Returns the set of reachable accept states.
`Object` `getInfo()` Returns extra information associated with this automaton.
`State` `getInitialState()` Gets initial state.
`State[]` `getNumberedStates()`
`int` `getNumberOfStates()` Returns the number of states in this automaton.
`int` `getNumberOfTransitions()` Returns the number of transitions in this automaton.
`String` `getSingleton()` Returns the singleton string for this automaton.
`Transition[][]` `getSortedTransitions()` Returns a sorted array of transitions for each state (and sets state numbers).
`int` `hashCode()`
`Automaton` `intersection(Automaton a)` See `BasicOperations.intersection(Automaton, Automaton)`.
`boolean` `isDeterministic()` Returns deterministic flag for this automaton.
`boolean` `isEmptyString()` See `BasicOperations.isEmptyString(Automaton)`.
`static Automaton` `minimize(Automaton a)` See `MinimizationOperations.minimize(Automaton)`.
`Automaton` `minus(Automaton a)` See `BasicOperations.minus(Automaton, Automaton)`.
`Automaton` `optional()` See `BasicOperations.optional(Automaton)`.
`void` `reduce()` Reduces this automaton.
`void` `removeDeadTransitions()` Removes transitions to dead states and calls `reduce()`.
`Automaton` `repeat()` See `BasicOperations.repeat(Automaton)`.
`Automaton` `repeat(int min)` See `BasicOperations.repeat(Automaton, int)`.
`Automaton` `repeat(int min, int max)` See `BasicOperations.repeat(Automaton, int, int)`.
`void` `restoreInvariant()` Restores representation invariant.
`static boolean` `setAllowMutate(boolean flag)` Sets or resets allow mutate flag.
`void` `setDeterministic(boolean deterministic)` Sets deterministic flag for this automaton.
`void` `setInfo(Object info)` Associates extra information with this automaton.
`static void` `setMinimization(int algorithm)` Selects minimization algorithm (default: `MINIMIZE_HOPCROFT`).
`static void` `setMinimizeAlways(boolean flag)` Sets or resets minimize always flag.
`void` `setNumberedStates(State[] states)`
`void` `setNumberedStates(State[] states, int count)`
`boolean` `subsetOf(Automaton a)` See `BasicOperations.subsetOf(Automaton, Automaton)`.
`String` `toDot()` Returns Graphviz Dot representation of this automaton.
`String` `toString()` Returns a string representation of this automaton.
`Automaton` `union(Automaton a)` See `BasicOperations.union(Automaton, Automaton)`.
`static Automaton` `union(Collection<Automaton> l)` See `BasicOperations.union(Collection)`.

### Methods inherited from class java.lang.Object

`finalize, getClass, notify, notifyAll, wait, wait, wait`

### Field Detail

#### MINIMIZE_HOPCROFT

    public static final int MINIMIZE_HOPCROFT

Minimize using Hopcroft's O(n log n) algorithm. This is regarded as one of the most generally efficient algorithms that exist.

See Also:
  `setMinimization(int)`, Constant Field Values

### Constructor Detail

#### Automaton

    public Automaton(State initial)

Constructs a new automaton that accepts the empty language. Using this constructor, automata can be constructed manually from `State` and `Transition` objects.

See Also:
  `State`, `Transition`

#### Automaton

    public Automaton()

### Method Detail

#### setMinimization

    public static void setMinimization(int algorithm)

Selects minimization algorithm (default: `MINIMIZE_HOPCROFT`).

Parameters:
  `algorithm` - minimization algorithm

#### setMinimizeAlways

    public static void setMinimizeAlways(boolean flag)

Sets or resets minimize always flag. If this flag is set, then `MinimizationOperations.minimize(Automaton)` will automatically be invoked after all operations that otherwise may produce non-minimal automata. By default, the flag is not set.

Parameters:
  `flag` - if true, the flag is set

#### setAllowMutate

    public static boolean setAllowMutate(boolean flag)

Sets or resets allow mutate flag. If this flag is set, then all automata operations may modify automata given as input; otherwise, operations will always leave input automata languages unmodified. By default, the flag is not set.

Parameters:
  `flag` - if true, the flag is set
Returns:
  previous value of the flag

#### getSingleton

    public String getSingleton()

Returns the singleton string for this automaton. An automaton that accepts exactly one string may be represented in singleton mode. In that case, this method may be used to obtain the string.

Returns:
  string, null if this automaton is not in singleton mode.

#### getInitialState

    public State getInitialState()

Gets initial state.

Returns:
  state

#### isDeterministic

    public boolean isDeterministic()

Returns deterministic flag for this automaton.

Returns:
  true if the automaton is definitely deterministic, false if the automaton may be nondeterministic

#### setDeterministic

    public void setDeterministic(boolean deterministic)

Sets deterministic flag for this automaton. This method should (only) be used if automata are constructed manually.

Parameters:
  `deterministic` - true if the automaton is definitely deterministic, false if the automaton may be nondeterministic

#### setInfo

    public void setInfo(Object info)

Associates extra information with this automaton.

Parameters:
  `info` - extra information

#### getInfo

    public Object getInfo()

Returns extra information associated with this automaton.

Returns:
  extra information
See Also:
  `setInfo(Object)`

#### getNumberedStates

    public State[] getNumberedStates()

#### setNumberedStates

    public void setNumberedStates(State[] states)

#### setNumberedStates

    public void setNumberedStates(State[] states,
                         int count)

#### clearNumberedStates

    public void clearNumberedStates()

#### getAcceptStates

    public Set<State> getAcceptStates()

Returns the set of reachable accept states.

Returns:
  set of `State` objects

#### restoreInvariant

    public void restoreInvariant()

Restores representation invariant. This method must be invoked before any built-in automata operation is performed if automaton states or transitions are manipulated manually.

See Also:
  `setDeterministic(boolean)`

#### reduce

    public void reduce()

Reduces this automaton. An automaton is "reduced" by combining overlapping and adjacent edge intervals with same destination.

#### removeDeadTransitions

    public void removeDeadTransitions()

Removes transitions to dead states and calls `reduce()`. (A state is "dead" if no accept state is reachable from it.)

#### getSortedTransitions

    public Transition[][] getSortedTransitions()

Returns a sorted array of transitions for each state (and sets state numbers).

#### expandSingleton

    public void expandSingleton()

Expands singleton representation to normal representation. Does nothing if not in singleton representation.

#### getNumberOfStates

    public int getNumberOfStates()

Returns the number of states in this automaton.

#### getNumberOfTransitions

    public int getNumberOfTransitions()

Returns the number of transitions in this automaton. This number is counted as the total number of edges, where one edge may be a character interval.

#### equals

    public boolean equals(Object obj)

Overrides:
  `equals` in class `Object`

#### hashCode

    public int hashCode()

Overrides:
  `hashCode` in class `Object`

#### toString

    public String toString()

Returns a string representation of this automaton.

Overrides:
  `toString` in class `Object`

#### toDot

    public String toDot()

Returns Graphviz Dot representation of this automaton.

#### clone

    public Automaton clone()

Returns a clone of this automaton.

Overrides:
  `clone` in class `Object`

#### concatenate

    public Automaton concatenate(Automaton a)

See `BasicOperations.concatenate(Automaton, Automaton)`.

#### concatenate

    public static Automaton concatenate(List<Automaton> l)

See `BasicOperations.concatenate(List)`.

#### optional

    public Automaton optional()

See `BasicOperations.optional(Automaton)`.

#### repeat

    public Automaton repeat()

See `BasicOperations.repeat(Automaton)`.

#### repeat

    public Automaton repeat(int min)

See `BasicOperations.repeat(Automaton, int)`.

#### repeat

    public Automaton repeat(int min,
                   int max)

See `BasicOperations.repeat(Automaton, int, int)`.

#### complement

    public Automaton complement()

See `BasicOperations.complement(Automaton)`.

#### minus

    public Automaton minus(Automaton a)

See `BasicOperations.minus(Automaton, Automaton)`.

#### intersection

    public Automaton intersection(Automaton a)

See `BasicOperations.intersection(Automaton, Automaton)`.

#### subsetOf

    public boolean subsetOf(Automaton a)

See `BasicOperations.subsetOf(Automaton, Automaton)`.

#### union

    public Automaton union(Automaton a)

See `BasicOperations.union(Automaton, Automaton)`.

#### union

    public static Automaton union(Collection<Automaton> l)

See `BasicOperations.union(Collection)`.

#### determinize

    public void determinize()

See `BasicOperations.determinize(Automaton)`.

#### isEmptyString

    public boolean isEmptyString()

See `BasicOperations.isEmptyString(Automaton)`.

#### minimize

    public static Automaton minimize(Automaton a)

See `MinimizationOperations.minimize(Automaton)`. Returns the automaton being given as argument.