Generated on Wed Jul 27 2011 15:08:42 for Gecode by doxygen 1.7.4
bnd.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
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 Distinct {
00039 
00040   template<class View>
00041   forceinline
00042   Bnd<View>::Bnd(Home home, ViewArray<View>& x0)
00043     : Propagator(home), x(x0), y(home,x0) {
00044     // Both x and y initially contain the same variables
00045     //  - x is used for bounds propagation
00046     //  - y is used for performing singleton propagation
00047     // They can not be shared as singleton propagation removes
00048     // determined variables still required for bounds propagation.
00049     y.subscribe(home,*this,PC_INT_BND);
00050   }
00051 
00052   template<class View>
00053   forceinline size_t
00054   Bnd<View>::dispose(Space& home) {
00055     y.cancel(home,*this,PC_INT_BND);
00056     (void) Propagator::dispose(home);
00057     return sizeof(*this);
00058   }
00059 
00060   template<class View>
00061   forceinline
00062   Bnd<View>::Bnd(Space& home, bool share, Bnd<View>& p)
00063     : Propagator(home,share,p) {
00064       x.update(home,share,p.x);
00065       y.update(home,share,p.y);
00066   }
00067 
00068   template<class View>
00069   Actor*
00070   Bnd<View>::copy(Space& home, bool share) {
00071     return new (home) Bnd<View>(home,share,*this);
00072   }
00073 
00074   template<class View>
00075   PropCost
00076   Bnd<View>::cost(const Space&, const ModEventDelta& med) const {
00077     if (View::me(med) == ME_INT_VAL)
00078       return PropCost::linear(PropCost::LO, y.size());
00079     else
00080       return PropCost::quadratic(PropCost::LO, x.size());
00081   }
00082 
00083 
00085   class Rank {
00086   public:
00087     int min, max;
00088   };
00089 
00091   template<class View>
00092   class MaxInc {
00093   protected:
00094     ViewArray<View> x;
00095   public:
00096     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00097     forceinline bool
00098     operator ()(const int i, const int j) {
00099       return x[i].max() < x[j].max();
00100     }
00101   };
00102 
00104   template<class View>
00105   class MinInc {
00106   public:
00107     forceinline bool
00108     operator ()(const View& x, const View& y) {
00109       return x.min() < y.min();
00110     }
00111   };
00112 
00114   class HallInfo {
00115   public:
00116     int bounds, t, d, h;
00117   };
00118 
00119   forceinline void
00120   pathset_t(HallInfo hall[], int start, int end, int to) {
00121     int k, l;
00122     for (l=start; (k=l) != end; hall[k].t=to) {
00123       l = hall[k].t;
00124     }
00125   }
00126 
00127   forceinline void
00128   pathset_h(HallInfo hall[], int start, int end, int to) {
00129     int k, l;
00130     for (l=start; (k=l) != end; hall[k].h=to) {
00131       l = hall[k].h;
00132     }
00133   }
00134 
00135   forceinline int
00136   pathmin_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   pathmin_t(const HallInfo hall[], int i) {
00144     while (hall[i].t < i)
00145       i = hall[i].t;
00146     return i;
00147   }
00148 
00149   forceinline int
00150   pathmax_h(const HallInfo hall[], int i) {
00151     while (hall[i].h > i)
00152       i = hall[i].h;
00153     return i;
00154   }
00155 
00156   forceinline int
00157   pathmax_t(const HallInfo hall[], int i) {
00158     while (hall[i].t > i)
00159       i = hall[i].t;
00160     return i;
00161   }
00162 
00163 #define GECODE_INT_MINSORTED(i) (i)
00164 #define GECODE_INT_MAXSORTED(i) (_maxsorted[i])
00165 
00166   template<class View>
00167   ExecStatus
00168   prop_bnd(Space& home, ViewArray<View>& x) {
00169     const int n = x.size();
00170     // Sort variable array for minimum directly
00171     {
00172       MinInc<View> min_inc;
00173       Support::insertion<View,MinInc<View> >(&x[0], n, min_inc);
00174     }
00175 
00176     Region r(home);
00177 
00178     int* _maxsorted = r.alloc<int>(n);
00179 
00180     for (int i = n; i--; )
00181       _maxsorted[i]=i;
00182 
00183     {
00184       MaxInc<View> max_inc(x);
00185       Support::insertion<int,MaxInc<View> >(_maxsorted, n, max_inc);
00186     }
00187 
00188     // Setup rank and bounds info
00189     HallInfo* hall = r.alloc<HallInfo>(2*n+2);
00190     Rank* rank = r.alloc<Rank>(n);
00191 
00192     int nb = 0;
00193     {
00194       int min  = x[GECODE_INT_MINSORTED(0)].min();
00195       int max  = x[GECODE_INT_MAXSORTED(0)].max() + 1;
00196       int last = min - 2;
00197 
00198       hall[0].bounds = last;
00199 
00200       int i = 0;
00201       int j = 0;
00202       while (true) {
00203         if ((i < n) && (min < max)) {
00204           if (min != last)
00205             hall[++nb].bounds = last = min;
00206           rank[GECODE_INT_MINSORTED(i)].min = nb;
00207           if (++i < n)
00208             min = x[GECODE_INT_MINSORTED(i)].min();
00209         } else {
00210           if (max != last)
00211             hall[++nb].bounds = last = max;
00212           rank[GECODE_INT_MAXSORTED(j)].max = nb;
00213           if (++j == n)
00214             break;
00215           max = x[GECODE_INT_MAXSORTED(j)].max() + 1;
00216         }
00217       }
00218       hall[nb+1].bounds = hall[nb].bounds + 2;
00219     }
00220 
00221     // If tells cross holes, we do not compute a fixpoint
00222     ExecStatus es = ES_FIX;
00223 
00224     // Propagate lower bounds
00225     for (int i=nb+2; --i;) {
00226       hall[i].t = hall[i].h = i-1;
00227       hall[i].d = hall[i].bounds - hall[i-1].bounds;
00228     }
00229     for (int i=0; i<n; i++) { // visit intervals in increasing max order
00230       int x0 = rank[GECODE_INT_MAXSORTED(i)].min;
00231       int z = pathmax_t(hall, x0+1);
00232       int j = hall[z].t;
00233       if (--hall[z].d == 0)
00234         hall[z = pathmax_t(hall, hall[z].t=z+1)].t = j;
00235       pathset_t(hall, x0+1, z, z); // path compression
00236       int y = rank[GECODE_INT_MAXSORTED(i)].max;
00237       if (hall[z].d < hall[z].bounds-hall[y].bounds)
00238         return ES_FAILED;
00239       if (hall[x0].h > x0) {
00240         int w = pathmax_h(hall, hall[x0].h);
00241         int m = hall[w].bounds;
00242         ModEvent me = x[GECODE_INT_MAXSORTED(i)].gq(home,m);
00243         if (me_failed(me))
00244           return ES_FAILED;
00245         if ((me == ME_INT_VAL) ||
00246             ((me == ME_INT_BND) && (m != x[GECODE_INT_MAXSORTED(i)].min())))
00247           es = ES_NOFIX;
00248         pathset_h(hall, x0, w, w); // path compression
00249       }
00250       if (hall[z].d == hall[z].bounds-hall[y].bounds) {
00251         pathset_h(hall, hall[y].h, j-1, y); // mark hall interval
00252         hall[y].h = j-1;
00253       }
00254     }
00255 
00256     // Propagate upper bounds
00257     for (int i=nb+1; i--;) {
00258       hall[i].t = hall[i].h = i+1;
00259       hall[i].d = hall[i+1].bounds - hall[i].bounds;
00260     }
00261     for (int i=n; --i>=0; ) { // visit intervals in decreasing min order
00262       int x0 = rank[GECODE_INT_MINSORTED(i)].max;
00263       int z = pathmin_t(hall, x0-1);
00264       int j = hall[z].t;
00265       if (--hall[z].d == 0)
00266         hall[z = pathmin_t(hall, hall[z].t=z-1)].t = j;
00267       pathset_t(hall, x0-1, z, z);
00268       int y = rank[GECODE_INT_MINSORTED(i)].min;
00269       if (hall[z].d < hall[y].bounds-hall[z].bounds)
00270         return ES_FAILED;
00271       if (hall[x0].h < x0) {
00272         int w = pathmin_h(hall, hall[x0].h);
00273         int m = hall[w].bounds - 1;
00274         ModEvent me = x[GECODE_INT_MINSORTED(i)].lq(home,m);
00275         if (me_failed(me))
00276           return ES_FAILED;
00277         if ((me == ME_INT_VAL) ||
00278             ((me == ME_INT_BND) && (m != x[GECODE_INT_MAXSORTED(i)].min())))
00279           es = ES_NOFIX;
00280         pathset_h(hall, x0, w, w);
00281       }
00282       if (hall[z].d == hall[y].bounds-hall[z].bounds) {
00283         pathset_h(hall, hall[y].h, j+1, y);
00284         hall[y].h = j+1;
00285       }
00286     }
00287 
00288     return es;
00289   }
00290 
00291 #undef GECODE_INT_MINSORTED
00292 #undef GECODE_INT_MAXSORTED
00293 
00294   template<class View>
00295   ExecStatus
00296   Bnd<View>::propagate(Space& home, const ModEventDelta& med) {
00297     assert(x.size() > 1);
00298 
00299     if (View::me(med) == ME_INT_VAL) {
00300       ExecStatus es = prop_val<View,false>(home,y);
00301       GECODE_ES_CHECK(es);
00302       if (y.size() < 2)
00303         return home.ES_SUBSUMED(*this);
00304       if (es == ES_FIX)
00305         return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_BND));
00306     }
00307 
00308     if (y.size() == 2)
00309       GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),y[0],y[1]));
00310 
00311     ExecStatus es = prop_bnd<View>(home,x);
00312 
00313     GECODE_ES_CHECK(es);
00314 
00315     const int n = x.size();
00316 
00317     if ((n > 2*y.size()) && (n > 6)) {
00318       // If there are many assigned views, try to eliminate them
00319       MinInc<View> min_inc;
00320       Support::insertion<View,MinInc<View> >(&x[0], n, min_inc);
00321       int i   = 0;
00322       int j   = 0;
00323       int max = x[0].max()-1;
00324       while (i < n-1) {
00325         if (!x[i].assigned() ||
00326             (x[i].val() <= max) || (x[i].val() > x[i+1].min())) {
00327           // Keep view x[i]
00328           max = std::max(max,x[i].max());
00329           x[j++]=x[i];
00330         }
00331         i++;
00332       }
00333       if (!x[i].assigned() || (x[i].val() <= max))
00334         x[j++]=x[i];
00335       x.size(j);
00336     }
00337 
00338     if (x.size() < 2)
00339       return home.ES_SUBSUMED(*this);
00340 
00341     if (x.size() == 2)
00342       GECODE_REWRITE(*this,Rel::Nq<View>::post(home(*this),x[0],x[1]));
00343 
00344     return es;
00345   }
00346 
00347   template<class View>
00348   ExecStatus
00349   Bnd<View>::post(Home home, ViewArray<View>& x){
00350     if (x.size() == 2)
00351       return Rel::Nq<View>::post(home,x[0],x[1]);
00352     if (x.size() > 2)
00353       (void) new (home) Bnd<View>(home,x);
00354     return ES_OK;
00355   }
00356 
00357 }}}
00358 
00359 // STATISTICS: int-prop
00360