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