this repo has no description
dekker.one
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#ifndef GECODE_GIST_NODECURSOR_HH
35#define GECODE_GIST_NODECURSOR_HH
36
37#include <gecode/gist/visualnode.hh>
38
39namespace Gecode { namespace Gist {
40
41 /// \brief A cursor that can be run over a tree
42 template<class Node>
43 class NodeCursor {
44 private:
45 /// The node where the iteration starts
46 Node* _startNode;
47 /// The current node
48 Node* _node;
49 /// The current alternative
50 unsigned int _alternative;
51 protected:
52 /// The node allocator
53 const typename Node::NodeAllocator& na;
54 /// Set current node to \a n
55 void node(Node* n);
56 /// Return start node
57 Node* startNode(void);
58 public:
59 /// Construct cursor, initially set to \a theNode
60 NodeCursor(Node* theNode, const typename Node::NodeAllocator& na);
61 /// Return current node
62 Node* node(void);
63 /// Return current alternative
64 unsigned int alternative(void);
65 /// Set current alternative
66 void alternative(unsigned int a);
67
68 /// \name Cursor interface
69 //@{
70 /// Test if the cursor may move to the parent node
71 bool mayMoveUpwards(void);
72 /// Move cursor to the parent node
73 void moveUpwards(void);
74 /// Test if cursor may move to the first child node
75 bool mayMoveDownwards(void);
76 /// Move cursor to the first child node
77 void moveDownwards(void);
78 /// Test if cursor may move to the first sibling
79 bool mayMoveSidewards(void);
80 /// Move cursor to the first sibling
81 void moveSidewards(void);
82 //@}
83 };
84
85 /// \brief A cursor that marks failed subtrees as hidden
86 class HideFailedCursor : public NodeCursor<VisualNode> {
87 private:
88 bool onlyDirty;
89 public:
90 /// Constructor
91 HideFailedCursor(VisualNode* theNode,
92 const VisualNode::NodeAllocator& na,
93 bool onlyDirtyNodes);
94 /// \name Cursor interface
95 //@{
96 /// Test if the cursor may move to the first child node
97 bool mayMoveDownwards(void);
98 /// Process node
99 void processCurrentNode(void);
100 //@}
101 };
102
103 /// \brief A cursor that marks all nodes in the tree as not hidden
104 class UnhideAllCursor : public NodeCursor<VisualNode> {
105 public:
106 /// Constructor
107 UnhideAllCursor(VisualNode* theNode,
108 const VisualNode::NodeAllocator& na);
109 /// \name Cursor interface
110 //@{
111 /// Process node
112 void processCurrentNode(void);
113 //@}
114 };
115
116 /// \brief A cursor that marks all nodes in the tree as not stopping
117 class UnstopAllCursor : public NodeCursor<VisualNode> {
118 public:
119 /// Constructor
120 UnstopAllCursor(VisualNode* theNode,
121 const VisualNode::NodeAllocator& na);
122 /// \name Cursor interface
123 //@{
124 /// Process node
125 void processCurrentNode(void);
126 //@}
127 };
128
129 /// \brief A cursor that finds the next solution
130 class NextSolCursor : public NodeCursor<VisualNode> {
131 private:
132 /// Whether to search backwards
133 bool back;
134 /// Whether the current node is not a solution
135 bool notOnSol(void);
136 public:
137 /// Constructor
138 NextSolCursor(VisualNode* theNode, bool backwards,
139 const VisualNode::NodeAllocator& na);
140 /// \name Cursor interface
141 //@{
142 /// Do nothing
143 void processCurrentNode(void);
144 /// Test if the cursor may move to the parent node
145 bool mayMoveUpwards(void);
146 /// Test if cursor may move to the first child node
147 bool mayMoveDownwards(void);
148 /// Move cursor to the first child node
149 void moveDownwards(void);
150 /// Test if cursor may move to the first sibling
151 bool mayMoveSidewards(void);
152 /// Move cursor to the first sibling
153 void moveSidewards(void);
154 //@}
155 };
156
157 /// \brief A cursor that collects statistics
158 class StatCursor : public NodeCursor<VisualNode> {
159 private:
160 /// Current depth
161 int curDepth;
162 public:
163 /// Depth of the search tree
164 int depth;
165 /// Number of failed nodes
166 int failed;
167 /// Number of solved nodes
168 int solved;
169 /// Number of choice nodes
170 int choice;
171 /// Number of open nodes
172 int open;
173
174 /// Constructor
175 StatCursor(VisualNode* theNode,
176 const VisualNode::NodeAllocator& na);
177
178 /// \name Cursor interface
179 //@{
180 /// Collect statistics
181 void processCurrentNode(void);
182 /// Move cursor to the first child node
183 void moveDownwards(void);
184 /// Move cursor to the parent node
185 void moveUpwards(void);
186 //@}
187
188 };
189
190 /// \brief A cursor that labels branches
191 class BranchLabelCursor : public NodeCursor<VisualNode> {
192 private:
193 /// The node allocator
194 VisualNode::NodeAllocator& _na;
195 /// Current best solution
196 BestNode* _curBest;
197 /// Recomputation distance
198 int _c_d;
199 /// Adaptive rcomputation distance
200 int _a_d;
201 /// Whether to clear labels
202 bool _clear;
203 public:
204 /// Constructor
205 BranchLabelCursor(VisualNode* theNode, BestNode* curBest,
206 int c_d, int a_d, bool clear,
207 VisualNode::NodeAllocator& na);
208 /// \name Cursor interface
209 //@{
210 void processCurrentNode(void);
211 //@}
212 };
213
214 /// \brief A cursor that frees all memory
215 class DisposeCursor : public NodeCursor<VisualNode> {
216 public:
217 /// Constructor
218 DisposeCursor(VisualNode* theNode,
219 const VisualNode::NodeAllocator& na);
220
221 /// \name Cursor interface
222 //@{
223 /// Dispose node
224 void processCurrentNode(void);
225 //@}
226
227 };
228
229}}
230
231#include <gecode/gist/nodecursor.hpp>
232
233#endif
234
235// STATISTICS: gist-any