Generated on Thu Feb 21 2013 23:11:48 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: 2010-07-22 19:59:14 +1000 (Thu, 22 Jul 2010) $ by $Author: schulte $
11  * $Revision: 11248 $
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);
89 
91  void dispose(void);
92  };
93  protected:
96  public:
98  Path(void);
100  const Choice* push(Worker& stat, Space* s, Space* c);
102  bool next(Worker& s);
104  Edge& top(void) const;
106  bool empty(void) const;
108  int lc(void) const;
110  void unwind(int l);
112  void commit(Space* s, int i) const;
114  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
116  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
117  const Space* best, int& mark);
119  int entries(void) const;
121  size_t size(void) const;
123  void reset(void);
124  };
125 
126 
127  /*
128  * Edge for recomputation
129  *
130  */
133 
136  : _space(c), _alt(0), _choice(s->choice()) {}
137 
139  Path::Edge::space(void) const {
140  return _space;
141  }
142  forceinline void
144  _space = s;
145  }
146 
147  forceinline unsigned int
148  Path::Edge::alt(void) const {
149  return _alt;
150  }
151  forceinline bool
152  Path::Edge::rightmost(void) const {
153  return _alt+1 == _choice->alternatives();
154  }
155  forceinline void
157  _alt++;
158  }
159 
160  forceinline const Choice*
161  Path::Edge::choice(void) const {
162  return _choice;
163  }
164 
165  forceinline void
167  delete _space;
168  delete _choice;
169  }
170 
171 
172 
173  /*
174  * Depth-first stack with recomputation
175  *
176  */
177 
179  Path::Path(void) : ds(heap) {}
180 
181  forceinline const Choice*
182  Path::push(Worker& stat, Space* s, Space* c) {
183  Edge sn(s,c);
184  ds.push(sn);
185  stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
186  return sn.choice();
187  }
188 
189  forceinline bool
191  while (!ds.empty())
192  if (ds.top().rightmost()) {
193  stat.pop(ds.top().space(),ds.top().choice());
194  ds.pop().dispose();
195  } else {
196  ds.top().next();
197  return true;
198  }
199  return false;
200  }
201 
203  Path::top(void) const {
204  assert(!ds.empty());
205  return ds.top();
206  }
207 
208  forceinline bool
209  Path::empty(void) const {
210  return ds.empty();
211  }
212 
213  forceinline void
214  Path::commit(Space* s, int i) const {
215  const Edge& n = ds[i];
216  s->commit(*n.choice(),n.alt());
217  }
218 
219  forceinline int
220  Path::lc(void) const {
221  int l = ds.entries()-1;
222  while (ds[l].space() == NULL)
223  l--;
224  return l;
225  }
226 
227  forceinline int
228  Path::entries(void) const {
229  return ds.entries();
230  }
231 
232  forceinline size_t
233  Path::size(void) const {
234  return ds.size();
235  }
236 
237  forceinline void
238  Path::unwind(int l) {
239  assert((ds[l].space() == NULL) || ds[l].space()->failed());
240  int n = ds.entries();
241  for (int i=l; i<n; i++)
242  ds.pop().dispose();
243  assert(ds.entries() == l);
244  }
245 
246  inline void
247  Path::reset(void) {
248  while (!ds.empty())
249  ds.pop().dispose();
250  }
251 
253  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
254  assert(!ds.empty());
255  // Recompute space according to path
256  // Also say distance to copy (d == 0) requires immediate copying
257 
258  // Check for LAO
259  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
260  Space* s = ds.top().space();
261  stat.lao(s);
262  s->commit(*ds.top().choice(),ds.top().alt());
263  assert(ds.entries()-1 == lc());
264  ds.top().space(NULL);
265  d = 0;
266  return s;
267  }
268  // General case for recomputation
269  int l = lc(); // Position of last clone
270  int n = ds.entries(); // Number of stack entries
271  // New distance, if no adaptive recomputation
272  d = static_cast<unsigned int>(n - l);
273 
274  Space* s = ds[l].space()->clone(); // Last clone
275 
276  if (d < a_d) {
277  // No adaptive recomputation
278  for (int i=l; i<n; i++)
279  commit(s,i);
280  } else {
281  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
282  int i = l; // To iterate over all entries
283  // Recompute up to middle
284  for (; i<m; i++ )
285  commit(s,i);
286  // Skip over all rightmost branches
287  for (; (i<n) && ds[i].rightmost(); i++)
288  commit(s,i);
289  // Is there any point to make a copy?
290  if (i<n-1) {
291  // Propagate to fixpoint
292  SpaceStatus ss = s->status(stat);
293  /*
294  * Again, the space might already propagate to failure (due to
295  * weakly monotonic propagators).
296  */
297  if (ss == SS_FAILED) {
298  // s must be deleted as it is not on the stack
299  delete s;
300  stat.fail++;
301  unwind(i);
302  return NULL;
303  }
304  ds[i].space(s->clone());
305  stat.adapt(ds[i].space());
306  d = static_cast<unsigned int>(n-i);
307  }
308  // Finally do the remaining commits
309  for (; i<n; i++)
310  commit(s,i);
311  }
312  return s;
313  }
314 
316  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
317  const Space* best, int& mark) {
318  assert(!ds.empty());
319  // Recompute space according to path
320  // Also say distance to copy (d == 0) requires immediate copying
321 
322  // Check for LAO
323  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
324  Space* s = ds.top().space();
325  stat.lao(s);
326  s->commit(*ds.top().choice(),ds.top().alt());
327  assert(ds.entries()-1 == lc());
328  if (mark > ds.entries()-1) {
329  mark = ds.entries()-1;
330  s->constrain(*best);
331  }
332  ds.top().space(NULL);
333  d = 0;
334  return s;
335  }
336  // General case for recomputation
337  int l = lc(); // Position of last clone
338  int n = ds.entries(); // Number of stack entries
339  // New distance, if no adaptive recomputation
340  d = static_cast<unsigned int>(n - l);
341 
342  Space* s = ds[l].space(); // Last clone
343 
344  if (l < mark) {
345  mark = l;
346  s->constrain(*best);
347  // The space on the stack could be failed now as an additional
348  // constraint might have been added.
349  if (s->status(stat) == SS_FAILED) {
350  // s does not need deletion as it is on the stack (unwind does this)
351  stat.fail++;
352  unwind(l);
353  return NULL;
354  }
355  // It is important to replace the space on the stack with the
356  // copy: a copy might be much smaller due to flushed caches
357  // of propagators
358  Space* c = s->clone();
359  ds[l].space(c);
360  stat.constrained(s,c);
361  } else {
362  s = s->clone();
363  }
364 
365  if (d < a_d) {
366  // No adaptive recomputation
367  for (int i=l; i<n; i++)
368  commit(s,i);
369  } else {
370  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
371  int i = l; // To iterate over all entries
372  // Recompute up to middle
373  for (; i<m; i++ )
374  commit(s,i);
375  // Skip over all rightmost branches
376  for (; (i<n) && ds[i].rightmost(); i++)
377  commit(s,i);
378  // Is there any point to make a copy?
379  if (i<n-1) {
380  // Propagate to fixpoint
381  SpaceStatus ss = s->status(stat);
382  /*
383  * Again, the space might already propagate to failure
384  *
385  * This can be for two reasons:
386  * - constrain is true, so we fail
387  * - the space has weakly monotonic propagators
388  */
389  if (ss == SS_FAILED) {
390  // s must be deleted as it is not on the stack
391  delete s;
392  stat.fail++;
393  unwind(i);
394  return NULL;
395  }
396  ds[i].space(s->clone());
397  stat.adapt(ds[i].space());
398  d = static_cast<unsigned int>(n-i);
399  }
400  // Finally do the remaining commits
401  for (; i<n; i++)
402  commit(s,i);
403  }
404  return s;
405  }
406 
407 }}}
408 
409 #endif
410 
411 // STATISTICS: search-sequential