H
Hendrik Maryns
Hi,
I wrote a method which completes a partial method, as part of a function
builder class. I really don´t like what it looks like right now, though
I think it is correct (almost, probably).
So if anybody would like to give some comments on how I can do this more
efficiently, but more important, more readably, you´re very welcome.
Here it is, it is no SSCCE, but I suppose you can infer what the other
methods do from their names...
It is rather long, but I do a lot of documenting, so I think it is readable.
I especially want to get rid of the array of iterators, (make this into
a list? Doesn´t seem much better/clearer), and nake the extracted
private function a bit slimmer.
Thanks in advance if anyone is wanting to read this through, otherwise
I'll look into trimming it a bit more.
H.
/**
* Keeps track on whether this function is complete. Mainly to avoid doing
* the computational intense complete function when unnecessary.
*/
private boolean complete = true;
/**
* Returns whether the function is complete.
*/
public boolean isComplete() {
return complete;
}
/**
* Complete the function with respect to the states it returns, the
* signature symbols that are already present in an argument it is defined
* on, and the states that are already present in an argument it is
defined
* on. All transitions that are newly added go to a new state, the dead
* state. New transitions are also added for the dead state.
*
* @post No transitions that were present have changed.
* | for arguments in FunctionInputTuple
* | if ( hasTransition(arguments) )
* | then new.apply(arguments) == apply(arguments)
* @post The domain now contains a new state, the dead state.
* | new.getDomain().getStates().size() ==
* | getDomain().getStates().size() + 1
* @post For each signature symbol that already occurred and for every
* possible combination of states that already occurred, its number
* conforming to the symbol's arity, a transition is registered
* going to a new state, the dead state.
* | let domain = getDomain() in
* | let domainExpansion = new.getDomain().getStates().removeAll(
* | domain.getStates())) in
* | let deadState = domainExpansion.get(0)
* | for arguments in FunctionInputTuple
* | let argStates = arguments.getStates() in
* | if ( domain.getSignature().contains(arguments.getSymbol()) &&
* | for each 0 <= i < argStates.length
* | domain.getStates().contains(argStates) )
* | then if ( ! hasTransition(arguments) )
* | then new.apply(arguments) == deadState
*/
public void complete() {
complete(new State());
}
/**
* Complete the function with respect to the states it returns, the
* signature symbols that are already present in an argument it is defined
* on, and the states that are already present in an argument it is
defined
* on. Existing transitions are untouched, newly added transitions all
* go to the given dead state. New transitions are also added for the
dead
* state.
*
* @param deadState
* The dead state to which all newly added transitions go.
* @post No transitions that were present have changed.
* | for arguments in FunctionInputTuple
* | if ( hasTransition(arguments) )
* | then new.apply(arguments) == apply(arguments)
* @post The domain now contains the dead state.
* | new.getDomain().getStates().size() ==
* | getDomain().getStates().size() + 1 &&
* | new.getDomain().getStates().contains(deadState)
* @post For each signature symbol that already occurred and for every
* possible combination of states that already occurred, its number
* conforming to the symbol's arity, a transition is registered
* going to the given dead state.
* | let domain = getDomain() in
* | for arguments in FunctionInputTuple
* | let argStates = arguments.getStates() in
* | if ( domain.getSignature().contains(arguments.getSymbol()) &&
* | for each 0 <= i < argStates.length
* | domain.getStates().contains(argStates) )
* | then if ( ! hasTransition(arguments) )
* | then new.apply(arguments) == deadState
*/
public void complete(State deadState) {
if (isComplete()) {
Domain domain = getDomain();
Set<State> allStates = domain.getStates();
allStates.addAll(getTransitions().values());
addCompletionOf(domain.getSignature(), allStates, deadState);
}
}
/**
* Add transitions to the function for every symbol and combination of
* states in the given signature and set of states. Existing transitions
* are untouched, newly added transitions all go to the given dead state.
* New transitions are also added for the dead state. </p>
* <p>This method is used in the completion process. It is rather useless
* to supply any non-initial state, as newly added states are
unreachable.
* Nevertheless, one can remove some transitions and replace them later.
* That is the only reason to make this a public method.
* TODO: privaat maken?
*
* @param signature
* The signature which should be included in the completion.
* @param states
* The set of states which should be added.
* @param deadState
* The dead state to which all newly added transitions go.
* @post No transitions that were present have changed.
* | for arguments in FunctionInputTuple
* | if ( hasTransition(arguments) )
* | then new.apply(arguments) == apply(arguments)
* @post For each signature symbol that was supplied and for every
* possible combination of the states that were supplied, its
* number conforming to the symbol's arity, a transition is
* registered going to the supplied dead state.
* | for arguments in FunctionInputTuple
* | let argStates = arguments.getStates() in
* | if ( signature.contains(arguments.getSymbol()) &&
* | for each 0 <= i < argStates.length
* | states.contains(argStates) )
* | then if ( ! hasTransition(arguments) )
* | then new.apply(arguments) == deadState
* @post The domain now contains the supplied signature, set of states
* and the dead state.
* | new.getDomain().getSignature().containsAll(signature) &&
* | new.getDomain().getStates().containsAll(states) &&
* | new.getDomain().getStates().contains(deadState)
*/
@SuppressWarnings("unchecked")//$NON-NLS-1$
public void addCompletionOf(Set<SignatureSymbol> signature,
Set<State> states, State deadState) {
Set<State> localStates = new HashSet<State>(states); // This might be
unnecessary. but safer because of possible NoSuchMethodException
localStates.add(deadState);
try {
/* Go through all possible combinations of symbol.getArity() states,
* and add a transition if one isn't present yet.
* @invar all symbols so far are completely processed, i.e. all
* possible combinations of states of number arity are in
* the function
* | for each symbol in localSig
* | for all input in State[symbol.getArity()]
* | if for all 0 <= i < input.length
* | localStates.contains(input)
* | then hasTransition(
* | new FunctionInputTuple(symbol, input))
* @var the number of symbols to be processed
* (Java takes care of this one!)
*/
for (SignatureSymbol symbol : signature) {
State[] inputStates = new State[symbol.getArity()];
Iterator<State>[] iters = new Iterator[symbol.getArity()];
Arrays.fill(iters, localStates.iterator());
/* Initialise the input array with the first state, at the same
* time keeping all the iterators synchronised.
* @invar The first state is assigned to inputStates[j] for
* every 0 <= j < i.
* | for all 0 <= j < i
* | inputStates[j] == iters[j].next()
* @var The number of slots to be initialised.
* | inputStates.length - i
*/
for (int i = 0; i < inputStates.length; i++) {
inputStates = iters.next();
}
// add the first transition if it is not yet present
FunctionInputTuple input = new FunctionInputTuple(symbol,
inputStates);
if (!hasTransition(input)) {
addTransition(input, deadState);
}
/* Cycle through all iterators and have it assign each possible
* state to its corresponding slot in the input array, for all
* possible states of the iterators before it; thus producing
* the cross product of the state sets.
* @invar For all configurations for the input array where
* only a state in position 0 <= j < i is different,
* this configuration has a transition.
* | for all input in State[symbol.getArity()]
* | if ( for all 0 <= j < i
* | localStates.contains(input[j]) &&
* | for all i <= j < input.length
* | input[j] == inputStates[j] )
* | then hasTransition(
* | new FunctionInputTuple(symbol, input))
* @var The number of iterators we have to cycle through.
* | iters.length - i
*/
for (int i = 0; i < iters.length; i++) {
loopIteratorAndPrevious(localStates, deadState, symbol,
inputStates, iters, i);
}
}
} catch (Exception e) {
// cannot occur
e.printStackTrace(); // I leave this in for testing TODO: remove this
}
//TODO refactor this method.
}
/**
* Loop through the iterator, adding all arguments generated to the
* function, invoking this same function on the previous iterator after
each
* step. Thus, recursively, the cross product is built.
*
* @param localStates
* The set of states of which the iterator stems.
* @param deadState
* The state to which all new transitions go.
* @param symbol
* The symbol for new transitions are added.
* @param inputStates
* The array of states that is used as input for the add method.
* @param iters
* The array of iterators of the localstates.
* @param i
* The index of the current iterator in iters.
* @post The recursion stops for i < 0.
* | if ( i < 0 )
* | then true
* @post
*/
private void loopIteratorAndPrevious(Set<State> localStates,
State deadState, SignatureSymbol symbol, State[] inputStates,
Iterator<State>[] iters, int i) {
if (i >= 0) {
try {
/* Step through all states in iters, adding transitions
* if necessary, in the meantime iterating over all
* preceding iterators.
* @invar TODO
* @var The number of states of this iterator to be
* processed. (No formal statement possible due to
* restrictive interface of iterators.)
*/
while (iters.hasNext()) {
inputStates = iters.next();
FunctionInputTuple input = new FunctionInputTuple(symbol,
inputStates);
if (!hasTransition(input)) {
addTransition(input, deadState);
}
loopIteratorAndPrevious(localStates, deadState, symbol,
inputStates, iters, i - 1);
}
// reset the iterator and the input slot
// they don't necessarily get reset to the same value
// each time, (see the Set.iterator contract), but that
// doesn't influence the correctness of the algorithm.
iters = localStates.iterator();
inputStates = iters.next();
} catch (Exception e) {
// cannot be thrown
e.printStackTrace(); //TODO remove this.
}
}
}
--
Hendrik Maryns
==================
www.lieverleven.be
http://aouw.org
I wrote a method which completes a partial method, as part of a function
builder class. I really don´t like what it looks like right now, though
I think it is correct (almost, probably).
So if anybody would like to give some comments on how I can do this more
efficiently, but more important, more readably, you´re very welcome.
Here it is, it is no SSCCE, but I suppose you can infer what the other
methods do from their names...
It is rather long, but I do a lot of documenting, so I think it is readable.
I especially want to get rid of the array of iterators, (make this into
a list? Doesn´t seem much better/clearer), and nake the extracted
private function a bit slimmer.
Thanks in advance if anyone is wanting to read this through, otherwise
I'll look into trimming it a bit more.
H.
/**
* Keeps track on whether this function is complete. Mainly to avoid doing
* the computational intense complete function when unnecessary.
*/
private boolean complete = true;
/**
* Returns whether the function is complete.
*/
public boolean isComplete() {
return complete;
}
/**
* Complete the function with respect to the states it returns, the
* signature symbols that are already present in an argument it is defined
* on, and the states that are already present in an argument it is
defined
* on. All transitions that are newly added go to a new state, the dead
* state. New transitions are also added for the dead state.
*
* @post No transitions that were present have changed.
* | for arguments in FunctionInputTuple
* | if ( hasTransition(arguments) )
* | then new.apply(arguments) == apply(arguments)
* @post The domain now contains a new state, the dead state.
* | new.getDomain().getStates().size() ==
* | getDomain().getStates().size() + 1
* @post For each signature symbol that already occurred and for every
* possible combination of states that already occurred, its number
* conforming to the symbol's arity, a transition is registered
* going to a new state, the dead state.
* | let domain = getDomain() in
* | let domainExpansion = new.getDomain().getStates().removeAll(
* | domain.getStates())) in
* | let deadState = domainExpansion.get(0)
* | for arguments in FunctionInputTuple
* | let argStates = arguments.getStates() in
* | if ( domain.getSignature().contains(arguments.getSymbol()) &&
* | for each 0 <= i < argStates.length
* | domain.getStates().contains(argStates) )
* | then if ( ! hasTransition(arguments) )
* | then new.apply(arguments) == deadState
*/
public void complete() {
complete(new State());
}
/**
* Complete the function with respect to the states it returns, the
* signature symbols that are already present in an argument it is defined
* on, and the states that are already present in an argument it is
defined
* on. Existing transitions are untouched, newly added transitions all
* go to the given dead state. New transitions are also added for the
dead
* state.
*
* @param deadState
* The dead state to which all newly added transitions go.
* @post No transitions that were present have changed.
* | for arguments in FunctionInputTuple
* | if ( hasTransition(arguments) )
* | then new.apply(arguments) == apply(arguments)
* @post The domain now contains the dead state.
* | new.getDomain().getStates().size() ==
* | getDomain().getStates().size() + 1 &&
* | new.getDomain().getStates().contains(deadState)
* @post For each signature symbol that already occurred and for every
* possible combination of states that already occurred, its number
* conforming to the symbol's arity, a transition is registered
* going to the given dead state.
* | let domain = getDomain() in
* | for arguments in FunctionInputTuple
* | let argStates = arguments.getStates() in
* | if ( domain.getSignature().contains(arguments.getSymbol()) &&
* | for each 0 <= i < argStates.length
* | domain.getStates().contains(argStates) )
* | then if ( ! hasTransition(arguments) )
* | then new.apply(arguments) == deadState
*/
public void complete(State deadState) {
if (isComplete()) {
Domain domain = getDomain();
Set<State> allStates = domain.getStates();
allStates.addAll(getTransitions().values());
addCompletionOf(domain.getSignature(), allStates, deadState);
}
}
/**
* Add transitions to the function for every symbol and combination of
* states in the given signature and set of states. Existing transitions
* are untouched, newly added transitions all go to the given dead state.
* New transitions are also added for the dead state. </p>
* <p>This method is used in the completion process. It is rather useless
* to supply any non-initial state, as newly added states are
unreachable.
* Nevertheless, one can remove some transitions and replace them later.
* That is the only reason to make this a public method.
* TODO: privaat maken?
*
* @param signature
* The signature which should be included in the completion.
* @param states
* The set of states which should be added.
* @param deadState
* The dead state to which all newly added transitions go.
* @post No transitions that were present have changed.
* | for arguments in FunctionInputTuple
* | if ( hasTransition(arguments) )
* | then new.apply(arguments) == apply(arguments)
* @post For each signature symbol that was supplied and for every
* possible combination of the states that were supplied, its
* number conforming to the symbol's arity, a transition is
* registered going to the supplied dead state.
* | for arguments in FunctionInputTuple
* | let argStates = arguments.getStates() in
* | if ( signature.contains(arguments.getSymbol()) &&
* | for each 0 <= i < argStates.length
* | states.contains(argStates) )
* | then if ( ! hasTransition(arguments) )
* | then new.apply(arguments) == deadState
* @post The domain now contains the supplied signature, set of states
* and the dead state.
* | new.getDomain().getSignature().containsAll(signature) &&
* | new.getDomain().getStates().containsAll(states) &&
* | new.getDomain().getStates().contains(deadState)
*/
@SuppressWarnings("unchecked")//$NON-NLS-1$
public void addCompletionOf(Set<SignatureSymbol> signature,
Set<State> states, State deadState) {
Set<State> localStates = new HashSet<State>(states); // This might be
unnecessary. but safer because of possible NoSuchMethodException
localStates.add(deadState);
try {
/* Go through all possible combinations of symbol.getArity() states,
* and add a transition if one isn't present yet.
* @invar all symbols so far are completely processed, i.e. all
* possible combinations of states of number arity are in
* the function
* | for each symbol in localSig
* | for all input in State[symbol.getArity()]
* | if for all 0 <= i < input.length
* | localStates.contains(input)
* | then hasTransition(
* | new FunctionInputTuple(symbol, input))
* @var the number of symbols to be processed
* (Java takes care of this one!)
*/
for (SignatureSymbol symbol : signature) {
State[] inputStates = new State[symbol.getArity()];
Iterator<State>[] iters = new Iterator[symbol.getArity()];
Arrays.fill(iters, localStates.iterator());
/* Initialise the input array with the first state, at the same
* time keeping all the iterators synchronised.
* @invar The first state is assigned to inputStates[j] for
* every 0 <= j < i.
* | for all 0 <= j < i
* | inputStates[j] == iters[j].next()
* @var The number of slots to be initialised.
* | inputStates.length - i
*/
for (int i = 0; i < inputStates.length; i++) {
inputStates = iters.next();
}
// add the first transition if it is not yet present
FunctionInputTuple input = new FunctionInputTuple(symbol,
inputStates);
if (!hasTransition(input)) {
addTransition(input, deadState);
}
/* Cycle through all iterators and have it assign each possible
* state to its corresponding slot in the input array, for all
* possible states of the iterators before it; thus producing
* the cross product of the state sets.
* @invar For all configurations for the input array where
* only a state in position 0 <= j < i is different,
* this configuration has a transition.
* | for all input in State[symbol.getArity()]
* | if ( for all 0 <= j < i
* | localStates.contains(input[j]) &&
* | for all i <= j < input.length
* | input[j] == inputStates[j] )
* | then hasTransition(
* | new FunctionInputTuple(symbol, input))
* @var The number of iterators we have to cycle through.
* | iters.length - i
*/
for (int i = 0; i < iters.length; i++) {
loopIteratorAndPrevious(localStates, deadState, symbol,
inputStates, iters, i);
}
}
} catch (Exception e) {
// cannot occur
e.printStackTrace(); // I leave this in for testing TODO: remove this
}
//TODO refactor this method.
}
/**
* Loop through the iterator, adding all arguments generated to the
* function, invoking this same function on the previous iterator after
each
* step. Thus, recursively, the cross product is built.
*
* @param localStates
* The set of states of which the iterator stems.
* @param deadState
* The state to which all new transitions go.
* @param symbol
* The symbol for new transitions are added.
* @param inputStates
* The array of states that is used as input for the add method.
* @param iters
* The array of iterators of the localstates.
* @param i
* The index of the current iterator in iters.
* @post The recursion stops for i < 0.
* | if ( i < 0 )
* | then true
* @post
*/
private void loopIteratorAndPrevious(Set<State> localStates,
State deadState, SignatureSymbol symbol, State[] inputStates,
Iterator<State>[] iters, int i) {
if (i >= 0) {
try {
/* Step through all states in iters, adding transitions
* if necessary, in the meantime iterating over all
* preceding iterators.
* @invar TODO
* @var The number of states of this iterator to be
* processed. (No formal statement possible due to
* restrictive interface of iterators.)
*/
while (iters.hasNext()) {
inputStates = iters.next();
FunctionInputTuple input = new FunctionInputTuple(symbol,
inputStates);
if (!hasTransition(input)) {
addTransition(input, deadState);
}
loopIteratorAndPrevious(localStates, deadState, symbol,
inputStates, iters, i - 1);
}
// reset the iterator and the input slot
// they don't necessarily get reset to the same value
// each time, (see the Set.iterator contract), but that
// doesn't influence the correctness of the algorithm.
iters = localStates.iterator();
inputStates = iters.next();
} catch (Exception e) {
// cannot be thrown
e.printStackTrace(); //TODO remove this.
}
}
}
--
Hendrik Maryns
==================
www.lieverleven.be
http://aouw.org