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 void
00053 Pack::reschedule(Space& home) {
00054 l.reschedule(home,*this,PC_INT_BND);
00055 bs.reschedule(home,*this,PC_INT_DOM);
00056 }
00057
00058 Actor*
00059 Pack::copy(Space& home, bool share) {
00060 return new (home) Pack(home,share,*this);
00061 }
00062
00064 class TellCache {
00065 protected:
00067 int* _nq;
00069 int _n_nq;
00071 int _eq;
00072 public:
00074 TellCache(Region& region, int m);
00076 void nq(int j);
00078 void eq(int j);
00080 ExecStatus tell(Space& home, IntView x);
00081 };
00082
00083 forceinline
00084 TellCache::TellCache(Region& region, int m)
00085 : _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {}
00086 forceinline void
00087 TellCache::nq(int j) {
00088 _nq[_n_nq++] = j;
00089 }
00090 forceinline void
00091 TellCache::eq(int j) {
00092
00093 if (_eq == -1)
00094 _eq = j;
00095 else
00096 _eq = -2;
00097 }
00098 ExecStatus
00099 TellCache::tell(Space& home, IntView x) {
00100 if (_eq == -2) {
00101 return ES_FAILED;
00102 } else if (_eq >= 0) {
00103 GECODE_ME_CHECK(x.eq(home,_eq));
00104 }
00105 Iter::Values::Array nqi(_nq, _n_nq);
00106 GECODE_ME_CHECK(x.minus_v(home, nqi));
00107 _n_nq=0; _eq=-1;
00108 return ES_OK;
00109 }
00110
00111
00112
00113
00114
00115
00116 ExecStatus
00117 Pack::propagate(Space& home, const ModEventDelta& med) {
00118
00119 int n = bs.size();
00120
00121 int m = l.size();
00122
00123 {
00124 Region region(home);
00125
00126
00127 int* s = region.alloc<int>(m);
00128
00129 for (int j=m; j--; )
00130 s[j] = 0;
00131
00132
00133 if (OffsetView::me(med) == ME_INT_VAL) {
00134
00135 int k=0;
00136 for (int i=0; i<n; i++)
00137 if (bs[i].assigned()) {
00138 int j = bs[i].bin().val();
00139 l[j].offset(l[j].offset() - bs[i].size());
00140 t -= bs[i].size();
00141 } else {
00142 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00143 s[j.val()] += bs[i].size();
00144 bs[k++] = bs[i];
00145 }
00146 n=k; bs.size(n);
00147 } else {
00148 for (int i=n; i--; ) {
00149 assert(!bs[i].assigned());
00150 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00151 s[j.val()] += bs[i].size();
00152 }
00153 }
00154
00155
00156 int min = t, max = t;
00157 for (int j=m; j--; ) {
00158 GECODE_ME_CHECK(l[j].gq(home,0));
00159 GECODE_ME_CHECK(l[j].lq(home,s[j]));
00160 min -= l[j].max(); max -= l[j].min();
00161 }
00162
00163
00164 for (bool mod = true; mod; ) {
00165 mod = false; ModEvent me;
00166 for (int j=m; j--; ) {
00167 int lj_min = l[j].min();
00168 me = l[j].gq(home, min + l[j].max());
00169 if (me_failed(me))
00170 return ES_FAILED;
00171 if (me_modified(me)) {
00172 max += lj_min - l[j].min(); mod = true;
00173 }
00174 int lj_max = l[j].max();
00175 me = l[j].lq(home, max + l[j].min());
00176 if (me_failed(me))
00177 return ES_FAILED;
00178 if (me_modified(me)) {
00179 min += lj_max - l[j].max(); mod = true;
00180 }
00181 }
00182 }
00183
00184 if (n == 0) {
00185 assert(l.assigned());
00186 return home.ES_SUBSUMED(*this);
00187 }
00188
00189
00190 {
00191 TellCache tc(region,m);
00192
00193 int k=0;
00194 for (int i=0; i<n; i++) {
00195 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
00196 if (bs[i].size() > l[j.val()].max())
00197 tc.nq(j.val());
00198 if (s[j.val()] - bs[i].size() < l[j.val()].min())
00199 tc.eq(j.val());
00200 }
00201 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
00202
00203 if (bs[i].assigned()) {
00204 int j = bs[i].bin().val();
00205 l[j].offset(l[j].offset() - bs[i].size());
00206 t -= bs[i].size();
00207 } else {
00208 bs[k++] = bs[i];
00209 }
00210 }
00211 n=k; bs.size(n);
00212 }
00213
00214 }
00215
00216
00217
00218 if (IntView::me(modeventdelta()) != ME_INT_NONE)
00219 return ES_NOFIX;
00220
00221
00222 {
00223 Region region(home);
00224
00225
00226 SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m);
00227
00228 for (int j=m; j--; )
00229 s[j] = SizeSetMinusOne(region,n);
00230
00231
00232 for (int i=0; i<n; i++) {
00233 assert(!bs[i].assigned());
00234 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00235 s[j.val()].add(bs[i].size());
00236 }
00237
00238 for (int j=m; j--; ) {
00239
00240 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max()))
00241 return ES_FAILED;
00242 int ap, bp;
00243
00244 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].min(),
00245 ap, bp))
00246 GECODE_ME_CHECK(l[j].gq(home,bp));
00247
00248 if (nosum(static_cast<SizeSet&>(s[j]), l[j].max(), l[j].max(),
00249 ap, bp))
00250 GECODE_ME_CHECK(l[j].lq(home,ap));
00251 }
00252
00253 TellCache tc(region,m);
00254
00255 int k=0;
00256 for (int i=0; i<n; i++) {
00257 assert(!bs[i].assigned());
00258 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
00259
00260 s[j.val()].minus(bs[i].size());
00261
00262 if (nosum(s[j.val()],
00263 l[j.val()].min() - bs[i].size(),
00264 l[j.val()].max() - bs[i].size()))
00265 tc.nq(j.val());
00266
00267 if (nosum(s[j.val()], l[j.val()].min(), l[j.val()].max()))
00268 tc.eq(j.val());
00269 }
00270 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
00271 if (bs[i].assigned()) {
00272 int j = bs[i].bin().val();
00273 l[j].offset(l[j].offset() - bs[i].size());
00274 t -= bs[i].size();
00275 } else {
00276 bs[k++] = bs[i];
00277 }
00278 }
00279 n=k; bs.size(n);
00280 }
00281
00282
00283 if (n > 0) {
00284 Region region(home);
00285
00286
00287
00288 int c = bs[0].size();
00289 for (int j=m; j--; )
00290 c = std::max(c,l[j].max());
00291
00292
00293 int* n_s = region.alloc<int>(c+1);
00294
00295 for (int i=c+1; i--; )
00296 n_s[i] = 0;
00297
00298
00299 for (int i=n; i--; )
00300 n_s[bs[i].size()]++;
00301
00302
00303 int nm = n;
00304
00305
00306 for (int j=m; j--; )
00307 if (l[j].max() < 0) {
00308 return ES_FAILED;
00309 } else if (c > l[j].max()) {
00310 n_s[c - l[j].max()]++; nm++;
00311 }
00312
00313
00314 int* s = region.alloc<int>(nm);
00315
00316
00317 {
00318 int k=0;
00319 for (int i=c+1; i--; )
00320 for (int j=n_s[i]; j--; )
00321 s[k++]=i;
00322 assert(k == nm);
00323 }
00324
00325
00326 int n1 = 0;
00327
00328 int n12 = 0;
00329
00330 int n3 = 0;
00331
00332 int f2 = 0;
00333
00334 int s3 = 0;
00335
00336
00337 for (; (n12 < nm) && (s[n12] > c/2); n12++)
00338 f2 += c - s[n12];
00339
00340
00341 for (n3 = n12; n3 < nm; n3++)
00342 s3 += s[n3];
00343
00344
00345 for (int k=0; k<=c/2; k++) {
00346
00347 for (; (n1 < nm) && (s[n1] > c-k); n1++)
00348 f2 -= c - s[n1];
00349 assert(n1 <= n12);
00350
00351 for (; (s[n3-1] < k) && (n3 > n12); n3--)
00352 s3 -= s[n3-1];
00353
00354 int o = (s3 > f2) ? ((s3 - f2 + c - 1) / c) : 0;
00355 if (n12 + o > m)
00356 return ES_FAILED;
00357 }
00358 }
00359
00360 return ES_NOFIX;
00361 }
00362
00363 ExecStatus
00364 Pack::post(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs) {
00365
00366 Support::quicksort(&bs[0], bs.size());
00367
00368 int s = 0;
00369
00370 for (int i=bs.size(); i--; ) {
00371 s += bs[i].size();
00372 GECODE_ME_CHECK(bs[i].bin().gq(home,0));
00373 GECODE_ME_CHECK(bs[i].bin().le(home,l.size()));
00374 }
00375
00376 {
00377 int n = bs.size();
00378 while ((n > 0) && (bs[n-1].size() == 0))
00379 n--;
00380 bs.size(n);
00381 }
00382 if (bs.size() == 0) {
00383
00384 for (int i=l.size(); i--; )
00385 GECODE_ME_CHECK(l[i].eq(home,0));
00386 return ES_OK;
00387 } else if (l.size() == 0) {
00388
00389 return ES_FAILED;
00390 } else {
00391
00392 for (int j=l.size(); j--; ) {
00393 GECODE_ME_CHECK(l[j].gq(home,0));
00394 GECODE_ME_CHECK(l[j].lq(home,s));
00395 }
00396 (void) new (home) Pack(home,l,bs);
00397 return ES_OK;
00398 }
00399 }
00400
00401 }}}
00402
00403
00404