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

order.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-02 11:48:39 +0100 (Fri, 02 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2686 $
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 #include "support/sort.hh"
00023 
00024 namespace Gecode { namespace Int { namespace Sortedness {
00025 
00033   template <class View, class Tuple, bool Perm>
00034   forceinline void 
00035   sort_sigma(ViewArray<Tuple>& xz, bool fixed) {
00036     int xs = xz.size();
00037 
00038     if (fixed) {
00039       TupleMinIncPerm<Tuple> min_inc;
00040       Support::quicksort<Tuple, TupleMinIncPerm<Tuple> >
00041         (&xz[0], xs, min_inc);
00042     } else {
00043       TupleMinInc<Tuple> min_inc;
00044       Support::quicksort<Tuple, TupleMinInc<Tuple> >(&xz[0], xs, min_inc);
00045     }
00046   }
00047 
00056   template <class View, class Tuple, bool Perm>
00057   forceinline void 
00058   sort_tau(ViewArray<Tuple>& xz, int tau[]) {
00059     int xs = xz.size();
00060     TupleMaxInc<Tuple> ltmax(xz);
00061     Support::quicksort(&(*tau), xs, ltmax);
00062   }
00063 
00071   template <class View, class Tuple, bool shared>
00072   forceinline bool
00073   normalize(Space* home, 
00074             ViewArray<View>& y, 
00075             ViewArray<Tuple>& xz,
00076             bool& nofix) {
00077 
00078     int ys = y.size();
00079     for (int i = 1; i < ys; i++) {
00080       if (shared && y[i].modified()) {
00081         nofix = true;
00082         return true;
00083       }
00084       ModEvent me_lb = y[i].gq(home, y[i - 1].min()); 
00085       if (me_failed(me_lb)) {
00086         return false;
00087       }
00088       nofix |= (me_modified(me_lb) && y[i - 1].min() != y[i].min());
00089     }
00090     
00091     for (int i = ys - 1; i--; ) {
00092       if (shared && y[i].modified()) {
00093         nofix = true;
00094         return true;
00095       }
00096 
00097       ModEvent me_ub = y[i].lq(home, y[i + 1].max());
00098       if (me_failed(me_ub)) {
00099         return false;
00100       }
00101       nofix |= (me_modified(me_ub) && y[i + 1].max() != y[i].max());
00102     }
00103 
00104     int xs = xz.size();
00105     for (int i = xs; i--; ) {
00106       if (shared && xz[i][0].modified()) {
00107         nofix = true;
00108         return true;
00109       }
00110 
00111       ModEvent me = xz[i][0].lq(home, y[xs - 1].max()); 
00112       if (me_failed(me)) {
00113         return false;
00114       }
00115       nofix |= (me_modified(me) && xz[i][0].max() != y[xs - 1].max());
00116     }
00117     return true;
00118   }
00119 
00129   template<class View, class Tuple, bool Perm, bool shared>
00130   forceinline bool
00131   perm_bc(Space* home, int tau[], 
00132           ViewArray<Tuple>& xz, 
00133           bool& crossingedge, 
00134           bool& nofix) {
00135 
00136     int ps        = xz.size();
00137     bool edge_up  = false;
00138     for (int i = 1; i < ps; i++) {
00139       // if there are "crossed edges"
00140       if (xz[i][0].min() > xz[i - 1][0].max()) {
00141         if (xz[i][1].min() < xz[i - 1][1].min()) {
00142           edge_up = true; 
00143           break;
00144         }
00145       }
00146     }
00147 
00148     bool edge_low = false;
00149     for (int i = ps - 1; i--; ) {
00150       if (xz[tau[i]][0].max() < xz[tau[i + 1]][0].min()) {
00151         if (xz[tau[i]][1].max() > xz[tau[i + 1]][1].max()) {
00152           edge_low = true;
00153           break;
00154         }
00155       }
00156     }
00157 
00158     if (edge_up && edge_low) {
00159       for (int i = 1; i < ps; i++) {
00160         // if there are "crossed edges"
00161         if (xz[i][0].min() > xz[i - 1][0].max()) {
00162           if (xz[i][1].min() < xz[i - 1][1].min()) {
00163             // std::cout <<"ce found low ..";
00164             crossingedge = true;
00165             // and the permutation can still be changed
00166             if (!xz[i][1].assigned() && !xz[i - 1][1].assigned()) {
00167               // fix the permutation, i.e. modify z
00168               // std::cout <<"fixed perm\n";
00169               ModEvent me_z = xz[i][1].gq(home, xz[i - 1][1].min());
00170               if (me_failed(me_z)) {
00171                 return false;
00172               }
00173               nofix |= ( me_modified(me_z) &&
00174                          xz[i - 1][1].min() != xz[i][1].min());
00175             } else {
00176               // std::cout <<"fixed sigma\n";
00177               // if the permutation is already determined at this index
00178               // try to fix the sigma sorting, i.e. modify x
00179               if (shared && xz[i - 1][0].modified()) {
00180                 nofix = true;
00181                 return true;
00182               }
00183 
00184               ModEvent me_x = xz[i - 1][0].gq(home,xz[i][0].min());
00185               if (me_failed(me_x)) {
00186                 return false;
00187               }
00188               nofix |= (me_modified(me_x) &&
00189                         xz[i][0].min() != xz[i - 1][0].min());
00190             }
00191           }
00192         }
00193       }
00194 
00195       // the same check as above for the upper bounds
00196       for (int i = ps - 1; i--; ) {
00197         if (xz[tau[i]][0].max() < xz[tau[i + 1]][0].min()) {
00198           if (xz[tau[i]][1].max() > xz[tau[i + 1]][1].max()) {
00199             // std::cout <<"ce found up ..";
00200             crossingedge = true;
00201             if (!xz[tau[i]][1].assigned() && !xz[tau[i + 1]][1].assigned()) {
00202               // std::cout <<"fixed perm\n";
00203               ModEvent me_z = xz[tau[i]][1].lq(home, xz[tau[i + 1]][1].max());
00204               if (me_failed(me_z)) {
00205                 return false;
00206               }
00207               nofix |= (me_modified(me_z) &&
00208                         xz[tau[i + 1]][1].max() != xz[tau[i]][1].max());
00209             } else {
00210               // std::cout <<"fixed tau\n";
00211               if (shared && xz[tau[i + 1]][0].modified()) {
00212                 nofix = true;
00213                 return true;
00214               }
00215 
00216               ModEvent me_x = xz[tau[i + 1]][0].lq(home,xz[tau[i]][0].max());
00217               if (me_failed(me_x)) {
00218                 return false;
00219               }
00220               nofix |= (me_modified(me_x) &&
00221                         xz[tau[i]][0].max() != xz[tau[i + 1]][0].max());
00222             }
00223           }
00224         }
00225       }
00226     }
00227     return true;
00228   }    
00229 
00230 }}}
00231 
00232 // STATISTICS: int-prop
00233