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;
271 template<
class VarImp>
323 static const int idx_c = VIC::idx_c;
325 static const int idx_d = VIC::idx_d;
327 static const int free_bits = VIC::free_bits;
329 unsigned int entries;
331 unsigned int free_and_bits;
346 unsigned int idx[pc_max+1];
358 unsigned int idx(
PropCond pc)
const;
380 void resize(
Space& home);
389 void cancel(
Space& home);
398 void _fail(
Space& home);
402 #ifdef GECODE_HAS_VAR_DISPOSE 451 unsigned int degree(
void)
const;
458 double afc(
void)
const;
466 bool copied(
void)
const;
468 VarImp* forward(
void)
const;
509 unsigned int bits(
void)
const;
512 unsigned int& bits(
void);
522 static void*
operator new(size_t,
Space&);
525 static void operator delete(
void*,
Space&);
527 static void operator delete(
void*);
684 bool empty(
void)
const;
686 template<
class T>
static ActorLink* cast(T*
a);
688 template<
class T>
static const ActorLink* cast(
const T*
a);
720 virtual size_t dispose(
Space& home);
722 static void*
operator new(
size_t s,
Space& home);
724 static void operator delete(
void*
p,
Space& home);
730 static void*
operator new(
size_t s);
732 static void operator delete(
void*
p);
750 static const unsigned int GROUPID_ALL = 0U;
752 static const unsigned int GROUPID_DEF = 1U;
754 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
764 Group(
unsigned int gid0);
776 unsigned int id(
void)
const;
840 void kill(
Space& home);
843 void disable(
Space& home);
851 void enable(
Space& home,
bool s=
true);
909 void kill(
Space& home);
943 operator Space&(void);
962 bool failed(
void)
const;
1002 What what(
void)
const;
1006 const Brancher& brancher(
void)
const;
1052 unsigned int id(
void)
const;
1058 Status status(
void)
const;
1077 unsigned int id(
void)
const;
1081 const Brancher& brancher(
void)
const;
1083 const Choice& choice(
void)
const;
1085 unsigned int alternative(
void)
const;
1116 void disable(
Space& home);
1118 void enable(
Space& home);
1218 double afc(
void)
const;
1223 unsigned int id(
void)
const;
1230 bool disabled(
void)
const;
1255 bool empty(
void)
const;
1259 void dispose(
Space& home);
1276 bool operator ()(
void)
const;
1278 void operator ++(
void);
1280 A& advisor(
void)
const;
1301 bool disposed(
void)
const;
1324 static void*
operator new(
size_t s,
Space& home);
1326 static void operator delete(
void*
p,
Space& home);
1330 static void operator delete(
void*
p);
1333 static void*
operator new(
size_t s);
1373 virtual bool notice(
void)
const;
1375 virtual size_t dispose(
Space& home);
1378 bool leaf(
void)
const;
1381 NGL* next(
void)
const;
1391 static void*
operator new(
size_t s,
Space& home);
1394 static void operator delete(
void* s,
Space& home);
1396 static void operator delete(
void*
p);
1402 static void*
operator new(
size_t s);
1421 unsigned int id(
void)
const;
1427 unsigned int alternatives(
void)
const;
1431 virtual size_t size(
void)
const = 0;
1434 virtual void archive(
Archive& e)
const;
1475 virtual bool status(
const Space& home)
const = 0;
1493 unsigned int a) = 0;
1518 std::ostream& o)
const;
1522 unsigned int id(
void)
const;
1598 unsigned long int n;
1606 unsigned long int ng(
void)
const;
1608 void ng(
unsigned long int n);
1634 const unsigned long int r;
1637 const unsigned long int s;
1639 const unsigned long int f;
1647 const unsigned int a;
1655 unsigned long int s,
1656 unsigned long int f,
1662 Type type(
void)
const;
1666 unsigned long int restart(
void)
const;
1669 unsigned long int solution(
void)
const;
1671 unsigned long int fail(
void)
const;
1673 const Space* last(
void)
const;
1675 const NoGoods& nogoods(
void)
const;
1679 unsigned int asset(
void)
const;
1752 friend class Propagators;
1755 friend class Branchers;
1795 Brancher* brancher(
unsigned int id);
1804 void kill_brancher(
unsigned int id);
1807 static const unsigned reserved_bid = 0U;
1810 static const unsigned int sc_bits = 2;
1812 static const unsigned int sc_fast = 0;
1814 static const unsigned int sc_disabled = 1;
1816 static const unsigned int sc_trace = 2;
1866 #ifdef GECODE_HAS_VAR_DISPOSE 1872 template<
class VIC>
VarImpBase* vars_d(
void)
const;
1919 bool share_info=
true);
1954 void _commit(
const Choice&
c,
unsigned int a);
1987 void _trycommit(
const Choice&
c,
unsigned int a);
1996 void ap_notice_dispose(
Actor*
a,
bool d);
2004 void ap_ignore_dispose(
Actor*
a,
bool d);
2031 virtual ~
Space(
void);
2074 virtual bool master(
const MetaInfo& mi);
2101 virtual bool slave(
const MetaInfo& mi);
2154 const Choice* choice(
void);
2192 bool share_info=
true,
2229 void commit(
const Choice&
c,
unsigned int a,
2263 void trycommit(
const Choice&
c,
unsigned int a,
2301 void print(
const Choice&
c,
unsigned int a, std::ostream& o)
const;
2427 bool failed(
void)
const;
2432 bool stable(
void)
const;
2456 T* alloc(
long unsigned int n);
2464 T* alloc(
long int n);
2472 T* alloc(
unsigned int n);
2491 void free(T*
b,
long unsigned int n);
2502 void free(T*
b,
long int n);
2513 void free(T*
b,
unsigned int n);
2524 void free(T*
b,
int n);
2537 T* realloc(T*
b,
long unsigned int n,
long unsigned int m);
2550 T* realloc(T*
b,
long int n,
long int m);
2563 T* realloc(T*
b,
unsigned int n,
unsigned int m);
2576 T* realloc(T*
b,
int n,
int m);
2585 T** realloc(T**
b,
long unsigned int n,
long unsigned int m);
2594 T** realloc(T**
b,
long int n,
long int m);
2603 T** realloc(T**
b,
unsigned int n,
unsigned int m);
2612 T** realloc(T**
b,
int n,
int m);
2614 void* ralloc(
size_t s);
2616 void rfree(
void*
p,
size_t s);
2618 void* rrealloc(
void*
b,
size_t n,
size_t m);
2620 template<
size_t>
void* fl_alloc(
void);
2649 template<
class T,
typename A1>
2650 T& construct(A1
const& a1);
2656 template<
class T,
typename A1,
typename A2>
2657 T& construct(A1
const& a1, A2
const& a2);
2663 template<
class T,
typename A1,
typename A2,
typename A3>
2664 T& construct(A1
const& a1, A2
const& a2, A3
const& a3);
2670 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
2671 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4);
2677 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
2678 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4, A5
const& a5);
2683 void afc_decay(
double d);
2686 double afc_decay(
void)
const;
2707 Propagators(
Space& home);
2709 bool operator ()(
void)
const;
2711 void operator ++(
void);
2720 class ScheduledPropagators {
2732 ScheduledPropagators(
Space& home);
2734 bool operator ()(
void)
const;
2736 void operator ++(
void);
2745 class IdlePropagators {
2753 IdlePropagators(
Space& home);
2755 bool operator ()(
void)
const;
2757 void operator ++(
void);
2774 Branchers(
Space& home);
2776 bool operator ()(
void)
const;
2778 void operator ++(
void);
2795 bool operator ()(
void)
const;
2797 void operator ++(
void);
2813 bool operator ()(
void)
const;
2815 void operator ++(
void);
2817 const Brancher& brancher(
void)
const;
2831 return mm.alloc(
sm,s);
2835 return mm.reuse(p,s);
2839 char*
b =
static_cast<char*
>(
_b);
2841 char*
p =
static_cast<char*
>(ralloc(m));
2854 return mm.template fl_alloc<s>(
sm);
2859 mm.template fl_dispose<s>(
f,
l);
2869 T*
p =
static_cast<T*
>(ralloc(
sizeof(T)*n));
2870 for (
long unsigned int i=n;
i--; )
2871 (
void)
new (p+
i) T();
2878 return alloc<T>(
static_cast<long unsigned int>(
n));
2883 return alloc<T>(
static_cast<long unsigned int>(
n));
2889 return alloc<T>(
static_cast<long unsigned int>(
n));
2895 for (
long unsigned int i=n;
i--; )
2897 rfree(b,n*
sizeof(T));
2903 free<T>(
b,
static_cast<long unsigned int>(
n));
2908 free<T>(
b,
static_cast<long unsigned int>(
n));
2914 free<T>(
b,
static_cast<long unsigned int>(
n));
2921 T*
p =
static_cast<T*
>(ralloc(
sizeof(T)*m));
2922 for (
long unsigned int i=n;
i--; )
2923 (
void)
new (p+
i) T(b[
i]);
2924 for (
long unsigned int i=n; i<m; i++)
2925 (
void)
new (p+
i) T();
2936 assert((n >= 0) && (m >= 0));
2937 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2938 static_cast<long unsigned int>(m));
2943 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2944 static_cast<long unsigned int>(m));
2949 assert((n >= 0) && (m >= 0));
2950 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2951 static_cast<long unsigned int>(m));
2954 #define GECODE_KERNEL_REALLOC(T) \ 2957 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \ 2958 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \ 2962 Space::realloc<T>(T* b, long int n, long int m) { \ 2963 assert((n >= 0) && (m >= 0)); \ 2964 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2965 static_cast<long unsigned int>(m)); \ 2969 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \ 2970 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2971 static_cast<long unsigned int>(m)); \ 2975 Space::realloc<T>(T* b, int n, int m) { \ 2976 assert((n >= 0) && (m >= 0)); \ 2977 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2978 static_cast<long unsigned int>(m)); \ 2993 #undef GECODE_KERNEL_REALLOC 2998 return static_cast<T**
>(rrealloc(b,n*
sizeof(T),m*
sizeof(T*)));
3003 assert((n >= 0) && (m >= 0));
3004 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
3005 static_cast<long unsigned int>(m));
3010 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
3011 static_cast<long unsigned int>(m));
3016 assert((n >= 0) && (m >= 0));
3017 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
3018 static_cast<long unsigned int>(m));
3022 #ifdef GECODE_HAS_VAR_DISPOSE 3025 Space::vars_d(
void)
const {
3026 return _vars_d[VIC::idx_d];
3031 _vars_d[VIC::idx_d] =
x;
3037 Actor::operator
delete(
void*) {}
3039 Actor::operator
delete(
void*,
Space&) {}
3041 Actor::operator
new(
size_t s,
Space& home) {
3042 return home.ralloc(s);
3054 return home.ralloc(s);
3059 Advisor::operator
delete(
void*) {}
3062 Advisor::operator
delete(
void*,
Space&) {}
3064 Advisor::operator
new(
size_t s,
Space& home) {
3065 return home.ralloc(s);
3069 NGL::operator
delete(
void*) {}
3073 NGL::operator
new(
size_t s,
Space& home) {
3074 return home.ralloc(s);
3083 : next(NULL), fwd(NULL), use_cnt(0) {}
3086 assert(use_cnt == 0);
3094 SharedHandle::subscribe(
void) {
3095 if (o != NULL) o->use_cnt++;
3098 SharedHandle::cancel(
void) {
3099 if ((o != NULL) && (--o->use_cnt == 0))
3106 cancel(); o=
n; subscribe();
3122 cancel(); o=sh.o; subscribe();
3132 }
else if (sh.o->fwd != NULL) {
3137 sh.o->next = home.pc.
c.shared;
3138 home.pc.
c.shared = sh.o;
3173 unsigned long int s0,
3174 unsigned long int f0,
3177 :
t(RESTART),
r(r0), s(s0),
f(f0),
l(l0),
ng(ng0),
a(0) {}
3252 p->_next =
n; n->_prev =
p;
3257 _next =
this; _prev =
this;
3264 this->_next =
a; a->_prev =
this;
3265 a->_next =
n; n->_prev =
a;
3272 a->_next =
this; this->_prev =
a;
3273 p->_next =
a; a->_prev =
p;
3278 return _next ==
this;
3309 return static_cast<Actor*
>(&
t);
3317 return static_cast<const Actor*
>(&
t);
3322 s.notice(a,p,duplicate);
3330 return const_cast<Space*
>(
this)->_clone(share_data,share_info);
3355 return sizeof(*this);
3366 : s(s0),
p(p0), pg(pg0), bg(bg0) {}
3390 return Home(*
this,&p);
3411 who =
reinterpret_cast<ptrdiff_t
>(&
p) | PROPAGATOR;
3415 who =
reinterpret_cast<ptrdiff_t
>(&
b) | BRANCHER;
3419 who = (g.
id() << 2) | POST;
3427 return static_cast<What>(who & 3);
3431 assert(what() == PROPAGATOR);
3437 assert(what() == BRANCHER);
3438 return *
reinterpret_cast<Brancher*
>(who & ~3);
3442 assert(what() == POST);
3465 :
i(i0), g(g0),
p(p0), s(s0) {}
3491 :
b(b0),
c(c0),
a(a0) {}
3545 Propagator::disable(
Space& home) {
3546 home.pc.
p.bid_sc |= Space::sc_disabled;
3551 Propagator::enable(
Space& home) {
3567 static_cast<
Space&>(home).gpi.allocate(home.propagatorgroup().gid)) {
3569 assert((u.med == 0) && (u.size == 0));
3570 static_cast<Space&
>(home).pl.head(
this);
3575 : gpi_disabled(p.gpi_disabled) {
3577 assert((u.med == 0) && (u.size == 0));
3622 assert(p.u.
med != 0);
3629 assert(p.u.
med != 0);
3652 return static_cast<const Brancher*
>(&
t);
3657 gid(_home.branchergroup().gid) {
3659 bid = home.pc.
p.bid_sc >> Space::sc_bits;
3660 home.pc.
p.bid_sc += (1 << Space::sc_bits);
3661 if ((home.pc.
p.bid_sc >> Space::sc_bits) == 0U)
3664 if (home.b_status == &static_cast<Space&>(home).bl) {
3665 home.b_status =
this;
3666 if (home.b_commit == &static_cast<Space&>(home).bl)
3667 home.b_commit =
this;
3674 : bid(b.bid), gid(b.gid) {
3700 b_commit = Brancher::cast(b.next());
3702 b_status = Brancher::cast(b.next());
3715 Space::brancher(
unsigned int id) {
3732 while (b_commit != Brancher::cast(&bl))
3733 if (
id != b_commit->id())
3734 b_commit = Brancher::cast(b_commit->next());
3737 if (b_commit == Brancher::cast(&bl)) {
3739 b_commit = Brancher::cast(bl.next());
3740 while (b_commit != b_old)
3741 if (
id != b_commit->id())
3742 b_commit = Brancher::cast(b_commit->next());
3785 fwdcopy(home,share);
3818 : bid(b.id()), alt(a) {}
3826 Choice::id(
void)
const {
3873 return sizeof(*this);
3893 Advisor::disposed(
void)
const {
3894 return prev() == NULL;
3899 return static_cast<Advisor*
>(al);
3904 return static_cast<const Advisor*
>(al);
3909 assert(!disposed());
3916 assert(!disposed());
3920 if ((n != NULL) && n->disposed())
3926 return home.pc.
p.vti;
3969 while ((a != NULL) && static_cast<A*>(a)->disposed())
3981 while ((a != NULL) && static_cast<A*>(a)->disposed())
3986 if (c.advisors != NULL) {
3990 Propagator* p_t = Propagator::cast(p_f->prev());
3995 while (*a_f != NULL) {
3996 if (static_cast<A*>(*a_f)->disposed()) {
3997 *a_f = (*a_f)->next();
4000 A*
a =
new (home) A(home,share,*static_cast<A*>(*a_f));
4008 a_f = (*a_f)->next_ref();
4025 if (!static_cast<A*>(a)->disposed())
4026 static_cast<A*
>(
a)->dispose(home,*
this);
4041 while ((a != NULL) && static_cast<A*>(a)->disposed())
4056 }
while ((a != NULL) && static_cast<A*>(a)->disposed());
4062 return *
static_cast<A*
>(a);
4076 if (c > pc.p.active)
4105 return ((pc.p.active < &pc.p.queue[0]) ||
4110 Space::findtr(
void) {
4112 for (
Actor** a=d_fst; a<d_cur; a++)
4125 ap_notice_dispose(&a,d);
4128 pc.p.bid_sc |= sc_trace;
4131 pc.p.bid_sc |= sc_trace;
4145 ap_ignore_dispose(&a,d);
4147 if ((p &
AP_TRACE) && (d_fst != NULL))
4162 assert((pc >= 0) && (pc < pc_max+2));
4163 return (pc == 0) ? b.base : b.base+
u.idx[pc-1];
4169 assert((pc > 0) && (pc < pc_max+2));
4170 return b.base+
u.idx[pc-1];
4176 assert((pc > 0) && (pc < pc_max+2));
4183 assert((pc > 0) && (pc < pc_max+2));
4190 b.base = NULL; entries = 0;
4191 for (
PropCond pc=1; pc<pc_max+2; pc++)
4199 b.base = NULL; entries = 0;
4200 for (
PropCond pc=1; pc<pc_max+2; pc++)
4221 d += Propagator::cast(*a)->afc(); a++;
4230 ->propagator().afc();
4246 return free_and_bits;
4252 return free_and_bits;
4255 #ifdef GECODE_HAS_VAR_DISPOSE 4259 return static_cast<VarImp<VIC>*
>(home.vars_d<VIC>());
4265 home.vars_d<VIC>(
x);
4293 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4294 if (x.b.
base == NULL) {
4296 reg = &home.pc.
c.vars_noidx;
4299 reg = &home.pc.
c.vars_u[idx_c];
4303 entries = x.entries;
4304 for (
PropCond pc=1; pc<pc_max+2; pc++)
4305 idx(pc) = x.
idx(pc);
4316 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4328 return VIC::me_combine(me1,me2);
4335 if (VIC::med_update(p.u.
med,me) || force)
4345 schedule(home,*Propagator::cast(*p),me);
4351 if (b.base == NULL) {
4352 assert((free_and_bits >> free_bits) == 0);
4354 free_and_bits += 4 << free_bits;
4356 for (
int i=0;
i<pc_max+1;
i++)
4360 unsigned int n = degree();
4366 ((s <= b.base) && (b.base < s+home.pc.
p.n_sub)) ?
4367 (n+4) : ((n+1)*3>>1);
4369 free_and_bits += (m-
n) << free_bits;
4371 Heap::copy<ActorLink*>(prop, b.base,
n);
4380 assert(pc <= pc_max);
4382 home.pc.
p.n_sub += 1;
4383 if ((free_and_bits >> free_bits) == 0)
4385 free_and_bits -= 1 << free_bits;
4388 b.base[entries] = *actorNonZero(pc_max+1);
4390 for (
PropCond j = pc_max; j > pc; j--) {
4391 *actorNonZero(j+1) = *actorNonZero(j);
4394 *actorNonZero(pc+1) = *actor(pc);
4400 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4415 home.pc.
p.n_sub += 1;
4416 if ((free_and_bits >> free_bits) == 0)
4418 free_and_bits -= 1 << free_bits;
4421 b.base[entries++] = *actorNonZero(pc_max+1);
4422 *actorNonZero(pc_max+1) = a;
4463 assert(pc <= pc_max);
4468 while (f < actorNonZero(pc+1))
4476 while (*f != a) f++;
4479 *f = *(actorNonZero(pc+1)-1);
4480 for (
PropCond j = pc+1; j< pc_max+1; j++) {
4481 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4484 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4487 free_and_bits += 1 << free_bits;
4488 home.pc.
p.n_sub -= 1;
4505 while (f < b.base+entries)
4513 while (*f != a) f++;
4516 *f = b.base[--entries];
4517 free_and_bits += 1 << free_bits;
4518 home.pc.
p.n_sub -= 1;
4524 if (b.base != NULL) {
4533 unsigned int n_sub = degree();
4534 home.pc.
p.n_sub -= n_sub;
4535 unsigned int n = (free_and_bits >> free_bits) + n_sub;
4542 for (
PropCond pc=1; pc<pc_max+2; pc++)
4544 free_and_bits &= (1 << free_bits) - 1;
4555 ActorLink** la = actorNonZero(pc_max+1);
4566 assert(!a->disposed());
4568 switch (p.advise(home,*a,d)) {
4574 schedule(home,p,me);
4577 schedule(home,p,me,
true);
4583 }
while (++la < le);
4595 ActorLink** la = actorNonZero(pc_max+1);
4604 Advisor* a = Advisor::cast(static_cast<ActorLink*>
4606 assert(!a->disposed());
4610 }
while (++la < le);
4627 x->u.
idx[0] =
u.idx[0];
4628 if (pc_max > 0 &&
sizeof(
ActorLink**) >
sizeof(
unsigned int))
4629 x->u.
idx[1] =
u.idx[1];
4632 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4634 static_cast<unsigned int >(x->b.
base + x->entries -
4635 x->actorNonZero(pc_max+1));
4636 unsigned int n = na + np;
4637 assert(n == x->
degree());
4650 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4651 np -= 4; t += 4; f += 4;
4656 t[0] = p0; t[1] = p1;
4657 np -= 2; t += 2; f += 2;
4666 ptrdiff_t m0, m1, m2, m3;
4679 na -= 4; t += 4; f += 4;
4689 na -= 2; t += 2; f += 2;
4714 template<
class VarImp>
4716 #ifdef GECODE_HAS_VAR_DISPOSE 4717 Space::vd[VarImp::idx_d] =
this;
4721 template<
class VarImp>
4726 x->dispose(home); x =
static_cast<VarImp*
>(x->next_d());
4727 }
while (x != NULL);
4800 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4802 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4804 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4806 return (m == LO) ? lo : hi;
4815 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4820 return crazy(m,static_cast<unsigned int>(n));
4824 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4829 return cubic(m,static_cast<unsigned int>(n));
4833 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4838 return quadratic(m,static_cast<unsigned int>(n));
4842 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4847 return linear(m,static_cast<unsigned int>(n));
4851 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4855 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4859 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4867 Space::Propagators::Propagators(
Space& home0)
4868 : home(home0), q(home.pc.
p.active) {
4869 while (q >= &home.pc.
p.queue[0]) {
4870 if (q->next() != q) {
4871 c = q->next(); e = q; q--;
4877 if (!home.pl.
empty()) {
4878 c = Propagator::cast(home.pl.
next());
4879 e = Propagator::cast(&home.pl);
4885 Space::Propagators::operator ()(
void)
const {
4889 Space::Propagators::operator ++(
void) {
4895 while (q >= &home.pc.
p.queue[0]) {
4896 if (q->next() != q) {
4897 c = q->next(); e = q; q--;
4903 if (!home.pl.
empty()) {
4904 c = Propagator::cast(home.pl.
next());
4905 e = Propagator::cast(&home.pl);
4914 return *Propagator::cast(
c);
4919 Space::ScheduledPropagators::ScheduledPropagators(
Space& home0)
4920 : home(home0), q(home.pc.
p.active) {
4921 while (q >= &home.pc.
p.queue[0]) {
4922 if (q->next() != q) {
4923 c = q->next(); e = q; q--;
4931 Space::ScheduledPropagators::operator ()(
void)
const {
4935 Space::ScheduledPropagators::operator ++(
void) {
4941 while (q >= &home.pc.
p.queue[0]) {
4942 if (q->next() != q) {
4943 c = q->next(); e = q; q--;
4954 return *Propagator::cast(
c);
4959 Space::IdlePropagators::IdlePropagators(
Space& home) {
4960 c = Propagator::cast(home.pl.
next());
4961 e = Propagator::cast(&home.pl);
4964 Space::IdlePropagators::operator ()(
void)
const {
4968 Space::IdlePropagators::operator ++(
void) {
4973 return *Propagator::cast(
c);
4978 Space::Branchers::Branchers(
Space& home)
4979 :
c(Brancher::cast(home.bl.
next())), e(&home.bl) {}
4981 Space::Branchers::operator ()(
void)
const {
4985 Space::Branchers::operator ++(
void) {
4989 Space::Branchers::brancher(
void)
const {
4990 return *Brancher::cast(
c);
5047 return id() == g.
id();
5051 return id() != g.
id();
5085 return id() == g.
id();
5089 return id() != g.
id();
5107 while (ps() && !g.
in(ps.propagator().group()))
5118 while (ps() && !g.
in(ps.propagator().group()));
5122 return ps.propagator();
5128 while (bs() && !g.
in(bs.brancher().group()))
5139 while (bs() && !g.
in(bs.brancher().group()));
5143 return bs.brancher();
5156 template<
class T,
typename A1>
5159 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5163 template<
class T,
typename A1,
typename A2>
5166 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5170 template<
class T,
typename A1,
typename A2,
typename A3>
5173 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5174 new (&
t) T(a1,a2,a3);
5177 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
5180 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5181 new (&
t) T(a1,a2,a3,a4);
5184 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
5187 T&
t = *
static_cast<T*
>(ralloc(
sizeof(T)));
5188 new (&
t) T(a1,a2,a3,a4,a5);
bool empty(void) const
Test whether actor link is empty (points to itself)
void other(void)
Record that nothing is known at this point.
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)
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.
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
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)
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)
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.
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 .
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 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.
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 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.
struct Gecode::Space::@56::@57 p
Data only available during propagation or branching.
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.
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.
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
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.
Gecode::IntArgs i(4, 1, 2, 3, 4)
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.
Global propagator information.
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.
unsigned int pid
Propagator identifier.
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.
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Execution has resulted in failure.
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Commit trace information.
StatusStatistics(void)
Initialize.
FloatVal operator+(const FloatVal &x)
SharedHandle::Object * object(void) const
Access to the shared object.
PropagatorGroup group(void) const
Return propagator group.
Propagator for recording trace information.
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.
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 Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
bool failed(void) const
Check whether corresponding space is failed.
PropagatorGroup g
Propagator group.
unsigned int size(I &i)
Size of all ranges of range iterator i.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
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.
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.
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
const Choice & choice(void) const
Return choice.
Council(void)
Default constructor.
LocalObject * fwd(Space &home, bool share)
Return forwarding pointer.
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.
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.
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.
double afc(void) const
Return accumulated failure count (plus degree)
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.
Advisor forces rescheduling of propagator.
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Post propagator for SetVar SetOpType SetVar SetRelType r
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.
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.
BrancherGroup(void)
Constructor.
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.
virtual ~Object(void)
Delete shared object.
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.
unsigned int gid
Group identifier.
Exception: action has wrong arity
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.
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.
struct Gecode::Space::@56::@58 c
Data available only during copying.
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.
const Propagator & propagator(void) const
Return currently executing propagator.
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.
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.
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.
Class for storing timed-decay value.
#define GECODE_VTABLE_EXPORT
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.
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 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.
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
ViewTraceInfo vti
View trace information.
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.
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)
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
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.