193 template<
class VarImp>
245 static const int idx_c = VIC::idx_c;
247 static const int idx_d = VIC::idx_d;
249 static const int free_bits = VIC::free_bits;
251 unsigned int entries;
253 unsigned int free_and_bits;
256 #ifdef GECODE_HAS_CBS 257 const unsigned var_id;
272 unsigned int idx[pc_max+1];
284 unsigned int idx(
PropCond pc)
const;
306 void resize(
Space& home);
324 void _fail(
Space& home);
328 #ifdef GECODE_HAS_VAR_DISPOSE 341 #ifdef GECODE_HAS_CBS 342 unsigned int id(
void)
const;
382 unsigned int degree(
void)
const;
389 double afc(
void)
const;
397 bool copied(
void)
const;
399 VarImp* forward(
void)
const;
440 unsigned int bits(
void)
const;
443 unsigned int& bits(
void);
453 static void*
operator new(size_t,
Space&);
456 static void operator delete(
void*,
Space&);
458 static void operator delete(
void*);
615 bool empty(
void)
const;
617 template<
class T>
static ActorLink* cast(T*
a);
619 template<
class T>
static const ActorLink* cast(
const T*
a);
651 virtual size_t dispose(
Space& home);
653 static void*
operator new(
size_t s,
Space& home);
655 static void operator delete(
void*
p,
Space& home);
661 static void*
operator new(
size_t s);
663 static void operator delete(
void*
p);
681 static const unsigned int GROUPID_ALL = 0U;
683 static const unsigned int GROUPID_DEF = 1U;
685 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
695 Group(
unsigned int gid0);
707 unsigned int id(
void)
const;
771 void kill(
Space& home);
774 void disable(
Space& home);
782 void enable(
Space& home,
bool s=
true);
840 void kill(
Space& home);
874 operator Space&(void);
893 bool failed(
void)
const;
933 What what(
void)
const;
937 const Brancher& brancher(
void)
const;
983 unsigned int id(
void)
const;
989 Status status(
void)
const;
1008 unsigned int id(
void)
const;
1012 const Brancher& brancher(
void)
const;
1014 const Choice& choice(
void)
const;
1016 unsigned int alternative(
void)
const;
1047 void disable(
Space& home);
1049 void enable(
Space& home);
1149 double afc(
void)
const;
1152 #ifdef GECODE_HAS_CBS 1161 typedef std::function<void(
unsigned int prop_id,
unsigned int var_id,
1163 int val,
double dens)> SendMarginal;
1164 virtual void solndistrib(
Space& home, SendMarginal send)
const;
1172 typedef std::function<bool(unsigned int var_id)> InDecision;
1174 virtual void domainsizesum(InDecision in,
unsigned int&
size,
1175 unsigned int& size_b)
const;
1180 unsigned int id(
void)
const;
1187 bool disabled(
void)
const;
1212 bool empty(
void)
const;
1216 void dispose(
Space& home);
1233 bool operator ()(
void)
const;
1235 void operator ++(
void);
1237 A& advisor(
void)
const;
1258 bool disposed(
void)
const;
1281 static void*
operator new(
size_t s,
Space& home);
1283 static void operator delete(
void*
p,
Space& home);
1287 static void operator delete(
void*
p);
1290 static void*
operator new(
size_t s);
1327 virtual NGL* copy(
Space& home) = 0;
1330 virtual bool notice(
void)
const;
1332 virtual size_t dispose(
Space& home);
1335 bool leaf(
void)
const;
1338 NGL* next(
void)
const;
1348 static void*
operator new(
size_t s,
Space& home);
1351 static void operator delete(
void* s,
Space& home);
1353 static void operator delete(
void*
p);
1359 static void*
operator new(
size_t s);
1378 unsigned int id(
void)
const;
1384 unsigned int alternatives(
void)
const;
1389 virtual void archive(
Archive& e)
const;
1430 virtual bool status(
const Space& home)
const = 0;
1448 unsigned int a) = 0;
1473 std::ostream& o)
const;
1477 unsigned int id(
void)
const;
1550 unsigned long int n;
1558 unsigned long int ng(
void)
const;
1560 void ng(
unsigned long int n);
1586 const unsigned long int r;
1589 const unsigned long int s;
1591 const unsigned long int f;
1599 const unsigned int a;
1607 unsigned long int s,
1608 unsigned long int f,
1614 Type type(
void)
const;
1618 unsigned long int restart(
void)
const;
1621 unsigned long int solution(
void)
const;
1623 unsigned long int fail(
void)
const;
1625 const Space* last(
void)
const;
1627 const NoGoods& nogoods(
void)
const;
1631 unsigned int asset(
void)
const;
1724 #ifdef GECODE_HAS_CBS 1725 unsigned int var_id_counter;
1751 Brancher* brancher(
unsigned int id);
1760 void kill_brancher(
unsigned int id);
1763 static const unsigned reserved_bid = 0U;
1766 static const unsigned int sc_bits = 2;
1768 static const unsigned int sc_fast = 0;
1770 static const unsigned int sc_disabled = 1;
1772 static const unsigned int sc_trace = 2;
1820 #ifdef GECODE_HAS_VAR_DISPOSE 1826 template<
class VIC>
VarImpBase* vars_d(
void)
const;
1896 void _commit(
const Choice&
c,
unsigned int a);
1929 void _trycommit(
const Choice&
c,
unsigned int a);
1942 void ap_notice_dispose(
Actor*
a,
bool d);
1950 void ap_ignore_dispose(
Actor*
a,
bool d);
1974 virtual ~
Space(
void);
1981 virtual Space* copy(
void) = 0;
2017 virtual bool master(
const MetaInfo& mi);
2044 virtual bool slave(
const MetaInfo& mi);
2097 const Choice* choice(
void);
2162 void commit(
const Choice&
c,
unsigned int a,
2196 void trycommit(
const Choice&
c,
unsigned int a,
2234 void print(
const Choice&
c,
unsigned int a, std::ostream& o)
const;
2360 bool failed(
void)
const;
2365 bool stable(
void)
const;
2389 T* alloc(
long unsigned int n);
2397 T* alloc(
long int n);
2405 T* alloc(
unsigned int n);
2424 void free(T*
b,
long unsigned int n);
2435 void free(T*
b,
long int n);
2446 void free(T*
b,
unsigned int n);
2457 void free(T*
b,
int n);
2470 T* realloc(T*
b,
long unsigned int n,
long unsigned int m);
2483 T* realloc(T*
b,
long int n,
long int m);
2496 T* realloc(T*
b,
unsigned int n,
unsigned int m);
2509 T* realloc(T*
b,
int n,
int m);
2518 T** realloc(T**
b,
long unsigned int n,
long unsigned int m);
2527 T** realloc(T**
b,
long int n,
long int m);
2536 T** realloc(T**
b,
unsigned int n,
unsigned int m);
2545 T** realloc(T**
b,
int n,
int m);
2547 void* ralloc(
size_t s);
2549 void rfree(
void*
p,
size_t s);
2551 void* rrealloc(
void*
b,
size_t n,
size_t m);
2553 template<
size_t>
void* fl_alloc(
void);
2573 template<
class T,
typename A1>
2574 T& construct(A1
const& a1);
2580 template<
class T,
typename A1,
typename A2>
2581 T& construct(A1
const& a1, A2
const& a2);
2587 template<
class T,
typename A1,
typename A2,
typename A3>
2588 T& construct(A1
const& a1, A2
const& a2, A3
const& a3);
2594 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
2595 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4);
2601 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
2602 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4, A5
const& a5);
2607 void afc_decay(
double d);
2610 double afc_decay(
void)
const;
2635 bool operator ()(
void)
const;
2637 void operator ++(
void);
2660 bool operator ()(
void)
const;
2662 void operator ++(
void);
2681 bool operator ()(
void)
const;
2683 void operator ++(
void);
2702 bool operator ()(
void)
const;
2704 void operator ++(
void);
2721 bool operator ()(
void)
const;
2723 void operator ++(
void);
2739 bool operator ()(
void)
const;
2741 void operator ++(
void);
2743 const Brancher& brancher(
void)
const;
2757 return mm.alloc(ssd.data().sm,s);
2761 return mm.reuse(p,s);
2765 char*
b =
static_cast<char*
>(
_b);
2767 char*
p =
static_cast<char*
>(ralloc(m));
2780 return mm.template fl_alloc<s>(ssd.data().sm);
2785 mm.template fl_dispose<s>(
f,
l);
2795 T*
p =
static_cast<T*
>(ralloc(
sizeof(T)*n));
2796 for (
long unsigned int i=0;
i<
n;
i++)
2797 (
void)
new (p+
i) T();
2804 return alloc<T>(
static_cast<long unsigned int>(
n));
2809 return alloc<T>(
static_cast<long unsigned int>(
n));
2815 return alloc<T>(
static_cast<long unsigned int>(
n));
2821 for (
long unsigned int i=0;
i<
n;
i++)
2823 rfree(b,n*
sizeof(T));
2829 free<T>(
b,
static_cast<long unsigned int>(
n));
2834 free<T>(
b,
static_cast<long unsigned int>(
n));
2840 free<T>(
b,
static_cast<long unsigned int>(
n));
2847 T*
p =
static_cast<T*
>(ralloc(
sizeof(T)*m));
2848 for (
long unsigned int i=0;
i<
n;
i++)
2849 (
void)
new (p+
i) T(b[
i]);
2850 for (
long unsigned int i=n; i<m; i++)
2851 (
void)
new (p+
i) T();
2862 assert((n >= 0) && (m >= 0));
2863 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2864 static_cast<long unsigned int>(m));
2869 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2870 static_cast<long unsigned int>(m));
2875 assert((n >= 0) && (m >= 0));
2876 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2877 static_cast<long unsigned int>(m));
2880 #define GECODE_KERNEL_REALLOC(T) \ 2883 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \ 2884 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \ 2888 Space::realloc<T>(T* b, long int n, long int m) { \ 2889 assert((n >= 0) && (m >= 0)); \ 2890 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2891 static_cast<long unsigned int>(m)); \ 2895 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \ 2896 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2897 static_cast<long unsigned int>(m)); \ 2901 Space::realloc<T>(T* b, int n, int m) { \ 2902 assert((n >= 0) && (m >= 0)); \ 2903 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2904 static_cast<long unsigned int>(m)); \ 2919 #undef GECODE_KERNEL_REALLOC 2924 return static_cast<T**
>(rrealloc(b,n*
sizeof(T),m*
sizeof(T*)));
2929 assert((n >= 0) && (m >= 0));
2930 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2931 static_cast<long unsigned int>(m));
2936 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2937 static_cast<long unsigned int>(m));
2942 assert((n >= 0) && (m >= 0));
2943 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2944 static_cast<long unsigned int>(m));
2948 #ifdef GECODE_HAS_VAR_DISPOSE 2951 Space::vars_d(
void)
const {
2952 return _vars_d[VIC::idx_d];
2957 _vars_d[VIC::idx_d] =
x;
2963 Actor::operator
delete(
void*) {}
2965 Actor::operator
delete(
void*,
Space&) {}
2967 Actor::operator
new(
size_t s,
Space& home) {
2968 return home.ralloc(s);
2980 return home.ralloc(s);
2985 Advisor::operator
delete(
void*) {}
2988 Advisor::operator
delete(
void*,
Space&) {}
2990 Advisor::operator
new(
size_t s,
Space& home) {
2991 return home.ralloc(s);
2995 NGL::operator
delete(
void*) {}
2999 NGL::operator
new(
size_t s,
Space& home) {
3000 return home.ralloc(s);
3028 unsigned long int s0,
3029 unsigned long int f0,
3032 :
t(RESTART),
r(r0), s(s0),
f(f0),
l(l0),
ng(ng0),
a(0) {}
3107 p->_next =
n; n->_prev =
p;
3112 _next =
this; _prev =
this;
3119 this->_next =
a; a->_prev =
this;
3120 a->_next =
n; n->_prev =
a;
3127 a->_next =
this; this->_prev =
a;
3128 p->_next =
a; a->_prev =
p;
3133 return _next ==
this;
3164 return static_cast<Actor*
>(&
t);
3172 return static_cast<const Actor*
>(&
t);
3177 s.notice(a,p,duplicate);
3185 return const_cast<Space*
>(
this)->_clone();
3200 return ssd.data().gpi.decay();
3205 ssd.data().gpi.decay(d);
3210 return sizeof(*this);
3221 : s(s0),
p(p0), pg(pg0), bg(bg0) {}
3245 return Home(*
this,&p);
3274 who =
reinterpret_cast<ptrdiff_t
>(&
p) | PROPAGATOR;
3278 who =
reinterpret_cast<ptrdiff_t
>(&
b) | BRANCHER;
3282 who = (g.
id() << 2) | POST;
3290 return static_cast<What>(who & 3);
3294 assert(what() == PROPAGATOR);
3300 assert(what() == BRANCHER);
3301 return *
reinterpret_cast<Brancher*
>(who & ~3);
3305 assert(what() == POST);
3328 :
i(i0), g(g0),
p(p0), s(s0) {}
3354 :
b(b0),
c(c0),
a(a0) {}
3408 Propagator::disable(
Space& home) {
3409 home.pc.
p.bid_sc |= Space::sc_disabled;
3414 Propagator::enable(
Space& home) {
3430 static_cast<
Space&>(home).ssd.data().gpi.allocate
3431 (home.propagatorgroup().gid)) {
3433 assert((u.med == 0) && (u.size == 0));
3434 static_cast<Space&
>(home).pl.head(
this);
3439 : gpi_disabled(p.gpi_disabled) {
3441 assert((u.med == 0) && (u.size == 0));
3456 #ifdef GECODE_HAS_CBS 3458 Propagator::solndistrib(
Space&, SendMarginal)
const {}
3461 Propagator::domainsizesum(InDecision,
unsigned int&
size,
3462 unsigned int& size_b)
const {
3498 assert(p.u.
med != 0);
3505 assert(p.u.
med != 0);
3528 return static_cast<const Brancher*
>(&
t);
3533 gid(_home.branchergroup().gid) {
3535 bid = home.pc.
p.bid_sc >> Space::sc_bits;
3536 home.pc.
p.bid_sc += (1 << Space::sc_bits);
3537 if ((home.pc.
p.bid_sc >> Space::sc_bits) == 0U)
3540 if (home.b_status == &static_cast<Space&>(home).bl) {
3541 home.b_status =
this;
3542 if (home.b_commit == &static_cast<Space&>(home).bl)
3543 home.b_commit =
this;
3550 : bid(b.bid), gid(b.gid) {
3576 b_commit = Brancher::cast(b.next());
3578 b_status = Brancher::cast(b.next());
3591 Space::brancher(
unsigned int id) {
3608 while (b_commit != Brancher::cast(&bl))
3609 if (
id != b_commit->id())
3610 b_commit = Brancher::cast(b_commit->next());
3613 if (b_commit == Brancher::cast(&bl)) {
3615 b_commit = Brancher::cast(bl.next());
3616 while (b_commit != b_old)
3617 if (
id != b_commit->id())
3618 b_commit = Brancher::cast(b_commit->next());
3694 : bid(b.id()), alt(a) {}
3702 Choice::id(
void)
const {
3749 return sizeof(*this);
3769 Advisor::disposed(
void)
const {
3770 return prev() == NULL;
3775 return static_cast<Advisor*
>(al);
3780 return static_cast<const Advisor*
>(al);
3785 assert(!disposed());
3792 assert(!disposed());
3796 if ((n != NULL) && n->disposed())
3802 return home.pc.
p.vti;
3845 while ((a != NULL) && static_cast<A*>(a)->disposed())
3857 while ((a != NULL) && static_cast<A*>(a)->disposed())
3862 if (c.advisors != NULL) {
3866 Propagator* p_t = Propagator::cast(p_f->prev());
3871 while (*a_f != NULL) {
3872 if (static_cast<A*>(*a_f)->disposed()) {
3873 *a_f = (*a_f)->next();
3876 A*
a =
new (home) A(home,*static_cast<A*>(*a_f));
3884 a_f = (*a_f)->next_ref();
3901 if (!static_cast<A*>(a)->disposed())
3902 static_cast<A*
>(
a)->dispose(home,*
this);
3917 while ((a != NULL) && static_cast<A*>(a)->disposed())
3932 }
while ((a != NULL) && static_cast<A*>(a)->disposed());
3938 return *
static_cast<A*
>(a);
3952 if (c > pc.p.active)
3981 return ((pc.p.active < &pc.p.queue[0]) ||
3988 ap_notice_dispose(&a,d);
3991 pc.p.bid_sc |= sc_trace;
3994 pc.p.bid_sc |= sc_trace;
4005 ap_ignore_dispose(&a,d);
4021 assert((pc >= 0) && (pc < pc_max+2));
4022 return (pc == 0) ? b.base : b.base+
u.idx[pc-1];
4028 assert((pc > 0) && (pc < pc_max+2));
4029 return b.base+
u.idx[pc-1];
4035 assert((pc > 0) && (pc < pc_max+2));
4042 assert((pc > 0) && (pc < pc_max+2));
4049 #ifdef GECODE_HAS_CBS 4050 : var_id(++home.var_id_counter)
4053 #ifndef GECODE_HAS_CBS 4056 b.base = NULL; entries = 0;
4057 for (
PropCond pc=1; pc<pc_max+2; pc++)
4065 #ifdef GECODE_HAS_CBS 4069 b.base = NULL; entries = 0;
4070 for (
PropCond pc=1; pc<pc_max+2; pc++)
4075 #ifdef GECODE_HAS_CBS 4099 d += Propagator::cast(*a)->afc(); a++;
4108 ->propagator().afc();
4124 return free_and_bits;
4130 return free_and_bits;
4133 #ifdef GECODE_HAS_VAR_DISPOSE 4137 return static_cast<VarImp<VIC>*
>(home.vars_d<VIC>());
4143 home.vars_d<VIC>(
x);
4170 #ifdef GECODE_HAS_CBS 4175 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4176 if (x.b.
base == NULL) {
4178 reg = &home.pc.
c.vars_noidx;
4181 reg = &home.pc.
c.vars_u[idx_c];
4185 entries = x.entries;
4186 for (
PropCond pc=1; pc<pc_max+2; pc++)
4187 idx(pc) = x.
idx(pc);
4198 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4210 return VIC::me_combine(me1,me2);
4217 if (VIC::med_update(p.u.
med,me) || force)
4227 schedule(home,*Propagator::cast(*p),me);
4233 if (b.base == NULL) {
4234 assert((free_and_bits >> free_bits) == 0);
4236 free_and_bits += 4 << free_bits;
4238 for (
int i=0;
i<pc_max+1;
i++)
4242 unsigned int n = degree();
4248 ((s <= b.base) && (b.base < s+home.pc.
p.n_sub)) ?
4249 (n+4) : ((n+1)*3>>1);
4251 free_and_bits += (m-
n) << free_bits;
4253 Heap::copy<ActorLink*>(prop, b.base,
n);
4262 assert(pc <= pc_max);
4264 home.pc.
p.n_sub += 1;
4265 if ((free_and_bits >> free_bits) == 0)
4267 free_and_bits -= 1 << free_bits;
4270 b.base[entries] = *actorNonZero(pc_max+1);
4272 for (
PropCond j = pc_max; j > pc; j--) {
4273 *actorNonZero(j+1) = *actorNonZero(j);
4276 *actorNonZero(pc+1) = *actor(pc);
4282 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4297 home.pc.
p.n_sub += 1;
4298 if ((free_and_bits >> free_bits) == 0)
4300 free_and_bits -= 1 << free_bits;
4303 b.base[entries++] = *actorNonZero(pc_max+1);
4304 *actorNonZero(pc_max+1) = a;
4345 assert(pc <= pc_max);
4350 while (f < actorNonZero(pc+1))
4358 while (*f != a) f++;
4361 *f = *(actorNonZero(pc+1)-1);
4362 for (
PropCond j = pc+1; j< pc_max+1; j++) {
4363 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4366 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4369 free_and_bits += 1 << free_bits;
4370 home.pc.
p.n_sub -= 1;
4387 while (f < b.base+entries)
4395 while (*f != a) f++;
4398 *f = b.base[--entries];
4399 free_and_bits += 1 << free_bits;
4400 home.pc.
p.n_sub -= 1;
4406 if (b.base != NULL) {
4415 unsigned int n_sub = degree();
4416 home.pc.
p.n_sub -= n_sub;
4417 unsigned int n = (free_and_bits >> free_bits) + n_sub;
4424 for (
PropCond pc=1; pc<pc_max+2; pc++)
4426 free_and_bits &= (1 << free_bits) - 1;
4437 ActorLink** la = actorNonZero(pc_max+1);
4448 assert(!a->disposed());
4450 switch (p.advise(home,*a,d)) {
4456 schedule(home,p,me);
4459 schedule(home,p,me,
true);
4465 }
while (++la < le);
4477 ActorLink** la = actorNonZero(pc_max+1);
4486 Advisor* a = Advisor::cast(static_cast<ActorLink*>
4488 assert(!a->disposed());
4492 }
while (++la < le);
4509 x->u.
idx[0] =
u.idx[0];
4510 if (pc_max > 0 &&
sizeof(
ActorLink**) >
sizeof(
unsigned int))
4511 x->u.
idx[1] =
u.idx[1];
4514 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4516 static_cast<unsigned int >(x->b.
base + x->entries -
4517 x->actorNonZero(pc_max+1));
4518 unsigned int n = na + np;
4519 assert(n == x->
degree());
4532 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4533 np -= 4; t += 4; f += 4;
4538 t[0] = p0; t[1] = p1;
4539 np -= 2; t += 2; f += 2;
4548 ptrdiff_t m0, m1, m2, m3;
4561 na -= 4; t += 4; f += 4;
4571 na -= 2; t += 2; f += 2;
4596 template<
class VarImp>
4598 #ifdef GECODE_HAS_VAR_DISPOSE 4599 Space::vd[VarImp::idx_d] =
this;
4603 template<
class VarImp>
4608 x->dispose(home); x =
static_cast<VarImp*
>(x->next_d());
4609 }
while (x != NULL);
4682 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4684 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4686 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4688 return (m == LO) ? lo : hi;
4697 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4702 return crazy(m,static_cast<unsigned int>(n));
4706 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4711 return cubic(m,static_cast<unsigned int>(n));
4715 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4720 return quadratic(m,static_cast<unsigned int>(n));
4724 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4729 return linear(m,static_cast<unsigned int>(n));
4733 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4737 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4741 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4750 : home(home0), q(home.pc.p.active) {
4751 while (q >= &home.pc.
p.queue[0]) {
4752 if (q->
next() != q) {
4753 c = q->
next(); e = q; q--;
4759 if (!home.pl.
empty()) {
4760 c = Propagator::cast(home.pl.
next());
4761 e = Propagator::cast(&home.pl);
4777 while (q >= &home.pc.
p.queue[0]) {
4778 if (q->
next() != q) {
4779 c = q->
next(); e = q; q--;
4785 if (!home.pl.
empty()) {
4786 c = Propagator::cast(home.pl.
next());
4787 e = Propagator::cast(&home.pl);
4796 return *Propagator::cast(c);
4802 : home(home0), q(home.pc.p.
active) {
4803 while (q >= &home.pc.
p.queue[0]) {
4804 if (q->
next() != q) {
4805 c = q->
next(); e = q; q--;
4823 while (q >= &home.pc.
p.queue[0]) {
4824 if (q->
next() != q) {
4825 c = q->
next(); e = q; q--;
4836 return *Propagator::cast(c);
4842 c = Propagator::cast(home.pl.
next());
4843 e = Propagator::cast(&home.pl);
4855 return *Propagator::cast(c);
4861 : c(
Brancher::cast(home.bl.next())), e(&home.bl) {}
4872 return *Brancher::cast(c);
4929 return id() == g.
id();
4933 return id() != g.
id();
4967 return id() == g.
id();
4971 return id() != g.
id();
4988 : ps(const_cast<
Space&>(home)), g(g0) {
5009 : bs(const_cast<
Space&>(home)), g(g0) {
5038 template<
class T,
typename A1>
5041 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5045 template<
class T,
typename A1,
typename A2>
5048 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5052 template<
class T,
typename A1,
typename A2,
typename A3>
5055 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5056 new (&
t) T(a1,a2,a3);
5059 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
5062 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5063 new (&
t) T(a1,a2,a3,a4);
5066 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
5069 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5070 new (&
t) T(a1,a2,a3,a4,a5);
bool empty(void) const
Test whether actor link is empty (points to itself)
static const int med_lst
End of bits for modification event delta.
void other(void)
Record that nothing is known at this point.
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)
Base-class for variable implementations.
Propagator * fwd(void) const
Return forwarding pointer during copying.
Space must be branched (at least one brancher left)
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_sc
Id of next brancher to be created plus status control.
BrancherGroup group(void) const
Return brancher group.
PropagatorGroup propagatorgroup(void) const
Return propagator group.
unsigned int a
Alternative.
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.
Kernel::GPI::Info & gpi(void)
Provide access to global propagator information.
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)
VarImpDisposer(void)
Constructor (registers disposer with kernel)
void update(Space &home, LocalHandle &lh)
Updating during cloning.
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)
const ViewTraceInfo & operator()(const Space &home) const
Provide access to view trace information.
PropagatorGroup(void)
Constructor.
NGL(void)
Constructor for creation.
void cancel(Space &home, Propagator &p, IntSet &y)
static const int free_bits
Freely available bits.
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
~PostInfo(void)
Reset information.
static PropagatorGroup all
Group of all propagators.
static BrancherGroup def
Group of branchers not in any user-defined group.
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.
const Propagator * propagator(void) const
Return pointer to non-subsumed propagator.
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.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Branchers(Space &home)
Initialize.
static ModEvent modevent(const Delta &d)
Return modification event.
Base-class for propagators.
Internal: propagator is subsumed, do not use.
virtual ~Choice(void)
Destructor.
const Brancher & b
Brancher.
T & construct(void)
Construction routines.
static const int idx_d
Index for disposal.
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
static PropCost record(void)
For recording information (no propagation allowed)
ActorLink ** base
Subscribed actors.
Propagator & propagator(void) const
Return propagator.
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.
void * mark(void *p)
Return marked pointer for unmarked pointer 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)
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
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Branchers(const Space &home, BrancherGroup g)
Initialize.
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.
bool operator()(void) const
Test whether there are branchers left.
void head(ActorLink *al)
Insert al directly after this.
Gecode::FloatVal c(-8, 8)
Configuration class for variable implementations without index structure.
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.
Class to iterate over branchers of a space.
Base-class for branchers.
Class for AFC (accumulated failure count) management.
const Brancher & brancher(void) const
Return currently executing brancher.
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.
const Propagator * p
Propagator.
What
What is currently executing.
void reset(void)
Reset information.
void reset(void)
Reset information.
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
Gecode::IntArgs i({1, 2, 3, 4})
bool operator()(void) const
Test whether there are propagators left.
double afc_decay(void) const
Return AFC decay factor.
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
bool copied(void) const
Is variable already copied.
Propagator & propagator(void) const
Return propagator.
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Propagators(const Space &home, PropagatorGroup g)
Initialize.
Execution has resulted in failure.
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Commit trace information.
StatusStatistics(void)
Initialize.
Propagator & propagator(void) const
Return propagator.
FloatVal operator+(const FloatVal &x)
void operator++(void)
Move iterator to next propagator.
PropagatorGroup group(void) const
Return propagator group.
Propagator for recording trace information.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
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.
bool failed(void) const
Check whether space is failed.
Propagator computed fixpoint.
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 const int idx_c
Index for update.
void operator++(void)
Move iterator to next propagator.
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
struct Gecode::Space::@58::@59 p
Data only available during propagation or branching.
bool failed(void) const
Check whether corresponding space is failed.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
static const int med_mask
Bitmask for modification event delta.
PropagatorGroup g
Propagator group.
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.
struct Gecode::Space::@58::@60 c
Data available only during copying.
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.
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
PropagatorGroup group(void) const
Return group propagator belongs to.
bool operator()(void) const
Test whether there are propagators left.
size_t size
The size of the propagator (used during subsumption)
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
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.
friend class PropagatorGroup
bool operator()(void) const
Test whether there are propagators left.
const Choice & choice(void) const
Return choice.
Council(void)
Default constructor.
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
#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.
unsigned int alternative(void) const
Return alternative.
static unsigned int next
Next group id.
Home & operator=(const Home &h)
Assignment operator.
IdlePropagators(Space &home)
Initialize.
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Propagate trace information.
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
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.
double afc(void) const
Return accumulated failure count (plus degree)
NGL * next(void) const
Return pointer to next literal.
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.
Advisor forces rescheduling of propagator.
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
void * subscriptions(void) const
Get the memory area for subscriptions.
Post propagator for SetVar SetOpType SetVar SetRelType r
unsigned int id(void) const
Return brancher id.
Class to iterate over propagators of a space.
Home operator()(Space &home)
To augment a space argument.
Class to iterate over idle propagators of a space.
const Brancher & brancher(void) const
Return propagator.
Class to store data shared among several spaces.
unsigned int i
Propagator id.
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.
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
void * ralloc(size_t s)
Allocate memory on space heap.
ScheduledPropagators(Space &home)
Initialize.
BrancherGroup(void)
Constructor.
Propagators(Space &home)
Initialize.
Class for storing propagator information.
ActualCost ac
Actual cost.
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
const Brancher & brancher(void) const
Return brancher.
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.
Generic domain change information to be supplied to advisors.
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
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.
Propagator did not compute fixpoint.
Propagator & propagator(void) const
Return the advisor's propagator.
Choice for performing commit
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
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 operator++(void)
Move iterator to next propagator.
unsigned int id(void) const
Return brancher identifier.
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Space & s
The space where the propagator is to be posted.
static NoGoods eng
Empty no-goods.
const Propagator & propagator(void) const
Return currently executing propagator.
static const PropCond pc_max
Maximal propagation condition.
Home operator()(Space &home)
To augment a space argument.
LocalObject * fwd(Space &home)
Return forwarding pointer.
void operator++(void)
Move iterator to next brancher.
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.
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
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.
Post propagator for SetVar x
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
VarImp< VIC > * fwd
Forwarding pointer.
Status status(void) const
Return propagator status.
virtual size_t dispose(Space &home)
Dispose.
Propagation has not computed fixpoint.
PropagateTraceInfo(unsigned int i, PropagatorGroup g, const Propagator *p, Status s)
Initialize.
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
unsigned int id(void) const
Return propagator identifier.
Propagator * p
A propagator (possibly) that is currently being rewritten.
void fail(void)
Mark space as failed.
void trace(Home home, const FloatVarArgs &x, TraceFilter tf, int te, FloatTracer &t)
Create a tracer for float variables.
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)
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
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.
#define GECODE_VTABLE_EXPORT
Class to iterate over scheduled propagators of a space.
unsigned int pid
Propagator identifier.
What what(void) const
Return what is currently executing.
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.
int ModEventDelta
Modification event deltas.
CommitTraceInfo(const Brancher &b, const Choice &c, unsigned int a)
Initialize.
unsigned int gid
Group identifier.
static const int idx_d
Index for dispose.
ptrdiff_t who
Encoding a tagged pointer or a tagged group id.
Home class for posting propagators
unsigned int bits(void) const
Provide access to free bits.
Base class for heap allocated objects.
static const int med_fst
Start of bits for modification event delta.
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
#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.
void update(IntSet &y, Space &home, IntSet &py)
bool advise(Space &home, ModEvent me, Delta &d)
Run advisors when variable implementation has been modified with modification event me and domain cha...
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Brancher & brancher(void) const
Return propagator.
CommitStatistics(void)
Initialize.
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
ViewTraceInfo vti
View trace information.
Base class for Variable type disposer.
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.
double afc(void) const
Return the accumlated failure count.
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.