gccbndsup.icc
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 namespace Gecode { namespace Int { namespace GCC {
00024
00026
00027
00031 class Rank {
00032 public:
00037 int min;
00042 int max;
00043 };
00044
00052 template <class View>
00053 class MaxInc {
00054 protected:
00055 ViewArray<View> x;
00056 public:
00057 MaxInc(const ViewArray<View>& x0) : x(x0) {}
00058 forceinline bool
00059 operator()(const int i, const int j) {
00060 return x[i].max() < x[j].max();
00061 }
00062 };
00063
00071 template <class View>
00072 class MinInc {
00073 protected:
00074 ViewArray<View> x;
00075 public:
00076 MinInc(const ViewArray<View>& x0) : x(x0) {}
00077 forceinline bool
00078 operator()(const int i, const int j) {
00079 return x[i].min() < x[j].min();
00080 }
00081 };
00082
00083
00089 template <class Card>
00090 class PartialSum {
00091 private:
00093 char* mem;
00094
00095 int* sum;
00100 int* ds;
00102 int size;
00103 public:
00105
00106 PartialSum( int, int, Card& , bool);
00107 ~PartialSum(void);
00109
00110
00111 int firstValue;
00112 int lastValue;
00113 int sumup(int, int);
00114 int minValue(void);
00115 int maxValue(void);
00116 int skipNonNullElementsRight(int);
00117 int skipNonNullElementsLeft(int);
00118 void* operator new(size_t s);
00119 void operator delete(void* p);
00120 void print(void);
00121 bool check_update_max(Card& k);
00122 bool check_update_min(Card& k);
00123 int getsize(void);
00125 };
00126
00127 template <class Card>
00128 forceinline
00129 PartialSum<Card>::~PartialSum(void){
00130 assert(mem != NULL);
00131 Memory::free(mem);
00132 }
00133
00134 template <class Card>
00135 forceinline void*
00136 PartialSum<Card>::operator new(size_t t){
00137 void* allocated = Memory::malloc(t);
00138 return allocated;
00139 }
00140
00141 template <class Card>
00142 forceinline void
00143 PartialSum<Card>::operator delete(void* p){
00144 Memory::free(p);
00145 }
00146
00156 template <class Card>
00157 forceinline
00158 PartialSum<Card>::PartialSum(int first,
00159 int count,
00160 Card& elements,
00161 bool up) {
00162 int i = 0;
00163 int j = 0;
00164
00165
00166 size = count + 5;
00167
00168 size_t sum_size = (size) * sizeof(int);
00169 size_t ds_size = (size) * sizeof(int);
00170 size_t total = sum_size + ds_size;
00171
00172 mem = reinterpret_cast<char*> (Memory::malloc(total));
00173 sum = reinterpret_cast<int*> (mem);
00174 ds = reinterpret_cast<int*> (mem + sum_size);
00175
00176 for (int z = 0; z < size; z++) {
00177 sum[z] = 0;
00178 ds[z] = 0;
00179 }
00180
00181
00182
00183
00184
00185
00186
00187 firstValue = first - 3;
00188 lastValue = first + count + 1;
00189
00190
00191
00192 for (i = 3; i--; ){
00193 sum[i] = i;
00194 }
00195
00196 int shift = count + 2;
00197
00198
00199
00200 for (i = 2; i < shift; i++){
00201 if (up) {
00202 sum[i + 1] = sum[i] + elements[i - 2].max();
00203 } else {
00204 sum[i + 1] = sum[i] + elements[i - 2].min();
00205 }
00206 }
00207 sum[i + 1] = sum[i] + 1;
00208 sum[i + 2] = sum[i + 1] + 1;
00209
00210
00211
00212 i = count + 3;
00213 j = i + 1;
00214 for ( ; i > 0; ){
00215 while(sum[i] == sum[i - 1]) {
00216 ds[i] = j;
00217 i--;
00218 }
00219 ds[j] = i;
00220 i--;
00221 j = ds[j];
00222 }
00223 ds[j] = 0;
00224
00225 ds[0] = 0;
00226 }
00227
00231 template <class Card>
00232 forceinline int
00233 PartialSum<Card>::sumup(int from, int to){
00234 int result = 0;
00235 if (from <= to) {
00236 result = sum[to - firstValue] - sum[from - firstValue - 1];
00237 }
00238 else {
00239 result = sum[to - firstValue - 1] - sum[from - firstValue];
00240 }
00241 return result;
00242 }
00243
00249 template <class Card>
00250 forceinline int
00251 PartialSum<Card>::minValue(void){
00252 return firstValue + 3;
00253 }
00254
00261 template <class Card>
00262 forceinline int
00263 PartialSum<Card>::maxValue(void){
00264 return lastValue - 2;
00265 }
00266
00267
00272 template <class Card>
00273 forceinline int
00274 PartialSum<Card>::skipNonNullElementsRight(int value) {
00275 value -= firstValue;
00276 return (ds[value] < value ? value : ds[value]) + firstValue;
00277 }
00278
00279 template <class Card>
00280 forceinline int
00281 PartialSum<Card>::skipNonNullElementsLeft(int value) {
00282 value -= firstValue;
00283 return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00284 }
00285
00287 template <class Card>
00288 forceinline void
00289 PartialSum<Card>::print(void){
00290 std::cout << "fsv: "<< firstValue <<" lsv: " << lastValue
00291 << " size = "<< size << "\n";
00292 std::cout << "number of elements = "<< size - 5<<"\n";
00293 std::cout << "elements: ";
00294 for (int i = 3; i < size - 2; i++) {
00295 std::cout << sum[i] - sum[i-1] << " ";
00296 }
00297 std::cout <<"\n";
00298
00299 std::cout << "sum: ";
00300 for (int i = 0; i < size; i++) {
00301 std::cout <<sum[i] << " ";
00302 }
00303 std::cout <<"\n";
00304 std::cout << "ds: ";
00305 for (int i = 0; i < size; i++) {
00306 std::cout <<sum[i] << " ";
00307 }
00308 std::cout <<"\n";
00309
00310 }
00311
00312 template <class Card>
00313 forceinline bool
00314 PartialSum<Card>::check_update_max(Card& k){
00315 if (k.size() <= size - 5) {
00316 return true;
00317 } else {
00318 for (int i = 3; i < size - 2; i++) {
00319 if ((sum[i] - sum[i - 1]) != k[i - 3].max()) {
00320 return true;
00321 }
00322 }
00323 return false;
00324 }
00325 }
00326
00327 template <class Card>
00328 forceinline bool
00329 PartialSum<Card>::check_update_min(Card& k){
00330 if (k.size() <= size - 5) {
00331 return true;
00332 } else {
00333 for (int i = 3; i < size - 2; i++) {
00334 if ((sum[i] - sum[i - 1]) != k[i - 3].min()) {
00335 return true;
00336 }
00337 }
00338 return false;
00339 }
00340 }
00341
00342 template <class Card>
00343 forceinline int
00344 PartialSum<Card>::getsize(void){
00345 return size;
00346 }
00347
00348
00359 class HallInfo {
00360 public:
00362 int bounds;
00368 int t;
00376 int d;
00385 int h;
00390 int s;
00395 int ps;
00402 int newBound;
00403 };
00404
00405
00415
00416 inline void
00417 pathset_ps(HallInfo hall[], int start, int end, int to) {
00418 int k = 0;
00419 int l = start;
00420 for ( ; (k = l) != end; hall[k].ps = to) {
00421 l = hall[k].ps;
00422
00423 }
00424 }
00426 inline void
00427 pathset_s(HallInfo hall[], int start, int end, int to) {
00428 int k = 0;
00429 int l = start;
00430 for ( ; (k = l) != end; hall[k].s = to) {
00431 l = hall[k].s;
00432 }
00433 }
00434
00436 inline void
00437 pathset_t(HallInfo hall[], int start, int end, int to) {
00438 int k = 0;
00439 int l = start;
00440 for ( ; (k = l) != end; hall[k].t = to) {
00441 l = hall[k].t;
00442 }
00443 }
00444
00446 inline void
00447 pathset_h(HallInfo hall[], int start, int end, int to) {
00448 int k = 0;
00449 int l = start;
00450 for ( ; (k = l) != end; hall[k].h = to) {
00451 l = hall[k].h;
00452 }
00453 }
00455
00463
00464 forceinline int
00465 pathmin_h(const HallInfo hall[], int i) {
00466 while (hall[i].h < i)
00467 i = hall[i].h;
00468 return i;
00469 }
00471 forceinline int
00472 pathmin_t(const HallInfo hall[], int i) {
00473 while (hall[i].t < i)
00474 i = hall[i].t;
00475 return i;
00476 }
00478
00485
00486 forceinline int
00487 pathmax_h(const HallInfo hall[], int i) {
00488 while (hall[i].h > i)
00489 i = hall[i].h;
00490 return i;
00491 }
00492
00493
00495 forceinline int
00496 pathmax_t(const HallInfo hall[], int i) {
00497 while (hall[i].t > i)
00498 i = hall[i].t;
00499 return i;
00500 }
00501
00503 forceinline int
00504 pathmax_s(const HallInfo hall[], int i) {
00505 while (hall[i].s > i)
00506 i = hall[i].s;
00507 return i;
00508 }
00509
00511 forceinline int
00512 pathmax_ps(const HallInfo hall[], int i) {
00513 while (hall[i].ps > i)
00514 i = hall[i].ps;
00515 return i;
00516 }
00518
00519
00529 template <class Card>
00530 void reduce_card(int cmin, int cmax, Card& k) {
00531
00532 if (cmin == cmax) {
00533 int idx = 0;
00534 while (k[idx].card() != cmax) {
00535 idx++;
00536 }
00537 k[0] = k[idx];
00538 k.size(1);
00539 } else {
00540
00541 GECODE_AUTOARRAY(bool, zero, k.size());
00542 int ks = k.size();
00543 int zc = 0;
00544 for (int i = 0; i < ks; i++) {
00545 bool impossible = ( (k[i].counter() == 0) &&
00546 (k[i].card() < cmin ||
00547 k[i].card() > cmax));
00548
00549 if (impossible) {
00550 zero[i] = true;
00551 zc++;
00552 } else {
00553 zero[i] = false;
00554 }
00555 }
00556
00557 if (zero[ks - 1]) {
00558 int m = ks;
00559 while(zero[m - 1]) {
00560 m--;
00561 zc--;
00562 }
00563 k.size(m);
00564 }
00565
00566 int start_size = k.size();
00567 if (zc > 0) {
00568 int ks = k.size();
00569
00570 for (int i = 0; i < ks; i++) {
00571 assert(0 <= i && i < ks);
00572 if (zero[i]) {
00573 if (i == ks - 1) {
00574 break;
00575 }
00576
00577
00578
00579 int j = i + 1;
00580 assert(0 <= j && j < ks);
00581 if (j < ks) {
00582 while (zero[j]) {
00583 j++;
00584 }
00585 }
00586 if (j > ks - 1) {
00587 break;
00588 }
00589 k[i] = k[j];
00590 zero[j] = true;
00591 }
00592 }
00593 k.size(ks - zc);
00594 }
00595
00596
00597 int end_size = k.size();
00598 assert(start_size == end_size + zc);
00599 }
00600
00601
00602
00603
00604
00605 }
00606
00607 }}}
00608
00609
00610