38 #ifndef __GECODE_SEARCH_PARALLEL_PATH_HH__
39 #define __GECODE_SEARCH_PARALLEL_PATH_HH__
46 namespace Gecode {
namespace Search {
namespace Parallel {
90 unsigned int alt(
void)
const;
92 unsigned int truealt(
void)
const;
98 bool work(
void)
const;
102 unsigned int steal(
void);
118 int ngdl(
void)
const;
128 bool empty(
void)
const;
145 bool steal(
void)
const;
162 : _space(c), _alt(0), _choice(s->choice()) {
181 assert(_alt < _choice->alternatives());
186 return _alt >= _alt_max;
190 return _alt > _alt_max;
194 return _alt < _alt_max;
240 if (!
ds.empty() &&
ds.top().lao()) {
248 stat.
stack_depth(static_cast<unsigned long int>(
ds.entries()));
255 if (
ds.top().rightmost()) {
258 assert(
ds.top().work());
260 if (!
ds.top().work())
285 int l =
ds.entries()-1;
286 while (
ds[l].space() == NULL)
298 assert((
ds[l].space() == NULL) ||
ds[l].space()->failed());
299 int n =
ds.entries();
300 for (
int i=l;
i<
n;
i++) {
305 assert(
ds.entries() ==
l);
324 int n =
ds.entries()-1;
333 while (
ds[l].space() == NULL)
337 for (
int i=l;
i<
n;
i++)
344 d = stat.
steal_depth(static_cast<unsigned long int>(n+1));
359 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
362 assert(
ds.entries()-1 ==
lc());
363 ds.top().space(NULL);
365 if (
ds.entries() >
ngdl())
372 int n =
ds.entries();
374 d =
static_cast<unsigned int>(n -
l);
380 for (
int i=l;
i<
n;
i++)
383 int m = l +
static_cast<int>(d >> 1);
389 for (; (i<
n) &&
ds[i].rightmost(); i++)
407 d =
static_cast<unsigned int>(n-
i);
424 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
427 assert(
ds.entries()-1 ==
lc());
428 if (mark >
ds.entries()-1) {
429 mark =
ds.entries()-1;
432 ds.top().space(NULL);
434 if (
ds.entries() >
ngdl())
441 int n =
ds.entries();
443 d =
static_cast<unsigned int>(n -
l);
469 for (
int i=l;
i<
n;
i++)
472 int m = l +
static_cast<int>(d >> 1);
478 for (; (i<
n) &&
ds[i].rightmost(); i++)
499 d =
static_cast<unsigned int>(n-
i);
Space * space(void) const
Return space for edge.
Depth-first path (stack of edges) supporting recomputation.
Search tree edge for recomputation
bool steal(void) const
Make a quick check whether stealing might be feasible.
Edge & top(void) const
Provide access to topmost edge.
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Edge(void)
Default constructor.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
unsigned long int fail
Number of failed nodes in search tree.
unsigned int n_work
Number of edges that have work for stealing.
unsigned int alternatives(void) const
Return number of alternatives.
void * mark(void *p)
Return marked pointer for p.
const Choice * _choice
Choice.
Heap heap
The single global heap.
const Choice * choice(void) const
Return choice.
void next(void)
Move to next alternative.
Gecode::FloatVal c(-8, 8)
bool empty(void) const
Test whether path is empty.
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void unwind(int l)
Unwind the stack up to position l (after failure)
unsigned int steal(void)
Steal rightmost alternative and return its number.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
int _ngdl
Depth limit for no-good generation.
virtual void post(Space &home) const
Post no-goods.
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
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.
unsigned int _alt
Current alternative.
int entries(void) const
Return number of entries on stack.
unsigned int alt(void) const
Return number for alternatives.
bool work(void) const
Test whether there is an alternative that can be stolen.
Space * _space
Space corresponding to this edge (might be NULL)
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s)
Recompute space according to path.
void dispose(void)
Free memory for edge.
Path(int l)
Initialize with no-good depth limit l.
void next(void)
Generate path for next node.
int ngdl(void) const
Return no-good depth limit.
Choice for performing commit
No-goods recorded from restarts.
Stack with arbitrary number of elements.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
int lc(void) const
Return position on stack of last copy.
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
void stack_depth(unsigned long int d)
Record stack depth d.
bool rightmost(void) const
Test whether current alternative is rightmost.
Gecode toplevel namespace
unsigned int _alt_max
Number of alternatives left.
unsigned long int n
Number of no-goods.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
void reset(int l)
Reset stack and set no-good depth limit to l.
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
bool lao(void) const
Test whether current alternative was LAO.