Generated on Fri Oct 19 11:25:09 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // x is now the root of the tree
00191     // return the set, x belongs to
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     // x is now the root of the tree
00203     for (int i=0; i<vsize; i++)
00204       sequence[vertices[i]].parent = x;
00205     // return the set, x belongs to
00206     return sequence[x].name;
00207   }
00208 
00209   forceinline void
00210   OfflineMin::unite(int a, int b, int c){
00211     // c is the union of a and b
00212     int ra = sequence[a].root;
00213     int rb = sequence[b].root;
00214     int large = rb;
00215     int small = ra;
00216     if (sequence[ra].rank > sequence[rb].rank) {
00217       large = ra;
00218       small = rb;
00219     }
00220     sequence[small].parent =  large;
00221     sequence[large].rank   += sequence[small].rank;
00222     sequence[large].name   =  c;
00223     sequence[c].root       =  large;
00224   }
00225 
00226   forceinline void
00227   OfflineMin::makeset(void){
00228     for(int i = n; i--; ){
00229       OfflineMinItem& cur = sequence[i];
00230       cur.rank   = 0;     // initially each set is empty
00231       cur.name   = i;     // it has its own name
00232       cur.root   = i;     // it is the root node
00233       cur.parent = i;     // it is its own parent
00234       cur.pred   = i - 1;
00235       cur.succ   = i + 1;
00236       cur.iset   = -5;
00237     }
00238   }
00239 
00240   forceinline int
00241   OfflineMin::size(void){
00242     return n;
00243   }
00244 
00245   forceinline OfflineMinItem&
00246   OfflineMin::operator [](int i){
00247     return sequence[i];
00248   }
00249 
00259   template<class View>
00260   class TupleMaxInc {
00261   protected:
00262     ViewArray<View> x;
00263   public:
00264     TupleMaxInc(const ViewArray<View>& x0) : x(x0) {}
00265     bool operator ()(const int i, const int j) {
00266       if (x[i].max() == x[j].max()) {
00267         return x[i].min() < x[j].min();
00268       } else {
00269         return x[i].max() < x[j].max();
00270       }
00271     }
00272   };
00273 
00274 
00284   template<class View>
00285   class TupleMaxIncExt {
00286   protected:
00287     ViewArray<View> x;
00288     ViewArray<View> z;
00289   public:
00290     TupleMaxIncExt(const ViewArray<View>& x0,
00291                    const ViewArray<View>& z0) : x(x0), z(z0) {}
00292     bool operator ()(const int i, const int j) {
00293       if (x[i].max() == x[j].max()) {
00294         if (x[i].min() == x[j].min()) {
00295           if (z[i].max() == z[j].max()) {
00296             return z[i].min() < z[j].min();
00297           } else {
00298             return z[i].max() < z[j].max();
00299           }
00300         } else {
00301           return x[i].min() < x[j].min();
00302         }
00303       } else {
00304         return x[i].max() < x[j].max();
00305       }
00306     }
00307   };
00308 
00318   template<class View>
00319   class TupleMinInc {
00320   public:
00321     bool operator ()(const View& x, const View& y) {
00322       if (x.min() == y.min()) {
00323         return x.max() < y.max();
00324       } else {
00325         return x.min() < y.min();
00326       }
00327     }
00328   };
00329 
00330 
00332   template<class View>
00333   class ViewPair {
00334   public:
00335     View x;
00336     View z;
00337   };
00338 
00349   template<class View>
00350   class TupleMinIncExt {
00351   public:
00352     bool operator ()(const ViewPair<View>& x, const ViewPair<View>& y) {
00353       if (x.x.min() == y.x.min()) {
00354         if (x.x.max() == y.x.max()) {
00355           if (x.z.min() == y.z.min()) {
00356             return x.z.max() < y.z.max();
00357           } else {
00358             return x.z.min() < y.z.min();
00359           }
00360         } else {
00361           return x.x.max() < y.x.max();
00362         }
00363       } else {
00364         return x.x.min() < y.x.min();
00365       }
00366     }
00367   };
00368 
00376   template<class View, bool Perm>
00377   inline bool
00378   array_assigned(Space& home,
00379                  ViewArray<View>& x,
00380                  ViewArray<View>& y,
00381                  ViewArray<View>& z,
00382                  bool& subsumed,
00383                  bool& match_fixed,
00384                  bool&,
00385                  bool& noperm_bc) {
00386 
00387     bool x_complete = true;
00388     bool y_complete = true;
00389     bool z_complete = true;
00390 
00391     for (int i=0; i<y.size(); i++) {
00392       x_complete &= x[i].assigned();
00393       y_complete &= y[i].assigned();
00394       if (Perm) {
00395         z_complete &= z[i].assigned();
00396       }
00397     }
00398 
00399     if (x_complete) {
00400       for (int i=0; i<x.size(); i++) {
00401         ModEvent me = y[i].eq(home, x[i].val());
00402         if (me_failed(me)) {
00403           return false;
00404         }
00405       }
00406       if (Perm) {
00407         subsumed = false;
00408       } else {
00409         subsumed = true;
00410       }
00411     }
00412 
00413     if (y_complete) {
00414       bool y_equality = true;
00415       for (int i=1; i<y.size(); i++) {
00416         y_equality &= (y[i-1].val() == y[i].val());
00417       }
00418       if (y_equality) {
00419         for (int i=0; i<x.size(); i++) {
00420           ModEvent me = x[i].eq(home, y[i].val());
00421           if (me_failed(me)) {
00422             return false;
00423           }
00424         }
00425         if (Perm) {
00426           subsumed = false;
00427         } else {
00428           subsumed = true;
00429         }
00430         noperm_bc = true;
00431       }
00432     }
00433 
00434     if (Perm) {
00435       if (z_complete) {
00436         if (x_complete) {
00437           for (int i=0; i<x.size(); i++) {
00438             ModEvent me = y[z[i].val()].eq(home, x[i].val());
00439             if (me_failed(me)) {
00440               return false;
00441             }
00442           }
00443           subsumed = true;
00444           return subsumed;
00445         }
00446         if (y_complete) {
00447           for (int i=0; i<x.size(); i++) {
00448             ModEvent me = x[i].eq(home, y[z[i].val()].val());
00449             if (me_failed(me)) {
00450               return false;
00451             }
00452           }
00453           subsumed = true;
00454           return subsumed;
00455         }
00456 
00457         // validate the permutation
00458         int sum = 0;
00459         for (int i=0; i<x.size(); i++) {
00460           int pi = z[i].val();
00461           if (x[i].max() < y[pi].min() ||
00462               x[i].min() > y[pi].max()) {
00463             return false;
00464           }
00465           sum += pi;
00466         }
00467         int n = x.size();
00468         int gauss = ( (n * (n + 1)) / 2);
00469         // if the sum over all assigned permutation variables is not
00470         // equal to the gaussian sum - n they are not distinct, hence invalid
00471         if (sum != gauss - n) {
00472           return false;
00473         }
00474         match_fixed = true;
00475       }
00476     }
00477     return true;
00478   }
00479 
00487   template<class View>
00488   forceinline bool
00489   channel(Space& home, ViewArray<View>& x, ViewArray<View>& y,
00490           ViewArray<View>& z, bool& nofix) {
00491     int n = x.size();
00492     for (int i=0; i<n; i++) {
00493       if (z[i].assigned()) {
00494         int v = z[i].val();
00495         if (x[i].assigned()) {
00496           // channel equality from x to y
00497           ModEvent me = y[v].eq(home, x[i].val());
00498           if (me_failed(me))
00499             return false;
00500           nofix |= me_modified(me);
00501         } else {
00502           if (y[v].assigned()) {
00503             // channel equality from y to x
00504             ModEvent me = x[i].eq(home, y[v].val());
00505             if (me_failed(me))
00506               return false;
00507             nofix |= me_modified(me);
00508           } else {
00509             // constrain upper bound
00510             ModEvent me = x[i].lq(home, y[v].max());
00511             if (me_failed(me))
00512               return false;
00513             nofix |= me_modified(me);
00514 
00515             // constrain lower bound
00516             me = x[i].gq(home, y[v].min());
00517             if (me_failed(me))
00518               return false;
00519             nofix |= me_modified(me);
00520 
00521             // constrain the sorted variable
00522             // constrain upper bound
00523             me = y[v].lq(home, x[i].max());
00524             if (me_failed(me))
00525               return false;
00526             nofix |= me_modified(me);
00527 
00528             // constrain lower bound
00529             me = y[v].gq(home, x[i].min());
00530             if (me_failed(me))
00531               return false;
00532             nofix |= me_modified(me);
00533           }
00534         }
00535       } else {
00536         // if the permutation variable is undetermined
00537         int l = z[i].min();
00538         int r = z[i].max();
00539         // upper bound
00540         ModEvent me = x[i].lq(home, y[r].max());
00541         if (me_failed(me))
00542           return false;
00543         nofix |= me_modified(me);
00544 
00545         // lower bound
00546         me = x[i].gq(home, y[l].min());
00547         if (me_failed(me))
00548           return false;
00549         nofix |= me_modified(me);
00550       }
00551     }
00552     return true;
00553   }
00554 
00555 
00556 }}}
00557 
00558 
00559 // STATISTICS: int-prop