/* Copyright (c) 2008 Charles Rich and Worcester Polytechnic Institute.
 * All Rights Reserved.  Use is subject to license terms.  See the file
 * "license.terms" for information on usage and redistribution of this
 * file and for a DISCLAIMER OF ALL WARRANTIES.
 */
package edu.wpi.cetask;

import java.io.PrintStream;
import java.util.*;

// NB supports subplans not only from decompositions

public class Plan {
   
   private final Task goal;
   
   public Plan (Task goal) {
      if ( goal == null ) 
         throw new NullPointerException("Goal of plan cannot be null");
      this.goal = goal;
   }
 
   /**
    * @return the task which this plan is supposed to achieve
    */
   public Task getGoal () { return goal; }
   
   private boolean optional;
   
   private final List<Object> notes = new ArrayList<Object>();
   
   /**
    * Return list of notes to be added to verbose printing of this plan. This is
    * convenience feature for applications to manage by side effect.
    * 
    * @see #print(PrintStream)
    */
   public List<Object>getNotes () { return notes; }
      
   public void setOptional (boolean optional) {
      this.optional = optional;
   }
   
   public boolean isOptional () { 
      return optional || ( parent != null && parent.isOptional() ); 
   }
  
   // future improvement: allow multiple parents
   private Plan parent;
   private final List<Plan> children = new ArrayList<Plan>();
   
   public Plan getParent () { return parent; } 
     
   // whether this plan contributes to parent
   // set to false for leftover steps in failure-driven retry (see checkSuccess)
   private boolean contributes = true;

   /**
    * Test whether given plan can be reached from this plan by following parents.
    * Note plan is <em>not</em> its own ancestor.
    */
   public boolean isAncestor (Plan plan) {
      return plan == parent || (parent != null && parent.isAncestor(plan));
   }
   
   /**
    * Test whether given plan can be reached from this plan by following children.
    * Note plan is <em>not</em> its own descendant.
    */
   public boolean isDescendant (Plan plan) {
      for (Plan child : children)
         if ( child == plan || child.isDescendant(plan) ) return true;
      return false;
   }
  
   /**
    * Return path from this plan to given plan iff it is a descendant; otherwise 
    * null.  Path does <em>not</em> include this plan or descendant and thus will 
    * be empty if given plan is child.
    */
   public Stack<Plan> pathToDescendant (Plan plan) {
      Stack<Plan> path = new Stack<Plan>();
      return pathToDescendant(plan, path, this) ? path : null;
   }
   
   private boolean pathToDescendant (Plan plan, Stack<Plan> path, Plan root) {
      for (Plan child : children)
         if ( child == plan || child.pathToDescendant(plan, path, root) ) {
            if ( this != root ) path.push(this);
            return true;
         }
      return false;
   }
   
   /**
    * @return iterator for children of this plan.
    */
   public Iterator<Plan> children () { return children.iterator(); }
 
   /**
    * Add given plan as child of this plan.
    */
   public void add (Plan plan) { 
      if ( plan.parent != null ) 
         throw new IllegalArgumentException(
               "Plan already has a parent: "+plan.parent);
      plan.parent = this;
      children.add(plan);
   }
   
   /**
    * Remove given child of this plan.
    * 
    * @param child - must be child of this plan
    */
   public void remove (Plan child) {
      if ( !children.contains(child) )
         throw new IllegalArgumentException(child+" is not child of "+this);
      children.remove(child);
      child.parent = null;
   }
   
   // usually siblings (common parent), but not checking
   private final List<Plan> required = new ArrayList<Plan>();
   
   public void requires (Plan plan) {
      required.add(plan);
   }
   
   public boolean isRequired (Plan plan) {
      return required.contains(plan);
   }
   
   /**
    * System executes script for goal of this plan.
    */
   public void execute () {
      goal.execute();
      checkSuccess();
   }
   
   public boolean occurred () { return goal.occurred(); }
   
   /**
    * Tests whether plans which require this plan should become live.
    */
   public boolean isDone () {
      return ( occurred() 
            || Utils.isTrue(goal.isAchieved()) 
            || isComplete() )
            && !isFailed();
   }
   
   public boolean isFailed () {
      return Utils.isFalse(goal.getSuccess());
   }

   public boolean isLive () {
      Boolean live = goal.engine.isLive(this); // check cached value
      if ( live != null ) return live;
      // do not call isDone() or isLive() below to avoid infinite recursion
      live = isLive(this) && !isComplete() && (parent == null || isLive(parent));
      goal.engine.setLive(this, live); // store cache
      return live;
   }
   
