/*
    * Copyright (C) 2006  Tom Gibara
    *
    * This library is free software; you can redistribute it and/or
    * modify it under the terms of the GNU Lesser General Public
    * License as published by the Free Software Foundation; either
    * version 2.1 of the License, or (at your option) any later version.
    *
    * This library is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   * Lesser General Public License for more details.
   *
   * You should have received a copy of the GNU Lesser General Public
   * License along with this library; if not, write to the Free Software
   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
   */
  
  package com.tomgibara.pronto.state.impl;
  
  import java.util.Collections;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  
  import com.tomgibara.pronto.state.PathType;
  import com.tomgibara.pronto.state.ProntoStateException;
  import com.tomgibara.pronto.state.StateGraph;
  import com.tomgibara.pronto.state.StateGraphEditor;
  import com.tomgibara.pronto.state.StateTransition;
  import com.tomgibara.pronto.util.Arguments;
  
  public class StateGraphImpl<S, L> implements StateGraph<S, L> {
  
      // fields
  
      private final HashSet<S> states;
  
      private final HashSet<StateTransitionImpl<S, L>> transitions;
  
      private final Set<S> publicStates;
  
      private final Set<StateTransition<S, L>> publicTransitions;
  
      private final PathFinder<S, L> pathFinder;
  
      // constructors
  
      StateGraphImpl() {
          states = new HashSet<S>();
          transitions = new HashSet<StateTransitionImpl<S, L>>();
          pathFinder = new PathFinder<S, L>(states, transitions);
  
          publicStates = Collections.unmodifiableSet(states);
          publicTransitions = Collections.unmodifiableSet(castFromImpl(transitions));
      }
  
      StateGraphImpl(final Set<S> states, final Set<StateTransitionImpl<S, L>> transitions)
              throws IllegalArgumentException {
          // we don't do the work of checking that the two sets are consistent,
          // because the editor should have done that
          // we do test for null, because it's quick to do
          Arguments.notNull(states, "states");
          Arguments.notNull(transitions, "transitions");
  
          this.states = new HashSet<S>(states);
          this.transitions = new HashSet<StateTransitionImpl<S, L>>(transitions);
          pathFinder = new PathFinder<S, L>(states, transitions);
  
          publicStates = Collections.unmodifiableSet(states);
          publicTransitions = Collections.unmodifiableSet(castFromImpl(transitions));
      }
  
      // state graph methods
  
      public Set<S> states() {
          return publicStates;
      }
  
      public Set<S> getTerminalStates() {
          HashSet<S> states = new HashSet<S>(this.states);
          for (StateTransitionImpl<S, L> transition : transitions) {
              states.remove(transition.getSource());
          }
          return Collections.unmodifiableSet(states);
      }
  
      public S getTerminalState() throws ProntoStateException {
          Set<S> terminalStates = getTerminalStates();
          int size = terminalStates.size();
          if (size == 0) return null;
          if (size == 1) return terminalStates.iterator().next();
          throw new ProntoStateException("Ambiguous: more than one terminal state: " + terminalStates);
      }
  
      public Set<S> getInitialStates() {
          HashSet<S> states = new HashSet<S>(this.states);
          for (StateTransitionImpl<S, L> transition : transitions) {
              states.remove(transition.getTarget());
         }
         return Collections.unmodifiableSet(states);
     }
 
     public S getInitialState() throws ProntoStateException {
         Set<S> initialStates = getInitialStates();
         int size = initialStates.size();
         if (size == 0) return null;
         if (size == 1) return initialStates.iterator().next();
         throw new ProntoStateException("Ambiguous: more than one initial state: " + initialStates);
     }
 
     public StateTransition<S, L> getTransition(final S source, final L label, final S target) {
         StateTransitionImpl<S, L> transition = new StateTransitionImpl<S, L>(source, label, target);
         return transitions.contains(transition) ? transition : null;
     }
 
     public Set<StateTransition<S, L>> getTransitionsMatching(final S source, final L label, final S target) {
         if (source == null && label == null && target == null) return transitions();
         return Collections.unmodifiableSet(getTransitionsFiltered(new TransitionFilter<S, L>() {
             public boolean accept(final StateTransitionImpl<S, L> transition) {
                 if (source != null && !transition.getSource().equals(source)) return false;
                 if (label != null && !transition.getLabel().equals(label)) return false;
                 if (target != null && !transition.getTarget().equals(target)) return false;
                 return true;
             }
         }));
     }
 
     public Set<StateTransition<S, L>> transitions() {
         return publicTransitions;
     }
 
     public Set<List<StateTransition<S, L>>> getMultiPaths(final Set<S> initial, final Set<S> terminal,
             final PathType type) {
         Arguments.notNull(initial, "initial");
         Arguments.notNull(type, "type");
 
         if (!states.containsAll(initial)) throw new IllegalArgumentException(
                 "Initial states not a subset of graph states.");
         if (terminal != null && !states.containsAll(terminal)) throw new IllegalArgumentException(
                 "Terminal states not a subset of graph states.");
 
         // accumulates the paths we have found
         final HashSet<List<StateTransition<S, L>>> paths = new HashSet<List<StateTransition<S, L>>>();
         // iterate over the initial states so that we can find paths from each
         // one in turn
         for (S state : initial) {
             pathFinder.addPathsBetween(state, terminal, paths, type);
         }
         // all the heavy lifting has been done for us
         return Collections.unmodifiableSet(paths);
     }
 
     public Set<List<StateTransition<S, L>>> getPaths(final S initial, final S terminal, final PathType type) {
         Arguments.notNull(initial, "initial");
         return getMultiPaths(Collections.singleton(initial), terminal == null ? null : Collections.singleton(terminal),
                 type);
     }
 
     public List<StateTransition<S, L>> getPath(final S initial, final S terminal, final PathType type)
             throws ProntoStateException {
         Set<List<StateTransition<S, L>>> paths = getPaths(initial, terminal, type);
         int size = paths.size();
         if (size == 0) return null;
         if (size == 1) return paths.iterator().next();
         throw new ProntoStateException("Ambiguous: more than one path: " + paths);
     }
 
     public StateGraphEditor<S, L> newEditor() {
         return new StateGraphEditorImpl<S, L>(this);
     }
 
     // object methods
 
     @SuppressWarnings("unchecked")
     @Override
     public boolean equals(final Object obj) {
         if (this == obj) return true;
         if (!(obj instanceof StateGraphImpl)) return false;
         StateGraphImpl<S, L> that = (StateGraphImpl<S, L>) obj;
         if (!this.states.equals(that.states)) return false;
         if (!this.transitions.equals(that.transitions)) return false;
         return true;
     }
 
     @Override
     public int hashCode() {
         return states.hashCode() ^ transitions.hashCode();
     }
 
     @Override
     public String toString() {
         return "[states: " + states + " transitions: " + transitions + "]";
     }
 
     // private utility methods
 
     private Set<StateTransition<S, L>> getTransitionsFiltered(final TransitionFilter<S, L> filter) {
         Set<StateTransition<S, L>> set = new HashSet<StateTransition<S, L>>();
         for (StateTransitionImpl<S, L> transition : transitions) {
             if (filter.accept(transition)) set.add(transition);
         }
         return set;
     }
 
     @SuppressWarnings("unchecked")
     // sleight of hand to dupe the generic type system
     private Set<StateTransition<S, L>> castFromImpl(final Set<StateTransitionImpl<S, L>> set) {
         return (Set) set;
     }
 }