org.apache.lucene.util.automaton
Class Automaton

java.lang.Object
  extended by 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:

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
static int MINIMIZE_HOPCROFT
          Minimize using Hopcroft's O(n log n) algorithm.
 
Constructor Summary
Automaton()
           
Automaton(State initial)
          Constructs a new automaton that accepts the empty language.
 
Method Summary
 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.



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