Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.1
path.hh
Go to the documentation of this file.
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  * Last modified:
10  * $Date: 2013-02-26 10:47:43 +0100 (Tue, 26 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13414 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
39 #define __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
40 
41 #include <gecode/search.hh>
42 
43 namespace Gecode { namespace Search { namespace Sequential {
44 
58  class Path {
59  public:
61  class Edge {
62  protected:
66  unsigned int _alt;
68  const Choice* _choice;
69  public:
71  Edge(void);
73  Edge(Space* s, Space* c);
74 
76  Space* space(void) const;
78  void space(Space* s);
79 
81  const Choice* choice(void) const;
82 
84  unsigned int alt(void) const;
86  bool rightmost(void) const;
88  void next(void);
90  bool lao(void) const;
91 
93  void dispose(void);
94  };
95  protected:
98  public:
100  Path(void);
102  const Choice* push(Worker& stat, Space* s, Space* c);
104  bool next(Worker& s);
106  Edge& top(void) const;
108  bool empty(void) const;
110  int lc(void) const;
112  void unwind(int l);
114  void commit(Space* s, int i) const;
116  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
118  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
119  const Space* best, int& mark);
121  int entries(void) const;
123  size_t size(void) const;
125  void reset(void);
126  };
127 
128 
129  /*
130  * Edge for recomputation
131  *
132  */
135 
138  : _space(c), _alt(0), _choice(s->choice()) {}
139 
141  Path::Edge::space(void) const {
142  return _space;
143  }
144  forceinline void
146  _space = s;
147  }
148 
149  forceinline unsigned int
150  Path::Edge::alt(void) const {
151  return _alt;
152  }
153  forceinline bool
154  Path::Edge::rightmost(void) const {
155  return _alt+1 >= _choice->alternatives();
156  }
157  forceinline bool
158  Path::Edge::lao(void) const {
159  return _alt >= _choice->alternatives();
160  }
161  forceinline void
163  _alt++;
164  }
165 
166  forceinline const Choice*
167  Path::Edge::choice(void) const {
168  return _choice;
169  }
170 
171  forceinline void
173  delete _space;
174  delete _choice;
175  }
176 
177 
178 
179  /*
180  * Depth-first stack with recomputation
181  *
182  */
183 
185  Path::Path(void) : ds(heap) {}
186 
187  forceinline const Choice*
188  Path::push(Worker& stat, Space* s, Space* c) {
189  if (!ds.empty() && ds.top().lao()) {
190  // Topmost stack entry was LAO -> reuse
191  stat.pop(ds.top().space(),ds.top().choice());
192  ds.pop().dispose();
193  }
194  Edge sn(s,c);
195  ds.push(sn);
196  stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
197  return sn.choice();
198  }
199 
200  forceinline bool
202  while (!ds.empty())
203  if (ds.top().rightmost()) {
204  stat.pop(ds.top().space(),ds.top().choice());
205  ds.pop().dispose();
206  } else {
207  ds.top().next();
208  return true;
209  }
210  return false;
211  }
212 
214  Path::top(void) const {
215  assert(!ds.empty());
216  return ds.top();
217  }
218 
219  forceinline bool
220  Path::empty(void) const {
221  return ds.empty();
222  }
223 
224  forceinline void
225  Path::commit(Space* s, int i) const {
226  const Edge& n = ds[i];
227  s->commit(*n.choice(),n.alt());
228  }
229 
230  forceinline int
231  Path::lc(void) const {
232  int l = ds.entries()-1;
233  while (ds[l].space() == NULL)
234  l--;
235  return l;
236  }
237 
238  forceinline int
239  Path::entries(void) const {
240  return ds.entries();
241  }
242 
243  forceinline size_t
244  Path::size(void) const {
245  return ds.size();
246  }
247 
248  forceinline void
250  assert((ds[l].space() == NULL) || ds[l].space()->failed());
251  int n = ds.entries();
252  for (int i=l; i<n; i++)
253  ds.pop().dispose();
254  assert(ds.entries() == l);
255  }
256 
257  inline void
258  Path::reset(void) {
259  while (!ds.empty())
260  ds.pop().dispose();
261  }
262 
264  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
265  assert(!ds.empty());
266  // Recompute space according to path
267  // Also say distance to copy (d == 0) requires immediate copying
268 
269  // Check for LAO
270  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
271  Space* s = ds.top().space();
272  stat.lao(s);
273  s->commit(*ds.top().choice(),ds.top().alt());
274  assert(ds.entries()-1 == lc());
275  ds.top().space(NULL);
276  // Mark as reusable
277  ds.top().next();
278  d = 0;
279  return s;
280  }
281  // General case for recomputation
282  int l = lc(); // Position of last clone
283  int n = ds.entries(); // Number of stack entries
284  // New distance, if no adaptive recomputation
285  d = static_cast<unsigned int>(n - l);
286 
287  Space* s = ds[l].space()->clone(); // Last clone
288 
289  if (d < a_d) {
290  // No adaptive recomputation
291  for (int i=l; i<n; i++)
292  commit(s,i);
293  } else {
294  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
295  int i = l; // To iterate over all entries
296  // Recompute up to middle
297  for (; i<m; i++ )
298  commit(s,i);
299  // Skip over all rightmost branches
300  for (; (i<n) && ds[i].rightmost(); i++)
301  commit(s,i);
302  // Is there any point to make a copy?
303  if (i<n-1) {
304  // Propagate to fixpoint
305  SpaceStatus ss = s->status(stat);
306  /*
307  * Again, the space might already propagate to failure (due to
308  * weakly monotonic propagators).
309  */
310  if (ss == SS_FAILED) {
311  // s must be deleted as it is not on the stack
312  delete s;
313  stat.fail++;
314  unwind(i);
315  return NULL;
316  }
317  ds[i].space(s->clone());
318  stat.adapt(ds[i].space());
319  d = static_cast<unsigned int>(n-i);
320  }
321  // Finally do the remaining commits
322  for (; i<n; i++)
323  commit(s,i);
324  }
325  return s;
326  }
327 
329  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
330  const Space* best, int& mark) {
331  assert(!ds.empty());
332  // Recompute space according to path
333  // Also say distance to copy (d == 0) requires immediate copying
334 
335  // Check for LAO
336  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
337  Space* s = ds.top().space();
338  stat.lao(s);
339  s->commit(*ds.top().choice(),ds.top().alt());
340  assert(ds.entries()-1 == lc());
341  if (mark > ds.entries()-1) {
342  mark = ds.entries()-1;
343  s->constrain(*best);
344  }
345  ds.top().space(NULL);
346  // Mark as reusable
347  ds.top().next();
348  d = 0;
349  return s;
350  }
351  // General case for recomputation
352  int l = lc(); // Position of last clone
353  int n = ds.entries(); // Number of stack entries
354  // New distance, if no adaptive recomputation
355  d = static_cast<unsigned int>(n - l);
356 
357  Space* s = ds[l].space(); // Last clone
358 
359  if (l < mark) {
360  mark = l;
361  s->constrain(*best);
362  // The space on the stack could be failed now as an additional
363  // constraint might have been added.
364  if (s->status(stat) == SS_FAILED) {
365  // s does not need deletion as it is on the stack (unwind does this)
366  stat.fail++;
367  unwind(l);
368  return NULL;
369  }
370  // It is important to replace the space on the stack with the
371  // copy: a copy might be much smaller due to flushed caches
372  // of propagators
373  Space* c = s->clone();
374  ds[l].space(c);
375  stat.constrained(s,c);
376  } else {
377  s = s->clone();
378  }
379 
380  if (d < a_d) {
381  // No adaptive recomputation
382  for (int i=l; i<n; i++)
383  commit(s,i);
384  } else {
385  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
386  int i = l; // To iterate over all entries
387  // Recompute up to middle
388  for (; i<m; i++ )
389  commit(s,i);
390  // Skip over all rightmost branches
391  for (; (i<n) && ds[i].rightmost(); i++)
392  commit(s,i);
393  // Is there any point to make a copy?
394  if (i<n-1) {
395  // Propagate to fixpoint
396  SpaceStatus ss = s->status(stat);
397  /*
398  * Again, the space might already propagate to failure
399  *
400  * This can be for two reasons:
401  * - constrain is true, so we fail
402  * - the space has weakly monotonic propagators
403  */
404  if (ss == SS_FAILED) {
405  // s must be deleted as it is not on the stack
406  delete s;
407  stat.fail++;
408  unwind(i);
409  return NULL;
410  }
411  ds[i].space(s->clone());
412  stat.adapt(ds[i].space());
413  d = static_cast<unsigned int>(n-i);
414  }
415  // Finally do the remaining commits
416  for (; i<n; i++)
417  commit(s,i);
418  }
419  return s;
420  }
421 
422 }}}
423 
424 #endif
425 
426 // STATISTICS: search-sequential