Generated on Wed Jan 4 17:49:11 2006 for Gecode by doxygen 1.4.6

sortsup.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2696 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */     
00021 
00022 namespace Gecode { namespace Int { namespace Sortedness {
00023 
00037   template<class View, class Tuple, bool Perm>
00038   forceinline bool
00039   check_subsumption(Space* home, 
00040                     ViewArray<Tuple>& xz, 
00041                     ViewArray<View>& y, 
00042                     bool& subsumed, 
00043                     int& dropfst) {
00044 
00045     dropfst  = 0;
00046     subsumed = true;
00047     int  xs  = xz.size();
00048     for (int i = 0; i < xs ; i++) {
00049       if (Perm) {
00050         subsumed &= (xz[i][0].assigned() && 
00051                      xz[i][1].assigned() &&
00052                      y[xz[i][1].val()].assigned());
00053         if (subsumed) {
00054           if (xz[i][0].val() != y[xz[i][1].val()].val()) {
00055             return false;
00056           } else {
00057             if (xz[i][1].val() == i) {
00058               dropfst++;
00059             }
00060           }
00061         }
00062       } else {
00063         subsumed &= (xz[i][0].assigned() && y[i].assigned());
00064         if (subsumed) {
00065           if (xz[i][0].val() != y[i].val()) {
00066             return false;
00067           } else {
00068             dropfst++;
00069           }
00070         } 
00071       }
00072     }
00073     return true;
00074   }
00075 
00081   class OfflineMinItem{
00082   public:
00084     int root;  
00086     int parent; 
00088     int rank;   
00090     int name;   
00098     int iset;   
00100     int succ;   
00102     int pred;
00103   };
00104 
00110   class OfflineMin{
00111   private:
00112     OfflineMinItem* sequence;
00113     int* vertices;
00114     int  n;
00115   public:
00116     OfflineMin(void);
00117     ~OfflineMin(void);
00118     OfflineMin(OfflineMinItem[], int[], int);
00123     int  find(int x);
00128     int  find_pc(int x);
00130     void unite(int a, int b, int c);
00132     void makeset(void);
00134     int  size(void);
00135     OfflineMinItem& operator[](int);
00136   };
00137 
00138   OfflineMin::OfflineMin(void){
00139     n = 0;
00140     sequence = NULL;
00141     vertices = NULL;
00142   }
00143 
00144   OfflineMin::OfflineMin(OfflineMinItem s[], int v[], int size){
00145     n = size;
00146     sequence = &s[0];
00147     vertices = &v[0];
00148   }
00149 
00150   OfflineMin::~OfflineMin(void){
00151     sequence = NULL;
00152     vertices = NULL;
00153   }
00154 
00155   forceinline int 
00156   OfflineMin::find(int x) {
00157     while (sequence[x].parent != x) { 
00158       x = sequence[x].parent;
00159     }
00160     // x is now the root of the tree
00161     // return the set, x belongs to 
00162     return sequence[x].name;
00163   }
00164 
00165   forceinline int 
00166   OfflineMin::find_pc(int x){
00167     int vsize = 0;
00168     while (sequence[x].parent != x) { 
00169       vertices[x] = x;
00170       x = sequence[x].parent;
00171     }
00172     // x is now the root of the tree
00173     for (int i = vsize; i--; ) {
00174       sequence[vertices[i]].parent = x;
00175     }
00176     // return the set, x belongs to 
00177     return sequence[x].name;
00178   }
00179 
00180   forceinline void 
00181   OfflineMin::unite(int a, int b, int c){
00182     // c is the union of a and b
00183     int ra = sequence[a].root;
00184     int rb = sequence[b].root;
00185     int large = rb;
00186     int small = ra;
00187     if (sequence[ra].rank > sequence[rb].rank) {
00188       large = ra;
00189       small = rb;
00190     }
00191     sequence[small].parent =  large;
00192     sequence[large].rank   += sequence[small].rank;
00193     sequence[large].name   =  c;
00194     sequence[c].root       =  large;
00195   }
00196 
00197   forceinline void
00198   OfflineMin::makeset(void){
00199     for(int i = n; i--; ){
00200       OfflineMinItem& cur = sequence[i];
00201       cur.rank   = 0;     // initially each set is empty
00202       cur.name   = i;     // it has its own name
00203       cur.root   = i;     // it is the root node         
00204       cur.parent = i;     // it is its own parent         
00205       cur.pred   = i - 1;    
00206       cur.succ   = i + 1;
00207       cur.iset   = -5;
00208     }
00209   }
00210 
00211   forceinline int 
00212   OfflineMin::size(void){
00213     return n;
00214   }
00215 
00216   forceinline OfflineMinItem& 
00217   OfflineMin::operator [](int i){
00218     return sequence[i];
00219   }
00220 
00222   forceinline std::ostream& 
00223   operator<<(std::ostream& os,  OfflineMin seq){
00224     for (int i = 0; i < seq.size();i++) {
00225       os << "Succ(" <<seq[i].succ   << ") "
00226          << "Pred(" <<seq[i].pred   << ") "
00227          << "Root(" <<seq[i].root   << ") "
00228          << "Par (" <<seq[i].parent << ") "
00229          << "Rank(" <<seq[i].rank   << ") "
00230          << "Name(" <<seq[i].name   << ") "
00231          << "Set (" <<seq[i].iset   << ") \n";
00232     }
00233     return os;
00234   }
00235 
00245   template <class Tuple>
00246   class TupleMaxInc {
00247   protected:
00248     ViewArray<Tuple> x;
00249   public:
00250     TupleMaxInc(const ViewArray<Tuple>& x0) : x(x0) {}
00251     bool operator()(const int i, const int j) {
00252         return x[i][0].max() < x[j][0].max();
00253     }
00254   };
00255 
00265   template <class View>
00266   class TupleMinInc {
00267   public:
00268     bool operator()(const View& x, const View& y) {
00269         return x[0].min() < y[0].min();
00270     }
00271   };
00272 
00281   template <class View>
00282   class TupleMinIncPerm {
00283   public:
00284     bool operator()(const View& x, const View& y) {
00285       return x[1].min() < y[1].min();
00286     }
00287   };
00288 
00296   template<class View, class Tuple, bool Perm, bool shared>
00297   forceinline bool
00298   array_assigned(Space* home, 
00299                  ViewArray<Tuple>& xz, 
00300                  ViewArray<View>& y, 
00301                  bool& subsumed, 
00302                  bool& match_fixed, 
00303                  bool& nofix) {
00304 
00305     bool x_complete = true;
00306     bool y_complete = true;
00307     bool z_complete = true;
00308 
00309     for (int i = y.size(); i--; ) {
00310       x_complete &= xz[i][0].assigned();
00311       y_complete &= y[i].assigned();
00312       if (Perm) {
00313         z_complete &= xz[i][1].assigned();
00314       }
00315     }
00316 
00317     if (x_complete) {
00318       for (int i = xz.size(); i--; ) {
00319         if (shared && y[i].modified()) {
00320           nofix = true;
00321           return true;
00322         }
00323         ModEvent me = y[i].eq(home, xz[i][0].val());
00324         if (me_failed(me)) {
00325           return false;
00326         }
00327       }
00328       if (Perm) {
00329         subsumed = false;
00330       } else {
00331         subsumed = true;
00332       }
00333     }
00334 
00335     if (y_complete) {
00336       bool y_equality = true;
00337       for (int i = y.size() - 1; i--; ) {
00338         y_equality &= (y[i].val() == y[i + 1].val());
00339       }
00340       if (y_equality) {
00341         for (int i = xz.size(); i--; ) {
00342           if (shared && xz[i][0].modified()) {
00343             nofix = true;
00344             return true;
00345           }
00346           ModEvent me = xz[i][0].eq(home, y[i].val());
00347           if (me_failed(me)) {
00348             return false;
00349           }
00350         }
00351         if (Perm) {
00352           subsumed = false;
00353         } else {
00354           subsumed = true;
00355         }
00356       }
00357     }
00358 
00359     if (Perm) {
00360       if (z_complete) {
00361         if (x_complete) {
00362           for (int i = xz.size(); i--; ) {
00363             ModEvent me = y[xz[i][1].val()].eq(home, xz[i][0].val());
00364             if (me_failed(me)) {
00365               return false;
00366             }
00367           }
00368           subsumed = true;
00369           return subsumed;
00370         }
00371         if (y_complete) {
00372           for (int i = xz.size(); i--; ) {
00373             if (shared && xz[i][0].modified()) {
00374               nofix = true;
00375               return true;
00376             }
00377 
00378             ModEvent me = xz[i][0].eq(home, y[xz[i][1].val()].val());
00379             if (me_failed(me)) {
00380               return false;
00381             }
00382           }
00383           subsumed = true;
00384           return subsumed;
00385         }
00386 
00387         // validate the permutation
00388         int sum = 0;
00389         for (int i = xz.size(); i--; ) {
00390           int pi = xz[i][1].val();
00391           if (xz[i][0].max() < y[pi].min() ||
00392               xz[i][0].min() > y[pi].max()) {
00393             return false;
00394           }
00395           sum += pi;
00396         }
00397         int n = xz.size();
00398         int gauss = ( (n * (n + 1)) / 2);
00399         // if the sum over all assigned permutation variables is not
00400         // equal to the gaussian sum - n they are not distinct, hence invalid
00401         if (sum != gauss - n) {
00402           return false;
00403         }
00404         match_fixed = true;
00405       }
00406     }
00407     return true;
00408   }
00409 
00410 }}}
00411 
00412 
00413 // STATISTICS: int-prop