Package net.automatalib.automaton.base

Class AbstractCompact<I,T,SP,TP>

java.lang.Object

net.automatalib.automaton.base.AbstractCompact<I,T,SP,TP>

Type Parameters:

I - input symbol type

T - transition type

SP - state property type

TP - transition property type

All Implemented Interfaces:

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

Direct Known Subclasses:

AbstractCompactDeterministic, AbstractCompactMTS, AbstractCompactSimpleNondet

public abstract class AbstractCompact<I,T,SP,TP>
extends Object
implements MutableAutomaton<Integer,I,T,SP,TP>, StateIDs<Integer>, UniversalFiniteAlphabetAutomaton<Integer,I,T,SP,TP>, SupportsGrowingAlphabet<I>, StateLocalInput<Integer,I>

Abstract super class for compact automata representations. Compactness is achieved by representing states as integers, such that each state can be conveniently used to address a memory location. As a result most of the relevant automata data (such as successors, state- or transition properties) can be stored in compact arrays.

This class provides basic implementations (as far as possible on this abstract level) for several of the implemented concepts and offers utility methods to subclasses, for updating their array-based automata data.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	AbstractCompact.Payload	A utility class that encapsulates necessary information for performing an update of the stored automata data.

Field Summary

Fields

Modifier and Type	Field	Description
protected static int	DEFAULT_INIT_CAPACITY
protected static float	DEFAULT_RESIZE_FACTOR
protected static int	INVALID_STATE

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
void	addAlphabetSymbol(I symbol)	Notifies the data structure that a new symbol should be added to the alphabet.
int	addIntState(@Nullable SP property)
Integer	addState(@Nullable SP property)	Adds a state to the automaton.
void	clear()	Removes all states and transitions.
Alphabet<I>	getInputAlphabet()
Collection<I>	getLocalInputs(Integer state)	Returns the collection of input symbols for which a successor state is defined.
Integer	getState(int id)	Return for a given id the state of the automaton identified by it.
int	getStateId(Integer state)	Returns for a given state of the automaton an integer uniquely identifying the state.
Collection<Integer>	getStates()	Retrieves all states of the transition system.
protected int	getSymbolIndex(I input)
int	numInputs()
abstract void	setStateProperty(int state, @Nullable SP property)
int	size()	Retrieves the size (number of states) of this transition system.
StateIDs<Integer>	stateIDs()
protected static int	toId(@Nullable Integer id)
protected int	toMemoryIndex(int stateId, int inputId)	Returns for a given state id and input symbol index, the memory location for its associated data.
protected static @Nullable Integer	toState(int id)
protected Object[]	updateStateStorage(@Nullable Object[] oldStorage, @Nullable Object defaultValue, AbstractCompact.Payload payload)	Return a copy of the provided array with updated memory layout.
protected void	updateStateStorage(AbstractCompact.Payload payload)	Implementing classes should override this method in order to react to changes to the layout of their array-based state data, e.g. due to calls to MutableAutomaton.addState().
protected int[]	updateTransitionStorage(int[] oldStorage, int defaultValue, AbstractCompact.Payload payload)	Return a copy of the provided array with updated memory layout.
protected @Nullable Object[]	updateTransitionStorage(@Nullable Object[] oldStorage, @Nullable Object defaultValue, AbstractCompact.Payload payload)	Return a copy of the provided array with updated memory layout.
protected <S> @Nullable S[]	updateTransitionStorage(@Nullable S[] oldStorage, IntFunction<@Nullable S[]> arrayConstructor, @Nullable S defaultValue, AbstractCompact.Payload payload)	Return a copy of the provided array with updated memory layout.
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 addAlphabetSymbol(Object).

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, addTransition, addTransitions, copyTransition, createTransition, removeAllTransitions, removeAllTransitions, removeTransition, setInitial, setStateProperty, setTransitionProperty, setTransitions

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

createDynamicStateMapping, createStaticStateMapping, iterator

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

getInitialStates, getStates, getSuccessors, getSuccessors

Methods inherited from interface net.automatalib.ts.TransitionSystem

getSuccessor, getSuccessors, getTransitions, 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, getTransitionProperty

Field Detail

DEFAULT_RESIZE_FACTOR

protected static final float DEFAULT_RESIZE_FACTOR

See Also:

Constant Field Values

DEFAULT_INIT_CAPACITY

protected static final int DEFAULT_INIT_CAPACITY

See Also:

Constant Field Values

INVALID_STATE

protected static final int INVALID_STATE

See Also:

Constant Field Values

Constructor Detail

AbstractCompact

public AbstractCompact(Alphabet<I> alphabet,
                       AbstractCompact<?,?,?,?> other)

AbstractCompact

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

Method Detail

getStates

public Collection<Integer> getStates()

Description copied from interface: SimpleAutomaton

Retrieves all states of the transition system. Implementing classes should return an unmodifiable collection

Specified by:

getStates in interface SimpleAutomaton<I,T>

Returns:

all states in the transition system

stateIDs

public StateIDs<Integer> stateIDs()

Specified by:

stateIDs in interface SimpleAutomaton<I,T>

size

public int size()

Description copied from interface: SimpleAutomaton

Retrieves the size (number of states) of this transition system.

Specified by:

size in interface FiniteRepresentation

Specified by:

size in interface SimpleAutomaton<I,T>

Returns:

the number of states of this transition system

getStateId

public int getStateId(Integer state)

