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 #include <algorithm>
00039 #include <type_traits>
00040
00041 namespace Gecode { namespace Int { namespace Extensional {
00042
00043
00044
00045
00046
00047 template<class View>
00048 forceinline void
00049 Compact<View>::CTAdvisor::adjust(void) {
00050 {
00051 int n = view().min();
00052 assert((_fst->min <= n) && (n <= _lst->max));
00053 while (n > _fst->max)
00054 _fst++;
00055 assert((_fst->min <= n) && (n <= _lst->max));
00056 }
00057 {
00058 int n = view().max();
00059 assert((_fst->min <= n) && (n <= _lst->max));
00060 while (n < _lst->min)
00061 _lst--;
00062 assert((_fst->min <= n) && (n <= _lst->max));
00063 }
00064 }
00065
00066 template<class View>
00067 forceinline
00068 Compact<View>::CTAdvisor::CTAdvisor
00069 (Space& home, Propagator& p,
00070 Council<CTAdvisor>& c, const TupleSet& ts, View x0, int i)
00071 : ViewAdvisor<View>(home,p,c,x0), _fst(ts.fst(i)), _lst(ts.lst(i)) {
00072 adjust();
00073 }
00074
00075 template<class View>
00076 forceinline
00077 Compact<View>::CTAdvisor::CTAdvisor(Space& home, CTAdvisor& a)
00078 : ViewAdvisor<View>(home,a), _fst(a._fst), _lst(a._lst) {}
00079
00080 template<class View>
00081 forceinline const typename Compact<View>::Range*
00082 Compact<View>::CTAdvisor::fst(void) const {
00083 return _fst;
00084 }
00085
00086 template<class View>
00087 forceinline const typename Compact<View>::Range*
00088 Compact<View>::CTAdvisor::lst(void) const {
00089 return _lst;
00090 }
00091
00092 template<class View>
00093 forceinline void
00094 Compact<View>::CTAdvisor::dispose(Space& home, Council<CTAdvisor>& c) {
00095 (void) ViewAdvisor<View>::dispose(home,c);
00096 }
00097
00098
00099
00100
00101
00102
00103 template<class View>
00104 forceinline
00105 Compact<View>::Status::Status(StatusType t)
00106 : s(t) {}
00107 template<class View>
00108 forceinline
00109 Compact<View>::Status::Status(const Status& s)
00110 : s(s.s) {}
00111 template<class View>
00112 forceinline typename Compact<View>::StatusType
00113 Compact<View>::Status::type(void) const {
00114 return static_cast<StatusType>(s & 3);
00115 }
00116 template<class View>
00117 forceinline bool
00118 Compact<View>::Status::single(CTAdvisor& a) const {
00119 if (type() != SINGLE)
00120 return false;
00121 assert(type() == 0);
00122 return reinterpret_cast<CTAdvisor*>(s) == &a;
00123 }
00124 template<class View>
00125 forceinline void
00126 Compact<View>::Status::touched(CTAdvisor& a) {
00127 if (!single(a))
00128 s = MULTIPLE;
00129 }
00130 template<class View>
00131 forceinline void
00132 Compact<View>::Status::none(void) {
00133 s = NONE;
00134 }
00135 template<class View>
00136 forceinline void
00137 Compact<View>::Status::propagating(void) {
00138 s = PROPAGATING;
00139 }
00140
00141
00142
00143
00144
00145
00146
00147 template<class View>
00148 const typename Compact<View>::Range*
00149 Compact<View>::range(CTAdvisor& a, int n) {
00150 assert((n > a.fst()->max) && (n < a.lst()->min));
00151 const Range* f=a.fst()+1;
00152 const Range* l=a.lst()-1;
00153 assert(f<=l);
00154 while (f < l) {
00155 const Range* m = f + ((l-f) >> 1);
00156 if (n < m->min) {
00157 l=m-1;
00158 } else if (n > m->max) {
00159 f=m+1;
00160 } else {
00161 f=m; break;
00162 }
00163 }
00164 assert((f->min <= n) && (n <= f->max));
00165 return f;
00166 }
00167
00168 template<class View>
00169 forceinline const BitSetData*
00170 Compact<View>::supports(CTAdvisor& a, int n) {
00171 const Range* fnd;
00172 const Range* fst=a.fst();
00173 const Range* lst=a.lst();
00174 if (n <= fst->max) {
00175 fnd=fst; goto found;
00176 } else if (n >= lst->min) {
00177 fnd=lst; goto found;
00178 } else {
00179 fnd=range(a,n);
00180 }
00181 found:
00182 assert((fnd->min <= n) && (n <= fnd->max));
00183 return fnd->supports(n_words,n);
00184 }
00185
00186 template<class View>
00187 forceinline
00188 Compact<View>::ValidSupports::ValidSupports(const Compact<View>& p,
00189 CTAdvisor& a)
00190 : n_words(p.n_words), max(a.view().max()),
00191 xr(a.view()), sr(a.fst()), n(xr.min()) {
00192 while (n > sr->max)
00193 sr++;
00194 s=sr->supports(n_words,n);
00195 }
00196 template<class View>
00197 forceinline
00198 Compact<View>::ValidSupports::ValidSupports(const TupleSet& ts,
00199 int i, View x)
00200 : n_words(ts.words()), max(x.max()), xr(x), sr(ts.fst(i)), n(xr.min()) {
00201 while (n > sr->max)
00202 sr++;
00203 s=sr->supports(n_words,n);
00204 }
00205 template<class View>
00206 forceinline void
00207 Compact<View>::ValidSupports::operator ++(void) {
00208 n++;
00209 if (n <= xr.max()) {
00210 assert(n <= sr->max);
00211 s += n_words;
00212 } else if (n <= max) {
00213 while (n > xr.max())
00214 ++xr;
00215 n = xr.min();
00216 while (n > sr->max)
00217 sr++;
00218 s = sr->supports(n_words,n);
00219 assert((xr.min() <= n) && (n <= xr.max()));
00220 assert((sr->min <= n) && (n <= sr->max));
00221 assert(sr->min <= xr.min());
00222 }
00223 }
00224 template<class View>
00225 forceinline bool
00226 Compact<View>::ValidSupports::operator ()(void) const {
00227 return n <= max;
00228 }
00229 template<class View>
00230 forceinline const BitSetData*
00231 Compact<View>::ValidSupports::supports(void) const {
00232 assert(s == sr->supports(n_words,n));
00233 return s;
00234 }
00235 template<class View>
00236 forceinline int
00237 Compact<View>::ValidSupports::val(void) const {
00238 return n;
00239 }
00240
00241
00242
00243
00244
00245 template<class View>
00246 forceinline
00247 Compact<View>::LostSupports::LostSupports
00248 (const Compact<View>& p, CTAdvisor& a, int l0, int h0)
00249 : n_words(p.n_words), r(a.fst()), l(l0), h(h0) {
00250
00251 while (l > r->max)
00252 r++;
00253 l=std::max(l,r->min);
00254 s=r->supports(n_words,l);
00255 }
00256 template<class View>
00257 forceinline void
00258 Compact<View>::LostSupports::operator ++(void) {
00259 l++; s += n_words;
00260 while ((l <= h) && (l > r->max)) {
00261 r++; l=r->min; s=r->s;
00262 }
00263 }
00264 template<class View>
00265 forceinline bool
00266 Compact<View>::LostSupports::operator ()(void) const {
00267 return l<=h;
00268 }
00269 template<class View>
00270 forceinline const TupleSet::BitSetData*
00271 Compact<View>::LostSupports::supports(void) const {
00272 assert((l >= r->min) && (l <= r->max));
00273 assert(s == r->supports(n_words,l));
00274 return s;
00275 }
00276
00277 template<class View>
00278 forceinline
00279 Compact<View>::Compact(Space& home, Compact& p)
00280 : Propagator(home,p), unassigned(p.unassigned), n_words(p.n_words),
00281 status(NONE), ts(p.ts) {
00282 c.update(home,p.c);
00283 }
00284
00285 template<class View>
00286 forceinline
00287 Compact<View>::Compact(Home home, ViewArray<View>& x,
00288 const TupleSet& ts0)
00289 : Propagator(home), unassigned(x.size()), n_words(ts0.words()),
00290 status(MULTIPLE), ts(ts0), c(home) {
00291 home.notice(*this, AP_DISPOSE);
00292 }
00293
00294 template<class View>
00295 forceinline size_t
00296 Compact<View>::dispose(Space& home) {
00297 home.ignore(*this,AP_DISPOSE);
00298 c.dispose(home);
00299 ts.~TupleSet();
00300 (void) Propagator::dispose(home);
00301 return sizeof(*this);
00302 }
00303
00304
00305
00306
00307
00308
00309 template<class View, class Table>
00310 template<class TableProp>
00311 forceinline
00312 CompactTable<View,Table>::CompactTable(Space& home, TableProp& p)
00313 : Compact<View>(home,p), table(home,p.table) {
00314 assert(!table.empty());
00315 }
00316
00317 template<class View, class Table>
00318 Actor*
00319 CompactTable<View,Table>::copy(Space& home) {
00320 assert((table.words() > 0U) && (table.width() >= table.words()));
00321 if (table.words() <= 4U) {
00322 switch (table.width()) {
00323 case 0U:
00324 GECODE_NEVER; break;
00325 case 1U:
00326 return new (home) CompactTable<View,TinyBitSet<1U>>(home,*this);
00327 case 2U:
00328 return new (home) CompactTable<View,TinyBitSet<2U>>(home,*this);
00329 case 3U:
00330 return new (home) CompactTable<View,TinyBitSet<3U>>(home,*this);
00331 case 4U:
00332 return new (home) CompactTable<View,TinyBitSet<4U>>(home,*this);
00333 default:
00334 break;
00335 }
00336 }
00337 if (std::is_same<Table,BitSet<unsigned char>>::value) {
00338 goto copy_char;
00339 } else if (std::is_same<Table,BitSet<unsigned short int>>::value) {
00340 switch (Gecode::Support::u_type(table.width())) {
00341 case Gecode::Support::IT_CHAR:
00342 goto copy_char;
00343 case Gecode::Support::IT_SHRT:
00344 goto copy_short;
00345 case Gecode::Support::IT_INT:
00346 default:
00347 GECODE_NEVER;
00348 }
00349 } else {
00350 switch (Gecode::Support::u_type(table.width())) {
00351 case Gecode::Support::IT_CHAR:
00352 goto copy_char;
00353 case Gecode::Support::IT_SHRT:
00354 goto copy_short;
00355 case Gecode::Support::IT_INT:
00356 return new (home) CompactTable<View,BitSet<unsigned int>>(home,*this);
00357 default: GECODE_NEVER;
00358 }
00359 GECODE_NEVER;
00360 return nullptr;
00361 }
00362 copy_char:
00363 return new (home) CompactTable<View,BitSet<unsigned char>>(home,*this);
00364 copy_short:
00365 return new (home) CompactTable<View,BitSet<unsigned short int>>(home,*this);
00366 }
00367
00368 template<class View,class Table>
00369 forceinline
00370 CompactTable<View,Table>::CompactTable(Home home, ViewArray<View>& x,
00371 const TupleSet& ts)
00372 : Compact<View>(home,x,ts), table(home,ts.words()) {
00373 Region r;
00374 BitSetData* mask = r.alloc<BitSetData>(table.size());
00375
00376 for (int i = x.size(); i--; ) {
00377 table.clear_mask(mask);
00378 for (ValidSupports vs(ts,i,x[i]); vs(); ++vs)
00379 table.add_to_mask(vs.supports(),mask);
00380 table.template intersect_with_mask<false>(mask);
00381 if (table.empty())
00382 return;
00383 }
00384
00385 for (int i = x.size(); i--; ) {
00386 if (!x[i].assigned())
00387 (void) new (home) CTAdvisor(home,*this,c,ts,x[i],i);
00388 else
00389 unassigned--;
00390 }
00391
00392 if (unassigned < x.size())
00393 View::schedule(home,*this,ME_INT_VAL);
00394 else
00395 View::schedule(home,*this,ME_INT_BND);
00396 }
00397
00398 template<class View, class Table>
00399 forceinline size_t
00400 CompactTable<View,Table>::dispose(Space& home) {
00401 (void) Compact<View>::dispose(home);
00402 return sizeof(*this);
00403 }
00404
00405 template<class View, class Table>
00406 PropCost
00407 CompactTable<View,Table>::cost(const Space&, const ModEventDelta&) const {
00408 return PropCost::quadratic(PropCost::HI,unassigned);
00409 }
00410
00411 template<class View, class Table>
00412 void
00413 CompactTable<View,Table>::reschedule(Space& home) {
00414
00415 if ((status.type() != StatusType::NONE) || (unassigned == 0) || table.empty())
00416 View::schedule(home,*this,ME_INT_DOM);
00417 }
00418
00419 template<class View, class Table>
00420 ExecStatus
00421 CompactTable<View,Table>::propagate(Space& home, const ModEventDelta&) {
00422 if (table.empty())
00423 return ES_FAILED;
00424 if (unassigned == 0)
00425 return home.ES_SUBSUMED(*this);
00426
00427 Status touched(status);
00428
00429 status.propagating();
00430
00431 Region r;
00432
00433
00434 for (Advisors<CTAdvisor> as(c); as(); ++as) {
00435 CTAdvisor& a = as.advisor();
00436 View x = a.view();
00437
00438
00439 if (touched.single(a) || x.assigned())
00440 continue;
00441
00442 if (x.size() == 2) {
00443 if (!table.intersects(supports(a,x.min())))
00444 GECODE_ME_CHECK(x.eq(home,x.max()));
00445 else if (!table.intersects(supports(a,x.max())))
00446 GECODE_ME_CHECK(x.eq(home,x.min()));
00447 if (x.assigned())
00448 unassigned--;
00449 else
00450 a.adjust();
00451 } else {
00452
00453 int* nq = r.alloc<int>(x.size());
00454 unsigned int n_nq = 0U;
00455
00456 int last_support = 0;
00457 for (ValidSupports vs(*this,a); vs(); ++vs)
00458 if (!table.intersects(vs.supports()))
00459 nq[n_nq++] = vs.val();
00460 else
00461 last_support = vs.val();
00462
00463 if (n_nq > 0U) {
00464 if (n_nq == 1U) {
00465 ModEvent me = x.nq(home,nq[0]);
00466 if (me_failed(me)) return ES_FAILED;
00467 assert(me != ME_INT_VAL);
00468 } else if (n_nq == x.size() - 1U) {
00469 GECODE_ME_CHECK(x.eq(home,last_support));
00470 unassigned--;
00471 goto noadjust;
00472 } else {
00473 Iter::Values::Array rnq(nq,n_nq);
00474 GECODE_ASSUME(n_nq >= 2U);
00475 ModEvent me = x.minus_v(home,rnq,false);
00476 if (me_failed(me)) return ES_FAILED;
00477 assert(me != ME_INT_VAL);
00478 }
00479 a.adjust();
00480 noadjust: ;
00481 }
00482 r.free();
00483 }
00484 }
00485
00486
00487 status.none();
00488
00489 assert(!table.empty());
00490
00491 return (unassigned <= 1) ? home.ES_SUBSUMED(*this) : ES_FIX;
00492 }
00493
00494 template<class View, class Table>
00495 forceinline ExecStatus
00496 CompactTable<View,Table>::post(Home home, ViewArray<View>& x,
00497 const TupleSet& ts) {
00498
00499 for (int i=x.size(); i--; ) {
00500 TupleSet::Ranges r(ts,i);
00501 GECODE_ME_CHECK(x[i].inter_r(home, r, false));
00502 }
00503 if ((x.size() > 1) && (ts.tuples() > 1)) {
00504 CompactTable<View,Table>* ct = new (home) CompactTable(home,x,ts);
00505 if (ct->table.empty())
00506 return ES_FAILED;
00507 }
00508 return ES_OK;
00509 }
00510
00511 template<class View, class Table>
00512 ExecStatus
00513 CompactTable<View,Table>::advise(Space& home, Advisor& a0, const Delta& d) {
00514 CTAdvisor& a = static_cast<CTAdvisor&>(a0);
00515
00516
00517 if (table.empty())
00518 return Compact<View>::disabled() ? home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
00519
00520 View x = a.view();
00521
00522
00523
00524
00525
00526 if (status.type() == StatusType::PROPAGATING)
00527 return x.assigned() ? home.ES_FIX_DISPOSE(c,a) : ES_FIX;
00528
00529
00530 status.touched(a);
00531
00532 if (x.assigned()) {
00533
00534 table.template intersect_with_mask<true>(supports(a,x.val()));
00535 unassigned--;
00536 return home.ES_NOFIX_DISPOSE(c,a);
00537 }
00538
00539 if (!x.any(d) && (x.min(d) == x.max(d))) {
00540 table.nand_with_mask(supports(a,x.min(d)));
00541 a.adjust();
00542 } else if (!x.any(d) && (x.width(d) <= x.size())) {
00543
00544 for (LostSupports ls(*this,a,x.min(d),x.max(d)); ls(); ++ls) {
00545 table.nand_with_mask(ls.supports());
00546 if (table.empty())
00547 return Compact<View>::disabled() ? home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
00548 }
00549 a.adjust();
00550 } else {
00551 a.adjust();
00552
00553 if (x.size() == 2) {
00554 table.intersect_with_masks(supports(a,x.min()),
00555 supports(a,x.max()));
00556 } else {
00557 Region r;
00558 BitSetData* mask = r.alloc<BitSetData>(table.size());
00559
00560 table.clear_mask(mask);
00561 for (ValidSupports vs(*this,a); vs(); ++vs)
00562 table.add_to_mask(vs.supports(),mask);
00563 table.template intersect_with_mask<false>(mask);
00564 }
00565 }
00566
00567
00568 if (table.empty())
00569 return Compact<View>::disabled() ? home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
00570
00571
00572 return ES_NOFIX;
00573 }
00574
00575
00576
00577
00578
00579 template<class View>
00580 inline ExecStatus
00581 postcompact(Home home, ViewArray<View>& x, const TupleSet& ts) {
00582 assert(ts.words() > 0U);
00583
00584 for (int i=x.size(); i--; ) {
00585 TupleSet::Ranges r(ts,i);
00586 GECODE_ME_CHECK(x[i].inter_r(home, r, false));
00587 }
00588
00589 switch (ts.words()) {
00590 case 0U:
00591 GECODE_NEVER; return ES_OK;
00592 case 1U:
00593 return CompactTable<View,TinyBitSet<1U>>::post(home,x,ts);
00594 case 2U:
00595 return CompactTable<View,TinyBitSet<2U>>::post(home,x,ts);
00596 case 3U:
00597 return CompactTable<View,TinyBitSet<3U>>::post(home,x,ts);
00598 case 4U:
00599 return CompactTable<View,TinyBitSet<4U>>::post(home,x,ts);
00600 default:
00601 switch (Gecode::Support::u_type(ts.words())) {
00602 case Gecode::Support::IT_CHAR:
00603 return CompactTable<View,BitSet<unsigned char>>::post(home,x,ts);
00604 case Gecode::Support::IT_SHRT:
00605 return CompactTable<View,BitSet<unsigned short int>>::post(home,x,ts);
00606 case Gecode::Support::IT_INT:
00607 return CompactTable<View,BitSet<unsigned int>>::post(home,x,ts);
00608 default: GECODE_NEVER;
00609 }
00610 }
00611 GECODE_NEVER;
00612 return ES_OK;
00613 }
00614
00615 }}}
00616
00617
00618