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>::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 iv(v,n);
00274 GECODE_ME_CHECK(x0.minus_v(home,iv,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
00326 iv = home.alloc<IdxVal>(x0.size() + 1);
00327
00328
00329
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
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
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
00372 iv[0].idx_next = 1;
00373 iv[0].val_next = by_val[0];
00374 } else {
00375 prune_idx();
00376 }
00377
00378
00379 prune_val();
00380
00381
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
00443