bnd-sup.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * Guido Tack <tack@gecode.org> 00009 * 00010 * Copyright: 00011 * Patrick Pekczynski, 2004 00012 * Christian Schulte, 2009 00013 * Guido Tack, 2009 00014 * 00015 * Last modified: 00016 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00017 * $Revision: 10684 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 namespace Gecode { namespace Int { namespace GCC { 00045 00057 class UnReachable { 00058 public: 00060 int minb; 00062 int maxb; 00064 int eq; 00066 int le; 00068 int gr; 00069 }; 00070 00076 template<class Card> 00077 ExecStatus 00078 prop_card(Space& home, 00079 ViewArray<IntView>& x, ViewArray<Card>& k) { 00080 int n = x.size(); 00081 int m = k.size(); 00082 Region r(home); 00083 UnReachable* rv = r.alloc<UnReachable>(m); 00084 for(int i = m; i--; ) 00085 rv[i].minb=rv[i].maxb=rv[i].le=rv[i].gr=rv[i].eq=0; 00086 00087 for (int i = n; i--; ) { 00088 int min_idx; 00089 if (!lookupValue(k,x[i].min(),min_idx)) 00090 return ES_FAILED; 00091 if (x[i].assigned()) { 00092 rv[min_idx].minb++; 00093 rv[min_idx].maxb++; 00094 rv[min_idx].eq++; 00095 } else { 00096 // count the number of variables 00097 // with lower bound k[min_idx].card() 00098 rv[min_idx].minb++; 00099 int max_idx; 00100 if (!lookupValue(k,x[i].max(),max_idx)) 00101 return ES_FAILED; 00102 // count the number of variables 00103 // with upper bound k[max_idx].card() 00104 rv[max_idx].maxb++; 00105 } 00106 } 00107 00108 rv[0].le = 0; 00109 int c_min = 0; 00110 for (int i = 1; i < m; i++) { 00111 rv[i].le = c_min + rv[i - 1].maxb; 00112 c_min += rv[i - 1].maxb; 00113 } 00114 00115 rv[m-1].gr = 0; 00116 int c_max = 0; 00117 for (int i = m-1; i--; ) { 00118 rv[i].gr = c_max + rv[i + 1].minb; 00119 c_max += rv[i + 1].minb; 00120 } 00121 00122 for (int i = m; i--; ) { 00123 int reachable = x.size() - rv[i].le - rv[i].gr; 00124 if (!k[i].assigned()) { 00125 GECODE_ME_CHECK(k[i].lq(home, reachable)); 00126 GECODE_ME_CHECK(k[i].gq(home, rv[i].eq)); 00127 } else { 00128 // check validity of the cardinality value 00129 if ((rv[i].eq > k[i].max()) || (k[i].max() > reachable)) 00130 return ES_FAILED; 00131 } 00132 } 00133 00134 return ES_OK; 00135 } 00136 00137 00141 template<class Card> 00142 forceinline bool 00143 card_consistent(ViewArray<IntView>& x, ViewArray<Card>& k) { 00144 int smin = 0; 00145 int smax = 0; 00146 for (int i = k.size(); i--; ) { 00147 smax += k[i].max(); 00148 smin += k[i].min(); 00149 } 00150 // Consistent if number of variables within cardinality bounds 00151 return (smin <= x.size()) && (x.size() <= smax); 00152 } 00153 00158 class Rank { 00159 public: 00164 int min; 00169 int max; 00170 }; 00171 00179 template<class View> 00180 class MaxInc { 00181 protected: 00183 ViewArray<View> x; 00184 public: 00186 MaxInc(const ViewArray<View>& x0) : x(x0) {} 00188 forceinline bool 00189 operator ()(const int i, const int j) { 00190 return x[i].max() < x[j].max(); 00191 } 00192 }; 00193 00194 00202 template<class View> 00203 class MinInc { 00204 protected: 00206 ViewArray<View> x; 00207 public: 00209 MinInc(const ViewArray<View>& x0) : x(x0) {} 00211 forceinline bool 00212 operator ()(const int i, const int j) { 00213 return x[i].min() < x[j].min(); 00214 } 00215 }; 00216 00217 00224 template<class Card> 00225 class MinIdx { 00226 public: 00228 forceinline bool 00229 operator ()(const Card& x, const Card& y) { 00230 return x.card() < y.card(); 00231 } 00232 }; 00233 00240 template<class Card> 00241 class PartialSum { 00242 private: 00244 int* sum; 00246 int size; 00247 public: 00249 int firstValue, lastValue; 00251 00252 00253 PartialSum(void); 00255 void init(Space& home, ViewArray<Card>& k, bool up); 00257 void reinit(void); 00259 bool initialized(void) const; 00261 00262 00263 00264 int sumup(int from, int to) const; 00266 int minValue(void) const; 00268 int maxValue(void) const; 00270 int skipNonNullElementsRight(int v) const; 00272 int skipNonNullElementsLeft(int v) const; 00274 00275 00276 00283 bool check_update_min(ViewArray<Card>& k); 00291 bool check_update_max(ViewArray<Card>& k); 00293 }; 00294 00295 00296 template<class Card> 00297 forceinline 00298 PartialSum<Card>::PartialSum(void) : sum(NULL), size(-1) {} 00299 00300 template<class Card> 00301 forceinline bool 00302 PartialSum<Card>::initialized(void) const { 00303 return size != -1; 00304 } 00305 template<class Card> 00306 inline void 00307 PartialSum<Card>::init(Space& home, ViewArray<Card>& elements, bool up) { 00308 int i = 0; 00309 int j = 0; 00310 00311 // Determine number of holes in the index set 00312 int holes = 0; 00313 for (i = 1; i < elements.size(); i++) { 00314 if (elements[i].card() != elements[i-1].card() + 1) 00315 holes += elements[i].card()-elements[i-1].card()-1; 00316 } 00317 00318 // we add three elements at the beginning and two at the end 00319 size = elements.size() + holes + 5; 00320 00321 // memory allocation 00322 if (sum == NULL) { 00323 sum = home.alloc<int>(2*size); 00324 } 00325 int* ds = &sum[size]; 00326 00327 int first = elements[0].card(); 00328 00329 firstValue = first - 3; 00330 lastValue = first + elements.size() + holes + 1; 00331 00332 // the first three elements 00333 for (i = 3; i--; ) 00334 sum[i] = i; 00335 00336 /* 00337 * copy the bounds into sum, filling up holes with zeroes 00338 */ 00339 int prevCard = elements[0].card()-1; 00340 i = 0; 00341 for (j = 2; j < elements.size() + holes + 2; j++) { 00342 if (elements[i].card() != prevCard + 1) { 00343 sum[j + 1] = sum[j]; 00344 } else if (up) { 00345 sum[j + 1] = sum[j] + elements[i].max(); 00346 i++; 00347 } else { 00348 sum[j + 1] = sum[j] + elements[i].min(); 00349 i++; 00350 } 00351 prevCard++; 00352 } 00353 sum[j + 1] = sum[j] + 1; 00354 sum[j + 2] = sum[j + 1] + 1; 00355 00356 // Compute distances, eliminating zeroes 00357 i = elements.size() + holes + 3; 00358 j = i + 1; 00359 for ( ; i > 0; ) { 00360 while(sum[i] == sum[i - 1]) { 00361 ds[i] = j; 00362 i--; 00363 } 00364 ds[j] = i; 00365 i--; 00366 j = ds[j]; 00367 } 00368 ds[j] = 0; 00369 ds[0] = 0; 00370 } 00371 00372 template<class Card> 00373 forceinline void 00374 PartialSum<Card>::reinit(void) { 00375 size = -1; 00376 } 00377 00378 00379 template<class Card> 00380 forceinline int 00381 PartialSum<Card>::sumup(int from, int to) const { 00382 if (from <= to) { 00383 return sum[to - firstValue] - sum[from - firstValue - 1]; 00384 } else { 00385 assert(to - firstValue - 1 >= 0); 00386 assert(to - firstValue - 1 < size); 00387 assert(from - firstValue >= 0); 00388 assert(from - firstValue < size); 00389 return sum[to - firstValue - 1] - sum[from - firstValue]; 00390 } 00391 } 00392 00393 template<class Card> 00394 forceinline int 00395 PartialSum<Card>::minValue(void) const { 00396 return firstValue + 3; 00397 } 00398 template<class Card> 00399 forceinline int 00400 PartialSum<Card>::maxValue(void) const { 00401 return lastValue - 2; 00402 } 00403 00404 00405 template<class Card> 00406 forceinline int 00407 PartialSum<Card>::skipNonNullElementsRight(int value) const { 00408 value -= firstValue; 00409 int* ds = &sum[size]; 00410 return (ds[value] < value ? value : ds[value]) + firstValue; 00411 } 00412 template<class Card> 00413 forceinline int 00414 PartialSum<Card>::skipNonNullElementsLeft(int value) const { 00415 value -= firstValue; 00416 int* ds = &sum[size]; 00417 return (ds[value] > value ? ds[ds[value]] : value) + firstValue; 00418 } 00419 00420 template<class Card> 00421 inline bool 00422 PartialSum<Card>::check_update_max(ViewArray<Card>& k) { 00423 int j = 0; 00424 for (int i = 3; i < size - 2; i++) { 00425 int max = 0; 00426 if (k[j].card() == i+firstValue) 00427 max = k[j++].max(); 00428 if ((sum[i] - sum[i - 1]) != max) 00429 return true; 00430 } 00431 return false; 00432 } 00433 00434 template<class Card> 00435 inline bool 00436 PartialSum<Card>::check_update_min(ViewArray<Card>& k) { 00437 int j = 0; 00438 for (int i = 3; i < size - 2; i++) { 00439 int min = 0; 00440 if (k[j].card() == i+firstValue) 00441 min = k[j++].min(); 00442 if ((sum[i] - sum[i - 1]) != min) 00443 return true; 00444 } 00445 return false; 00446 } 00447 00448 00460 class HallInfo { 00461 public: 00463 int bounds; 00469 int t; 00477 int d; 00486 int h; 00488 int s; 00490 int ps; 00497 int newBound; 00498 }; 00499 00500 00509 00510 forceinline void 00511 pathset_ps(HallInfo hall[], int start, int end, int to) { 00512 int k, l; 00513 for (l=start; (k=l) != end; hall[k].ps=to) { 00514 l = hall[k].ps; 00515 } 00516 } 00518 forceinline void 00519 pathset_s(HallInfo hall[], int start, int end, int to) { 00520 int k, l; 00521 for (l=start; (k=l) != end; hall[k].s=to) { 00522 l = hall[k].s; 00523 } 00524 } 00526 forceinline void 00527 pathset_t(HallInfo hall[], int start, int end, int to) { 00528 int k, l; 00529 for (l=start; (k=l) != end; hall[k].t=to) { 00530 l = hall[k].t; 00531 } 00532 } 00534 forceinline void 00535 pathset_h(HallInfo hall[], int start, int end, int to) { 00536 int k, l; 00537 for (l=start; (k=l) != end; hall[k].h=to) { 00538 l = hall[k].h; 00539 assert(l != k); 00540 } 00541 } 00543 00551 00552 forceinline int 00553 pathmin_h(const HallInfo hall[], int i) { 00554 while (hall[i].h < i) 00555 i = hall[i].h; 00556 return i; 00557 } 00559 forceinline int 00560 pathmin_t(const HallInfo hall[], int i) { 00561 while (hall[i].t < i) 00562 i = hall[i].t; 00563 return i; 00564 } 00566 00574 00575 forceinline int 00576 pathmax_h(const HallInfo hall[], int i) { 00577 while (hall[i].h > i) 00578 i = hall[i].h; 00579 return i; 00580 } 00582 forceinline int 00583 pathmax_t(const HallInfo hall[], int i) { 00584 while (hall[i].t > i) { 00585 i = hall[i].t; 00586 } 00587 return i; 00588 } 00590 forceinline int 00591 pathmax_s(const HallInfo hall[], int i) { 00592 while (hall[i].s > i) 00593 i = hall[i].s; 00594 return i; 00595 } 00597 forceinline int 00598 pathmax_ps(const HallInfo hall[], int i) { 00599 while (hall[i].ps > i) 00600 i = hall[i].ps; 00601 return i; 00602 } 00604 00605 }}} 00606 00607 // STATISTICS: int-prop 00608