main page modules namespaces classes files
Gecode/J home

DFS.java

Go to the documentation of this file.

/* -*- indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Marco Kuhlmann <kuhlmann@ps.uni-sb.de>
 *     Guido Tack <tack@gecode.org>
 *
 *  Contributing authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Marco Kuhlmann, 2005
 *     Guido Tack, 2006
 *
 *  Last modified:
 *     $Date: 2006-10-26 11:31:58 +0200 (Thu, 26 Oct 2006) $ by $Author: tack $
 *     $Revision: 3796 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

package org.gecode.gist;

import java.util.*;

public class DFS implements SearchEngineInterface {
    private Stack<SpaceNode> stack;

    public DFS() {
        stack = new Stack<SpaceNode>();
    }

    public void setup(SpaceNode root) {
        stack.clear();
        stack.push(root);
    }

    public boolean step() {
        if (stack.empty())
            return true;
        SpaceNode node = stack.pop();
        Iterator childrenIterator = node.reversedChildrenIterator();
        while (childrenIterator.hasNext()) {
            SpaceNode nextChild = (SpaceNode) childrenIterator.next();
            if (nextChild.isOpen())
                stack.push(nextChild);
        }
        return stack.empty();
    }

}