Generated on Tue Mar 24 2020 14:04:04 for Gecode by doxygen 1.8.17
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  * 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 namespace Gecode { namespace Search { namespace Seq {
35 
36  /*
37  * Edge for recomputation
38  *
39  */
40  template<class Tracer>
43 
44  template<class Tracer>
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>
52  return _space;
53  }
54  template<class Tracer>
55  forceinline void
57  _space = s;
58  }
59 
60  template<class Tracer>
61  forceinline unsigned int
63  return _alt;
64  }
65  template<class Tracer>
66  forceinline unsigned int
68  return std::min(_alt,_choice->alternatives()-1);
69  }
70  template<class Tracer>
71  forceinline bool
73  return _alt == 0;
74  }
75  template<class Tracer>
76  forceinline bool
78  return _alt+1 >= _choice->alternatives();
79  }
80  template<class Tracer>
81  forceinline bool
83  return _alt >= _choice->alternatives();
84  }
85  template<class Tracer>
86  forceinline void
88  _alt++;
89  }
90 
91  template<class Tracer>
92  forceinline const Choice*
94  return _choice;
95  }
96 
97  template<class Tracer>
98  forceinline unsigned int
100  return _nid;
101  }
102 
103  template<class Tracer>
104  forceinline 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>
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
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>
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() == NULL)
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
197  assert((ds[l].space() == NULL) || 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
219  while (!ds.empty())
220  ds.pop().dispose();
221  }
222 
223  template<class Tracer>
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() != NULL) && 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(NULL);
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 NULL;
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>
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() != NULL) && 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(NULL);
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 NULL;
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 NULL;
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
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:70
Search worker statistics
Definition: worker.hh:44
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:67
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hpp:82
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition: path.hpp:119
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:841
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hpp:161
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3770
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:150
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:60
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:111
void * mark(void *p)
Return marked pointer for unmarked pointer p.
bool leftmost(void) const
Test whether current alternative is leftmost.
Definition: path.hpp:72
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Search tree edge for recomputation
Definition: path.hh:66
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3232
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Computation spaces.
Definition: core.hpp:1742
bool empty(void) const
Test whether path is empty.
Definition: path.hpp:168
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:62
Gecode toplevel namespace
const Choice * choice(void) const
Return choice.
Definition: path.hpp:108
void next(void)
Move to next alternative.
Definition: path.hpp:87
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3224
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:99
Search tree edge for recomputation
Definition: path.hh:66
int entries(void) const
Return number of entries on stack.
Definition: path.hpp:190
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hpp:77
Space * space(void) const
Return space for edge.
Definition: path.hpp:51
void dispose(void)
Free memory for edge.
Definition: path.hpp:105
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
const Choice * choice(void) const
Return choice.
Definition: path.hpp:93
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Tracer.
Definition: tracer.hpp:149
Heap heap
The single global heap.
Definition: heap.cpp:44
Edge information.
Definition: search.hh:242
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
unsigned int _ngdl
Depth limit for no-good generation.
Definition: path.hh:113
Gecode::IntSet d(v, 7)
void stack_depth(unsigned long int d)
Record stack depth d.
Definition: worker.hh:100
#define forceinline
Definition: config.hpp:185
SpaceStatus
Space status
Definition: core.hpp:1681
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Choice for performing commit
Definition: core.hpp:1412
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:64
Gecode::IntArgs i({1, 2, 3, 4})
@ SS_FAILED
Space is failed
Definition: core.hpp:1682
Edge(void)
Default constructor.
Definition: path.hpp:42