post.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, 2004/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.
*
*/
#include <gecode/int/linear.hh>
#include <gecode/int/distinct.hh>
namespace Gecode { namespace Int { namespace GCC {
template<class Card>
class CardLess : public Support::Less<Card> {
public:
bool operator ()(const Card& x, const Card& y) {
return x.card() < y.card();
}
};
template<class Card>
ExecStatus
postSideConstraints(Home home, ViewArray<IntView>& x, ViewArray<Card>& k) {
CardLess<Card> cl;
Support::quicksort(&k[0], k.size(), cl);
Region r;
{
int smin = 0;
int smax = 0;
for (int i = k.size(); i--; ) {
GECODE_ME_CHECK((k[i].gq(home, 0)));
GECODE_ME_CHECK((k[i].lq(home, x.size())));
smin += k[i].min();
smax += k[i].max();
}
// not enough variables to satisfy min req
if ((x.size() < smin) || (smax < x.size()))
return ES_FAILED;
}
// Remove all values from the x that are not in v
{
int* v = r.alloc<int>(k.size());
for (int i=k.size(); i--;)
v[i]=k[i].card();
Support::quicksort(v,k.size());
for (int i=x.size(); i--; ) {
Iter::Values::Array iv(v,k.size());
GECODE_ME_CHECK(x[i].inter_v(home, iv, false));
}
}
// Remove all values with 0 max occurrence
// and remove corresponding occurrence variables from k
{
// The number of zeroes
int n_z = 0;
for (int i=k.size(); i--;)
if (k[i].max() == 0)
n_z++;
if (n_z > 0) {
int* z = r.alloc<int>(n_z);
n_z = 0;
int n_k = 0;
for (int i=0; i<k.size(); i++)
if (k[i].max() == 0) {
z[n_z++] = k[i].card();
} else {
k[n_k++] = k[i];
}
k.size(n_k);
Support::quicksort(z,n_z);
for (int i=x.size(); i--;) {
Iter::Values::Array zi(z,n_z);
GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
}
}
}
if (Card::propagate) {
Linear::Term<IntView>* t = r.alloc<Linear::Term<IntView> >(k.size());
for (int i = k.size(); i--; ) {
t[i].a=1; t[i].x=k[i].base();
}
Linear::post(home,t,k.size(),IRT_EQ,x.size(),IPL_BND);
}
return ES_OK;
}
template<class Card>
inline bool
isDistinct(ViewArray<IntView>& x, ViewArray<Card>& k) {
if (Card::propagate) {
Region r;
ViewRanges<IntView>* xrange = r.alloc<ViewRanges<IntView> >(x.size());
for (int i = x.size(); i--; ){
ViewRanges<IntView> iter(x[i]);
xrange[i] = iter;
}
Iter::Ranges::NaryUnion drl(r, &xrange[0], x.size());
if (static_cast<unsigned int>(k.size()) == Iter::Ranges::size(drl)) {
for (int i=k.size(); i--;)
if (k[i].min() != 1 || k[i].max() != 1)
return false;
return true;
} else {
return false;
}
} else {
for (int i=k.size(); i--;)
if (k[i].min() != 0 || k[i].max() != 1)
return false;
return true;
}
}
}}}
// STATISTICS: int-prop
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::GCC::CardLess
Sort by increasing cardinality
Definition post.hpp:47
Gecode::Int::GCC::CardLess::operator()
bool operator()(const Card &x, const Card &y)
Definition post.hpp:49
Gecode::Int::Linear::Term
Class for describing linear term .
Definition linear.hh:1336
Gecode::Int::Linear::Term::x
View x
View.
Definition linear.hh:1341
Gecode::Int::Linear::Term::a
int a
Coefficient.
Definition linear.hh:1339
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Iter::Ranges::NaryUnion
Range iterator for union of iterators.
Definition ranges-union.hpp:74
Gecode::Iter::Values::Array
Value iterator for array of integers
Definition values-array.hpp:46
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Support::Less
Comparison class for sorting using <.
Definition sort.hpp:161
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::Int::Linear::post
void post(Home home, Term< IntView > *t, int n, IntRelType irt, int c, IntPropLevel=IPL_DEF)
Post propagator for linear constraint over integers.
Definition int-post.cpp:219
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IPL_BND
@ IPL_BND
Bounds propagation.
Definition int.hh:978
distinct.hh
linear.hh
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::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::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition ranges-operations.hpp:74
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
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::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49