/*
    * Created on 30-Oct-2006
    *
    */
   package com.tomgibara.pronto.state.impl;
   
   import java.util.ArrayList;
   import java.util.Collections;
   import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Set;
  
  import com.tomgibara.pronto.state.PathType;
  import com.tomgibara.pronto.state.StateTransition;
  
  class PathFinder<S, L> {
  
      private final Set<S> states;
  
      private final Set<StateTransitionImpl<S, L>> transitions;
  
      private final HashMap<S, Set<StateTransitionImpl<S, L>>> transitionStates
          = new HashMap<S, Set<StateTransitionImpl<S, L>>>();
  
      PathFinder(final Set<S> states, final Set<StateTransitionImpl<S, L>> transitions) {
          this.states = states;
          this.transitions = transitions;
      }
  
      void addPathsBetween(final S initialState, final Set<S> finalStates,
              final HashSet<List<StateTransition<S, L>>> paths, final PathType type) {
          // start at the initial state supplied
          S state = initialState;
          // a collection of iterators over the nodes we haven't exhausted yet
          final LinkedList<Iterator<StateTransitionImpl<S, L>>> iterators =
              new LinkedList<Iterator<StateTransitionImpl<S, L>>>();
          // the list of transitions that forms the path thus far
          final LinkedList<StateTransitionImpl<S, L>> traversed =
              new LinkedList<StateTransitionImpl<S, L>>();
          // a set of the transitions that are in the path thus far, or null if we don't care
          final HashSet<StateTransitionImpl<S, L>> uniqueTransitions =
              type == PathType.uniqueTransitions ? new HashSet<StateTransitionImpl<S, L>>() : null;
          // a set of the states that are in the path thus far, or null if we don't care
          final HashSet<S> uniqueStates =
              type == PathType.uniqueStates || type == PathType.strictlyUniqueStates ? new HashSet<S>() : null;
  
          // if we are looking for strict uniqueness then we cannot visit the initial node twice
          if (type == PathType.strictlyUniqueStates) uniqueStates.add(initialState);
  
          while (true) {
              // i is a reference to the 'active' iterator which we obtain on each
              // pass from the current state's transitions
              Iterator<StateTransitionImpl<S, L>> i = getTransitionsFromState(state).iterator();
              // the iteratot i is always the last iterator in our list
              iterators.add(i);
              // check for a final state - we may need to record a path
              if (traversed.size() > 0 && (finalStates == null || finalStates.contains(state))) {
                  // our criteria are met, so convert to a path ...
                  List<StateTransition<S, L>> path = new ArrayList<StateTransition<S, L>>(traversed);
                  // ... and record it (unmodifiably)
                  paths.add(Collections.unmodifiableList(path));
              }
  
              // get the next transition
              StateTransitionImpl<S, L> transition = null;
              // find a non-exhausted iterator
              outer: while (true) {
                  while (i.hasNext()) {
                      transition = i.next();
                      switch (type) {
                      case uniqueStates:
                      case strictlyUniqueStates:
                          if (!uniqueStates.contains(transition.getTarget())) break outer;
                          break;
                      case uniqueTransitions:
                          if (!uniqueTransitions.contains(transition)) break outer;
                          break;
                      default:
                          throw new IllegalStateException(String
                                  .format("Unexpected PathType enumeration value: %s", type));
                      }
                  }
  
                  // i is empty, we need to find our next transition
                  // this iterator is exhausted, remove it
                  iterators.removeLast();
  
                  if (iterators.isEmpty()) {
                      // no more iterators, our work is done
                      /* EARLY RETURN */
                      return;
                  }
  
                  // get the new last iterator
                  i = iterators.getLast();
  
                 // we need to remove the last traversed state too
                 StateTransitionImpl<S, L> trans = traversed.removeLast();
 
                 // and tidy-up any verifying sets
                 switch (type) {
                 case uniqueStates:
                 case strictlyUniqueStates:
                     uniqueStates.remove(trans.getTarget());
                     break;
                 case uniqueTransitions:
                     uniqueTransitions.remove(trans);
                     break;
                 default:
                     throw new IllegalStateException(String.format("Unexpected PathType enumeration value: %s", type));
                 }
             }
 
             // make the transition
             traversed.add(transition); // record the transition
             state = transition.getTarget(); // update our state
             //update the uniqueness set
             switch (type) {
             case uniqueStates:
             case strictlyUniqueStates:
                 uniqueStates.add(state);
                 break;
             case uniqueTransitions:
                 uniqueTransitions.add(transition);
                 break;
             default:
                 throw new IllegalStateException(String.format("Unexpected PathType enumeration value: %s", type));
             }
         }
     }
 
     Set<StateTransitionImpl<S, L>> getTransitionsFromState(final S state) {
         Set<StateTransitionImpl<S, L>> set = transitionStates.get(state);
         if (set == null) {
             set = new HashSet<StateTransitionImpl<S, L>>();
             for (StateTransitionImpl<S, L> transition : transitions) {
                 if (transition.getSource().equals(state)) set.add(transition);
             }
         }
         return set;
     }
 
 }