laser.regularlanguage.fsa
Class MutableFSA<L extends LabelInterface>

java.lang.Object
  extended by laser.regularlanguage.fsa.AbstractFSA<L>
      extended by laser.regularlanguage.fsa.AbstractMutableFSA<L>
          extended by laser.regularlanguage.fsa.MutableFSA<L>
Type Parameters:
L - The type of Label associated with this FSA.
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, ArtifactInterface, FSAInterface<L>, MutableFSAInterface<L>, Annotatable, Persistent, Visualizable
Direct Known Subclasses:
MutableDFA

public class MutableFSA<L extends LabelInterface>
extends AbstractMutableFSA<L>

This class represents FSAs that are mutable.

Note that this class is not synchronized, and attempts to use it with non-sequential code may result in unexpected behavior.

Author:
Nathan A. Jokel (laser-software@cs.umass.edu)
See Also:
MutableFSAInterface, Serialized Form

Field Summary
 
Fields inherited from class laser.regularlanguage.fsa.AbstractFSA
_alphabet, _factory, _nextStateID, _nextTransitionID, _startState, _states, _transitionIndex, _transitions
 
Fields inherited from interface laser.util.Persistent
PER_EXTENSION, READ_PERSISTENT_METHOD_NAME
 
Constructor Summary
protected MutableFSA(AbstractFSA<L> fsa)
          Creates a new MutableFSA with the same states, transitions, and Alphabet as the specified FSA.
protected MutableFSA(AlphabetInterface<L> alphabet, AbstractFSAFactory<L> factory)
          Returns a new MutableFSA with the specified Alphabet and FSA factory.
 
Method Summary
 FSAEpsilonTransitionInterface<L> addEpsilonTransition(FSAStateInterface<L> source, FSAStateInterface<L> target, java.lang.Object... args)
          Adds an epsilon (ε) transition to this FSA from the specified source state to the specified target state, and returns a reference to the newly created transition (optional operation).
 FSALabelPatternTransitionInterface<L> addTransition(FSAStateInterface<L> source, LabelPatternInterface<L> labelPattern, FSAStateInterface<L> target, java.lang.Object... args)
          Adds a transition to this FSA from the specified source state to the specified target state on the given LabelPattern and returns a reference to the newly created transition (optional operation).
 FSALabelTransitionInterface<L> addTransition(FSAStateInterface<L> source, L label, FSAStateInterface<L> target, java.lang.Object... args)
          Adds a transition to this FSA from the specified source state to the specified target state on the given Label, and returns a reference to the newly created transition.
 MutableFSA<L> clone()
          Returns a copy of this mutable FSA.
 RunnableFSAInterface<L> getRunnableFSA()
          Returns the runnable FSA corresponding to this mutable FSA.
 boolean supportsEpsilonTransitions()
          Returns true if this FSA supports epsilon transitions and false otherwise.
 boolean supportsNondeterminism()
          Returns true if this FSA supports nondeterminism and false otherwise.
 
Methods inherited from class laser.regularlanguage.fsa.AbstractMutableFSA
_checkLabelPattern, addLabel, addLabels, addState, addTransitions, copy, copyFSAAttributes, copyState, copyTransition, deleteDeadStates, deleteUnreachableStates, getCreateArgsForLabelTransition, getCreateArgsForTrapState, getCreateArgsForTrapTransition, getLabelPatterns, getStartState, getTransition, hasTransitionsOnLabelPatterns, makeTotal, removeLabel, removeLabels, removeState, removeTransition, removeTransitions, replaceLabelPatternTransitionsWithLabelTransitions, setAlphabet, setStartState, supportsLabelPatterns
 
Methods inherited from class laser.regularlanguage.fsa.AbstractFSA
_checkLabel, _checkState, _checkTransition, _internalAddTransition, _internalCopyFSAAttributes, _internalRemoveState, _internalRemoveTransition, addAnnotation, addAnnotations, checkWellFormed, copyAnnotations, getAcceptStates, getAlphabet, getAnnotationClasses, getAnnotationClasses, getAnnotationFilters, getAnnotations, getAnnotations, getDescription, getDotWriter, getEpsilonTransition, getFactory, getName, getNonAcceptStates, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, getVisExtension, hasTransitionsOnEpsilon, isDeterministic, isTotal, readPersistent, readPersistent, removeAnnotation, removeAnnotations, removeAnnotations, removeAnnotations, setAnnotationFilters, setDescription, setName, toDot, toDot, visualize, visualize, writePersistent, writePersistent
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface laser.regularlanguage.fsa.FSAInterface
checkWellFormed, getAcceptStates, getAlphabet, getDescription, getEpsilonTransition, getFactory, getName, getNonAcceptStates, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, hasTransitionsOnEpsilon, isDeterministic, isTotal, setDescription, setName
 
Methods inherited from interface laser.util.Annotatable
addAnnotation, addAnnotations, copyAnnotations, getAnnotationClasses, getAnnotationClasses, getAnnotationFilters, getAnnotations, getAnnotations, removeAnnotation, removeAnnotations, removeAnnotations, removeAnnotations, setAnnotationFilters
 
Methods inherited from interface laser.util.Persistent
writePersistent, writePersistent
 
Methods inherited from interface laser.util.Visualizable
getVisExtension, visualize, visualize
 

Constructor Detail

MutableFSA

protected MutableFSA(AlphabetInterface<L> alphabet,
                     AbstractFSAFactory<L> factory)
Returns a new MutableFSA with the specified Alphabet and FSA factory. The factory is used to create states and transitions and to get the runnable FSA corresponding to this mutable FSA.

PRECONDITIONS:

Note this constructor should only be called by the AbstractFSAFactory._internalCreateMutableFSAInterface(laser.alphabet.AlphabetInterface, laser.regularlanguage.fsa.AbstractFSAFactory) method and by constructors of subclasses of this class.

Parameters:
alphabet - The Alphabet.
factory - The factory
See Also:
AbstractFSAFactory._internalCreateMutableFSAInterface(laser.alphabet.AlphabetInterface, laser.regularlanguage.fsa.AbstractFSAFactory)

MutableFSA

protected MutableFSA(AbstractFSA<L> fsa)
Creates a new MutableFSA with the same states, transitions, and Alphabet as the specified FSA. The annotations on the FSA, its states and transitions are also copied.

PRECONDITION: The fsa is not null.

Note this constructor should only be called by the AbstractRunnableFSA.getMutableFSA() and clone() methods.

Parameters:
fsa - The FSA.
See Also:
AbstractRunnableFSA.getMutableFSA(), clone()
Method Detail

clone

public MutableFSA<L> clone()
Returns a copy of this mutable FSA.

Specified by:
clone in interface FSAInterface<L extends LabelInterface>
Specified by:
clone in class AbstractMutableFSA<L extends LabelInterface>
Returns:
A copy of this mutable FSA.

addEpsilonTransition

public FSAEpsilonTransitionInterface<L> addEpsilonTransition(FSAStateInterface<L> source,
                                                             FSAStateInterface<L> target,
                                                             java.lang.Object... args)
Adds an epsilon (ε) transition to this FSA from the specified source state to the specified target state, and returns a reference to the newly created transition (optional operation).

More formally, adds a transition t to T such that source(t) = sourcetarget(t) = targetlabel(t) = ε.

NOTES:

If the same source and target state are specified as that of an epsilon (ε) transition that already exists in the FSA, a reference to that transition is returned and the FSA remains unchanged.

If this FSA does not support epsilon (ε) transitions, this method should not be supported. Depending on the implementation, calling this method may cause an UnsupportedOperationException to be thrown.

PRECONDITIONS:

Parameters:
source - The source state of the transition to be added.
target - The target state of the transition to be added.
args - Implementation specific arguments used to create the transition (optional).
Returns:
A reference to the epsilon (ε) transition.
Throws:
java.lang.IllegalArgumentException - if source/target is null or is not a state in this FSA else if invalid arguments are specified by args.

addTransition

public FSALabelTransitionInterface<L> addTransition(FSAStateInterface<L> source,
                                                    L label,
                                                    FSAStateInterface<L> target,
                                                    java.lang.Object... args)
Adds a transition to this FSA from the specified source state to the specified target state on the given Label, and returns a reference to the newly created transition. More formally, adds a transition t to T such that source(t) = sourcetarget(t) = targetlabel(t) = label. The behavior of this method differs depending on whether the FSA supports nondeterminism or not.

If the FSA does not support nondeterminism, there can only be exactly one transition with a certain source state and Label. In this case, attempting to add a transition with the same source state and Label but a different target state as an existing transition will result in an UnsupportedOperationException being thrown. This condition is formally specified as (∃ t'T : source(t') = sourcetarget(t') ≠ targetlabel(t') = label. Instead, the existing transition should first be removed using the AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface) method.

By contrast, if the FSA supports nondeterminism, there can be multiple transitions with the same source state and Label but differing target states. In this case, adding such a transition with a different target state is allowed, and the existing transition(s) remain unchanged.

NOTES:

A copy of the Label is used, thus no references are maintained between the specified Label and the Label on the transition, thus modifying the specified Label has no effect on the Label on the transition and vice versa.

If the same source state, Label, and target state are specified as a transition that already exists in the FSA, a reference to that transition is returned and the FSA remains unchanged.

