de.learnlib.datastructure.pta.pta

Class BasePTA<SP,TP,S extends AbstractBasePTAState<SP,TP,S>>

java.lang.Object

de.learnlib.datastructure.pta.pta.BasePTA<SP,TP,S>

Type Parameters:

SP - state property type

TP - transition property type

S - state type

All Implemented Interfaces:

Iterable<S>, net.automatalib.automata.Automaton<S,Integer,PTATransition<S>>, net.automatalib.automata.DeterministicAutomaton<S,Integer,PTATransition<S>>, net.automatalib.automata.simple.SimpleAutomaton<S,Integer>, net.automatalib.automata.simple.SimpleDeterministicAutomaton<S,Integer>, net.automatalib.automata.UniversalAutomaton<S,Integer,PTATransition<S>,SP,TP>, net.automatalib.automata.UniversalDeterministicAutomaton<S,Integer,PTATransition<S>,SP,TP>, net.automatalib.ts.DeterministicTransitionSystem<S,Integer,PTATransition<S>>, net.automatalib.ts.simple.SimpleDTS<S,Integer>, net.automatalib.ts.simple.SimpleTS<S,Integer>, net.automatalib.ts.TransitionSystem<S,Integer,PTATransition<S>>, net.automatalib.ts.UniversalDTS<S,Integer,PTATransition<S>,SP,TP>, net.automatalib.ts.UniversalTransitionSystem<S,Integer,PTATransition<S>,SP,TP>

Direct Known Subclasses:

AbstractBlueFringePTA

@ParametersAreNonnullByDefault
public class BasePTA<SP,TP,S extends AbstractBasePTAState<SP,TP,S>>
extends Object
implements net.automatalib.automata.UniversalDeterministicAutomaton<S,Integer,PTATransition<S>,SP,TP>

Base class for prefix tree acceptors.

Author:

Malte Isberner

Nested Class Summary

Nested classes/interfaces inherited from interface net.automatalib.automata.UniversalDeterministicAutomaton

net.automatalib.automata.UniversalDeterministicAutomaton.FullIntAbstraction<T,SP,TP>, net.automatalib.automata.UniversalDeterministicAutomaton.IntAbstraction<T,SP,TP>, net.automatalib.automata.UniversalDeterministicAutomaton.StateIntAbstraction<I,T,SP,TP>

Field Summary

Fields

Modifier and Type	Field and Description
protected int	alphabetSize
protected S	root

Constructor Summary

Constructors

Constructor and Description
BasePTA(int alphabetSize, S root) Constructor.

Method Summary

Modifier and Type	Method and Description
void	addSample(int[] sample, SP lastProperty) Adds a sample to the PTA, and sets the property of the last reached (or inserted) state accordingly.
void	addSampleWithStateProperties(int[] sample, List<? extends SP> lastStateProperties)
void	addSampleWithTransitionProperties(int[] sample, List<? extends TP> lastTransitionProperties)
Iterator<S>	bfsIterator() Retrieves an iterator that can be used for iterating over all states in this PTA that are reachable from the root state in a breadth-first order.
List<S>	bfsStates() Retrieves a list of all states in this PTA that are reachable from the root state.
int	countStates() Counts the number of states in this PTA.
S	getInitialState()
S	getOrCreateState(int[] word) Retrieves the state reached by the given word (represented as an int array).
S	getRoot() Retrieves the root of the PTA.
S	getState(int[] word) Retrieves the state reached by the given word (represented as an int array).
SP	getStateProperty(S state)
Collection<S>	getStates()
S	getSuccessor(PTATransition<S> transition)
S	getSuccessor(S state, Integer input)
PTATransition<S>	getTransition(S state, Integer input)
TP	getTransitionProperty(PTATransition<S> transition)
<I> net.automatalib.graphs.Graph<S,PTATransition<S>>	graphView(net.automatalib.words.Alphabet<I> alphabet)
Iterator<S>	iterator()
int	size()
<I> void	toAutomaton(net.automatalib.automata.MutableDeterministic<?,I,?,? super SP,? super TP> automaton, net.automatalib.words.Alphabet<I> alphabet)
<S2,I,SP2,TP2> void	toAutomaton(net.automatalib.automata.MutableDeterministic<S2,I,?,? super SP2,? super TP2> automaton, net.automatalib.words.Alphabet<I> alphabet, Function<? super SP,? extends SP2> spExtractor, Function<? super TP,? extends TP2> tpExtractor)

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.automatalib.automata.UniversalDeterministicAutomaton

fullIntAbstraction, fullIntAbstraction, stateIntAbstraction

Methods inherited from interface net.automatalib.ts.UniversalDTS

getTransitionProperty

Methods inherited from interface net.automatalib.ts.DeterministicTransitionSystem

getSuccessors, getTransitions, transToSet

Methods inherited from interface net.automatalib.ts.simple.SimpleDTS

getInitialStates, getState, getStates, getSuccessor, getSuccessors, stateToSet

Methods inherited from interface net.automatalib.automata.UniversalAutomaton

transitionGraphView

Methods inherited from interface net.automatalib.automata.simple.SimpleAutomaton

createStaticStateMapping, stateIDs

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface net.automatalib.ts.TransitionSystem

powersetView

Methods inherited from interface net.automatalib.ts.simple.SimpleTS

createDynamicStateMapping, getSuccessors

Field Detail

alphabetSize

@Nonnegative
protected final int alphabetSize

root

