main page modules namespaces classes files
Gecode/J home

SpaceNode.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.*;
import org.gecode.*;

public abstract class SpaceNode extends VisualNode {

    class Branch {
        int alternative;
        BranchingDesc desc;
        Space ownBest = null;
        Branch(int a, BranchingDesc d) {
            alternative = a;
            desc = d;
        }
        Branch(int a, BranchingDesc d, Space best) {
            alternative = a;
            desc = d;
            ownBest = best;
        }
    }

    protected Statistics stats;
    
    private Space copy;
    public Space workingSpace;

    private BranchingDesc desc;
    private int alternative;
    private NodeStatus status = NodeStatus.UNDETERMINED;
    
    public BestSpace curBest = null;
    private Space ownBest = null;

    private int noOfOpenChildren = 0;
    private boolean hasFailedChildren = false;
    private boolean hasSolvedChildren = false;
    
    public SpaceNode(int alt, Statistics theStats) {
        super();
        alternative = alt;
        stats = theStats;
    }
    
    public SpaceNode(int alt, BestSpace best, Statistics theStats) {
        super();
        alternative = alt;
        curBest = best;
        stats = theStats;
    }

    public SpaceNode(Space root, Statistics theStats) {
        super();
        workingSpace = root;
        if (!root.failed()) {
            copy = root.cloneSpace();
        } else {
            copy = root;
        }
        stats = theStats;
    }

    public void initCurBest(BestSpace c) {
            curBest = c;
    }
        
    protected int recompute() {
            int rdist = 0;
            if (workingSpace == null) {
            SpaceNode curNode = this;
            Stack<Branch> stack = new Stack<Branch>();

            while (curNode.copy==null) {
                SpaceNode parent = (SpaceNode)curNode.getParent();
                Branch b;
                if (curBest != null) {
                        b = new Branch(curNode.alternative, parent.desc, curNode.ownBest);
                } else {
                        b = new Branch(curNode.alternative, parent.desc);
                }
                stack.push(b);
                curNode = parent;
                rdist++;
            }
            Space curSpace = curNode.copy.cloneSpace();

            Space lastBest = null;
            SpaceNode middleNode = curNode;
            int curDist = 0;
            while (!stack.empty()) {
                if (Config.a_d() >= 0 && 
                    curDist > Config.a_d() && 
                    curDist == rdist / 2) {
                    middleNode.copy = curSpace.cloneSpace();
                }
                Branch b = (Branch)stack.pop();
                curSpace.commit(b.desc, b.alternative);

                if (b.ownBest != lastBest && b.ownBest != null) {
                    curSpace.constrain(b.ownBest);
                    lastBest = b.ownBest;
                }
                curDist++;
                middleNode = (SpaceNode) middleNode.getChild(b.alternative);
            }
            workingSpace = curSpace;
        }
            return rdist;
    }

    private Space donateSpace(int alt, Space ownBest) {
        Space ret = workingSpace;
        if (ret != null) {            
            workingSpace = null;
            ret.commit(desc, alt);

            if (ownBest != null) {
                ret.constrain(ownBest);
            }
        }
        return ret;
    }
    
    private Space checkLAO(int alt, Space ownBest) {
        Space ret = null;
            if (copy != null && noOfOpenChildren == 1 && getParent() != null) {
            // last alternative optimization
            ret = copy;
            copy = null;
            ret.commit(desc, alt);

            if (ownBest != null) {
                ret.constrain(ownBest);
            }
            }
            return ret;
    }
    
    protected void acquireSpace() {
            SpaceNode p = (SpaceNode) getParent();
        if (status==Undetermined && curBest != null && ownBest == null && 
            p != null && curBest.s != p.ownBest) {
                ownBest = curBest.s;
        }
            if (workingSpace == null && p != null)
            workingSpace = p.donateSpace(alternative, ownBest);
        if (workingSpace == null) {
                if ( recompute() > Config.mrd() && Config.mrd() >= 0 &&
                     workingSpace.status(new long[1]) == SpaceStatus.SS_BRANCH ) {
                    copy = workingSpace.cloneSpace();
            }
        }
        if (copy == null && p != null) {
            copy = p.checkLAO(alternative, ownBest);
        }
    }

