Package net.automatalib.automaton.base

Class AbstractCompactSimpleNondet<I,SP>

java.lang.Object

net.automatalib.automaton.base.AbstractCompact<I,Integer,SP,Void>

net.automatalib.automaton.base.AbstractCompactSimpleNondet<I,SP>

Type Parameters:

I - input symbol type

SP - state property type

All Implemented Interfaces:

Iterable<Integer>, SupportsGrowingAlphabet<I>, Automaton<Integer,I,Integer>, FiniteRepresentation, InputAlphabetHolder<I>, StateIDs<Integer>, StateLocalInput<Integer,I>, FiniteAlphabetAutomaton<Integer,I,Integer>, MutableAutomaton<Integer,I,Integer,SP,Void>, SimpleAutomaton<Integer,I>, UniversalAutomaton<Integer,I,Integer,SP,Void>, UniversalFiniteAlphabetAutomaton<Integer,I,Integer,SP,Void>, GraphViewable, SimpleTS<Integer,I>, TransitionSystem<Integer,I,Integer>, UniversalTransitionSystem<Integer,I,Integer,SP,Void>

Direct Known Subclasses:

CompactNFA

public abstract class AbstractCompactSimpleNondet<I,SP>
extends AbstractCompact<I,Integer,SP,Void>

Abstract super class that refines AbstractCompact for transition-property-less automata. As a result, transitions may be represented as integers (where a transition object effectively is the successor).

Implementation note: This class uses BitSets to store the successors of each state. This makes the memory consumption of this class depend on the number of states rather than the density of its adjacency matrix (since the maximum bit/index determines the size of each BitSet). For the majority of cases (tests showed if the average number of outgoing transitions per state is more than 0.2% of the number of states) this still requires less memory than using e.g. a Set of Integers. However, for very large but very sparse NFAs one may consider using the AbstractFastMutableNondet class instead.

Nested Class Summary

Nested classes/interfaces inherited from class net.automatalib.automaton.base.AbstractCompact

AbstractCompact.Payload

Field Summary

Fields inherited from class net.automatalib.automaton.base.AbstractCompact

DEFAULT_INIT_CAPACITY, DEFAULT_RESIZE_FACTOR, INVALID_STATE

Constructor Summary

Constructors

Modifier	Constructor	Description
	AbstractCompactSimpleNondet(Alphabet<I> alphabet, int stateCapacity, float resizeFactor)
protected	AbstractCompactSimpleNondet(Alphabet<I> alphabet, AbstractCompactSimpleNondet<?,?> other)

Method Summary

Modifier and Type	Method	Description
void	addTransition(int stateId, int inputIdx, int succId)
void	addTransition(int stateId, I input, int succId)
void	addTransition(Integer state, I input, Integer transition)
void	clear()	Removes all states and transitions.
Integer	copyTransition(Integer trans, Integer succ)
Integer	createTransition(Integer successor, Void properties)
Set<Integer>	getInitialStates()	Retrieves the set of initial states of the transition system.
Integer	getSuccessor(Integer transition)	Retrieves the successor state of a given transition.
Void	getTransitionProperty(Integer transition)	Retrieves the transition property for the given state.
Set<Integer>	getTransitions(int state, int inputIdx)
Set<Integer>	getTransitions(int state, I input)
Collection<Integer>	getTransitions(Integer state, I input)	Retrieves the transitions that can be triggered by the given input symbol.
void	removeAllTransitions(int state)
void	removeAllTransitions(int stateId, int inputIdx)
void	removeAllTransitions(int stateId, I input)
void	removeAllTransitions(Integer state)
void	removeAllTransitions(Integer state, I input)
void	removeTransition(int stateId, int inputIdx, int successorId)
void	removeTransition(int stateId, I input, int successorId)
void	removeTransition(Integer state, I input, Integer transition)
void	setInitial(int state, boolean initial)
void	setInitial(Integer state, boolean initial)
void	setTransitionProperty(Integer transition, Void property)
void	setTransitions(int state, int inputIdx, Collection<? extends Integer> successors)
void	setTransitions(int state, I input, Collection<? extends Integer> successors)
void	setTransitions(Integer state, I input, Collection<? extends Integer> transitions)
protected void	updateTransitionStorage(AbstractCompact.Payload payload)	Implementing classes should override this method in order to react to changes to the layout of their array-based transition data, e.g. due to calls to MutableAutomaton.addState() or AbstractCompact.addAlphabetSymbol(Object).

Methods inherited from class net.automatalib.automaton.base.AbstractCompact

addAlphabetSymbol, addIntState, addState, getInputAlphabet, getLocalInputs, getState, getStateId, getStates, getSymbolIndex, numInputs, setStateProperty, size, stateIDs, toId, toMemoryIndex, toState, updateStateStorage, updateStateStorage, updateTransitionStorage, updateTransitionStorage, updateTransitionStorage

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.automatalib.automaton.FiniteAlphabetAutomaton

