compact.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Linnea Ingmar <linnea.ingmar@hotmail.com>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Linnea Ingmar, 2017
* Christian Schulte, 2017
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <algorithm>
#include <type_traits>
namespace Gecode { namespace Int { namespace Extensional {
/*
* Advisor
*
*/
template<class View, bool pos>
forceinline void
Compact<View,pos>::CTAdvisor::adjust(void) {
if (pos) {
{
int n = view().min();
assert((_fst->min <= n) && (n <= _lst->max));
while (n > _fst->max)
_fst++;
assert((_fst->min <= n) && (n <= _lst->max));
}
{
int n = view().max();
assert((_fst->min <= n) && (n <= _lst->max));
while (n < _lst->min)
_lst--;
assert((_fst->min <= n) && (n <= _lst->max));
}
} else {
{
int n = view().min();
while ((_fst <= _lst) && (n > _fst->max))
_fst++;
}
{
int n = view().max();
while ((_fst <= _lst) && (n < _lst->min))
_lst--;
}
}
}
template<class View, bool pos>
forceinline
Compact<View,pos>::CTAdvisor::CTAdvisor
(Space& home, Propagator& p,
Council<CTAdvisor>& c, const TupleSet& ts, View x0, int i)
: ViewAdvisor<View>(home,p,c,x0), _fst(ts.fst(i)), _lst(ts.lst(i)) {
adjust();
}
template<class View, bool pos>
forceinline
Compact<View,pos>::CTAdvisor::CTAdvisor(Space& home, CTAdvisor& a)
: ViewAdvisor<View>(home,a), _fst(a._fst), _lst(a._lst) {}
template<class View, bool pos>
forceinline const typename Compact<View,pos>::Range*
Compact<View,pos>::CTAdvisor::fst(void) const {
return _fst;
}
template<class View, bool pos>
forceinline const typename Compact<View,pos>::Range*
Compact<View,pos>::CTAdvisor::lst(void) const {
return _lst;
}
template<class View, bool pos>
forceinline void
Compact<View,pos>::CTAdvisor::dispose(Space& home, Council<CTAdvisor>& c) {
(void) ViewAdvisor<View>::dispose(home,c);
}
/*
* The propagator base class
*
*/
template<class View, bool pos>
const typename Compact<View,pos>::Range*
Compact<View,pos>::range(CTAdvisor& a, int n) {
assert((n > a.fst()->max) && (n < a.lst()->min));
const Range* f=a.fst()+1;
const Range* l=a.lst()-1;
assert(!pos || (f<=l));
while (f < l) {
const Range* m = f + ((l-f) >> 1);
if (n < m->min) {
l=m-1;
} else if (n > m->max) {
f=m+1;
} else {
f=m; break;
}
}
if (pos) {
assert((f->min <= n) && (n <= f->max));
return f;
} else {
if ((f <= l) && (f->min <= n) && (n <= f->max))
return f;
else
return nullptr;
}
}
template<class View, bool pos>
forceinline const BitSetData*
Compact<View,pos>::supports(CTAdvisor& a, int n) {
const Range* fnd;
const Range* fst=a.fst();
const Range* lst=a.lst();
if (pos) {
if (n <= fst->max) {
fnd=fst;
} else if (n >= lst->min) {
fnd=lst;
} else {
fnd=range(a,n);
}
} else {
if ((n < fst->min) || (n > lst->max))
return nullptr;
if (n <= fst->max) {
fnd=fst;
} else if (n >= lst->min) {
fnd=lst;
} else {
fnd=range(a,n);
if (!fnd)
return nullptr;
}
}
assert((fnd->min <= n) && (n <= fnd->max));
return fnd->supports(n_words,n);
}
template<class View, bool pos>
forceinline void
Compact<View,pos>::ValidSupports::find(void) {
assert(!pos);
assert(n <= max);
while (true) {
while (xr() && (n > xr.max()))
++xr;
if (!xr()) {
n = max+1; return;
}
assert(n <= xr.max());
n = std::max(n,xr.min());
while ((sr <= lst) && (n > sr->max))
sr++;
if (sr > lst) {
n = max+1; return;
}
assert(n <= sr->max);
n = std::max(n,sr->min);
if ((xr.min() <= n) && (n <= xr.max())) {
s = sr->supports(n_words,n);
return;
}
}
GECODE_NEVER;
}
template<class View, bool pos>
forceinline
Compact<View,pos>::ValidSupports::ValidSupports(const Compact<View,pos>& p,
CTAdvisor& a)
: n_words(p.n_words), max(a.view().max()),
xr(a.view()), sr(a.fst()), lst(a.lst()), n(xr.min()) {
if (pos) {
while (n > sr->max)
sr++;
s = sr->supports(n_words,n);
} else {
s = nullptr; // To avoid warnings
find();
}
}
template<class View, bool pos>
forceinline
Compact<View,pos>::ValidSupports::ValidSupports(const TupleSet& ts,
int i, View x)
: n_words(ts.words()), max(x.max()),
xr(x), sr(ts.fst(i)), lst(ts.lst(i)), n(xr.min()) {
if (pos) {
while (n > sr->max)
sr++;
s = sr->supports(n_words,n);
} else {
s = nullptr; // To avoid warnings
find();
}
}
template<class View, bool pos>
forceinline void
Compact<View,pos>::ValidSupports::operator ++(void) {
n++;
if (pos) {
if (n <= xr.max()) {
assert(n <= sr->max);
s += n_words;
} else if (n <= max) {
while (n > xr.max())
++xr;
n = xr.min();
while (n > sr->max)
sr++;
s = sr->supports(n_words,n);
assert((xr.min() <= n) && (n <= xr.max()));
assert((sr->min <= n) && (n <= sr->max));
assert(sr->min <= xr.min());
}
} else {
if ((n <= sr->max) && (n <= xr.max())) {
s += n_words;
} else if (n <= max) {
find();
}
}
}
template<class View, bool pos>
forceinline bool
Compact<View,pos>::ValidSupports::operator ()(void) const {
return n <= max;
}
template<class View, bool pos>
forceinline const BitSetData*
Compact<View,pos>::ValidSupports::supports(void) const {
assert(s == sr->supports(n_words,n));
return s;
}
template<class View, bool pos>
forceinline int
Compact<View,pos>::ValidSupports::val(void) const {
return n;
}
/*
* Lost supports iterator
*
*/
template<class View, bool pos>
forceinline
Compact<View,pos>::LostSupports::LostSupports
(const Compact<View,pos>& p, CTAdvisor& a, int l0, int h0)
: n_words(p.n_words), r(a.fst()), l(l0), h(h0) {
assert(pos);
// Move to first value for which there is support
while (l > r->max)
r++;
l = std::max(l,r->min);
s = r->supports(n_words,l);
}
template<class View, bool pos>
forceinline void
Compact<View,pos>::LostSupports::operator ++(void) {
l++; s += n_words;
while ((l <= h) && (l > r->max)) {
r++; l=r->min; s=r->s;
}
}
template<class View, bool pos>
forceinline bool
Compact<View,pos>::LostSupports::operator ()(void) const {
return l<=h;
}
template<class View, bool pos>
forceinline const TupleSet::BitSetData*
Compact<View,pos>::LostSupports::supports(void) const {
assert((l >= r->min) && (l <= r->max));
assert(s == r->supports(n_words,l));
return s;
}
template<class View, bool pos>
forceinline bool
Compact<View,pos>::all(void) const {
Advisors<CTAdvisor> as(c);
return !as();
}
template<class View, bool pos>
forceinline bool
Compact<View,pos>::atmostone(void) const {
Advisors<CTAdvisor> as(c);
if (!as()) return true;
++as;
return !as();
}
template<class View, bool pos>
forceinline
Compact<View,pos>::Compact(Space& home, Compact& p)
: Propagator(home,p), n_words(p.n_words), ts(p.ts) {
c.update(home,p.c);
}
template<class View, bool pos>
forceinline
Compact<View,pos>::Compact(Home home, const TupleSet& ts0)
: Propagator(home), n_words(ts0.words()), ts(ts0), c(home) {
home.notice(*this, AP_DISPOSE);
}
template<class View, bool pos>
template<class Table>
void
Compact<View,pos>::setup(Space& home, Table& table, ViewArray<View>& x) {
// For scheduling the propagator
ModEvent me = ME_INT_BND;
Region r;
BitSetData* mask = r.alloc<BitSetData>(table.size());
// Invalidate tuples
for (int i=0; i<x.size(); i++) {
table.clear_mask(mask);
for (ValidSupports vs(ts,i,x[i]); vs(); ++vs)
table.add_to_mask(vs.supports(),mask);
table.template intersect_with_mask<false>(mask);
// The propagator must be scheduled for subsumption
if (table.empty())
goto schedule;
}
// Post advisors
for (int i=0; i<x.size(); i++)
if (!x[i].assigned())
(void) new (home) CTAdvisor(home,*this,c,ts,x[i],i);
else
me = ME_INT_VAL;
// Schedule propagator
schedule:
View::schedule(home,*this,me);
}
template<class View, bool pos>
template<class Table>
forceinline bool
Compact<View,pos>::full(const Table& table) const {
unsigned long long int s = 1U;
for (Advisors<CTAdvisor> as(c); as(); ++as) {
s *= static_cast<unsigned long long int>(as.advisor().view().size());
if (s > table.bits())
return false;
}
return s == table.ones();
}
template<class View, bool pos>
PropCost
Compact<View,pos>::cost(const Space&, const ModEventDelta&) const {
// Computing this is crucial in case there are many propagators!
int n = 0;
// The value of 3 is cheating from the Gecode kernel...
for (Advisors<CTAdvisor> as(c); as() && (n <= 3); ++as)
n++;
return PropCost::quadratic(PropCost::HI,n);
}
template<class View, bool pos>
forceinline size_t
Compact<View,pos>::dispose(Space& home) {
home.ignore(*this,AP_DISPOSE);
c.dispose(home);
ts.~TupleSet();
(void) Propagator::dispose(home);
return sizeof(*this);
}
/*
* Status for the positive propagator
*
*/
template<class View, class Table>
forceinline
PosCompact<View,Table>::Status::Status(StatusType t)
: s(t) {}
template<class View, class Table>
forceinline
PosCompact<View,Table>::Status::Status(const Status& s)
: s(s.s) {}
template<class View, class Table>
forceinline typename PosCompact<View,Table>::StatusType
PosCompact<View,Table>::Status::type(void) const {
return static_cast<StatusType>(s & 3);
}
template<class View, class Table>
forceinline bool
PosCompact<View,Table>::Status::single(CTAdvisor& a) const {
if (type() != SINGLE)
return false;
assert(type() == 0);
return reinterpret_cast<CTAdvisor*>(s) == &a;
}
template<class View, class Table>
forceinline void
PosCompact<View,Table>::Status::touched(CTAdvisor& a) {
if (!single(a))
s = MULTIPLE;
}
template<class View, class Table>
forceinline void
PosCompact<View,Table>::Status::none(void) {
s = NONE;
}
template<class View, class Table>
forceinline void
PosCompact<View,Table>::Status::propagating(void) {
s = PROPAGATING;
}
/*
* The propagator proper
*
*/
template<class View, class Table>
template<class TableProp>
forceinline
PosCompact<View,Table>::PosCompact(Space& home, TableProp& p)
: Compact<View,true>(home,p), status(NONE), table(home,p.table) {
assert(!table.empty());
}
template<class View, class Table>
Actor*
PosCompact<View,Table>::copy(Space& home) {
assert((table.words() > 0U) && (table.width() >= table.words()));
if (table.words() <= 4U) {
switch (table.width()) {
case 0U:
GECODE_NEVER; break;
case 1U:
return new (home) PosCompact<View,TinyBitSet<1U>>(home,*this);
case 2U:
return new (home) PosCompact<View,TinyBitSet<2U>>(home,*this);
case 3U:
return new (home) PosCompact<View,TinyBitSet<3U>>(home,*this);
case 4U:
return new (home) PosCompact<View,TinyBitSet<4U>>(home,*this);
default:
break;
}
}
if (std::is_same<Table,BitSet<unsigned char>>::value) {
goto copy_char;
} else if (std::is_same<Table,BitSet<unsigned short int>>::value) {
switch (Gecode::Support::u_type(table.width())) {
case Gecode::Support::IT_CHAR: goto copy_char;
case Gecode::Support::IT_SHRT: goto copy_short;
case Gecode::Support::IT_INT: GECODE_NEVER;
default: GECODE_NEVER;
}
} else {
switch (Gecode::Support::u_type(table.width())) {
case Gecode::Support::IT_CHAR: goto copy_char;
case Gecode::Support::IT_SHRT: goto copy_short;
case Gecode::Support::IT_INT: goto copy_int;
default: GECODE_NEVER;
}
GECODE_NEVER;
return nullptr;
}
copy_char:
return new (home) PosCompact<View,BitSet<unsigned char>>(home,*this);
copy_short:
return new (home) PosCompact<View,BitSet<unsigned short int>>(home,*this);
copy_int:
return new (home) PosCompact<View,BitSet<unsigned int>>(home,*this);
}
template<class View, class Table>
forceinline
PosCompact<View,Table>::PosCompact(Home home, ViewArray<View>& x,
const TupleSet& ts)
: Compact<View,true>(home,ts), status(MULTIPLE), table(home,ts.words()) {
setup(home,table,x);
}
template<class View, class Table>
forceinline ExecStatus
PosCompact<View,Table>::post(Home home, ViewArray<View>& x,
const TupleSet& ts) {
auto ct = new (home) PosCompact(home,x,ts);
assert((x.size() > 1) && (ts.tuples() > 1));
return ct->table.empty() ? ES_FAILED : ES_OK;
}
template<class View, class Table>
forceinline size_t
PosCompact<View,Table>::dispose(Space& home) {
(void) Compact<View,true>::dispose(home);
return sizeof(*this);
}
template<class View, class Table>
void
PosCompact<View,Table>::reschedule(Space& home) {
// Modified variable, subsumption, or failure
if ((status.type() != StatusType::NONE) ||
all() || table.empty())
View::schedule(home,*this,ME_INT_DOM);
}
template<class View, class Table>
ExecStatus
PosCompact<View,Table>::propagate(Space& home, const ModEventDelta&) {
if (table.empty())
return ES_FAILED;
if (all())
return home.ES_SUBSUMED(*this);
Status touched(status);
// Mark as performing propagation
status.propagating();
Region r;
// Scan all values of all unassigned variables to see if they
// are still supported.
for (Advisors<CTAdvisor> as(c); as(); ++as) {
CTAdvisor& a = as.advisor();
View x = a.view();
// No point filtering variable if it was the only modified variable
if (touched.single(a) || x.assigned())
continue;
if (x.size() == 2) { // Consider min and max values only
if (!table.intersects(supports(a,x.min())))
GECODE_ME_CHECK(x.eq(home,x.max()));
else if (!table.intersects(supports(a,x.max())))
GECODE_ME_CHECK(x.eq(home,x.min()));
if (!x.assigned())
a.adjust();
} else { // x.size() > 2
// How many values to remove
int* nq = r.alloc<int>(x.size());
unsigned int n_nq = 0;
// The initialization is here just to avoid warnings...
int last_support = 0;
for (ValidSupports vs(*this,a); vs(); ++vs)
if (!table.intersects(vs.supports()))
nq[n_nq++] = vs.val();
else
last_support = vs.val();
// Remove collected values
if (n_nq > 0U) {
if (n_nq == 1U) {
GECODE_ME_CHECK(x.nq(home,nq[0]));
} else if (n_nq == x.size() - 1U) {
GECODE_ME_CHECK(x.eq(home,last_support));
goto noadjust;
} else {
Iter::Values::Array rnq(nq,n_nq);
GECODE_ASSUME(n_nq >= 2U);
GECODE_ME_CHECK(x.minus_v(home,rnq,false));
}
a.adjust();
noadjust: ;
}
r.free();
}
}
// Mark as no touched variable
status.none();
// Should not be in a failed state
assert(!table.empty());
// Subsume if there is at most one non-assigned variable
return atmostone() ? home.ES_SUBSUMED(*this) : ES_FIX;
}
template<class View, class Table>
ExecStatus
PosCompact<View,Table>::advise(Space& home, Advisor& a0, const Delta& d) {
CTAdvisor& a = static_cast<CTAdvisor&>(a0);
// Do not fail a disabled propagator
if (table.empty())
return Compact<View,true>::disabled() ?
home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
View x = a.view();
/*
* Do not schedule if propagator is performing propagation,
* and dispose if assigned.
*/
if (status.type() == StatusType::PROPAGATING)
return x.assigned() ? home.ES_FIX_DISPOSE(c,a) : ES_FIX;
// Update status
status.touched(a);
if (x.assigned()) {
// Variable is assigned -- intersect with its value
table.template intersect_with_mask<true>(supports(a,x.val()));
return home.ES_NOFIX_DISPOSE(c,a);
}
if (!x.any(d) && (x.min(d) == x.max(d))) {
table.nand_with_mask(supports(a,x.min(d)));
a.adjust();
} else if (!x.any(d) && (x.width(d) <= x.size())) {
// Incremental update, using the removed values
for (LostSupports ls(*this,a,x.min(d),x.max(d)); ls(); ++ls) {
table.nand_with_mask(ls.supports());
if (table.empty())
return Compact<View,true>::disabled() ?
home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
}
a.adjust();
} else {
a.adjust();
// Reset-based update, using the values that are left
if (x.size() == 2) {
table.intersect_with_masks(supports(a,x.min()),
supports(a,x.max()));
} else {
Region r;
BitSetData* mask = r.alloc<BitSetData>(table.size());
// Collect all tuples to be kept in a temporary mask
table.clear_mask(mask);
for (ValidSupports vs(*this,a); vs(); ++vs)
table.add_to_mask(vs.supports(),mask);
table.template intersect_with_mask<false>(mask);
}
}
// Do not fail a disabled propagator
if (table.empty())
return Compact<View,true>::disabled() ?
home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
// Schedule propagator
return ES_NOFIX;
}
/*
* Post function
*/
template<class View>
ExecStatus
postposcompact(Home home, ViewArray<View>& x, const TupleSet& ts) {
if (ts.tuples() == 0)
return (x.size() == 0) ? ES_OK : ES_FAILED;
// All variables pruned to correct domain
for (int i=0; i<x.size(); i++) {
TupleSet::Ranges r(ts,i);
GECODE_ME_CHECK(x[i].inter_r(home, r, false));
}
if ((x.size() <= 1) || (ts.tuples() <= 1))
return ES_OK;
// Choose the right bit set implementation
switch (ts.words()) {
case 0U:
GECODE_NEVER; return ES_OK;
case 1U:
return PosCompact<View,TinyBitSet<1U>>::post(home,x,ts);
case 2U:
return PosCompact<View,TinyBitSet<2U>>::post(home,x,ts);
case 3U:
return PosCompact<View,TinyBitSet<3U>>::post(home,x,ts);
case 4U:
return PosCompact<View,TinyBitSet<4U>>::post(home,x,ts);
default:
switch (Gecode::Support::u_type(ts.words())) {
case Gecode::Support::IT_CHAR:
return PosCompact<View,BitSet<unsigned char>>
::post(home,x,ts);
case Gecode::Support::IT_SHRT:
return PosCompact<View,BitSet<unsigned short int>>
::post(home,x,ts);
case Gecode::Support::IT_INT:
return PosCompact<View,BitSet<unsigned int>>
::post(home,x,ts);
default: GECODE_NEVER;
}
}
GECODE_NEVER;
return ES_OK;
}
/*
* The negative propagator
*
*/
template<class View, class Table>
template<class TableProp>
forceinline
NegCompact<View,Table>::NegCompact(Space& home, TableProp& p)
: Compact<View,false>(home,p), table(home,p.table) {
assert(!table.empty());
}
template<class View, class Table>
Actor*
NegCompact<View,Table>::copy(Space& home) {
assert((table.words() > 0U) && (table.width() >= table.words()));
if (table.words() <= 4U) {
switch (table.width()) {
case 0U:
GECODE_NEVER; break;
case 1U:
return new (home) NegCompact<View,TinyBitSet<1U>>(home,*this);
case 2U:
return new (home) NegCompact<View,TinyBitSet<2U>>(home,*this);
case 3U:
return new (home) NegCompact<View,TinyBitSet<3U>>(home,*this);
case 4U:
return new (home) NegCompact<View,TinyBitSet<4U>>(home,*this);
default:
break;
}
}
if (std::is_same<Table,BitSet<unsigned char>>::value) {
goto copy_char;
} else if (std::is_same<Table,BitSet<unsigned short int>>::value) {
switch (Gecode::Support::u_type(table.width())) {
case Gecode::Support::IT_CHAR: goto copy_char;
case Gecode::Support::IT_SHRT: goto copy_short;
case Gecode::Support::IT_INT: GECODE_NEVER;
default: GECODE_NEVER;
}
} else {
switch (Gecode::Support::u_type(table.width())) {
case Gecode::Support::IT_CHAR: goto copy_char;
case Gecode::Support::IT_SHRT: goto copy_short;
case Gecode::Support::IT_INT: goto copy_int;
default: GECODE_NEVER;
}
GECODE_NEVER;
return nullptr;
}
copy_char:
return new (home) NegCompact<View,BitSet<unsigned char>>(home,*this);
copy_short:
return new (home) NegCompact<View,BitSet<unsigned short int>>(home,*this);
copy_int:
return new (home) NegCompact<View,BitSet<unsigned int>>(home,*this);
}
template<class View, class Table>
forceinline
NegCompact<View,Table>::NegCompact(Home home, ViewArray<View>& x,
const TupleSet& ts)
: Compact<View,false>(home,ts), table(home,ts.words()) {
setup(home,table,x);
}
template<class View, class Table>
forceinline ExecStatus
NegCompact<View,Table>::post(Home home, ViewArray<View>& x,
const TupleSet& ts) {
auto ct = new (home) NegCompact(home,x,ts);
return ct->full(ct->table) ? ES_FAILED : ES_OK;
}
template<class View, class Table>
forceinline size_t
NegCompact<View,Table>::dispose(Space& home) {
(void) Compact<View,false>::dispose(home);
return sizeof(*this);
}
template<class View, class Table>
void
NegCompact<View,Table>::reschedule(Space& home) {
View::schedule(home,*this,ME_INT_DOM);
}
template<class View, class Table>
ExecStatus
NegCompact<View,Table>::propagate(Space& home, const ModEventDelta&) {
#ifndef NDEBUG
if (!table.empty()) {
// Check that all views have at least one value with support
for (Advisors<CTAdvisor> as(c); as(); ++as) {
ValidSupports vs(*this,as.advisor());
assert(vs());
}
}
#endif
if (table.empty())
return home.ES_SUBSUMED(*this);
// Estimate whether any pruning will be possible
unsigned long long int x_size = 1U;
unsigned long long int x_max = 1U;
/* The size of the Cartesian product will be x_size times x_max,
* where x_max is the size of the largest variable domain.
*/
for (Advisors<CTAdvisor> as(c); as(); ++as) {
unsigned long long int n = as.advisor().view().size();
if (n > x_max) {
x_size *= x_max; x_max = n;
} else {
x_size *= n;
}
if (x_size > table.bits())
return ES_FIX;
}
if (x_size > table.ones())
return ES_FIX;
{
// Adjust to size of the Cartesian product
x_size *= x_max;
Region r;
for (Advisors<CTAdvisor> as(c); as(); ++as) {
assert(!table.empty());
CTAdvisor& a = as.advisor();
View x = a.view();
// Adjust for the current variable domain
x_size /= static_cast<unsigned long long int>(x.size());
if ((x_size <= table.bits()) && (x_size <= table.ones())) {
// How many values to remove
int* nq = r.alloc<int>(x.size());
unsigned int n_nq = 0U;
for (ValidSupports vs(*this,a); vs(); ++vs)
if (x_size == table.ones(vs.supports()))
nq[n_nq++] = vs.val();
// Remove collected values
if (n_nq > 0U) {
if (n_nq == 1U) {
GECODE_ME_CHECK(x.nq(home,nq[0]));
} else {
Iter::Values::Array rnq(nq,n_nq);
GECODE_ASSUME(n_nq >= 2U);
GECODE_ME_CHECK(x.minus_v(home,rnq,false));
}
if (table.empty())
return home.ES_SUBSUMED(*this);
a.adjust();
}
r.free();
}
// Re-adjust size
x_size *= static_cast<unsigned long long int>(x.size());
}
}
if (table.ones() == x_size)
return ES_FAILED;
if (table.empty() || atmostone())
return home.ES_SUBSUMED(*this);
return ES_FIX;
}
template<class View, class Table>
ExecStatus
NegCompact<View,Table>::advise(Space& home, Advisor& a0, const Delta&) {
CTAdvisor& a = static_cast<CTAdvisor&>(a0);
// We are subsumed
if (table.empty())
return home.ES_NOFIX_DISPOSE(c,a);
View x = a.view();
a.adjust();
if (x.assigned()) {
// Variable is assigned -- intersect with its value
if (const BitSetData* s = supports(a,x.val()))
table.template intersect_with_mask<true>(s);
else
table.flush(); // Mark as subsumed
return home.ES_NOFIX_DISPOSE(c,a);
}
{
ValidSupports vs(*this,a);
if (!vs()) {
table.flush(); // Mark as subsumed
return home.ES_NOFIX_DISPOSE(c,a);
}
Region r;
BitSetData* mask = r.alloc<BitSetData>(table.size());
// Collect all tuples to be kept in a temporary mask
table.clear_mask(mask);
do {
table.add_to_mask(vs.supports(),mask);
++vs;
} while (vs());
table.template intersect_with_mask<false>(mask);
}
if (table.empty())
return home.ES_NOFIX_DISPOSE(c,a);
// Schedule propagator
return ES_NOFIX;
}
/*
* Post function
*/
template<class View>
ExecStatus
postnegcompact(Home home, ViewArray<View>& x, const TupleSet& ts) {
if (ts.tuples() == 0)
return ES_OK;
// Check whether a variable does not overlap with supported values
for (int i=0; i<x.size(); i++) {
TupleSet::Ranges rs(ts,i);
ViewRanges<View> rx(x[i]);
if (Iter::Ranges::disjoint(rs,rx))
return ES_OK;
}
// Choose the right bit set implementation
switch (ts.words()) {
case 0U:
GECODE_NEVER; return ES_OK;
case 1U:
return NegCompact<View,TinyBitSet<1U>>::post(home,x,ts);
case 2U:
return NegCompact<View,TinyBitSet<2U>>::post(home,x,ts);
case 3U:
return NegCompact<View,TinyBitSet<3U>>::post(home,x,ts);
case 4U:
return NegCompact<View,TinyBitSet<4U>>::post(home,x,ts);
default:
switch (Gecode::Support::u_type(ts.words())) {
case Gecode::Support::IT_CHAR:
return NegCompact<View,BitSet<unsigned char>>
::post(home,x,ts);
case Gecode::Support::IT_SHRT:
return NegCompact<View,BitSet<unsigned short int>>
::post(home,x,ts);
case Gecode::Support::IT_INT:
return NegCompact<View,BitSet<unsigned int>>
::post(home,x,ts);
default: GECODE_NEVER;
}
}
GECODE_NEVER;
return ES_OK;
}
/*
* The reified propagator
*
*/
template<class View, class Table, class CtrlView, ReifyMode rm>
template<class TableProp>
forceinline
ReCompact<View,Table,CtrlView,rm>::ReCompact(Space& home, TableProp& p)
: Compact<View,false>(home,p), table(home,p.table) {
b.update(home,p.b);
y.update(home,p.y);
assert(!table.empty());
}
template<class View, class Table, class CtrlView, ReifyMode rm>
Actor*
ReCompact<View,Table,CtrlView,rm>::copy(Space& home) {
assert((table.words() > 0U) && (table.width() >= table.words()));
if (table.words() <= 4U) {
switch (table.width()) {
case 0U:
GECODE_NEVER; break;
case 1U:
return new (home) ReCompact<View,TinyBitSet<1U>,CtrlView,rm>
(home,*this);
case 2U:
return new (home) ReCompact<View,TinyBitSet<2U>,CtrlView,rm>
(home,*this);
case 3U:
return new (home) ReCompact<View,TinyBitSet<3U>,CtrlView,rm>
(home,*this);
case 4U:
return new (home) ReCompact<View,TinyBitSet<4U>,CtrlView,rm>
(home,*this);
default:
break;
}
}
if (std::is_same<Table,BitSet<unsigned char>>::value) {
goto copy_char;
} else if (std::is_same<Table,BitSet<unsigned short int>>::value) {
switch (Gecode::Support::u_type(table.width())) {
case Gecode::Support::IT_CHAR: goto copy_char;
case Gecode::Support::IT_SHRT: goto copy_short;
case Gecode::Support::IT_INT: GECODE_NEVER;
default: GECODE_NEVER;
}
} else {
switch (Gecode::Support::u_type(table.width())) {
case Gecode::Support::IT_CHAR: goto copy_char;
case Gecode::Support::IT_SHRT: goto copy_short;
case Gecode::Support::IT_INT: goto copy_int;
default: GECODE_NEVER;
}
GECODE_NEVER;
return nullptr;
}
copy_char:
return new (home) ReCompact<View,BitSet<unsigned char>,CtrlView,rm>
(home,*this);
copy_short:
return new (home) ReCompact<View,BitSet<unsigned short int>,CtrlView,rm>
(home,*this);
copy_int:
return new (home) ReCompact<View,BitSet<unsigned int>,CtrlView,rm>
(home,*this);
}
template<class View, class Table, class CtrlView, ReifyMode rm>
forceinline
ReCompact<View,Table,CtrlView,rm>::ReCompact(Home home, ViewArray<View>& x,
const TupleSet& ts, CtrlView b0)
: Compact<View,false>(home,ts), table(home,ts.words()), b(b0), y(x) {
b.subscribe(home,*this,PC_BOOL_VAL);
setup(home,table,x);
}
template<class View, class Table, class CtrlView, ReifyMode rm>
forceinline ExecStatus
ReCompact<View,Table,CtrlView,rm>::post(Home home, ViewArray<View>& x,
const TupleSet& ts, CtrlView b) {
if (b.one()) {
if (rm == RM_PMI)
return ES_OK;
return postposcompact(home,x,ts);
}
if (b.zero()) {
if (rm == RM_IMP)
return ES_OK;
return postnegcompact(home,x,ts);
}
(void) new (home) ReCompact(home,x,ts,b);
return ES_OK;
}
template<class View, class Table, class CtrlView, ReifyMode rm>
forceinline size_t
ReCompact<View,Table,CtrlView,rm>::dispose(Space& home) {
b.cancel(home,*this,PC_BOOL_VAL);
(void) Compact<View,false>::dispose(home);
return sizeof(*this);
}
template<class View, class Table, class CtrlView, ReifyMode rm>
void
ReCompact<View,Table,CtrlView,rm>::reschedule(Space& home) {
View::schedule(home,*this,ME_INT_DOM);
}
template<class View, class Table, class CtrlView, ReifyMode rm>
ExecStatus
ReCompact<View,Table,CtrlView,rm>::propagate(Space& home,
const ModEventDelta&) {
if (b.one()) {
if (rm == RM_PMI)
return home.ES_SUBSUMED(*this);
TupleSet keep(ts);
GECODE_REWRITE(*this,postposcompact(home(*this),y,keep));
}
if (b.zero()) {
if (rm == RM_IMP)
return home.ES_SUBSUMED(*this);
TupleSet keep(ts);
GECODE_REWRITE(*this,postnegcompact(home(*this),y,keep));
}
if (table.empty()) {
if (rm != RM_PMI)
GECODE_ME_CHECK(b.zero_none(home));
return home.ES_SUBSUMED(*this);
}
if (full(table)) {
if (rm != RM_IMP)
GECODE_ME_CHECK(b.one_none(home));
return home.ES_SUBSUMED(*this);
}
return ES_FIX;
}
template<class View, class Table, class CtrlView, ReifyMode rm>
ExecStatus
ReCompact<View,Table,CtrlView,rm>::advise(Space& home,
Advisor& a0, const Delta&) {
CTAdvisor& a = static_cast<CTAdvisor&>(a0);
// We are subsumed
if (table.empty() || b.assigned())
return home.ES_NOFIX_DISPOSE(c,a);
View x = a.view();
a.adjust();
if (x.assigned()) {
// Variable is assigned -- intersect with its value
if (const BitSetData* s = supports(a,x.val()))
table.template intersect_with_mask<true>(s);
else
table.flush(); // Mark as failed
return home.ES_NOFIX_DISPOSE(c,a);
}
{
ValidSupports vs(*this,a);
if (!vs()) {
table.flush(); // Mark as failed
return home.ES_NOFIX_DISPOSE(c,a);
}
Region r;
BitSetData* mask = r.alloc<BitSetData>(table.size());
// Collect all tuples to be kept in a temporary mask
table.clear_mask(mask);
do {
table.add_to_mask(vs.supports(),mask);
++vs;
} while (vs());
table.template intersect_with_mask<false>(mask);
}
if (table.empty())
return home.ES_NOFIX_DISPOSE(c,a);
// Schedule propagator
return ES_NOFIX;
}
/*
* Post function
*/
template<class View, class CtrlView, ReifyMode rm>
ExecStatus
postrecompact(Home home, ViewArray<View>& x, const TupleSet& ts,
CtrlView b) {
// Enforce invariant that there is at least one tuple...
if (ts.tuples() == 0) {
if (x.size() != 0) {
if (rm != RM_PMI)
GECODE_ME_CHECK(b.zero(home));
} else {
if (rm != RM_IMP)
GECODE_ME_CHECK(b.one(home));
}
return ES_OK;
}
// Check whether a variable does not overlap with supported values
for (int i=0; i<x.size(); i++) {
TupleSet::Ranges rs(ts,i);
ViewRanges<View> rx(x[i]);
if (Iter::Ranges::disjoint(rs,rx)) {
if (rm != RM_PMI)
GECODE_ME_CHECK(b.zero(home));
return ES_OK;
}
}
// Choose the right bit set implementation
switch (ts.words()) {
case 0U:
GECODE_NEVER; return ES_OK;
case 1U:
return ReCompact<View,TinyBitSet<1U>,CtrlView,rm>::post(home,x,ts,b);
case 2U:
return ReCompact<View,TinyBitSet<2U>,CtrlView,rm>::post(home,x,ts,b);
case 3U:
return ReCompact<View,TinyBitSet<3U>,CtrlView,rm>::post(home,x,ts,b);
case 4U:
return ReCompact<View,TinyBitSet<4U>,CtrlView,rm>::post(home,x,ts,b);
default:
switch (Gecode::Support::u_type(ts.words())) {
case Gecode::Support::IT_CHAR:
return ReCompact<View,BitSet<unsigned char>,CtrlView,rm>
::post(home,x,ts,b);
case Gecode::Support::IT_SHRT:
return ReCompact<View,BitSet<unsigned short int>,CtrlView,rm>
::post(home,x,ts,b);
case Gecode::Support::IT_INT:
return ReCompact<View,BitSet<unsigned int>,CtrlView,rm>
::post(home,x,ts,b);
default: GECODE_NEVER;
}
}
GECODE_NEVER;
return ES_OK;
}
}}}
// STATISTICS: int-prop
Gecode::ActorLink::Space
friend class Space
Definition core.hpp:595
Gecode::ActorLink::Propagator
friend class Propagator
Definition core.hpp:591
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::Advisor::Council
friend class Council
Definition core.hpp:1294
Gecode::Advisors
Class to iterate over advisors of a council.
Definition core.hpp:1266
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Gecode::Int::Extensional::BitSet
Bit-set.
Definition extensional.hh:235
Gecode::Int::Extensional::Compact::CTAdvisor
Advisor for updating current table.
Definition extensional.hh:367
Gecode::Int::Extensional::Compact::CTAdvisor::lst
const Range * lst(void) const
Return lasst range of support data structure.
Definition compact.hpp:99
Gecode::Int::Extensional::Compact::CTAdvisor::_lst
const Range * _lst
Last range of support data structure.
Definition extensional.hh:374
Gecode::Int::Extensional::Compact::CTAdvisor::fst
const Range * fst(void) const
Return first range of support data structure.
Definition compact.hpp:93
Gecode::Int::Extensional::Compact::CTAdvisor::adjust
void adjust(void)
Adjust supports.
Definition compact.hpp:47
Gecode::Int::Extensional::Compact::CTAdvisor::dispose
void dispose(Space &home, Council< CTAdvisor > &c)
Dispose advisor.
Definition compact.hpp:105
Gecode::Int::Extensional::Compact::CTAdvisor::CTAdvisor
CTAdvisor(Space &home, Propagator &p, Council< CTAdvisor > &c, const TupleSet &ts, View x0, int i)
Initialise from parameters.
Definition compact.hpp:80
Gecode::Int::Extensional::Compact::CTAdvisor::_fst
const Range * _fst
First range of support data structure.
Definition extensional.hh:372
Gecode::Int::Extensional::Compact::LostSupports::s
const BitSetData * s
The lost value's support.
Definition extensional.hh:443
Gecode::Int::Extensional::Compact::LostSupports::h
int h
High value.
Definition extensional.hh:441
Gecode::Int::Extensional::Compact::LostSupports::operator()
bool operator()(void) const
Whether iterator is done.
Definition compact.hpp:307
Gecode::Int::Extensional::Compact::LostSupports::supports
const BitSetData * supports(void) const
Provide access to corresponding supports.
Definition compact.hpp:312
Gecode::Int::Extensional::Compact::LostSupports::operator++
void operator++(void)
Move iterator to next value.
Definition compact.hpp:299
Gecode::Int::Extensional::Compact::LostSupports::LostSupports
LostSupports(const Compact< View, pos > &p, CTAdvisor &a, int l, int h)
Initialize iterator for values between l and h.
Definition compact.hpp:288
Gecode::Int::Extensional::Compact::LostSupports::l
int l
Low value.
Definition extensional.hh:439
Gecode::Int::Extensional::Compact::LostSupports::r
const Range * r
Range information.
Definition extensional.hh:435
Gecode::Int::Extensional::Compact::LostSupports::n_words
const unsigned int n_words
Number of words.
Definition extensional.hh:433
Gecode::Int::Extensional::Compact::ValidSupports
Iterator over valid supports.
Definition extensional.hh:397
Gecode::Int::Extensional::Compact::ValidSupports::operator()
bool operator()(void) const
Whether there are still supports left.
Definition compact.hpp:266
Gecode::Int::Extensional::Compact::ValidSupports::supports
const BitSetData * supports(void) const
Return supports.
Definition compact.hpp:271
Gecode::Int::Extensional::Compact::ValidSupports::n
int n
The value.
Definition extensional.hh:410
Gecode::Int::Extensional::Compact::ValidSupports::lst
const Range * lst
The last range.
Definition extensional.hh:408
Gecode::Int::Extensional::Compact::ValidSupports::operator++
void operator++(void)
Move to next supports.
Definition compact.hpp:239
Gecode::Int::Extensional::Compact::ValidSupports::xr
ViewRanges< View > xr
Range iterator.
Definition extensional.hh:404
Gecode::Int::Extensional::Compact::ValidSupports::ValidSupports
ValidSupports(const Compact< View, pos > &p, CTAdvisor &a)
Initialize from initialized propagator.
Definition compact.hpp:209
Gecode::Int::Extensional::Compact::ValidSupports::max
int max
Maximal value.
Definition extensional.hh:402
Gecode::Int::Extensional::Compact::ValidSupports::sr
const Range * sr
Support iterator.
Definition extensional.hh:406
Gecode::Int::Extensional::Compact::ValidSupports::find
void find(void)
Find a new value (only for negative case).
Definition compact.hpp:179
Gecode::Int::Extensional::Compact::ValidSupports::s
const BitSetData * s
The value's support.
Definition extensional.hh:412
Gecode::Int::Extensional::Compact::ValidSupports::n_words
const unsigned int n_words
Number of words.
Definition extensional.hh:400
Gecode::Int::Extensional::Compact::ValidSupports::val
int val(void) const
Return supported value.
Definition compact.hpp:277
Gecode::Int::Extensional::Compact::Compact
Compact(Space &home, Compact &p)
Constructor for cloning p.
Definition compact.hpp:335
Gecode::Int::Extensional::Compact::dispose
size_t dispose(Space &home)
Delete propagator and return its size.
Definition compact.hpp:402
Gecode::Int::Extensional::Compact::ts
TupleSet ts
The tuple set.
Definition extensional.hh:467
Gecode::Int::Extensional::Compact::supports
const BitSetData * supports(CTAdvisor &a, int n)
Return supports for value n.
Definition compact.hpp:148
Gecode::Int::Extensional::Compact::full
bool full(const Table &table) const
Check whether the table covers the whole Cartedion product.
Definition compact.hpp:379
Gecode::Int::Extensional::Compact::setup
void setup(Space &home, Table &table, ViewArray< View > &x)
Setup the actual table.
Definition compact.hpp:350
Gecode::Int::Extensional::Compact::n_words
const unsigned int n_words
Number of words in supports.
Definition extensional.hh:465
Gecode::Int::Extensional::Compact::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition compact.hpp:391
Gecode::Int::Extensional::Compact::all
bool all(void) const
Whether all variables are assigned.
Definition compact.hpp:320
Gecode::Int::Extensional::Compact::range
const Range * range(CTAdvisor &a, int n)
Find range for n.
Definition compact.hpp:116
Gecode::Int::Extensional::Compact::atmostone
bool atmostone(void) const
Whether at most one variable is unassigned.
Definition compact.hpp:326
Gecode::Int::Extensional::Compact::Range
TupleSet::Range Range
Range type for supports.
Definition extensional.hh:365
Gecode::Int::Extensional::Compact::c
Council< CTAdvisor > c
The advisor council.
Definition extensional.hh:469
Gecode::Int::Extensional::NegCompact
Domain consistent negative extensional propagator.
Definition extensional.hh:594
Gecode::Int::Extensional::NegCompact::ValidSupports
Compact< View, false >::ValidSupports ValidSupports
Definition extensional.hh:596
Gecode::Int::Extensional::NegCompact::CTAdvisor
Compact< View, false >::CTAdvisor CTAdvisor
Definition extensional.hh:598
Gecode::Int::Extensional::NegCompact::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition compact.hpp:743
Gecode::Int::Extensional::NegCompact::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition compact.hpp:904
Gecode::Int::Extensional::NegCompact::table
Table table
Current table.
Definition extensional.hh:608
Gecode::Int::Extensional::NegCompact::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition compact.hpp:819
Gecode::Int::Extensional::NegCompact::NegCompact
NegCompact(Space &home, TableProp &p)
Constructor for cloning p.
Definition compact.hpp:736
Gecode::Int::Extensional::NegCompact::dispose
size_t dispose(Space &home)
Delete propagator and return its size.
Definition compact.hpp:806
Gecode::Int::Extensional::NegCompact::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition compact.hpp:813
Gecode::Int::Extensional::NegCompact::post
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts)
Post propagator for views x and table t.
Definition compact.hpp:798
Gecode::Int::Extensional::PosCompact::Status
Status management.
Definition extensional.hh:528
Gecode::Int::Extensional::PosCompact::Status::none
void none(void)
Set status to NONE.
Definition compact.hpp:444
Gecode::Int::Extensional::PosCompact::Status::s
ptrdiff_t s
A tagged pointer for storing the status.
Definition extensional.hh:531
Gecode::Int::Extensional::PosCompact::Status::single
bool single(CTAdvisor &a) const
Check whether status is single and equal to a.
Definition compact.hpp:430
Gecode::Int::Extensional::PosCompact::Status::Status
Status(StatusType t)
Initialize with type t (either NONE or SEVERAL).
Definition compact.hpp:417
Gecode::Int::Extensional::PosCompact::Status::touched
void touched(CTAdvisor &a)
Set status to SINGLE or MULTIPLE depending on a.
Definition compact.hpp:438
Gecode::Int::Extensional::PosCompact::Status::type
StatusType type(void) const
Return status type.
Definition compact.hpp:425
Gecode::Int::Extensional::PosCompact::Status::propagating
void propagating(void)
Set status to PROPAGATING.
Definition compact.hpp:449
Gecode::Int::Extensional::PosCompact
Domain consistent positive extensional propagator.
Definition extensional.hh:504
Gecode::Int::Extensional::PosCompact::dispose
size_t dispose(Space &home)
Delete propagator and return its size.
Definition compact.hpp:531
Gecode::Int::Extensional::PosCompact::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition compact.hpp:467
Gecode::Int::Extensional::PosCompact::ValidSupports
Compact< View, true >::ValidSupports ValidSupports
Definition extensional.hh:506
Gecode::Int::Extensional::PosCompact::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition compact.hpp:615
Gecode::Int::Extensional::PosCompact::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition compact.hpp:547
Gecode::Int::Extensional::PosCompact::table
Table table
Current table.
Definition extensional.hh:551
Gecode::Int::Extensional::PosCompact::CTAdvisor
Compact< View, true >::CTAdvisor CTAdvisor
Definition extensional.hh:508
Gecode::Int::Extensional::PosCompact::status
Status status
Propagator status.
Definition extensional.hh:549
Gecode::Int::Extensional::PosCompact::StatusType
StatusType
Type of status.
Definition extensional.hh:521
Gecode::Int::Extensional::PosCompact::NONE
@ NONE
No view has been touched.
Definition extensional.hh:524
Gecode::Int::Extensional::PosCompact::PROPAGATING
@ PROPAGATING
The propagator is currently running.
Definition extensional.hh:525
Gecode::Int::Extensional::PosCompact::SINGLE
@ SINGLE
A single view has been touched.
Definition extensional.hh:522
Gecode::Int::Extensional::PosCompact::MULTIPLE
@ MULTIPLE
Multiple view have been touched.
Definition extensional.hh:523
Gecode::Int::Extensional::PosCompact::LostSupports
Compact< View, true >::LostSupports LostSupports
Definition extensional.hh:509
Gecode::Int::Extensional::PosCompact::post
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts)
Post propagator for views x and table t.
Definition compact.hpp:522
Gecode::Int::Extensional::PosCompact::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition compact.hpp:538
Gecode::Int::Extensional::PosCompact::PosCompact
PosCompact(Space &home, TableProp &p)
Constructor for cloning p.
Definition compact.hpp:460
Gecode::Int::Extensional::ReCompact
Domain consistent reified extensional propagator.
Definition extensional.hh:636
Gecode::Int::Extensional::ReCompact::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition compact.hpp:1014
Gecode::Int::Extensional::ReCompact::table
Table table
Current table.
Definition extensional.hh:649
Gecode::Int::Extensional::ReCompact::y
ViewArray< View > y
The views (for rewriting).
Definition extensional.hh:653
Gecode::Int::Extensional::ReCompact::CTAdvisor
Compact< View, false >::CTAdvisor CTAdvisor
Definition extensional.hh:640
Gecode::Int::Extensional::ReCompact::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition compact.hpp:1140
Gecode::Int::Extensional::ReCompact::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition compact.hpp:1109
Gecode::Int::Extensional::ReCompact::ReCompact
ReCompact(Space &home, TableProp &p)
Constructor for cloning p.
Definition compact.hpp:1005
Gecode::Int::Extensional::ReCompact::post
static ExecStatus post(Home home, ViewArray< View > &x, const TupleSet &ts, CtrlView b)
Post propagator for views x and table t.
Definition compact.hpp:1077
Gecode::Int::Extensional::ReCompact::b
CtrlView b
Boolean control view.
Definition extensional.hh:651
Gecode::Int::Extensional::ReCompact::ValidSupports
Compact< View, false >::ValidSupports ValidSupports
Definition extensional.hh:638
Gecode::Int::Extensional::ReCompact::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition compact.hpp:1103
Gecode::Int::Extensional::ReCompact::dispose
size_t dispose(Space &home)
Delete propagator and return its size.
Definition compact.hpp:1095
Gecode::Int::Extensional::TinyBitSet
Tiny bit-set.
Definition extensional.hh:302
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Iter::Values::Array
Value iterator for array of integers
Definition values-array.hpp:46
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::quadratic
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
Gecode::PropCost::HI
@ HI
Expensive.
Definition core.hpp:514
Gecode::Propagator::size
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1077
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Advisor
friend class Advisor
Definition core.hpp:1068
Gecode::Propagator::disabled
bool disabled(void) const
Whether propagator is currently disabled.
Definition core.hpp:3476
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::TupleSet::Range::max
int max
Maximum value.
Definition int.hh:2206
Gecode::TupleSet::Range::min
int min
Minimum value.
Definition int.hh:2204
Gecode::TupleSet::Range::supports
const BitSetData * supports(unsigned int n_words, int n) const
Return the supports for value n.
Definition tuple-set.hpp:50
Gecode::TupleSet::Ranges
Iterator over ranges.
Definition int.hh:2359
Gecode::TupleSet
Class represeting a set of tuples.
Definition int.hh:2191
Gecode::TupleSet::tuples
int tuples(void) const
Number of tuples.
Definition tuple-set.hpp:185
Gecode::TupleSet::words
unsigned int words(void) const
Return number of required bit set words.
Definition tuple-set.hpp:189
Gecode::TupleSet::BitSetData
Gecode::Support::BitSetData BitSetData
Import bit set data type.
Definition int.hh:2199
Gecode::View
Gecode::ValSelCommitBase::val
virtual Val val(const Space &home, View x, int i)=0
Return value of view x at position i.
Gecode::ViewAdvisor::ViewAdvisor
ViewAdvisor(Space &home, Propagator &p, Council< A > &c, View x0)
Constructor for creation.
Definition advisor.hpp:66
Gecode::ViewAdvisor::dispose
void dispose(Space &home, Council< A > &c)
Delete advisor.
Definition advisor.hpp:90
Gecode::ViewAdvisor::view
View view(void) const
Access view.
Definition advisor.hpp:79
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1156
Gecode::Space::ES_FIX_DISPOSE
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition core.hpp:3880
Gecode::Space::ES_NOFIX_DISPOSE
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:3887
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::Space::ignore
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
GECODE_REWRITE
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
Gecode::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
Gecode::RM_IMP
@ RM_IMP
Implication for reification.
Definition int.hh:862
Gecode::RM_PMI
@ RM_PMI
Inverse implication for reification.
Definition int.hh:869
Gecode::Int::Extensional
Extensional propagators
Gecode::Int::Extensional::postnegcompact
ExecStatus postnegcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for compact table propagator.
Definition compact.hpp:955
Gecode::Int::Extensional::postposcompact
ExecStatus postposcompact(Home home, ViewArray< View > &x, const TupleSet &ts)
Post function for positive compact table propagator.
Definition compact.hpp:685
Gecode::Int::Extensional::BitSetData
Gecode::Support::BitSetData BitSetData
Import type.
Definition extensional.hh:226
Gecode::Int::Extensional::postrecompact
ExecStatus postrecompact(Home home, ViewArray< View > &x, const TupleSet &ts, CtrlView b)
Post function for compact table propagator.
Definition compact.hpp:1192
Gecode::Int
Finite domain integers.
Gecode::Int::ME_INT_BND
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition var-type.hpp:65
Gecode::Int::PC_BOOL_VAL
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value).
Definition var-type.hpp:126
Gecode::Int::ME_INT_VAL
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:56
Gecode::Int::ME_INT_DOM
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Gecode::Iter::Ranges::disjoint
bool disjoint(I &i, J &j)
Check whether range iterators i and j are disjoint.
Definition ranges-operations.hpp:112
Gecode::Support::u_type
IntType u_type(unsigned int n)
Return type required to represent n.
Definition int-type.hpp:147
Gecode::Support::IT_CHAR
@ IT_CHAR
char integer type
Definition int-type.hpp:40
Gecode::Support::IT_INT
@ IT_INT
integer type
Definition int-type.hpp:42
Gecode::Support::IT_SHRT
@ IT_SHRT
short integer type
Definition int-type.hpp:41
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::post
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition filter.cpp:138
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114