Generated on Fri Oct 19 11:25:01 2018 for Gecode by doxygen 1.6.3

propagate.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2010
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Int { namespace BinPacking {
00035 
00036   /*
00037    * Item
00038    *
00039    */
00040   forceinline
00041   Item::Item(void)
00042     : s(0) {}
00043   forceinline
00044   Item::Item(IntView b, int s0)
00045     : DerivedView<IntView>(b), s(s0) {}
00046 
00047   forceinline IntView
00048   Item::bin(void) const {
00049     return x;
00050   }
00051   forceinline
00052   void Item::bin(IntView b) {
00053     x = b;
00054   }
00055   forceinline int
00056   Item::size(void) const {
00057     return s;
00058   }
00059   forceinline void
00060   Item::size(int s0) {
00061     s = s0;
00062   }
00063 
00064   forceinline void
00065   Item::update(Space& home, Item& i) {
00066     x.update(home,i.x);
00067     s = i.s;
00068   }
00069 
00070 
00071   forceinline bool
00072   operator ==(const Item& i, const Item& j) {
00073     return (i.bin() == j.bin()) && (i.size() == j.size());
00074   }
00075   forceinline bool
00076   operator !=(const Item& i, const Item& j) {
00077     return !(i == j);
00078   }
00079 
00081   forceinline bool
00082   operator <(const Item& i, const Item& j) {
00083     return ((i.size() > j.size()) ||
00084             ((i.size() == j.size()) && (i.bin() < j.bin())));
00085   }
00086 
00087 
00088   /*
00089    * Size set
00090    *
00091    */
00092   forceinline
00093   SizeSet::SizeSet(void) {}
00094   forceinline
00095   SizeSet::SizeSet(Region& region, int n_max)
00096     : n(0), t(0), s(region.alloc<int>(n_max)) {}
00097   forceinline void
00098   SizeSet::add(int s0) {
00099     t += s0; s[n++] = s0;
00100   }
00101   forceinline int
00102   SizeSet::card(void) const {
00103     return n;
00104   }
00105   forceinline int
00106   SizeSet::total(void) const {
00107     return t;
00108   }
00109   forceinline int
00110   SizeSet::operator [](int i) const {
00111     return s[i];
00112   }
00113 
00114   forceinline
00115   SizeSetMinusOne::SizeSetMinusOne(void) {}
00116   forceinline
00117   SizeSetMinusOne::SizeSetMinusOne(Region& region, int n_max)
00118     : SizeSet(region,n_max), p(-1) {}
00119   forceinline void
00120   SizeSetMinusOne::minus(int s0) {
00121     // This rests on the fact that items are removed in order
00122     do
00123       p++;
00124     while (s[p] > s0);
00125     assert(p < n);
00126   }
00127   forceinline int
00128   SizeSetMinusOne::card(void) const {
00129     assert(p >= 0);
00130     return n - 1;
00131   }
00132   forceinline int
00133   SizeSetMinusOne::total(void) const {
00134     assert(p >= 0);
00135     return t - s[p];
00136   }
00137   forceinline int
00138   SizeSetMinusOne::operator [](int i) const {
00139     assert(p >= 0);
00140     return s[(i < p) ? i : i+1];
00141   }
00142 
00143 
00144 
00145   /*
00146    * Packing propagator
00147    *
00148    */
00149 
00150   forceinline
00151   Pack::Pack(Home home, ViewArray<OffsetView>& l0, ViewArray<Item>& bs0)
00152     : Propagator(home), l(l0), bs(bs0), t(0) {
00153     l.subscribe(home,*this,PC_INT_BND);
00154     bs.subscribe(home,*this,PC_INT_DOM);
00155     for (int i=0; i<bs.size(); i++)
00156       t += bs[i].size();
00157   }
00158 
00159   forceinline
00160   Pack::Pack(Space& home, Pack& p)
00161     : Propagator(home,p), t(p.t) {
00162     l.update(home,p.l);
00163     bs.update(home,p.bs);
00164   }
00165 
00166   forceinline size_t
00167   Pack::dispose(Space& home) {
00168     l.cancel(home,*this,PC_INT_BND);
00169     bs.cancel(home,*this,PC_INT_DOM);
00170     (void) Propagator::dispose(home);
00171     return sizeof(*this);
00172   }
00173 
00174   template<class SizeSet>
00175   forceinline bool
00176   Pack::nosum(const SizeSet& s, int a, int b, int& ap, int& bp) {
00177     if ((a <= 0) || (b >= s.total()))
00178       return false;
00179     int n=s.card()-1;
00180     int sc=0;
00181     int kp=0;
00182     while (sc + s[n-kp] < a) {
00183       sc += s[n-kp];
00184       kp++;
00185     }
00186     int k=0;
00187     int sa=0, sb = s[n-kp];
00188     while ((sa < a) && (sb <= b)) {
00189       sa += s[k++];
00190       if (sa < a) {
00191         kp--;
00192         sb += s[n-kp];
00193         sc -= s[n-kp];
00194         while (sa + sc >= a) {
00195           kp--;
00196           sc -= s[n-kp];
00197           sb += s[n-kp] - s[n-kp-k-1];
00198         }
00199       }
00200     }
00201     ap = sa + sc; bp = sb;
00202     return sa < a;
00203   }
00204 
00205   template<class SizeSet>
00206   forceinline bool
00207   Pack::nosum(const SizeSet& s, int a, int b) {
00208     int ap, bp;
00209     return nosum(s, a, b, ap, bp);
00210   }
00211 
00212 }}}
00213 
00214 // STATISTICS: int-prop
00215