int-base.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2011
*
* 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/distinct.hh>
namespace Gecode { namespace Int { namespace NValues {
template<class VY>
forceinline
IntBase<VY>::IntBase(Home home, ValSet& vs0, ViewArray<IntView>& x, VY y)
: MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home,x,y),
vs(vs0) {}
template<class VY>
forceinline
IntBase<VY>::IntBase(Space& home, IntBase<VY>& p)
: MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home, p) {
vs.update(home, p.vs);
}
template<class VY>
forceinline size_t
IntBase<VY>::dispose(Space& home) {
vs.dispose(home);
(void) MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>
::dispose(home);
return sizeof(*this);
}
template<class VY>
PropCost
IntBase<VY>::cost(const Space&, const ModEventDelta&) const {
return PropCost::quadratic(PropCost::HI, x.size());
}
template<class VY>
void
IntBase<VY>::add(Space& home) {
int n=x.size();
for (int i=n; i--; )
if (x[i].assigned()) {
vs.add(home, x[i].val());
x[i] = x[--n];
}
x.size(n);
}
template<class VY>
void
IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) {
// Compute positions of disjoint views
int n=x.size();
dis = r.alloc<int>(n); n_dis = 0;
int i=0;
while (i < n)
switch (vs.compare(x[i])) {
case Iter::Ranges::CS_SUBSET:
// All values are already contained in vs, eliminate x[i]
x[i].cancel(home, *this, PC_INT_DOM);
x[i] = x[--n];
break;
case Iter::Ranges::CS_DISJOINT:
dis[n_dis++] = i++;
break;
case Iter::Ranges::CS_NONE:
i++;
break;
default:
GECODE_NEVER;
}
x.size(n);
}
template<class VY>
void
IntBase<VY>::eliminate(Space& home) {
int n=x.size();
for (int i=n; i--; )
if (vs.subset(x[i])) {
// All values are already contained in vs, eliminate x[i]
x[i].cancel(home, *this, PC_INT_DOM);
x[i] = x[--n];
}
x.size(n);
}
template<class VY>
ExecStatus
IntBase<VY>::all_in_valset(Space& home) {
for (int i=x.size(); i--; ) {
ValSet::Ranges vsr(vs);
GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
}
return home.ES_SUBSUMED(*this);
}
template<class VY>
ExecStatus
IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
assert(n_dis > 0);
// At least one more value will be needed
GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
Region r;
// Only one additional value is allowed
if (y.max() == vs.size() + 1) {
// Compute possible values
ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
for (int i=n_dis; i--; )
r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
// Is there a common value at all?
if (!iv())
return ES_FAILED;
ValSet::Ranges vsr(vs);
Iter::Ranges::NaryUnion pv(r,iv,vsr);
// Enforce common values
for (int i=x.size(); i--; ) {
pv.reset();
GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
}
return ES_OK;
}
// Compute independent set for lower bound
// ovl is a bit-matrix defining whether two views overlap
SymBitMatrix ovl(r,x.size());
// deg[i] is the degree of x[i]
int* deg = r.alloc<int>(x.size());
// ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
int** ovl_i = r.alloc<int*>(x.size());
// n_ovl_i[i] defines how many integers are stored for ovl_i[i]
int* n_ovl_i = r.alloc<int>(x.size());
{
#ifndef NDEBUG
// Initialize all to null pointers so that things crash ;-)
for (int i=x.size(); i--; )
ovl_i[i] = NULL;
#endif
// For each i there can be at most n_dis-1 entries in ovl_i[i]
int* m = r.alloc<int>(n_dis*(n_dis-1));
for (int i=n_dis; i--; ) {
deg[dis[i]] = 0;
ovl_i[dis[i]] = m; m += n_dis-1;
}
}
// Initialize overlap matrix by analyzing the view ranges
{
// Compute how many events are needed
// One event for the end marker
int n_re = 1;
// Two events for each range
for (int i=n_dis; i--; )
for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
n_re += 2;
// Allocate and initialize events
RangeEvent* re = r.alloc<RangeEvent>(n_re);
{
int j=0;
for (int i=n_dis; i--; )
for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
// Event when a range starts
re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
// Event when a range ends
re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
}
// Make this the last event
re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
assert(j+1 == n_re);
}
// Sort and process events
Support::quicksort(re,n_re);
// Current views with a range being active
Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
// Process all events
for (int i=0; true; i++)
switch (re[i].ret) {
case RET_FST:
// Process all overlapping views
for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur);
j(); ++j) {
int di = re[i].view, dj = j.val();
if (!ovl.get(di,dj)) {
ovl.set(di,dj);
ovl_i[di][deg[di]++] = dj;
ovl_i[dj][deg[dj]++] = di;
}
}
cur.set(static_cast<unsigned int>(re[i].view));
break;
case RET_LST:
cur.clear(static_cast<unsigned int>(re[i].view));
break;
case RET_END:
goto done;
default:
GECODE_NEVER;
}
done:
r.free<RangeEvent>(re,n_re);
}
// While deg changes, n_ovl_i remains unchanged and is needed, so copy it
for (int i=n_dis; i--; ) {
assert(deg[dis[i]] < n_dis);
n_ovl_i[dis[i]] = deg[dis[i]];
}
// Views in the independent set
int* ind = r.alloc<int>(n_dis);
int n_ind = 0;
while (n_dis > 0) {
int i_min = n_dis-1;
int d_min = deg[dis[i_min]];
unsigned int s_min = x[dis[i_min]].size();
// Find view with smallest (degree,size)
for (int i=n_dis-1; i--; )
if ((d_min > deg[dis[i]]) ||
((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
i_min = i;
d_min = deg[dis[i]];
s_min = x[dis[i]].size();
}
// i_min refers to view with smallest (degree,size)
ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
// Filter out non disjoint views
for (int i=n_dis; i--; )
if (ovl.get(dis[i],ind[n_ind-1])) {
// Update degree information
for (int j=n_ovl_i[dis[i]]; j--; )
deg[ovl_i[dis[i]][j]]--;
// Eliminate view
dis[i] = dis[--n_dis];
}
}
// Enforce lower bound
GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
// Prune, if possible
if (vs.size() + n_ind == y.max()) {
// Only values from the indepent set a can be taken
ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
for (int i=n_ind; i--; )
r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
ValSet::Ranges vsr(vs);
v_ind |= vsr;
for (int i=x.size(); i--; ) {
v_ind.reset();
GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
}
}
return ES_OK;
}
template<class VY>
forceinline ExecStatus
IntBase<VY>::prune_upper(Space& home, Graph& g) {
if (!g) {
g.init(home,vs,x);
} else {
g.purge();
g.sync();
}
GECODE_ME_CHECK(y.lq(home, g.size()));
if (y.min() == g.size()) {
// All values must be taken on
if (vs.size() + x.size() == g.size()) {
// This is in fact a distinct, simplify and rewrite
for (int i=x.size(); i--; ) {
ValSet::Ranges vsr(vs);
GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
}
GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home(*this),x));
}
if (g.mark())
GECODE_ES_CHECK(g.prune(home));
}
return ES_OK;
}
}}}
// STATISTICS: int-prop
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::Distinct::Dom::post
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition dom.hpp:45
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Int::NValues::Graph
View-value graph for propagation of upper bound.
Definition nvalues.hh:96
Gecode::Int::NValues::Graph::init
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition graph.hpp:46
Gecode::Int::NValues::Graph::sync
void sync(void)
Synchronize graph with new view domains.
Definition graph.hpp:90
Gecode::Int::NValues::Graph::mark
bool mark(void)
Definition graph.hpp:152
Gecode::Int::NValues::Graph::prune
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition graph.hpp:255
Gecode::Int::NValues::Graph::size
int size(void) const
Return size of maximal matching (excluding assigned views).
Definition graph.hpp:41
Gecode::Int::NValues::IntBase::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-base.hpp:53
Gecode::Int::NValues::IntBase::vs
ValSet vs
Value set storing the values of already assigned views.
Definition nvalues.hh:138
Gecode::Int::NValues::IntBase::prune_lower
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition int-base.hpp:130
Gecode::Int::NValues::IntBase::disjoint
void disjoint(Space &home, Region &r, int *&dis, int &n_dis)
Definition int-base.hpp:80
Gecode::Int::NValues::IntBase::cost
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition int-base.hpp:62
Gecode::Int::NValues::IntBase::add
void add(Space &home)
Add values of assigned views to value set.
Definition int-base.hpp:68
Gecode::Int::NValues::IntBase::eliminate
void eliminate(Space &home)
Eliminate subsumed views (all values included in the value set vs).
Definition int-base.hpp:107
Gecode::Int::NValues::IntBase::all_in_valset
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition int-base.hpp:120
Gecode::Int::NValues::IntBase::prune_upper
ExecStatus prune_upper(Space &home, Graph &g)
Definition int-base.hpp:298
Gecode::Int::NValues::IntBase::IntBase
IntBase(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-base.hpp:40
Gecode::Int::NValues::RangeEvent
Event for range-based overlap analysis.
Definition nvalues.hh:58
Gecode::Int::NValues::RangeEvent::ret
RangeEventType ret
The event type.
Definition nvalues.hh:61
Gecode::Int::NValues::RangeEvent::view
int view
Which view does this range belong to.
Definition nvalues.hh:65
Gecode::Int::NValues::RangeEvent::val
int val
The value for the range (first or last value, depending on type).
Definition nvalues.hh:63
Gecode::Int::NValues::SymBitMatrix
Symmetric diagonal bit matrix.
Definition nvalues.hh:71
Gecode::Int::NValues::SymBitMatrix::get
bool get(int x, int y) const
Is bit at position x, y set?
Definition sym-bit-matrix.hpp:50
Gecode::Int::NValues::SymBitMatrix::set
void set(int x, int y)
Set bit at position x, y.
Definition sym-bit-matrix.hpp:57
Gecode::Int::ValSet::Ranges
Iterator over ranges.
Definition val-set.hh:78
Gecode::Int::ValSet
Class for storing values of already assigned views.
Definition val-set.hh:44
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Int::ViewValGraph::Graph::purge
void purge(void)
Purge graph if necessary (reset information to avoid overflow).
Definition graph.hpp:130
Gecode::Iter::Ranges::NaryInter
Range iterator for intersection of iterators.
Definition ranges-inter.hpp:74
Gecode::Iter::Ranges::NaryUnion
Range iterator for union of iterators.
Definition ranges-union.hpp:74
Gecode::Iter::Ranges::RangeListIter::reset
void reset(void)
Reset iterator to start.
Definition ranges-list.hpp:240
Gecode::Iter::Values::BitSet
Value iterator for values in a bitset.
Definition values-bitset.hpp:42
Gecode::MixNaryOnePropagator< IntView, PC_INT_DOM, VY, PC_INT_BND >::MixNaryOnePropagator
MixNaryOnePropagator(Space &home, MixNaryOnePropagator &p)
Definition pattern.hpp:733
Gecode::MixNaryOnePropagator< IntView, PC_INT_DOM, VY, PC_INT_BND >::x
ViewArray< IntView > x
Definition pattern.hpp:275
Gecode::MixNaryOnePropagator< IntView, PC_INT_DOM, VY, PC_INT_BND >::y
VY y
Definition pattern.hpp:277
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::quadratic
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
Gecode::PropCost::HI
@ HI
Expensive.
Definition core.hpp:514
Gecode::Propagator::size
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1077
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Support::BitSetBase::clear
void clear(unsigned int i)
Clear bit i.
Definition bitset-base.hpp:600
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::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_REWRITE
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
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
distinct.hh
Gecode::Int::Limits::infinity
const int infinity
Infinity for integers.
Definition int.hh:120
Gecode::Int::NValues
Number of values propagators.
Gecode::Int::NValues::RET_FST
@ RET_FST
A range starts.
Definition nvalues.hh:50
Gecode::Int::NValues::RET_LST
@ RET_LST
A range ends.
Definition nvalues.hh:52
Gecode::Int::NValues::RET_END
@ RET_END
No further events.
Definition nvalues.hh:54
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_BND
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode::Iter::Ranges::CS_NONE
@ CS_NONE
Neither of the above.
Definition ranges-operations.hpp:63
Gecode::Iter::Ranges::CS_SUBSET
@ CS_SUBSET
First is subset of second iterator.
Definition ranges-operations.hpp:61
Gecode::Iter::Ranges::CS_DISJOINT
@ CS_DISJOINT
Intersection is empty.
Definition ranges-operations.hpp:62
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
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
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56