Description copied from interface: StateIDs

Returns for a given state of the automaton an integer uniquely identifying the state. The returned ids should be within the range of the number of states of the automaton so that they can be used for array-based indexing.

Specified by:

getStateId in interface StateIDs<I>

Parameters:

state - the state whose id should be retrieved

Returns:

the (positive) id of the given automaton state

getState

public Integer getState(int id)

Description copied from interface: StateIDs

Return for a given id the state of the automaton identified by it.

Specified by:

getState in interface StateIDs<I>

Parameters:

id - the id of the state to be returned

Returns:

the automaton state identified by the given id.

clear

public void clear()

Description copied from interface: MutableAutomaton

Removes all states and transitions.

Specified by:

clear in interface MutableAutomaton<Integer,I,T,SP,TP>

addState

public final Integer addState(@Nullable SP property)

Description copied from interface: MutableAutomaton

Adds a state to the automaton.

Specified by:

addState in interface MutableAutomaton<Integer,I,T,SP,TP>

addIntState

public int addIntState(@Nullable SP property)

getInputAlphabet

public Alphabet<I> getInputAlphabet()

Specified by:

getInputAlphabet in interface InputAlphabetHolder<I>

addAlphabetSymbol

public final void addAlphabetSymbol(I symbol)

Description copied from interface: SupportsGrowingAlphabet

Notifies the data structure that a new symbol should be added to the alphabet. Behavior depends on the implementation:

• After adding a new symbol, the symbol-related data may either be initialized with default values or undefined.
• Duplicate symbols may: (1) be handled accordingly, (2) be ignored or (3) result in an error.

Some data structures may need to be properly initialized (e.g. with a GrowingAlphabet) to handle potentially shared state across multiple instances. If the needed requirements are not met, a GrowingAlphabetNotSupportedException can be thrown.

Specified by:

addAlphabetSymbol in interface SupportsGrowingAlphabet<I>

Parameters:

symbol - the symbol to add to the alphabet.

getLocalInputs

public Collection<I> getLocalInputs(Integer state)

Description copied from interface: StateLocalInput

Returns the collection of input symbols for which a successor state is defined.

Specified by:

getLocalInputs in interface StateLocalInput<I,T>

Parameters:

state - the state for which the defined inputs should be returned

Returns:

the collection of input symbols for which a successor state is defined.

setStateProperty

public abstract void setStateProperty(int state,
                                      @Nullable SP property)

updateStateStorage

protected void updateStateStorage(AbstractCompact.Payload payload)

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

Subclasses may use one of the updateStateStorage(Object[], 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.

Parameters:

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

updateStateStorage

protected final Object[] updateStateStorage(@Nullable Object[] oldStorage,
                                            @Nullable Object defaultValue,
                                            AbstractCompact.Payload payload)

Return a copy of the provided array with updated memory layout.

Parameters:

oldStorage - the current array

defaultValue - default value for newly allocated array positions

payload - the payload object

Returns:

a copy of the provided array with updated memory layout.

updateTransitionStorage

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 addAlphabetSymbol(Object).

Subclasses may use one of the 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.

Parameters:

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

updateTransitionStorage

protected final int[] updateTransitionStorage(int[] oldStorage,
                                              int defaultValue,
                                              AbstractCompact.Payload payload)

Return a copy of the provided array with updated memory layout.

Parameters:

oldStorage - the current array

defaultValue - default value for newly allocated array positions

payload - the payload object

Returns:

a copy of the provided array with updated memory layout.

See Also:

updateTransitionStorage(Object[], Object, Payload), updateTransitionStorage(Object[], IntFunction, Object, Payload)

updateTransitionStorage

protected final @Nullable Object[] updateTransitionStorage(@Nullable Object[] oldStorage,
                                                           @Nullable Object defaultValue,
                                                           AbstractCompact.Payload payload)

Return a copy of the provided array with updated memory layout.

Parameters:

oldStorage - the current array

defaultValue - default value for newly allocated array positions

payload - the payload object

Returns:

a copy of the provided array with updated memory layout.

See Also:

updateTransitionStorage(int[], int, Payload), updateTransitionStorage(Object[], IntFunction, Object, Payload)

updateTransitionStorage

protected final <S> @Nullable S[] updateTransitionStorage(@Nullable S[] oldStorage,
                                                          IntFunction<@Nullable S[]> arrayConstructor,
                                                          @Nullable S defaultValue,
                                                          AbstractCompact.Payload payload)

Return a copy of the provided array with updated memory layout.

Type Parameters:

S - the storage type

Parameters:

oldStorage - the current array

defaultValue - default value for newly allocated array positions

payload - the payload object

Returns:

a copy of the provided array with updated memory layout.

See Also:

updateTransitionStorage(int[], int, Payload), updateTransitionStorage(Object[], Object, Payload)

toState

protected static @Nullable Integer toState(int id)

toId

protected static int toId(@Nullable Integer id)

toMemoryIndex

protected final int toMemoryIndex(int stateId,
                                  int inputId)

Returns for a given state id and input symbol index, the memory location for its associated data.

Parameters:

stateId - the state id

inputId - the index of input symbol

Returns:

the memory location for the given state id and input symbol index

See Also:

getSymbolIndex(Object)

getSymbolIndex

protected final int getSymbolIndex(I input)

numInputs

public final int numInputs(@UnknownInitialization(AbstractCompact.class) AbstractCompact<I,T,SP,TP> this)