propagate.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, 2010
*
* 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 BinPacking {
/*
* Item
*
*/
forceinline
Item::Item(void)
: s(0) {}
forceinline
Item::Item(IntView b, int s0)
: DerivedView<IntView>(b), s(s0) {}
forceinline IntView
Item::bin(void) const {
return x;
}
forceinline
void Item::bin(IntView b) {
x = b;
}
forceinline int
Item::size(void) const {
return s;
}
forceinline void
Item::size(int s0) {
s = s0;
}
forceinline void
Item::update(Space& home, Item& i) {
x.update(home,i.x);
s = i.s;
}
forceinline bool
operator ==(const Item& i, const Item& j) {
return (i.bin() == j.bin()) && (i.size() == j.size());
}
forceinline bool
operator !=(const Item& i, const Item& j) {
return !(i == j);
}
forceinline bool
operator <(const Item& i, const Item& j) {
return i.size() > j.size();
}
/*
* Size set
*
*/
forceinline
SizeSet::SizeSet(void) {}
forceinline
SizeSet::SizeSet(Region& region, int n_max)
: n(0), t(0), s(region.alloc<int>(n_max)) {}
forceinline void
SizeSet::add(int s0) {
t += s0; s[n++] = s0;
}
forceinline int
SizeSet::card(void) const {
return n;
}
forceinline int
SizeSet::total(void) const {
return t;
}
forceinline int
SizeSet::operator [](int i) const {
return s[i];
}
forceinline
SizeSetMinusOne::SizeSetMinusOne(void) {}
forceinline
SizeSetMinusOne::SizeSetMinusOne(Region& region, int n_max)
: SizeSet(region,n_max), p(-1) {}
forceinline void
SizeSetMinusOne::minus(int s0) {
// This rests on the fact that items are removed in order
do
p++;
while (s[p] > s0);
assert(p < n);
}
forceinline int
SizeSetMinusOne::card(void) const {
assert(p >= 0);
return n - 1;
}
forceinline int
SizeSetMinusOne::total(void) const {
assert(p >= 0);
return t - s[p];
}
forceinline int
SizeSetMinusOne::operator [](int i) const {
assert(p >= 0);
return s[(i < p) ? i : i+1];
}
/*
* Packing propagator
*
*/
forceinline
Pack::Pack(Home home, ViewArray<OffsetView>& l0, ViewArray<Item>& bs0)
: Propagator(home), l(l0), bs(bs0), t(0) {
l.subscribe(home,*this,PC_INT_BND);
bs.subscribe(home,*this,PC_INT_DOM);
for (int i=0; i<bs.size(); i++)
t += bs[i].size();
}
forceinline
Pack::Pack(Space& home, Pack& p)
: Propagator(home,p), t(p.t) {
l.update(home,p.l);
bs.update(home,p.bs);
}
forceinline size_t
Pack::dispose(Space& home) {
l.cancel(home,*this,PC_INT_BND);
bs.cancel(home,*this,PC_INT_DOM);
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class SizeSet>
forceinline bool
Pack::nosum(const SizeSet& s, int a, int b, int& ap, int& bp) {
if ((a <= 0) || (b >= s.total()))
return false;
int n=s.card()-1;
int sc=0;
int kp=0;
while (sc + s[n-kp] < a) {
sc += s[n-kp];
kp++;
}
int k=0;
int sa=0, sb = s[n-kp];
while ((sa < a) && (sb <= b)) {
sa += s[k++];
if (sa < a) {
kp--;
sb += s[n-kp];
sc -= s[n-kp];
while (sa + sc >= a) {
kp--;
sc -= s[n-kp];
sb += s[n-kp] - s[n-kp-k-1];
}
}
}
ap = sa + sc; bp = sb;
return sa < a;
}
template<class SizeSet>
forceinline bool
Pack::nosum(const SizeSet& s, int a, int b) {
int ap, bp;
return nosum(s, a, b, ap, bp);
}
}}}
// STATISTICS: int-prop
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::DerivedView< IntView >::x
IntView x
Definition view.hpp:238
Gecode::DerivedView< IntView >::DerivedView
DerivedView(void)
Definition view.hpp:584
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::BinPacking::Item
Item combining bin and size information.
Definition bin-packing.hh:53
Gecode::Int::BinPacking::Item::bin
IntView bin(void) const
Return bin of item.
Definition propagate.hpp:48
Gecode::Int::BinPacking::Item::update
void update(Space &home, Item &i)
Update item during cloning.
Definition propagate.hpp:65
Gecode::Int::BinPacking::Item::s
int s
Size of item.
Definition bin-packing.hh:57
Gecode::Int::BinPacking::Item::Item
Item(void)
Default constructor.
Definition propagate.hpp:41
Gecode::Int::BinPacking::Item::size
int size(void) const
Return size of item.
Definition propagate.hpp:56
Gecode::Int::BinPacking::Pack::l
ViewArray< OffsetView > l
Views for load of bins.
Definition bin-packing.hh:144
Gecode::Int::BinPacking::Pack::bs
ViewArray< Item > bs
Items with bin and size.
Definition bin-packing.hh:146
Gecode::Int::BinPacking::Pack::Pack
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
Definition propagate.hpp:150
Gecode::Int::BinPacking::Pack::t
int t
Total size of all items.
Definition bin-packing.hh:148
Gecode::Int::BinPacking::Pack::nosum
bool nosum(const SizeSet &s, int a, int b, int &ap, int &bp)
Detect non-existence of sums in a .. b.
Definition propagate.hpp:175
Gecode::Int::BinPacking::Pack::dispose
virtual size_t dispose(Space &home)
Destructor.
Definition propagate.hpp:166
Gecode::Int::BinPacking::SizeSetMinusOne::operator[]
int operator[](int i) const
Return size of item i.
Definition propagate.hpp:137
Gecode::Int::BinPacking::SizeSetMinusOne::minus
void minus(int s)
Discard size s.
Definition propagate.hpp:119
Gecode::Int::BinPacking::SizeSetMinusOne::SizeSetMinusOne
SizeSetMinusOne(void)
Default constructor.
Definition propagate.hpp:114
Gecode::Int::BinPacking::SizeSetMinusOne::p
int p
Position of discarded item.
Definition bin-packing.hh:114
Gecode::Int::BinPacking::SizeSetMinusOne::total
int total(void) const
Return total size.
Definition propagate.hpp:132
Gecode::Int::BinPacking::SizeSetMinusOne::card
int card(void) const
Return cardinality of set (number of entries).
Definition propagate.hpp:127
Gecode::Int::BinPacking::SizeSet
Size sets.
Definition bin-packing.hh:87
Gecode::Int::BinPacking::SizeSet::t
int t
Total size of the set.
Definition bin-packing.hh:92
Gecode::Int::BinPacking::SizeSet::SizeSet
SizeSet(void)
Default constructor.
Definition propagate.hpp:92
Gecode::Int::BinPacking::SizeSet::add
void add(int s)
Add new size s.
Definition propagate.hpp:97
Gecode::Int::BinPacking::SizeSet::total
int total(void) const
Return total size.
Definition propagate.hpp:105
Gecode::Int::BinPacking::SizeSet::operator[]
int operator[](int i) const
Return size of item i.
Definition propagate.hpp:109
Gecode::Int::BinPacking::SizeSet::n
int n
Number of size entries in the set.
Definition bin-packing.hh:90
Gecode::Int::BinPacking::SizeSet::s
int * s
Array of sizes (will have more elements).
Definition bin-packing.hh:94
Gecode::Int::BinPacking::SizeSet::card
int card(void) const
Return cardinality of set (number of entries).
Definition propagate.hpp:101
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
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::Int::BinPacking
Bin-packing propagators
Gecode::Int::BinPacking::operator<
bool operator<(const Item &i, const Item &j)
Order, also for sorting according to size.
Definition propagate.hpp:82
Gecode::Int::BinPacking::operator!=
bool operator!=(const Item &i, const Item &j)
Whether two items are not the same.
Definition propagate.hpp:76
Gecode::Int::BinPacking::operator==
bool operator==(const Item &i, const Item &j)
Whether two items are the same.
Definition propagate.hpp:72
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
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187