00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifdef NDEBUG
00023 #define START_SIZE
00024 #define END_SIZE
00025 #else
00026 #define START_SIZE int start_size = k.size();
00027 #define END_SIZE int end_size = k.size();
00028 #endif
00029
00030
00031
00032 namespace Gecode { namespace Int { namespace GCC {
00033
00035
00036
00042 class UnReachable {
00043 public:
00044 unsigned int minb;
00045 unsigned int maxb;
00046 unsigned int eq;
00047 unsigned int le;
00048 unsigned int gr;
00049 };
00050
00055 template <class View, class Card, bool shared>
00056 forceinline ExecStatus
00057 prop_card(Space* home, ViewArray<View>& x, ViewArray<Card>& k, bool& mod) {
00058 int n = x.size();
00059 int m = k.size();
00060 GECODE_AUTOARRAY(UnReachable, rv, m);
00061 for(int i = m; i--; ) {
00062 rv[i].minb = 0;
00063 rv[i].maxb = 0;
00064 rv[i].le = 0;
00065 rv[i].gr = 0;
00066 rv[i].eq = 0;
00067 }
00068
00069 for (int i = n; i--; ) {
00070 int b = x[i].assigned();
00071 int min_idx = 0;
00072 int max_idx = 0;
00073 min_idx = lookupValue(k,x[i].min());
00074 if (min_idx == -1) {
00075 return ES_FAILED;
00076 }
00077 if (b) {
00078 rv[min_idx].minb++;
00079 rv[min_idx].maxb++;
00080 rv[min_idx].eq++;
00081 } else {
00082 max_idx = lookupValue(k,x[i].max());
00083 if (max_idx == -1) {
00084 return ES_FAILED;
00085 }
00086
00087
00088 rv[min_idx].minb++;
00089
00090
00091
00092 rv[max_idx].maxb++;
00093 }
00094 }
00095
00096 rv[0].le = 0;
00097 int c_min = 0;
00098 for (int i = 1; i < m; i++) {
00099 rv[i].le = c_min + rv[i - 1].maxb;
00100 c_min += rv[i - 1].maxb;
00101 }
00102
00103 rv[m-1].gr = 0;
00104 int c_max = 0;
00105 for (int i = m-1; i--; ) {
00106 rv[i].gr = c_max + rv[i + 1].minb;
00107 c_max += rv[i + 1].minb;
00108 }
00109
00110 for (int i = m; i--; ) {
00111 int reachable = (int) (x.size() - rv[i].le - rv[i].gr);
00112 if (!k[i].assigned()) {
00113 ModEvent me = k[i].lq(home, reachable);
00114 if (me_failed(me)) {
00115 return ES_FAILED;
00116 }
00117 mod |= (k[i].modified() && (k[i].max() != reachable));
00118 mod |= shared && k[i].modified();
00119
00120 if (rv[i].eq > 0) {
00121 ModEvent me = k[i].gq(home, (int) rv[i].eq);
00122 if (me_failed(me)) {
00123 return ES_FAILED;
00124 }
00125 mod |= (k[i].modified() && (k[i].min() != (int) rv[i].eq));
00126 mod |= shared && k[i].modified();
00127 }
00128 } else {
00129
00130 int v = k[i].max();
00131 if ( !( (int) rv[i].eq <= v && v <= reachable) ) {
00132 return ES_FAILED;
00133 }
00134 }
00135 }
00136
00137 return ES_OK;
00138 }
00139
00140
00144 template <class View, class Card>
00145 inline bool
00146 card_consistent(int& smin, int& smax, ViewArray<View>& x,
00147 ViewArray<Card>& k, bool& all) {
00148
00149 int m = k.size();
00150 int n = x.size();
00151 for (int i = m; i--; ) {
00152 smax += k[i].max();
00153 smin += k[i].min();
00154 }
00155
00156
00157 if (n < smin) {
00158 return false;
00159 }
00160
00161
00162
00163 if (all && smax < n) {
00164 return false;
00165 }
00166
00167 return true;
00168 }
00169
00173 class Rank {
00174 public:
00179 int min;
00184 int max;
00185 };
00186
00194 template <class View>
00195 class MaxInc {
00196 protected:
00197 ViewArray<View> x;
00198 public:
00199 MaxInc(const ViewArray<View>& x0) : x(x0) {}
00200 forceinline bool
00201 operator()(const int i, const int j) {
00202 return x[i].max() < x[j].max();
00203 }
00204 };
00205
00213 template <class View>
00214 class MinInc {
00215 protected:
00216 ViewArray<View> x;
00217 public:
00218 MinInc(const ViewArray<View>& x0) : x(x0) {}
00219 forceinline bool
00220 operator()(const int i, const int j) {
00221 return x[i].min() < x[j].min();
00222 }
00223 };
00224
00225
00231 template <class Card>
00232 class PartialSum {
00233 private:
00235 char* mem;
00237 int* sum;
00242 int* ds;
00244 int size;
00245 public:
00247
00248 PartialSum( int, int, ViewArray<Card>& , bool);
00249 ~PartialSum(void);
00251
00252
00253 int firstValue;
00254 int lastValue;
00255 int sumup(int, int);
00256 int minValue(void);
00257 int maxValue(void);
00258 int skipNonNullElementsRight(int);
00259 int skipNonNullElementsLeft(int);
00260 void* operator new(size_t s);
00261 void operator delete(void* p);
00262 void print(void);
00263 bool check_update_max(ViewArray<Card>& k);
00264 bool check_update_min(ViewArray<Card>& k);
00265 int getsize(void);
00267 };
00268
00270 template <class Card>
00271 forceinline
00272 PartialSum<Card>::~PartialSum(void){
00273 assert(mem != NULL);
00274 Memory::free(mem);
00275 }
00276
00278 template <class Card>
00279 forceinline void*
00280 PartialSum<Card>::operator new(size_t t){
00281 void* allocated = Memory::malloc(t);
00282 return allocated;
00283 }
00284
00286 template <class Card>
00287 forceinline void
00288 PartialSum<Card>::operator delete(void* p){
00289 Memory::free(p);
00290 }
00291
00304 template <class Card>
00305 inline
00306 PartialSum<Card>::PartialSum(int first,
00307 int count,
00308 ViewArray<Card>& elements,
00309 bool up) {
00310 int i = 0;
00311 int j = 0;
00312
00313 size = count + 5;
00314
00315 size_t sum_size = (size) * sizeof(int);
00316 size_t ds_size = (size) * sizeof(int);
00317 size_t total = sum_size + ds_size;
00318
00319 mem = reinterpret_cast<char*> (Memory::malloc(total));
00320 sum = reinterpret_cast<int*> (mem);
00321 ds = reinterpret_cast<int*> (mem + sum_size);
00322
00323 for (int z = 0; z < size; z++) {
00324 sum[z] = 0;
00325 ds[z] = 0;
00326 }
00327
00328
00329
00330
00331
00332
00333 firstValue = first - 3;
00334 lastValue = first + count + 1;
00335
00336
00337
00338 for (i = 3; i--; ){
00339 sum[i] = i;
00340 }
00341
00342 int shift = count + 2;
00343
00344
00345
00346
00347
00348
00349 for (i = 2; i < shift; i++){
00350 if (up) {
00351 sum[i + 1] = sum[i] + elements[i - 2].max();
00352 } else {
00353 sum[i + 1] = sum[i] + elements[i - 2].min();
00354 }
00355 }
00356 sum[i + 1] = sum[i] + 1;
00357 sum[i + 2] = sum[i + 1] + 1;
00358
00359
00360
00361 i = count + 3;
00362 j = i + 1;
00363 for ( ; i > 0; ){
00364 while(sum[i] == sum[i - 1]) {
00365 ds[i] = j;
00366 i--;
00367 }
00368 ds[j] = i;
00369 i--;
00370 j = ds[j];
00371 }
00372 ds[j] = 0;
00373
00374 ds[0] = 0;
00375 }
00376
00380 template <class Card>
00381 forceinline int
00382 PartialSum<Card>::sumup(int from, int to){
00383 if (from <= to) {
00384 return sum[to - firstValue] - sum[from - firstValue - 1];
00385 } else {
00386 return sum[to - firstValue - 1] - sum[from - firstValue];
00387 }
00388 }
00389
00394 template <class Card>
00395 forceinline int
00396 PartialSum<Card>::minValue(void){
00397 return firstValue + 3;
00398 }
00399
00405 template <class Card>
00406 forceinline int
00407 PartialSum<Card>::maxValue(void){
00408 return lastValue - 2;
00409 }
00410
00411
00417 template <class Card>
00418 forceinline int
00419 PartialSum<Card>::skipNonNullElementsRight(int value) {
00420 value -= firstValue;
00421 return (ds[value] < value ? value : ds[value]) + firstValue;
00422 }
00423
00429 template <class Card>
00430 forceinline int
00431 PartialSum<Card>::skipNonNullElementsLeft(int value) {
00432 value -= firstValue;
00433 return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00434 }
00435
00437 template <class Card>
00438 void
00439 PartialSum<Card>::print(void){
00440 std::cout << "----------\n";
00441 std::cout << "smallest elem = "<< minValue() << " - "
00442 << "largest elem = "<< maxValue() << "\n";
00443 std::cout << "fsv: "<< firstValue <<" lsv: " << lastValue
00444 << " size = "<< size << "\n";
00445 std::cout << "number of elements = "<< size - 5<<"\n";
00446 std::cout << "elements: ";
00447 for (int i = 3; i < size - 2; i++) {
00448 std::cout << sum[i] - sum[i-1] << " ";
00449 }
00450 std::cout <<"\n";
00451
00452 std::cout << "sum: ";
00453 for (int i = 0; i < size; i++) {
00454 std::cout <<sum[i] << " ";
00455 }
00456 std::cout <<"\n";
00457 std::cout << "ds: ";
00458 for (int i = 0; i < size; i++) {
00459 std::cout <<sum[i] << " ";
00460 }
00461 std::cout <<"\n";
00462
00463 }
00464
00473 template <class Card>
00474 inline bool
00475 PartialSum<Card>::check_update_max(ViewArray<Card>& k){
00476 if (k.size() <= size - 5) {
00477 return true;
00478 } else {
00479 for (int i = 3; i < size - 2; i++) {
00480 if ((sum[i] - sum[i - 1]) != k[i - 3].max()) {
00481 return true;
00482 }
00483 }
00484 return false;
00485 }
00486 }
00487
00496 template <class Card>
00497 inline bool
00498 PartialSum<Card>::check_update_min(ViewArray<Card>& k){
00499 if (k.size() <= size - 5) {
00500 return true;
00501 } else {
00502 for (int i = 3; i < size - 2; i++) {
00503 if ((sum[i] - sum[i - 1]) != k[i - 3].min()) {
00504 return true;
00505 }
00506 }
00507 return false;
00508 }
00509 }
00510
00512 template <class Card>
00513 forceinline int
00514 PartialSum<Card>::getsize(void){
00515 return size;
00516 }
00517
00518
00529 class HallInfo {
00530 public:
00532 int bounds;
00538 int t;
00546 int d;
00555 int h;
00560 int s;
00565 int ps;
00572 int newBound;
00573 };
00574
00575
00585
00586 inline void
00587 pathset_ps(HallInfo hall[], int start, int end, int to) {
00588 int k, l;
00589 for (l=start; (k=l) != end; hall[k].ps=to) {
00590 l = hall[k].ps;
00591 }
00592 }
00593
00595 inline void
00596 pathset_s(HallInfo hall[], int start, int end, int to) {
00597 int k, l;
00598 for (l=start; (k=l) != end; hall[k].s=to) {
00599 l = hall[k].s;
00600 }
00601 }
00602
00604 inline void
00605 pathset_t(HallInfo hall[], int start, int end, int to) {
00606 int k, l;
00607 for (l=start; (k=l) != end; hall[k].t=to) {
00608 l = hall[k].t;
00609 }
00610 }
00611
00613 inline void
00614 pathset_h(HallInfo hall[], int start, int end, int to) {
00615 int k, l;
00616 for (l=start; (k=l) != end; hall[k].h=to) {
00617 l = hall[k].h;
00618 }
00619 }
00621
00629
00630 forceinline int
00631 pathmin_h(const HallInfo hall[], int i) {
00632 while (hall[i].h < i)
00633 i = hall[i].h;
00634 return i;
00635 }
00637 forceinline int
00638 pathmin_t(const HallInfo hall[], int i) {
00639 while (hall[i].t < i)
00640 i = hall[i].t;
00641 return i;
00642 }
00644
00651
00652 forceinline int
00653 pathmax_h(const HallInfo hall[], int i) {
00654 while (hall[i].h > i)
00655 i = hall[i].h;
00656 return i;
00657 }
00658
00659
00661 forceinline int
00662 pathmax_t(const HallInfo hall[], int i) {
00663 while (hall[i].t > i) {
00664 i = hall[i].t;
00665 }
00666 return i;
00667 }
00668
00670 forceinline int
00671 pathmax_s(const HallInfo hall[], int i) {
00672 while (hall[i].s > i)
00673 i = hall[i].s;
00674 return i;
00675 }
00676
00678 forceinline int
00679 pathmax_ps(const HallInfo hall[], int i) {
00680 while (hall[i].ps > i)
00681 i = hall[i].ps;
00682 return i;
00683 }
00685
00686
00696 template <class Card>
00697 void
00698 reduce_card(int cmin, int cmax, ViewArray<Card>& k) {
00699 if (cmin == cmax) {
00700 int idx = 0;
00701 while (k[idx].card() != cmax) {
00702 idx++;
00703 }
00704 k[0] = k[idx];
00705 k.size(1);
00706 } else {
00707
00708 GECODE_AUTOARRAY(bool, zero, k.size());
00709 int ks = k.size();
00710 int zc = 0;
00711 for (int i = 0; i < ks; i++) {
00712 bool impossible = ( (k[i].counter() == 0) &&
00713 (k[i].card() < cmin ||
00714 k[i].card() > cmax));
00715
00716 if (impossible) {
00717 zero[i] = true;
00718 zc++;
00719 } else {
00720 zero[i] = false;
00721 }
00722 }
00723
00724
00725 if (zero[ks - 1]) {
00726 int m = ks;
00727 while(zero[m - 1]) {
00728 m--;
00729 zc--;
00730 }
00731 k.size(m);
00732 }
00733
00734 START_SIZE
00735 if (zc > 0) {
00736 int ks = k.size();
00737
00738 for (int i = 0; i < ks; i++) {
00739 assert(0 <= i && i < ks);
00740 if (zero[i]) {
00741 if (i == ks - 1) {
00742 break;
00743 }
00744
00745
00746
00747 int j = i + 1;
00748 assert(0 <= j && j < ks);
00749 if (j < ks) {
00750 while (zero[j]) {
00751 j++;
00752 }
00753 }
00754 if (j > ks - 1) {
00755 break;
00756 }
00757 k[i] = k[j];
00758 zero[j] = true;
00759 }
00760 }
00761 k.size(ks - zc);
00762 }
00763
00764 END_SIZE
00765 assert(start_size == end_size + zc);
00766 }
00767
00768
00769
00770
00771
00772 }
00773
00774 }}}
00775
00776
00777