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())
286 int l =
ds.entries()-1;
287 while (
ds[
l].space() == NULL)
299 assert((
ds[
l].space() == NULL) ||
ds[
l].space()->failed());
300 int n =
ds.entries();
301 for (
int i=
l;
i<
n;
i++) {
306 assert(
ds.entries() ==
l);
325 int n =
ds.entries()-1;
334 while (
ds[
l].space() == NULL)
338 for (
int i=
l;
i<
n;
i++)
360 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
363 assert(
ds.entries()-1 ==
lc());
364 ds.top().space(NULL);
366 if (
ds.entries() >
ngdl())
373 int n =
ds.entries();
375 d = static_cast<unsigned int>(
n -
l);
381 for (
int i=
l;
i<
n;
i++)
384 int m =
l + static_cast<int>(
d >> 1);
390 for (; (
i<
n) &&
ds[
i].rightmost();
i++)
408 d = static_cast<unsigned int>(
n-
i);
425 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
428 assert(
ds.entries()-1 ==
lc());
429 if (
mark >
ds.entries()-1) {
433 ds.top().space(NULL);
435 if (
ds.entries() >
ngdl())
442 int n =
ds.entries();
444 d = static_cast<unsigned int>(
n -
l);
470 for (
int i=
l;
i<
n;
i++)
473 int m =
l + static_cast<int>(
d >> 1);
479 for (; (
i<
n) &&
ds[
i].rightmost();
i++)
500 d = static_cast<unsigned int>(
n-
i);
unsigned int alternatives(void) const
Return number of alternatives.
Depth-first path (stack of edges) supporting recomputation.
bool empty(void) const
Test whether path is empty.
Search tree edge for recomputation
Edge(void)
Default constructor.
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
unsigned long int fail
Number of failed nodes in search tree.
int ngdl(void) const
Return no-good depth limit.
int lc(void) const
Return position on stack of last copy.
unsigned int n_work
Number of edges that have work for stealing.
void * mark(void *p)
Return marked pointer for p.
const Choice * _choice
Choice.
unsigned int alt(void) const
Return number for alternatives.
Heap heap
The single global heap.
void next(void)
Move to next alternative.
Gecode::FloatVal c(-8, 8)
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.
Edge & top(void) const
Provide access to topmost edge.
bool next(void)
Generate path for next node and return whether a next node exists.
int entries(void) const
Return number of entries on stack.
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.
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.
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Choice for performing commit
No-goods recorded from restarts.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
bool rightmost(void) const
Test whether current alternative is rightmost.
virtual void post(Space &home)
Post no-goods.
Stack with arbitrary number of elements.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
bool steal(void) const
Make a quick check whether stealing might be feasible.
void stack_depth(unsigned long int d)
Record stack depth d.
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Gecode toplevel namespace
const Choice * choice(void) const
Return choice.
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.
Space * space(void) const
Return space for edge.
bool lao(void) const
Test whether current alternative was LAO.
bool work(void) const
Test whether there is an alternative that can be stolen.