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