bnd-sup.hpp
Go to the documentation of this file.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
00039
00040
00041
00042
00043
00044 namespace Gecode { namespace Int { namespace GCC {
00045
00058 class UnReachable {
00059 public:
00061 int minb;
00063 int maxb;
00065 int eq;
00067 int le;
00069 int gr;
00070 };
00071
00077 template<class Card>
00078 ExecStatus
00079 prop_card(Space& home,
00080 ViewArray<IntView>& x, ViewArray<Card>& k) {
00081 int n = x.size();
00082 int m = k.size();
00083 Region r(home);
00084 UnReachable* rv = r.alloc<UnReachable>(m);
00085 for(int i = m; i--; )
00086 rv[i].minb=rv[i].maxb=rv[i].le=rv[i].gr=rv[i].eq=0;
00087
00088 for (int i = n; i--; ) {
00089 int min_idx;
00090 if (!lookupValue(k,x[i].min(),min_idx))
00091 return ES_FAILED;
00092 if (x[i].assigned()) {
00093 rv[min_idx].minb++;
00094 rv[min_idx].maxb++;
00095 rv[min_idx].eq++;
00096 } else {
00097
00098
00099 rv[min_idx].minb++;
00100 int max_idx;
00101 if (!lookupValue(k,x[i].max(),max_idx))
00102 return ES_FAILED;
00103
00104
00105 rv[max_idx].maxb++;
00106 }
00107 }
00108
00109 rv[0].le = 0;
00110 int c_min = 0;
00111 for (int i = 1; i < m; i++) {
00112 rv[i].le = c_min + rv[i - 1].maxb;
00113 c_min += rv[i - 1].maxb;
00114 }
00115
00116 rv[m-1].gr = 0;
00117 int c_max = 0;
00118 for (int i = m-1; i--; ) {
00119 rv[i].gr = c_max + rv[i + 1].minb;
00120 c_max += rv[i + 1].minb;
00121 }
00122
00123 for (int i = m; i--; ) {
00124 int reachable = x.size() - rv[i].le - rv[i].gr;
00125 if (!k[i].assigned()) {
00126 GECODE_ME_CHECK(k[i].lq(home, reachable));
00127 GECODE_ME_CHECK(k[i].gq(home, rv[i].eq));
00128 } else {
00129
00130 if ((rv[i].eq > k[i].max()) || (k[i].max() > reachable))
00131 return ES_FAILED;
00132 }
00133 }
00134
00135 return ES_OK;
00136 }
00137
00138
00142 template<class Card>
00143 forceinline bool
00144 card_consistent(ViewArray<IntView>& x, ViewArray<Card>& k) {
00145 int smin = 0;
00146 int smax = 0;
00147 for (int i = k.size(); i--; ) {
00148 smax += k[i].max();
00149 smin += k[i].min();
00150 }
00151
00152 return (smin <= x.size()) && (x.size() <= smax);
00153 }
00154
00159 class Rank {
00160 public:
00165 int min;
00170 int max;
00171 };
00172
00180 template<class View>
00181 class MaxInc {
00182 protected:
00184 ViewArray<View> x;
00185 public:
00187 MaxInc(const ViewArray<View>& x0) : x(x0) {}
00189 forceinline bool
00190 operator ()(const int i, const int j) {
00191 return x[i].max() < x[j].max();
00192 }
00193 };
00194
00195
00203 template<class View>
00204 class MinInc {
00205 protected:
00207 ViewArray<View> x;
00208 public:
00210 MinInc(const ViewArray<View>& x0) : x(x0) {}
00212 forceinline bool
00213 operator ()(const int i, const int j) {
00214 return x[i].min() < x[j].min();
00215 }
00216 };
00217
00218
00225 template<class Card>
00226 class MinIdx {
00227 public:
00229 forceinline bool
00230 operator ()(const Card& x, const Card& y) {
00231 return x.card() < y.card();
00232 }
00233 };
00234
00241 template<class Card>
00242 class PartialSum {
00243 private:
00245 int* sum;
00247 int size;
00248 public:
00250 int firstValue, lastValue;
00252
00253
00254 PartialSum(void);
00256 void init(Space& home, ViewArray<Card>& k, bool up);
00258 void reinit(void);
00260 bool initialized(void) const;
00262
00263
00264
00265 int sumup(int from, int to) const;
00267 int minValue(void) const;
00269 int maxValue(void) const;
00271 int skipNonNullElementsRight(int v) const;
00273 int skipNonNullElementsLeft(int v) const;
00275
00276
00277
00284 bool check_update_min(ViewArray<Card>& k);
00292 bool check_update_max(ViewArray<Card>& k);
00294 };
00295
00296
00297 template<class Card>
00298 forceinline
00299 PartialSum<Card>::PartialSum(void) : sum(NULL), size(-1) {}
00300
00301 template<class Card>
00302 forceinline bool
00303 PartialSum<Card>::initialized(void) const {
00304 return size != -1;
00305 }
00306 template<class Card>
00307 inline void
00308 PartialSum<Card>::init(Space& home, ViewArray<Card>& elements, bool up) {
00309 int i = 0;
00310 int j = 0;
00311
00312
00313 int holes = 0;
00314 for (i = 1; i < elements.size(); i++) {
00315 if (elements[i].card() != elements[i-1].card() + 1)
00316 holes += elements[i].card()-elements[i-1].card()-1;
00317 }
00318
00319
00320 size = elements.size() + holes + 5;
00321
00322
00323 if (sum == NULL) {
00324 sum = home.alloc<int>(2*size);
00325 }
00326 int* ds = &sum[size];
00327
00328 int first = elements[0].card();
00329
00330 firstValue = first - 3;
00331 lastValue = first + elements.size() + holes + 1;
00332
00333
00334 for (i = 3; i--; )
00335 sum[i] = i;
00336
00337
00338
00339
00340 int prevCard = elements[0].card()-1;
00341 i = 0;
00342 for (j = 2; j < elements.size() + holes + 2; j++) {
00343 if (elements[i].card() != prevCard + 1) {
00344 sum[j + 1] = sum[j];
00345 } else if (up) {
00346 sum[j + 1] = sum[j] + elements[i].max();
00347 i++;
00348 } else {
00349 sum[j + 1] = sum[j] + elements[i].min();
00350 i++;
00351 }
00352 prevCard++;
00353 }
00354 sum[j + 1] = sum[j] + 1;
00355 sum[j + 2] = sum[j + 1] + 1;
00356
00357
00358 i = elements.size() + holes + 3;
00359 j = i + 1;
00360 for ( ; i > 0; ) {
00361 while(sum[i] == sum[i - 1]) {
00362 ds[i] = j;
00363 i--;
00364 }
00365 ds[j] = i;
00366 i--;
00367 j = ds[j];
00368 }
00369 ds[j] = 0;
00370 ds[0] = 0;
00371 }
00372
00373 template<class Card>
00374 forceinline void
00375 PartialSum<Card>::reinit(void) {
00376 size = -1;
00377 }
00378
00379
00380 template<class Card>
00381 forceinline int
00382 PartialSum<Card>::sumup(int from, int to) const {
00383 if (from <= to) {
00384 return sum[to - firstValue] - sum[from - firstValue - 1];
00385 } else {
00386 assert(to - firstValue - 1 >= 0);
00387 assert(to - firstValue - 1 < size);
00388 assert(from - firstValue >= 0);
00389 assert(from - firstValue < size);
00390 return sum[to - firstValue - 1] - sum[from - firstValue];
00391 }
00392 }
00393
00394 template<class Card>
00395 forceinline int
00396 PartialSum<Card>::minValue(void) const {
00397 return firstValue + 3;
00398 }
00399 template<class Card>
00400 forceinline int
00401 PartialSum<Card>::maxValue(void) const {
00402 return lastValue - 2;
00403 }
00404
00405
00406 template<class Card>
00407 forceinline int
00408 PartialSum<Card>::skipNonNullElementsRight(int value) const {
00409 value -= firstValue;
00410 int* ds = &sum[size];
00411 return (ds[value] < value ? value : ds[value]) + firstValue;
00412 }
00413 template<class Card>
00414 forceinline int
00415 PartialSum<Card>::skipNonNullElementsLeft(int value) const {
00416 value -= firstValue;
00417 int* ds = &sum[size];
00418 return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00419 }
00420
00421 template<class Card>
00422 inline bool
00423 PartialSum<Card>::check_update_max(ViewArray<Card>& k) {
00424 int j = 0;
00425 for (int i = 3; i < size - 2; i++) {
00426 int max = 0;
00427 if (k[j].card() == i+firstValue)
00428 max = k[j++].max();
00429 if ((sum[i] - sum[i - 1]) != max)
00430 return true;
00431 }
00432 return false;
00433 }
00434
00435 template<class Card>
00436 inline bool
00437 PartialSum<Card>::check_update_min(ViewArray<Card>& k) {
00438 int j = 0;
00439 for (int i = 3; i < size - 2; i++) {
00440 int min = 0;
00441 if (k[j].card() == i+firstValue)
00442 min = k[j++].min();
00443 if ((sum[i] - sum[i - 1]) != min)
00444 return true;
00445 }
00446 return false;
00447 }
00448
00449
00461 class HallInfo {
00462 public:
00464 int bounds;
00470 int t;
00478 int d;
00487 int h;
00489 int s;
00491 int ps;
00498 int newBound;
00499 };
00500
00501
00510
00511 forceinline void
00512 pathset_ps(HallInfo hall[], int start, int end, int to) {
00513 int k, l;
00514 for (l=start; (k=l) != end; hall[k].ps=to) {
00515 l = hall[k].ps;
00516 }
00517 }
00519 forceinline void
00520 pathset_s(HallInfo hall[], int start, int end, int to) {
00521 int k, l;
00522 for (l=start; (k=l) != end; hall[k].s=to) {
00523 l = hall[k].s;
00524 }
00525 }
00527 forceinline void
00528 pathset_t(HallInfo hall[], int start, int end, int to) {
00529 int k, l;
00530 for (l=start; (k=l) != end; hall[k].t=to) {
00531 l = hall[k].t;
00532 }
00533 }
00535 forceinline void
00536 pathset_h(HallInfo hall[], int start, int end, int to) {
00537 int k, l;
00538 for (l=start; (k=l) != end; hall[k].h=to) {
00539 l = hall[k].h;
00540 assert(l != k);
00541 }
00542 }
00544
00552
00553 forceinline int
00554 pathmin_h(const HallInfo hall[], int i) {
00555 while (hall[i].h < i)
00556 i = hall[i].h;
00557 return i;
00558 }
00560 forceinline int
00561 pathmin_t(const HallInfo hall[], int i) {
00562 while (hall[i].t < i)
00563 i = hall[i].t;
00564 return i;
00565 }
00567
00575
00576 forceinline int
00577 pathmax_h(const HallInfo hall[], int i) {
00578 while (hall[i].h > i)
00579 i = hall[i].h;
00580 return i;
00581 }
00583 forceinline int
00584 pathmax_t(const HallInfo hall[], int i) {
00585 while (hall[i].t > i) {
00586 i = hall[i].t;
00587 }
00588 return i;
00589 }
00591 forceinline int
00592 pathmax_s(const HallInfo hall[], int i) {
00593 while (hall[i].s > i)
00594 i = hall[i].s;
00595 return i;
00596 }
00598 forceinline int
00599 pathmax_ps(const HallInfo hall[], int i) {
00600 while (hall[i].ps > i)
00601 i = hall[i].ps;
00602 return i;
00603 }
00605
00606 }}}
00607
00608
00609