Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
145
146 forceinline void
148 VisualNode* n = node();
149 if (n->isHidden()) {
150 n->setHidden(false);
151 n->dirtyUp(na);
152 }
153 }
154
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
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
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
290
291 forceinline void
295
296}}
297
298// STATISTICS: gist-any
NNF * l
Left subtree.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
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.
void processCurrentNode(void)
Dispose node.
DisposeCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
void processCurrentNode(void)
Process node.
HideFailedCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na, bool onlyDirtyNodes)
Constructor.
bool mayMoveDownwards(void)
Test if the cursor may move to the first child node.
void processCurrentNode(void)
Do nothing.
bool mayMoveUpwards(void)
Test if the cursor may move to the parent node.
NextSolCursor(VisualNode *theNode, bool backwards, const VisualNode::NodeAllocator &na)
Constructor.
void moveSidewards(void)
Move cursor to the first sibling.
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
bool mayMoveSidewards(void)
Test if cursor may move to the first sibling.
void moveDownwards(void)
Move cursor to the first child node.
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 VisualNode::NodeAllocator & na
Definition nodecursor.hh:53
void moveDownwards(void)
Move cursor to the first child node.
bool mayMoveUpwards(void)
Test if the cursor may move to the parent node.
NodeCursor(Node *theNode, const typename Node::NodeAllocator &na)
Construct cursor, initially set to theNode.
Node * node(void)
Return current node.
unsigned int alternative(void)
Return current alternative.
Node * startNode(void)
Return start node.
void moveSidewards(void)
Move cursor to the first sibling.
bool mayMoveSidewards(void)
Test if cursor may move to the first sibling.
void moveUpwards(void)
Move cursor to the parent node.
bool mayMoveDownwards(void)
Test if cursor may move to the first child node.
Base class for nodes of the search tree.
Definition node.hh:106
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition node.hpp:214
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.
NodeStatus getStatus(void) const
Return current status of the node.
Definition spacenode.hpp:71
int choice
Number of choice nodes.
void moveDownwards(void)
Move cursor to the first child node.
int failed
Number of failed nodes.
StatCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
int depth
Depth of the search tree.
void processCurrentNode(void)
Collect statistics.
int open
Number of open nodes.
int solved
Number of solved nodes.
void moveUpwards(void)
Move cursor to the parent node.
UnhideAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
void processCurrentNode(void)
Process node.
void processCurrentNode(void)
Process node.
UnstopAllCursor(VisualNode *theNode, const VisualNode::NodeAllocator &na)
Constructor.
Node class that supports visual layout
void dispose(void)
Free allocated memory.
@ 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:187