int.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, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-05-28 20:54:33 +0200 (Fri, 28 May 2010) $ by $Author: schulte $ 00011 * $Revision: 10982 $ 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 Element { 00039 00040 00041 // Index value pairs 00042 template<class V0, class V1, class Idx, class Val> 00043 forceinline void 00044 Int<V0,V1,Idx,Val>::IdxVal::mark(void) { 00045 idx = -1; 00046 } 00047 template<class V0, class V1, class Idx, class Val> 00048 forceinline bool 00049 Int<V0,V1,Idx,Val>::IdxVal::marked(void) const { 00050 return idx<0; 00051 } 00052 00053 00054 // Index iterator 00055 template<class V0, class V1, class Idx, class Val> 00056 forceinline 00057 Int<V0,V1,Idx,Val>::IterIdxUnmark::IterIdxUnmark(IdxVal* iv0) 00058 : iv(iv0) { 00059 Idx p=0; 00060 i = iv[p].idx_next; 00061 while ((i != 0) && iv[i].marked()) 00062 i=iv[i].idx_next; 00063 iv[p].idx_next=i; 00064 } 00065 template<class V0, class V1, class Idx, class Val> 00066 forceinline bool 00067 Int<V0,V1,Idx,Val>::IterIdxUnmark::operator ()(void) const { 00068 return i != 0; 00069 } 00070 template<class V0, class V1, class Idx, class Val> 00071 forceinline void 00072 Int<V0,V1,Idx,Val>::IterIdxUnmark::operator ++(void) { 00073 int p=i; 00074 i = iv[p].idx_next; 00075 while ((i != 0) && iv[i].marked()) 00076 i=iv[i].idx_next; 00077 iv[p].idx_next=i; 00078 } 00079 template<class V0, class V1, class Idx, class Val> 00080 forceinline Idx 00081 Int<V0,V1,Idx,Val>::IterIdxUnmark::val(void) const { 00082 assert(!iv[i].marked()); 00083 return iv[i].idx; 00084 } 00085 00086 00087 00088 template<class V0, class V1, class Idx, class Val> 00089 forceinline 00090 Int<V0,V1,Idx,Val>::IterVal::IterVal(IdxVal* iv0) 00091 : iv(iv0), i(iv[0].val_next) {} 00092 template<class V0, class V1, class Idx, class Val> 00093 forceinline bool 00094 Int<V0,V1,Idx,Val>::IterVal::operator ()(void) const { 00095 return i != 0; 00096 } 00097 template<class V0, class V1, class Idx, class Val> 00098 forceinline void 00099 Int<V0,V1,Idx,Val>::IterVal::operator ++(void) { 00100 i=iv[i].val_next; 00101 } 00102 template<class V0, class V1, class Idx, class Val> 00103 forceinline Val 00104 Int<V0,V1,Idx,Val>::IterVal::val(void) const { 00105 assert(!iv[i].marked()); 00106 return iv[i].val; 00107 } 00108 00109 00110 00111 template<class V0, class V1, class Idx, class Val> 00112 forceinline 00113 Int<V0,V1,Idx,Val>::IterValUnmark::IterValUnmark(IdxVal* iv0) 00114 : iv(iv0) { 00115 Idx p=0; 00116 i = iv[p].val_next; 00117 while ((i != 0) && iv[i].marked()) 00118 i=iv[i].val_next; 00119 iv[p].val_next=i; 00120 } 00121 template<class V0, class V1, class Idx, class Val> 00122 forceinline bool 00123 Int<V0,V1,Idx,Val>::IterValUnmark::operator ()(void) const { 00124 return i != 0; 00125 } 00126 template<class V0, class V1, class Idx, class Val> 00127 forceinline void 00128 Int<V0,V1,Idx,Val>::IterValUnmark::operator ++(void) { 00129 int p=i; 00130 i = iv[p].val_next; 00131 while ((i != 0) && iv[i].marked()) 00132 i=iv[i].val_next; 00133 iv[p].val_next=i; 00134 } 00135 template<class V0, class V1, class Idx, class Val> 00136 forceinline Val 00137 Int<V0,V1,Idx,Val>::IterValUnmark::val(void) const { 00138 assert(!iv[i].marked()); 00139 return iv[i].val; 00140 } 00141 00142 00143 00144 // Sort function 00145 template<class V0, class V1, class Idx, class Val> 00146 forceinline 00147 Int<V0,V1,Idx,Val>::ByVal::ByVal(const IdxVal* iv0) 00148 : iv(iv0) {} 00149 template<class V0, class V1, class Idx, class Val> 00150 forceinline bool 00151 Int<V0,V1,Idx,Val>::ByVal::operator ()(Idx& i, Idx& j) { 00152 return iv[i].val < iv[j].val; 00153 } 00154 00155 00156 /* 00157 * Element propagator proper 00158 * 00159 */ 00160 template<class V0, class V1, class Idx, class Val> 00161 forceinline 00162 Int<V0,V1,Idx,Val>::Int(Home home, IntSharedArray& c0, V0 y0, V1 y1) 00163 : Propagator(home), x0(y0), s0(0), x1(y1), s1(0), c(c0), iv(NULL) { 00164 home.notice(*this,AP_DISPOSE); 00165 x0.subscribe(home,*this,PC_INT_DOM); 00166 x1.subscribe(home,*this,PC_INT_DOM); 00167 } 00168 00169 template<class V0, class V1, class Idx, class Val> 00170 forceinline size_t 00171 Int<V0,V1,Idx,Val>::dispose(Space& home) { 00172 home.ignore(*this,AP_DISPOSE); 00173 x0.cancel(home,*this,PC_INT_DOM); 00174 x1.cancel(home,*this,PC_INT_DOM); 00175 c.~IntSharedArray(); 00176 (void) Propagator::dispose(home); 00177 return sizeof(*this); 00178 } 00179 00180 template<class V0, class V1, class Idx, class Val> 00181 ExecStatus 00182 Int<V0,V1,Idx,Val>::post(Home home, IntSharedArray& c, V0 x0, V1 x1) { 00183 if (x0.assigned()) { 00184 GECODE_ME_CHECK(x1.eq(home,c[x0.val()])); 00185 } else if (x1.assigned()) { 00186 GECODE_ES_CHECK(assigned_val(home,c,x0,x1)); 00187 } else { 00188 (void) new (home) Int<V0,V1,Idx,Val>(home,c,x0,x1); 00189 } 00190 return ES_OK; 00191 } 00192 00193 template<class V0, class V1, class Idx, class Val> 00194 forceinline 00195 Int<V0,V1,Idx,Val>::Int(Space& home, bool share, Int& p) 00196 : Propagator(home,share,p), s0(0), s1(0), iv(NULL) { 00197 c.update(home,share,p.c); 00198 x0.update(home,share,p.x0); 00199 x1.update(home,share,p.x1); 00200 } 00201 00202 template<class V0, class V1, class Idx, class Val> 00203 Actor* 00204 Int<V0,V1,Idx,Val>::copy(Space& home, bool share) { 00205 return new (home) Int<V0,V1,Idx,Val>(home,share,*this); 00206 } 00207 00208 template<class V0, class V1, class Idx, class Val> 00209 PropCost 00210 Int<V0,V1,Idx,Val>::cost(const Space&, const ModEventDelta& med) const { 00211 if ((V0::me(med) == ME_INT_VAL) || 00212 (V1::me(med) == ME_INT_VAL)) 00213 return PropCost::unary(PropCost::LO); 00214 else 00215 return PropCost::binary(PropCost::HI); 00216 } 00217 00218 template<class V0, class V1, class Idx, class Val> 00219 void 00220 Int<V0,V1,Idx,Val>::prune_idx(void) { 00221 Idx p = 0; 00222 Idx i = iv[p].idx_next; 00223 ViewRanges<V0> v(x0); 00224 while (v() && (i != 0)) { 00225 assert(!iv[i].marked()); 00226 if (iv[i].idx < v.min()) { 00227 iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i; 00228 } else if (iv[i].idx > v.max()) { 00229 ++v; 00230 } else { 00231 p=i; i=iv[i].idx_next; 00232 } 00233 } 00234 iv[p].idx_next = 0; 00235 while (i != 0) { 00236 iv[i].mark(); i=iv[i].idx_next; 00237 } 00238 } 00239 00240 template<class V0, class V1, class Idx, class Val> 00241 void 00242 Int<V0,V1,Idx,Val>::prune_val(void) { 00243 Idx p = 0; 00244 Idx i = iv[p].val_next; 00245 ViewRanges<V1> v(x1); 00246 while (v() && (i != 0)) { 00247 if (iv[i].marked()) { 00248 i=iv[i].val_next; iv[p].val_next=i; 00249 } else if (iv[i].val < v.min()) { 00250 iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i; 00251 } else if (iv[i].val > v.max()) { 00252 ++v; 00253 } else { 00254 p=i; i=iv[i].val_next; 00255 } 00256 } 00257 iv[p].val_next = 0; 00258 while (i != 0) { 00259 iv[i].mark(); i=iv[i].val_next; 00260 } 00261 } 00262 00263 template<class V0, class V1, class Idx, class Val> 00264 ExecStatus 00265 Int<V0,V1,Idx,Val>::assigned_val(Space& home, IntSharedArray& c, 00266 V0 x0, V1 x1) { 00267 Region r(home); 00268 int* v = r.alloc<int>(x0.size()); 00269 int n = 0; 00270 for (ViewValues<V0> i(x0); i(); ++i) 00271 if (c[i.val()] != x1.val()) 00272 v[n++]=i.val(); 00273 Iter::Values::Array i(v,n); 00274 GECODE_ME_CHECK(x0.minus_v(home,i,false)); 00275 return ES_OK; 00276 } 00277 00278 template<class V0, class V1, class Idx, class Val> 00279 ExecStatus 00280 Int<V0,V1,Idx,Val>::propagate(Space& home, const ModEventDelta&) { 00281 if (x0.assigned()) { 00282 GECODE_ME_CHECK(x1.eq(home,c[x0.val()])); 00283 return home.ES_SUBSUMED(*this); 00284 } 00285 00286 if (x1.assigned() && (iv == NULL)) { 00287 GECODE_ES_CHECK(assigned_val(home,c,x0,x1)); 00288 return home.ES_SUBSUMED(*this); 00289 } 00290 00291 if ((static_cast<ValSize>(x1.size()) == s1) && 00292 (static_cast<IdxSize>(x0.size()) != s0)) { 00293 assert(iv != NULL); 00294 assert(!shared(x0,x1)); 00295 00296 prune_idx(); 00297 00298 IterValUnmark v(iv); 00299 GECODE_ME_CHECK(x1.narrow_v(home,v,false)); 00300 00301 s1=static_cast<ValSize>(x1.size()); 00302 00303 assert(!x0.assigned()); 00304 return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX; 00305 } 00306 00307 if ((static_cast<IdxSize>(x0.size()) == s0) && 00308 (static_cast<ValSize>(x1.size()) != s1)) { 00309 assert(iv != NULL); 00310 assert(!shared(x0,x1)); 00311 00312 prune_val(); 00313 00314 IterIdxUnmark i(iv); 00315 GECODE_ME_CHECK(x0.narrow_v(home,i,false)); 00316 00317 s0=static_cast<IdxSize>(x0.size()); 00318 00319 return (x0.assigned() || x1.assigned()) ? 00320 home.ES_SUBSUMED(*this) : ES_FIX; 00321 } 00322 00323 bool assigned = x0.assigned() && x1.assigned(); 00324 if (iv == NULL) { 00325 // Initialize data structure 00326 iv = home.alloc<IdxVal>(x0.size() + 1); 00327 00328 // The first element in iv[0] is used as sentinel 00329 // Enter information sorted by idx 00330 IdxVal* by_idx = &iv[1]; 00331 Idx size = 0; 00332 for (ViewValues<V0> v(x0); v(); ++v) 00333 if ((x1.min() <= c[v.val()]) && (x1.max() >= c[v.val()])) { 00334 by_idx[size].idx = static_cast<Idx>(v.val()); 00335 by_idx[size].val = static_cast<Val>(c[v.val()]); 00336 size++; 00337 } 00338 if (size == 0) 00339 return ES_FAILED; 00340 // Create val links sorted by val 00341 Region r(home); 00342 Idx* by_val = r.alloc<Idx>(size); 00343 if (x1.width() <= 128) { 00344 int n_buckets = static_cast<int>(x1.width()); 00345 int* pos = r.alloc<int>(n_buckets); 00346 int* buckets = pos - x1.min(); 00347 for (int i=n_buckets; i--; ) 00348 pos[i]=0; 00349 for (Idx i=size; i--; ) 00350 buckets[by_idx[i].val]++; 00351 int p=0; 00352 for (int i=0; i<n_buckets; i++) { 00353 int n=pos[i]; pos[i]=p; p+=n; 00354 } 00355 assert(p == size); 00356 for (Idx i=size; i--; ) 00357 by_val[buckets[by_idx[i].val]++] = i+1; 00358 } else { 00359 for (Idx i = size; i--; ) 00360 by_val[i] = i+1; 00361 ByVal less(iv); 00362 Support::quicksort<Idx>(by_val,size,less); 00363 } 00364 // Create val links 00365 for (Idx i = size-1; i--; ) { 00366 by_idx[i].idx_next = i+2; 00367 iv[by_val[i]].val_next = by_val[i+1]; 00368 } 00369 by_idx[size-1].idx_next = 0; 00370 iv[by_val[size-1]].val_next = 0; 00371 // Set up sentinel element: iv[0] 00372 iv[0].idx_next = 1; 00373 iv[0].val_next = by_val[0]; 00374 } else { 00375 prune_idx(); 00376 } 00377 00378 // Prune values 00379 prune_val(); 00380 00381 // Peform tell 00382 { 00383 IterIdxUnmark i(iv); 00384 GECODE_ME_CHECK(x0.narrow_v(home,i,false)); 00385 IterVal v(iv); 00386 if (shared(x0,x1)) { 00387 GECODE_ME_CHECK(x1.inter_v(home,v,false)); 00388 s0=static_cast<IdxSize>(x0.size()); 00389 s1=static_cast<ValSize>(x1.size()); 00390 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX; 00391 } else { 00392 GECODE_ME_CHECK(x1.narrow_v(home,v,false)); 00393 s0=static_cast<IdxSize>(x0.size()); 00394 s1=static_cast<ValSize>(x1.size()); 00395 return (x0.assigned() || x1.assigned()) ? 00396 home.ES_SUBSUMED(*this) : ES_FIX; 00397 } 00398 } 00399 } 00400 00401 template<class V0, class V1> 00402 forceinline ExecStatus 00403 post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) { 00404 assert(c.size() > 0); 00405 GECODE_ME_CHECK(x0.gq(home,0)); 00406 GECODE_ME_CHECK(x0.le(home,c.size())); 00407 Support::IntType idx_type = Support::s_type(c.size()); 00408 int min = c[0]; 00409 int max = c[0]; 00410 for (int i=1; i<c.size(); i++) { 00411 min = std::min(c[i],min); max = std::max(c[i],max); 00412 } 00413 GECODE_ME_CHECK(x1.gq(home,min)); 00414 GECODE_ME_CHECK(x1.lq(home,max)); 00415 Support::IntType val_type = 00416 std::max(Support::s_type(min),Support::s_type(max)); 00417 switch (idx_type) { 00418 case Support::IT_CHAR: 00419 switch (val_type) { 00420 case Support::IT_CHAR: 00421 return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1); 00422 case Support::IT_SHRT: 00423 return Int<V0,V1,signed char,signed short int>::post(home,c,x0,x1); 00424 default: break; 00425 } 00426 break; 00427 case Support::IT_SHRT: 00428 switch (val_type) { 00429 case Support::IT_CHAR: 00430 case Support::IT_SHRT: 00431 return Int<V0,V1,signed short int,signed short int>::post(home,c,x0,x1); 00432 default: break; 00433 } 00434 break; 00435 default: break; 00436 } 00437 return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1); 00438 } 00439 00440 }}} 00441 00442 // STATISTICS: int-prop 00443