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()) {
263 int l =
ds.entries()-1;
264 while (
ds[l].space() == NULL)
276 assert((
ds[l].space() == NULL) ||
ds[l].space()->failed());
277 int n =
ds.entries();
278 for (
int i=l;
i<
n;
i++)
280 assert(
ds.entries() ==
l);
296 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
299 assert(
ds.entries()-1 ==
lc());
300 ds.top().space(NULL);
302 if (
ds.entries() >
ngdl())
309 int n =
ds.entries();
311 d =
static_cast<unsigned int>(n -
l);
317 for (
int i=l;
i<
n;
i++)
320 int m = l +
static_cast<int>(d >> 1);
326 for (; (i<
n) &&
ds[i].rightmost(); i++)
344 d =
static_cast<unsigned int>(n-
i);
361 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
364 assert(
ds.entries()-1 ==
lc());
365 if (mark >
ds.entries()-1) {
366 mark =
ds.entries()-1;
369 ds.top().space(NULL);
371 if (
ds.entries() >
ngdl())
378 int n =
ds.entries();
380 d =
static_cast<unsigned int>(n -
l);
406 for (
int i=l;
i<
n;
i++)
409 int m = l +
static_cast<int>(d >> 1);
415 for (; (i<
n) &&
ds[i].rightmost(); i++)
436 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.
Edge & top(void) const
Provide access to topmost edge.
virtual void post(Space &home) const
Post no-goods.
void reset(void)
Reset stack.
void dispose(void)
Free memory for edge.
Choice for performing commit
No-goods recorded from restarts.
void next(void)
Generate path for next node.
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.
Gecode toplevel namespace
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.