getTransitions, graphView

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface net.automatalib.automaton.MutableAutomaton

addInitialState, addInitialState, addState, addTransition, addTransitions, setStateProperty

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

createDynamicStateMapping, createStaticStateMapping, iterator

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

getStates, getSuccessors, getSuccessors

Methods inherited from interface net.automatalib.ts.TransitionSystem

getSuccessors, powersetView

Methods inherited from interface net.automatalib.automaton.UniversalAutomaton

transitionGraphView

Methods inherited from interface net.automatalib.automaton.UniversalFiniteAlphabetAutomaton

transitionGraphView

Methods inherited from interface net.automatalib.ts.UniversalTransitionSystem

getStateProperty

Constructor Detail

AbstractCompactSimpleNondet

public AbstractCompactSimpleNondet(Alphabet<I> alphabet,
                                   int stateCapacity,
                                   float resizeFactor)

AbstractCompactSimpleNondet

protected AbstractCompactSimpleNondet(Alphabet<I> alphabet,
                                      AbstractCompactSimpleNondet<?,?> other)

Method Detail

updateTransitionStorage

protected void updateTransitionStorage(AbstractCompact.Payload payload)

Description copied from class: AbstractCompact

Implementing classes should override this method in order to react to changes to the layout of their array-based transition data, e.g. due to calls to MutableAutomaton.addState() or AbstractCompact.addAlphabetSymbol(Object).

Subclasses may use one of the AbstractCompact.updateTransitionStorage(Object[], IntFunction, Object, Payload)... methods to conveniently delegate this task to this base class. This leaves subclasses only with the task to invoke the provided update methods for each of their local array storages.

Overrides:

updateTransitionStorage in class AbstractCompact<I,Integer,SP,Void>

Parameters:

payload - the payload containing the necessary information for the update operation. This object must be passed as-is to the AbstractCompact.updateTransitionStorage(Object[], IntFunction, Object, Payload)... methods.

getTransitionProperty

public Void getTransitionProperty(Integer transition)

Description copied from interface: UniversalTransitionSystem

Retrieves the transition property for the given state.

Parameters:

transition - the transition.

Returns:

the corresponding property.

setInitial

public void setInitial(Integer state,
                       boolean initial)

setInitial

public void setInitial(int state,
                       boolean initial)

clear

public void clear()

Description copied from interface: MutableAutomaton

Removes all states and transitions.

Specified by:

clear in interface MutableAutomaton<Integer,I,Integer,SP,Void>

Overrides:

clear in class AbstractCompact<I,Integer,SP,Void>

setTransitionProperty

public void setTransitionProperty(Integer transition,
                                  Void property)

removeTransition

public void removeTransition(Integer state,
                             I input,
                             Integer transition)

removeTransition

public void removeTransition(int stateId,
                             I input,
                             int successorId)

removeTransition

public void removeTransition(int stateId,
                             int inputIdx,
                             int successorId)

removeAllTransitions

public void removeAllTransitions(Integer state,
                                 I input)

removeAllTransitions

public void removeAllTransitions(int stateId,
                                 I input)

removeAllTransitions

public void removeAllTransitions(int stateId,
                                 int inputIdx)

removeAllTransitions

public void removeAllTransitions(Integer state)

removeAllTransitions

public void removeAllTransitions(int state)

addTransition

public void addTransition(Integer state,
                          I input,
                          Integer transition)

addTransition

public void addTransition(int stateId,
                          I input,
                          int succId)

addTransition

public void addTransition(int stateId,
                          int inputIdx,
                          int succId)

copyTransition

public Integer copyTransition(Integer trans,
                              Integer succ)

createTransition

public Integer createTransition(Integer successor,
                                Void properties)

setTransitions

public void setTransitions(Integer state,
                           I input,
                           Collection<? extends Integer> transitions)

setTransitions

public void setTransitions(int state,
                           I input,
                           Collection<? extends Integer> successors)

setTransitions

public void setTransitions(int state,
                           int inputIdx,
                           Collection<? extends Integer> successors)

getSuccessor

public Integer getSuccessor(Integer transition)

Description copied from interface: TransitionSystem

Retrieves the successor state of a given transition.

Parameters:

transition - the transition.

Returns:

the successor state.

getTransitions

public Collection<Integer> getTransitions(Integer state,
                                          I input)

Description copied from interface: TransitionSystem

Retrieves the transitions that can be triggered by the given input symbol.

The return value must not be null; if there are no transitions triggered by the specified input, Collections.emptySet() should be returned.

Parameters:

state - the source state.

input - the input symbol.

Returns:

the transitions triggered by the given input

getTransitions

public Set<Integer> getTransitions(int state,
                                   I input)

getTransitions

public Set<Integer> getTransitions(int state,
                                   int inputIdx)

getInitialStates

public Set<Integer> getInitialStates()

Description copied from interface: SimpleTS

Retrieves the set of initial states of the transition system.

Returns:

the initial states.