sortsup.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>
*
* Copyright:
* Patrick Pekczynski, 2004
*
* 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 Sorted {
class Rank {
public:
int min;
int max;
};
class SccComponent {
public:
int leftmost;
int left;
int right;
int rightmost;
};
template<class View, bool Perm>
inline bool
check_subsumption(ViewArray<View>& x, ViewArray<View>& y, ViewArray<View>& z,
bool& subsumed, int& dropfst) {
dropfst = 0;
subsumed = true;
int xs = x.size();
for (int i = 0; i < xs ; i++) {
if (Perm) {
subsumed &= (x[i].assigned() &&
z[i].assigned() &&
y[z[i].val()].assigned());
if (subsumed) {
if (x[i].val() != y[z[i].val()].val()) {
return false;
} else {
if (z[i].val() == i) {
dropfst++;
}
}
}
} else {
subsumed &= (x[i].assigned() && y[i].assigned());
if (subsumed) {
if (x[i].val() != y[i].val()) {
return false;
} else {
dropfst++;
}
}
}
}
return true;
}
class OfflineMinItem {
public:
int root;
int parent;
int rank;
int name;
int iset;
int succ;
int pred;
};
class OfflineMin {
private:
OfflineMinItem* sequence;
int* vertices;
int n;
public:
OfflineMin(void);
OfflineMin(OfflineMinItem[], int[], int);
int find(int x);
int find_pc(int x);
void unite(int a, int b, int c);
void makeset(void);
int size(void);
OfflineMinItem& operator [](int);
};
OfflineMin::OfflineMin(void){
n = 0;
sequence = NULL;
vertices = NULL;
}
OfflineMin::OfflineMin(OfflineMinItem s[], int v[], int size){
n = size;
sequence = &s[0];
vertices = &v[0];
}
forceinline int
OfflineMin::find(int x) {
while (sequence[x].parent != x) {
x = sequence[x].parent;
}
// x is now the root of the tree
// return the set, x belongs to
return sequence[x].name;
}
forceinline int
OfflineMin::find_pc(int x){
int vsize = 0;
while (sequence[x].parent != x) {
vertices[x] = x;
x = sequence[x].parent;
}
// x is now the root of the tree
for (int i=0; i<vsize; i++)
sequence[vertices[i]].parent = x;
// return the set, x belongs to
return sequence[x].name;
}
forceinline void
OfflineMin::unite(int a, int b, int c){
// c is the union of a and b
int ra = sequence[a].root;
int rb = sequence[b].root;
int large = rb;
int small = ra;
if (sequence[ra].rank > sequence[rb].rank) {
large = ra;
small = rb;
}
sequence[small].parent = large;
sequence[large].rank += sequence[small].rank;
sequence[large].name = c;
sequence[c].root = large;
}
forceinline void
OfflineMin::makeset(void){
for(int i = n; i--; ){
OfflineMinItem& cur = sequence[i];
cur.rank = 0; // initially each set is empty
cur.name = i; // it has its own name
cur.root = i; // it is the root node
cur.parent = i; // it is its own parent
cur.pred = i - 1;
cur.succ = i + 1;
cur.iset = -5;
}
}
forceinline int
OfflineMin::size(void){
return n;
}
forceinline OfflineMinItem&
OfflineMin::operator [](int i){
return sequence[i];
}
template<class View>
class TupleMaxInc {
protected:
ViewArray<View> x;
public:
TupleMaxInc(const ViewArray<View>& x0) : x(x0) {}
bool operator ()(const int i, const int j) {
if (x[i].max() == x[j].max()) {
return x[i].min() < x[j].min();
} else {
return x[i].max() < x[j].max();
}
}
};
template<class View>
class TupleMaxIncExt {
protected:
ViewArray<View> x;
ViewArray<View> z;
public:
TupleMaxIncExt(const ViewArray<View>& x0,
const ViewArray<View>& z0) : x(x0), z(z0) {}
bool operator ()(const int i, const int j) {
if (x[i].max() == x[j].max()) {
if (x[i].min() == x[j].min()) {
if (z[i].max() == z[j].max()) {
return z[i].min() < z[j].min();
} else {
return z[i].max() < z[j].max();
}
} else {
return x[i].min() < x[j].min();
}
} else {
return x[i].max() < x[j].max();
}
}
};
template<class View>
class TupleMinInc {
public:
bool operator ()(const View& x, const View& y) {
if (x.min() == y.min()) {
return x.max() < y.max();
} else {
return x.min() < y.min();
}
}
};
template<class View>
class ViewPair {
public:
View x;
View z;
};
template<class View>
class TupleMinIncExt {
public:
bool operator ()(const ViewPair<View>& x, const ViewPair<View>& y) {
if (x.x.min() == y.x.min()) {
if (x.x.max() == y.x.max()) {
if (x.z.min() == y.z.min()) {
return x.z.max() < y.z.max();
} else {
return x.z.min() < y.z.min();
}
} else {
return x.x.max() < y.x.max();
}
} else {
return x.x.min() < y.x.min();
}
}
};
template<class View, bool Perm>
inline bool
array_assigned(Space& home,
ViewArray<View>& x,
ViewArray<View>& y,
ViewArray<View>& z,
bool& subsumed,
bool& match_fixed,
bool&,
bool& noperm_bc) {
bool x_complete = true;
bool y_complete = true;
bool z_complete = true;
for (int i=0; i<y.size(); i++) {
x_complete &= x[i].assigned();
y_complete &= y[i].assigned();
if (Perm) {
z_complete &= z[i].assigned();
}
}
if (x_complete) {
for (int i=0; i<x.size(); i++) {
ModEvent me = y[i].eq(home, x[i].val());
if (me_failed(me)) {
return false;
}
}
if (Perm) {
subsumed = false;
} else {
subsumed = true;
}
}
if (y_complete) {
bool y_equality = true;
for (int i=1; i<y.size(); i++) {
y_equality &= (y[i-1].val() == y[i].val());
}
if (y_equality) {
for (int i=0; i<x.size(); i++) {
ModEvent me = x[i].eq(home, y[i].val());
if (me_failed(me)) {
return false;
}
}
if (Perm) {
subsumed = false;
} else {
subsumed = true;
}
noperm_bc = true;
}
}
if (Perm) {
if (z_complete) {
if (x_complete) {
for (int i=0; i<x.size(); i++) {
ModEvent me = y[z[i].val()].eq(home, x[i].val());
if (me_failed(me)) {
return false;
}
}
subsumed = true;
return subsumed;
}
if (y_complete) {
for (int i=0; i<x.size(); i++) {
ModEvent me = x[i].eq(home, y[z[i].val()].val());
if (me_failed(me)) {
return false;
}
}
subsumed = true;
return subsumed;
}
// validate the permutation
int sum = 0;
for (int i=0; i<x.size(); i++) {
int pi = z[i].val();
if (x[i].max() < y[pi].min() ||
x[i].min() > y[pi].max()) {
return false;
}
sum += pi;
}
int n = x.size();
int gauss = ( (n * (n + 1)) / 2);
// if the sum over all assigned permutation variables is not
// equal to the gaussian sum - n they are not distinct, hence invalid
if (sum != gauss - n) {
return false;
}
match_fixed = true;
}
}
return true;
}
template<class View>
forceinline bool
channel(Space& home, ViewArray<View>& x, ViewArray<View>& y,
ViewArray<View>& z, bool& nofix) {
int n = x.size();
for (int i=0; i<n; i++) {
if (z[i].assigned()) {
int v = z[i].val();
if (x[i].assigned()) {
// channel equality from x to y
ModEvent me = y[v].eq(home, x[i].val());
if (me_failed(me))
return false;
nofix |= me_modified(me);
} else {
if (y[v].assigned()) {
// channel equality from y to x
ModEvent me = x[i].eq(home, y[v].val());
if (me_failed(me))
return false;
nofix |= me_modified(me);
} else {
// constrain upper bound
ModEvent me = x[i].lq(home, y[v].max());
if (me_failed(me))
return false;
nofix |= me_modified(me);
// constrain lower bound
me = x[i].gq(home, y[v].min());
if (me_failed(me))
return false;
nofix |= me_modified(me);
// constrain the sorted variable
// constrain upper bound
me = y[v].lq(home, x[i].max());
if (me_failed(me))
return false;
nofix |= me_modified(me);
// constrain lower bound
me = y[v].gq(home, x[i].min());
if (me_failed(me))
return false;
nofix |= me_modified(me);
}
}
} else {
// if the permutation variable is undetermined
int l = z[i].min();
int r = z[i].max();
// upper bound
ModEvent me = x[i].lq(home, y[r].max());
if (me_failed(me))
return false;
nofix |= me_modified(me);
// lower bound
me = x[i].gq(home, y[l].min());
if (me_failed(me))
return false;
nofix |= me_modified(me);
}
}
return true;
}
}}}
// STATISTICS: int-prop
Gecode::Int::Sorted::OfflineMinItem
Item used to construct the OfflineMin sequence.
Definition sortsup.hpp:117
Gecode::Int::Sorted::OfflineMinItem::iset
int iset
Initial set label.
Definition sortsup.hpp:134
Gecode::Int::Sorted::OfflineMinItem::pred
int pred
Predecessor in the Offline-Min sequence.
Definition sortsup.hpp:138
Gecode::Int::Sorted::OfflineMinItem::root
int root
Root node representing the set the vertex belongs to.
Definition sortsup.hpp:120
Gecode::Int::Sorted::OfflineMinItem::succ
int succ
Successor in the Offline-Min sequence.
Definition sortsup.hpp:136
Gecode::Int::Sorted::OfflineMinItem::rank
int rank
Ranking of the set given by its cardinality.
Definition sortsup.hpp:124
Gecode::Int::Sorted::OfflineMinItem::name
int name
Name or label of a set.
Definition sortsup.hpp:126
Gecode::Int::Sorted::OfflineMinItem::parent
int parent
Predecessor in the tree representation of the set.
Definition sortsup.hpp:122
Gecode::Int::Sorted::OfflineMin::OfflineMin
OfflineMin(void)
Definition sortsup.hpp:173
Gecode::Int::Sorted::OfflineMin::unite
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition sortsup.hpp:210
Gecode::Int::Sorted::OfflineMin::operator[]
OfflineMinItem & operator[](int)
Definition sortsup.hpp:246
Gecode::Int::Sorted::OfflineMin::makeset
void makeset(void)
Initialization of the datastructure.
Definition sortsup.hpp:227
Gecode::Int::Sorted::OfflineMin::size
int size(void)
Return the size of the Offline-Min item.
Definition sortsup.hpp:241
Gecode::Int::Sorted::OfflineMin::find_pc
int find_pc(int x)
Definition sortsup.hpp:196
Gecode::Int::Sorted::OfflineMin::find
int find(int x)
Definition sortsup.hpp:186
Gecode::Int::Sorted::Rank
Storage class for mininmum and maximum of a variable.
Definition sortsup.hpp:39
Gecode::Int::Sorted::Rank::max
int max
stores the mininmum of a variable
Definition sortsup.hpp:44
Gecode::Int::Sorted::Rank::min
int min
stores the mininmum of a variable
Definition sortsup.hpp:42
Gecode::Int::Sorted::SccComponent
Representation of a strongly connected component.
Definition sortsup.hpp:53
Gecode::Int::Sorted::SccComponent::leftmost
int leftmost
Leftmost y-node in a scc.
Definition sortsup.hpp:56
Gecode::Int::Sorted::SccComponent::left
int left
Direct left neighbour of an y-node in a scc.
Definition sortsup.hpp:58
Gecode::Int::Sorted::SccComponent::right
int right
Direct right neighbour of an y-node in a scc.
Definition sortsup.hpp:60
Gecode::Int::Sorted::SccComponent::rightmost
int rightmost
Rightmost reachable y-node in a scc.
Definition sortsup.hpp:62
Gecode::Int::Sorted::TupleMaxIncExt::x
ViewArray< View > x
Definition sortsup.hpp:287
Gecode::Int::Sorted::TupleMaxIncExt::z
ViewArray< View > z
Definition sortsup.hpp:288
Gecode::Int::Sorted::TupleMaxIncExt::operator()
bool operator()(const int i, const int j)
Definition sortsup.hpp:292
Gecode::Int::Sorted::TupleMaxIncExt::TupleMaxIncExt
TupleMaxIncExt(const ViewArray< View > &x0, const ViewArray< View > &z0)
Definition sortsup.hpp:290
Gecode::Int::Sorted::TupleMaxInc::operator()
bool operator()(const int i, const int j)
Definition sortsup.hpp:265
Gecode::Int::Sorted::TupleMaxInc::TupleMaxInc
TupleMaxInc(const ViewArray< View > &x0)
Definition sortsup.hpp:264
Gecode::Int::Sorted::TupleMaxInc::x
ViewArray< View > x
Definition sortsup.hpp:262
Gecode::Int::Sorted::TupleMinIncExt
Extended view comparison on pairs of views.
Definition sortsup.hpp:350
Gecode::Int::Sorted::TupleMinIncExt::operator()
bool operator()(const ViewPair< View > &x, const ViewPair< View > &y)
Definition sortsup.hpp:352
Gecode::Int::Sorted::TupleMinInc
View comparison on ViewTuples.
Definition sortsup.hpp:319
Gecode::Int::Sorted::TupleMinInc::operator()
bool operator()(const View &x, const View &y)
Definition sortsup.hpp:321
Gecode::Int::Sorted::ViewPair
Pair of views.
Definition sortsup.hpp:333
Gecode::Int::Sorted::ViewPair::x
View x
Definition sortsup.hpp:335
Gecode::Int::Sorted::ViewPair::z
View z
Definition sortsup.hpp:336
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewArray::assigned
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1377
Gecode::ViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1156
small
const int small[]
Small Photo example.
Definition photo.cpp:192
large
const int large[]
Large Photo example.
Definition photo.cpp:202
pi
const int * pi[]
Definition photo.cpp:14262
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
Gecode::me_modified
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Gecode::Int::Sorted
Sorted propagators
Gecode::Int::Sorted::channel
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
Definition sortsup.hpp:489
Gecode::Int::Sorted::array_assigned
bool array_assigned(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, bool &match_fixed, bool &, bool &noperm_bc)
Check for assignment of a variable array.
Definition sortsup.hpp:378
Gecode::Int::Sorted::check_subsumption
bool check_subsumption(ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, int &dropfst)
Subsumption test.
Definition sortsup.hpp:78
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::sum
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:880
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