// Path: src/main/java/kiwi/propagation/PropagationQueue.java
// public class PropagationQueue {
//   
//   // The propagation queue that contains all the propagators waiting for
//   // propagation. A propagator is considered to be enqueued only if its
//   // enqueued boolean is set to true.
//   private final ArrayDeque<Propagator> queue = new ArrayDeque<Propagator>();
// 
//   /**
//    * Enqueues the propagator for propagation.
//    * 
//    * <p>
//    * This method does nothing if the propagator is already enqueued.
//    * </p>
//    * 
//    * @param propagator the propagator to be scheduled for propagation.
//    */
//   public void enqueue(Propagator propagator) {
//     if (!propagator.enqueued) {
//       queue.addLast(propagator);
//       propagator.enqueued = true;
//     }
//   }
// 
//   /**
//    * Propagates the pending propagators.
//    * 
//    * <p>
//    * Propagate all the propagators contained in the propagation queue.
//    * Propagation is likely to enqueue additional propagators while it is
//    * running. The propagation stops either when the queue is empty, or if a
//    * propagator failed (meaning that the problem is infeasible).
//    * </p>
//    * 
//    * <p>
//    * The method returns true if the propagation succeeded or false if a
//    * propagator failed. The queue is empty at the end of the propagation and all
//    * propagators contained in the queue have their enqueued boolean set to
//    * false.
//    * </p>
//    * 
//    * @return true if propagation succeeded, false otherwise.
//    */
//   public boolean propagate() {
//     boolean feasible = true;
//     while (!queue.isEmpty()) {
//       Propagator propagator = queue.removeFirst();
//       // Dequeue the propagator only if it is not idempotent. This allows the
//       // propagator to enqueue itself back in the propagation queue if it
//       // changed the domain of at least one of its variable.
//       propagator.enqueued = propagator.idempotent;
//       // Propagate only if the problem is still feasible.
//       feasible = feasible && propagator.propagate();
//       // Dequeue the propagator no matter what.
//       propagator.enqueued = false;
//     }
//     return feasible;
//   }
// }
// 
// Path: src/main/java/kiwi/trail/Trail.java
// public class Trail {
// 
//   private long timestamp = 0L;
// 
//   private final Stack<Change> changes = new Stack<Change>();
//   private final StackInt levels = new StackInt();
// 
//   public long getTimestamp() {
//     return timestamp;
//   }
// 
//   public void store(Change change) {
//     changes.push(change);
//   }
// 
//   public void newLevel() {
//     levels.push(changes.getSize());
//     timestamp++;
//   }
// 
//   public void undoLevel() {
//     if (levels.getSize() > 0)
//       undoUntil(levels.pop());
//     timestamp++;
//   }
// 
//   public void undoAll() {
//     while (levels.getSize() > 0) {
//       undoUntil(levels.pop());
//     }
//     timestamp++;
//   }
// 
//   private void undoUntil(int size) {
//     while (changes.getSize() > size) {
//       changes.pop().undo();
//     }
//   }
// }
// 
// Path: src/main/java/kiwi/util/Action.java
// public interface Action {
//   public void execute();
// }
// 
// Path: src/main/java/kiwi/util/Stack.java
// public class Stack<T> {
// 
//   private Object[] array = new Object[16];
// 
//   private int index = 0;
// 
//   public int getSize() {
//     return index;
//   }
// 
//   public boolean isEmpty() {
//     return index == 0;
//   }
// 
//   @SuppressWarnings("unchecked")
//   public T top() {
//     return (T) array[index - 1];
//   }
// 
//   public void push(T elem) {
//     if (index == array.length) {
//       growStack();
//     }
//     array[index] = (Object) elem;
//     index++;
//   }
// 
//   public void clear() {
//     while (index > 0) {
//       index--;
//       array[index] = null;
//     }
//   }
// 
//   @SuppressWarnings("unchecked")
//   public T pop() {
//     return (T) array[--index];
//   }
// 
//   @SuppressWarnings("unchecked")
//   public void forEach(Consumer<T> c) {
//     for (int i = 0; i < index; i++) {
//       c.accept((T) array[i]);
//     }
//   }
// 
//   private void growStack() {
//     Object[] newArray = new Object[index * 2];
//     System.arraycopy(array, 0, newArray, 0, index);
//     array = newArray;
//   }
// }


