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 forceinline ExecStatus
00047 ubc(Space* home, ViewArray<View>& x, int& nb,
00048 HallInfo hall[], Rank rank[],
00049 PartialSum<Card>* ups,
00050 int mu[], int nu[]){
00051
00052 ExecStatus es = ES_FIX;
00053
00054 int rightmost = nb + 1;
00055 int bsize = nb + 2;
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066 hall[0].h = 0;
00067 hall[0].t = 0;
00068 hall[0].d = 0;
00069
00070 for (int i = 1; i < bsize; i++) {
00071 int pred = i - 1;
00072 hall[i].h = pred;
00073 hall[i].t = pred;
00074 hall[i].d = ups->sumup(hall[pred].bounds, hall[i].bounds - 1);
00075 }
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090 int n = x.size();
00091 for (int i = 0; i < n; i++) {
00092
00093 int x0 = rank[mu[i]].min;
00094 int succ = x0 + 1;
00095 int y = rank[mu[i]].max;
00096 int z = pathmax_t(hall, succ);
00097 int j = hall[z].t;
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114 if (--hall[z].d == 0){
00115 hall[z].t = z + 1;
00116 z = pathmax_t(hall, hall[z].t);
00117 hall[z].t = j;
00118 }
00119 pathset_t(hall, succ, z, z);
00120
00121
00122
00123
00124
00125
00126
00127
00128 if (hall[z].d < ups->sumup(hall[y].bounds, hall[z].bounds - 1)){
00129 return ES_FAILED;
00130 }
00131
00132
00133
00134
00135
00136
00137 if (hall[x0].h > x0) {
00138 int w = pathmax_h(hall, hall[x0].h);
00139 int m = hall[w].bounds;
00140
00141
00142 if (shared && x[mu[i]].modified()) {
00143 es = ES_NOFIX;
00144 }
00145 ModEvent me = x[mu[i]].gq(home, m);
00146 GECODE_ME_CHECK(me);
00147 if (me_modified(me) && (m != x[mu[i]].min())) {
00148 es = ES_NOFIX;
00149 }
00150 pathset_h(hall, x0, w, w);
00151 }
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167 if (hall[z].d == ups->sumup(hall[y].bounds, hall[z].bounds - 1)) {
00168
00169
00170
00171 int predj = j - 1;
00172 pathset_h(hall, hall[y].h, predj, y);
00173 hall[y].h = predj;
00174 }
00175 }
00176
00177
00178
00179
00180 MinInc<View> min_inc(x);
00181 Support::quicksort<int, MinInc<View> >(nu, n, min_inc);
00182
00183
00184
00185
00186
00187
00188 for (int i = 0; i < rightmost; i++) {
00189 int succ = i + 1;
00190 hall[i].h = succ;
00191 hall[i].t = succ;
00192 hall[i].d = ups->sumup(hall[i].bounds, hall[succ].bounds - 1);
00193 }
00194 for (int i = n; i--; ) {
00195
00196 int x0 = rank[nu[i]].max;
00197 int pred = x0 - 1;
00198 int y = rank[nu[i]].min;
00199 int z = pathmin_t(hall, pred);
00200 int j = hall[z].t;
00201
00202
00203 if (--hall[z].d == 0){
00204 hall[z].t = z - 1;
00205 z = pathmin_t(hall, hall[z].t);
00206 hall[z].t = j;
00207 }
00208 pathset_t(hall, pred, z, z);
00209
00210
00211 if (hall[z].d < ups->sumup(hall[z].bounds,hall[y].bounds-1)){
00212 return ES_FAILED;
00213 }
00214
00215
00216
00217
00218
00219
00220 if (hall[x0].h < x0) {
00221 int w = pathmin_h(hall, hall[x0].h);
00222 int m = hall[w].bounds - 1;
00223 if (shared && x[nu[i]].modified()) {
00224 es = ES_NOFIX;
00225 }
00226 ModEvent me = x[nu[i]].lq(home, m);
00227 GECODE_ME_CHECK(me);
00228 if (me_modified(me) && (m != x[nu[i]].max())) {
00229 es = ES_NOFIX;
00230 }
00231 pathset_h(hall, x0, w, w);
00232 }
00233
00234 if (hall[z].d == ups->sumup(hall[z].bounds, hall[y].bounds - 1)) {
00235
00236 int succj = j + 1;
00237 pathset_h(hall, hall[y].h, succj, y);
00238 hall[y].h = succj;
00239 }
00240 }
00241 return es;
00242 }
00243
00244 }}}
00245
00246
00247
00248
00249
00250
00251