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