Generated on Wed Mar 19 07:30:00 2008 for Gecode by doxygen 1.5.5

sortsup.icc

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: 2007-12-17 16:45:17 +0100 (Mon, 17 Dec 2007) $ by $Author: schulte $
00011  *     $Revision: 5732 $
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, 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     // x is now the root of the tree
00198     // return the set, x belongs to
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     // x is now the root of the tree
00210     for (int i = vsize; i--; ) {
00211       sequence[vertices[i]].parent = x;
00212     }
00213     // return the set, x belongs to
00214     return sequence[x].name;
00215   }
00216 
00217   forceinline void
00218   OfflineMin::unite(int a, int b, int c){
00219     // c is the union of a and b
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;     // initially each set is empty
00239       cur.name   = i;     // it has its own name
00240       cur.root   = i;     // it is the root node
00241       cur.parent = i;     // it is its own parent
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         // validate the permutation
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         // if the sum over all assigned permutation variables is not
00507         // equal to the gaussian sum - n they are not distinct, hence invalid
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         // if the permutation variable is determined
00531         int v = xz[i][1].val();
00532         if (xz[i][0].assigned()) {
00533           // channel equality from x to y
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             // channel equality from y to x
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             // constrain upper bound
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             // constrain lower bound
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             // constrain the sorted variable
00559             // constrain upper bound
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             // constrain lower bound
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         // if the permutation variable is undetermined
00574         int l = xz[i][1].min();
00575         int r = xz[i][1].max();
00576         // upper bound
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         // lower bound
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 // STATISTICS: int-prop