com.nobigsoftware.dfalex

Class DfaAuxiliaryInformation<MATCHRESULT>

java.lang.Object

com.nobigsoftware.dfalex.DfaAuxiliaryInformation<MATCHRESULT>

public class DfaAuxiliaryInformation<MATCHRESULT>
extends java.lang.Object

Utility class to calculate various auxiliary information about DFAs.

An instance of this class is created with a set of start states, which all the other methods of this class will calculate information about.

Unless otherwise noted, the methods of this class all operated in linear time or better.

Use one instance of this class to calculate everything you need. It will remember results you ask for and reuse them for other calculations when required.

Constructor Summary

Constructors

Constructor and Description
DfaAuxiliaryInformation(java.util.Collection<DfaState<MATCHRESULT>> startStates) Create a new DfaAuxiliaryInformation.

Method Summary

Modifier and Type	Method and Description
void	depthFirstSearch(java.util.function.BiConsumer<DfaState<MATCHRESULT>,DfaState<MATCHRESULT>> onEnter, java.util.function.BiConsumer<DfaState<MATCHRESULT>,DfaState<MATCHRESULT>> onSkip, java.util.function.BiConsumer<DfaState<MATCHRESULT>,DfaState<MATCHRESULT>> onLeave) Perform a depth first search of all states, starting at the start states
int[]	getCycleNumbers() Get an array that maps each state number to the state's 'cycle number', such that: States that are not in a cycle have cycle number -1 States that are in a cycle have cycle number >= 0 States in cycles have the same cycle number IFF they are in the same cycle (i.e., they are reachable from each other) Cycles are compactly numbered from 0 Note that states with cycle numbers >=0 match an infinite number of different strings, while states with cycle number -1 match a finite number of strings with lengths <= the size of this array.
java.util.List<MATCHRESULT>	getDestinies() Get a list that maps each state number to the state's "destiny"
java.util.List<DfaState<MATCHRESULT>>	getStatesByNumber() Get a list of all states reachable from the start states.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DfaAuxiliaryInformation

public DfaAuxiliaryInformation(java.util.Collection<DfaState<MATCHRESULT>> startStates)

Create a new DfaAuxiliaryInformation.

Parameters:

startStates - A collection of start states returned by a single call to DfaBuilder. The states must have been returned by a single call, so that the state numbers of all states they reach will be unique. Methods of this class will calculate various information about these states

Method Detail

getStatesByNumber

public java.util.List<DfaState<MATCHRESULT>> getStatesByNumber()

Get a list of all states reachable from the start states.

Multiple calls to this method will return the same list.

Returns:

a list that contains every state reachable from the start states, with the index of each state s equal to s.getStateNumber(). Unused indexes will have null values.

depthFirstSearch

public void depthFirstSearch(java.util.function.BiConsumer<DfaState<MATCHRESULT>,DfaState<MATCHRESULT>> onEnter,
                             java.util.function.BiConsumer<DfaState<MATCHRESULT>,DfaState<MATCHRESULT>> onSkip,
                             java.util.function.BiConsumer<DfaState<MATCHRESULT>,DfaState<MATCHRESULT>> onLeave)

Perform a depth first search of all states, starting at the start states

To avoid stack overflow errors on large DFAs, the implementation uses an auxiliary stack on the heap instead of recursing

Parameters:

onEnter - called with (parent, child) when a child is entered. parent == null for roots.

onSkip - called with (parent, child) when a child is skipped because it has been entered previously. exited. parent == null for roots.

onLeave - called with (parent, child) when a child is exited. parent == null for roots.

getCycleNumbers

public int[] getCycleNumbers()

Get an array that maps each state number to the state's 'cycle number', such that:

• States that are not in a cycle have cycle number -1
• States that are in a cycle have cycle number >= 0
• States in cycles have the same cycle number IFF they are in the same cycle (i.e., they are reachable from each other)
• Cycles are compactly numbered from 0

Note that states with cycle numbers >=0 match an infinite number of different strings, while states with cycle number -1 match a finite number of strings with lengths <= the size of this array.

Returns:

the cycle numbers array

getDestinies

public java.util.List<MATCHRESULT> getDestinies()

Get a list that maps each state number to the state's "destiny"

If all strings accepted by the state produce the same MATCHRESULT, then that MATCHRESULT is the state's destiny. Otherwise the state's destiny is null.

Returns:

The list of destinies by state number