   private static boolean isLive (Plan plan) {
      return !plan.occurred()  
         && !plan.isPassed()
         && plan.getBlockers().isEmpty()
         && (plan.isStarted() || !Utils.isFalse(plan.goal.isApplicable()))
         && !Utils.isTrue(plan.goal.isAchieved())
         && !plan.isFailed();
   }

   /**
    * Tests whether popping plan from the stack would would constitute an
    * unnecessary focus shift.
    * 
    * @return true iff popping would <em>not</em> be an unnecessary focus
    *         shift.
    */
   public boolean isPoppable () { return !isLive() || isDone(); }

   /**
    * Tests whether this plan has been decomposed (either by applying a
    * DecompositionClass or procedurally) and all the non-optional steps
    * are done. Note that even if this method returns true (and this
    * plan is therefore done), it may still have optional ("trailing") children
    * that are live.
    * 
    * @see #isDecomposed()
    * @see #isDone()
    * @see #isPassed()
    */
   public boolean isComplete () {
      if ( !decomposed ) return false;
      // need to ignore failed children from failed decomposition
      if ( decomp == null ) {
         for (Plan child: children)
            if ( !isComplete(child) ) return false;
      } else if ( !failed.contains(decomp) ) { 
         for (Task step : decomp.getSteps()) 
            if ( !isComplete(childWithGoal(step)) ) return false;
      }
      return true;
   }

   private static boolean isComplete (Plan child) {
      return child.isDone() || child.isOptional();
   }
   
   public boolean isPassed () {
      if ( parent != null ) {
         for (Plan sibling : parent.children)
            if ( (sibling.isRequired(this) && sibling.isStarted()) ) return true;
         if ( parent.isPassed() ) return true; // must recurse upward in tree
      }
      return false;
   }
   
   public boolean isBlocked () {
      for (Plan plan : required)
         if ( plan.isOptional() ) { if ( plan.isBlocked() ) return true; }
         else if ( !plan.isDone() ) return true;
      return false;
   }
   
   public List<Plan> getBlockers () {
      List<Plan> blockers = new ArrayList<Plan>();
      for (Plan plan : required) 
         if ( plan.isOptional() ) blockers.addAll(plan.getBlockers());
         else if ( !plan.isDone() ) blockers.add(plan);
      return blockers;
   }
   
   /**
    * Return list of live children of this plan.
    */
   public List<Plan> getLive () {
      List<Plan> live = new ArrayList<Plan>();
      for (Plan child : children)
         if ( child.isLive() ) live.add(child);
      return live;
   }
    
   /**
    * Return list of live descendants of this plan.
    */
   public List<Plan> getLiveDescendants () {
      return getLiveDescendants(new ArrayList<Plan>());
   }
   
   private List<Plan>getLiveDescendants (List<Plan> live) {
      for (Plan child : children) {
         child.getLiveDescendants(live);
         if ( child.isLive() ) live.add(child);
      }
      return live;
   }
 
   /**
    * Test whether this plan has any live descendants.
    */
   public boolean hasLiveDescendants () {
      for (Plan child : children)
         if ( child.isLive() || child.hasLiveDescendants() ) return true;
      return false;
   }
   
   /**
    * Test whether this plan has any failed contributing children.
    */
   public boolean hasFailed () {
      for (Plan child : children)
         if ( child.contributes && child.isFailed() ) return true;
      return false;
   }
   
   public boolean isStarted () {
      if ( occurred() ) return true;
      for (Plan child : children)
         if ( child.isStarted() ) return true;
      return false;
   }
   
   /**
    * Test whether this plan has any remaining steps that could be executed
    */
   public boolean isExhausted () {
      return isFailed() || Utils.isTrue(goal.getSuccess()) || isMoot()
        || isBlocked() || ( goal.getType().isPrimitive() && !isLive() );
   }

   /**
    * Tests whether this plan is incomplete, but does not need to be executed
    * because all the reasons for doing it have already been achieved or are no
    * longer desired. Currently, this means that there is an achieved or
    * occurred plan looking "up" from this plan. 
    */
   public boolean isMoot () { return !isComplete() && isMooted();  }
   
   private boolean isMooted () {
      return parent != null && 
        ( parent.occurred() || Utils.isTrue(parent.getGoal().getSuccess())
              || parent.isMooted());
   }
   