import java.util.function.Predicate;
import kiwi.propagation.PropagationQueue;
import kiwi.trail.Trail;
import kiwi.util.Action;
import kiwi.util.Stack;
/*
 * 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;



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;
  }
  
// Path: src/main/java/kiwi/propagation/PropagationQueue.java
// public class PropagationQueue {
//   
//   // The propagation queue that contains all the propagators waiting for
//   // propagation. A propagator is considered to be enqueued only if its
//   // enqueued boolean is set to true.
//   private final ArrayDeque<Propagator> queue = new ArrayDeque<Propagator>();
// 
//   /**
//    * Enqueues the propagator for propagation.
//    * 
//    * <p>
//    * This method does nothing if the propagator is already enqueued.
//    * </p>
//    * 
//    * @param propagator the propagator to be scheduled for propagation.
//    */
//   public void enqueue(Propagator propagator) {
//     if (!propagator.enqueued) {
//       queue.addLast(propagator);
//       propagator.enqueued = true;
//     }
//   }
// 
//   /**
//    * Propagates the pending propagators.
//    * 
//    * <p>
//    * Propagate all the propagators contained in the propagation queue.
//    * Propagation is likely to enqueue additional propagators while it is
//    * running. The propagation stops either when the queue is empty, or if a
//    * propagator failed (meaning that the problem is infeasible).
//    * </p>
//    * 
//    * <p>
//    * The method returns true if the propagation succeeded or false if a
//    * propagator failed. The queue is empty at the end of the propagation and all
//    * propagators contained in the queue have their enqueued boolean set to
//    * false.
//    * </p>
//    * 
//    * @return true if propagation succeeded, false otherwise.
//    */
//   public boolean propagate() {
//     boolean feasible = true;
//     while (!queue.isEmpty()) {
//       Propagator propagator = queue.removeFirst();
//       // Dequeue the propagator only if it is not idempotent. This allows the
//       // propagator to enqueue itself back in the propagation queue if it
//       // changed the domain of at least one of its variable.
//       propagator.enqueued = propagator.idempotent;
//       // Propagate only if the problem is still feasible.
//       feasible = feasible && propagator.propagate();
//       // Dequeue the propagator no matter what.
//       propagator.enqueued = false;
//     }
//     return feasible;
//   }
// }
// 
// Path: src/main/java/kiwi/trail/Trail.java
// public class Trail {
// 
//   private long timestamp = 0L;
// 
//   private final Stack<Change> changes = new Stack<Change>();
//   private final StackInt levels = new StackInt();
// 
//   public long getTimestamp() {
//     return timestamp;
//   }
// 
//   public void store(Change change) {
//     changes.push(change);
//   }
// 
//   public void newLevel() {
//     levels.push(changes.getSize());
//     timestamp++;
//   }
// 
//   public void undoLevel() {
//     if (levels.getSize() > 0)
//       undoUntil(levels.pop());
//     timestamp++;
//   }
// 
//   public void undoAll() {
//     while (levels.getSize() > 0) {
//       undoUntil(levels.pop());
//     }
//     timestamp++;
//   }
// 
//   private void undoUntil(int size) {
//     while (changes.getSize() > size) {
//       changes.pop().undo();
//     }
//   }
// }
// 
// Path: src/main/java/kiwi/util/Action.java
// public interface Action {
//   public void execute();
// }
// 
// Path: src/main/java/kiwi/util/Stack.java
// public class Stack<T> {
// 
//   private Object[] array = new Object[16];
// 
//   private int index = 0;
// 
//   public int getSize() {
//     return index;
//   }
// 
//   public boolean isEmpty() {
//     return index == 0;
//   }
// 
//   @SuppressWarnings("unchecked")
//   public T top() {
//     return (T) array[index - 1];
//   }
// 
//   public void push(T elem) {
//     if (index == array.length) {
//       growStack();
//     }
//     array[index] = (Object) elem;
//     index++;
//   }
// 
//   public void clear() {
//     while (index > 0) {
//       index--;
//       array[index] = null;
//     }
//   }
// 
//   @SuppressWarnings("unchecked")
//   public T pop() {
//     return (T) array[--index];
//   }
// 
//   @SuppressWarnings("unchecked")
//   public void forEach(Consumer<T> c) {
//     for (int i = 0; i < index; i++) {
//       c.accept((T) array[i]);
//     }
//   }
// 
//   private void growStack() {
//     Object[] newArray = new Object[index * 2];
//     System.arraycopy(array, 0, newArray, 0, index);
//     array = newArray;
//   }
// }


// Path: src/main/java/kiwi/search/DFSearch.java
import java.util.function.Predicate;
import kiwi.propagation.PropagationQueue;
import kiwi.trail.Trail;
import kiwi.util.Action;
import kiwi.util.Stack;

/*
 * 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;



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) {