bnd-sup.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
* 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 {
class UnReachable {
public:
int minb;
int maxb;
int eq;
int le;
int gr;
};
template<class Card>
ExecStatus
prop_card(Space& home,
ViewArray<IntView>& x, ViewArray<Card>& k) {
int n = x.size();
int m = k.size();
Region r;
UnReachable* rv = r.alloc<UnReachable>(m);
for(int i = m; i--; )
rv[i].minb=rv[i].maxb=rv[i].le=rv[i].gr=rv[i].eq=0;
for (int i = n; i--; ) {
int min_idx;
if (!lookupValue(k,x[i].min(),min_idx))
return ES_FAILED;
if (x[i].assigned()) {
rv[min_idx].minb++;
rv[min_idx].maxb++;
rv[min_idx].eq++;
} else {
// count the number of variables
// with lower bound k[min_idx].card()
rv[min_idx].minb++;
int max_idx;
if (!lookupValue(k,x[i].max(),max_idx))
return ES_FAILED;
// count the number of variables
// with upper bound k[max_idx].card()
rv[max_idx].maxb++;
}
}
rv[0].le = 0;
int c_min = 0;
for (int i = 1; i < m; i++) {
rv[i].le = c_min + rv[i - 1].maxb;
c_min += rv[i - 1].maxb;
}
rv[m-1].gr = 0;
int c_max = 0;
for (int i = m-1; i--; ) {
rv[i].gr = c_max + rv[i + 1].minb;
c_max += rv[i + 1].minb;
}
for (int i = m; i--; ) {
int reachable = x.size() - rv[i].le - rv[i].gr;
if (!k[i].assigned()) {
GECODE_ME_CHECK(k[i].lq(home, reachable));
GECODE_ME_CHECK(k[i].gq(home, rv[i].eq));
} else {
// check validity of the cardinality value
if ((rv[i].eq > k[i].max()) || (k[i].max() > reachable))
return ES_FAILED;
}
}
return ES_OK;
}
template<class Card>
forceinline bool
card_consistent(ViewArray<IntView>& x, ViewArray<Card>& k) {
int smin = 0;
int smax = 0;
for (int i = k.size(); i--; ) {
smax += k[i].max();
smin += k[i].min();
}
// Consistent if number of variables within cardinality bounds
return (smin <= x.size()) && (x.size() <= smax);
}
class Rank {
public:
int min;
int max;
};
template<class View>
class MaxInc {
protected:
ViewArray<View> x;
public:
MaxInc(const ViewArray<View>& x0) : x(x0) {}
forceinline bool
operator ()(const int i, const int j) {
return x[i].max() < x[j].max();
}
};
template<class View>
class MinInc {
protected:
ViewArray<View> x;
public:
MinInc(const ViewArray<View>& x0) : x(x0) {}
forceinline bool
operator ()(const int i, const int j) {
return x[i].min() < x[j].min();
}
};
template<class Card>
class MinIdx {
public:
forceinline bool
operator ()(const Card& x, const Card& y) {
return x.card() < y.card();
}
};
template<class Card>
class PartialSum {
private:
int* sum;
int size;
public:
int firstValue, lastValue;
PartialSum(void);
void init(Space& home, ViewArray<Card>& k, bool up);
void reinit(void);
operator bool(void) const;
int sumup(int from, int to) const;
int minValue(void) const;
int maxValue(void) const;
int skipNonNullElementsRight(int v) const;
int skipNonNullElementsLeft(int v) const;
bool check_update_min(ViewArray<Card>& k);
bool check_update_max(ViewArray<Card>& k);
};
template<class Card>
forceinline
PartialSum<Card>::PartialSum(void) : sum(NULL), size(-1) {}
template<class Card>
forceinline
PartialSum<Card>::operator bool(void) const {
return size != -1;
}
template<class Card>
inline void
PartialSum<Card>::init(Space& home, ViewArray<Card>& elements, bool up) {
int i = 0;
int j = 0;
// Determine number of holes in the index set
int holes = 0;
for (i = 1; i < elements.size(); i++) {
if (elements[i].card() != elements[i-1].card() + 1)
holes += elements[i].card()-elements[i-1].card()-1;
}
// we add three elements at the beginning and two at the end
size = elements.size() + holes + 5;
// memory allocation
if (sum == NULL) {
sum = home.alloc<int>(2*size);
}
int* ds = &sum[size];
int first = elements[0].card();
firstValue = first - 3;
lastValue = first + elements.size() + holes + 1;
// the first three elements
for (i = 3; i--; )
sum[i] = i;
/*
* copy the bounds into sum, filling up holes with zeroes
*/
int prevCard = elements[0].card()-1;
i = 0;
for (j = 2; j < elements.size() + holes + 2; j++) {
if (elements[i].card() != prevCard + 1) {
sum[j + 1] = sum[j];
} else if (up) {
sum[j + 1] = sum[j] + elements[i].max();
i++;
} else {
sum[j + 1] = sum[j] + elements[i].min();
i++;
}
prevCard++;
}
sum[j + 1] = sum[j] + 1;
sum[j + 2] = sum[j + 1] + 1;
// Compute distances, eliminating zeroes
i = elements.size() + holes + 3;
j = i + 1;
for ( ; i > 0; ) {
while(sum[i] == sum[i - 1]) {
ds[i] = j;
i--;
}
ds[j] = i;
i--;
j = ds[j];
}
ds[j] = 0;
ds[0] = 0;
}
template<class Card>
forceinline void
PartialSum<Card>::reinit(void) {
size = -1;
}
template<class Card>
forceinline int
PartialSum<Card>::sumup(int from, int to) const {
if (from <= to) {
return sum[to - firstValue] - sum[from - firstValue - 1];
} else {
assert(to - firstValue - 1 >= 0);
assert(to - firstValue - 1 < size);
assert(from - firstValue >= 0);
assert(from - firstValue < size);
return sum[to - firstValue - 1] - sum[from - firstValue];
}
}
template<class Card>
forceinline int
PartialSum<Card>::minValue(void) const {
return firstValue + 3;
}
template<class Card>
forceinline int
PartialSum<Card>::maxValue(void) const {
return lastValue - 2;
}
template<class Card>
forceinline int
PartialSum<Card>::skipNonNullElementsRight(int value) const {
value -= firstValue;
int* ds = &sum[size];
return (ds[value] < value ? value : ds[value]) + firstValue;
}
template<class Card>
forceinline int
PartialSum<Card>::skipNonNullElementsLeft(int value) const {
value -= firstValue;
int* ds = &sum[size];
return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
}
template<class Card>
inline bool
PartialSum<Card>::check_update_max(ViewArray<Card>& k) {
int j = 0;
for (int i = 3; i < size - 2; i++) {
int max = 0;
if (k[j].card() == i+firstValue)
max = k[j++].max();
if ((sum[i] - sum[i - 1]) != max)
return true;
}
return false;
}
template<class Card>
inline bool
PartialSum<Card>::check_update_min(ViewArray<Card>& k) {
int j = 0;
for (int i = 3; i < size - 2; i++) {
int min = 0;
if (k[j].card() == i+firstValue)
min = k[j++].min();
if ((sum[i] - sum[i - 1]) != min)
return true;
}
return false;
}
class HallInfo {
public:
int bounds;
int t;
int d;
int h;
int s;
int ps;
int newBound;
};
forceinline void
pathset_ps(HallInfo hall[], int start, int end, int to) {
int k, l;
for (l=start; (k=l) != end; hall[k].ps=to) {
l = hall[k].ps;
}
}
forceinline void
pathset_s(HallInfo hall[], int start, int end, int to) {
int k, l;
for (l=start; (k=l) != end; hall[k].s=to) {
l = hall[k].s;
}
}
forceinline void
pathset_t(HallInfo hall[], int start, int end, int to) {
int k, l;
for (l=start; (k=l) != end; hall[k].t=to) {
l = hall[k].t;
}
}
forceinline void
pathset_h(HallInfo hall[], int start, int end, int to) {
int k, l;
for (l=start; (k=l) != end; hall[k].h=to) {
l = hall[k].h;
assert(l != k);
}
}
forceinline int
pathmin_h(const HallInfo hall[], int i) {
while (hall[i].h < i)
i = hall[i].h;
return i;
}
forceinline int
pathmin_t(const HallInfo hall[], int i) {
while (hall[i].t < i)
i = hall[i].t;
return i;
}
forceinline int
pathmax_h(const HallInfo hall[], int i) {
while (hall[i].h > i)
i = hall[i].h;
return i;
}
forceinline int
pathmax_t(const HallInfo hall[], int i) {
while (hall[i].t > i) {
i = hall[i].t;
}
return i;
}
forceinline int
pathmax_s(const HallInfo hall[], int i) {
while (hall[i].s > i)
i = hall[i].s;
return i;
}
forceinline int
pathmax_ps(const HallInfo hall[], int i) {
while (hall[i].ps > i)
i = hall[i].ps;
return i;
}
}}}
// STATISTICS: int-prop
Gecode::Int::GCC::HallInfo
Container class provding information about the Hall structure of the problem variables.
Definition bnd-sup.hpp:456
Gecode::Int::GCC::HallInfo::t
int t
Critical capacity pointer t represents a predecessor function where denotes the predecessor of i in ...
Definition bnd-sup.hpp:465
Gecode::Int::GCC::HallInfo::newBound
int newBound
Bound update.
Definition bnd-sup.hpp:493
Gecode::Int::GCC::HallInfo::h
int h
Hall set pointer.
Definition bnd-sup.hpp:482
Gecode::Int::GCC::HallInfo::bounds
int bounds
Represents the union of all lower and upper domain bounds.
Definition bnd-sup.hpp:459
Gecode::Int::GCC::HallInfo::s
int s
Stable Set pointer.
Definition bnd-sup.hpp:484
Gecode::Int::GCC::HallInfo::ps
int ps
Potentially Stable Set pointer.
Definition bnd-sup.hpp:486
Gecode::Int::GCC::HallInfo::d
int d
Difference between critical capacities.
Definition bnd-sup.hpp:473
Gecode::Int::GCC::MaxInc::x
ViewArray< View > x
View array for comparison.
Definition bnd-sup.hpp:179
Gecode::Int::GCC::MaxInc::MaxInc
MaxInc(const ViewArray< View > &x0)
Constructor.
Definition bnd-sup.hpp:182
Gecode::Int::GCC::MaxInc::operator()
bool operator()(const int i, const int j)
Order.
Definition bnd-sup.hpp:185
Gecode::Int::GCC::MinIdx
Compares two cardinality views according to the index.
Definition bnd-sup.hpp:221
Gecode::Int::GCC::MinIdx::operator()
bool operator()(const Card &x, const Card &y)
Comparison.
Definition bnd-sup.hpp:225
Gecode::Int::GCC::MinInc::MinInc
MinInc(const ViewArray< View > &x0)
Constructor.
Definition bnd-sup.hpp:205
Gecode::Int::GCC::MinInc::x
ViewArray< View > x
View array for comparison.
Definition bnd-sup.hpp:202
Gecode::Int::GCC::MinInc::operator()
bool operator()(const int i, const int j)
Comparison.
Definition bnd-sup.hpp:208
Gecode::Int::GCC::PartialSum::lastValue
int lastValue
Definition bnd-sup.hpp:245
Gecode::Int::GCC::PartialSum::firstValue
int firstValue
Sentinels indicating whether an end of sum is reached.
Definition bnd-sup.hpp:245
Gecode::Int::GCC::PartialSum::skipNonNullElementsLeft
int skipNonNullElementsLeft(int v) const
Skip neigbouring array entries if their values do not differ.
Definition bnd-sup.hpp:410
Gecode::Int::GCC::PartialSum::maxValue
int maxValue(void) const
Return largest bound of variables.
Definition bnd-sup.hpp:396
Gecode::Int::GCC::PartialSum::reinit
void reinit(void)
Mark datstructure as requiring reinitialization.
Definition bnd-sup.hpp:370
Gecode::Int::GCC::PartialSum::check_update_max
bool check_update_max(ViewArray< Card > &k)
Check whether the values in the partial sum structure containting the upper cardinality bounds differ...
Definition bnd-sup.hpp:418
Gecode::Int::GCC::PartialSum::minValue
int minValue(void) const
Return smallest bound of variables.
Definition bnd-sup.hpp:391
Gecode::Int::GCC::PartialSum::PartialSum
PartialSum(void)
Constructor.
Definition bnd-sup.hpp:294
Gecode::Int::GCC::PartialSum::check_update_min
bool check_update_min(ViewArray< Card > &k)
Check whether the values in the partial sum structure containting the lower cardinality bounds differ...
Definition bnd-sup.hpp:432
Gecode::Int::GCC::PartialSum::init
void init(Space &home, ViewArray< Card > &k, bool up)
Initialization.
Definition bnd-sup.hpp:303
Gecode::Int::GCC::PartialSum::sumup
int sumup(int from, int to) const
Compute the maximum capacity of an interval.
Definition bnd-sup.hpp:377
Gecode::Int::GCC::PartialSum::skipNonNullElementsRight
int skipNonNullElementsRight(int v) const
Skip neigbouring array entries if their values do not differ.
Definition bnd-sup.hpp:403
Gecode::Int::GCC::Rank
Maps domain bounds to their position in hall[].bounds.
Definition bnd-sup.hpp:154
Gecode::Int::GCC::Rank::min
int min
Definition bnd-sup.hpp:160
Gecode::Int::GCC::Rank::max
int max
Definition bnd-sup.hpp:165
Gecode::Int::GCC::UnReachable
Class for computing unreachable values in the value GCC propagator.
Definition bnd-sup.hpp:53
Gecode::Int::GCC::UnReachable::maxb
int maxb
Number of variables with upper bound.
Definition bnd-sup.hpp:58
Gecode::Int::GCC::UnReachable::gr
int gr
Number of greater variables.
Definition bnd-sup.hpp:64
Gecode::Int::GCC::UnReachable::minb
int minb
Number of variables with lower bound.
Definition bnd-sup.hpp:56
Gecode::Int::GCC::UnReachable::eq
int eq
Number of equal variables.
Definition bnd-sup.hpp:60
Gecode::Int::GCC::UnReachable::le
int le
Number of smaller variables.
Definition bnd-sup.hpp:62
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
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::GCC::card_consistent
bool card_consistent(ViewArray< IntView > &x, ViewArray< Card > &k)
Consistency check, whether the cardinality values are feasible.
Definition bnd-sup.hpp:139
Gecode::Int::GCC::prop_card
ExecStatus prop_card(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Bounds consistency check for cardinality variables.
Definition bnd-sup.hpp:74
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::Int::GCC
Global cardinality propagators (Counting).
Gecode::Int::GCC::pathmin_h
int pathmin_h(const HallInfo hall[], int i)
Path minimum for hall pointer structure.
Definition bnd-sup.hpp:549
Gecode::Int::GCC::pathmax_t
int pathmax_t(const HallInfo hall[], int i)
Path maximum for capacity pointer structure.
Definition bnd-sup.hpp:579
Gecode::Int::GCC::pathset_ps
void pathset_ps(HallInfo hall[], int start, int end, int to)
Path compression for potentially stable set structure.
Definition bnd-sup.hpp:507
Gecode::Int::GCC::pathmax_s
int pathmax_s(const HallInfo hall[], int i)
Path maximum for stable set pointer structure.
Definition bnd-sup.hpp:587
Gecode::Int::GCC::pathset_t
void pathset_t(HallInfo hall[], int start, int end, int to)
Path compression for capacity pointer structure.
Definition bnd-sup.hpp:523
Gecode::Int::GCC::pathmin_t
int pathmin_t(const HallInfo hall[], int i)
Path minimum for capacity pointer structure.
Definition bnd-sup.hpp:556
Gecode::Int::GCC::pathset_h
void pathset_h(HallInfo hall[], int start, int end, int to)
Path compression for hall pointer structure.
Definition bnd-sup.hpp:531
Gecode::Int::GCC::pathset_s
void pathset_s(HallInfo hall[], int start, int end, int to)
Path compression for stable set structure.
Definition bnd-sup.hpp:515
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::pathmax_h
int pathmax_h(const HallInfo hall[], int i)
Path maximum for hall pointer structure.
Definition bnd-sup.hpp:572
Gecode::Int::GCC::pathmax_ps
int pathmax_ps(const HallInfo hall[], int i)
Path maximum for potentially stable set pointer structure.
Definition bnd-sup.hpp:594
Gecode::Int
Finite domain integers.
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
forceinline
#define forceinline
Definition config.hpp:187