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
00035
00036
00037
00038 namespace Gecode { namespace Int { namespace Element {
00039
00040
00041
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
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
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
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>::reschedule(Space& home) {
00221 x0.reschedule(home,*this,PC_INT_DOM);
00222 x1.reschedule(home,*this,PC_INT_DOM);
00223 }
00224
00225 template<class V0, class V1, class Idx, class Val>
00226 void
00227 Int<V0,V1,Idx,Val>::prune_idx(void) {
00228 Idx p = 0;
00229 Idx i = iv[p].idx_next;
00230 ViewRanges<V0> v(x0);
00231 while (v() && (i != 0)) {
00232 assert(!iv[i].marked());
00233 if (iv[i].idx < v.min()) {
00234 iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
00235 } else if (iv[i].idx > v.max()) {
00236 ++v;
00237 } else {
00238 p=i; i=iv[i].idx_next;
00239 }
00240 }
00241 iv[p].idx_next = 0;
00242 while (i != 0) {
00243 iv[i].mark(); i=iv[i].idx_next;
00244 }
00245 }
00246
00247 template<class V0, class V1, class Idx, class Val>
00248 void
00249 Int<V0,V1,Idx,Val>::prune_val(void) {
00250 Idx p = 0;
00251 Idx i = iv[p].val_next;
00252 ViewRanges<V1> v(x1);
00253 while (v() && (i != 0)) {
00254 if (iv[i].marked()) {
00255 i=iv[i].val_next; iv[p].val_next=i;
00256 } else if (iv[i].val < v.min()) {
00257 iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
00258 } else if (iv[i].val > v.max()) {
00259 ++v;
00260 } else {
00261 p=i; i=iv[i].val_next;
00262 }
00263 }
00264 iv[p].val_next = 0;
00265 while (i != 0) {
00266 iv[i].mark(); i=iv[i].val_next;
00267 }
00268 }
00269
00270 template<class V0, class V1, class Idx, class Val>
00271 ExecStatus
00272 Int<V0,V1,Idx,Val>::assigned_val(Space& home, IntSharedArray& c,
00273 V0 x0, V1 x1) {
00274 Region r(home);
00275 int* v = r.alloc<int>(x0.size());
00276 int n = 0;
00277 for (ViewValues<V0> i(x0); i(); ++i)
00278 if (c[i.val()] != x1.val())
00279 v[n++]=i.val();
00280 Iter::Values::Array iv(v,n);
00281 GECODE_ME_CHECK(x0.minus_v(home,iv,false));
00282 return ES_OK;
00283 }
00284
00285 template<class V0, class V1, class Idx, class Val>
00286 ExecStatus
00287 Int<V0,V1,Idx,Val>::propagate(Space& home, const ModEventDelta&) {
00288 if (x0.assigned()) {
00289 GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
00290 return home.ES_SUBSUMED(*this);
00291 }
00292
00293 if (x1.assigned() && (iv == NULL)) {
00294 GECODE_ES_CHECK(assigned_val(home,c,x0,x1));
00295 return home.ES_SUBSUMED(*this);
00296 }
00297
00298 if ((static_cast<ValSize>(x1.size()) == s1) &&
00299 (static_cast<IdxSize>(x0.size()) != s0)) {
00300 assert(iv != NULL);
00301 assert(!shared(x0,x1));
00302
00303 prune_idx();
00304
00305 IterValUnmark v(iv);
00306 GECODE_ME_CHECK(x1.narrow_v(home,v,false));
00307
00308 s1=static_cast<ValSize>(x1.size());
00309
00310 assert(!x0.assigned());
00311 return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00312 }
00313
00314 if ((static_cast<IdxSize>(x0.size()) == s0) &&
00315 (static_cast<ValSize>(x1.size()) != s1)) {
00316 assert(iv != NULL);
00317 assert(!shared(x0,x1));
00318
00319 prune_val();
00320
00321 IterIdxUnmark i(iv);
00322 GECODE_ME_CHECK(x0.narrow_v(home,i,false));
00323
00324 s0=static_cast<IdxSize>(x0.size());
00325
00326 return (x0.assigned() || x1.assigned()) ?
00327 home.ES_SUBSUMED(*this) : ES_FIX;
00328 }
00329
00330 bool assigned = x0.assigned() && x1.assigned();
00331 if (iv == NULL) {
00332
00333 iv = home.alloc<IdxVal>(x0.size() + 1);
00334
00335
00336
00337 IdxVal* by_idx = &iv[1];
00338 Idx size = 0;
00339 for (ViewValues<V0> v(x0); v(); ++v)
00340 if ((x1.min() <= c[v.val()]) && (x1.max() >= c[v.val()])) {
00341 by_idx[size].idx = static_cast<Idx>(v.val());
00342 by_idx[size].val = static_cast<Val>(c[v.val()]);
00343 size++;
00344 }
00345 if (size == 0)
00346 return ES_FAILED;
00347
00348 Region r(home);
00349 Idx* by_val = r.alloc<Idx>(size);
00350 if (x1.width() <= 128) {
00351 int n_buckets = static_cast<int>(x1.width());
00352 int* pos = r.alloc<int>(n_buckets);
00353 int* buckets = pos - x1.min();
00354 for (int i=n_buckets; i--; )
00355 pos[i]=0;
00356 for (Idx i=size; i--; )
00357 buckets[by_idx[i].val]++;
00358 int p=0;
00359 for (int i=0; i<n_buckets; i++) {
00360 int n=pos[i]; pos[i]=p; p+=n;
00361 }
00362 assert(p == size);
00363 for (Idx i=size; i--; )
00364 by_val[buckets[by_idx[i].val]++] = i+1;
00365 } else {
00366 for (Idx i = size; i--; )
00367 by_val[i] = i+1;
00368 ByVal less(iv);
00369 Support::quicksort<Idx>(by_val,size,less);
00370 }
00371
00372 for (Idx i = size-1; i--; ) {
00373 by_idx[i].idx_next = i+2;
00374 iv[by_val[i]].val_next = by_val[i+1];
00375 }
00376 by_idx[size-1].idx_next = 0;
00377 iv[by_val[size-1]].val_next = 0;
00378
00379 iv[0].idx_next = 1;
00380 iv[0].val_next = by_val[0];
00381 } else {
00382 prune_idx();
00383 }
00384
00385
00386 prune_val();
00387
00388
00389 {
00390 IterIdxUnmark i(iv);
00391 GECODE_ME_CHECK(x0.narrow_v(home,i,false));
00392 IterVal v(iv);
00393 if (shared(x0,x1)) {
00394 GECODE_ME_CHECK(x1.inter_v(home,v,false));
00395 s0=static_cast<IdxSize>(x0.size());
00396 s1=static_cast<ValSize>(x1.size());
00397 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00398 } else {
00399 GECODE_ME_CHECK(x1.narrow_v(home,v,false));
00400 s0=static_cast<IdxSize>(x0.size());
00401 s1=static_cast<ValSize>(x1.size());
00402 return (x0.assigned() || x1.assigned()) ?
00403 home.ES_SUBSUMED(*this) : ES_FIX;
00404 }
00405 }
00406 }
00407
00408 template<class V0, class V1>
00409 forceinline ExecStatus
00410 post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
00411 assert(c.size() > 0);
00412 GECODE_ME_CHECK(x0.gq(home,0));
00413 GECODE_ME_CHECK(x0.le(home,c.size()));
00414 Support::IntType idx_type = Support::s_type(c.size());
00415 int min = c[0];
00416 int max = c[0];
00417 for (int i=1; i<c.size(); i++) {
00418 min = std::min(c[i],min); max = std::max(c[i],max);
00419 }
00420 GECODE_ME_CHECK(x1.gq(home,min));
00421 GECODE_ME_CHECK(x1.lq(home,max));
00422 Support::IntType val_type =
00423 std::max(Support::s_type(min),Support::s_type(max));
00424 switch (idx_type) {
00425 case Support::IT_CHAR:
00426 switch (val_type) {
00427 case Support::IT_CHAR:
00428 return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
00429 case Support::IT_SHRT:
00430 return Int<V0,V1,signed char,signed short int>::post(home,c,x0,x1);
00431 default: break;
00432 }
00433 break;
00434 case Support::IT_SHRT:
00435 switch (val_type) {
00436 case Support::IT_CHAR:
00437 case Support::IT_SHRT:
00438 return Int<V0,V1,signed short int,signed short int>::post(home,c,x0,x1);
00439 default: break;
00440 }
00441 break;
00442 default: break;
00443 }
00444 return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
00445 }
00446
00447 }}}
00448
00449
00450