181 static const int idx_c = -1;
183 static const int idx_d = -1;
187 static const int free_bits = 0;
189 static const int med_fst = 0;
191 static const int med_lst = 0;
193 static const int med_mask = 0;
267 template<
class VarImp>
319 static const int idx_c = VIC::idx_c;
321 static const int idx_d = VIC::idx_d;
323 static const int free_bits = VIC::free_bits;
325 unsigned int entries;
327 unsigned int free_and_bits;
342 unsigned int idx[pc_max+1];
354 unsigned int idx(
PropCond pc)
const;
376 void resize(
Space& home);
385 void cancel(
Space& home);
392 #ifdef GECODE_HAS_VAR_DISPOSE 447 unsigned int degree(
void)
const;
454 double afc(
const Space& home)
const;
462 bool copied(
void)
const;
464 VarImp* forward(
void)
const;
505 unsigned int bits(
void)
const;
508 unsigned int& bits(
void);
518 static void*
operator new(size_t,
Space&);
521 static void operator delete(
void*,
Space&);
523 static void operator delete(
void*);
670 bool empty(
void)
const;
672 template<
class T>
static ActorLink* cast(T*
a);
674 template<
class T>
static const ActorLink* cast(
const T*
a);
706 virtual size_t dispose(
Space& home);
708 static void*
operator new(
size_t s,
Space& home);
710 static void operator delete(
void*
p,
Space& home);
716 static void*
operator new(
size_t s);
718 static void operator delete(
void*
p);
734 static const unsigned int GROUPID_ALL = 0U;
736 static const unsigned int GROUPID_DEF = 1U;
738 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
748 Group(
unsigned int gid0);
760 unsigned int id(
void)
const;
823 void kill(
Space& home);
826 void disable(
Space& home);
834 void enable(
Space& home,
bool s=
true);
892 void kill(
Space& home);
926 operator Space&(void);
945 bool failed(
void)
const;
985 What what(
void)
const;
989 const Brancher& brancher(
void)
const;
1130 double afc(
const Space& home)
const;
1135 unsigned int id(
void)
const;
1142 bool disabled(
void)
const;
1144 void kill(
Space& home);
1173 bool empty(
void)
const;
1177 void dispose(
Space& home);
1194 bool operator ()(
void)
const;
1196 void operator ++(
void);
1198 A& advisor(
void)
const;
1219 bool disposed(
void)
const;
1242 static void*
operator new(
size_t s,
Space& home);
1244 static void operator delete(
void*
p,
Space& home);
1248 static void operator delete(
void*
p);
1251 static void*
operator new(
size_t s);
1291 virtual bool notice(
void)
const;
1293 virtual size_t dispose(
Space& home);
1296 bool leaf(
void)
const;
1299 NGL* next(
void)
const;
1309 static void*
operator new(
size_t s,
Space& home);
1312 static void operator delete(
void* s,
Space& home);
1314 static void operator delete(
void*
p);
1320 static void*
operator new(
size_t s);
1339 unsigned int id(
void)
const;
1345 unsigned int alternatives(
void)
const;
1349 virtual size_t size(
void)
const = 0;
1352 virtual void archive(
Archive& e)
const;
1393 virtual bool status(
const Space& home)
const = 0;
1411 unsigned int a) = 0;
1438 std::ostream& o)
const;
1442 unsigned int id(
void)
const;
1449 void kill(
Space& home);
1520 unsigned long int n;
1528 unsigned long int ng(
void)
const;
1530 void ng(
unsigned long int n);
1556 const unsigned long int r;
1559 const unsigned long int s;
1561 const unsigned long int f;
1569 const unsigned int a;
1577 unsigned long int s,
1578 unsigned long int f,
1584 Type type(
void)
const;
1588 unsigned long int restart(
void)
const;
1591 unsigned long int solution(
void)
const;
1593 unsigned long int fail(
void)
const;
1595 const Space* last(
void)
const;
1597 const NoGoods& nogoods(
void)
const;
1601 unsigned int asset(
void)
const;
1676 friend class Propagators;
1679 friend class Branchers;
1719 Brancher* brancher(
unsigned int id);
1728 void kill_brancher(
unsigned int id);
1731 static const unsigned reserved_bid = 0U;
1776 #ifdef GECODE_HAS_VAR_DISPOSE 1782 template<
class VIC>
VarImpBase* vars_d(
void)
const;
1808 unsigned int _wmp_afc;
1810 void afc_enable(
void);
1812 bool afc_enabled(
void)
const;
1814 void wmp(
unsigned int n);
1816 unsigned int wmp(
void)
const;
1847 bool share_info=
true);
1882 void _commit(
const Choice&
c,
unsigned int a);
1915 void _trycommit(
const Choice&
c,
unsigned int a);
1942 virtual ~
Space(
void);
1985 virtual bool master(
const MetaInfo& mi);
2012 virtual bool slave(
const MetaInfo& mi);
2065 const Choice* choice(
void);
2103 bool share_info=
true,
2140 void commit(
const Choice&
c,
unsigned int a,
2174 void trycommit(
const Choice&
c,
unsigned int a,
2212 void print(
const Choice&
c,
unsigned int a, std::ostream& o)
const;
2338 bool failed(
void)
const;
2343 bool stable(
void)
const;
2367 T* alloc(
long unsigned int n);
2375 T* alloc(
long int n);
2383 T* alloc(
unsigned int n);
2402 void free(T*
b,
long unsigned int n);
2413 void free(T*
b,
long int n);
2424 void free(T*
b,
unsigned int n);
2435 void free(T*
b,
int n);
2448 T* realloc(T*
b,
long unsigned int n,
long unsigned int m);
2461 T* realloc(T*
b,
long int n,
long int m);
2474 T* realloc(T*
b,
unsigned int n,
unsigned int m);
2487 T* realloc(T*
b,
int n,
int m);
2496 T** realloc(T**
b,
long unsigned int n,
long unsigned int m);
2505 T** realloc(T**
b,
long int n,
long int m);
2514 T** realloc(T**
b,
unsigned int n,
unsigned int m);
2523 T** realloc(T**
b,
int n,
int m);
2525 void* ralloc(
size_t s);
2527 void rfree(
void*
p,
size_t s);
2529 void* rrealloc(
void*
b,
size_t n,
size_t m);
2531 template<
size_t>
void* fl_alloc(
void);
2560 template<
class T,
typename A1>
2561 T& construct(A1
const& a1);
2567 template<
class T,
typename A1,
typename A2>
2568 T& construct(A1
const& a1, A2
const& a2);
2574 template<
class T,
typename A1,
typename A2,
typename A3>
2575 T& construct(A1
const& a1, A2
const& a2, A3
const& a3);
2581 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
2582 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4);
2588 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
2589 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4, A5
const& a5);
2596 void afc_decay(
double d);
2598 double afc_decay(
void)
const;
2601 void afc_set(
double a);
2622 Propagators(
Space& home);
2624 bool operator ()(
void)
const;
2626 void operator ++(
void);
2635 class ScheduledPropagators {
2647 ScheduledPropagators(
Space& home);
2649 bool operator ()(
void)
const;
2651 void operator ++(
void);
2660 class IdlePropagators {
2668 IdlePropagators(
Space& home);
2670 bool operator ()(
void)
const;
2672 void operator ++(
void);
2689 Branchers(
Space& home);
2691 bool operator ()(
void)
const;
2693 void operator ++(
void);
2710 bool operator ()(
void)
const;
2712 void operator ++(
void);
2728 bool operator ()(
void)
const;
2730 void operator ++(
void);
2732 const Brancher& brancher(
void)
const;
2746 return mm.alloc(
sm,s);
2750 return mm.reuse(p,s);
2754 char*
b =
static_cast<char*
>(
_b);
2756 char*
p =
static_cast<char*
>(ralloc(m));
2769 return mm.template fl_alloc<s>(
sm);
2774 mm.template fl_dispose<s>(f,
l);
2784 T*
p =
static_cast<T*
>(ralloc(
sizeof(T)*n));
2785 for (
long unsigned int i=n;
i--; )
2786 (
void)
new (p+
i) T();
2793 return alloc<T>(
static_cast<long unsigned int>(
n));
2798 return alloc<T>(
static_cast<long unsigned int>(
n));
2804 return alloc<T>(
static_cast<long unsigned int>(
n));
2810 for (
long unsigned int i=n;
i--; )
2812 rfree(b,n*
sizeof(T));
2818 free<T>(
b,
static_cast<long unsigned int>(
n));
2823 free<T>(
b,
static_cast<long unsigned int>(
n));
2829 free<T>(
b,
static_cast<long unsigned int>(
n));
2836 T*
p =
static_cast<T*
>(ralloc(
sizeof(T)*m));
2837 for (
long unsigned int i=n;
i--; )
2838 (
void)
new (p+
i) T(b[
i]);
2839 for (
long unsigned int i=n; i<m; i++)
2840 (
void)
new (p+
i) T();
2851 assert((n >= 0) && (m >= 0));
2852 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2853 static_cast<long unsigned int>(m));
2858 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2859 static_cast<long unsigned int>(m));
2864 assert((n >= 0) && (m >= 0));
2865 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2866 static_cast<long unsigned int>(m));
2869 #define GECODE_KERNEL_REALLOC(T) \ 2872 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \ 2873 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \ 2877 Space::realloc<T>(T* b, long int n, long int m) { \ 2878 assert((n >= 0) && (m >= 0)); \ 2879 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2880 static_cast<long unsigned int>(m)); \ 2884 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \ 2885 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2886 static_cast<long unsigned int>(m)); \ 2890 Space::realloc<T>(T* b, int n, int m) { \ 2891 assert((n >= 0) && (m >= 0)); \ 2892 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2893 static_cast<long unsigned int>(m)); \ 2908 #undef GECODE_KERNEL_REALLOC 2913 return static_cast<T**
>(rrealloc(b,n*
sizeof(T),m*
sizeof(T*)));
2918 assert((n >= 0) && (m >= 0));
2919 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2920 static_cast<long unsigned int>(m));
2925 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2926 static_cast<long unsigned int>(m));
2931 assert((n >= 0) && (m >= 0));
2932 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2933 static_cast<long unsigned int>(m));
2937 #ifdef GECODE_HAS_VAR_DISPOSE 2940 Space::vars_d(
void)
const {
2941 return _vars_d[VIC::idx_d];
2946 _vars_d[VIC::idx_d] =
x;
2952 Actor::operator
delete(
void*) {}
2954 Actor::operator
delete(
void*,
Space&) {}
2956 Actor::operator
new(
size_t s,
Space& home) {
2957 return home.ralloc(s);
2969 return home.ralloc(s);
2974 Advisor::operator
delete(
void*) {}
2977 Advisor::operator
delete(
void*,
Space&) {}
2979 Advisor::operator
new(
size_t s,
Space& home) {
2980 return home.ralloc(s);
2984 NGL::operator
delete(
void*) {}
2988 NGL::operator
new(
size_t s,
Space& home) {
2989 return home.ralloc(s);
2998 : next(NULL), fwd(NULL), use_cnt(0) {}
3001 assert(use_cnt == 0);
3009 SharedHandle::subscribe(
void) {
3010 if (o != NULL) o->use_cnt++;
3013 SharedHandle::cancel(
void) {
3014 if ((o != NULL) && (--o->use_cnt == 0))
3021 cancel(); o=
n; subscribe();
3037 cancel(); o=sh.o; subscribe();
3047 }
else if (sh.o->fwd != NULL) {
3052 sh.o->next = home.pc.
c.shared;
3053 home.pc.
c.shared = sh.o;
3088 unsigned long int s0,
3089 unsigned long int f0,
3092 :
t(RESTART),
r(r0), s(s0), f(f0),
l(l0),
ng(ng0),
a(0) {}
3167 p->_next =
n; n->_prev =
p;
3172 _next =
this; _prev =
this;
3179 this->_next =
a; a->_prev =
this;
3180 a->_next =
n; n->_prev =
a;
3187 a->_next =
this; this->_prev =
a;
3188 p->_next =
a; a->_prev =
p;
3193 return _next ==
this;
3224 return static_cast<Actor*
>(&
t);
3232 return static_cast<const Actor*
>(&
t);
3236 Space::afc_enable(
void) {
3240 Space::afc_enabled(
void)
const {
3241 return (_wmp_afc & 1U) != 0U;
3244 Space::wmp(
unsigned int n) {
3245 _wmp_afc = (_wmp_afc & 1U) | (n << 1);
3248 Space::wmp(
void)
const {
3249 return _wmp_afc >> 1U;
3254 s.notice(a,p,duplicate);
3262 return const_cast<Space*
>(
this)->_clone(share_data,share_info);
3282 return sizeof(*this);
3293 : s(s0),
p(p0), pg(pg0), bg(bg0) {}
3317 return Home(*
this,&p);
3338 who =
reinterpret_cast<ptrdiff_t
>(&
p) | PROPAGATOR;
3342 who =
reinterpret_cast<ptrdiff_t
>(&
b) | BRANCHER;
3346 who = (g.
id() << 2) | POST;
3354 return static_cast<What>(who & 3);
3358 assert(what() == PROPAGATOR);
3364 assert(what() == BRANCHER);
3365 return *
reinterpret_cast<Brancher*
>(who & ~3);
3369 assert(what() == POST);
3437 static_cast<
Space&>(home).gpi.allocate(home.propagatorgroup().gid)) {
3439 assert((u.med == 0) && (u.size == 0));
3440 static_cast<Space&
>(home).pl.head(
this);
3445 : gpi_disabled(p.gpi_disabled) {
3447 assert((u.med == 0) && (u.size == 0));
3459 return const_cast<Space&
>(home).
gpi.afc(const_cast<Propagator&>(*this).gpi());
3492 assert(p.u.
med != 0);
3499 assert(p.u.
med != 0);
3522 return static_cast<const Brancher*
>(&
t);
3527 bid(static_cast<
Space&>(home).pc.
p.bid++),
3528 gid(home.branchergroup().gid) {
3529 if (static_cast<Space&>(home).pc.p.bid == 0U)
3532 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
3533 static_cast<Space&
>(home).b_status =
this;
3534 if (static_cast<Space&>(home).b_commit == &
static_cast<Space&
>(home).bl)
3535 static_cast<Space&
>(home).b_commit =
this;
3537 static_cast<Space&
>(home).bl.tail(
this);
3542 : bid(b.bid), gid(b.gid) {
3568 b_commit = Brancher::cast(b.next());
3570 b_status = Brancher::cast(b.next());
3583 Space::brancher(
unsigned int id) {
3600 while (b_commit != Brancher::cast(&bl))
3601 if (
id != b_commit->id())
3602 b_commit = Brancher::cast(b_commit->next());
3605 if (b_commit == Brancher::cast(&bl)) {
3607 b_commit = Brancher::cast(bl.next());
3608 while (b_commit != b_old)
3609 if (
id != b_commit->id())
3610 b_commit = Brancher::cast(b_commit->next());
3653 fwdcopy(home,share);
3686 : bid(b.id()), alt(a) {}
3694 Choice::id(
void)
const {
3741 return sizeof(*this);
3761 Advisor::disposed(
void)
const {
3762 return prev() == NULL;
3767 return static_cast<Advisor*
>(al);
3772 return static_cast<const Advisor*
>(al);
3777 assert(!disposed());
3784 assert(!disposed());
3788 if ((n != NULL) && n->disposed())
3794 return home.pc.
p.ei;
3837 while ((a != NULL) && static_cast<A*>(a)->disposed())
3849 while ((a != NULL) && static_cast<A*>(a)->disposed())
3854 if (c.advisors != NULL) {
3858 Propagator* p_t = Propagator::cast(p_f->prev());
3863 while (*a_f != NULL) {
3864 if (static_cast<A*>(*a_f)->disposed()) {
3865 *a_f = (*a_f)->next();
3868 A*
a =
new (home) A(home,share,*static_cast<A*>(*a_f));
3876 a_f = (*a_f)->next_ref();
3893 if (!static_cast<A*>(a)->disposed())
3894 static_cast<A*
>(
a)->dispose(home,*
this);
3909 while ((a != NULL) && static_cast<A*>(a)->disposed())
3924 }
while ((a != NULL) && static_cast<A*>(a)->disposed());
3930 return *
static_cast<A*
>(a);
3944 if (c > pc.p.active)
3973 return ((pc.p.active < &pc.p.queue[0]) ||
3986 assert((pc >= 0) && (pc < pc_max+2));
3987 return (pc == 0) ? b.base : b.base+
u.idx[pc-1];
3993 assert((pc > 0) && (pc < pc_max+2));
3994 return b.base+
u.idx[pc-1];
4000 assert((pc > 0) && (pc < pc_max+2));
4007 assert((pc > 0) && (pc < pc_max+2));
4014 b.base = NULL; entries = 0;
4015 for (
PropCond pc=1; pc<pc_max+2; pc++)
4023 b.base = NULL; entries = 0;
4024 for (
PropCond pc=1; pc<pc_max+2; pc++)
4045 d += Propagator::cast(*a)->afc(home); a++;
4053 d += Advisor::cast(*a)->propagator().afc(home); a++;
4068 return free_and_bits;
4074 return free_and_bits;
4077 #ifdef GECODE_HAS_VAR_DISPOSE 4081 return static_cast<VarImp<VIC>*
>(home.vars_d<VIC>());
4087 home.vars_d<VIC>(
x);
4115 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4116 if (x.b.
base == NULL) {
4118 reg = &home.pc.
c.vars_noidx;
4121 reg = &home.pc.
c.vars_u[idx_c];
4125 entries = x.entries;
4126 for (
PropCond pc=1; pc<pc_max+2; pc++)
4127 idx(pc) = x.
idx(pc);
4138 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4150 return VIC::me_combine(me1,me2);
4157 if (VIC::med_update(p.u.
med,me) || force)
4167 schedule(home,*Propagator::cast(*p),me);
4173 assert(pc <= pc_max);
4175 home.pc.
p.n_sub += 1;
4176 if ((free_and_bits >> free_bits) == 0)
4178 free_and_bits -= 1 << free_bits;
4181 b.base[entries] = *actorNonZero(pc_max+1);
4183 for (
PropCond j = pc_max; j > pc; j--) {
4184 *actorNonZero(j+1) = *actorNonZero(j);
4187 *actorNonZero(pc+1) = *actor(pc);
4193 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4207 home.pc.
p.n_sub += 1;
4208 if ((free_and_bits >> free_bits) == 0)
4210 free_and_bits -= 1 << free_bits;
4213 b.base[entries++] = *actorNonZero(pc_max+1);
4214 *actorNonZero(pc_max+1) = a;
4220 if (b.base == NULL) {
4221 assert((free_and_bits >> free_bits) == 0);
4223 free_and_bits += 4 << free_bits;
4225 for (
int i=0;
i<pc_max+1;
i++)
4229 unsigned int n = degree();
4235 ((s <= b.base) && (b.base < s+home.pc.
p.n_sub)) ?
4236 (n+4) : ((n+1)*3>>1);
4238 free_and_bits += (m-
n) << free_bits;
4240 Heap::copy<ActorLink*>(prop, b.base,
n);
4282 assert(pc <= pc_max);
4287 while (f < actorNonZero(pc+1))
4295 while (*f != a) f++;
4298 *f = *(actorNonZero(pc+1)-1);
4299 for (
PropCond j = pc+1; j< pc_max+1; j++) {
4300 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4303 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4306 free_and_bits += 1 << free_bits;
4307 home.pc.
p.n_sub -= 1;
4316 while (f < b.base+entries)
4324 while (*f != a) f++;
4327 *f = b.base[--entries];
4328 free_and_bits += 1 << free_bits;
4329 home.pc.
p.n_sub -= 1;
4349 unsigned int n_sub = degree();
4350 home.pc.
p.n_sub -= n_sub;
4351 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
4367 ActorLink** la = actorNonZero(pc_max+1);
4376 Advisor* a = Advisor::cast(*la);
4377 assert(!a->disposed());
4379 switch (p.advise(home,*a,d)) {
4383 if (home.afc_enabled())
4384 home.gpi.
fail(p.gpi());
4387 schedule(home,p,me);
4390 schedule(home,p,me,
true);
4396 }
while (++la < le);
4407 x->u.
idx[0] =
u.idx[0];
4408 if (pc_max > 0 &&
sizeof(
ActorLink**) >
sizeof(
unsigned int))
4409 x->u.
idx[1] =
u.idx[1];
4412 unsigned int n = x->
degree();
4419 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
4420 t[2]=f[2]->
prev(); t[3]=f[3]->
prev();
4425 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
4448 template<
class VarImp>
4450 #ifdef GECODE_HAS_VAR_DISPOSE 4451 Space::vd[VarImp::idx_d] =
this;
4455 template<
class VarImp>
4460 x->dispose(home); x =
static_cast<VarImp*
>(x->next_d());
4461 }
while (x != NULL);
4536 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4538 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4540 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4542 return (m == LO) ? lo : hi;
4551 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4556 return crazy(m,static_cast<unsigned int>(n));
4560 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4565 return cubic(m,static_cast<unsigned int>(n));
4569 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4574 return quadratic(m,static_cast<unsigned int>(n));
4578 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4583 return linear(m,static_cast<unsigned int>(n));
4587 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4591 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4595 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4603 Space::Propagators::Propagators(
Space& home0)
4604 : home(home0), q(home.pc.
p.active) {
4605 while (q >= &home.pc.
p.queue[0]) {
4606 if (q->next() != q) {
4607 c = q->next(); e = q; q--;
4613 if (!home.pl.
empty()) {
4614 c = Propagator::cast(home.pl.
next());
4615 e = Propagator::cast(&home.pl);
4621 Space::Propagators::operator ()(
void)
const {
4625 Space::Propagators::operator ++(
void) {
4631 while (q >= &home.pc.
p.queue[0]) {
4632 if (q->next() != q) {
4633 c = q->next(); e = q; q--;
4639 if (!home.pl.
empty()) {
4640 c = Propagator::cast(home.pl.
next());
4641 e = Propagator::cast(&home.pl);
4650 return *Propagator::cast(
c);
4655 Space::ScheduledPropagators::ScheduledPropagators(
Space& home0)
4656 : home(home0), q(home.pc.
p.active) {
4657 while (q >= &home.pc.
p.queue[0]) {
4658 if (q->next() != q) {
4659 c = q->next(); e = q; q--;
4667 Space::ScheduledPropagators::operator ()(
void)
const {
4671 Space::ScheduledPropagators::operator ++(
void) {
4677 while (q >= &home.pc.
p.queue[0]) {
4678 if (q->next() != q) {
4679 c = q->next(); e = q; q--;
4690 return *Propagator::cast(
c);
4695 Space::IdlePropagators::IdlePropagators(
Space& home) {
4696 c = Propagator::cast(home.pl.
next());
4697 e = Propagator::cast(&home.pl);
4700 Space::IdlePropagators::operator ()(
void)
const {
4704 Space::IdlePropagators::operator ++(
void) {
4709 return *Propagator::cast(
c);
4714 Space::Branchers::Branchers(
Space& home)
4715 :
c(Brancher::cast(home.bl.
next())), e(&home.bl) {}
4717 Space::Branchers::operator ()(
void)
const {
4721 Space::Branchers::operator ++(
void) {
4725 Space::Branchers::brancher(
void)
const {
4726 return *Brancher::cast(
c);
4783 return id() == g.
id();
4787 return id() != g.
id();
4821 return id() == g.
id();
4825 return id() != g.
id();
4843 while (ps() && !g.
in(ps.propagator().group()))
4854 while (ps() && !g.
in(ps.propagator().group()));
4858 return ps.propagator();
4864 while (bs() && !g.
in(bs.brancher().group()))
4875 while (bs() && !g.
in(bs.brancher().group()));
4879 return bs.brancher();
4892 template<
class T,
typename A1>
4895 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
4899 template<
class T,
typename A1,
typename A2>
4902 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
4906 template<
class T,
typename A1,
typename A2,
typename A3>
4909 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
4910 new (&
t) T(a1,a2,a3);
4913 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
4916 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
4917 new (&
t) T(a1,a2,a3,a4);
4920 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
4923 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
4924 new (&
t) T(a1,a2,a3,a4,a5);
bool empty(void) const
Test whether actor link is empty (points to itself)
virtual Object * copy(void) const =0
Return fresh copy for update.
Double-linked list for actors.
unsigned int alternatives(void) const
Return number of alternatives.
void reset(void)
Reset information.
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
bool marked(void *p)
Check whether p is marked.
Iterator over subscribed propagators.
void init(void)
Initialize links (self-linked)
SharedHandle(void)
Create shared handle with no object pointing to.
Base-class for variable implementations.
Propagator * fwd(void) const
Return forwarding pointer during copying.
Space must be branched (at least one brancher left)
double afc(const Space &home) const
Return the accumlated failure count.
Class to iterate over branchers in a group.
ActorLink ** next_ref(void)
Routines for double-linked list.
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
bool operator!=(PropagatorGroup g) const
Test whether this group is different from group g.
unsigned int bid
Id of next brancher to be created.
PropagatorGroup propagatorgroup(void) const
Return propagator group.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
void unlink(void)
Remove from predecessor and successor.
VarImp * forward(void) const
Use forward pointer if variable already copied.
static BrancherGroup all
Group of all branchers.
LocalObject(Home home)
Constructor for creation.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Group & operator=(const Group &g)
Assignment operator.
bool in(Group a) const
Check whether actor group a is included in this group.
VarImp(void)
Creation of static instances.
ExecStatus ES_SUBSUMED(Propagator &p)
ExecInfo ei
Execution information.
VarImpDisposer(void)
Constructor (registers disposer with kernel)
VarImp< VIC > * next
During cloning, points to the next copied variable.
LocalObject * object(void) const
Access to the local object.
ActorLink * next(void) const
Routines for double-linked list.
Actor must always be disposed.
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
PropagatorGroup(void)
Constructor.
NGL(void)
Constructor for creation.
void cancel(Space &home, Propagator &p, IntSet &y)
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
~PostInfo(void)
Reset information.
void * subscriptions(void) const
Get the memory area for subscriptions.
static PropagatorGroup all
Group of all propagators.
static BrancherGroup def
Group of branchers not in any user-defined group.
Propagators(Space &home, PropagatorGroup g)
Initialize.
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from the space heap...
ActorLink * prev(void) const
Routines for double-linked list.
double afc(const Space &home) const
Return accumulated failure count (plus degree)
Class to iterate over propagators in a group.
Statistics for execution of commit
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Local (space-shared) object.
Status
The status of a no-good literal.
int ModEvent
Type for modification events.
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
static ModEvent modevent(const Delta &d)
Return modification event.
Base-class for propagators.
Internal: propagator is subsumed, do not use.
virtual ~Choice(void)
Destructor.
T & construct(void)
Construction routines.
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
bool wmp
Whether a weakly monotonic propagator might have been executed.
static PropCost record(void)
For recording information (no propagation allowed)
ActorLink ** base
Subscribed actors.
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Class to iterate over advisors of a council.
static Group def
Group of actors not in any user-defined group.
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
friend class SharedHandle
void * mark(void *p)
Return marked pointer for p.
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
PropagatorGroup pg
A propagator group.
Base-class for variable implementations.
LocalObject * local
Linked list of local objects.
unsigned long int propagate
Number of propagator executions.
Propagation has computed fixpoint.
unsigned int id(void) const
Return a unique id for the group.
void operator++(void)
Move iterator to next brancher.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
const Propagator & propagator(void) const
Return currently executing propagator.
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
void * rrealloc(void *b, size_t n, size_t m)
Reallocate memory block starting at b from size n to size s.
PostInfo(Home home)
Set information.
Base-class for both propagators and branchers.
Statistics for execution of status
What what(void) const
Return what is currently executing.
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
unsigned int id(void) const
Return propagator id.
A mutex for mutual exclausion among several threads.
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
static const unsigned int GROUPID_DEF
Pre-defined default group id.
void head(ActorLink *al)
Insert al directly after this.
Gecode::FloatVal c(-8, 8)
Configuration class for variable implementations without index structure.
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
bool leaf(void) const
Test whether literal is a leaf.
Handles for local (space-shared) objects.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Class for AFC (accumulated failure count) management.
int n
Number of negative literals for node type.
BrancherGroup group(void) const
Return group brancher belongs to.
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Global propagator information.
void reset(void)
Reset information.
void reset(void)
Reset information.
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
unsigned int pid
Propagator identifier.
double afc_decay(void) const
Return AFC decay factor.
struct Gecode::Space::@55::@56 p
Data only available during propagation or branching.
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
bool copied(void) const
Is variable already copied.
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
union Gecode::@554::NNF::@60 u
Union depending on nodetype t.
Execution has resulted in failure.
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
StatusStatistics(void)
Initialize.
FloatVal operator+(const FloatVal &x)
SharedHandle::Object * object(void) const
Access to the shared object.
void other(void)
Record that nothing is known at this point.
Statistics for execution of clone
Class to set group information when a post function is executed.
bool operator!=(const FloatVal &x, const FloatVal &y)
int PropCond
Type for propagation conditions.
void subscribe(Space &home, Propagator &p, IntSet &y)
virtual ~NoGoods(void)
Destructor.
SharedHandle & operator=(const SharedHandle &sh)
Assignment operator maintaining reference count.
bool failed(void) const
Check whether space is failed.
ModEventDelta med
A set of modification events (used during propagation)
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
unsigned int n_sub
Number of subscriptions.
void fail(void)
Fail space.
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
const Brancher & brancher(void) const
Return currently executing brancher.
bool failed(void) const
Check whether corresponding space is failed.
unsigned int size(I &i)
Size of all ranges of range iterator i.
const Propagator & propagator(void) const
Return propagator.
bool stable(void) const
Return if space is stable (at fixpoint or failed)
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
CloneStatistics(void)
Initialize.
LocalHandle(void)
Create local handle pointing to NULL object.
Home(Space &s, Propagator *p=NULL, PropagatorGroup pg=PropagatorGroup::def, BrancherGroup bg=BrancherGroup::def)
Initialize the home with space s and propagator p and group g.
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
PropagatorGroup group(void) const
Return group propagator belongs to.
size_t size
The size of the propagator (used during subsumption)
static Support::Mutex m
Mutex for protection.
Group baseclass for controlling actors.
bool operator()(void) const
Test whether there advisors left.
bool disabled(void) const
Whether propagator is currently disabled.
Council(void)
Default constructor.
LocalObject * fwd(Space &home, bool share)
Return forwarding pointer.
#define GECODE_KERNEL_EXPORT
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
static unsigned int next
Next group id.
Home & operator=(const Home &h)
Assignment operator.
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Branchers(Space &home, BrancherGroup g)
Initialize.
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
IntPropLevel sm(IntPropLevel ipl)
Extract speed or memory from propagation level.
Exception: too many branchers
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Mod
Propagation cost modifier.
bool operator()(void) const
Test whether there are branchers left.
NGL * next(void) const
Return pointer to next literal.
~SharedHandle(void)
Destructor that maintains reference count.
bool operator()(void) const
Test whether there are propagators left.
BrancherGroup branchergroup(void) const
Return brancher group.
ModEventDelta modeventdelta(void) const
Return the modification event delta.
void update(Space &home, bool share, LocalHandle &lh)
Updating during cloning.
ptrdiff_t who
Encoding a tagged pointer or a tagged group id.
Advisor forces rescheduling of propagator.
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
unsigned int id(void) const
Return brancher id.
Home operator()(Space &home)
To augment a space argument.
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
const Brancher & brancher(void) const
Return propagator.
What
What is currently executing.
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
static PropagatorGroup def
Group of propagators not in any user-defined group.
void * ralloc(size_t s)
Allocate memory on space heap.
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
BrancherGroup(void)
Constructor.
ActualCost ac
Actual cost.
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
const ExecInfo & operator()(const Space &home) const
Provide access to execution information.
Node * x
Pointer to corresponding Boolean expression node.
Generic domain change information to be supplied to advisors.
Brancher(Home home)
Constructor for creation.
static const int idx_c
Index for cloning.
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
virtual ~Object(void)
Delete shared object.
Propagator & propagator(void) const
Return the advisor's propagator.
Choice for performing commit
unsigned int gid
Group identifier.
struct Gecode::Space::@55::@57 c
Data available only during copying.
No-goods recorded from restarts.
virtual size_t dispose(Space &home)
Delete actor and return its size.
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
void operator++(void)
Move iterator to next advisor.
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
#define GECODE_KERNEL_REALLOC(T)
bool operator!=(BrancherGroup g) const
Test whether this group is different from group g.
static ActorLink * cast(T *a)
Static cast for a non-null pointer (to give a hint to optimizer)
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
bool assigned(View x, int v)
Whether x is assigned to value v.
void enable(void)
Enable propagator.
void fail(Info &c)
Increment failure count.
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
SharedHandle::Object * shared
Linked list of shared objects.
Space & s
The space where the propagator is to be posted.
static NoGoods eng
Empty no-goods.
Home operator()(Space &home)
To augment a space argument.
static void reschedule(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me)
Schedule propagator p.
Base-class for freelist-managed objects.
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
void operator++(void)
Move iterator to next propagator.
Internal: propagator has computed partial fixpoint, do not use.
Variable implementation disposer
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
VarImp< VIC > * fwd
Forwarding pointer.
virtual size_t dispose(Space &home)
Dispose.
Propagation has not computed fixpoint.
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
Propagator * p
A propagator (possibly) that is currently being rewritten.
void fail(void)
Mark space as failed.
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
bool in(void) const
Check whether this is a real group (and not just default)
bool operator==(const FloatVal &x, const FloatVal &y)
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Propagator(Home home)
Constructor for posting.
Gecode toplevel namespace
static Group all
Group of all actors.
BrancherGroup bg
A brancher group.
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
ActorLink * active
Cost level with next propagator to be executed.
Class for storing timed-decay value.
#define GECODE_VTABLE_EXPORT
VarImpBase * vars_noidx
Keep variables during copying without index structure.
ActorProperty
Actor properties.
VarImp * next(void) const
Return next copied variable.
void reschedule(Space &home, Propagator &p, IntSet &y)
unsigned long int ng(void) const
Return number of no-goods posted.
ActualCost
The actual cost values that are used.
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
unsigned long int n
Number of no-goods.
void * fl_alloc(void)
Allocate from freelist-managed memory.
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
int ModEventDelta
Modification event deltas.
static const int idx_d
Index for dispose.
Home class for posting propagators
unsigned int bits(void) const
Provide access to free bits.
Base class for heap allocated objects.
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Shared object for several memory areas.
#define GECODE_NEVER
Assert that this command is never executed.
A & advisor(void) const
Return advisor.
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl)
Post propagators for scheduling tasks on unary resources.
bool advise(Space &home, ModEvent me, Delta &d)
Run advisors when variable implementation has been modified with modification event me and domain cha...
CommitStatistics(void)
Initialize.
void disable(void)
Disable propagator.
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Base class for Variable type disposer.
GPI::Info & gpi(void)
Provide access to global propagator information.
ExecStatus ES_NOFIX_DISPOSE_FORCE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be forcefully rescheduled
const bool clone
Whether engines create a clone when being initialized.
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
unsigned int gid
The group id.
void tail(ActorLink *al)
Insert al directly before this.
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Space is solved (no brancher left)
No-good literal recorded during search.
~LocalHandle(void)
Destructor.