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
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, class Tuple, bool Perm>
00081 inline bool
00082 check_subsumption(Space*,
00083 ViewArray<Tuple>& xz,
00084 ViewArray<View>& y,
00085 bool& subsumed,
00086 int& dropfst) {
00087
00088 dropfst = 0;
00089 subsumed = true;
00090 int xs = xz.size();
00091 for (int i = 0; i < xs ; i++) {
00092 if (Perm) {
00093 subsumed &= (xz[i][0].assigned() &&
00094 xz[i][1].assigned() &&
00095 y[xz[i][1].val()].assigned());
00096 if (subsumed) {
00097 if (xz[i][0].val() != y[xz[i][1].val()].val()) {
00098 return false;
00099 } else {
00100 if (xz[i][1].val() == i) {
00101 dropfst++;
00102 }
00103 }
00104 }
00105 } else {
00106 subsumed &= (xz[i][0].assigned() && y[i].assigned());
00107 if (subsumed) {
00108 if (xz[i][0].val() != y[i].val()) {
00109 return false;
00110 } else {
00111 dropfst++;
00112 }
00113 }
00114 }
00115 }
00116 return true;
00117 }
00118
00124 class OfflineMinItem {
00125 public:
00127 int root;
00129 int parent;
00131 int rank;
00133 int name;
00141 int iset;
00143 int succ;
00145 int pred;
00146 };
00147
00153 class OfflineMin {
00154 private:
00155 OfflineMinItem* sequence;
00156 int* vertices;
00157 int n;
00158 public:
00159 OfflineMin(void);
00160 OfflineMin(OfflineMinItem[], int[], int);
00165 int find(int x);
00170 int find_pc(int x);
00172 void unite(int a, int b, int c);
00174 void makeset(void);
00176 int size(void);
00177 OfflineMinItem& operator[](int);
00178 };
00179
00180 OfflineMin::OfflineMin(void){
00181 n = 0;
00182 sequence = NULL;
00183 vertices = NULL;
00184 }
00185
00186 OfflineMin::OfflineMin(OfflineMinItem s[], int v[], int size){
00187 n = size;
00188 sequence = &s[0];
00189 vertices = &v[0];
00190 }
00191
00192 forceinline int
00193 OfflineMin::find(int x) {
00194 while (sequence[x].parent != x) {
00195 x = sequence[x].parent;
00196 }
00197
00198
00199 return sequence[x].name;
00200 }
00201
00202 forceinline int
00203 OfflineMin::find_pc(int x){
00204 int vsize = 0;
00205 while (sequence[x].parent != x) {
00206 vertices[x] = x;
00207 x = sequence[x].parent;
00208 }
00209
00210 for (int i = vsize; i--; ) {
00211 sequence[vertices[i]].parent = x;
00212 }
00213
00214 return sequence[x].name;
00215 }
00216
00217 forceinline void
00218 OfflineMin::unite(int a, int b, int c){
00219
00220 int ra = sequence[a].root;
00221 int rb = sequence[b].root;
00222 int large = rb;
00223 int small = ra;
00224 if (sequence[ra].rank > sequence[rb].rank) {
00225 large = ra;
00226 small = rb;
00227 }
00228 sequence[small].parent = large;
00229 sequence[large].rank += sequence[small].rank;
00230 sequence[large].name = c;
00231 sequence[c].root = large;
00232 }
00233
00234 forceinline void
00235 OfflineMin::makeset(void){
00236 for(int i = n; i--; ){
00237 OfflineMinItem& cur = sequence[i];
00238 cur.rank = 0;
00239 cur.name = i;
00240 cur.root = i;
00241 cur.parent = i;
00242 cur.pred = i - 1;
00243 cur.succ = i + 1;
00244 cur.iset = -5;
00245 }
00246 }
00247
00248 forceinline int
00249 OfflineMin::size(void){
00250 return n;
00251 }
00252
00253 forceinline OfflineMinItem&
00254 OfflineMin::operator [](int i){
00255 return sequence[i];
00256 }
00257
00267 template <class Tuple>
00268 class TupleMaxInc {
00269 protected:
00270 ViewArray<Tuple> x;
00271 public:
00272 TupleMaxInc(const ViewArray<Tuple>& x0) : x(x0) {}
00273 bool operator()(const int i, const int j) {
00274 if (x[i][0].max() == x[j][0].max()) {
00275 return x[i][0].min() < x[j][0].min();
00276 } else {
00277 return x[i][0].max() < x[j][0].max();
00278 }
00279 }
00280 };
00281
00282
00292 template <class Tuple>
00293 class TupleMaxIncExt {
00294 protected:
00295 ViewArray<Tuple> x;
00296 public:
00297 TupleMaxIncExt(const ViewArray<Tuple>& x0) : x(x0) {}
00298 bool operator()(const int i, const int j) {
00299 if (x[i][0].max() == x[j][0].max()) {
00300 if (x[i][0].min() == x[j][0].min()) {
00301 if (x[i][1].max() == x[j][1].max()) {
00302 return x[i][1].min() < x[j][1].min();
00303 } else {
00304 return x[i][1].max() < x[j][1].max();
00305 }
00306 } else {
00307 return x[i][0].min() < x[j][0].min();
00308 }
00309 } else {
00310 return x[i][0].max() < x[j][0].max();
00311 }
00312 }
00313 };
00314
00324 template <class View>
00325 class TupleMinInc {
00326 public:
00327 bool operator()(const View& x, const View& y) {
00328 if (x[0].min() == y[0].min()) {
00329 return x[0].max() < y[0].max();
00330 } else {
00331 return x[0].min() < y[0].min();
00332 }
00333 }
00334 };
00335
00347 template <class View>
00348 class TupleMinIncExt {
00349 public:
00350 bool operator()(const View& x, const View& y) {
00351 if (x[0].min() == y[0].min()) {
00352 if (x[0].max() == y[0].max()) {
00353 if (x[1].min() == y[1].min()) {
00354 return x[1].max() < y[1].max();
00355 } else {
00356 return x[1].min() < y[1].min();
00357 }
00358 } else {
00359 return x[0].max() < y[0].max();
00360 }
00361 } else {
00362 return x[0].min() < y[0].min();
00363 }
00364 }
00365 };
00366
00375 template <class View>
00376 class TupleMinIncPerm {
00377 public:
00378 bool operator()(const View& x, const View& y) {
00379 if (x[1].min() == y[1].min()) {
00380 return x[1].max() < y[1].max();
00381 } else {
00382 return x[1].min() < y[1].min();
00383 }
00384 }
00385 };
00386
00395 template <class View>
00396 class TupleMaxIncPerm {
00397 public:
00398 bool operator()(const View& x, const View& y) {
00399 if (x[1].max() == y[1].max()) {
00400 return x[1].min() < y[1].min();
00401 } else {
00402 return x[1].max() < y[1].max();
00403 }
00404 }
00405 };
00406
00414 template<class View, class Tuple, bool Perm>
00415 inline bool
00416 array_assigned(Space* home,
00417 ViewArray<Tuple>& xz,
00418 ViewArray<View>& y,
00419 bool& subsumed,
00420 bool& match_fixed,
00421 bool&,
00422 bool& noperm_bc) {
00423
00424 bool x_complete = true;
00425 bool y_complete = true;
00426 bool z_complete = true;
00427
00428 for (int i = y.size(); i--; ) {
00429 x_complete &= xz[i][0].assigned();
00430 y_complete &= y[i].assigned();
00431 if (Perm) {
00432 z_complete &= xz[i][1].assigned();
00433 }
00434 }
00435
00436 if (x_complete) {
00437 for (int i = xz.size(); i--; ) {
00438 ModEvent me = y[i].eq(home, xz[i][0].val());
00439 if (me_failed(me)) {
00440 return false;
00441 }
00442 }
00443 if (Perm) {
00444 subsumed = false;
00445 } else {
00446 subsumed = true;
00447 }
00448 }
00449
00450 if (y_complete) {
00451 bool y_equality = true;
00452 for (int i = y.size() - 1; i--; ) {
00453 y_equality &= (y[i].val() == y[i + 1].val());
00454 }
00455 if (y_equality) {
00456 for (int i = xz.size(); i--; ) {
00457 ModEvent me = xz[i][0].eq(home, y[i].val());
00458 if (me_failed(me)) {
00459 return false;
00460 }
00461 }
00462 if (Perm) {
00463 subsumed = false;
00464 } else {
00465 subsumed = true;
00466 }
00467 noperm_bc = true;
00468 }
00469 }
00470
00471 if (Perm) {
00472 if (z_complete) {
00473 if (x_complete) {
00474 for (int i = xz.size(); i--; ) {
00475 ModEvent me = y[xz[i][1].val()].eq(home, xz[i][0].val());
00476 if (me_failed(me)) {
00477 return false;
00478 }
00479 }
00480 subsumed = true;
00481 return subsumed;
00482 }
00483 if (y_complete) {
00484 for (int i = xz.size(); i--; ) {
00485 ModEvent me = xz[i][0].eq(home, y[xz[i][1].val()].val());
00486 if (me_failed(me)) {
00487 return false;
00488 }
00489 }
00490 subsumed = true;
00491 return subsumed;
00492 }
00493
00494
00495 int sum = 0;
00496 for (int i = xz.size(); i--; ) {
00497 int pi = xz[i][1].val();
00498 if (xz[i][0].max() < y[pi].min() ||
00499 xz[i][0].min() > y[pi].max()) {
00500 return false;
00501 }
00502 sum += pi;
00503 }
00504 int n = xz.size();
00505 int gauss = ( (n * (n + 1)) / 2);
00506
00507
00508 if (sum != gauss - n) {
00509 return false;
00510 }
00511 match_fixed = true;
00512 }
00513 }
00514 return true;
00515 }
00516
00524 template<class View, class Tuple, bool Perm>
00525 forceinline bool
00526 channel(Space* home, ViewArray<Tuple>& xz, ViewArray<View>& y, bool& nofix) {
00527 int n = xz.size();
00528 for (int i = n; i--; ) {
00529 if (xz[i][1].assigned()) {
00530
00531 int v = xz[i][1].val();
00532 if (xz[i][0].assigned()) {
00533
00534 ModEvent me = y[v].eq(home, xz[i][0].val());
00535 if (me_failed(me))
00536 return false;
00537 nofix |= me_modified(me);
00538 } else {
00539 if (y[v].assigned()) {
00540
00541 ModEvent me = xz[i][0].eq(home, y[v].val());
00542 if (me_failed(me))
00543 return false;
00544 nofix |= me_modified(me);
00545 } else {
00546
00547 ModEvent me = xz[i][0].lq(home, y[v].max());
00548 if (me_failed(me))
00549 return false;
00550 nofix |= me_modified(me);
00551
00552
00553 me = xz[i][0].gq(home, y[v].min());
00554 if (me_failed(me))
00555 return false;
00556 nofix |= me_modified(me);
00557
00558
00559
00560 me = y[v].lq(home, xz[i][0].max());
00561 if (me_failed(me))
00562 return false;
00563 nofix |= me_modified(me);
00564
00565
00566 me = y[v].gq(home, xz[i][0].min());
00567 if (me_failed(me))
00568 return false;
00569 nofix |= me_modified(me);
00570 }
00571 }
00572 } else {
00573
00574 int l = xz[i][1].min();
00575 int r = xz[i][1].max();
00576
00577 ModEvent me = xz[i][0].lq(home, y[r].max());
00578 if (me_failed(me))
00579 return false;
00580 nofix |= me_modified(me);
00581
00582
00583 me = xz[i][0].gq(home, y[l].min());
00584 if (me_failed(me))
00585 return false;
00586 nofix |= me_modified(me);
00587 }
00588 }
00589 return true;
00590 }
00591
00592
00593 }}}
00594
00595
00596