PRECONDITIONS:

Parameters:
source - The source state of the transition to be added.
label - The Label of the transition to be added.
target - The target state of the transition to be added.
args - Implementation specific arguments used to create the transition (optional).
Returns:
A reference to the transition.
Throws:
java.lang.IllegalArgumentException - if source/target is null or is not a state in this FSA, if label is null or is not contained in the alphabet of this FSA, or if invalid arguments are specified by args
See Also:
FSAInterface.checkWellFormed(), AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface)

addTransition

public FSALabelPatternTransitionInterface<L> addTransition(FSAStateInterface<L> source,
                                                           LabelPatternInterface<L> labelPattern,
                                                           FSAStateInterface<L> target,
                                                           java.lang.Object... args)
Adds a transition to this FSA from the specified source state to the specified target state on the given LabelPattern and returns a reference to the newly created transition (optional operation). For details see FSALabelPatternTransitionInterface and AbstractMutableFSA.replaceLabelPatternTransitionsWithLabelTransitions().

This may introduce nondeterminism if a transition exists or is later added to the FSA with the same source state and a different target state on a Label that is matched by the LabelPattern or another LabelPattern that matches a common Label with the specified LabelPattern. Nondeterminism may also be introduced if the Alphabet of the FSA is subsequently changed, thus changing the set of Labels matched by the LabelPattern. If the FSA does not support nondeterminism, this may cause the FSA to be not well-formed.

If the FSA does not support nondeterminism, attempting to add a transition with the same source state and an equal LabelPattern but a different target state as an existing transition will definitely result in nondeterminism, thus an UnsupportedOperationException will be thrown. This condition is formally specified as (∃ t'T : source(t') = sourcetarget(t') ≠ targetlabel(t') = labelPattern. Instead, the existing transition should first be removed using the AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface) method.

By contrast, if the FSA supports nondeterminism, there can be multiple transitions with the same source state and an equal LabelPattern but differing target states. In this case, adding such a transition with a different target state is allowed, and the existing transition(s) remain unchanged.

NOTES:

A copy of the LabelPattern is used, thus no references are maintained between the specified LabelPattern and the LabelPattern on the transition, thus modifying the specified LabelPattern has no effect on the LabelPattern on the transition and vice versa.

If the same source state, LabelPattern, and target state are specified as a transition that already exists in the FSA, a reference to that transition is returned and the FSA remains unchanged.

If this FSA does not support transitions on LabelPatterns, calling this method may cause an UnsupportedOperationException to be thrown, depending on the implementation.

PRECONDITIONS:

Parameters:
source - The source state of the transition to be added.
labelPattern - The LabelPattern of the transition to be added.
target - The target state of the transition to be added.
args - Implementation specific arguments used to create the transition (optional).
Returns:
A refernce to the transition.
Throws:
java.lang.IllegalArgumentException - if source/target is null or is not a state in this FSA, if labelPattern is null, or if invalid arguments are specified by args
See Also:
laser.alphabetinterface.labelpatterninterface.LabelPatternInterface, FSAInterface.checkWellFormed(), AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface)

getRunnableFSA

public RunnableFSAInterface<L> getRunnableFSA()
                                                              throws FSAInterfaceException
Returns the runnable FSA corresponding to this mutable FSA. This FSA must be well-formed. Any transitions on LabelPatterns are replaced with the corresponding transitions on Labels in the runnable FSA since a runnable FSA can not have transitions on LabelPatterns, but the mutable FSA remains unchanged. The states and transitions in the runnable FSA are reindexed, therefore the ID of a state or transition in the mutable FSA might not equal the ID of its corresponding state or transition in the runnable FSA.

No references are maintained between the FSAs, thus modifying the mutable FSA has no effect on the runnable FSA.

Specified by:
getRunnableFSA in interface MutableFSAInterface<L extends LabelInterface>
Specified by:
getRunnableFSA in class AbstractMutableFSA<L extends LabelInterface>
Returns:
The runnable FSA corresponding to this mutable FSA.
Throws:
WellFormednessException - if this FSA is not well-formed.
FSAInterfaceException - if this FSA is not well-formed.
See Also:
RunnableFSAInterface, FSAInterface.checkWellFormed(), AbstractMutableFSA.replaceLabelPatternTransitionsWithLabelTransitions()

supportsEpsilonTransitions

public boolean supportsEpsilonTransitions()
Returns true if this FSA supports epsilon transitions and false otherwise.

Returns:
True if epsilon transitions are supported and false otherwise

supportsNondeterminism

public boolean supportsNondeterminism()
Returns true if this FSA supports nondeterminism and false otherwise.

Returns:
True if nondeterminism is supported and false otherwise