00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
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