Go to the documentation of this file.
37 #include <type_traits>
39 namespace Gecode {
namespace Int {
namespace Extensional {
45 template<
class View,
bool pos>
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));
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>
212 xr(
a.view()), sr(
a.fst()), lst(
a.lst()),
n(xr.
min()) {
222 template<
class View,
bool pos>
227 xr(
x), sr(
ts.fst(
i)), lst(
ts.lst(
i)),
n(xr.
min()) {
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));
254 assert(sr->min <= xr.min());
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>
272 assert(s == sr->supports(
n_words,
n));
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>
426 return static_cast<StatusType>(s & 3);
428 template<
class View,
class Table>
434 return reinterpret_cast<CTAdvisor*>(s) == &
a;
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>
468 assert((table.words() > 0U) && (table.width() >= table.words()));
469 if (table.words() <= 4U) {
470 switch (table.width()) {
512 template<
class View,
class Table>
516 :
Compact<View,true>(home,ts), status(MULTIPLE), table(home,ts.words()) {
520 template<
class View,
class Table>
525 assert((
x.size() > 1) && (ts.
tuples() > 1));
529 template<
class View,
class Table>
533 return sizeof(*this);
536 template<
class View,
class Table>
540 if ((status.type() != StatusType::NONE) ||
541 all() || table.empty())
545 template<
class View,
class Table>
555 status.propagating();
569 if (!table.intersects(supports(
a,
x.min())))
571 else if (!table.intersects(supports(
a,
x.max())))
577 int* nq =
r.alloc<
int>(
x.size());
578 unsigned int n_nq = 0;
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>
629 if (status.type() == StatusType::PROPAGATING)
637 table.template intersect_with_mask<true>(supports(
a,
x.val()));
641 if (!
x.any(
d) && (
x.min(
d) ==
x.max(
d))) {
642 table.nand_with_mask(supports(
a,
x.min(
d)));
644 }
else if (!
x.any(
d) && (
x.width(
d) <=
x.size())) {
647 table.nand_with_mask(ls.supports());
657 table.intersect_with_masks(supports(
a,
x.min()),
658 supports(
a,
x.max()));
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++) {
695 if ((
x.size() <= 1) || (ts.
tuples() <= 1))
699 switch (ts.
words()) {
733 template<
class View,
class Table>
734 template<
class TableProp>
737 :
Compact<View,false>(home,
p), table(home,
p.table) {
738 assert(!
table.empty());
741 template<
class View,
class Table>
744 assert((table.words() > 0U) && (table.width() >= table.words()));
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)
897 if (table.empty() || atmostone())
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>
1006 :
Compact<View,false>(home,
p), table(home,
p.table) {
1009 assert(!
table.empty());
1012 template<
class View,
class Table,
class CtrlView, ReifyMode rm>
1015 assert((table.words() > 0U) && (table.width() >= table.words()));
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>
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()) {
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
const Range * lst(int i) const
Return last range for position i.
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Base class for compact table propagator.
Post propagator for SetVar x
Compact< View, false >::ValidSupports ValidSupports
Table table
Current table.
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
Post propagator for SetVar SetOpType SetVar y
Council< CTAdvisor > c
The advisor council.
const BitSetData * supports(void) const
Return supports.
Inverse implication for reification.
bool full(const Table &table) const
Check whether the table covers the whole Cartedion product.
const Range * fst(int i) const
Return first range for position i.
unsigned int words(void) const
Return number of required bit set words.
const unsigned int n_words
Number of words in supports.
Compact< View, true >::LostSupports LostSupports
The propagator is currently running.
void propagating(void)
Set status to PROPAGATING.
A single view has been touched.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
bool all(void) const
Whether all variables are assigned.
ExecStatus ES_SUBSUMED(Propagator &p)
Compact(Space &home, Compact &p)
Constructor for cloning p.
StatusType
Type of status.
const Range * sr
Support iterator.
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts)
Post propagator for views x and table t.
ReCompact(Space &home, TableProp &p)
Constructor for cloning p.
const unsigned int n_words
Number of words.
Advisor for updating current table.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
bool atmostone(void) const
Whether at most one variable is unassigned.
virtual void reschedule(Space &home)
Schedule function.
bool assigned(View x, int v)
Whether x is assigned to value v.
const Range * range(CTAdvisor &a, int n)
Find range for n.
Table table
Current table.
Class to iterate over advisors of a council.
Compact< View, false >::ValidSupports ValidSupports
Value iterator for array of integers
Implication for reification.
Multiple view have been touched.
void operator++(void)
Move iterator to next value.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
bool disjoint(I &i, J &j)
Check whether range iterators i and j are disjoint.
size_t dispose(Space &home)
Delete propagator and return its size.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
CtrlView b
Boolean control view.
bool operator()(void) const
Whether there are still supports left.
Compact< View, false >::CTAdvisor CTAdvisor
const Range * _lst
Last range of support data structure.
Advisor storing a single view
Base-class for both propagators and branchers.
const BitSetData * supports(void) const
Provide access to corresponding supports.
bool assigned(void) const
Test whether view is assigned.
Compact< View, false >::CTAdvisor CTAdvisor
CTAdvisor(Space &home, Propagator &p, Council< CTAdvisor > &c, const TupleSet &ts, View x0, int i)
Initialise from parameters.
Table table
Current table.
ExecStatus postposcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for positive compact table propagator.
void dispose(Space &home, Council< CTAdvisor > &c)
Dispose advisor.
void touched(CTAdvisor &a)
Set status to SINGLE or MULTIPLE depending on a.
StatusType type(void) const
Return status type.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
ExecStatus postnegcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for compact table propagator.
PosCompact(Space &home, TableProp &p)
Constructor for cloning p.
int val(void) const
Return supported value.
TupleSet ts
The tuple set.
Gecode toplevel namespace
Domain consistent negative extensional propagator.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Base-class for propagators.
void setup(Space &home, Table &table, ViewArray< View > &x)
Setup the actual table.
Range iterator for integer views.
const BitSetData * s
The value's support.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
IntType u_type(unsigned int n)
Return type required to represent n.
Generic domain change information to be supplied to advisors.
View view(void) const
Access view.
Home class for posting propagators
Actor must always be disposed.
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
const BitSetData * supports(unsigned int n_words, int n) const
Return the supports for value n.
Post propagator for SetVar SetOpType SetVar SetRelType r
bool operator()(void) const
Whether iterator is done.
const BitSetData * supports(CTAdvisor &a, int n)
Return supports for value n.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
virtual void reschedule(Space &home)
Schedule function.
Compact< View, true >::ValidSupports ValidSupports
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts)
Post propagator for views x and table t.
void operator++(void)
Move to next supports.
Domain consistent reified extensional propagator.
const Range * fst(void) const
Return first range of support data structure.
virtual void reschedule(Space &home)
Schedule function.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
void none(void)
Set status to NONE.
Class represeting a set of tuples.
#define GECODE_NEVER
Assert that this command is never executed.
ValidSupports(const Compact< View, pos > &p, CTAdvisor &a)
Initialize from initialized propagator.
Status status
Propagator status.
int ModEvent
Type for modification events.
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts, CtrlView b)
Post propagator for views x and table t.
Domain consistent positive extensional propagator.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Propagation has computed fixpoint.
void adjust(void)
Adjust supports.
void find(void)
Find a new value (only for negative case)
Status(StatusType t)
Initialize with type t (either NONE or SEVERAL)
int tuples(void) const
Number of tuples.
const Range * lst(void) const
Return lasst range of support data structure.
ViewArray< View > y
The views (for rewriting)
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
size_t dispose(Space &home)
Delete propagator and return its size.
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
size_t dispose(Space &home)
Delete propagator and return its size.
ExecStatus postrecompact(Home home, ViewArray< View > &x, const TupleSet &ts, CtrlView b)
Post function for compact table propagator.
No view has been touched.
int n
Number of negative literals for node type.
const Range * _fst
First range of support data structure.
Execution has resulted in failure.
LostSupports(const Compact< View, pos > &p, CTAdvisor &a, int l, int h)
Initialize iterator for values between l and h.
bool single(CTAdvisor &a) const
Check whether status is single and equal to a.
int ModEventDelta
Modification event deltas.
Propagation has not computed fixpoint.
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Gecode::IntArgs i({1, 2, 3, 4})
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
bool pos(const View &x)
Test whether x is postive.
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
int p
Number of positive literals for node type.
const FloatNum max
Largest allowed float value.
NegCompact(Space &home, TableProp &p)
Constructor for cloning p.
Compact< View, true >::CTAdvisor CTAdvisor
#define GECODE_ASSUME(p)
Assert certain property.