val.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Patrick Pekczynski, 2005
* Christian Schulte, 2009
* Guido Tack, 2009
*
* 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.
*/
namespace Gecode { namespace Int { namespace GCC {
template<class Card>
forceinline
Val<Card>::Val(Home home,
ViewArray<IntView>& x0, ViewArray<Card>& k0)
: Propagator(home), x(x0), k(k0){
x.subscribe(home, *this, PC_INT_VAL);
k.subscribe(home, *this, PC_INT_VAL);
}
template<class Card>
forceinline
Val<Card>::Val(Space& home, Val<Card>& p)
: Propagator(home,p) {
x.update(home, p.x);
k.update(home, p.k);
}
template<class Card>
forceinline size_t
Val<Card>::dispose(Space& home) {
x.cancel(home,*this, PC_INT_VAL);
k.cancel(home,*this, PC_INT_VAL);
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class Card>
Actor*
Val<Card>::copy(Space& home) {
return new (home) Val<Card>(home,*this);
}
template<class Card>
PropCost
Val<Card>::cost(const Space&, const ModEventDelta&) const {
/*
* Complexity depends on the time needed for value lookup in \a k
* which is O(n log n).
*/
return PropCost::linear(PropCost::HI,x.size());
}
template<class Card>
void
Val<Card>::reschedule(Space& home) {
x.reschedule(home, *this, PC_INT_VAL);
k.reschedule(home, *this, PC_INT_VAL);
}
template<class Card>
ExecStatus
prop_val(Space& home, Propagator& p,
ViewArray<IntView>& x, ViewArray<Card>& k) {
assert(x.size() > 0);
Region r;
// count[i] denotes how often value k[i].card() occurs in x
int* count = r.alloc<int>(k.size());
// initialization
int sum_min = 0;
int removed = 0;
for (int i=0; i<k.size(); i++) {
removed += k[i].counter();
sum_min += k[i].min();
count[i] = 0;
}
// less than or equal than the total number of free variables
// to satisfy the required occurences
for (int i=0; i<k.size(); i++)
GECODE_ME_CHECK(k[i].lq(home, x.size()+removed-(sum_min - k[i].min())));
// number of unassigned views
int non = x.size();
for (int i=0; i<x.size(); i++)
if (x[i].assigned()) {
int idx;
if (!lookupValue(k,x[i].val(),idx)) {
return ES_FAILED;
}
count[idx]++;
non--;
}
// check for subsumption
if (non == 0) {
for (int i=0; i<k.size(); i++)
GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
return home.ES_SUBSUMED(p);
}
// total number of unsatisfied miminum occurences
int req = 0;
// number of values whose min requirements are not yet met
int n_r = 0;
// if only one value is unsatisified single holds the index of that value
int single = -1;
// total number of assigned views wrt. the original probem size
int t_noa = 0;
for (int i = k.size(); i--; ) {
int ci = count[i] + k[i].counter();
t_noa += ci;
if (ci == 0) { // this works
req += k[i].min();
n_r++;
single = i;
}
// number of unassigned views cannot satisfy
// the required minimum occurence
if (req > non) {
return ES_FAILED;
}
}
// if only one unsatisfied occurences is left
if ((req == non) && (n_r == 1)) {
// This works as the x are not shared!
for (int i = x.size(); i--; ) {
// try to assign it
if (!x[i].assigned()) {
GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
assert((single >= 0) && (single < k.size()));
count[single]++;
}
}
assert((single >= 0) && (single < k.size()));
for (int i = k.size(); i--; )
GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
return home.ES_SUBSUMED(p);
}
// Bitset for indexes that can be removed
Support::BitSet<Region> rem(r,static_cast<unsigned int>(k.size()));
for (int i = k.size(); i--; ) {
int ci = count[i] + k[i].counter();
if (ci == k[i].max()) {
assert(!rem.get(i));
rem.set(static_cast<unsigned int>(i));
k[i].counter(ci);
// the solution contains ci occurences of value k[i].card();
GECODE_ME_CHECK(k[i].eq(home, ci));
} else {
if (ci > k[i].max()) {
return ES_FAILED;
}
// in case of variable cardinalities
if (Card::propagate) {
GECODE_ME_CHECK(k[i].gq(home, ci));
int occupied = t_noa - ci;
GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
}
}
// reset counter
count[i] = 0;
}
// reduce the problem size
{
int n_x = x.size();
for (int i = n_x; i--; ) {
if (x[i].assigned()) {
int idx;
if (!lookupValue(k,x[i].val(),idx)) {
return ES_FAILED;
}
if (rem.get(static_cast<unsigned int>(idx)))
x[i]=x[--n_x];
}
}
x.size(n_x);
}
// remove values
{
// Values to prune
int* pr = r.alloc<int>(k.size());
// Number of values to prune
int n_pr = 0;
for (Iter::Values::BitSet<Support::BitSet<Region> > i(rem); i(); ++i)
pr[n_pr++] = k[i.val()].card();
Support::quicksort(pr,n_pr);
for (int i = x.size(); i--;) {
Iter::Values::Array pi(pr,n_pr);
GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
}
}
{
bool all_assigned = true;
for (int i = x.size(); i--; ) {
if (x[i].assigned()) {
int idx;
if (!lookupValue(k,x[i].val(),idx)) {
return ES_FAILED;
}
count[idx]++;
} else {
all_assigned = false;
}
}
if (all_assigned) {
for (int i = k.size(); i--; )
GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
return home.ES_SUBSUMED(p);
}
}
if (Card::propagate) {
// check again consistency of cardinalities
int reqmin = 0;
int allmax = 0;
for (int i = k.size(); i--; ) {
if (k[i].counter() > k[i].max()) {
return ES_FAILED;
}
allmax += k[i].max() - k[i].counter();
if (k[i].counter() < k[i].min())
reqmin += k[i].min() - k[i].counter();
GECODE_ME_CHECK((k[i].lq(home, x.size()+k[i].counter())));
}
if ((x.size() < reqmin) || (allmax < x.size())) {
return ES_FAILED;
}
}
return ES_NOFIX;
}
template<class Card>
ExecStatus
Val<Card>::propagate(Space& home, const ModEventDelta&) {
return prop_val<Card>(home, *this, x, k);
}
template<class Card>
ExecStatus
Val<Card>::post(Home home,
ViewArray<IntView>& x, ViewArray<Card>& k) {
GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
if (isDistinct<Card>(x,k))
return Distinct::Val<IntView>::post(home,x);
(void) new (home) Val<Card>(home,x,k);
return ES_OK;
}
}}}
// STATISTICS: int-prop
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::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::Distinct::Val::post
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition val.hpp:185
Gecode::Int::GCC::Val::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition val.hpp:85
Gecode::Int::GCC::Val::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion returning high linear.
Definition val.hpp:75
Gecode::Int::GCC::Val::post
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition val.hpp:287
Gecode::Int::GCC::Val::k
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition gcc.hh:68
Gecode::Int::GCC::Val::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition val.hpp:69
Gecode::Int::GCC::Val::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition val.hpp:281
Gecode::Int::GCC::Val::x
ViewArray< IntView > x
Views on which to perform value-propagation.
Definition gcc.hh:66
Gecode::Int::GCC::Val::dispose
virtual size_t dispose(Space &home)
Destructor.
Definition val.hpp:60
Gecode::Int::GCC::Val::Val
Val(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Constructor for posting.
Definition val.hpp:43
Gecode::Iter::Values::Array
Value iterator for array of integers
Definition values-array.hpp:46
Gecode::Iter::Values::BitSet
Value iterator for values in a bitset.
Definition values-bitset.hpp:42
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::linear
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Gecode::PropCost::HI
@ HI
Expensive.
Definition core.hpp:514
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::BitSetBase::get
bool get(unsigned int i) const
Access value at bit i.
Definition bitset-base.hpp:590
Gecode::Support::BitSetBase::set
void set(unsigned int i)
Set bit i.
Definition bitset-base.hpp:595
Gecode::Support::BitSet
Simple bitsets.
Definition bitset.hpp:45
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
pi
const int * pi[]
Definition photo.cpp:14262
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
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_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Gecode::Int::GCC
Global cardinality propagators (Counting).
Gecode::Int::GCC::isDistinct
bool isDistinct(ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
Definition post.hpp:138
Gecode::Int::GCC::prop_val
ExecStatus prop_val(Space &home, Propagator &p, ViewArray< IntView > &x, ViewArray< Card > &k)
Definition val.hpp:92
Gecode::Int::GCC::lookupValue
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition view.hpp:45
Gecode::Int::GCC::postSideConstraints
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
Definition post.hpp:60
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_VAL
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value).
Definition var-type.hpp:82
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
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
forceinline
#define forceinline
Definition config.hpp:187