opt.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.
*
*/
namespace Gecode { namespace Int { namespace NoOverlap {
template<class Box>
forceinline
OptProp<Box>::OptProp(Home home, Box* b, int n, int m0)
: Base<Box>(home,b,n), m(m0) {
for (int i=0; i<m; i++)
b[n+i].subscribe(home, *this);
}
template<class Box>
ExecStatus
OptProp<Box>::post(Home home, Box* b, int n) {
// Partition into mandatory and optional boxes
if (n > 1) {
int p = Base<Box>::partition(b, 0, n);
(void) new (home) OptProp<Box>(home,b,p,n-p);
}
return ES_OK;
}
template<class Box>
forceinline size_t
OptProp<Box>::dispose(Space& home) {
for (int i=0; i<m; i++)
b[n+i].cancel(home, *this);
(void) Base<Box>::dispose(home);
return sizeof(*this);
}
template<class Box>
forceinline
OptProp<Box>::OptProp(Space& home, OptProp<Box>& p)
: Base<Box>(home, p, p.n + p.m), m(p.m) {}
template<class Box>
Actor*
OptProp<Box>::copy(Space& home) {
return new (home) OptProp<Box>(home,*this);
}
template<class Box>
ExecStatus
OptProp<Box>::propagate(Space& home, const ModEventDelta& med) {
Region r;
if (BoolView::me(med) == ME_BOOL_VAL) {
// Eliminate excluded boxes
for (int i=m; i--; )
if (b[n+i].excluded()) {
b[n+i].cancel(home,*this);
b[n+i] = b[n+(--m)];
}
// Reconsider optional boxes
if (m > 0) {
int p = Base<Box>::partition(b+n, 0, m);
n += p; m -= p;
}
}
// Number of disjoint boxes
int* db = r.alloc<int>(n);
for (int i=0; i<n; i++)
db[i] = n-1;
// Number of boxes to be eliminated
int e = 0;
for (int i=0; i<n; i++) {
assert(b[i].mandatory());
for (int j=0; j<i; j++)
if (b[i].nooverlap(b[j])) {
assert(db[i] > 0); assert(db[j] > 0);
if (--db[i] == 0) e++;
if (--db[j] == 0) e++;
continue;
} else {
GECODE_ES_CHECK(b[i].nooverlap(home,b[j]));
}
}
if (m == 0) {
if (e == n)
return home.ES_SUBSUMED(*this);
int i = n-1;
while (e > 0) {
// Eliminate boxes that do not overlap
while (db[i] > 0)
i--;
b[i].cancel(home, *this);
b[i] = b[--n]; b[n] = b[n+m];
e--; i--;
}
if (n < 2)
return home.ES_SUBSUMED(*this);
}
// Check whether some optional boxes must be excluded
for (int i=m; i--; ) {
if (b[n+i].optional()) {
for (int j=n; j--; )
if (b[n+i].overlap(b[j])) {
GECODE_ES_CHECK(b[n+i].exclude(home));
b[n+i].cancel(home,*this);
b[n+i] = b[n+(--m)];
break;
}
} else {
// This might be the case if the same Boolean view occurs
// several times and has already been excluded
assert(b[n+i].excluded());
b[n+i].cancel(home,*this);
b[n+i] = b[n+(--m)];
}
}
return ES_NOFIX;
}
}}}
// STATISTICS: int-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::FloatVal::overlap
bool overlap(const FloatVal &x, const FloatVal &y)
Test whether x and y overlap.
Definition val.hpp:498
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::NoOverlap::Base::n
int n
Number of mandatory boxes: b[0] ... b[n-1].
Definition no-overlap.hh:239
Gecode::Int::NoOverlap::Base::Base
Base(Home home, Box *b, int n)
Constructor for posting with n mandatory boxes.
Definition base.hpp:38
Gecode::Int::NoOverlap::Base::dispose
virtual size_t dispose(Space &home)
Destructor.
Definition base.hpp:59
Gecode::Int::NoOverlap::Base::b
Box * b
Boxes.
Definition no-overlap.hh:237
Gecode::Int::NoOverlap::Base::partition
static int partition(Box *b, int i, int n)
Partition n boxes b starting at position i.
Definition base.hpp:46
Gecode::Int::NoOverlap::OptProp::dispose
virtual size_t dispose(Space &home)
Destructor.
Definition opt.hpp:57
Gecode::Int::NoOverlap::OptProp::post
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition opt.hpp:46
Gecode::Int::NoOverlap::OptProp::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition opt.hpp:78
Gecode::Int::NoOverlap::OptProp::OptProp
OptProp(Home home, Box *b, int n, int m)
Constructor for posting.
Definition opt.hpp:38
Gecode::Int::NoOverlap::OptProp::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition opt.hpp:72
Gecode::Int::NoOverlap::OptProp::m
int m
Number of optional boxes: b[n] ... b[n+m-1].
Definition no-overlap.hh:299
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::VarImpView< BoolVar >::me
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
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::nooverlap
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntPropLevel ipl=IPL_DEF)
Post propagator for rectangle packing.
Definition no-overlap.cpp:51
Gecode::Int::NoOverlap
No-overlap propagators
Definition no-overlap.cpp:38
Gecode::Int::NoOverlap::optional
bool optional(const BoolVarArgs &m)
Definition no-overlap.cpp:41
Gecode::Int
Finite domain integers.
Gecode::Int::ME_BOOL_VAL
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:116
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_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
forceinline
#define forceinline
Definition config.hpp:187