sortsup.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 * Copyright: 00007 * Patrick Pekczynski, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00011 * $Revision: 10684 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 namespace Gecode { namespace Int { namespace Sorted { 00039 00043 class Rank { 00044 public: 00046 int min; 00048 int max; 00049 }; 00050 00057 class SccComponent { 00058 public: 00060 int leftmost; 00062 int left; 00064 int right; 00066 int rightmost; 00067 }; 00068 00080 template<class View, bool Perm> 00081 inline bool 00082 check_subsumption(ViewArray<View>& x, ViewArray<View>& y, ViewArray<View>& z, 00083 bool& subsumed, int& dropfst) { 00084 00085 dropfst = 0; 00086 subsumed = true; 00087 int xs = x.size(); 00088 for (int i = 0; i < xs ; i++) { 00089 if (Perm) { 00090 subsumed &= (x[i].assigned() && 00091 z[i].assigned() && 00092 y[z[i].val()].assigned()); 00093 if (subsumed) { 00094 if (x[i].val() != y[z[i].val()].val()) { 00095 return false; 00096 } else { 00097 if (z[i].val() == i) { 00098 dropfst++; 00099 } 00100 } 00101 } 00102 } else { 00103 subsumed &= (x[i].assigned() && y[i].assigned()); 00104 if (subsumed) { 00105 if (x[i].val() != y[i].val()) { 00106 return false; 00107 } else { 00108 dropfst++; 00109 } 00110 } 00111 } 00112 } 00113 return true; 00114 } 00115 00121 class OfflineMinItem { 00122 public: 00124 int root; 00126 int parent; 00128 int rank; 00130 int name; 00138 int iset; 00140 int succ; 00142 int pred; 00143 }; 00144 00150 class OfflineMin { 00151 private: 00152 OfflineMinItem* sequence; 00153 int* vertices; 00154 int n; 00155 public: 00156 OfflineMin(void); 00157 OfflineMin(OfflineMinItem[], int[], int); 00162 int find(int x); 00167 int find_pc(int x); 00169 void unite(int a, int b, int c); 00171 void makeset(void); 00173 int size(void); 00174 OfflineMinItem& operator [](int); 00175 }; 00176 00177 OfflineMin::OfflineMin(void){ 00178 n = 0; 00179 sequence = NULL; 00180 vertices = NULL; 00181 } 00182 00183 OfflineMin::OfflineMin(OfflineMinItem s[], int v[], int size){ 00184 n = size; 00185 sequence = &s[0]; 00186 vertices = &v[0]; 00187 } 00188 00189 forceinline int 00190 OfflineMin::find(int x) { 00191 while (sequence[x].parent != x) { 00192 x = sequence[x].parent; 00193 } 00194 // x is now the root of the tree 00195 // return the set, x belongs to 00196 return sequence[x].name; 00197 } 00198 00199 forceinline int 00200 OfflineMin::find_pc(int x){ 00201 int vsize = 0; 00202 while (sequence[x].parent != x) { 00203 vertices[x] = x; 00204 x = sequence[x].parent; 00205 } 00206 // x is now the root of the tree 00207 for (int i = vsize; i--; ) { 00208 sequence[vertices[i]].parent = x; 00209 } 00210 // return the set, x belongs to 00211 return sequence[x].name; 00212 } 00213 00214 forceinline void 00215 OfflineMin::unite(int a, int b, int c){ 00216 // c is the union of a and b 00217 int ra = sequence[a].root; 00218 int rb = sequence[b].root; 00219 int large = rb; 00220 int small = ra; 00221 if (sequence[ra].rank > sequence[rb].rank) { 00222 large = ra; 00223 small = rb; 00224 } 00225 sequence[small].parent = large; 00226 sequence[large].rank += sequence[small].rank; 00227 sequence[large].name = c; 00228 sequence[c].root = large; 00229 } 00230 00231 forceinline void 00232 OfflineMin::makeset(void){ 00233 for(int i = n; i--; ){ 00234 OfflineMinItem& cur = sequence[i]; 00235 cur.rank = 0; // initially each set is empty 00236 cur.name = i; // it has its own name 00237 cur.root = i; // it is the root node 00238 cur.parent = i; // it is its own parent 00239 cur.pred = i - 1; 00240 cur.succ = i + 1; 00241 cur.iset = -5; 00242 } 00243 } 00244 00245 forceinline int 00246 OfflineMin::size(void){ 00247 return n; 00248 } 00249 00250 forceinline OfflineMinItem& 00251 OfflineMin::operator [](int i){ 00252 return sequence[i]; 00253 } 00254 00264 template<class View> 00265 class TupleMaxInc { 00266 protected: 00267 ViewArray<View> x; 00268 public: 00269 TupleMaxInc(const ViewArray<View>& x0) : x(x0) {} 00270 bool operator ()(const int i, const int j) { 00271 if (x[i].max() == x[j].max()) { 00272 return x[i].min() < x[j].min(); 00273 } else { 00274 return x[i].max() < x[j].max(); 00275 } 00276 } 00277 }; 00278 00279 00289 template<class View> 00290 class TupleMaxIncExt { 00291 protected: 00292 ViewArray<View> x; 00293 ViewArray<View> z; 00294 public: 00295 TupleMaxIncExt(const ViewArray<View>& x0, 00296 const ViewArray<View>& z0) : x(x0), z(z0) {} 00297 bool operator ()(const int i, const int j) { 00298 if (x[i].max() == x[j].max()) { 00299 if (x[i].min() == x[j].min()) { 00300 if (z[i].max() == z[j].max()) { 00301 return z[i].min() < z[j].min(); 00302 } else { 00303 return z[i].max() < z[j].max(); 00304 } 00305 } else { 00306 return x[i].min() < x[j].min(); 00307 } 00308 } else { 00309 return x[i].max() < x[j].max(); 00310 } 00311 } 00312 }; 00313 00323 template<class View> 00324 class TupleMinInc { 00325 public: 00326 bool operator ()(const View& x, const View& y) { 00327 if (x.min() == y.min()) { 00328 return x.max() < y.max(); 00329 } else { 00330 return x.min() < y.min(); 00331 } 00332 } 00333 }; 00334 00335 00337 template<class View> 00338 class ViewPair { 00339 public: 00340 View x; 00341 View z; 00342 }; 00343 00354 template<class View> 00355 class TupleMinIncExt { 00356 public: 00357 bool operator ()(const ViewPair<View>& x, const ViewPair<View>& y) { 00358 if (x.x.min() == y.x.min()) { 00359 if (x.x.max() == y.x.max()) { 00360 if (x.z.min() == y.z.min()) { 00361 return x.z.max() < y.z.max(); 00362 } else { 00363 return x.z.min() < y.z.min(); 00364 } 00365 } else { 00366 return x.x.max() < y.x.max(); 00367 } 00368 } else { 00369 return x.x.min() < y.x.min(); 00370 } 00371 } 00372 }; 00373 00381 template<class View, bool Perm> 00382 inline bool 00383 array_assigned(Space& home, 00384 ViewArray<View>& x, 00385 ViewArray<View>& y, 00386 ViewArray<View>& z, 00387 bool& subsumed, 00388 bool& match_fixed, 00389 bool&, 00390 bool& noperm_bc) { 00391 00392 bool x_complete = true; 00393 bool y_complete = true; 00394 bool z_complete = true; 00395 00396 for (int i = y.size(); i--; ) { 00397 x_complete &= x[i].assigned(); 00398 y_complete &= y[i].assigned(); 00399 if (Perm) { 00400 z_complete &= z[i].assigned(); 00401 } 00402 } 00403 00404 if (x_complete) { 00405 for (int i = x.size(); i--; ) { 00406 ModEvent me = y[i].eq(home, x[i].val()); 00407 if (me_failed(me)) { 00408 return false; 00409 } 00410 } 00411 if (Perm) { 00412 subsumed = false; 00413 } else { 00414 subsumed = true; 00415 } 00416 } 00417 00418 if (y_complete) { 00419 bool y_equality = true; 00420 for (int i = y.size() - 1; i--; ) { 00421 y_equality &= (y[i].val() == y[i + 1].val()); 00422 } 00423 if (y_equality) { 00424 for (int i = x.size(); i--; ) { 00425 ModEvent me = x[i].eq(home, y[i].val()); 00426 if (me_failed(me)) { 00427 return false; 00428 } 00429 } 00430 if (Perm) { 00431 subsumed = false; 00432 } else { 00433 subsumed = true; 00434 } 00435 noperm_bc = true; 00436 } 00437 } 00438 00439 if (Perm) { 00440 if (z_complete) { 00441 if (x_complete) { 00442 for (int i = x.size(); i--; ) { 00443 ModEvent me = y[z[i].val()].eq(home, x[i].val()); 00444 if (me_failed(me)) { 00445 return false; 00446 } 00447 } 00448 subsumed = true; 00449 return subsumed; 00450 } 00451 if (y_complete) { 00452 for (int i = x.size(); i--; ) { 00453 ModEvent me = x[i].eq(home, y[z[i].val()].val()); 00454 if (me_failed(me)) { 00455 return false; 00456 } 00457 } 00458 subsumed = true; 00459 return subsumed; 00460 } 00461 00462 // validate the permutation 00463 int sum = 0; 00464 for (int i = x.size(); i--; ) { 00465 int pi = z[i].val(); 00466 if (x[i].max() < y[pi].min() || 00467 x[i].min() > y[pi].max()) { 00468 return false; 00469 } 00470 sum += pi; 00471 } 00472 int n = x.size(); 00473 int gauss = ( (n * (n + 1)) / 2); 00474 // if the sum over all assigned permutation variables is not 00475 // equal to the gaussian sum - n they are not distinct, hence invalid 00476 if (sum != gauss - n) { 00477 return false; 00478 } 00479 match_fixed = true; 00480 } 00481 } 00482 return true; 00483 } 00484 00492 template<class View> 00493 forceinline bool 00494 channel(Space& home, ViewArray<View>& x, ViewArray<View>& y, 00495 ViewArray<View>& z, bool& nofix) { 00496 int n = x.size(); 00497 for (int i = n; i--; ) { 00498 if (z[i].assigned()) { 00499 int v = z[i].val(); 00500 if (x[i].assigned()) { 00501 // channel equality from x to y 00502 ModEvent me = y[v].eq(home, x[i].val()); 00503 if (me_failed(me)) 00504 return false; 00505 nofix |= me_modified(me); 00506 } else { 00507 if (y[v].assigned()) { 00508 // channel equality from y to x 00509 ModEvent me = x[i].eq(home, y[v].val()); 00510 if (me_failed(me)) 00511 return false; 00512 nofix |= me_modified(me); 00513 } else { 00514 // constrain upper bound 00515 ModEvent me = x[i].lq(home, y[v].max()); 00516 if (me_failed(me)) 00517 return false; 00518 nofix |= me_modified(me); 00519 00520 // constrain lower bound 00521 me = x[i].gq(home, y[v].min()); 00522 if (me_failed(me)) 00523 return false; 00524 nofix |= me_modified(me); 00525 00526 // constrain the sorted variable 00527 // constrain upper bound 00528 me = y[v].lq(home, x[i].max()); 00529 if (me_failed(me)) 00530 return false; 00531 nofix |= me_modified(me); 00532 00533 // constrain lower bound 00534 me = y[v].gq(home, x[i].min()); 00535 if (me_failed(me)) 00536 return false; 00537 nofix |= me_modified(me); 00538 } 00539 } 00540 } else { 00541 // if the permutation variable is undetermined 00542 int l = z[i].min(); 00543 int r = z[i].max(); 00544 // upper bound 00545 ModEvent me = x[i].lq(home, y[r].max()); 00546 if (me_failed(me)) 00547 return false; 00548 nofix |= me_modified(me); 00549 00550 // lower bound 00551 me = x[i].gq(home, y[l].min()); 00552 if (me_failed(me)) 00553 return false; 00554 nofix |= me_modified(me); 00555 } 00556 } 00557 return true; 00558 } 00559 00560 00561 }}} 00562 00563 00564 // STATISTICS: int-prop