/*
 * Copyright 2016, Google Inc.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 *     
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package kiwi.search;

import java.util.function.Predicate;

import kiwi.propagation.PropagationQueue;
import kiwi.trail.Trail;
import kiwi.util.Action;
import kiwi.util.Stack;

public class DFSearch {

  private final PropagationQueue pQueue;
  private final Trail trail;

  private final Stack<Decision> decisions = new Stack<>();
  private final Stack<Action> solutionActions = new Stack<>();
  
  private Objective objective = null;

  public DFSearch(PropagationQueue pQueue, Trail trail) {
    this.pQueue = pQueue;
    this.trail = trail;
  }
  
  public void addSolutionAction(Action action) {
    solutionActions.push(action);
  }
  
  public void foundSolution(SearchStats stats) {
    stats.nSolutions++;
    solutionActions.forEach(action -> action.execute());
    if (objective != null) {
      objective.tighten();
    }
  }
  
  public void setObjective(Objective obj) {
    this.objective = obj;
  }
  
  private boolean propagate() {
    // Propagate the objective only if it is not null.
    boolean feasible = objective == null || objective.propagate();
    // Propagate the propagators only if the problem is still feasible.
    return feasible && pQueue.propagate();
  }

  /** Starts the search */
  public SearchStats search(Heuristic heuristic, Predicate<SearchStats> stopCondition) {
    SearchStats stats = new SearchStats();
    
    stats.startTime = System.currentTimeMillis();

    // Perform root propagation.
    if (!propagate()) {
      return stats;
    }

    // Check if the root is a solution. 
    // If it is not, push the next decisions to try on the decisions stack.
    if (heuristic.pushDecisions(decisions)) {
      foundSolution(stats);
      return stats;
    }

    // Save the root state.
    trail.newLevel();

    // Start the search.
    while (!decisions.isEmpty() && !stopCondition.test(stats)) {
      stats.nNodes++;

      // Apply the next decision and propagate.
      if (!decisions.pop().apply() || !pQueue.propagate()) {
        trail.undoLevel();
        stats.nFails++;
        continue;
      }

      // Check if the node is a solution. If not, it pushes
      // the next decisions to try on the decisions stack.
      if (heuristic.pushDecisions(decisions)) {
        foundSolution(stats);
        trail.undoLevel();
        continue;
      }

      // Save the node state.
      trail.newLevel();
    }

    // The search is complete if there's no remaining decisions to be applied.
    stats.completed = decisions.isEmpty();
    
    // Clear the remaining decisions (if the search is incomplete) and restore
    // the state of the root node.
    trail.undoAll();
    decisions.clear();
    
    // We consider that restoring the root state is part of the search hence 
    // we only compute the total time once the search has been reset.
    stats.searchTime = System.currentTimeMillis() - stats.startTime;
    
    return stats;
  }
}

@@ -2116,98 +2116,34 @@
 oot 
-is a solution. %0A    // If it is not, push the next decisions to try on the decisions stack
+node is already a solution
 .%0A  
@@ -2214,36 +2214,16 @@
 stats);%0A
-      return stats;%0A
     %7D%0A%0A 
@@ -2296,16 +2296,179 @@
  search.
+ The search terminates if the stack of decisions%0A    // is empty (meaning that the search tree has been entirely explored) or %0A    // if the stop condition is met.
 %0A    whi
@@ -2591,24 +2591,111 @@
 d propagate.
+ This can result in a failed%0A      // node in which case we restore the previous state.
 %0A      if (!
@@ -2722,23 +2722,16 @@
 y() %7C%7C !
-pQueue.
 propagat
@@ -2749,196 +2749,194 @@
     
-trail.undoLevel();%0A        stats.nFails++;%0A        continue;%0A      %7D%0A%0A      // Check if the node is a solution. If not, it pushes%0A      // the next decisions to try on the decisions stack.
+stats.nFails++;%0A        trail.undoLevel();%0A        continue;%0A      %7D%0A%0A      // At this point we know that the new node is not failed and we check %0A      // that it is a solution or not. 
 %0A   
@@ -3077,27 +3077,102 @@
  // 
-Save the node state
+The node is neither a failed node or a solution so we continue to %0A      // explore the branch
 .%0A  

Fix a bug in DFSearch and add some comments.