    public Space getSpace() {
            acquireSpace();
            if (workingSpace.status(new long[1]) != SpaceStatus.SS_FAILED) {
            return workingSpace.cloneSpace();
            }
            return workingSpace;
    }
    
    private void solveUp() {
        SpaceNode p = (SpaceNode)getParent();
        hasSolvedChildren = true;
        if (p != null && !p.hasSolvedChildren)
            p.solveUp();
    }
    void closeChild(boolean hadFailures, boolean hadSolutions) {
            noOfOpenChildren--;
        hasFailedChildren = hasFailedChildren || hadFailures;
        hasSolvedChildren = hasSolvedChildren || hadSolutions;
            SpaceNode p = (SpaceNode)getParent();
            if (noOfOpenChildren == 0) {
            stats.close();
            if (p != null)
                p.closeChild(hasFailedChildren, hasSolvedChildren);
        } else if (hadSolutions) {
            solveUp();
        }
    }

    public void hideFailed() {
        DefaultNodeCursor cursor =
            new DefaultNodeCursor(this) {
                public boolean mayMoveDownwards() {
                    SpaceNode snode = (SpaceNode) getCurrentNode();
                    return
                        super.mayMoveDownwards() &&
                        (snode.hasSolvedChildren ||
                         snode.noOfOpenChildren > 0);
                }
                public void processCurrentNode() {
                    SpaceNode snode = (SpaceNode) getCurrentNode();
                    if (snode.getStatus() == NodeStatus.BRANCH &&
                        !snode.hasSolvedChildren &&
                        snode.noOfOpenChildren == 0)
                        snode.hide();
                }
            };
        PreOrderNodeVisitor visitor = new PreOrderNodeVisitor(cursor);
        visitor.run();
    }
    
    public Iterator reversedChildrenIterator() {
        // only needed for the sake of the side effect
        int numberNotNeeded = getNumberOfChildNodes();
        return super.reversedChildrenIterator();
    }
    
    public int getNumberOfChildNodes() {
        int kids = getNumberOfChildren();
        if (kids == -1) {
            stats.newDetermined();
            acquireSpace();
            status = NodeStatus.valueOf(workingSpace.status());
            switch (status) {
            case FAILED:
                workingSpace.delete();
                workingSpace = null;
                kids = 0;
                hasSolvedChildren = false;
                hasFailedChildren = true;
                stats.newFailure();
                stats.newDepth(getDepth());
                if (getParent() != null)
                    ((SpaceNode)getParent()).closeChild(true,false);
                break;
            case SOLVED:
                kids = 0;
                hasSolvedChildren = true;
                hasFailedChildren = false;
                stats.newSolution();
                stats.newDepth(getDepth());
                    if (curBest != null) {
                    curBest.s = workingSpace.cloneSpace();
                    }
                if (getParent() != null)
                    ((SpaceNode)getParent()).closeChild(false,true);
                break;
            case BRANCH:
                desc = workingSpace.description();
                kids = (int) desc.alternatives();
                stats.newChoice();
                stats.newOpen();
                stats.newUndetermined(kids);
                stats.newDepth(getDepth() + 1);
                break;
            }
            setNumberOfChildren(kids);
            noOfOpenChildren = kids;
            dirtyUp();
            for (int i = 0; i < kids; i++) {
                SpaceNode child = createChild(i);
                setNextChild(i, child);
                child.dirtyUp();
            }
        }
        return kids;
    }

    public NodeStatus getStatus() {
        return status;
    }
    public void setStatus(NodeStatus s) {
        status = s;
    }

    public boolean isOpen() {
        return status==Undetermined || noOfOpenChildren > 0;
    }

    public boolean hasFailedChildren() {
        return hasFailedChildren;
    }
    public boolean hasSolvedChildren() {
        return hasSolvedChildren;
    }

    protected abstract SpaceNode createChild(int i);

    protected int getAlternative() {
        return alternative;
    }
}