com.raffaeleconforti.kazennikov.dafsa

Class AbstractIntDAFSA

java.lang.Object

com.raffaeleconforti.kazennikov.dafsa.IntDaciukAlgoIndexed

com.raffaeleconforti.kazennikov.dafsa.AbstractIntDAFSA

Direct Known Subclasses:

IntDAFSAInt

public abstract class AbstractIntDAFSA
extends IntDaciukAlgoIndexed

Abstract DAFSA builder. It almost complete implementation, where only finality state data is missing. Main difference from previous implementations is that final value is stored in the DAFSA instead of the state. So one doesn't need to subclass the node state, instead one can implement it's own handling strategy for final values using abstract functions. Also, the finals are indexed by state number

Author:

Anton Kazennikov

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	AbstractIntDAFSA.State Basic FSA state.

Constructor Summary

Constructors

Constructor and Description
AbstractIntDAFSA()

Method Summary

Modifier and Type	Method and Description
int	addState() Adds a new state to the automaton
int	cloneState(int srcState) Clones given state.
static int	decodeDest(long val) Decode destination from the transition table value
static int	decodeLabel(long val) Decode label from the transition table value
static long	encodeTransition(int input, int next) Encode transition to table value
abstract void	finalAssign(int destState, int srcState) Copy final value from source state to destination state
abstract boolean	finalEquals(int state1, int state2) Check if final values of two states are equal
abstract int	finalHash(int state) Compute hash code for the final value of the state
abstract void	finalReset(int state) Reset the final value of the given state
int	getNext(int state, int input) Find matching outbound transition for given state
int	getStartState()
java.util.List<AbstractIntDAFSA.State>	getStates()
int	getTransitionCount(int state)
int	getTransitionInput(int state, int transitionIndex)
int	getTransitionNext(int state, int transitionIndex)
abstract void	initFinals() Initialize finality values for this FSA
boolean	isConfluence(int state) Checks a state for confluence (if in has more that 1 inbound transitions)
abstract boolean	isFinalState(int state) Checks if state is final
boolean	isSource(int stateNumber)
abstract void	newFinal(int state) Initialize final value for given state
void	regAdd(int state) Add state to register
int	regGet(int state) Get equivalent state from register
void	regRemove(int state) Remove given state from register.
void	removeState(int state) Removes given state from the automaton
boolean	setNext(int src, int label, int dest) Adds a transition from src to dest on given label, if a transition from src with given label already exists, then change it to new destination state.
int	size()
void	toDot(java.io.PrintWriter pw) Output this DAFSA to dot format
void	toDot(java.lang.String fileName)
int	transitionCount()

Methods inherited from class com.raffaeleconforti.kazennikov.dafsa.IntDaciukAlgoIndexed

add, addMinWord, addSuffix, hasFinal, replaceOrRegister, setFinal

Methods inherited from class java.lang.Object

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

Constructor Detail

AbstractIntDAFSA

public AbstractIntDAFSA()

Method Detail

decodeLabel

public static int decodeLabel(long val)

Decode label from the transition table value

Parameters:

val - transition table value

Returns:

decodeDest

public static int decodeDest(long val)

Decode destination from the transition table value

Parameters:

val - transition table value

Returns:

encodeTransition

public static long encodeTransition(int input,
                                    int next)

Encode transition to table value

Parameters:

input - input symbol

next - next state number

Returns:

regAdd

public void regAdd(int state)

Description copied from class: IntDaciukAlgoIndexed

Add state to register

Specified by:

regAdd in class IntDaciukAlgoIndexed

Parameters:

state - state number

regGet

public int regGet(int state)

Description copied from class: IntDaciukAlgoIndexed

Get equivalent state from register

Specified by:

regGet in class IntDaciukAlgoIndexed

Parameters:

state - reference state

Returns:

number of registered state, or -1 (INVALID_STATE) if no such state exist

regRemove

public void regRemove(int state)

Description copied from class: IntDaciukAlgoIndexed

Remove given state from register. Removes exact state not equivalent one.

Specified by:

regRemove in class IntDaciukAlgoIndexed

Parameters:

state - state to remove

getNext

public int getNext(int state,
                   int input)

Description copied from class: IntDaciukAlgoIndexed

Find matching outbound transition for given state

Specified by:

getNext in class IntDaciukAlgoIndexed

Parameters:

state - source state

input - label

Returns:

dest state, or -1, if no such transition exists

isConfluence

public boolean isConfluence(int state)

Description copied from class: IntDaciukAlgoIndexed

Checks a state for confluence (if in has more that 1 inbound transitions)

Specified by:

isConfluence in class IntDaciukAlgoIndexed

Parameters:

state - state to check

Returns:

true if state has more than one inbound transitions

cloneState

public int cloneState(int srcState)

Description copied from class: IntDaciukAlgoIndexed

Clones given state. It clones:

• transitions
• final features

Specified by:

cloneState in class IntDaciukAlgoIndexed

Returns:

addState

public int addState()

Description copied from class: IntDaciukAlgoIndexed

Adds a new state to the automaton

Specified by:

addState in class IntDaciukAlgoIndexed

Returns:

index of the new state

setNext

public boolean setNext(int src,
                       int label,
                       int dest)

Description copied from class: IntDaciukAlgoIndexed

Adds a transition from src to dest on given label, if a transition from src with given label already exists, then change it to new destination state.

Specified by:

setNext in class IntDaciukAlgoIndexed

Parameters:

src - source state

label - transition label

dest - destination state

Returns:

true, if state has changed

removeState

public void removeState(int state)

Description copied from class: IntDaciukAlgoIndexed

Removes given state from the automaton

Specified by:

removeState in class IntDaciukAlgoIndexed

Parameters:

state - state index

size

public int size()

getTransitionCount

public int getTransitionCount(int state)

getTransitionInput

public int getTransitionInput(int state,
                              int transitionIndex)

getTransitionNext

public int getTransitionNext(int state,
                             int transitionIndex)

getStartState

public int getStartState()

initFinals

public abstract void initFinals()

Initialize finality values for this FSA

finalHash

public abstract int finalHash(int state)

Compute hash code for the final value of the state

Parameters:

state - state

Returns:

hash code

finalEquals

public abstract boolean finalEquals(int state1,
                                    int state2)

Check if final values of two states are equal

Parameters:

state1 - first state

state2 - second state

Returns:

true, if they are equal

finalReset

public abstract void finalReset(int state)

Reset the final value of the given state

Parameters:

state -

finalAssign

public abstract void finalAssign(int destState,
                                 int srcState)

Copy final value from source state to destination state

Parameters:

destState - destination state

srcState - source state

newFinal

public abstract void newFinal(int state)

Initialize final value for given state

Parameters:

state -

isFinalState

public abstract boolean isFinalState(int state)

Checks if state is final

Parameters:

state - state number

toDot

public void toDot(java.io.PrintWriter pw)
           throws java.io.IOException

Output this DAFSA to dot format

Parameters:

pw - print writer

Throws:

java.io.IOException

toDot

public void toDot(java.lang.String fileName)
           throws java.io.IOException

Throws:

java.io.IOException

transitionCount

public int transitionCount()

getStates

public java.util.List<AbstractIntDAFSA.State> getStates()

isSource

public boolean isSource(int stateNumber)