net.automatalib.automata.base.compact

Class AbstractCompact<I,T,SP,TP>

java.lang.Object

net.automatalib.automata.base.compact.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:

Serializable, Iterable<Integer>, Automaton<Integer,I,T>, 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, SupportsGrowingAlphabet<I>, SimpleTS<Integer,I>, TransitionSystem<Integer,I,T>, UniversalTransitionSystem<Integer,I,T,SP,TP>

Direct Known Subclasses:

AbstractCompactDeterministic, AbstractCompactSimpleNondet

@ParametersAreNonnullByDefault
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>, Serializable

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.

Author:

frohme, Malte Isberner

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and 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 and Description
protected static int	DEFAULT_INIT_CAPACITY
protected static float	DEFAULT_RESIZE_FACTOR
protected static int	INVALID_STATE

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
void	addAlphabetSymbol(I symbol) Notifies the data structure that a new symbol should be added to the alphabet.
int	addIntState(SP property)
Integer	addState(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)
int	getStateId(Integer state)
Collection<Integer>	getStates() Retrieves all states of the transition system.
protected int	getSymbolIndex(I input)
int	numInputs()
abstract void	setStateProperty(int state, SP property)
int	size() Retrieves the size (number of states) of this transition system.
StateIDs<Integer>	stateIDs()
protected static int	toId(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 Integer	toState(int id)
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 Object[]	updateStateStorage(Object[] oldStorage, Object 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).
protected int[]	updateTransitionStorage(int[] oldStorage, int defaultValue, AbstractCompact.Payload payload) Return a copy of the provided array with updated memory layout.
protected Object[]	updateTransitionStorage(Object[] oldStorage, Object defaultValue, AbstractCompact.Payload payload) Return a copy of the provided array with updated memory layout.
protected <T> T[]	updateTransitionStorage(T[] oldStorage, IntFunction<T[]> arrayConstructor, T defaultValue, AbstractCompact.Payload payload) Return a copy of the provided array with updated memory layout.

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.MutableAutomaton

addInitialState, addInitialState, addState, addTransition, addTransition, addTransitions, copyTransition, createTransition, removeAllTransitions, removeAllTransitions, removeTransition, setInitial, setStateProperty, setTransitionProperty, setTransitions

Methods inherited from interface net.automatalib.automata.UniversalFiniteAlphabetAutomaton

transitionGraphView

Methods inherited from interface net.automatalib.automata.UniversalAutomaton

transitionGraphView

Methods inherited from interface net.automatalib.ts.UniversalTransitionSystem

getStateProperty, getTransitionProperty

Methods inherited from interface net.automatalib.automata.FiniteAlphabetAutomaton

graphView

Methods inherited from interface net.automatalib.ts.TransitionSystem

getSuccessor, getSuccessors, getTransitions, powersetView

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

createStaticStateMapping, iterator

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

createDynamicStateMapping, getInitialStates, getStates, getSuccessors, getSuccessors

Methods inherited from interface java.lang.Iterable

forEach, spliterator

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<Integer,I>

Returns:

all states in the transition system

stateIDs

public StateIDs<Integer> stateIDs()

Specified by:

stateIDs in interface SimpleAutomaton<Integer,I>

size

public int size()

Description copied from interface: SimpleAutomaton

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

Specified by:

size in interface SimpleAutomaton<Integer,I>

Returns:

the number of states of this transition system

getStateId

public int getStateId(Integer state)

Specified by:

getStateId in interface StateIDs<Integer>

getState

public Integer getState(int id)

Specified by:

getState in interface StateIDs<Integer>

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)
                             throws GrowingAlphabetNotSupportedException

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.

Throws:

GrowingAlphabetNotSupportedException - if the data structure was not properly initialized (e.g. with a GrowingAlphabet).

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<Integer,I>

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(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 Object[] updateTransitionStorage(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 <T> T[] updateTransitionStorage(T[] oldStorage,
                                                IntFunction<T[]> arrayConstructor,
                                                @Nullable
                                                T 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[], Object, Payload)

toState

protected static 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(@Nullable
                                   I input)

numInputs

public final int numInputs()