   /**
    * Tests whether this plan is or is expected to ever become live.  For
    * example, a plan which has been passed (required successor started) can 
    * never become live.  Used mainly for status.
    */
   public boolean isExpected () {
      return contributes &&
         !( occurred()  
            || goal.getSuccess() != null // already succeeded or failed
            // don't expect if postcondition currently true
            || Utils.isTrue(goal.isAchieved())
            // or optional step and precondition currently false 
            || (optional && Utils.isFalse(goal.isApplicable())) //sic not isOptional
            || isPassed()
            // trailing optionals not expected
            || (isComplete() && !hasExpected())
            ); 
   }
   
   /**
    * Test whether this plan has immediate subplan which is expected.
    * 
    * @see #isExpected()
    */
   public boolean hasExpected () {
      for (Plan child : children) if ( child.isExpected() ) return true;
      return false;
   }
   
   public List<Plan> getExpected () {
      List<Plan> expected = new ArrayList<Plan>(children.size());
      for (Plan child : children) if ( child.isExpected() ) expected.add(child);
      // sort live plans to front
      Collections.sort(expected, new Comparator<Plan>() { 
         // note this comparator imposes orderings inconsistent with equals
         public int compare (Plan p, Plan q) { 
            return p.isLive() ? ( q.isLive() ? 0 : -1 ) :
               q.isLive() ? ( p.isLive() ? 0 : 1 ) :
                  0;
         }
      });
      return expected;
   }
   
   /**
    * Recognize given task as matching this plan and copy slot values. If given
    * task is occurrence, then also check for failure (false postcondition) in
    * ancestor plans.
    */
   public void recognize (Task task) {
      goal.copySlotValues(task);
      goal.engine.clearLive();
      // this is the only moment to check for failure
      if ( task.occurred() ) checkSuccess();
   }
   
   // TODO When to set success slot to true for unstarted
   //      plans (fortuitous success)
   
   // TODO Add more general failure driven retry?
   
   private void checkSuccess () {
      if ( !hasLiveDescendants() ) {
         // no more chances to succeed
         Boolean success = goal.isAchieved();
         if ( success != null ) 
            // if condition is unknown, then respect existing value of 'success'
            // slot, since it may come from communication
            goal.setSuccess(success);
         if ( decomp != null && 
               (Utils.isFalse(success) || (success == null && hasFailed())) ) {
            if ( failed == Collections.EMPTY_LIST ) failed = new ArrayList<Decomposition>();
            failed.add(decomp);
            decomp.setFailed(true);
            goal.setSuccess(false);
            for (Decomposition.Step step : decomp.getSteps()) {
               Plan child = childWithGoal(step);
               if ( child.isStarted() ) child.contributes = false;
               else remove(child);
            }
            // check for alternative decompositions
            // note success slot is still false for applicability conditions
            List<DecompositionClass> decomps = getDecompositions();
            if ( !decomps.isEmpty() ) {
               for (String name : goal.getType().getOutputNames())
                  goal.deleteSlotValue(name);
               goal.deleteSlotValue("success");
               apply(decomps.get(0));
            }            
         }
      }
      if ( parent != null ) parent.checkSuccess(); // recurse up tree
   }

   private List<DecompositionClass> getDecompositions () {
      List<DecompositionClass> decomps = goal.getDecompositions();
      // remove failed and inapplicable decompositions
      loop: 
         for (Iterator<DecompositionClass> i = decomps.iterator();
           i.hasNext();) {
         DecompositionClass next = i.next();  // sic
         for (Decomposition fail : failed)
            if ( fail.getType().equals(next) ) {
               i.remove(); continue loop;
            }
         if ( Utils.isFalse(next.isApplicable(goal)) ) i.remove();
      }
      return decomps;
   }
   
   private Decomposition decomp; 
   
   private List<Decomposition> failed = Collections.emptyList();
   
   // Allow for procedural decomposition
   private boolean decomposed;
   public boolean isDecomposed () { return decomposed; }
   public void setDecomposed (boolean decomposed) {
      this.decomposed = decomposed;
   }
   
   public Decomposition getDecomposition () { return decomp; }
   