@Nonnull
protected final S extends AbstractBasePTAState<SP,TP,S> root

Constructor Detail

BasePTA

public BasePTA(@Nonnegative
               int alphabetSize,
               S root)

Constructor.

Parameters:

alphabetSize - the size of the input alphabet

root - the root state

Method Detail

getState

@Nullable
public S getState(int[] word)

Retrieves the state reached by the given word (represented as an int array). If there is no path for the given word in the PTA, null is returned.

Parameters:

word - the word

Returns:

the state reached by this word, or null if there is no path for the given word in the PTA

addSample

public void addSample(int[] sample,
                      SP lastProperty)

Adds a sample to the PTA, and sets the property of the last reached (or inserted) state accordingly.

Parameters:

sample - the word to add to the PTA

lastProperty - the property of the last state to set

getOrCreateState

@Nonnull
public S getOrCreateState(int[] word)

Retrieves the state reached by the given word (represented as an int array). If there is no path for the word in the PTA, it will be added to the PTA on-the-fly.

Parameters:

word - the word

Returns:

the state reached by this word, which might have been newly created (along with all required predecessor states)

addSampleWithStateProperties

public void addSampleWithStateProperties(int[] sample,
                                         List<? extends SP> lastStateProperties)

getRoot

@Nonnull
public S getRoot()

Retrieves the root of the PTA.

Returns:

the root state

addSampleWithTransitionProperties

public void addSampleWithTransitionProperties(int[] sample,
                                              List<? extends TP> lastTransitionProperties)

toAutomaton

public <I> void toAutomaton(net.automatalib.automata.MutableDeterministic<?,I,?,? super SP,? super TP> automaton,
                            net.automatalib.words.Alphabet<I> alphabet)

toAutomaton

public <S2,I,SP2,TP2> void toAutomaton(net.automatalib.automata.MutableDeterministic<S2,I,?,? super SP2,? super TP2> automaton,
                                       net.automatalib.words.Alphabet<I> alphabet,
                                       Function<? super SP,? extends SP2> spExtractor,
                                       Function<? super TP,? extends TP2> tpExtractor)

graphView

public <I> net.automatalib.graphs.Graph<S,PTATransition<S>> graphView(net.automatalib.words.Alphabet<I> alphabet)

bfsStates

@Nonnull
public List<S> bfsStates()

Retrieves a list of all states in this PTA that are reachable from the root state. The states will be returned in breadth-first order.

Returns:

a breadth-first ordered list of all states in this PTA

bfsIterator

@Nonnull
public Iterator<S> bfsIterator()

Retrieves an iterator that can be used for iterating over all states in this PTA that are reachable from the root state in a breadth-first order.

Returns:

an iterator for iterating over all states in this PTA

getSuccessor

public S getSuccessor(PTATransition<S> transition)

Specified by:

getSuccessor in interface net.automatalib.ts.TransitionSystem<S extends AbstractBasePTAState<SP,TP,S>,Integer,PTATransition<S extends AbstractBasePTAState<SP,TP,S>>>

getSuccessor

public S getSuccessor(S state,
                      Integer input)

Specified by:

getSuccessor in interface net.automatalib.ts.DeterministicTransitionSystem<S extends AbstractBasePTAState<SP,TP,S>,Integer,PTATransition<S extends AbstractBasePTAState<SP,TP,S>>>

Specified by:

getSuccessor in interface net.automatalib.ts.simple.SimpleDTS<S extends AbstractBasePTAState<SP,TP,S>,Integer>

iterator

public Iterator<S> iterator()

Specified by:

iterator in interface Iterable<S extends AbstractBasePTAState<SP,TP,S>>

Specified by:

iterator in interface net.automatalib.automata.simple.SimpleAutomaton<S extends AbstractBasePTAState<SP,TP,S>,Integer>

getStates

public Collection<S> getStates()

Specified by:

getStates in interface net.automatalib.automata.simple.SimpleAutomaton<S extends AbstractBasePTAState<SP,TP,S>,Integer>

size

public int size()

Specified by:

size in interface net.automatalib.automata.simple.SimpleAutomaton<S extends AbstractBasePTAState<SP,TP,S>,Integer>

countStates

@Nonnegative
public int countStates()

Counts the number of states in this PTA. Note that this method might require a complete traversal of the PTA.

Returns:

the number of states in the PTA reachable from the root state

getInitialState

public S getInitialState()

Specified by:

getInitialState in interface net.automatalib.ts.simple.SimpleDTS<S extends AbstractBasePTAState<SP,TP,S>,Integer>

getTransition

public PTATransition<S> getTransition(S state,
                                      Integer input)

Specified by:

getTransition in interface net.automatalib.ts.DeterministicTransitionSystem<S extends AbstractBasePTAState<SP,TP,S>,Integer,PTATransition<S extends AbstractBasePTAState<SP,TP,S>>>

getStateProperty

public SP getStateProperty(S state)

Specified by:

getStateProperty in interface net.automatalib.ts.UniversalTransitionSystem<S extends AbstractBasePTAState<SP,TP,S>,Integer,PTATransition<S extends AbstractBasePTAState<SP,TP,S>>,SP,TP>

getTransitionProperty

public TP getTransitionProperty(PTATransition<S> transition)

Specified by:

getTransitionProperty in interface net.automatalib.ts.UniversalTransitionSystem<S extends AbstractBasePTAState<SP,TP,S>,Integer,PTATransition<S extends AbstractBasePTAState<SP,TP,S>>,SP,TP>