38 #ifndef __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
39 #define __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
46 namespace Gecode {
namespace Search {
namespace Sequential {
88 unsigned int alt(
void)
const;
90 unsigned int truealt(
void)
const;
112 int ngdl(
void)
const;
122 bool empty(
void)
const;
152 : _space(c), _alt(0), _choice(s->choice()) {}
169 assert(_alt < _choice->alternatives());
178 return _alt+1 >= _choice->alternatives();
182 return _alt >= _choice->alternatives();
223 if (!
ds.empty() &&
ds.top().lao()) {
229 stat.
stack_depth(static_cast<unsigned long int>(
ds.entries()));
236 if (
ds.top().rightmost()) {
264 int l =
ds.entries()-1;
265 while (
ds[l].space() == NULL)
277 assert((
ds[l].space() == NULL) ||
ds[l].space()->failed());
278 int n =
ds.entries();
279 for (
int i=l;
i<
n;
i++)
281 assert(
ds.entries() ==
l);
297 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
300 assert(
ds.entries()-1 ==
lc());
301 ds.top().space(NULL);
303 if (
ds.entries() >
ngdl())
310 int n =
ds.entries();
312 d =
static_cast<unsigned int>(n -
l);
318 for (
int i=l;
i<
n;
i++)
321 int m = l +
static_cast<int>(d >> 1);
327 for (; (i<
n) &&
ds[i].rightmost(); i++)
345 d =
static_cast<unsigned int>(n-
i);
362 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
365 assert(
ds.entries()-1 ==
lc());
366 if (mark >
ds.entries()-1) {
367 mark =
ds.entries()-1;
370 ds.top().space(NULL);
372 if (
ds.entries() >
ngdl())
379 int n =
ds.entries();
381 d =
static_cast<unsigned int>(n -
l);
407 for (
int i=l;
i<
n;
i++)
410 int m = l +
static_cast<int>(d >> 1);
416 for (; (i<
n) &&
ds[i].rightmost(); i++)
437 d =
static_cast<unsigned int>(n-
i);
Search tree edge for recomputation
Space * _space
Space corresponding to this edge (might be NULL)
int lc(void) const
Return position on stack of last copy.
void next(void)
Move to next alternative.
Edge(void)
Default constructor.
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
unsigned int alt(void) const
Return number for alternatives.
Depth-first path (stack of edges) supporting recomputation.
void unwind(int l)
Unwind the stack up to position l (after failure)
unsigned long int fail
Number of failed nodes in search tree.
void * mark(void *p)
Return marked pointer for p.
Heap heap
The single global heap.
int entries(void) const
Return number of entries on stack.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
const Choice * _choice
Choice.
bool lao(void) const
Test whether current alternative was LAO.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s)
Recompute space according to path.
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
virtual void constrain(const Space &best)
Constrain function for best solution search.
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
virtual void post(Space &home)
Post no-goods.
bool next(void)
Generate path for next node and return whether a next node exists.
Edge & top(void) const
Provide access to topmost edge.
void reset(void)
Reset stack.
void dispose(void)
Free memory for edge.
Choice for performing commit
No-goods recorded from restarts.
Stack with arbitrary number of elements.
Space * space(void) const
Return space for edge.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
void stack_depth(unsigned long int d)
Record stack depth d.
Path(int l)
Initialize with no-good depth limit l.
bool rightmost(void) const
Test whether current alternative is rightmost.
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
bool leftmost(void) const
Test whether current alternative is leftmost.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
unsigned long int n
Number of no-goods.
int ngdl(void) const
Return no-good depth limit.
unsigned int _alt
Current alternative.
const Choice * choice(void) const
Return choice.
int _ngdl
Depth limit for no-good generation.
bool empty(void) const
Test whether path is empty.