Generated on Fri Oct 19 11:24:59 2018 for Gecode by doxygen 1.6.3

nodecursor.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2006
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  * Permission is hereby granted, free of charge, to any person obtaining
00014  * a copy of this software and associated documentation files (the
00015  * "Software"), to deal in the Software without restriction, including
00016  * without limitation the rights to use, copy, modify, merge, publish,
00017  * distribute, sublicense, and/or sell copies of the Software, and to
00018  * permit persons to whom the Software is furnished to do so, subject to
00019  * the following conditions:
00020  *
00021  * The above copyright notice and this permission notice shall be
00022  * included in all copies or substantial portions of the Software.
00023  *
00024  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Gist {
00035 
00036   template<class Node>
00037   forceinline
00038   NodeCursor<Node>::NodeCursor(Node* theNode,
00039                                const typename Node::NodeAllocator& na0)
00040    : _startNode(theNode), _node(theNode),
00041      _alternative(theNode->getAlternative(na0)),
00042      na(na0) {}
00043 
00044   template<class Node>
00045   forceinline Node*
00046   NodeCursor<Node>::node(void) { return _node; }
00047 
00048   template<class Node>
00049   forceinline unsigned int
00050   NodeCursor<Node>::alternative(void) { return _alternative; }
00051 
00052   template<class Node>
00053   forceinline void
00054   NodeCursor<Node>::alternative(unsigned int a) { _alternative=a; }
00055 
00056   template<class Node>
00057   forceinline Node*
00058   NodeCursor<Node>::startNode(void) { return _startNode; }
00059 
00060   template<class Node>
00061   forceinline void
00062   NodeCursor<Node>::node(Node* n) { _node = n; }
00063 
00064   template<class Node>
00065   forceinline bool
00066   NodeCursor<Node>::mayMoveUpwards(void) {
00067     return _node != _startNode && !_node->isRoot();
00068   }
00069 
00070   template<class Node>
00071   forceinline void
00072   NodeCursor<Node>::moveUpwards(void) {
00073     _node = static_cast<Node*>(_node->getParent(na));
00074     if (_node->isRoot()) {
00075       _alternative = 0;
00076     } else {
00077       Node* p = static_cast<Node*>(_node->getParent(na));
00078       for (int i=p->getNumberOfChildren(); i--;) {
00079         if (p->getChild(na,i) == _node) {
00080           _alternative = i;
00081           break;
00082         }
00083       }
00084     }
00085   }
00086 
00087   template<class Node>
00088   forceinline bool
00089   NodeCursor<Node>::mayMoveDownwards(void) {
00090     return _node->getNumberOfChildren() > 0;
00091   }
00092 
00093   template<class Node>
00094   forceinline void
00095   NodeCursor<Node>::moveDownwards(void) {
00096     _alternative = 0;
00097     _node = _node->getChild(na,0);
00098   }
00099 
00100   template<class Node>
00101   forceinline bool
00102   NodeCursor<Node>::mayMoveSidewards(void) {
00103     return (!_node->isRoot()) && (_node != _startNode) &&
00104       (_alternative < _node->getParent(na)->getNumberOfChildren() - 1);
00105   }
00106 
00107   template<class Node>
00108   forceinline void
00109   NodeCursor<Node>::moveSidewards(void) {
00110     _node =
00111       static_cast<Node*>(_node->getParent(na)->getChild(na,++_alternative));
00112   }
00113 
00114   forceinline bool
00115   HideFailedCursor::mayMoveDownwards(void) {
00116     VisualNode* n = node();
00117     return (!onlyDirty || n->isDirty()) &&
00118            NodeCursor<VisualNode>::mayMoveDownwards() &&
00119            (n->hasSolvedChildren() || n->getNoOfOpenChildren(na) > 0) &&
00120            (! n->isHidden());
00121   }
00122 
00123   forceinline
00124   HideFailedCursor::HideFailedCursor(VisualNode* root,
00125                                      const VisualNode::NodeAllocator& na,
00126                                      bool onlyDirtyNodes)
00127    : NodeCursor<VisualNode>(root,na), onlyDirty(onlyDirtyNodes) {}
00128 
00129   forceinline void
00130   HideFailedCursor::processCurrentNode(void) {
00131     VisualNode* n = node();
00132     if (n->getStatus() == BRANCH &&
00133         !n->hasSolvedChildren() &&
00134         n->getNoOfOpenChildren(na) == 0) {
00135       n->setHidden(true);
00136       n->setChildrenLayoutDone(false);
00137       n->dirtyUp(na);
00138     }
00139   }
00140 
00141   forceinline
00142   UnhideAllCursor::UnhideAllCursor(VisualNode* root,
00143                                    const VisualNode::NodeAllocator& na)
00144    : NodeCursor<VisualNode>(root,na) {}
00145 
00146   forceinline void
00147   UnhideAllCursor::processCurrentNode(void) {
00148     VisualNode* n = node();
00149     if (n->isHidden()) {
00150       n->setHidden(false);
00151       n->dirtyUp(na);
00152     }
00153   }
00154 
00155   forceinline
00156   UnstopAllCursor::UnstopAllCursor(VisualNode* root,
00157                                    const VisualNode::NodeAllocator& na)
00158    : NodeCursor<VisualNode>(root,na) {}
00159 
00160   forceinline void
00161   UnstopAllCursor::processCurrentNode(void) {
00162     VisualNode* n = node();
00163     if (n->getStatus() == STOP) {
00164       n->setStop(false);
00165       n->dirtyUp(na);
00166     }
00167   }
00168 
00169   forceinline
00170   NextSolCursor::NextSolCursor(VisualNode* theNode, bool backwards,
00171                                const VisualNode::NodeAllocator& na)
00172    : NodeCursor<VisualNode>(theNode,na), back(backwards) {}
00173 
00174   forceinline void
00175   NextSolCursor::processCurrentNode(void) {}
00176 
00177   forceinline bool
00178   NextSolCursor::notOnSol(void) {
00179     return node() == startNode() || node()->getStatus() != SOLVED;
00180   }
00181 
00182   forceinline bool
00183   NextSolCursor::mayMoveUpwards(void) {
00184     return notOnSol() && !node()->isRoot();
00185   }
00186 
00187   forceinline bool
00188   NextSolCursor::mayMoveDownwards(void) {
00189     return notOnSol() && !(back && node() == startNode())
00190            && node()->hasSolvedChildren()
00191            && NodeCursor<VisualNode>::mayMoveDownwards();
00192   }
00193 
00194   forceinline void
00195   NextSolCursor::moveDownwards(void) {
00196     NodeCursor<VisualNode>::moveDownwards();
00197     if (back) {
00198       while (NodeCursor<VisualNode>::mayMoveSidewards())
00199         NodeCursor<VisualNode>::moveSidewards();
00200     }
00201   }
00202 
00203   forceinline bool
00204   NextSolCursor::mayMoveSidewards(void) {
00205     if (back) {
00206       return notOnSol() && !node()->isRoot() && alternative() > 0;
00207     } else {
00208       return notOnSol() && !node()->isRoot() &&
00209              (alternative() <
00210               node()->getParent(na)->getNumberOfChildren() - 1);
00211     }
00212   }
00213 
00214   forceinline void
00215   NextSolCursor::moveSidewards(void) {
00216     if (back) {
00217       alternative(alternative()-1);
00218       node(node()->getParent(na)->getChild(na,alternative()));
00219     } else {
00220       NodeCursor<VisualNode>::moveSidewards();
00221     }
00222   }
00223 
00224   forceinline
00225   StatCursor::StatCursor(VisualNode* root,
00226                          const VisualNode::NodeAllocator& na)
00227    : NodeCursor<VisualNode>(root,na),
00228      curDepth(0), depth(0), failed(0), solved(0), choice(0), open(0) {}
00229 
00230   forceinline void
00231   StatCursor::processCurrentNode(void) {
00232     VisualNode* n = node();
00233     switch (n->getStatus()) {
00234     case SOLVED: solved++; break;
00235     case FAILED: failed++; break;
00236     case BRANCH: choice++; break;
00237     case UNDETERMINED: open++; break;
00238     default: break;
00239     }
00240   }
00241 
00242   forceinline void
00243   StatCursor::moveDownwards(void) {
00244     curDepth++;
00245     depth = std::max(depth,curDepth);
00246     NodeCursor<VisualNode>::moveDownwards();
00247   }
00248 
00249   forceinline void
00250   StatCursor::moveUpwards(void) {
00251     curDepth--;
00252     NodeCursor<VisualNode>::moveUpwards();
00253   }
00254 
00255   forceinline
00256   BranchLabelCursor::BranchLabelCursor(VisualNode* root, BestNode* curBest,
00257                                        int c_d, int a_d, bool clear,
00258                                        VisualNode::NodeAllocator& na)
00259     : NodeCursor<VisualNode>(root,na), _na(na), _curBest(curBest),
00260       _c_d(c_d), _a_d(a_d), _clear(clear) {}
00261 
00262   forceinline void
00263   BranchLabelCursor::processCurrentNode(void) {
00264     VisualNode* n = node();
00265     if (!_clear) {
00266       if (!na.hasLabel(n)) {
00267         VisualNode* p = n->getParent(_na);
00268         if (p) {
00269           std::string l =
00270             n->getBranchLabel(_na,p,p->getChoice(),
00271               _curBest,_c_d,_a_d,alternative());
00272           _na.setLabel(n,QString(l.c_str()));
00273           if (n->getNumberOfChildren() < 1 &&
00274               alternative() == p->getNumberOfChildren()-1)
00275             p->purge(_na);
00276         } else {
00277           _na.setLabel(n,"");
00278         }
00279       }
00280     } else {
00281       _na.clearLabel(n);
00282     }
00283     n->dirtyUp(na);
00284   }
00285 
00286   forceinline
00287   DisposeCursor::DisposeCursor(VisualNode* root,
00288                                const VisualNode::NodeAllocator& na)
00289    : NodeCursor<VisualNode>(root,na) {}
00290 
00291   forceinline void
00292   DisposeCursor::processCurrentNode(void) {
00293     node()->dispose();
00294   }
00295 
00296 }}
00297 
00298 // STATISTICS: gist-any