00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode { namespace Int { namespace GCC {
00023
00045 template <class View, class Card, bool shared>
00046 inline ExecStatus
00047 lbc(Space* home, ViewArray<View>& x, int& nb,
00048 HallInfo hall[], Rank rank[],
00049 PartialSum<Card>* lps,
00050 int mu[], int nu[]){
00051
00052 ExecStatus es = ES_FIX;
00053 int n = x.size();
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088 int i = 0;
00089 int j = 0;
00090 int w = 0;
00091 int z = 0;
00092 int v = 0;
00093
00094
00095 int rightmost = nb + 1;
00096 int bsize = nb + 2;
00097 w = rightmost;
00098
00099
00100
00101 hall[0].d = 0;
00102 hall[0].s = 0;
00103 hall[0].ps = 0;
00104
00105 for (i = bsize; --i; ) {
00106 int pred = i - 1;
00107 hall[i].s = pred;
00108 hall[i].ps = pred;
00109 hall[i].d = lps->sumup(hall[pred].bounds, hall[i].bounds - 1);
00110
00111
00112
00113
00114
00115
00116 if (hall[i].d == 0) {
00117 hall[pred].h = w;
00118 } else {
00119 hall[w].h = pred;
00120 w = pred;
00121 }
00122 }
00123
00124 w = rightmost;
00125 for (i = bsize; i--; ) {
00126 hall[i].t = i - 1;
00127 if (hall[i].d == 0) {
00128 hall[i].t = w;
00129 } else {
00130 hall[w].t = i;
00131 w = i;
00132 }
00133 }
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147 for (i = 0; i < n; i++) {
00148
00149 int x0 = rank[mu[i]].min;
00150 int y = rank[mu[i]].max;
00151 int succ = x0 + 1;
00152 z = pathmax_t(hall, succ);
00153 j = hall[z].t;
00154
00155
00156
00157
00158
00159
00160
00161
00162 if (z != succ) {
00163 w = pathmax_ps(hall, succ);
00164 v = hall[w].ps;
00165 pathset_ps(hall, succ, w, w);
00166 w = std::min(y, z);
00167 pathset_ps(hall, hall[w].ps, v, w);
00168 hall[w].ps = v;
00169 }
00170
00171
00172
00173
00174
00175
00176
00177
00178 if (hall[z].d <= lps->sumup(hall[y].bounds, hall[z].bounds - 1)) {
00179 w = pathmax_s(hall, hall[y].ps);
00180 pathset_s(hall, hall[y].ps, w, w);
00181
00182 v = hall[w].s;
00183 pathset_s(hall, hall[y].s, v, y);
00184 hall[y].s = v;
00185 } else {
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195 if (--hall[z].d == 0) {
00196 hall[z].t = z + 1;
00197 z = pathmax_t(hall, hall[z].t);
00198 hall[z].t = j;
00199 }
00200
00201
00202
00203
00204
00205
00206
00207 if (hall[x0].h > x0) {
00208 hall[i].newBound = pathmax_h(hall, x0);
00209 w = hall[i].newBound;
00210 pathset_h(hall, x0, w, w);
00211 } else {
00212
00213 hall[i].newBound = x0;
00214 }
00215
00216
00217
00218
00219
00220
00221
00222
00223 if (hall[z].d == lps->sumup(hall[y].bounds, hall[z].bounds - 1)) {
00224 if (hall[y].h > y)
00225
00226
00227
00228
00229 y = hall[y].h;
00230
00231 int predj = j - 1;
00232 pathset_h(hall, hall[y].h, predj, y);
00233
00234 hall[y].h = predj;
00235 }
00236 }
00237 pathset_t(hall, succ, z, z);
00238 }
00239
00240
00241
00242
00243
00244
00245 if (hall[nb].h != 0) {
00246 return ES_FAILED;
00247 }
00248
00249
00250
00251
00252
00253
00254 for (i = bsize; --i;) {
00255 if (hall[i].s > i) {
00256 hall[i].s = w;
00257 } else {
00258 w = i;
00259 }
00260 }
00261
00262
00263
00264
00265
00266
00267
00268
00269 for (i = n; i--; ) {
00270 int x0 = rank[mu[i]].min;
00271 int y = rank[mu[i]].max;
00272
00273 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
00274
00275 int m = lps->skipNonNullElementsRight(hall[hall[i].newBound].bounds);
00276 ModEvent me = x[mu[i]].gq(home, m);
00277 GECODE_ME_CHECK(me);
00278 if (me_modified(me) && m != x[mu[i]].min()) {
00279 es = ES_NOFIX;
00280 }
00281 if (shared && me_modified(me)) {
00282 es = ES_NOFIX;
00283 }
00284 }
00285 }
00286
00287
00288
00289 w = 0;
00290 for (i = 0; i <= nb; i++) {
00291 hall[i].d = lps->sumup(hall[i].bounds, hall[i + 1].bounds - 1);
00292 if (hall[i].d == 0) {
00293 hall[i].t = w;
00294 } else {
00295 hall[w].t = i;
00296 w = i;
00297 }
00298 }
00299 hall[w].t = i;
00300
00301 w = 0;
00302 for (i = 1; i <= nb; i++) {
00303 if (hall[i - 1].d == 0) {
00304 hall[i].h = w;
00305 } else {
00306 hall[w].h = i;
00307 w = i;
00308 }
00309 }
00310 hall[w].h = i;
00311
00312 for (i = n; i--; ) {
00313
00314
00315 int x0 = rank[nu[i]].max;
00316 int y = rank[nu[i]].min;
00317 int pred = x0 - 1;
00318 z = pathmin_t(hall, pred);
00319 j = hall[z].t;
00320
00321
00322
00323
00324 if (hall[z].d > lps->sumup(hall[z].bounds, hall[y].bounds - 1)) {
00325
00326 if (--hall[z].d == 0) {
00327 hall[z].t = z - 1;
00328 z = pathmin_t(hall, hall[z].t);
00329 hall[z].t = j;
00330 }
00331
00332 if (hall[x0].h < x0) {
00333 w = pathmin_h(hall, hall[x0].h);
00334 hall[i].newBound = w;
00335 pathset_h(hall, x0, w, w);
00336 } else {
00337 hall[i].newBound = x0;
00338 }
00339
00340 if (hall[z].d == lps->sumup(hall[z].bounds, hall[y].bounds - 1)) {
00341 if (hall[y].h < y) {
00342 y = hall[y].h;
00343 }
00344 int succj = j + 1;
00345
00346 pathset_h(hall, hall[y].h, succj, y);
00347 hall[y].h = succj;
00348 }
00349 }
00350 pathset_t(hall, pred, z, z);
00351 }
00352
00353
00354 for (i = n; i--; ) {
00355 int x0 = rank[nu[i]].min;
00356 int y = rank[nu[i]].max;
00357 if ((hall[x0].s <= x0) || (y > hall[x0].s)){
00358 int m = lps->skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
00359 ModEvent me = x[nu[i]].lq(home, m);
00360 GECODE_ME_CHECK(me);
00361 if (me_modified(me) && m != x[nu[i]].max()) {
00362 es = ES_NOFIX;
00363 }
00364 if (shared && me_modified(me)) {
00365 es = ES_NOFIX;
00366 }
00367 }
00368 }
00369 return es;
00370 }
00371
00372 }}}
00373
00374
00375