Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Gist {
35 
36  template<class Node>
39  const typename Node::NodeAllocator& na0)
40  : _startNode(theNode), _node(theNode),
41  _alternative(theNode->getAlternative(na0)),
42  na(na0) {}
43 
44  template<class Node>
46  NodeCursor<Node>::node(void) { return _node; }
47 
48  template<class Node>
49  forceinline unsigned int
50  NodeCursor<Node>::alternative(void) { return _alternative; }
51 
52  template<class Node>
53  forceinline void
54  NodeCursor<Node>::alternative(unsigned int a) { _alternative=a; }
55 
56  template<class Node>
58  NodeCursor<Node>::startNode(void) { return _startNode; }
59 
60  template<class Node>
61  forceinline void
62  NodeCursor<Node>::node(Node* n) { _node = n; }
63 
64  template<class Node>
65  forceinline bool
67  return _node != _startNode && !_node->isRoot();
68  }
69 
70  template<class Node>
71  forceinline void
73  _node = static_cast<Node*>(_node->getParent(na));
74  if (_node->isRoot()) {
75  _alternative = 0;
76  } else {
77  Node* p = static_cast<Node*>(_node->getParent(na));
78  for (int i=p->getNumberOfChildren(); i--;) {
79  if (p->getChild(na,i) == _node) {
80  _alternative = i;
81  break;
82  }
83  }
84  }
85  }
86 
87  template<class Node>
88  forceinline bool
90  return _node->getNumberOfChildren() > 0;
91  }
92 
93  template<class Node>
94  forceinline void
96  _alternative = 0;
97  _node = _node->getChild(na,0);
98  }
99 
100  template<class Node>
101  forceinline bool
103  return (!_node->isRoot()) && (_node != _startNode) &&
104  (_alternative < _node->getParent(na)->getNumberOfChildren() - 1);
105  }
106 
107  template<class Node>
108  forceinline void
110  _node =
111  static_cast<Node*>(_node->getParent(na)->getChild(na,++_alternative));
112  }
113 
114  forceinline bool
115  HideFailedCursor::mayMoveDownwards(void) {
116  VisualNode* n = node();
117  return (!onlyDirty || n->isDirty()) &&
119  (n->hasSolvedChildren() || n->getNoOfOpenChildren(na) > 0) &&
120  (! n->isHidden());
121  }
122 
124  HideFailedCursor::HideFailedCursor(VisualNode* root,
125  const VisualNode::NodeAllocator& na,
126  bool onlyDirtyNodes)
127  : NodeCursor<VisualNode>(root,na), onlyDirty(onlyDirtyNodes) {}
128 
129  forceinline void
131  VisualNode* n = node();
132  if (n->getStatus() == BRANCH &&
133  !n->hasSolvedChildren() &&
134  n->getNoOfOpenChildren(na) == 0) {
135  n->setHidden(true);
136  n->setChildrenLayoutDone(false);
137  n->dirtyUp(na);
138  }
139  }
140 
143  const VisualNode::NodeAllocator& na)
144  : NodeCursor<VisualNode>(root,na) {}
145 
146  forceinline void
148  VisualNode* n = node();
149  if (n->isHidden()) {
150  n->setHidden(false);
151  n->dirtyUp(na);
152  }
153  }
154 
157  const VisualNode::NodeAllocator& na)
158  : NodeCursor<VisualNode>(root,na) {}
159 
160  forceinline void
162  VisualNode* n = node();
163  if (n->getStatus() == STOP) {
164  n->setStop(false);
165  n->dirtyUp(na);
166  }
167  }
168 
170  NextSolCursor::NextSolCursor(VisualNode* theNode, bool backwards,
171  const VisualNode::NodeAllocator& na)
172  : NodeCursor<VisualNode>(theNode,na), back(backwards) {}
173 
174  forceinline void
176 
177  forceinline bool
178  NextSolCursor::notOnSol(void) {
179  return node() == startNode() || node()->getStatus() != SOLVED;
180  }
181 
182  forceinline bool
184  return notOnSol() && !node()->isRoot();
185  }
186 
187  forceinline bool
189  return notOnSol() && !(back && node() == startNode())
190  && node()->hasSolvedChildren()
192  }
193 
194  forceinline void
197  if (back) {
200  }
201  }
202 
203  forceinline bool
205  if (back) {
206  return notOnSol() && !node()->isRoot() && alternative() > 0;
207  } else {
208  return notOnSol() && !node()->isRoot() &&
209  (alternative() <
210  node()->getParent(na)->getNumberOfChildren() - 1);
211  }
212  }
213 
214  forceinline void
216  if (back) {
218  node(node()->getParent(na)->getChild(na,alternative()));
219  } else {
221  }
222  }
223 
226  const VisualNode::NodeAllocator& na)
227  : NodeCursor<VisualNode>(root,na),
228  curDepth(0), depth(0), failed(0), solved(0), choice(0), open(0) {}
229 
230  forceinline void
232  VisualNode* n = node();
233  switch (n->getStatus()) {
234  case SOLVED: solved++; break;
235  case FAILED: failed++; break;
236  case BRANCH: choice++; break;
237  case UNDETERMINED: open++; break;
238  default: break;
239  }
240  }
241 
242  forceinline void
244  curDepth++;
245  depth = std::max(depth,curDepth);
247  }
248 
249  forceinline void
251  curDepth--;
253  }
254 
257  int c_d, int a_d, bool clear,
259  : NodeCursor<VisualNode>(root,na), _na(na), _curBest(curBest),
260  _c_d(c_d), _a_d(a_d), _clear(clear) {}
261 
262  forceinline void
264  VisualNode* n = node();
265  if (!_clear) {
266  if (!na.hasLabel(n)) {
267  VisualNode* p = n->getParent(_na);
268  if (p) {
269  std::string l =
270  n->getBranchLabel(_na,p,p->getChoice(),
271  _curBest,_c_d,_a_d,alternative());
272  _na.setLabel(n,QString(l.c_str()));
273  if (n->getNumberOfChildren() < 1 &&
274  alternative() == p->getNumberOfChildren()-1)
275  p->purge(_na);
276  } else {
277  _na.setLabel(n,"");
278  }
279  }
280  } else {
281  _na.clearLabel(n);
282  }
283  n->dirtyUp(na);
284  }
285 
288  const VisualNode::NodeAllocator& na)
289  : NodeCursor<VisualNode>(root,na) {}
290 
291  forceinline void
293  node()->dispose();
294  }
295 
296 }}
297 
298 // STATISTICS: gist-any
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:95
int choice
Number of choice nodes.
Definition: nodecursor.hh:170
Node that has not been explored yet.
Definition: spacenode.hh:48
int open
Number of open nodes.
Definition: nodecursor.hh:172
void moveSidewards(void)
Move cursor to the first sibling.
Definition: nodecursor.hpp:215
int depth
Depth of the search tree.
Definition: nodecursor.hh:164
A cursor that can be run over a tree.
Definition: nodecursor.hh:43
DisposeCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:287
Node representing stop point.
Definition: spacenode.hh:49
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:243
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
Definition: spacenode.hpp:149
Node class that supports visual layout
Definition: visualnode.hh:125
StatCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:225
NodeStatus getStatus(void) const
Return current status of the node.
Definition: spacenode.hpp:71
void moveUpwards(void)
Move cursor to the parent node.
Definition: nodecursor.hpp:250
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:195
NextSolCursor(VisualNode *theNode, bool backwards, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:170
bool isRoot(void) const
Check if this node is the root of a tree.
Definition: node.hpp:211
Base class for nodes of the search tree.
Definition: node.hh:106
Gecode toplevel namespace
const VisualNode ::NodeAllocator & na
The node allocator.
Definition: nodecursor.hh:53
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
BranchLabelCursor(VisualNode *theNode, BestNode *curBest, int c_d, int a_d, bool clear, VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:256
bool mayMoveSidewards(void)
Test if cursor may move to the first sibling.
Definition: nodecursor.hpp:204
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:130
void processCurrentNode(void)
Collect statistics.
Definition: nodecursor.hpp:231
Node allocator.
Definition: node.hh:48
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
Definition: nodecursor.hpp:188
bool mayMoveUpwards(void)
Test if the cursor may move to the parent node.
Definition: nodecursor.hpp:183
NodeAllocatorBase< VisualNode > NodeAllocator
Definition: node.hh:143
Static reference to the currently best space.
Definition: spacenode.hh:80
int solved
Number of solved nodes.
Definition: nodecursor.hh:168
Node representing a branch.
Definition: spacenode.hh:47
int getParent(void) const
Return the parent.
Definition: node.hpp:182
void dispose(void)
Free allocated memory.
Definition: visualnode.cpp:96
UnhideAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:142
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:161
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:147
void moveSidewards(void)
Move cursor to the first sibling.
Definition: nodecursor.hpp:109
NodeCursor(Node *theNode, const typename Node::NodeAllocator &na)
Construct cursor, initially set to theNode.
Definition: nodecursor.hpp:38
void processCurrentNode(void)
Do nothing.
Definition: nodecursor.hpp:175
VisualNode * startNode(void)
Return start node.
Definition: nodecursor.hpp:58
void processCurrentNode(void)
Definition: nodecursor.hpp:263
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
UnstopAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:156
void processCurrentNode(void)
Dispose node.
Definition: nodecursor.hpp:292
#define forceinline
Definition: config.hpp:185
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:113
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
Definition: nodecursor.hpp:89
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node representing failure.
Definition: spacenode.hh:46
Gecode::IntArgs i({1, 2, 3, 4})
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
unsigned int alternative(void)
Return current alternative.
Definition: nodecursor.hpp:50
int failed
Number of failed nodes.
Definition: nodecursor.hh:166
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
Node representing a solution.
Definition: spacenode.hh:45
void moveUpwards(void)
Move cursor to the parent node.
Definition: nodecursor.hpp:72
VisualNode * node(void)
Return current node.
Definition: nodecursor.hpp:46