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