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) {
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);
bool lao(void) const
Test whether current alternative was LAO.
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.
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
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.
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.
virtual void post(Space &home)
Post no-goods.
bool next(void)
Generate path for next node and return whether a next node exists.
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.
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.
Path(int l)
Initialize with no-good depth limit l.
Gecode toplevel namespace
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.
int _ngdl
Depth limit for no-good generation.
int ngdl(void) const
Return no-good depth limit.