Generated on Sat Feb 7 2015 02:01:18 for Gecode by doxygen 1.8.9.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: 2013-05-06 09:02:17 +0200 (Mon, 06 May 2013) $ by $Author: tack $
11  * $Revision: 13613 $
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  int c_d, int a_d, bool clear,
263  : NodeCursor<VisualNode>(root,na), _na(na), _curBest(curBest),
264  _c_d(c_d), _a_d(a_d), _clear(clear) {}
265 
266  forceinline void
268  VisualNode* n = node();
269  if (!_clear) {
270  if (!na.hasLabel(n)) {
271  VisualNode* p = n->getParent(_na);
272  if (p) {
273  std::string l =
274  n->getBranchLabel(_na,p,p->getChoice(),
275  _curBest,_c_d,_a_d,alternative());
276  _na.setLabel(n,QString(l.c_str()));
277  if (n->getNumberOfChildren() < 1 &&
278  alternative() == p->getNumberOfChildren()-1)
279  p->purge(_na);
280  } else {
281  _na.setLabel(n,"");
282  }
283  }
284  } else {
285  _na.clearLabel(n);
286  }
287  n->dirtyUp(na);
288  }
289 
292  const VisualNode::NodeAllocator& na)
293  : NodeCursor<VisualNode>(root,na) {}
294 
295  forceinline void
297  node()->dispose();
298  }
299 
300 }}
301 
302 // STATISTICS: gist-any
Node representing stop point.
Definition: spacenode.hh:53
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
Definition: nodecursor.hpp:93
bool mayMoveDownwards(void)
Test if the cursor may move to the first child node.
Definition: nodecursor.hpp:119
BranchLabelCursor(VisualNode *theNode, BestNode *curBest, int c_d, int a_d, bool clear, VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:260
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void dispose(void)
Free allocated memory.
Definition: visualnode.cpp:100
Static reference to the currently best space.
Definition: spacenode.hh:84
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
Node representing a branch.
Definition: spacenode.hh:51
bool isDirty(void)
Return whether node is marked as dirty.
Definition: visualnode.hpp:157
void moveUpwards(void)
Move cursor to the parent node.
Definition: nodecursor.hpp:76
bool isHidden(void)
Return if node is hidden.
Definition: visualnode.hpp:133
NodeAllocatorBase< VisualNode > NodeAllocator
Definition: node.hh:147
void setChildrenLayoutDone(bool d)
Mark node whether the layout of the node's children has been completed.
Definition: visualnode.hpp:172
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:99
int depth
Depth of the search tree.
Definition: nodecursor.hh:168
void setStop(bool h)
Set stop state to h.
Definition: visualnode.hpp:143
bool mayMoveSidewards(void)
Test if cursor may move to the first sibling.
Definition: nodecursor.hpp:106
Node representing failure.
Definition: spacenode.hh:50
void moveSidewards(void)
Move cursor to the first sibling.
Definition: nodecursor.hpp:219
Base class for nodes of the search tree.
Definition: node.hh:110
Node allocator.
Definition: node.hh:52
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition: node.hpp:218
DisposeCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:291
void setHidden(bool h)
Set hidden state to h.
Definition: visualnode.hpp:138
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:151
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:134
Node that has not been explored yet.
Definition: spacenode.hh:52
std::string getBranchLabel(NodeAllocator &na, VisualNode *p, const Choice *c, BestNode *curBest, int c_d, int a_d, int alt)
Return string that describes the branch.
Definition: visualnode.cpp:288
const Choice * getChoice(void)
Return choice of this node.
Definition: spacenode.hpp:185
int getParent(void) const
Return the parent.
Definition: node.hpp:186
NodeStatus getStatus(void) const
Return current status of the node.
Definition: spacenode.hpp:75
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool isRoot(void) const
Check if this node is the root of a tree.
Definition: node.hpp:215
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool mayMoveUpwards(void)
Test if the cursor may move to the parent node.
Definition: nodecursor.hpp:70
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
HideFailedCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na, bool onlyDirtyNodes)
Constructor.
Definition: nodecursor.hpp:128
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:247
const VisualNode::NodeAllocator & na
The node allocator.
Definition: nodecursor.hh:57
void moveUpwards(void)
Move cursor to the parent node.
Definition: nodecursor.hpp:254
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:99
Node representing a solution.
Definition: spacenode.hh:49
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:165
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:199
void processCurrentNode(void)
Dispose node.
Definition: nodecursor.hpp:296
Node * startNode(void)
Return start node.
Definition: nodecursor.hpp:62
StatCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:229
UnhideAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:146
void moveSidewards(void)
Move cursor to the first sibling.
Definition: nodecursor.hpp:113
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
Definition: nodecursor.hpp:192
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
Definition: spacenode.cpp:373
int open
Number of open nodes.
Definition: nodecursor.hh:176
A cursor that can be run over a tree.
Definition: nodecursor.hh:47
void dirtyUp(const NodeAllocator &na)
Mark all nodes up the path to the parent as dirty.
Definition: visualnode.cpp:106
#define forceinline
Definition: config.hpp:132
Node class that supports visual layout
Definition: visualnode.hh:129
int choice
Number of choice nodes.
Definition: nodecursor.hh:174
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:97
int failed
Number of failed nodes.
Definition: nodecursor.hh:170
bool mayMoveSidewards(void)
Test if cursor may move to the first sibling.
Definition: nodecursor.hpp:208
void processCurrentNode(void)
Do nothing.
Definition: nodecursor.hpp:179
Node * node(void)
Return current node.
Definition: nodecursor.hpp:50
UnstopAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:160
NodeCursor(Node *theNode, const typename Node::NodeAllocator &na)
Construct cursor, initially set to theNode.
Definition: nodecursor.hpp:42
Gecode toplevel namespace
int getChild(int n) const
Return index of child no n.
Definition: node.hpp:199
unsigned int alternative(void)
Return current alternative.
Definition: nodecursor.hpp:54
void processCurrentNode(void)
Collect statistics.
Definition: nodecursor.hpp:235
bool hasLabel(T *n) const
Return whether node n has a label.
Definition: node.hpp:130
bool mayMoveUpwards(void)
Test if the cursor may move to the parent node.
Definition: nodecursor.hpp:187
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
int solved
Number of solved nodes.
Definition: nodecursor.hh:172
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
Definition: spacenode.hpp:153
NextSolCursor(VisualNode *theNode, bool backwards, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:174
void purge(const NodeAllocator &na)
Clear working space and copy (if present and this is not the root).
Definition: spacenode.hpp:124