sortsup.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 namespace Gecode { namespace Int { namespace Sorted {
00035
00039 class Rank {
00040 public:
00042 int min;
00044 int max;
00045 };
00046
00053 class SccComponent {
00054 public:
00056 int leftmost;
00058 int left;
00060 int right;
00062 int rightmost;
00063 };
00064
00076 template<class View, bool Perm>
00077 inline bool
00078 check_subsumption(ViewArray<View>& x, ViewArray<View>& y, ViewArray<View>& z,
00079 bool& subsumed, int& dropfst) {
00080
00081 dropfst = 0;
00082 subsumed = true;
00083 int xs = x.size();
00084 for (int i = 0; i < xs ; i++) {
00085 if (Perm) {
00086 subsumed &= (x[i].assigned() &&
00087 z[i].assigned() &&
00088 y[z[i].val()].assigned());
00089 if (subsumed) {
00090 if (x[i].val() != y[z[i].val()].val()) {
00091 return false;
00092 } else {
00093 if (z[i].val() == i) {
00094 dropfst++;
00095 }
00096 }
00097 }
00098 } else {
00099 subsumed &= (x[i].assigned() && y[i].assigned());
00100 if (subsumed) {
00101 if (x[i].val() != y[i].val()) {
00102 return false;
00103 } else {
00104 dropfst++;
00105 }
00106 }
00107 }
00108 }
00109 return true;
00110 }
00111
00117 class OfflineMinItem {
00118 public:
00120 int root;
00122 int parent;
00124 int rank;
00126 int name;
00134 int iset;
00136 int succ;
00138 int pred;
00139 };
00140
00146 class OfflineMin {
00147 private:
00148 OfflineMinItem* sequence;
00149 int* vertices;
00150 int n;
00151 public:
00152 OfflineMin(void);
00153 OfflineMin(OfflineMinItem[], int[], int);
00158 int find(int x);
00163 int find_pc(int x);
00165 void unite(int a, int b, int c);
00167 void makeset(void);
00169 int size(void);
00170 OfflineMinItem& operator [](int);
00171 };
00172
00173 OfflineMin::OfflineMin(void){
00174 n = 0;
00175 sequence = NULL;
00176 vertices = NULL;
00177 }
00178
00179 OfflineMin::OfflineMin(OfflineMinItem s[], int v[], int size){
00180 n = size;
00181 sequence = &s[0];
00182 vertices = &v[0];
00183 }
00184
00185 forceinline int
00186 OfflineMin::find(int x) {
00187 while (sequence[x].parent != x) {
00188 x = sequence[x].parent;
00189 }
00190
00191
00192 return sequence[x].name;
00193 }
00194
00195 forceinline int
00196 OfflineMin::find_pc(int x){
00197 int vsize = 0;
00198 while (sequence[x].parent != x) {
00199 vertices[x] = x;
00200 x = sequence[x].parent;
00201 }
00202
00203 for (int i = vsize; i--; ) {
00204 sequence[vertices[i]].parent = x;
00205 }
00206
00207 return sequence[x].name;
00208 }
00209
00210 forceinline void
00211 OfflineMin::unite(int a, int b, int c){
00212
00213 int ra = sequence[a].root;
00214 int rb = sequence[b].root;
00215 int large = rb;
00216 int small = ra;
00217 if (sequence[ra].rank > sequence[rb].rank) {
00218 large = ra;
00219 small = rb;
00220 }
00221 sequence[small].parent = large;
00222 sequence[large].rank += sequence[small].rank;
00223 sequence[large].name = c;
00224 sequence[c].root = large;
00225 }
00226
00227 forceinline void
00228 OfflineMin::makeset(void){
00229 for(int i = n; i--; ){
00230 OfflineMinItem& cur = sequence[i];
00231 cur.rank = 0;
00232 cur.name = i;
00233 cur.root = i;
00234 cur.parent = i;
00235 cur.pred = i - 1;
00236 cur.succ = i + 1;
00237 cur.iset = -5;
00238 }
00239 }
00240
00241 forceinline int
00242 OfflineMin::size(void){
00243 return n;
00244 }
00245
00246 forceinline OfflineMinItem&
00247 OfflineMin::operator [](int i){
00248 return sequence[i];
00249 }
00250
00260 template<class View>
00261 class TupleMaxInc {
00262 protected:
00263 ViewArray<View> x;
00264 public:
00265 TupleMaxInc(const ViewArray<View>& x0) : x(x0) {}
00266 bool operator ()(const int i, const int j) {
00267 if (x[i].max() == x[j].max()) {
00268 return x[i].min() < x[j].min();
00269 } else {
00270 return x[i].max() < x[j].max();
00271 }
00272 }
00273 };
00274
00275
00285 template<class View>
00286 class TupleMaxIncExt {
00287 protected:
00288 ViewArray<View> x;
00289 ViewArray<View> z;
00290 public:
00291 TupleMaxIncExt(const ViewArray<View>& x0,
00292 const ViewArray<View>& z0) : x(x0), z(z0) {}
00293 bool operator ()(const int i, const int j) {
00294 if (x[i].max() == x[j].max()) {
00295 if (x[i].min() == x[j].min()) {
00296 if (z[i].max() == z[j].max()) {
00297 return z[i].min() < z[j].min();
00298 } else {
00299 return z[i].max() < z[j].max();
00300 }
00301 } else {
00302 return x[i].min() < x[j].min();
00303 }
00304 } else {
00305 return x[i].max() < x[j].max();
00306 }
00307 }
00308 };
00309
00319 template<class View>
00320 class TupleMinInc {
00321 public:
00322 bool operator ()(const View& x, const View& y) {
00323 if (x.min() == y.min()) {
00324 return x.max() < y.max();
00325 } else {
00326 return x.min() < y.min();
00327 }
00328 }
00329 };
00330
00331
00333 template<class View>
00334 class ViewPair {
00335 public:
00336 View x;
00337 View z;
00338 };
00339
00350 template<class View>
00351 class TupleMinIncExt {
00352 public:
00353 bool operator ()(const ViewPair<View>& x, const ViewPair<View>& y) {
00354 if (x.x.min() == y.x.min()) {
00355 if (x.x.max() == y.x.max()) {
00356 if (x.z.min() == y.z.min()) {
00357 return x.z.max() < y.z.max();
00358 } else {
00359 return x.z.min() < y.z.min();
00360 }
00361 } else {
00362 return x.x.max() < y.x.max();
00363 }
00364 } else {
00365 return x.x.min() < y.x.min();
00366 }
00367 }
00368 };
00369
00377 template<class View, bool Perm>
00378 inline bool
00379 array_assigned(Space& home,
00380 ViewArray<View>& x,
00381 ViewArray<View>& y,
00382 ViewArray<View>& z,
00383 bool& subsumed,
00384 bool& match_fixed,
00385 bool&,
00386 bool& noperm_bc) {
00387
00388 bool x_complete = true;
00389 bool y_complete = true;
00390 bool z_complete = true;
00391
00392 for (int i = y.size(); i--; ) {
00393 x_complete &= x[i].assigned();
00394 y_complete &= y[i].assigned();
00395 if (Perm) {
00396 z_complete &= z[i].assigned();
00397 }
00398 }
00399
00400 if (x_complete) {
00401 for (int i = x.size(); i--; ) {
00402 ModEvent me = y[i].eq(home, x[i].val());
00403 if (me_failed(me)) {
00404 return false;
00405 }
00406 }
00407 if (Perm) {
00408 subsumed = false;
00409 } else {
00410 subsumed = true;
00411 }
00412 }
00413
00414 if (y_complete) {
00415 bool y_equality = true;
00416 for (int i = y.size() - 1; i--; ) {
00417 y_equality &= (y[i].val() == y[i + 1].val());
00418 }
00419 if (y_equality) {
00420 for (int i = x.size(); i--; ) {
00421 ModEvent me = x[i].eq(home, y[i].val());
00422 if (me_failed(me)) {
00423 return false;
00424 }
00425 }
00426 if (Perm) {
00427 subsumed = false;
00428 } else {
00429 subsumed = true;
00430 }
00431 noperm_bc = true;
00432 }
00433 }
00434
00435 if (Perm) {
00436 if (z_complete) {
00437 if (x_complete) {
00438 for (int i = x.size(); i--; ) {
00439 ModEvent me = y[z[i].val()].eq(home, x[i].val());
00440 if (me_failed(me)) {
00441 return false;
00442 }
00443 }
00444 subsumed = true;
00445 return subsumed;
00446 }
00447 if (y_complete) {
00448 for (int i = x.size(); i--; ) {
00449 ModEvent me = x[i].eq(home, y[z[i].val()].val());
00450 if (me_failed(me)) {
00451 return false;
00452 }
00453 }
00454 subsumed = true;
00455 return subsumed;
00456 }
00457
00458
00459 int sum = 0;
00460 for (int i = x.size(); i--; ) {
00461 int pi = z[i].val();
00462 if (x[i].max() < y[pi].min() ||
00463 x[i].min() > y[pi].max()) {
00464 return false;
00465 }
00466 sum += pi;
00467 }
00468 int n = x.size();
00469 int gauss = ( (n * (n + 1)) / 2);
00470
00471
00472 if (sum != gauss - n) {
00473 return false;
00474 }
00475 match_fixed = true;
00476 }
00477 }
00478 return true;
00479 }
00480
00488 template<class View>
00489 forceinline bool
00490 channel(Space& home, ViewArray<View>& x, ViewArray<View>& y,
00491 ViewArray<View>& z, bool& nofix) {
00492 int n = x.size();
00493 for (int i = n; i--; ) {
00494 if (z[i].assigned()) {
00495 int v = z[i].val();
00496 if (x[i].assigned()) {
00497
00498 ModEvent me = y[v].eq(home, x[i].val());
00499 if (me_failed(me))
00500 return false;
00501 nofix |= me_modified(me);
00502 } else {
00503 if (y[v].assigned()) {
00504
00505 ModEvent me = x[i].eq(home, y[v].val());
00506 if (me_failed(me))
00507 return false;
00508 nofix |= me_modified(me);
00509 } else {
00510
00511 ModEvent me = x[i].lq(home, y[v].max());
00512 if (me_failed(me))
00513 return false;
00514 nofix |= me_modified(me);
00515
00516
00517 me = x[i].gq(home, y[v].min());
00518 if (me_failed(me))
00519 return false;
00520 nofix |= me_modified(me);
00521
00522
00523
00524 me = y[v].lq(home, x[i].max());
00525 if (me_failed(me))
00526 return false;
00527 nofix |= me_modified(me);
00528
00529
00530 me = y[v].gq(home, x[i].min());
00531 if (me_failed(me))
00532 return false;
00533 nofix |= me_modified(me);
00534 }
00535 }
00536 } else {
00537
00538 int l = z[i].min();
00539 int r = z[i].max();
00540
00541 ModEvent me = x[i].lq(home, y[r].max());
00542 if (me_failed(me))
00543 return false;
00544 nofix |= me_modified(me);
00545
00546
00547 me = x[i].gq(home, y[l].min());
00548 if (me_failed(me))
00549 return false;
00550 nofix |= me_modified(me);
00551 }
00552 }
00553 return true;
00554 }
00555
00556
00557 }}}
00558
00559
00560