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.
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
#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.
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.
Heap heap
The single global heap.
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.
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Choice for performing commit
No-goods recorded from restarts.
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.