Generated on Thu Mar 22 10:39:41 2012 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  *  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