this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2003
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 Search { namespace Seq {
35
36 /*
37 * Edge for recomputation
38 *
39 */
40 template<class Tracer>
41 forceinline
42 Path<Tracer>::Edge::Edge(void) {}
43
44 template<class Tracer>
45 forceinline
46 Path<Tracer>::Edge::Edge(Space* s, Space* c, unsigned int nid)
47 : _space(c), _alt(0), _choice(s->choice()), _nid(nid) {}
48
49 template<class Tracer>
50 forceinline Space*
51 Path<Tracer>::Edge::space(void) const {
52 return _space;
53 }
54 template<class Tracer>
55 forceinline void
56 Path<Tracer>::Edge::space(Space* s) {
57 _space = s;
58 }
59
60 template<class Tracer>
61 forceinline unsigned int
62 Path<Tracer>::Edge::alt(void) const {
63 return _alt;
64 }
65 template<class Tracer>
66 forceinline unsigned int
67 Path<Tracer>::Edge::truealt(void) const {
68 return std::min(_alt,_choice->alternatives()-1);
69 }
70 template<class Tracer>
71 forceinline bool
72 Path<Tracer>::Edge::leftmost(void) const {
73 return _alt == 0;
74 }
75 template<class Tracer>
76 forceinline bool
77 Path<Tracer>::Edge::rightmost(void) const {
78 return _alt+1 >= _choice->alternatives();
79 }
80 template<class Tracer>
81 forceinline bool
82 Path<Tracer>::Edge::lao(void) const {
83 return _alt >= _choice->alternatives();
84 }
85 template<class Tracer>
86 forceinline void
87 Path<Tracer>::Edge::next(void) {
88 _alt++;
89 }
90
91 template<class Tracer>
92 forceinline const Choice*
93 Path<Tracer>::Edge::choice(void) const {
94 return _choice;
95 }
96
97 template<class Tracer>
98 forceinline unsigned int
99 Path<Tracer>::Edge::nid(void) const {
100 return _nid;
101 }
102
103 template<class Tracer>
104 forceinline void
105 Path<Tracer>::Edge::dispose(void) {
106 delete _space;
107 delete _choice;
108 }
109
110
111
112 /*
113 * Depth-first stack with recomputation
114 *
115 */
116
117 template<class Tracer>
118 forceinline
119 Path<Tracer>::Path(unsigned int l)
120 : ds(heap), _ngdl(l) {}
121
122 template<class Tracer>
123 forceinline unsigned int
124 Path<Tracer>::ngdl(void) const {
125 return _ngdl;
126 }
127
128 template<class Tracer>
129 forceinline void
130 Path<Tracer>::ngdl(unsigned int l) {
131 _ngdl = l;
132 }
133
134 template<class Tracer>
135 forceinline const Choice*
136 Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
137 if (!ds.empty() && ds.top().lao()) {
138 // Topmost stack entry was LAO -> reuse
139 ds.pop().dispose();
140 }
141 Edge sn(s,c,nid);
142 ds.push(sn);
143 stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
144 return sn.choice();
145 }
146
147 template<class Tracer>
148 forceinline void
149 Path<Tracer>::next(void) {
150 while (!ds.empty())
151 if (ds.top().rightmost()) {
152 ds.pop().dispose();
153 } else {
154 ds.top().next();
155 return;
156 }
157 }
158
159 template<class Tracer>
160 forceinline typename Path<Tracer>::Edge&
161 Path<Tracer>::top(void) const {
162 assert(!ds.empty());
163 return ds.top();
164 }
165
166 template<class Tracer>
167 forceinline bool
168 Path<Tracer>::empty(void) const {
169 return ds.empty();
170 }
171
172 template<class Tracer>
173 forceinline void
174 Path<Tracer>::commit(Space* s, int i) const {
175 const Edge& n = ds[i];
176 s->commit(*n.choice(),n.alt());
177 }
178
179 template<class Tracer>
180 forceinline int
181 Path<Tracer>::lc(void) const {
182 int l = ds.entries()-1;
183 while (ds[l].space() == nullptr)
184 l--;
185 return l;
186 }
187
188 template<class Tracer>
189 forceinline int
190 Path<Tracer>::entries(void) const {
191 return ds.entries();
192 }
193
194 template<class Tracer>
195 forceinline void
196 Path<Tracer>::unwind(int l, Tracer& t) {
197 assert((ds[l].space() == nullptr) || ds[l].space()->failed());
198 int n = ds.entries();
199 if (t) {
200 for (int i=l; i<n; i++) {
201 Path<Tracer>::Edge& top = ds.top();
202 unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
203 for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
204 SearchTracer::EdgeInfo ei(t.wid(),top.nid(),a);
205 t.skip(ei);
206 }
207 ds.pop().dispose();
208 }
209 } else {
210 for (int i=l; i<n; i++)
211 ds.pop().dispose();
212 }
213 assert(ds.entries() == l);
214 }
215
216 template<class Tracer>
217 inline void
218 Path<Tracer>::reset(void) {
219 while (!ds.empty())
220 ds.pop().dispose();
221 }
222
223 template<class Tracer>
224 forceinline Space*
225 Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
226 Tracer& t) {
227 assert(!ds.empty());
228 // Recompute space according to path
229 // Also say distance to copy (d == 0) requires immediate copying
230
231 // Check for LAO
232 if ((ds.top().space() != nullptr) && ds.top().rightmost()) {
233 Space* s = ds.top().space();
234 s->commit(*ds.top().choice(),ds.top().alt());
235 assert(ds.entries()-1 == lc());
236 ds.top().space(nullptr);
237 // Mark as reusable
238 if (static_cast<unsigned int>(ds.entries()) > ngdl())
239 ds.top().next();
240 d = 0;
241 return s;
242 }
243 // General case for recomputation
244 int l = lc(); // Position of last clone
245 int n = ds.entries(); // Number of stack entries
246 // New distance, if no adaptive recomputation
247 d = static_cast<unsigned int>(n - l);
248
249 Space* s = ds[l].space()->clone(); // Last clone
250
251 if (d < a_d) {
252 // No adaptive recomputation
253 for (int i=l; i<n; i++)
254 commit(s,i);
255 } else {
256 int m = l + static_cast<int>(d >> 1); // Middle between copy and top
257 int i = l; // To iterate over all entries
258 // Recompute up to middle
259 for (; i<m; i++ )
260 commit(s,i);
261 // Skip over all rightmost branches
262 for (; (i<n) && ds[i].rightmost(); i++)
263 commit(s,i);
264 // Is there any point to make a copy?
265 if (i<n-1) {
266 // Propagate to fixpoint
267 SpaceStatus ss = s->status(stat);
268 /*
269 * Again, the space might already propagate to failure (due to
270 * weakly monotonic propagators).
271 */
272 if (ss == SS_FAILED) {
273 // s must be deleted as it is not on the stack
274 delete s;
275 stat.fail++;
276 unwind(i,t);
277 return nullptr;
278 }
279 ds[i].space(s->clone());
280 d = static_cast<unsigned int>(n-i);
281 }
282 // Finally do the remaining commits
283 for (; i<n; i++)
284 commit(s,i);
285 }
286 return s;
287 }
288
289 template<class Tracer>
290 forceinline Space*
291 Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
292 const Space& best, int& mark,
293 Tracer& t) {
294 assert(!ds.empty());
295 // Recompute space according to path
296 // Also say distance to copy (d == 0) requires immediate copying
297
298 // Check for LAO
299 if ((ds.top().space() != nullptr) && ds.top().rightmost()) {
300 Space* s = ds.top().space();
301 s->commit(*ds.top().choice(),ds.top().alt());
302 assert(ds.entries()-1 == lc());
303 if (mark > ds.entries()-1) {
304 mark = ds.entries()-1;
305 s->constrain(best);
306 }
307 ds.top().space(nullptr);
308 // Mark as reusable
309 if (static_cast<unsigned int>(ds.entries()) > ngdl())
310 ds.top().next();
311 d = 0;
312 return s;
313 }
314 // General case for recomputation
315 int l = lc(); // Position of last clone
316 int n = ds.entries(); // Number of stack entries
317 // New distance, if no adaptive recomputation
318 d = static_cast<unsigned int>(n - l);
319
320 Space* s = ds[l].space(); // Last clone
321
322 if (l < mark) {
323 mark = l;
324 s->constrain(best);
325 // The space on the stack could be failed now as an additional
326 // constraint might have been added.
327 if (s->status(stat) == SS_FAILED) {
328 // s does not need deletion as it is on the stack (unwind does this)
329 stat.fail++;
330 unwind(l,t);
331 return nullptr;
332 }
333 // It is important to replace the space on the stack with the
334 // copy: a copy might be much smaller due to flushed caches
335 // of propagators
336 Space* c = s->clone();
337 ds[l].space(c);
338 } else {
339 s = s->clone();
340 }
341
342 if (d < a_d) {
343 // No adaptive recomputation
344 for (int i=l; i<n; i++)
345 commit(s,i);
346 } else {
347 int m = l + static_cast<int>(d >> 1); // Middle between copy and top
348 int i = l; // To iterate over all entries
349 // Recompute up to middle
350 for (; i<m; i++ )
351 commit(s,i);
352 // Skip over all rightmost branches
353 for (; (i<n) && ds[i].rightmost(); i++)
354 commit(s,i);
355 // Is there any point to make a copy?
356 if (i<n-1) {
357 // Propagate to fixpoint
358 SpaceStatus ss = s->status(stat);
359 /*
360 * Again, the space might already propagate to failure
361 *
362 * This can be for two reasons:
363 * - constrain is true, so we fail
364 * - the space has weakly monotonic propagators
365 */
366 if (ss == SS_FAILED) {
367 // s must be deleted as it is not on the stack
368 delete s;
369 stat.fail++;
370 unwind(i,t);
371 return nullptr;
372 }
373 ds[i].space(s->clone());
374 d = static_cast<unsigned int>(n-i);
375 }
376 // Finally do the remaining commits
377 for (; i<n; i++)
378 commit(s,i);
379 }
380 return s;
381 }
382
383 template<class Tracer>
384 void
385 Path<Tracer>::post(Space& home) const {
386 GECODE_ES_FAIL(NoGoodsProp::post(home,*this));
387 }
388
389}}}
390
391// STATISTICS: search-seq