seq-u.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
* Christian Schulte <schulte@gecode.org>
*
* Contributing authors:
* Gabor Szokoli <szokoli@gecode.org>
*
* Copyright:
* Guido Tack, 2004
* Christian Schulte, 2004
* Gabor Szokoli, 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.
*
*/
#include <gecode/set/sequence.hh>
namespace Gecode { namespace Set { namespace Sequence {
/*
* "Sequenced union" propagator
*
*/
Actor*
SeqU::copy(Space& home) {
return new (home) SeqU(home,*this);
}
ExecStatus
SeqU::propagateSeqUnion(Space& home,
bool& modified, ViewArray<SetView>& x,
SetView& y) {
Region r;
GlbRanges<SetView>* XLBs = r.alloc<GlbRanges<SetView> >(x.size());
for (int i=x.size(); i--; ) {
GlbRanges<SetView> lb(x[i]);
XLBs[i]=lb;
}
Iter::Ranges::NaryAppend<GlbRanges<SetView> > u(XLBs,x.size());
GECODE_ME_CHECK_MODIFIED(modified, y.includeI(home,u));
GLBndSet before(home);
for (int i=0; i<x.size(); i++) {
LubRanges<SetView> xiub(x[i]);
before.includeI(home, xiub);
BndSetRanges beforeR(before);
GlbRanges<SetView> ylb(y);
Iter::Ranges::Diff<GlbRanges<SetView>, BndSetRanges> diff(ylb, beforeR);
if (diff()) {
GECODE_ME_CHECK_MODIFIED(modified, x[i].exclude(home, diff.min(),
Limits::max));
}
}
before.dispose(home);
GLBndSet after(home);
for (int i=x.size(); i--; ) {
LubRanges<SetView> xiub(x[i]);
after.includeI(home, xiub);
BndSetRanges afterR(after);
GlbRanges<SetView> ylb(y);
Iter::Ranges::Diff<GlbRanges<SetView>, BndSetRanges> diff(ylb, afterR);
if (diff()) {
int max = diff.max();
for (; diff(); ++diff)
max = diff.max();
GECODE_ME_CHECK_MODIFIED(modified, x[i].exclude(home,
Limits::min,
max));
}
}
after.dispose(home);
return ES_FIX;
}
//Enforces sequentiality and ensures y contains union of Xi lower bounds.
ExecStatus
SeqU::propagate(Space& home, const ModEventDelta& med) {
ModEvent me0 = SetView::me(med);
bool ubevent = Rel::testSetEventUB(me0);
bool anybevent = Rel::testSetEventAnyB(me0);
bool cardevent = Rel::testSetEventCard(me0);
bool modified = false;
bool assigned=false;
bool oldModified = false;
do {
oldModified = modified;
modified = false;
if (oldModified || modified || anybevent || cardevent)
GECODE_ES_CHECK(propagateSeq(home,modified,assigned,x));
if (oldModified || modified || anybevent)
GECODE_ES_CHECK(propagateSeqUnion(home,modified,x,y));
if (oldModified || modified || ubevent)
GECODE_ES_CHECK(RelOp::unionNXiUB(home,modified,x,y,unionOfDets));
if (oldModified || modified || ubevent)
GECODE_ES_CHECK(RelOp::partitionNYUB(home,modified,x,y,unionOfDets));
if (oldModified || modified || anybevent)
GECODE_ES_CHECK(RelOp::partitionNXiLB(home,modified,x,y,unionOfDets));
if (oldModified || modified || cardevent || ubevent)
GECODE_ES_CHECK(RelOp::partitionNCard(home,modified,x,y,unionOfDets));
} while (modified);
for (int i=x.size(); i--;)
if (!x[i].assigned())
return ES_FIX;
return home.ES_SUBSUMED(*this);
}
}}}
// STATISTICS: set-prop
Gecode::Iter::Ranges::Diff
Range iterator for computing set difference.
Definition ranges-diff.hpp:43
Gecode::Iter::Ranges::MinMax::min
int min(void) const
Return smallest value of range.
Definition ranges-minmax.hpp:99
Gecode::Iter::Ranges::MinMax::max
int max(void) const
Return largest value of range.
Definition ranges-minmax.hpp:103
Gecode::Iter::Ranges::NaryAppend
Range iterator for appending arbitrarily many iterators.
Definition ranges-append.hpp:81
Gecode::NaryOnePropagator< SetView, PC_SET_ANY >::x
ViewArray< SetView > x
Definition pattern.hpp:175
Gecode::NaryOnePropagator< SetView, PC_SET_ANY >::y
SetView y
Definition pattern.hpp:177
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Set::BndSetRanges
Range iterator for integer sets.
Definition var-imp.hpp:185
Gecode::Set::BndSet::dispose
void dispose(Space &home)
Free memory used by this set.
Definition integerset.hpp:60
Gecode::Set::GLBndSet
Growing sets of integers.
Definition var-imp.hpp:205
Gecode::Set::GLBndSet::includeI
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition integerset.hpp:296
Gecode::Set::GlbRanges
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Gecode::Set::LubRanges
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Gecode::Set::Sequence::SeqU::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition seq-u.cpp:104
Gecode::Set::Sequence::SeqU::SeqU
SeqU(Space &home, SeqU &p)
Constructor for cloning p.
Definition seq-u.hpp:52
Gecode::Set::Sequence::SeqU::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition seq-u.cpp:50
Gecode::Set::Sequence::SeqU::propagateSeqUnion
ExecStatus propagateSeqUnion(Space &home, bool &modified, ViewArray< SetView > &x, SetView &y)
Definition seq-u.cpp:55
Gecode::Set::Sequence::SeqU::unionOfDets
GLBndSet unionOfDets
Definition sequence.hh:83
Gecode::Set::SetView
Set view for set variables
Definition view.hpp:56
Gecode::VarImpView< SetVar >::me
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
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_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
GECODE_ME_CHECK_MODIFIED
#define GECODE_ME_CHECK_MODIFIED(modified, me)
Check whether me is failed or modified, and forward failure.
Definition macros.hpp:64
Gecode::Set::Limits::min
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
Gecode::Set::Limits::max
const int max
Largest allowed integer in integer set.
Definition set.hh:97
Gecode::Set::RelOp::partitionNCard
ExecStatus partitionNCard(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition common.hpp:308
Gecode::Set::RelOp::unionNXiUB
ExecStatus unionNXiUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &)
Definition common.hpp:294
Gecode::Set::RelOp::partitionNXiLB
ExecStatus partitionNXiLB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition common.hpp:513
Gecode::Set::RelOp::partitionNYUB
ExecStatus partitionNYUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition common.hpp:587
Gecode::Set::Rel::testSetEventCard
bool testSetEventCard(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:95
Gecode::Set::Rel::testSetEventUB
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:87
Gecode::Set::Rel::testSetEventAnyB
bool testSetEventAnyB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:91
Gecode::Set::Sequence
Propagators for ordered sequences of sets.
Definition sequence.hh:45
Gecode::Set::Sequence::propagateSeq
ExecStatus propagateSeq(Space &home, bool &modified, bool &assigned, ViewArray< SetView > &x)
Definition common.hpp:43
Gecode::Set
Finite integer sets.
Definition var-imp.hpp:137
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
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
sequence.hh