Generated on Thu Jan 19 2023 00:00:00 for Gecode by doxygen 1.9.6
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
34namespace 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; }
56 template<class Node>
58 NodeCursor<Node>::startNode(void) { return _startNode; }
59
60 template<class Node>
61 forceinline void
63
64 template<class Node>
65 forceinline bool
67 return _node != _startNode && !_node->isRoot();
68 }
69
70 template<class Node>
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
116 VisualNode* n = node();
117 return (!onlyDirty || n->isDirty()) &&
119 (n->hasSolvedChildren() || n->getNoOfOpenChildren(na) > 0) &&
120 (! n->isHidden());
121 }
122
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
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
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,
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
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
289 : NodeCursor<VisualNode>(root,na) {}
290
291 forceinline void
293 node()->dispose();
294 }
295
296}}
297
298// STATISTICS: gist-any
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Static reference to the currently best space.
Definition: spacenode.hh:80
BranchLabelCursor(VisualNode *theNode, BestNode *curBest, int c_d, int a_d, bool clear, VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:256
void processCurrentNode(void)
Dispose node.
Definition: nodecursor.hpp:292
DisposeCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:287
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:130
HideFailedCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na, bool onlyDirtyNodes)
Constructor.
Definition: nodecursor.hpp:124
bool mayMoveDownwards(void)
Test if the cursor may move to the first child node.
Definition: nodecursor.hpp:115
void processCurrentNode(void)
Do nothing.
Definition: nodecursor.hpp:175
bool mayMoveUpwards(void)
Test if the cursor may move to the parent node.
Definition: nodecursor.hpp:183
NextSolCursor(VisualNode *theNode, bool backwards, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:170
void moveSidewards(void)
Move cursor to the first sibling.
Definition: nodecursor.hpp:215
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
Definition: nodecursor.hpp:188
bool mayMoveSidewards(void)
Test if cursor may move to the first sibling.
Definition: nodecursor.hpp:204
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:195
bool hasLabel(T *n) const
Return whether node n has a label.
Definition: node.hpp:126
void setLabel(T *n, const QString &l)
Set label of node n to l.
Definition: node.hpp:132
void clearLabel(T *n)
Remove label of node n.
Definition: node.hpp:138
A cursor that can be run over a tree.
Definition: nodecursor.hh:43
const Node::NodeAllocator & na
The node allocator.
Definition: nodecursor.hh:53
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:95
bool mayMoveUpwards(void)
Test if the cursor may move to the parent node.
Definition: nodecursor.hpp:66
NodeCursor(Node *theNode, const typename Node::NodeAllocator &na)
Construct cursor, initially set to theNode.
Definition: nodecursor.hpp:38
Node * node(void)
Return current node.
Definition: nodecursor.hpp:46
unsigned int alternative(void)
Return current alternative.
Definition: nodecursor.hpp:50
Node * startNode(void)
Return start node.
Definition: nodecursor.hpp:58
void moveSidewards(void)
Move cursor to the first sibling.
Definition: nodecursor.hpp:109
bool mayMoveSidewards(void)
Test if cursor may move to the first sibling.
Definition: nodecursor.hpp:102
void moveUpwards(void)
Move cursor to the parent node.
Definition: nodecursor.hpp:72
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
Definition: nodecursor.hpp:89
Base class for nodes of the search tree.
Definition: node.hh:106
int getParent(void) const
Return the parent.
Definition: node.hpp:182
bool isRoot(void) const
Check if this node is the root of a tree.
Definition: node.hpp:211
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
Definition: spacenode.hpp:149
NodeStatus getStatus(void) const
Return current status of the node.
Definition: spacenode.hpp:71
int choice
Number of choice nodes.
Definition: nodecursor.hh:170
void moveDownwards(void)
Move cursor to the first child node.
Definition: nodecursor.hpp:243
int failed
Number of failed nodes.
Definition: nodecursor.hh:166
StatCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:225
int depth
Depth of the search tree.
Definition: nodecursor.hh:164
void processCurrentNode(void)
Collect statistics.
Definition: nodecursor.hpp:231
int open
Number of open nodes.
Definition: nodecursor.hh:172
int solved
Number of solved nodes.
Definition: nodecursor.hh:168
void moveUpwards(void)
Move cursor to the parent node.
Definition: nodecursor.hpp:250
UnhideAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:142
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:147
void processCurrentNode(void)
Process node.
Definition: nodecursor.hpp:161
UnstopAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Definition: nodecursor.hpp:156
Node class that supports visual layout
Definition: visualnode.hh:125
void dispose(void)
Free allocated memory.
Definition: visualnode.cpp:96
@ UNDETERMINED
Node that has not been explored yet.
Definition: spacenode.hh:48
@ FAILED
Node representing failure.
Definition: spacenode.hh:46
@ STOP
Node representing stop point.
Definition: spacenode.hh:49
@ SOLVED
Node representing a solution.
Definition: spacenode.hh:45
@ BRANCH
Node representing a branch.
Definition: spacenode.hh:47
Gecode toplevel namespace
#define forceinline
Definition: config.hpp:194