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

bnd.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-10-23 16:23:09 +0200 (Sun, 23 Oct 2005) $ by $Author: schulte $
00010  *     $Revision: 2403 $
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 Distinct {
00025 
00026   template <class View, bool shared>
00027   inline
00028   BndImp<View,shared>::BndImp(Space* home, ViewArray<View>& x0)
00029     : Propagator(home), x(x0), y(home,x0) {
00030     // Both x and y initially contain the same variables
00031     //  - x is used for bounds propagation
00032     //  - y is used for performing singleton propagation
00033     // They can not be shared as singleton propagation removes
00034     // determined variables still required for bounds propagation.
00035     y.subscribe(home,this,PC_INT_BND);
00036   }
00037 
00038   template <class View, bool shared>
00039   BndImp<View,shared>::~BndImp(void) {
00040     y.cancel(this,PC_INT_BND);
00041   }
00042 
00043   template <class View, bool shared>
00044   forceinline
00045   BndImp<View,shared>::BndImp(Space* home, bool share, BndImp<View,shared>& p)
00046     : Propagator(home,share,p) {
00047       x.update(home,share,p.x);
00048       y.update(home,share,p.y);
00049   }
00050 
00051   template <class View, bool shared>
00052   Actor*
00053   BndImp<View,shared>::copy(Space* home, bool share) {
00054     return new (home) BndImp<View,shared>(home,share,*this);
00055   }
00056 
00057   template <class View, bool shared>
00058   PropCost
00059   BndImp<View,shared>::cost(void) const {
00060     return (View::pme(this) == ME_INT_VAL)
00061       ? cost_lo(y.size(),PC_LINEAR_LO)
00062       : cost_hi(x.size(),PC_LINEAR_HI);
00063   }
00064 
00065 
00067   class Rank {
00068   public:
00069     int min, max;
00070   };
00071 
00073   template <class View>
00074   class MaxInc {
00075   protected:
00076     ViewArray<View> x;
00077   public:
00078     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00079     forceinline bool
00080     operator()(const int i, const int j) {
00081       return x[i].max() < x[j].max();
00082     }
00083   };
00084 
00086   template <class View>
00087   class MinInc {
00088   public:
00089     forceinline bool
00090     operator()(const View& x, const View& y) {
00091       return x.min() < y.min();
00092     }
00093   };
00094 
00096   class HallInfo {
00097   public:
00098     int bounds, t, d, h;
00099   };
00100 
00101   inline void
00102   pathset_t(HallInfo hall[], int start, int end, int to) {
00103     int k, l;
00104     for (l=start; (k=l) != end; hall[k].t=to) {
00105       l = hall[k].t;
00106     }
00107   }
00108 
00109   inline void
00110   pathset_h(HallInfo hall[], int start, int end, int to) {
00111     int k, l;
00112     for (l=start; (k=l) != end; hall[k].h=to) {
00113       l = hall[k].h;
00114     }
00115   }
00116 
00117   forceinline int
00118   pathmin_h(const HallInfo hall[], int i) {
00119     while (hall[i].h < i)
00120       i = hall[i].h;
00121     return i;
00122   }
00123 
00124   forceinline int
00125   pathmin_t(const HallInfo hall[], int i) {
00126     while (hall[i].t < i)
00127       i = hall[i].t;
00128     return i;
00129   }
00130 
00131   forceinline int
00132   pathmax_h(const HallInfo hall[], int i) {
00133     while (hall[i].h > i)
00134       i = hall[i].h;
00135     return i;
00136   }
00137 
00138   forceinline int
00139   pathmax_t(const HallInfo hall[], int i) {
00140     while (hall[i].t > i)
00141       i = hall[i].t;
00142     return i;
00143   }
00144 
00145 #define minsorted(i) (i)
00146 #define maxsorted(i) (_maxsorted[i])
00147 
00148   template <class View, bool shared>
00149   ExecStatus
00150   prop_bnd(Space* home, ViewArray<View>& x) {
00151     // Sort variable array for minimum directly
00152     MinInc<View> min_inc;
00153     Support::insertion<View,MinInc<View> >(&x[0], x.size(), min_inc);
00154 
00155     const int n = x.size();
00156 
00157     GECODE_AUTOARRAY(int, _maxsorted, n);
00158     for (int i = n; i--; )
00159       _maxsorted[i]=i;
00160 
00161     MaxInc<View> max_inc(x);
00162     Support::insertion<int,MaxInc<View> >(_maxsorted, n, max_inc);
00163 
00164     // Setup rank and bounds info
00165     GECODE_AUTOARRAY(HallInfo, hall, 2*n+2);
00166     GECODE_AUTOARRAY(Rank,     rank, n);
00167 
00168     int nb = 0;
00169     {
00170       int min  = x[minsorted(0)].min();
00171       int max  = x[maxsorted(0)].max() + 1;
00172       int last = min - 2;
00173 
00174       hall[0].bounds = last;
00175 
00176       int i = 0;
00177       int j = 0;
00178       while (true) {
00179         if (i < n && min < max) {
00180           if (min != last)
00181             hall[++nb].bounds = last = min;
00182           rank[minsorted(i)].min = nb;
00183           if (++i < n)
00184             min = x[minsorted(i)].min();
00185         } else {
00186           if (max != last)
00187             hall[++nb].bounds = last = max;
00188           rank[maxsorted(j)].max = nb;
00189           if (++j == n)
00190             break;
00191           max = x[maxsorted(j)].max() + 1;
00192         }
00193       }
00194       hall[nb+1].bounds = hall[nb].bounds + 2;
00195     }
00196 
00197     // If tells cross holes, we do not compute a fixpoint
00198     ExecStatus es = ES_FIX;
00199 
00200     // Propagate lower bounds
00201     for (int i=nb+2; --i;) {
00202       hall[i].t = hall[i].h = i-1;
00203       hall[i].d = hall[i].bounds - hall[i-1].bounds;
00204     }
00205     for (int i=0; i<n; i++) { // visit intervals in increasing max order
00206       int x0 = rank[maxsorted(i)].min;
00207       int z = pathmax_t(hall, x0+1);
00208       int j = hall[z].t;
00209       if (--hall[z].d == 0)
00210         hall[z = pathmax_t(hall, hall[z].t=z+1)].t = j;
00211       pathset_t(hall, x0+1, z, z); // path compression
00212       int y = rank[maxsorted(i)].max;
00213       if (hall[z].d < hall[z].bounds-hall[y].bounds)
00214         return ES_FAILED;
00215       if (hall[x0].h > x0) {
00216         int w = pathmax_h(hall, hall[x0].h);
00217         int m = hall[w].bounds;
00218         // Check whether there are tells to shared variables
00219         if (shared && x[maxsorted(i)].modified())
00220           es = ES_NOFIX;
00221         ModEvent me = x[maxsorted(i)].gq(home,m);
00222         if (me_failed(me))
00223           return ES_FAILED;
00224         if (me_modified(me) && (m != x[maxsorted(i)].min()))
00225           es = ES_NOFIX;
00226         pathset_h(hall, x0, w, w); // path compression
00227       }
00228       if (hall[z].d == hall[z].bounds-hall[y].bounds) {
00229         pathset_h(hall, hall[y].h, j-1, y); // mark hall interval
00230         hall[y].h = j-1;
00231       }
00232     }
00233 
00234     // Propagate upper bounds
00235     for (int i=nb+1; i--;) {
00236       hall[i].t = hall[i].h = i+1;
00237       hall[i].d = hall[i+1].bounds - hall[i].bounds;
00238     }
00239     for (int i=n; --i>=0; ) { // visit intervals in decreasing min order
00240       int x0 = rank[minsorted(i)].max;
00241       int z = pathmin_t(hall, x0-1);
00242       int j = hall[z].t;
00243       if (--hall[z].d == 0)
00244         hall[z = pathmin_t(hall, hall[z].t=z-1)].t = j;
00245       pathset_t(hall, x0-1, z, z);
00246       int y = rank[minsorted(i)].min;
00247       if (hall[z].d < hall[y].bounds-hall[z].bounds)
00248         return ES_FAILED;
00249       if (hall[x0].h < x0) {
00250         int w = pathmin_h(hall, hall[x0].h);
00251         int m = hall[w].bounds - 1;
00252         // Test again for sharing: this is quite inaccurate as there
00253         // are two opreations perfomed per variable: hence if both
00254         // lower and upper bound are changed, and shared is true,
00255         // the propagator will report to be not at fixpoint.
00256         if (shared && x[maxsorted(i)].modified())
00257           es = ES_NOFIX;
00258         ModEvent me = x[minsorted(i)].lq(home,m);
00259         if (me_failed(me))
00260           return ES_FAILED;
00261         if (me_modified(me) && (m != x[minsorted(i)].max()))
00262           es = ES_NOFIX;
00263         pathset_h(hall, x0, w, w);
00264       }
00265       if (hall[z].d == hall[y].bounds-hall[z].bounds) {
00266         pathset_h(hall, hall[y].h, j+1, y);
00267         hall[y].h = j+1;
00268       }
00269     }
00270 
00271     return es;
00272   }
00273 
00274 #undef minsorted
00275 #undef maxsorted
00276 
00277   template <class View, bool shared>
00278   ExecStatus
00279   BndImp<View,shared>::propagate(Space* home) {
00280     assert(x.size() > 1);
00281 
00282     if (View::pme(this) == ME_INT_VAL) {
00283       ExecStatus es = prop_val<View,false>(home,y);
00284       if ((es == ES_FAILED) || (es == ES_SUBSUMED))
00285         return es;
00286       if (es == ES_FIX)
00287         return ES_FIX_PARTIAL(View::pme(ME_INT_BND));
00288     }
00289 
00290     if (y.size() == 2) {
00291       GECODE_ES_CHECK(Rel::Nq<View>::post(home,y[0],y[1]));
00292       return ES_SUBSUMED;
00293     }
00294 
00295     return prop_bnd<View,shared>(home,x);
00296   }
00297 
00298   template <class View>
00299   ExecStatus
00300   Bnd<View>::post(Space* home, ViewArray<View>& x){
00301     if (x.size() == 2)
00302       return Rel::Nq<View>::post(home,x[0],x[1]);
00303     if (x.size() > 2)
00304       if (x.shared()) {
00305         if (x.same())
00306           return ES_FAILED;
00307         else
00308           (void) new (home) BndImp<View,true>(home,x);
00309       } else {
00310         (void) new (home) BndImp<View,false>(home,x);
00311       }
00312     return ES_OK;
00313   }
00314 
00315 
00316 }}}
00317 
00318 // STATISTICS: int-prop
00319