37 #include <type_traits> 39 namespace Gecode {
namespace Int {
namespace Extensional {
45 template<
class View,
bool pos>
54 assert((
_fst->
min <= n) && (n <= _lst->max));
61 assert((
_fst->
min <= n) && (n <= _lst->max));
77 template<
class View,
bool pos>
86 template<
class View,
bool pos>
91 template<
class View,
bool pos>
97 template<
class View,
bool pos>
103 template<
class View,
bool pos>
114 template<
class View,
bool pos>
117 assert((n > a.fst()->max) && (n < a.lst()->min));
122 assert(!
pos || (f<=l));
125 const Range* m = f + ((l-
f) >> 1);
128 }
else if (n > m->
max) {
136 assert((f->
min <= n) && (n <= f->
max));
139 if ((f <= l) && (f->
min <= n) && (n <= f->
max))
146 template<
class View,
bool pos>
155 }
else if (n >= lst->
min) {
161 if ((n < fst->
min) || (n > lst->
max))
165 }
else if (n >= lst->
min) {
173 assert((fnd->
min <= n) && (n <= fnd->
max));
177 template<
class View,
bool pos>
183 while (xr() && (
n > xr.max()))
188 assert(
n <= xr.max());
191 while ((sr <=
lst) && (n > sr->max))
196 assert(n <= sr->
max);
199 if ((xr.min() <=
n) && (n <= xr.max())) {
207 template<
class View,
bool pos>
222 template<
class View,
bool pos>
237 template<
class View,
bool pos>
243 assert(n <= sr->
max);
245 }
else if (
n <=
max) {
252 assert((
xr.min() <=
n) && (
n <=
xr.max()));
253 assert((
sr->
min <=
n) && (n <= sr->
max));
257 if ((n <= sr->
max) && (
n <=
xr.max())) {
259 }
else if (
n <= max) {
264 template<
class View,
bool pos>
269 template<
class View,
bool pos>
275 template<
class View,
bool pos>
285 template<
class View,
bool pos>
297 template<
class View,
bool pos>
301 while ((
l <= h) && (
l >
r->max)) {
302 r++;
l=
r->min;
s=
r->s;
305 template<
class View,
bool pos>
310 template<
class View,
bool pos>
313 assert((
l >=
r->min) && (l <= r->
max));
318 template<
class View,
bool pos>
324 template<
class View,
bool pos>
328 if (!as())
return true;
333 template<
class View,
bool pos>
340 template<
class View,
bool pos>
343 :
Propagator(home), n_words(ts0.words()), ts(ts0), c(home) {
347 template<
class View,
bool pos>
348 template<
class Table>
356 for (
int i=0; i<x.
size(); i++) {
357 table.clear_mask(mask);
358 for (ValidSupports vs(ts,i,x[i]); vs(); ++vs)
359 table.add_to_mask(vs.supports(),mask);
360 table.template intersect_with_mask<false>(mask);
366 for (
int i=0; i<x.
size(); i++)
368 (
void)
new (home) CTAdvisor(home,*
this,c,ts,x[i],i);
373 View::schedule(home,*
this,me);
376 template<
class View,
bool pos>
377 template<
class Table>
380 unsigned long long int s = 1U;
382 s *=
static_cast<unsigned long long int>(as.advisor().view().size());
383 if (s > table.bits())
386 return s == table.ones();
389 template<
class View,
bool pos>
397 return PropCost::quadratic(PropCost::HI,n);
400 template<
class View,
bool pos>
406 (void) Propagator::dispose(home);
407 return sizeof(*this);
415 template<
class View,
class Table>
419 template<
class View,
class Table>
423 template<
class View,
class Table>
428 template<
class View,
class Table>
436 template<
class View,
class Table>
442 template<
class View,
class Table>
447 template<
class View,
class Table>
457 template<
class View,
class Table>
458 template<
class TableProp>
462 assert(!
table.empty());
465 template<
class View,
class Table>
469 if (
table.words() <= 4U) {
470 switch (
table.width()) {
512 template<
class View,
class Table>
520 template<
class View,
class Table>
529 template<
class View,
class Table>
533 return sizeof(*this);
536 template<
class View,
class Table>
545 template<
class View,
class Table>
565 if (touched.
single(a) || x.assigned())
577 int* nq = r.
alloc<
int>(x.size());
578 unsigned int n_nq = 0U;
580 int last_support = 0;
582 if (!
table.intersects(vs.supports()))
583 nq[n_nq++] = vs.val();
585 last_support = vs.val();
590 }
else if (n_nq == x.size() - 1U) {
608 assert(!
table.empty());
613 template<
class View,
class Table>
637 table.template intersect_with_mask<true>(
supports(a,x.val()));
641 if (!x.any(d) && (x.min(d) == x.max(d))) {
644 }
else if (!x.any(d) && (x.width(d) <= x.size())) {
646 for (
LostSupports ls(*
this,a,x.min(d),x.max(d)); ls(); ++ls) {
647 table.nand_with_mask(ls.supports());
663 table.clear_mask(mask);
665 table.add_to_mask(vs.supports(),mask);
666 table.template intersect_with_mask<false>(mask);
690 for (
int i=0; i<x.
size(); i++) {
699 switch (ts.
words()) {
733 template<
class View,
class Table>
734 template<
class TableProp>
738 assert(!
table.empty());
741 template<
class View,
class Table>
745 if (
table.words() <= 4U) {
746 switch (
table.width()) {
788 template<
class View,
class Table>
792 :
Compact<View,false>(home,ts),
table(home,ts.words()) {
796 template<
class View,
class Table>
804 template<
class View,
class Table>
808 return sizeof(*this);
811 template<
class View,
class Table>
817 template<
class View,
class Table>
821 if (!
table.empty()) {
834 unsigned long long int x_size = 1U;
835 unsigned long long int x_max = 1U;
840 unsigned long long int n = as.advisor().view().size();
842 x_size *= x_max; x_max =
n;
846 if (x_size >
table.bits())
849 if (x_size >
table.ones())
859 assert(!
table.empty());
864 x_size /=
static_cast<unsigned long long int>(x.size());
866 if ((x_size <=
table.bits()) && (x_size <=
table.ones())) {
868 int* nq = r.
alloc<
int>(x.size());
869 unsigned int n_nq = 0U;
872 if (x_size ==
table.ones(vs.supports()))
873 nq[n_nq++] = vs.val();
891 x_size *=
static_cast<unsigned long long int>(x.size());
895 if (
table.ones() == x_size)
902 template<
class View,
class Table>
918 table.template intersect_with_mask<true>(s);
934 table.clear_mask(mask);
936 table.add_to_mask(vs.supports(),mask);
939 table.template intersect_with_mask<false>(mask);
960 for (
int i=0; i<x.
size(); i++) {
968 switch (ts.
words()) {
1002 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1003 template<
class TableProp>
1009 assert(!
table.empty());
1012 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1016 if (
table.words() <= 4U) {
1017 switch (
table.width()) {
1066 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1070 :
Compact<View,false>(home,ts),
table(home,ts.words()),
b(b0),
y(x) {
1075 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1089 (void)
new (home)
ReCompact(home,x,ts,b);
1093 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1098 return sizeof(*this);
1101 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1107 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1124 if (
table.empty()) {
1138 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1145 if (
table.empty() ||
b.assigned())
1155 table.template intersect_with_mask<true>(s);
1171 table.clear_mask(mask);
1173 table.add_to_mask(vs.supports(),mask);
1176 table.template intersect_with_mask<false>(mask);
1190 template<
class View,
class CtrlView, ReifyMode rm>
1196 if (x.
size() != 0) {
1206 for (
int i=0; i<x.
size(); i++) {
1216 switch (ts.
words()) {
ExecStatus postnegcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for compact table propagator.
void free(void)
Free allocate memory.
void find(void)
Find a new value (only for negative case)
const Range * fst(void) const
Return first range of support data structure.
void dispose(Space &home, Council< A > &c)
Delete advisor.
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
ptrdiff_t s
A tagged pointer for storing the status.
TupleSet ts
The tuple set.
Inverse implication for reification.
virtual void reschedule(Space &home)
Schedule function.
Compact< View, false >::CTAdvisor CTAdvisor
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts, CtrlView b)
Post propagator for views x and table t.
const unsigned int n_words
Number of words.
Multiple view have been touched.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ExecStatus ES_SUBSUMED(Propagator &p)
#define GECODE_ASSUME(p)
Assert certain property.
const FloatNum max
Largest allowed float value.
StatusType type(void) const
Return status type.
Actor must always be disposed.
CtrlView b
Boolean control view.
Table table
Current table.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Value iterator for array of integers
void propagating(void)
Set status to PROPAGATING.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool assigned(void) const
Test whether view is assigned.
bool operator()(void) const
Whether iterator is done.
A single view has been touched.
ViewArray< View > y
The views (for rewriting)
const Range * _fst
First range of support data structure.
Compact< View, false >::CTAdvisor CTAdvisor
IntType u_type(unsigned int n)
Return type required to represent n.
bool pos(const View &x)
Test whether x is postive.
void adjust(void)
Adjust supports.
Compact< View, true >::LostSupports LostSupports
int ModEvent
Type for modification events.
Domain consistent positive extensional propagator.
Base-class for propagators.
bool all(void) const
Whether all variables are assigned.
void operator++(void)
Move iterator to next value.
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Class to iterate over advisors of a council.
const Range * range(CTAdvisor &a, int n)
Find range for n.
Table table
Current table.
bool single(CTAdvisor &a) const
Check whether status is single and equal to a.
void none(void)
Set status to NONE.
Propagation has computed fixpoint.
Advisor storing a single view
Base-class for both propagators and branchers.
Range iterator for integer views.
void touched(CTAdvisor &a)
Set status to SINGLE or MULTIPLE depending on a.
Compact< View, false >::ValidSupports ValidSupports
ValidSupports(const Compact< View, pos > &p, CTAdvisor &a)
Initialize from initialized propagator.
int tuples(void) const
Number of tuples.
View view(void) const
Access view.
int p
Number of positive literals for node type.
StatusType
Type of status.
Council< CTAdvisor > c
The advisor council.
int n
Number of negative literals for node type.
bool operator()(void) const
Whether there are still supports left.
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
size_t dispose(Space &home)
Delete propagator and return its size.
const Range * lst(void) const
Return lasst range of support data structure.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
const Range * lst(int i) const
Return last range for position i.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts)
Post propagator for views x and table t.
const BitSetData * supports(unsigned int n_words, int n) const
Return the supports for value n.
const unsigned int n_words
Number of words in supports.
Domain consistent reified extensional propagator.
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts)
Post propagator for views x and table t.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Compact(Space &home, Compact &p)
Constructor for cloning p.
virtual void reschedule(Space &home)
Schedule function.
ExecStatus postposcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for positive compact table propagator.
LostSupports(const Compact< View, pos > &p, CTAdvisor &a, int l, int h)
Initialize iterator for values between l and h.
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
NegCompact(Space &home, TableProp &p)
Constructor for cloning p.
const BitSetData * supports(void) const
Provide access to corresponding supports.
PosCompact(Space &home, TableProp &p)
Constructor for cloning p.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
bool atmostone(void) const
Whether at most one variable is unassigned.
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
const Range * fst(int i) const
Return first range for position i.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
const BitSetData * supports(CTAdvisor &a, int n)
Return supports for value n.
Class represeting a set of tuples.
const Range * lst
The last range.
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
const Range * _lst
Last range of support data structure.
size_t dispose(Space &home)
Delete propagator and return its size.
Node * x
Pointer to corresponding Boolean expression node.
Generic domain change information to be supplied to advisors.
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
CTAdvisor(Space &home, Propagator &p, Council< CTAdvisor > &c, const TupleSet &ts, View x0, int i)
Initialise from parameters.
virtual void reschedule(Space &home)
Schedule function.
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
The propagator is currently running.
void operator++(void)
Move to next supports.
bool assigned(View x, int v)
Whether x is assigned to value v.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Compact< View, true >::CTAdvisor CTAdvisor
bool disjoint(I &i, J &j)
Check whether range iterators i and j are disjoint.
Advisor for updating current table.
void dispose(Space &home, Council< CTAdvisor > &c)
Dispose advisor.
No view has been touched.
ViewRanges< View > xr
Range iterator.
Post propagator for SetVar x
Propagation has not computed fixpoint.
Domain consistent negative extensional propagator.
ReCompact(Space &home, TableProp &p)
Constructor for cloning p.
Gecode toplevel namespace
size_t dispose(Space &home)
Delete propagator and return its size.
Implication for reification.
Base class for compact table propagator.
Status(StatusType t)
Initialize with type t (either NONE or SEVERAL)
virtual Actor * copy(Space &home)
Copy propagator during cloning.
int ModEventDelta
Modification event deltas.
int size(void) const
Return size of array (number of elements)
const BitSetData * supports(void) const
Return supports.
Home class for posting propagators
void setup(Space &home, Table &table, ViewArray< View > &x)
Setup the actual table.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Table table
Current table.
#define GECODE_NEVER
Assert that this command is never executed.
const Range * sr
Support iterator.
Status status
Propagator status.
int val(void) const
Return supported value.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Compact< View, true >::ValidSupports ValidSupports
ExecStatus postrecompact(Home home, ViewArray< View > &x, const TupleSet &ts, CtrlView b)
Post function for compact table propagator.
bool full(const Table &table) const
Check whether the table covers the whole Cartedion product.
const BitSetData * s
The value's support.
Compact< View, false >::ValidSupports ValidSupports
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
unsigned int words(void) const
Return number of required bit set words.