order.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 {
template<class View, bool Perm>
inline void
sort_sigma(ViewArray<View>& x, ViewArray<View>& z) {
if (Perm) {
Region r;
ViewPair<View>* xz = r.alloc<ViewPair<View> >(x.size());
for (int i=x.size(); i--; ) {
xz[i].x=x[i]; xz[i].z=z[i];
}
TupleMinIncExt<View> min_inc;
Support::quicksort<ViewPair<View>,TupleMinIncExt<View> >
(&xz[0], x.size(), min_inc);
for (int i=x.size(); i--; ) {
x[i]=xz[i].x; z[i]=xz[i].z;
}
} else {
TupleMinInc<View> min_inc;
Support::quicksort<View,TupleMinInc<View> >(&x[0], x.size(), min_inc);
}
}
template<class View, bool Perm>
inline void
sort_tau(ViewArray<View>& x, ViewArray<View>& z, int tau[]) {
if (Perm) {
TupleMaxIncExt<View> ltmax(x,z);
Support::quicksort(&(*tau), x.size(), ltmax);
} else {
TupleMaxInc<View> ltmax(x);
Support::quicksort(&(*tau), x.size(), ltmax);
}
}
template<class View>
inline bool
normalize(Space& home,
ViewArray<View>& y,
ViewArray<View>& x,
bool& nofix) {
int ys = y.size();
for (int i = 1; i < ys; i++) {
ModEvent me_lb = y[i].gq(home, y[i - 1].min());
if (me_failed(me_lb))
return false;
nofix |= (me_modified(me_lb) && y[i - 1].min() != y[i].min());
}
for (int i = ys - 1; i--; ) {
ModEvent me_ub = y[i].lq(home, y[i + 1].max());
if (me_failed(me_ub))
return false;
nofix |= (me_modified(me_ub) && y[i + 1].max() != y[i].max());
}
int xs = x.size();
for (int i = xs; i--; ) {
ModEvent me = x[i].gq(home, y[0].min());
if (me_failed(me))
return false;
nofix |= (me_modified(me) && x[i].min() != y[0].min());
me = x[i].lq(home, y[xs - 1].max());
if (me_failed(me))
return false;
nofix |= (me_modified(me) && x[i].max() != y[xs - 1].max());
}
return true;
}
template<class View>
inline bool
perm_bc(Space& home, int tau[],
SccComponent sinfo[],
int scclist[],
ViewArray<View>& x,
ViewArray<View>& z,
bool& crossingedge,
bool& nofix) {
int ps = x.size();
for (int i = 1; i < ps; i++) {
// if there are "crossed edges"
if (x[i - 1].min() < x[i].min()) {
if (z[i - 1].min() > z[i].min()) {
if (z[i].min() != sinfo[scclist[i]].leftmost) {
// edge does not take part in solution
if (z[i].assigned()) { // vital edge do not remove it
if (x[i - 1].max() < x[i].min()) {
// invalid permutation
// the upper bound sorting cannot fix this
return false;
}
} else {
crossingedge = true;
// and the permutation can still be changed
// fix the permutation, i.e. modify z
ModEvent me_z = z[i].gq(home, z[i - 1].min());
if (me_failed(me_z)) {
return false;
}
nofix |= ( me_modified(me_z) &&
z[i - 1].min() != z[i].min());
}
}
}
}
}
// the same check as above for the upper bounds
for (int i = ps - 1; i--; ) {
if (x[tau[i]].max() < x[tau[i + 1]].max()) {
if (z[tau[i]].max() > z[tau[i + 1]].max()) {
if (z[tau[i]].max() != sinfo[scclist[tau[i]]].rightmost) {
// edge does not take part in solution
if (z[tau[i]].assigned()) {
if (x[tau[i + 1]].min() > x[tau[i]].max()) {
// invalid permutation
return false;
}
} else {
crossingedge = true;
ModEvent me_z = z[tau[i]].lq(home, z[tau[i + 1]].max());
if (me_failed(me_z)) {
return false;
}
nofix |= (me_modified(me_z) &&
z[tau[i + 1]].max() != z[tau[i]].max());
}
}
}
}
}
return true;
}
}}}
// STATISTICS: int-prop
Gecode::Int::Sorted::SccComponent
Representation of a strongly connected component.
Definition sortsup.hpp:53
Gecode::Int::Sorted::TupleMaxIncExt
Extended Index comparison for ViewArray<Tuple>.
Definition sortsup.hpp:285
Gecode::Int::Sorted::TupleMaxInc
Index comparison for ViewArray<Tuple>.
Definition sortsup.hpp:260
Gecode::Int::Sorted::TupleMinIncExt
Extended view comparison on pairs of views.
Definition sortsup.hpp:350
Gecode::Int::Sorted::TupleMinInc
View comparison on ViewTuples.
Definition sortsup.hpp:319
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::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
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::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::sort_tau
void sort_tau(ViewArray< View > &x, ViewArray< View > &z, int tau[])
Build .
Definition order.hpp:74
Gecode::Int::Sorted::normalize
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Definition order.hpp:93
Gecode::Int::Sorted::perm_bc
bool perm_bc(Space &home, int tau[], SccComponent sinfo[], int scclist[], ViewArray< View > &x, ViewArray< View > &z, bool &crossingedge, bool &nofix)
Bounds consistency on the permutation views.
Definition order.hpp:140
Gecode::Int::Sorted::sort_sigma
void sort_sigma(ViewArray< View > &x, ViewArray< View > &z)
Build .
Definition order.hpp:45
Gecode::Int
Finite domain integers.
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::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