00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/int/bin-packing.hh>
00039
00040 namespace Gecode { namespace Int { namespace BinPacking {
00041
00042
00043
00044
00045
00046
00047 PropCost
00048 Pack::cost(const Space&, const ModEventDelta&) const {
00049 return PropCost::quadratic(PropCost::HI,bs.size());
00050 }
00051
00052 Actor*
00053 Pack::copy(Space& home, bool share) {
00054 return new (home) Pack(home,share,*this);
00055 }
00056
00058 class TellCache {
00059 protected:
00061 int* _nq;
00063 int _n_nq;
00065 int _eq;
00066 public:
00068 TellCache(Region& region, int m);
00070 void nq(int j);
00072 void eq(int j);
00074 ExecStatus tell(Space& home, IntView x);
00075 };
00076
00077 forceinline
00078 TellCache::TellCache(Region& region, int m)
00079 : _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {}
00080 forceinline void
00081 TellCache::nq(int j) {
00082 _nq[_n_nq++] = j;
00083 }
00084 forceinline void
00085 TellCache::eq(int j) {
00086
00087 if (_eq == -1)
00088 _eq = j;
00089 else
00090 _eq = -2;
00091 }
00092 ExecStatus
00093 TellCache::tell(Space& home, IntView x) {
00094 if (_eq == -2) {
00095 return ES_FAILED;
00096 } else if (_eq >= 0) {
00097 GECODE_ME_CHECK(x.eq(home,_eq));
00098 }
00099 Iter::Values::Array nqi(_nq, _n_nq);
00100 GECODE_ME_CHECK(x.minus_v(home, nqi));
00101 _n_nq=0; _eq=-1;
00102 return ES_OK;
00103 }
00104
00105
00106
00107
00108
00109
00110 ExecStatus
00111 Pack::propagate(Space& home, const ModEventDelta& med) {
00112
00113 int n = bs.size();
00114
00115 int m = l.size();
00116
00117 {
00118 Region region(home);
00119
00120
00121 int* s = region.alloc<int>(m);
00122
00123 for (int j=m; j--; )
00124 s[j] = 0;
00125
00126
00127 if (OffsetView::me(med) == ME_INT_VAL) {
00128
00129 int k=0;
00130 for (int i=0; i<n; i++)
00131 if (bs[i].assigned()) {
00132 int j = bs[i].bin().val();
00133 l[j].offset(l[j].offset() - bs[i].size());
00134 t -= bs[i].size();
00135 } else {
00136 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00137 s[j.val()] += bs[i].size();
00138 bs[k++] = bs[i];
00139 }
00140 n=k; bs.size(n);
00141 } else {
00142 for (int i=n; i--; ) {
00143 assert(!bs[i].assigned());
00144 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00145 s[j.val()] += bs[i].size();
00146 }
00147 }
00148
00149
00150 int min = t, max = t;
00151 for (int j=m; j--; ) {
00152 GECODE_ME_CHECK(l[j].gq(home,0));
00153 GECODE_ME_CHECK(l[j].lq(home,s[j]));
00154 min -= l[j].max(); max -= l[j].min();
00155 }
00156
00157
00158 for (bool mod = true; mod; ) {
00159 mod = false; ModEvent me;
00160 for (int j=m; j--; ) {
00161 int lj_min = l[j].min();
00162 me = l[j].gq(home, min + l[j].max());
00163 if (me_failed(me))
00164 return ES_FAILED;
00165 if (me_modified(me)) {
00166 max += lj_min - l[j].min(); mod = true;
00167 }
00168 int lj_max = l[j].max();
00169 me = l[j].lq(home, max + l[j].min());
00170 if (me_failed(me))
00171 return ES_FAILED;
00172 if (me_modified(me)) {
00173 min += lj_max - l[j].max(); mod = true;
00174 }
00175 }
00176 }
00177
00178 if (n == 0) {
00179 assert(l.assigned());
00180 return home.ES_SUBSUMED(*this);
00181 }
00182
00183
00184 {
00185 TellCache tc(region,m);
00186
00187 int k=0;
00188 for (int i=0; i<n; i++) {
00189 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
00190 if (bs[i].size() > l[j.val()].max())
00191 tc.nq(j.val());
00192 if (s[j.val()] - bs[i].size() < l[j.val()].min())
00193 tc.eq(j.val());
00194 }
00195 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
00196
00197 if (bs[i].assigned()) {
00198 int j = bs[i].bin().val();
00199 l[j].offset(l[j].offset() - bs[i].size());
00200 t -= bs[i].size();
00201 } else {
00202 bs[k++] = bs[i];
00203 }
00204 }
00205 n=k; bs.size(n);
00206 }
00207
00208 }
00209
00210
00211 {
00212 Region region(home);
00213
00214
00215 SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m);
00216
00217 for (int j=m; j--; )
00218 s[j] = SizeSetMinusOne(region,n);
00219
00220
00221 for (int i=0; i<n; i++) {
00222 assert(!bs[i].assigned());
00223 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00224 s[j.val()].add(bs[i].size());
00225 }
00226
00227 for (int j=m; j--; ) {
00228
00229 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max()))
00230 return ES_FAILED;
00231 int ap, bp;
00232
00233 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].min(),
00234 ap, bp))
00235 GECODE_ME_CHECK(l[j].gq(home,bp));
00236
00237 if (nosum(static_cast<SizeSet&>(s[j]), l[j].max(), l[j].max(),
00238 ap, bp))
00239 GECODE_ME_CHECK(l[j].lq(home,ap));
00240 }
00241
00242 TellCache tc(region,m);
00243
00244 int k=0;
00245 for (int i=0; i<n; i++) {
00246 assert(!bs[i].assigned());
00247 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
00248
00249 s[j.val()].minus(bs[i].size());
00250
00251 if (nosum(s[j.val()],
00252 l[j.val()].min() - bs[i].size(),
00253 l[j.val()].max() - bs[i].size()))
00254 tc.nq(j.val());
00255
00256 if (nosum(s[j.val()], l[j.val()].min(), l[j.val()].max()))
00257 tc.eq(j.val());
00258 }
00259 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
00260 if (bs[i].assigned()) {
00261 int j = bs[i].bin().val();
00262 l[j].offset(l[j].offset() - bs[i].size());
00263 t -= bs[i].size();
00264 } else {
00265 bs[k++] = bs[i];
00266 }
00267 }
00268 n=k; bs.size(n);
00269 }
00270
00271
00272 if (n > 0) {
00273 Region region(home);
00274
00275
00276
00277 int c = bs[0].size();
00278 for (int j=m; j--; )
00279 c = std::max(c,l[j].max());
00280
00281
00282 int* n_s = region.alloc<int>(c+1);
00283
00284 for (int i=c+1; i--; )
00285 n_s[i] = 0;
00286
00287
00288 for (int i=n; i--; )
00289 n_s[bs[i].size()]++;
00290
00291
00292 int nm = n;
00293
00294
00295 for (int j=m; j--; )
00296 if (l[j].max() < 0) {
00297 return ES_FAILED;
00298 } else if (c > l[j].max()) {
00299 n_s[c - l[j].max()]++; nm++;
00300 }
00301
00302
00303 int* s = region.alloc<int>(nm);
00304
00305
00306 {
00307 int k=0;
00308 for (int i=c+1; i--; )
00309 for (int n=n_s[i]; n--; )
00310 s[k++]=i;
00311 assert(k == nm);
00312 }
00313
00314
00315 int n1 = 0;
00316
00317 int n12 = 0;
00318
00319 int n3 = 0;
00320
00321 int f2 = 0;
00322
00323 int s3 = 0;
00324
00325
00326 for (; (n12 < nm) && (s[n12] > c/2); n12++)
00327 f2 += c - s[n12];
00328
00329
00330 for (n3 = n12; n3 < nm; n3++)
00331 s3 += s[n3];
00332
00333
00334 for (int k=0; k<=c/2; k++) {
00335
00336 for (; (n1 < nm) && (s[n1] > c-k); n1++)
00337 f2 -= c - s[n1];
00338 assert(n1 <= n12);
00339
00340 for (; (s[n3-1] < k) && (n3 > n12); n3--)
00341 s3 -= s[n3-1];
00342
00343 int o = (s3 > f2) ? ((s3 - f2 + c - 1) / c) : 0;
00344 if (n12 + o > m)
00345 return ES_FAILED;
00346 }
00347 }
00348
00349 return ES_NOFIX;
00350 }
00351
00352 ExecStatus
00353 Pack::post(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs) {
00354 if (bs.size() == 0) {
00355
00356 for (int i=l.size(); i--; )
00357 GECODE_ME_CHECK(l[i].eq(home,0));
00358 return ES_OK;
00359 } else if (l.size() == 0) {
00360
00361 return ES_FAILED;
00362 } else {
00363 int s = 0;
00364
00365 for (int i=bs.size(); i--; ) {
00366 s += bs[i].size();
00367 GECODE_ME_CHECK(bs[i].bin().gq(home,0));
00368 GECODE_ME_CHECK(bs[i].bin().le(home,l.size()));
00369 }
00370
00371 for (int j=l.size(); j--; ) {
00372 GECODE_ME_CHECK(l[j].gq(home,0));
00373 GECODE_ME_CHECK(l[j].lq(home,s));
00374 }
00375 (void) new (home) Pack(home,l,bs);
00376 return ES_OK;
00377 }
00378 }
00379
00380 }}}
00381
00382
00383