Generated on Thu Jul 6 07:06:43 2006 for Gecode by doxygen 1.4.7

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: 2006-05-29 09:42:21 +0200 (Mon, 29 May 2006) $ by $Author: schulte $
00010  *     $Revision: 3246 $
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 "gecode/support/sort.hh"
00023 
00024 namespace Gecode { namespace Int { namespace Distinct {
00025 
00026   template <class View>
00027   inline
00028   Bnd<View>::Bnd(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>
00039   size_t
00040   Bnd<View>::dispose(Space* home) {
00041     assert(!home->failed());
00042     y.cancel(home,this,PC_INT_BND);
00043     (void) Propagator::dispose(home);
00044     return sizeof(*this);
00045   }
00046 
00047   template <class View>
00048   forceinline
00049   Bnd<View>::Bnd(Space* home, bool share, Bnd<View>& p)
00050     : Propagator(home,share,p) {
00051       x.update(home,share,p.x);
00052       y.update(home,share,p.y);
00053   }
00054 
00055   template <class View>
00056   Actor*
00057   Bnd<View>::copy(Space* home, bool share) {
00058     return new (home) Bnd<View>(home,share,*this);
00059   }
00060 
00061   template <class View>
00062   PropCost
00063   Bnd<View>::cost(void) const {
00064     return (View::pme(this) == ME_INT_VAL)
00065       ? cost_lo(y.size(),PC_LINEAR_LO)
00066       : cost_hi(x.size(),PC_LINEAR_HI);
00067   }
00068 
00069 
00071   class Rank {
00072   public:
00073     int min, max;
00074   };
00075 
00077   template <class View>
00078   class MaxInc {
00079   protected:
00080     ViewArray<View> x;
00081   public:
00082     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00083     forceinline bool
00084     operator()(const int i, const int j) {
00085       return x[i].max() < x[j].max();
00086     }
00087   };
00088 
00090   template <class View>
00091   class MinInc {
00092   public:
00093     forceinline bool
00094     operator()(const View& x, const View& y) {
00095       return x.min() < y.min();
00096     }
00097   };
00098 
00100   class HallInfo {
00101   public:
00102     int bounds, t, d, h;
00103   };
00104 
00105   inline void
00106   pathset_t(HallInfo hall[], int start, int end, int to) {
00107     int k, l;
00108     for (l=start; (k=l) != end; hall[k].t=to) {
00109       l = hall[k].t;
00110     }
00111   }
00112 
00113   inline void
00114   pathset_h(HallInfo hall[], int start, int end, int to) {
00115     int k, l;
00116     for (l=start; (k=l) != end; hall[k].h=to) {
00117       l = hall[k].h;
00118     }
00119   }
00120 
00121   forceinline int
00122   pathmin_h(const HallInfo hall[], int i) {
00123     while (hall[i].h < i)
00124       i = hall[i].h;
00125     return i;
00126   }
00127 
00128   forceinline int
00129   pathmin_t(const HallInfo hall[], int i) {
00130     while (hall[i].t < i)
00131       i = hall[i].t;
00132     return i;
00133   }
00134 
00135   forceinline int
00136   pathmax_h(const HallInfo hall[], int i) {
00137     while (hall[i].h > i)
00138       i = hall[i].h;
00139     return i;
00140   }
00141 
00142   forceinline int
00143   pathmax_t(const HallInfo hall[], int i) {
00144     while (hall[i].t > i)
00145       i = hall[i].t;
00146     return i;
00147   }
00148 
00149 #define minsorted(i) (i)
00150 #define maxsorted(i) (_maxsorted[i])
00151 
00152   template <class View>
00153   ExecStatus
00154   prop_bnd(Space* home, ViewArray<View>& x) {
00155     // Sort variable array for minimum directly
00156     MinInc<View> min_inc;
00157     Support::insertion<View,MinInc<View> >(&x[0], x.size(), min_inc);
00158 
00159     const int n = x.size();
00160 
00161     GECODE_AUTOARRAY(int, _maxsorted, n);
00162     for (int i = n; i--; )
00163       _maxsorted[i]=i;
00164 
00165     MaxInc<View> max_inc(x);
00166     Support::insertion<int,MaxInc<View> >(_maxsorted, n, max_inc);
00167 
00168     // Setup rank and bounds info
00169     GECODE_AUTOARRAY(HallInfo, hall, 2*n+2);
00170     GECODE_AUTOARRAY(Rank,     rank, n);
00171 
00172     int nb = 0;
00173     {
00174       int min  = x[minsorted(0)].min();
00175       int max  = x[maxsorted(0)].max() + 1;
00176       int last = min - 2;
00177 
00178       hall[0].bounds = last;
00179 
00180       int i = 0;
00181       int j = 0;
00182       while (true) {
00183         if (i < n && min < max) {
00184           if (min != last)
00185             hall[++nb].bounds = last = min;
00186           rank[minsorted(i)].min = nb;
00187           if (++i < n)
00188             min = x[minsorted(i)].min();
00189         } else {
00190           if (max != last)
00191             hall[++nb].bounds = last = max;
00192           rank[maxsorted(j)].max = nb;
00193           if (++j == n)
00194             break;
00195           max = x[maxsorted(j)].max() + 1;
00196         }
00197       }
00198       hall[nb+1].bounds = hall[nb].bounds + 2;
00199     }
00200 
00201     // If tells cross holes, we do not compute a fixpoint
00202     ExecStatus es = ES_FIX;
00203 
00204     // Propagate lower bounds
00205     for (int i=nb+2; --i;) {
00206       hall[i].t = hall[i].h = i-1;
00207       hall[i].d = hall[i].bounds - hall[i-1].bounds;
00208     }
00209     for (int i=0; i<n; i++) { // visit intervals in increasing max order
00210       int x0 = rank[maxsorted(i)].min;
00211       int z = pathmax_t(hall, x0+1);
00212       int j = hall[z].t;
00213       if (--hall[z].d == 0)
00214         hall[z = pathmax_t(hall, hall[z].t=z+1)].t = j;
00215       pathset_t(hall, x0+1, z, z); // path compression
00216       int y = rank[maxsorted(i)].max;
00217       if (hall[z].d < hall[z].bounds-hall[y].bounds)
00218         return ES_FAILED;
00219       if (hall[x0].h > x0) {
00220         int w = pathmax_h(hall, hall[x0].h);
00221         int m = hall[w].bounds;
00222         ModEvent me = x[maxsorted(i)].gq(home,m);
00223         if (me_failed(me))
00224           return ES_FAILED;
00225         if (me_modified(me) && (m != x[maxsorted(i)].min()))
00226           es = ES_NOFIX;
00227         pathset_h(hall, x0, w, w); // path compression
00228       }
00229       if (hall[z].d == hall[z].bounds-hall[y].bounds) {
00230         pathset_h(hall, hall[y].h, j-1, y); // mark hall interval
00231         hall[y].h = j-1;
00232       }
00233     }
00234 
00235     // Propagate upper bounds
00236     for (int i=nb+1; i--;) {
00237       hall[i].t = hall[i].h = i+1;
00238       hall[i].d = hall[i+1].bounds - hall[i].bounds;
00239     }
00240     for (int i=n; --i>=0; ) { // visit intervals in decreasing min order
00241       int x0 = rank[minsorted(i)].max;
00242       int z = pathmin_t(hall, x0-1);
00243       int j = hall[z].t;
00244       if (--hall[z].d == 0)
00245         hall[z = pathmin_t(hall, hall[z].t=z-1)].t = j;
00246       pathset_t(hall, x0-1, z, z);
00247       int y = rank[minsorted(i)].min;
00248       if (hall[z].d < hall[y].bounds-hall[z].bounds)
00249         return ES_FAILED;
00250       if (hall[x0].h < x0) {
00251         int w = pathmin_h(hall, hall[x0].h);
00252         int m = hall[w].bounds - 1;
00253         ModEvent me = x[minsorted(i)].lq(home,m);
00254         if (me_failed(me))
00255           return ES_FAILED;
00256         if (me_modified(me) && (m != x[minsorted(i)].max()))
00257           es = ES_NOFIX;
00258         pathset_h(hall, x0, w, w);
00259       }
00260       if (hall[z].d == hall[y].bounds-hall[z].bounds) {
00261         pathset_h(hall, hall[y].h, j+1, y);
00262         hall[y].h = j+1;
00263       }
00264     }
00265 
00266     return es;
00267   }
00268 
00269 #undef minsorted
00270 #undef maxsorted
00271 
00272   template <class View>
00273   ExecStatus
00274   Bnd<View>::propagate(Space* home) {
00275     assert(x.size() > 1);
00276 
00277     if (View::pme(this) == ME_INT_VAL) {
00278       ExecStatus es = prop_val<View,false>(home,y);
00279       if ((es == ES_FAILED) || (es == ES_SUBSUMED))
00280         return es;
00281       if (es == ES_FIX)
00282         return ES_FIX_PARTIAL(View::pme(ME_INT_BND));
00283     }
00284 
00285     if (y.size() == 2) {
00286       GECODE_ES_CHECK(Rel::Nq<View>::post(home,y[0],y[1]));
00287       return ES_SUBSUMED;
00288     }
00289 
00290     return prop_bnd<View>(home,x);
00291   }
00292 
00293   template <class View>
00294   ExecStatus
00295   Bnd<View>::post(Space* home, ViewArray<View>& x){
00296     if (x.size() == 2)
00297       return Rel::Nq<View>::post(home,x[0],x[1]);
00298     if (x.size() > 2)
00299       (void) new (home) Bnd<View>(home,x);
00300     return ES_OK;
00301   }
00302 
00303 
00304 }}}
00305 
00306 // STATISTICS: int-prop
00307