Generated on Thu Apr 11 13:59:04 2019 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   }
00085 
00086 
00087   /*
00088    * Size set
00089    *
00090    */
00091   forceinline
00092   SizeSet::SizeSet(void) {}
00093   forceinline
00094   SizeSet::SizeSet(Region& region, int n_max)
00095     : n(0), t(0), s(region.alloc<int>(n_max)) {}
00096   forceinline void
00097   SizeSet::add(int s0) {
00098     t += s0; s[n++] = s0;
00099   }
00100   forceinline int
00101   SizeSet::card(void) const {
00102     return n;
00103   }
00104   forceinline int
00105   SizeSet::total(void) const {
00106     return t;
00107   }
00108   forceinline int
00109   SizeSet::operator [](int i) const {
00110     return s[i];
00111   }
00112 
00113   forceinline
00114   SizeSetMinusOne::SizeSetMinusOne(void) {}
00115   forceinline
00116   SizeSetMinusOne::SizeSetMinusOne(Region& region, int n_max)
00117     : SizeSet(region,n_max), p(-1) {}
00118   forceinline void
00119   SizeSetMinusOne::minus(int s0) {
00120     // This rests on the fact that items are removed in order
00121     do
00122       p++;
00123     while (s[p] > s0);
00124     assert(p < n);
00125   }
00126   forceinline int
00127   SizeSetMinusOne::card(void) const {
00128     assert(p >= 0);
00129     return n - 1;
00130   }
00131   forceinline int
00132   SizeSetMinusOne::total(void) const {
00133     assert(p >= 0);
00134     return t - s[p];
00135   }
00136   forceinline int
00137   SizeSetMinusOne::operator [](int i) const {
00138     assert(p >= 0);
00139     return s[(i < p) ? i : i+1];
00140   }
00141 
00142 
00143 
00144   /*
00145    * Packing propagator
00146    *
00147    */
00148 
00149   forceinline
00150   Pack::Pack(Home home, ViewArray<OffsetView>& l0, ViewArray<Item>& bs0)
00151     : Propagator(home), l(l0), bs(bs0), t(0) {
00152     l.subscribe(home,*this,PC_INT_BND);
00153     bs.subscribe(home,*this,PC_INT_DOM);
00154     for (int i=0; i<bs.size(); i++)
00155       t += bs[i].size();
00156   }
00157 
00158   forceinline
00159   Pack::Pack(Space& home, Pack& p)
00160     : Propagator(home,p), t(p.t) {
00161     l.update(home,p.l);
00162     bs.update(home,p.bs);
00163   }
00164 
00165   forceinline size_t
00166   Pack::dispose(Space& home) {
00167     l.cancel(home,*this,PC_INT_BND);
00168     bs.cancel(home,*this,PC_INT_DOM);
00169     (void) Propagator::dispose(home);
00170     return sizeof(*this);
00171   }
00172 
00173   template<class SizeSet>
00174   forceinline bool
00175   Pack::nosum(const SizeSet& s, int a, int b, int& ap, int& bp) {
00176     if ((a <= 0) || (b >= s.total()))
00177       return false;
00178     int n=s.card()-1;
00179     int sc=0;
00180     int kp=0;
00181     while (sc + s[n-kp] < a) {
00182       sc += s[n-kp];
00183       kp++;
00184     }
00185     int k=0;
00186     int sa=0, sb = s[n-kp];
00187     while ((sa < a) && (sb <= b)) {
00188       sa += s[k++];
00189       if (sa < a) {
00190         kp--;
00191         sb += s[n-kp];
00192         sc -= s[n-kp];
00193         while (sa + sc >= a) {
00194           kp--;
00195           sc -= s[n-kp];
00196           sb += s[n-kp] - s[n-kp-k-1];
00197         }
00198       }
00199     }
00200     ap = sa + sc; bp = sb;
00201     return sa < a;
00202   }
00203 
00204   template<class SizeSet>
00205   forceinline bool
00206   Pack::nosum(const SizeSet& s, int a, int b) {
00207     int ap, bp;
00208     return nosum(s, a, b, ap, bp);
00209   }
00210 
00211 }}}
00212 
00213 // STATISTICS: int-prop
00214