   public void apply (DecompositionClass type) {
      decomp = new Decomposition(type, goal);
      decomposed = true;
      Iterator<TaskClass> types = type.getStepTypes().iterator();
      for (String name : type.getStepNames()) {
         TaskClass task = types.next();
         Plan child = addStep(task, name, type.isOptionalStep(name));
         decomp.putStep(name, (Decomposition.Step) child.getGoal());
         for (String required : type.getRequiredStepNames(name))
            child.requires(childWithGoal(decomp.getStep(required)));
         // TODO handle repeatable steps once in DecompositionClass instead by 
         //      creating additional steps with names such as "step<char>1", etc. with 
         //      appropriate ordering and binding for inputs only (where <char> is
         //      a character not allowed in XML names, but allowed in JavaScript ids)
         //      Could also handle outputs from _last_ step
         int max = type.getMaxOccursStep(name);
         if ( max < 0 ) {
            // TODO handle unbounded case (will need some sort of lazy mechanism)
            System.err.print("WARNING: Unbounded maxOccurs not supported; approximating 10");
            max = 10;
         }
         for (int i = max; i-- > 1;) { // add optional steps
            Plan requires = child;
            child = addStep(task, name, true);
            child.requires(requires); 
         }
      }
   }
   
   private Plan addStep (TaskClass type, String name, boolean optional) {
      Decomposition.Step step = decomp.new Step(type, name);
      Plan plan = new Plan(step);
      add(plan);
      plan.setOptional(optional);
      return plan;
   }
   
   private Plan childWithGoal (Task goal) {
      for (Plan child : children)
         if ( child.goal == goal) return child;
      throw new IllegalStateException("Expected child with goal "+goal);
   }

   public void decomposeAll () {
      decomposeAll(new Stack<DecompositionClass>());
   }
   
   private void decomposeAll (Stack<DecompositionClass> stack) {
      // recursively apply all decompositions that do not involve choices
      // do not decompose done plans
      if ( !(isDecomposed() || isDone()) ) {
         List<DecompositionClass> decomps = goal.getType().getDecompositions();
         // if only one known decomposition for goal type, apply it now if applicable
         if ( decomps.size() == 1 ) {
            DecompositionClass only = decomps.get(0);
            if ( !Utils.isFalse(only.isApplicable(goal)) ) {
               Plan focus = goal.engine.getFocus();
               // inhibit infinite recursion, but allow incremental expansion
               // at children of focus
               if ( !stack.contains(only) ||
                     (focus != null && focus.children.contains(this)) )
                  apply(only);
            }
         }
      }
      if ( decomp != null ) stack.push(decomp.getType());
      for (Plan child : children) child.decomposeAll(stack);
      if ( decomp != null ) stack.pop();
   }

   /**
    * Return list of plans in this plan tree whose goal matches given task.
    * 
    * @param onlyLive only search live plans
    */
   public List<Plan> findMatches (Task task, boolean onlyLive) {
      return findMatches(task, onlyLive, null);
   }
   
   /**
    * Return list of plans in this plan tree whose goal matches given task.
    * 
    * @param onlyLive only search live plans
    * @param exclude do not search given plan
    */
   public List<Plan> findMatches (Task task, boolean onlyLive, Plan exclude) {
      return findMatches(task, new ArrayList<Plan>(), onlyLive, exclude);
   }
   
   private List<Plan> findMatches (Task task, List<Plan> plans, 
         boolean onlyLive, Plan exclude) {
      if ( this == exclude || (onlyLive && !isLive()) ) return plans;
      if ( goal.matches(task) ) plans.add(this);
      for (Plan child : children) child.findMatches(task, plans, onlyLive, exclude);
      return plans;
   }
   
   @Override
   public String toString () { 
      return decomp == null ||
         // suppress unique known decomposition
         (!TaskEngine.VERBOSE && goal.getType().getDecompositions().size() == 1) ? 
            goal.toString() : goal+" by "+decomp; 
   }

   /**
    * @see #getNotes()
    */
   public void print (PrintStream stream) { print(stream, 0, true, false); }
   
   public void print (PrintStream stream, int indent, boolean recurse, boolean format) {
      for (int i = indent; i-- > 0;) stream.print("   ");
      stream.print(format ? Utils.capitalize(goal.format()) : this);
      if ( optional ) stream.print(" [optional]"); //sic not isOptional()
      if ( isLive() ) stream.print(" [live]");
      else {
         stream.print(Utils.isTrue(goal.getSuccess()) ? " [succeeded]" :
            isFailed() ? " [failed]" :
               isDone()? " [done]" : "");
      };
      if ( !notes.isEmpty() ) { stream.print(' '); stream.print(notes); }
      if ( recurse ) {
         stream.println();
         if ( !children.isEmpty() ) {
            indent++;
            for (Plan child : children) child.print(stream, indent, recurse, format);
         }
      }
   }
   
}
