38 #ifndef __GECODE_SEARCH_SEQUENTIAL_PATH_HH__ 39 #define __GECODE_SEARCH_SEQUENTIAL_PATH_HH__ 46 namespace Gecode {
namespace Search {
namespace Sequential {
80 Space* space(
void)
const;
85 const Choice* choice(
void)
const;
88 unsigned int alt(
void)
const;
90 unsigned int truealt(
void)
const;
92 bool leftmost(
void)
const;
94 bool rightmost(
void)
const;
110 Path(
unsigned int l);
112 unsigned int ngdl(
void)
const;
114 void ngdl(
unsigned int l);
120 Edge& top(
void)
const;
122 bool empty(
void)
const;
128 void commit(
Space* s,
int i)
const;
135 int entries(
void)
const;
152 : _space(c), _alt(0), _choice(s->choice()) {}
169 assert(_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 (static_cast<unsigned int>(
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 (static_cast<unsigned int>(
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);
bool lao(void) const
Test whether current alternative was LAO.
unsigned int alternatives(void) const
Return number of alternatives.
Search tree edge for recomputation
Space * _space
Space corresponding to this edge (might be NULL)
void next(void)
Move to next alternative.
Edge(void)
Default constructor.
#define GECODE_SEARCH_EXPORT
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
unsigned int _ngdl
Depth limit for no-good generation.
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.
bool empty(void) const
Test whether path is empty.
Path(unsigned int l)
Initialize with no-good depth limit l.
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
void * mark(void *p)
Return marked pointer for p.
const Choice * choice(void) const
Return choice.
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
int lc(void) const
Return position on stack of last copy.
const Choice * _choice
Choice.
unsigned int alt(void) const
Return number for alternatives.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
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.
bool leftmost(void) const
Test whether current alternative is leftmost.
void reset(void)
Reset stack.
void dispose(void)
Free memory for edge.
Choice for performing commit
No-goods recorded from restarts.
Heap heap
The single global heap.
void next(void)
Generate path for next node.
int entries(void) const
Return number of entries on stack.
Stack with arbitrary number of elements.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
bool rightmost(void) const
Test whether current alternative is rightmost.
void stack_depth(unsigned long int d)
Record stack depth d.
unsigned int ngdl(void) const
Return no-good depth limit.
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Edge & top(void) const
Provide access to topmost edge.
unsigned long int n
Number of no-goods.
Space * space(void) const
Return space for edge.
unsigned int _alt
Current alternative.
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.