Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
path.hpp
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$ by $Author$
11  * $Revision$
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 namespace Gecode { namespace Search { namespace Seq {
39 
40  /*
41  * Edge for recomputation
42  *
43  */
44  template<class Tracer>
47 
48  template<class Tracer>
51  : _space(c), _alt(0), _choice(s->choice()), _nid(nid) {}
52 
53  template<class Tracer>
56  return _space;
57  }
58  template<class Tracer>
59  forceinline void
61  _space = s;
62  }
63 
64  template<class Tracer>
65  forceinline unsigned int
67  return _alt;
68  }
69  template<class Tracer>
70  forceinline unsigned int
72  return std::min(_alt,_choice->alternatives()-1);
73  }
74  template<class Tracer>
75  forceinline bool
77  return _alt == 0;
78  }
79  template<class Tracer>
80  forceinline bool
82  return _alt+1 >= _choice->alternatives();
83  }
84  template<class Tracer>
85  forceinline bool
87  return _alt >= _choice->alternatives();
88  }
89  template<class Tracer>
90  forceinline void
92  _alt++;
93  }
94 
95  template<class Tracer>
96  forceinline const Choice*
98  return _choice;
99  }
100 
101  template<class Tracer>
102  forceinline unsigned int
104  return _nid;
105  }
106 
107  template<class Tracer>
108  forceinline void
110  delete _space;
111  delete _choice;
112  }
113 
114 
115 
116  /*
117  * Depth-first stack with recomputation
118  *
119  */
120 
121  template<class Tracer>
123  Path<Tracer>::Path(unsigned int l)
124  : ds(heap), _ngdl(l) {}
125 
126  template<class Tracer>
127  forceinline unsigned int
128  Path<Tracer>::ngdl(void) const {
129  return _ngdl;
130  }
131 
132  template<class Tracer>
133  forceinline void
134  Path<Tracer>::ngdl(unsigned int l) {
135  _ngdl = l;
136  }
137 
138  template<class Tracer>
139  forceinline const Choice*
140  Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
141  if (!ds.empty() && ds.top().lao()) {
142  // Topmost stack entry was LAO -> reuse
143  ds.pop().dispose();
144  }
145  Edge sn(s,c,nid);
146  ds.push(sn);
147  stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
148  return sn.choice();
149  }
150 
151  template<class Tracer>
152  forceinline void
154  while (!ds.empty())
155  if (ds.top().rightmost()) {
156  ds.pop().dispose();
157  } else {
158  ds.top().next();
159  return;
160  }
161  }
162 
163  template<class Tracer>
165  Path<Tracer>::top(void) const {
166  assert(!ds.empty());
167  return ds.top();
168  }
169 
170  template<class Tracer>
171  forceinline bool
172  Path<Tracer>::empty(void) const {
173  return ds.empty();
174  }
175 
176  template<class Tracer>
177  forceinline void
178  Path<Tracer>::commit(Space* s, int i) const {
179  const Edge& n = ds[i];
180  s->commit(*n.choice(),n.alt());
181  }
182 
183  template<class Tracer>
184  forceinline int
185  Path<Tracer>::lc(void) const {
186  int l = ds.entries()-1;
187  while (ds[l].space() == NULL)
188  l--;
189  return l;
190  }
191 
192  template<class Tracer>
193  forceinline int
194  Path<Tracer>::entries(void) const {
195  return ds.entries();
196  }
197 
198  template<class Tracer>
199  forceinline void
201  assert((ds[l].space() == NULL) || ds[l].space()->failed());
202  int n = ds.entries();
203  if (t) {
204  for (int i=l; i<n; i++) {
205  Path<Tracer>::Edge& top = ds.top();
206  unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
207  for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
208  SearchTracer::EdgeInfo ei(t.wid(),top.nid(),a);
209  t.skip(ei);
210  }
211  ds.pop().dispose();
212  }
213  } else {
214  for (int i=l; i<n; i++)
215  ds.pop().dispose();
216  }
217  assert(ds.entries() == l);
218  }
219 
220  template<class Tracer>
221  inline void
223  while (!ds.empty())
224  ds.pop().dispose();
225  }
226 
227  template<class Tracer>
229  Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
230  Tracer& t) {
231  assert(!ds.empty());
232  // Recompute space according to path
233  // Also say distance to copy (d == 0) requires immediate copying
234 
235  // Check for LAO
236  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
237  Space* s = ds.top().space();
238  s->commit(*ds.top().choice(),ds.top().alt());
239  assert(ds.entries()-1 == lc());
240  ds.top().space(NULL);
241  // Mark as reusable
242  if (static_cast<unsigned int>(ds.entries()) > ngdl())
243  ds.top().next();
244  d = 0;
245  return s;
246  }
247  // General case for recomputation
248  int l = lc(); // Position of last clone
249  int n = ds.entries(); // Number of stack entries
250  // New distance, if no adaptive recomputation
251  d = static_cast<unsigned int>(n - l);
252 
253  Space* s = ds[l].space()->clone(); // Last clone
254 
255  if (d < a_d) {
256  // No adaptive recomputation
257  for (int i=l; i<n; i++)
258  commit(s,i);
259  } else {
260  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
261  int i = l; // To iterate over all entries
262  // Recompute up to middle
263  for (; i<m; i++ )
264  commit(s,i);
265  // Skip over all rightmost branches
266  for (; (i<n) && ds[i].rightmost(); i++)
267  commit(s,i);
268  // Is there any point to make a copy?
269  if (i<n-1) {
270  // Propagate to fixpoint
271  SpaceStatus ss = s->status(stat);
272  /*
273  * Again, the space might already propagate to failure (due to
274  * weakly monotonic propagators).
275  */
276  if (ss == SS_FAILED) {
277  // s must be deleted as it is not on the stack
278  delete s;
279  stat.fail++;
280  unwind(i,t);
281  return NULL;
282  }
283  ds[i].space(s->clone());
284  d = static_cast<unsigned int>(n-i);
285  }
286  // Finally do the remaining commits
287  for (; i<n; i++)
288  commit(s,i);
289  }
290  return s;
291  }
292 
293  template<class Tracer>
295  Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
296  const Space& best, int& mark,
297  Tracer& t) {
298  assert(!ds.empty());
299  // Recompute space according to path
300  // Also say distance to copy (d == 0) requires immediate copying
301 
302  // Check for LAO
303  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
304  Space* s = ds.top().space();
305  s->commit(*ds.top().choice(),ds.top().alt());
306  assert(ds.entries()-1 == lc());
307  if (mark > ds.entries()-1) {
308  mark = ds.entries()-1;
309  s->constrain(best);
310  }
311  ds.top().space(NULL);
312  // Mark as reusable
313  if (static_cast<unsigned int>(ds.entries()) > ngdl())
314  ds.top().next();
315  d = 0;
316  return s;
317  }
318  // General case for recomputation
319  int l = lc(); // Position of last clone
320  int n = ds.entries(); // Number of stack entries
321  // New distance, if no adaptive recomputation
322  d = static_cast<unsigned int>(n - l);
323 
324  Space* s = ds[l].space(); // Last clone
325 
326  if (l < mark) {
327  mark = l;
328  s->constrain(best);
329  // The space on the stack could be failed now as an additional
330  // constraint might have been added.
331  if (s->status(stat) == SS_FAILED) {
332  // s does not need deletion as it is on the stack (unwind does this)
333  stat.fail++;
334  unwind(l,t);
335  return NULL;
336  }
337  // It is important to replace the space on the stack with the
338  // copy: a copy might be much smaller due to flushed caches
339  // of propagators
340  Space* c = s->clone();
341  ds[l].space(c);
342  } else {
343  s = s->clone();
344  }
345 
346  if (d < a_d) {
347  // No adaptive recomputation
348  for (int i=l; i<n; i++)
349  commit(s,i);
350  } else {
351  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
352  int i = l; // To iterate over all entries
353  // Recompute up to middle
354  for (; i<m; i++ )
355  commit(s,i);
356  // Skip over all rightmost branches
357  for (; (i<n) && ds[i].rightmost(); i++)
358  commit(s,i);
359  // Is there any point to make a copy?
360  if (i<n-1) {
361  // Propagate to fixpoint
362  SpaceStatus ss = s->status(stat);
363  /*
364  * Again, the space might already propagate to failure
365  *
366  * This can be for two reasons:
367  * - constrain is true, so we fail
368  * - the space has weakly monotonic propagators
369  */
370  if (ss == SS_FAILED) {
371  // s must be deleted as it is not on the stack
372  delete s;
373  stat.fail++;
374  unwind(i,t);
375  return NULL;
376  }
377  ds[i].space(s->clone());
378  d = static_cast<unsigned int>(n-i);
379  }
380  // Finally do the remaining commits
381  for (; i<n; i++)
382  commit(s,i);
383  }
384  return s;
385  }
386 
387  template<class Tracer>
388  void
389  Path<Tracer>::post(Space& home) const {
390  GECODE_ES_FAIL(NoGoodsProp::post(home,*this));
391  }
392 
393 }}}
394 
395 // STATISTICS: search-seq
Edge information.
Definition: search.hh:244
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3640
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:115
NodeType t
Type of node.
Definition: bool-expr.cpp:234
unsigned int _ngdl
Depth limit for no-good generation.
Definition: path.hh:117
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:68
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:242
SpaceStatus
Space status
Definition: core.hpp:1607
const Choice * choice(void) const
Return choice.
Definition: path.hpp:97
bool empty(void) const
Test whether path is empty.
Definition: path.hpp:172
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:152
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:103
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Search tree edge for recomputation
Definition: path.hh:70
#define forceinline
Definition: config.hpp:182
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:74
Computation spaces.
Definition: core.hpp:1668
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:71
int entries(void) const
Return number of entries on stack.
Definition: path.hpp:194
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hpp:86
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition: path.hpp:123
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3144
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:117
const Choice * _choice
Choice.
Definition: path.hh:77
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3152
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:807
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:73
const Choice * choice(void) const
Return choice.
Definition: path.hpp:112
Search worker statistics
Definition: worker.hh:48
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:66
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:64
void next(void)
Move to next alternative.
Definition: path.hpp:91
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1338
Heap heap
The single global heap.
Definition: heap.cpp:48
bool leftmost(void) const
Test whether current alternative is leftmost.
Definition: path.hpp:76
unsigned int _alt
Current alternative.
Definition: path.hh:75
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:229
Tracer.
Definition: tracer.hpp:153
void stack_depth(unsigned long int d)
Record stack depth d.
Definition: worker.hh:104
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hpp:81
Edge(void)
Default constructor.
Definition: path.hpp:46
Gecode toplevel namespace
Space * space(void) const
Return space for edge.
Definition: path.hpp:55
Space is failed
Definition: core.hpp:1608
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:107
ID _nid
Node identifier.
Definition: path.hh:79
void dispose(void)
Free memory for edge.
Definition: path.hpp:109
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hpp:165