Skip to content

Instantly share code, notes, and snippets.

@outofrange
Last active August 29, 2015 14:22
Show Gist options
  • Save outofrange/486ba2fadfeb4d46e79f to your computer and use it in GitHub Desktop.
Save outofrange/486ba2fadfeb4d46e79f to your computer and use it in GitHub Desktop.
State Machine
package example;
import com.google.common.collect.Table;
import org.apache.log4j.Logger;
import java.util.*;
import java.util.stream.Collectors;
/**
* An implementation of a state machine able to choose the shortest path between two states.
*
* @param <S> the Enum describing the possible states of this machine
*/
public class StateMachine<S> {
private static final Logger log = Logger.getLogger(StateMachine.class);
private final Table<S, S, List<Runnable>> transitions;
private S currentState;
private int transitionsDone = 0;
StateMachine(Table<S, S, List<Runnable>> transitions, S initialState) {
this.transitions = Objects.requireNonNull(transitions);
currentState = Objects.requireNonNull(initialState);
}
/**
* Tries to look for the shortest path from {@code currentState} to {@code state} and executing all registered
* transition actions.
*
* @param state the state to go to
* @return this
* @throws IllegalArgumentException if there is no path to {@code state}
*/
public StateMachine<S> go(S state) {
if (currentState != state) {
final List<Runnable> runnables = transitions.get(currentState, state);
if (runnables != null) {
// there's a direct path
log.trace("Going to state " + state);
runnables.forEach(Runnable::run);
currentState = state;
transitionsDone++;
} else {
// check if there is a path
List<S> intermediaryStates = getShortestStatePathBetween(currentState, state);
if (intermediaryStates != null) {
// the first item is the same as currentState, but since we ignore going to the current state,
// we don't have to strip it
intermediaryStates.forEach(this::go);
} else {
throw new IllegalArgumentException("There is no valid transition!");
}
}
}
return this;
}
/**
* Returns the current state the machine is in
*
* @return the current state of the machine
*/
public S getCurrentState() {
return currentState;
}
/**
* Returns how many transitions were done by this machine.
* <p>
* Most used for debugging purpouses.
*
* @return an integer greater or equal to 0, describing how many transitions were done
*/
public int getTransitionsDone() {
return transitionsDone;
}
/**
* Looks for the shortest available state path between the states {@code from} and {@code to}
* <p>
* Given the transitions {@code A -&gt; B -&gt; C -&gt; D -&gt; E}, a call to
* {@code getShortestStatePathBetween(B, D)} will return the list {@code [B, C, D]}
*
* @param from the state to start looking
* @param to the state to find a path to
* @return either a list describing the shortest path from {@code from} to {@code to} (including themselves),
* or null if no path could be found
*/
private List<S> getShortestStatePathBetween(S from, S to) {
final Set<S> reachableStates = getKeysWithoutValue(transitions.row(from));
if (reachableStates.contains(to)) {
final List<S> l = new ArrayList<>();
l.add(from);
l.add(to);
return l;
}
final List<List<S>> routes = new ArrayList<>();
for (S reachableState : reachableStates) {
final List<S> statesBetween = getShortestStatePathBetween(reachableState, to);
if (statesBetween != null) {
routes.add(statesBetween);
}
}
final Optional<List<S>> shortestRoute = getShortestList(routes);
if (shortestRoute.isPresent()) {
shortestRoute.get().add(0, from);
return shortestRoute.get();
} else {
return null;
}
}
protected static <T> Set<T> getKeysWithoutValue(Map<T, ?> map) {
return map.entrySet().stream().filter(e -> e.getValue() != null).map(Map.Entry::getKey).collect(Collectors
.toSet());
}
protected static <T> Optional<List<T>> getShortestList(List<List<T>> lists) {
return lists.stream().min((l1, l2) -> l1.size() - l2.size());
}
}
package example;
import com.google.common.collect.ArrayTable;
import com.google.common.collect.Table;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
/**
* Configuration class for creating enum based StateMachines.
* <p>
* To create a builder, call the static factory method {@link StateMachineBuilder#create(Class)}
* <p>
* Configuration is fluently done using {@link StateMachineBuilder#from(Enum)} and
* {@link at.vie.test.automation.util.fsm.StateMachineBuilder.TransitionAdder#to(Enum)}.
* <p>
* Example usage:
* <pre>
* StateMachineBuilder&lt;SomeEnum&gt; builder = StateMachineBuilder.create(SomeEnum.class);
*
* builder.from(SomeEnum.A).to(SomeEnum.B)
* .from(SomeEnum.B).to(SomeEnum.C).to(SomeEnum.D)
* .from(SomeEnum.A).to(SomeEnum.C, () -&gt; System.out.println(&quot;Transition to C&quot;);
*
* StateMachine&lt;SomeEnum<&gt; stateMachine = builder.startAt(SomeEnum.A);
* </pre>
*
* @param <S> the used Enum
*/
public class StateMachineBuilder<S extends Enum<S>> {
private final Table<S, S, List<Runnable>> transitions;
private StateMachineBuilder(S[] validStates) {
final List<S> valueList = Arrays.asList(validStates);
transitions = ArrayTable.create(valueList, valueList);
}
public static <T extends Enum<T>> StateMachineBuilder<T> create(Class<T> e) {
return new StateMachineBuilder<>(e.getEnumConstants());
}
public TransitionAdder from(S state) {
return new TransitionAdder(transitions.row(state));
}
/**
* Creates a new {@link StateMachine} using the current configuration
*
* @param initialState the starting state of the state machine
* @return a new StateMachine
*/
public StateMachine<S> startAt(S initialState) {
return new StateMachine<>(transitions, initialState);
}
public class TransitionAdder {
private final Map<S, List<Runnable>> transitionsTo;
private TransitionAdder(Map<S, List<Runnable>> transitionsTo) {
this.transitionsTo = transitionsTo;
}
/**
* Creates a new transition to {@code state}, executing the transition {@code transition} when
* switching the state to it
*
* @param state the state to create the transition to
* @param transition a functional interface which should be executed when transitioning to {@code state}
*/
public TransitionAdder to(S state, Runnable transition) {
List<Runnable> runnables = transitionsTo.get(state);
if (runnables == null) {
runnables = new ArrayList<>();
transitionsTo.put(state, runnables);
}
runnables.add(transition);
return this;
}
/**
* Creates a new transition to {@code state} without an action
*
* @param state the state to create the transition to
*/
public TransitionAdder to(S state) {
List<Runnable> runnables = transitionsTo.get(state);
if (runnables == null) {
runnables = new ArrayList<>();
transitionsTo.put(state, runnables);
}
return this;
}
/**
* @see StateMachineBuilder#from(Enum)
*/
public TransitionAdder from(S state) {
return StateMachineBuilder.this.from(state);
}
/**
* @see StateMachineBuilder#startAt(Enum)
*/
public StateMachine<S> startAt(S initialState) {
return StateMachineBuilder.this.startAt(initialState);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment