Generated on Sun Aug 26 2012 08:42:37 for Gecode by doxygen 1.8.1.1
nodecursor.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Copyright:
7  * Guido Tack, 2006
8  *
9  * Last modified:
10  * $Date: 2010-08-12 17:48:30 +1000 (Thu, 12 Aug 2010) $ by $Author: tack $
11  * $Revision: 11345 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Gist {
39 
40  template<class Node>
43  const typename Node::NodeAllocator& na0)
44  : _startNode(theNode), _node(theNode),
45  _alternative(theNode->getAlternative(na0)),
46  na(na0) {}
47 
48  template<class Node>
50  NodeCursor<Node>::node(void) { return _node; }
51 
52  template<class Node>
53  forceinline unsigned int
54  NodeCursor<Node>::alternative(void) { return _alternative; }
55 
56  template<class Node>
57  forceinline void
58  NodeCursor<Node>::alternative(unsigned int a) { _alternative=a; }
59 
60  template<class Node>
62  NodeCursor<Node>::startNode(void) { return _startNode; }
63 
64  template<class Node>
65  forceinline void
66  NodeCursor<Node>::node(Node* n) { _node = n; }
67 
68  template<class Node>
69  forceinline bool
71  return _node != _startNode && !_node->isRoot();
72  }
73 
74  template<class Node>
75  forceinline void
77  _node = static_cast<Node*>(_node->getParent(na));
78  if (_node->isRoot()) {
79  _alternative = 0;
80  } else {
81  Node* p = static_cast<Node*>(_node->getParent(na));
82  for (int i=p->getNumberOfChildren(); i--;) {
83  if (p->getChild(na,i) == _node) {
84  _alternative = i;
85  break;
86  }
87  }
88  }
89  }
90 
91  template<class Node>
92  forceinline bool
94  return _node->getNumberOfChildren() > 0;
95  }
96 
97  template<class Node>
98  forceinline void
100  _alternative = 0;
101  _node = _node->getChild(na,0);
102  }
103 
104  template<class Node>
105  forceinline bool
107  return (!_node->isRoot()) && (_node != _startNode) &&
108  (_alternative < _node->getParent(na)->getNumberOfChildren() - 1);
109  }
110 
111  template<class Node>
112  forceinline void
114  _node =
115  static_cast<Node*>(_node->getParent(na)->getChild(na,++_alternative));
116  }
117 
118  forceinline bool
120  VisualNode* n = node();
121  return (!onlyDirty || n->isDirty()) &&
123  (n->hasSolvedChildren() || n->getNoOfOpenChildren(na) > 0) &&
124  (! n->isHidden());
125  }
126 
129  const VisualNode::NodeAllocator& na,
130  bool onlyDirtyNodes)
131  : NodeCursor<VisualNode>(root,na), onlyDirty(onlyDirtyNodes) {}
132 
133  forceinline void
135  VisualNode* n = node();
136  if (n->getStatus() == BRANCH &&
137  !n->hasSolvedChildren() &&
138  n->getNoOfOpenChildren(na) == 0) {
139  n->setHidden(true);
140  n->setChildrenLayoutDone(false);
141  n->dirtyUp(na);
142  }
143  }
144 
147  const VisualNode::NodeAllocator& na)
148  : NodeCursor<VisualNode>(root,na) {}
149 
150  forceinline void
152  VisualNode* n = node();
153  if (n->isHidden()) {
154  n->setHidden(false);
155  n->dirtyUp(na);
156  }
157  }
158 
161  const VisualNode::NodeAllocator& na)
162  : NodeCursor<VisualNode>(root,na) {}
163 
164  forceinline void
166  VisualNode* n = node();
167  if (n->getStatus() == STOP) {
168  n->setStop(false);
169  n->dirtyUp(na);
170  }
171  }
172 
174  NextSolCursor::NextSolCursor(VisualNode* theNode, bool backwards,
175  const VisualNode::NodeAllocator& na)
176  : NodeCursor<VisualNode>(theNode,na), back(backwards) {}
177 
178  forceinline void
180 
181  forceinline bool
182  NextSolCursor::notOnSol(void) {
183  return node() == startNode() || node()->getStatus() != SOLVED;
184  }
185 
186  forceinline bool
188  return notOnSol() && !node()->isRoot();
189  }
190 
191  forceinline bool
193  return notOnSol() && !(back && node() == startNode())
194  && node()->hasSolvedChildren()
196  }
197 
198  forceinline void
201  if (back) {
204  }
205  }
206 
207  forceinline bool
209  if (back) {
210  return notOnSol() && !node()->isRoot() && alternative() > 0;
211  } else {
212  return notOnSol() && !node()->isRoot() &&
213  (alternative() <
214  node()->getParent(na)->getNumberOfChildren() - 1);
215  }
216  }
217 
218  forceinline void
220  if (back) {
222  node(node()->getParent(na)->getChild(na,alternative()));
223  } else {
225  }
226  }
227 
230  const VisualNode::NodeAllocator& na)
231  : NodeCursor<VisualNode>(root,na),
232  curDepth(0), depth(0), failed(0), solved(0), choice(0), open(0) {}
233 
234  forceinline void
236  VisualNode* n = node();
237  switch (n->getStatus()) {
238  case SOLVED: solved++; break;
239  case FAILED: failed++; break;
240  case BRANCH: choice++; break;
241  case UNDETERMINED: open++; break;
242  default: break;
243  }
244  }
245 
246  forceinline void
248  curDepth++;
249  depth = std::max(depth,curDepth);
251  }
252 
253  forceinline void
255  curDepth--;
257  }
258 
261  const VisualNode::NodeAllocator& na)
262  : NodeCursor<VisualNode>(root,na) {}
263 
264  forceinline void
266  node()->dispose();
267  }
268 
269 }}
270 
271 // STATISTICS: gist-any