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