Generated on Sun Feb 17 15:24:18 2019 for Gecode by doxygen 1.6.3

compact.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Linnea Ingmar <linnea.ingmar@hotmail.com>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Linnea Ingmar, 2017
00009  *     Christian Schulte, 2017
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <algorithm>
00037 #include <type_traits>
00038 
00039 namespace Gecode { namespace Int { namespace Extensional {
00040       
00041   /*
00042    * Advisor
00043    *
00044    */
00045   template<class View, bool pos>
00046   forceinline void
00047   Compact<View,pos>::CTAdvisor::adjust(void) {
00048     if (pos) {
00049       {
00050         int n = view().min();
00051         assert((_fst->min <= n) && (n <= _lst->max));
00052         while (n > _fst->max)
00053           _fst++;
00054         assert((_fst->min <= n) && (n <= _lst->max));
00055       }
00056       {
00057         int n = view().max();
00058         assert((_fst->min <= n) && (n <= _lst->max));
00059         while (n < _lst->min)
00060           _lst--;
00061         assert((_fst->min <= n) && (n <= _lst->max));
00062       }
00063     } else {
00064       {
00065         int n = view().min();
00066         while ((_fst <= _lst) && (n > _fst->max))
00067           _fst++;
00068       }
00069       {
00070         int n = view().max();
00071         while ((_fst <= _lst) && (n < _lst->min))
00072           _lst--;
00073       }
00074     }
00075   }
00076 
00077   template<class View, bool pos>
00078   forceinline
00079   Compact<View,pos>::CTAdvisor::CTAdvisor
00080   (Space& home, Propagator& p, 
00081    Council<CTAdvisor>& c, const TupleSet& ts, View x0, int i)
00082     : ViewAdvisor<View>(home,p,c,x0), _fst(ts.fst(i)), _lst(ts.lst(i)) {
00083     adjust();
00084   }
00085 
00086   template<class View, bool pos>
00087   forceinline
00088   Compact<View,pos>::CTAdvisor::CTAdvisor(Space& home, CTAdvisor& a)
00089     : ViewAdvisor<View>(home,a), _fst(a._fst), _lst(a._lst) {}
00090 
00091   template<class View, bool pos>
00092   forceinline const typename Compact<View,pos>::Range*
00093   Compact<View,pos>::CTAdvisor::fst(void) const {
00094     return _fst;
00095   }
00096 
00097   template<class View, bool pos>
00098   forceinline const typename Compact<View,pos>::Range*
00099   Compact<View,pos>::CTAdvisor::lst(void) const {
00100     return _lst;
00101   }
00102 
00103   template<class View, bool pos>
00104   forceinline void
00105   Compact<View,pos>::CTAdvisor::dispose(Space& home, Council<CTAdvisor>& c) {
00106     (void) ViewAdvisor<View>::dispose(home,c);
00107   }
00108 
00109 
00110   /*
00111    * The propagator base class
00112    *
00113    */
00114   template<class View, bool pos>
00115   const typename Compact<View,pos>::Range*
00116   Compact<View,pos>::range(CTAdvisor& a, int n) {
00117     assert((n > a.fst()->max) && (n < a.lst()->min));
00118 
00119     const Range* f=a.fst()+1;
00120     const Range* l=a.lst()-1;
00121 
00122     assert(!pos || (f<=l));
00123 
00124     while (f < l) {
00125       const Range* m = f + ((l-f) >> 1);
00126       if (n < m->min) {
00127         l=m-1;
00128       } else if (n > m->max) {
00129         f=m+1;
00130       } else {
00131         f=m; break;
00132       }
00133     }
00134 
00135     if (pos) {
00136       assert((f->min <= n) && (n <= f->max));
00137       return f;
00138     } else {
00139       if ((f <= l) && (f->min <= n) && (n <= f->max))
00140         return f;
00141       else
00142         return nullptr;
00143     }
00144   }
00145 
00146   template<class View, bool pos>
00147   forceinline const BitSetData*
00148   Compact<View,pos>::supports(CTAdvisor& a, int n) {
00149     const Range* fnd;
00150     const Range* fst=a.fst();
00151     const Range* lst=a.lst();
00152     if (pos) {
00153       if (n <= fst->max) {
00154         fnd=fst;
00155       } else if (n >= lst->min) {
00156         fnd=lst;
00157       } else {
00158         fnd=range(a,n);
00159       }
00160     } else {
00161       if ((n < fst->min) || (n > lst->max))
00162         return nullptr;
00163       if (n <= fst->max) {
00164         fnd=fst;
00165       } else if (n >= lst->min) {
00166         fnd=lst;
00167       } else {
00168         fnd=range(a,n);
00169         if (!fnd)
00170           return nullptr;
00171       }
00172     }
00173     assert((fnd->min <= n) && (n <= fnd->max));
00174     return fnd->supports(n_words,n);
00175   }
00176 
00177   template<class View, bool pos>
00178   forceinline void
00179   Compact<View,pos>::ValidSupports::find(void) {
00180     assert(!pos);
00181     assert(n <= max);
00182     while (true) {
00183       while (xr() && (n > xr.max()))
00184         ++xr;
00185       if (!xr()) {
00186         n = max+1; return;
00187       }
00188       assert(n <= xr.max());
00189       n = std::max(n,xr.min());
00190       
00191       while ((sr <= lst) && (n > sr->max))
00192         sr++;
00193       if (sr > lst) {
00194         n = max+1; return;
00195       }
00196       assert(n <= sr->max);
00197       n = std::max(n,sr->min);
00198 
00199       if ((xr.min() <= n) && (n <= xr.max())) {
00200         s = sr->supports(n_words,n);
00201         return;
00202       }
00203     }
00204     GECODE_NEVER;
00205   }
00206 
00207   template<class View, bool pos>
00208   forceinline
00209   Compact<View,pos>::ValidSupports::ValidSupports(const Compact<View,pos>& p,
00210                                                   CTAdvisor& a)
00211     : n_words(p.n_words), max(a.view().max()),
00212       xr(a.view()), sr(a.fst()), lst(a.lst()), n(xr.min()) {
00213     if (pos) {
00214       while (n > sr->max)
00215         sr++;
00216       s = sr->supports(n_words,n);
00217     } else {
00218       s = nullptr; // To avoid warnings
00219       find();
00220     }
00221   }
00222   template<class View, bool pos>
00223   forceinline
00224   Compact<View,pos>::ValidSupports::ValidSupports(const TupleSet& ts,
00225                                                   int i, View x)
00226     : n_words(ts.words()), max(x.max()),
00227       xr(x), sr(ts.fst(i)), lst(ts.lst(i)), n(xr.min()) {
00228     if (pos) {
00229       while (n > sr->max)
00230         sr++;
00231       s = sr->supports(n_words,n);
00232     } else {
00233       s = nullptr; // To avoid warnings
00234       find();
00235     }
00236   }
00237   template<class View, bool pos>
00238   forceinline void
00239   Compact<View,pos>::ValidSupports::operator ++(void) {
00240     n++;
00241     if (pos) {
00242       if (n <= xr.max()) {
00243         assert(n <= sr->max);
00244         s += n_words;
00245       } else if (n <= max) {
00246         while (n > xr.max())
00247           ++xr;
00248         n = xr.min();
00249         while (n > sr->max)
00250           sr++;
00251         s = sr->supports(n_words,n);
00252         assert((xr.min() <= n) && (n <= xr.max()));
00253         assert((sr->min <= n) && (n <= sr->max));
00254         assert(sr->min <= xr.min());
00255       }
00256     } else {
00257       if ((n <= sr->max) && (n <= xr.max())) {
00258         s += n_words;
00259       } else if (n <= max) {
00260         find();
00261       }
00262     }
00263   }
00264   template<class View, bool pos>
00265   forceinline bool
00266   Compact<View,pos>::ValidSupports::operator ()(void) const {
00267     return n <= max;
00268   }
00269   template<class View, bool pos>
00270   forceinline const BitSetData*
00271   Compact<View,pos>::ValidSupports::supports(void) const {
00272     assert(s == sr->supports(n_words,n));
00273     return s;
00274   }
00275   template<class View, bool pos>
00276   forceinline int
00277   Compact<View,pos>::ValidSupports::val(void) const {
00278     return n;
00279   }
00280 
00281   /*
00282    * Lost supports iterator
00283    *
00284    */
00285   template<class View, bool pos>
00286   forceinline
00287   Compact<View,pos>::LostSupports::LostSupports
00288   (const Compact<View,pos>& p, CTAdvisor& a, int l0, int h0)
00289     : n_words(p.n_words), r(a.fst()), l(l0), h(h0) {
00290     assert(pos);
00291     // Move to first value for which there is support
00292     while (l > r->max)
00293       r++;
00294     l = std::max(l,r->min);
00295     s = r->supports(n_words,l);
00296   }      
00297   template<class View, bool pos>
00298   forceinline void
00299   Compact<View,pos>::LostSupports::operator ++(void) {
00300     l++; s += n_words;
00301     while ((l <= h) && (l > r->max)) {
00302       r++; l=r->min; s=r->s;
00303     }
00304   }
00305   template<class View, bool pos>
00306   forceinline bool
00307   Compact<View,pos>::LostSupports::operator ()(void) const {
00308     return l<=h;
00309   }
00310   template<class View, bool pos>
00311   forceinline const TupleSet::BitSetData*
00312   Compact<View,pos>::LostSupports::supports(void) const {
00313     assert((l >= r->min) && (l <= r->max));
00314     assert(s == r->supports(n_words,l));
00315     return s;
00316   }
00317 
00318   template<class View, bool pos>
00319   forceinline bool
00320   Compact<View,pos>::all(void) const {
00321     Advisors<CTAdvisor> as(c);
00322     return !as();
00323   }
00324   template<class View, bool pos>
00325   forceinline bool
00326   Compact<View,pos>::atmostone(void) const {
00327     Advisors<CTAdvisor> as(c);
00328     if (!as()) return true;
00329     ++as;
00330     return !as();
00331   }
00332 
00333   template<class View, bool pos>
00334   forceinline
00335   Compact<View,pos>::Compact(Space& home, Compact& p)
00336     : Propagator(home,p), n_words(p.n_words), ts(p.ts) {
00337     c.update(home,p.c);
00338   }
00339   
00340   template<class View, bool pos>
00341   forceinline
00342   Compact<View,pos>::Compact(Home home, const TupleSet& ts0)
00343     : Propagator(home), n_words(ts0.words()), ts(ts0), c(home) {
00344     home.notice(*this, AP_DISPOSE);
00345   }
00346 
00347   template<class View, bool pos>
00348   template<class Table>
00349   void
00350   Compact<View,pos>::setup(Space& home, Table& table, ViewArray<View>& x) {
00351     // For scheduling the propagator
00352     ModEvent me = ME_INT_BND;
00353     Region r;
00354     BitSetData* mask = r.alloc<BitSetData>(table.size());
00355     // Invalidate tuples
00356     for (int i=0; i<x.size(); i++) {
00357       table.clear_mask(mask);
00358       for (ValidSupports vs(ts,i,x[i]); vs(); ++vs)
00359         table.add_to_mask(vs.supports(),mask);
00360       table.template intersect_with_mask<false>(mask);
00361       // The propagator must be scheduled for subsumption
00362       if (table.empty())
00363         goto schedule;
00364     }
00365     // Post advisors
00366     for (int i=0; i<x.size(); i++)
00367       if (!x[i].assigned())
00368         (void) new (home) CTAdvisor(home,*this,c,ts,x[i],i);
00369       else
00370         me = ME_INT_VAL;
00371     // Schedule propagator
00372   schedule:
00373     View::schedule(home,*this,me);
00374   }
00375 
00376   template<class View, bool pos>
00377   template<class Table>
00378   forceinline bool
00379   Compact<View,pos>::full(const Table& table) const {
00380     unsigned long long int s = 1U;
00381     for (Advisors<CTAdvisor> as(c); as(); ++as) {
00382       s *= static_cast<unsigned long long int>(as.advisor().view().size());
00383       if (s > table.bits())
00384         return false;
00385     }
00386     return s == table.ones();
00387   }
00388 
00389   template<class View, bool pos>
00390   PropCost
00391   Compact<View,pos>::cost(const Space&, const ModEventDelta&) const {
00392     // Computing this is crucial in case there are many propagators!
00393     int n = 0;
00394     // The value of 3 is cheating from the Gecode kernel...
00395     for (Advisors<CTAdvisor> as(c); as() && (n <= 3); ++as)
00396       n++;
00397     return PropCost::quadratic(PropCost::HI,n);
00398   }
00399 
00400   template<class View, bool pos>
00401   forceinline size_t
00402   Compact<View,pos>::dispose(Space& home) {
00403     home.ignore(*this,AP_DISPOSE);
00404     c.dispose(home);
00405     ts.~TupleSet();
00406     (void) Propagator::dispose(home);
00407     return sizeof(*this);
00408   }
00409 
00410 
00411   /*
00412    * Status for the positive propagator
00413    *
00414    */
00415   template<class View, class Table>
00416   forceinline
00417   PosCompact<View,Table>::Status::Status(StatusType t)
00418     : s(t) {}
00419   template<class View, class Table>
00420   forceinline
00421   PosCompact<View,Table>::Status::Status(const Status& s)
00422     : s(s.s) {}
00423   template<class View, class Table>
00424   forceinline typename PosCompact<View,Table>::StatusType
00425   PosCompact<View,Table>::Status::type(void) const {
00426     return static_cast<StatusType>(s & 3);
00427   }
00428   template<class View, class Table>
00429   forceinline bool
00430   PosCompact<View,Table>::Status::single(CTAdvisor& a) const {
00431     if (type() != SINGLE)
00432       return false;
00433     assert(type() == 0);
00434     return reinterpret_cast<CTAdvisor*>(s) == &a;
00435   }
00436   template<class View, class Table>
00437   forceinline void
00438   PosCompact<View,Table>::Status::touched(CTAdvisor& a) {
00439     if (!single(a))
00440       s = MULTIPLE;
00441   }
00442   template<class View, class Table>
00443   forceinline void
00444   PosCompact<View,Table>::Status::none(void) {
00445     s = NONE;
00446   }
00447   template<class View, class Table>
00448   forceinline void
00449   PosCompact<View,Table>::Status::propagating(void) {
00450     s = PROPAGATING;
00451   }
00452   
00453   /*
00454    * The propagator proper
00455    *
00456    */
00457   template<class View, class Table>
00458   template<class TableProp>
00459   forceinline
00460   PosCompact<View,Table>::PosCompact(Space& home, TableProp& p)
00461     : Compact<View,true>(home,p), status(NONE), table(home,p.table) {
00462     assert(!table.empty());
00463   }
00464 
00465   template<class View, class Table>
00466   Actor*
00467   PosCompact<View,Table>::copy(Space& home) {
00468     assert((table.words() > 0U) && (table.width() >= table.words()));
00469     if (table.words() <= 4U) {
00470       switch (table.width()) {
00471       case 0U:
00472         GECODE_NEVER; break;
00473       case 1U:
00474         return new (home) PosCompact<View,TinyBitSet<1U>>(home,*this);
00475       case 2U:
00476         return new (home) PosCompact<View,TinyBitSet<2U>>(home,*this);
00477       case 3U:
00478         return new (home) PosCompact<View,TinyBitSet<3U>>(home,*this);
00479       case 4U:
00480         return new (home) PosCompact<View,TinyBitSet<4U>>(home,*this);
00481       default:
00482         break;
00483       }
00484     }
00485     if (std::is_same<Table,BitSet<unsigned char>>::value) {
00486       goto copy_char;
00487     } else if (std::is_same<Table,BitSet<unsigned short int>>::value) {
00488       switch (Gecode::Support::u_type(table.width())) {
00489       case Gecode::Support::IT_CHAR: goto copy_char;
00490       case Gecode::Support::IT_SHRT: goto copy_short;
00491       case Gecode::Support::IT_INT:  GECODE_NEVER;
00492       default:                       GECODE_NEVER;
00493       }
00494     } else {
00495       switch (Gecode::Support::u_type(table.width())) {
00496       case Gecode::Support::IT_CHAR: goto copy_char;
00497       case Gecode::Support::IT_SHRT: goto copy_short;
00498       case Gecode::Support::IT_INT:  goto copy_int;
00499       default: GECODE_NEVER;
00500       }
00501       GECODE_NEVER;
00502       return nullptr;
00503     }
00504   copy_char:
00505     return new (home) PosCompact<View,BitSet<unsigned char>>(home,*this);
00506   copy_short:
00507     return new (home) PosCompact<View,BitSet<unsigned short int>>(home,*this);
00508   copy_int:
00509     return new (home) PosCompact<View,BitSet<unsigned int>>(home,*this);
00510   }
00511 
00512   template<class View, class Table>
00513   forceinline
00514   PosCompact<View,Table>::PosCompact(Home home, ViewArray<View>& x,
00515                                      const TupleSet& ts)
00516     : Compact<View,true>(home,ts), status(MULTIPLE), table(home,ts.words()) {
00517     setup(home,table,x);
00518   }
00519       
00520   template<class View, class Table>
00521   forceinline ExecStatus
00522   PosCompact<View,Table>::post(Home home, ViewArray<View>& x,
00523                                const TupleSet& ts) {
00524     auto ct = new (home) PosCompact(home,x,ts);
00525     assert((x.size() > 1) && (ts.tuples() > 1));
00526     return ct->table.empty() ? ES_FAILED : ES_OK;
00527   }
00528 
00529   template<class View, class Table>
00530   forceinline size_t
00531   PosCompact<View,Table>::dispose(Space& home) {
00532     (void) Compact<View,true>::dispose(home);
00533     return sizeof(*this);
00534   }
00535 
00536   template<class View, class Table>
00537   void
00538   PosCompact<View,Table>::reschedule(Space& home) {
00539     // Modified variable, subsumption, or failure
00540     if ((status.type() != StatusType::NONE) || 
00541         all() || table.empty())
00542       View::schedule(home,*this,ME_INT_DOM);
00543   }
00544 
00545   template<class View, class Table>
00546   ExecStatus
00547   PosCompact<View,Table>::propagate(Space& home, const ModEventDelta&) {
00548     if (table.empty())
00549       return ES_FAILED;
00550     if (all())
00551       return home.ES_SUBSUMED(*this);
00552 
00553     Status touched(status);
00554     // Mark as performing propagation
00555     status.propagating();
00556     
00557     Region r;
00558     // Scan all values of all unassigned variables to see if they
00559     // are still supported.
00560     for (Advisors<CTAdvisor> as(c); as(); ++as) {
00561       CTAdvisor& a = as.advisor();
00562       View x = a.view();
00563 
00564       // No point filtering variable if it was the only modified variable
00565       if (touched.single(a) || x.assigned())
00566         continue;
00567       
00568       if (x.size() == 2) { // Consider min and max values only
00569         if (!table.intersects(supports(a,x.min())))
00570           GECODE_ME_CHECK(x.eq(home,x.max()));
00571         else if (!table.intersects(supports(a,x.max())))
00572           GECODE_ME_CHECK(x.eq(home,x.min()));
00573         if (!x.assigned())
00574           a.adjust();
00575       } else { // x.size() > 2
00576         // How many values to remove
00577         int* nq = r.alloc<int>(x.size());
00578         unsigned int n_nq = 0;
00579         // The initialization is here just to avoid warnings...
00580         int last_support = 0;
00581         for (ValidSupports vs(*this,a); vs(); ++vs)
00582           if (!table.intersects(vs.supports()))
00583             nq[n_nq++] = vs.val();
00584           else
00585             last_support = vs.val();
00586         // Remove collected values
00587         if (n_nq > 0U) {
00588           if (n_nq == 1U) {
00589             GECODE_ME_CHECK(x.nq(home,nq[0]));
00590           } else if (n_nq == x.size() - 1U) {
00591             GECODE_ME_CHECK(x.eq(home,last_support));
00592             goto noadjust;
00593           } else {
00594             Iter::Values::Array rnq(nq,n_nq);
00595             GECODE_ASSUME(n_nq >= 2U);
00596             GECODE_ME_CHECK(x.minus_v(home,rnq,false));
00597           }
00598           a.adjust();
00599         noadjust: ;
00600         }
00601         r.free();
00602       }
00603     }
00604 
00605     // Mark as no touched variable
00606     status.none();
00607     // Should not be in a failed state
00608     assert(!table.empty());
00609     // Subsume if there is at most one non-assigned variable
00610     return atmostone() ? home.ES_SUBSUMED(*this) : ES_FIX;
00611   }
00612 
00613   template<class View, class Table>
00614   ExecStatus
00615   PosCompact<View,Table>::advise(Space& home, Advisor& a0, const Delta& d) {
00616     CTAdvisor& a = static_cast<CTAdvisor&>(a0);
00617 
00618     // Do not fail a disabled propagator
00619     if (table.empty())
00620       return Compact<View,true>::disabled() ?
00621         home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
00622       
00623     View x = a.view();
00624       
00625     /* 
00626      * Do not schedule if propagator is performing propagation,
00627      * and dispose if assigned.
00628      */ 
00629     if (status.type() == StatusType::PROPAGATING)
00630       return x.assigned() ? home.ES_FIX_DISPOSE(c,a) : ES_FIX;
00631       
00632     // Update status
00633     status.touched(a);
00634       
00635     if (x.assigned()) {
00636       // Variable is assigned -- intersect with its value
00637       table.template intersect_with_mask<true>(supports(a,x.val()));
00638       return home.ES_NOFIX_DISPOSE(c,a);
00639     }
00640       
00641     if (!x.any(d) && (x.min(d) == x.max(d))) {
00642       table.nand_with_mask(supports(a,x.min(d)));
00643       a.adjust();
00644     } else if (!x.any(d) && (x.width(d) <= x.size())) {
00645       // Incremental update, using the removed values
00646       for (LostSupports ls(*this,a,x.min(d),x.max(d)); ls(); ++ls) {
00647         table.nand_with_mask(ls.supports());
00648         if (table.empty())
00649           return Compact<View,true>::disabled() ?
00650             home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
00651       }
00652       a.adjust();
00653     } else {
00654       a.adjust();
00655       // Reset-based update, using the values that are left
00656       if (x.size() == 2) {
00657         table.intersect_with_masks(supports(a,x.min()),
00658                                    supports(a,x.max()));
00659       } else {
00660         Region r;
00661         BitSetData* mask = r.alloc<BitSetData>(table.size());
00662         // Collect all tuples to be kept in a temporary mask
00663         table.clear_mask(mask);
00664         for (ValidSupports vs(*this,a); vs(); ++vs)
00665           table.add_to_mask(vs.supports(),mask);
00666         table.template intersect_with_mask<false>(mask);
00667       }
00668     }
00669 
00670     // Do not fail a disabled propagator
00671     if (table.empty())
00672       return Compact<View,true>::disabled() ?
00673         home.ES_NOFIX_DISPOSE(c,a) : ES_FAILED;
00674       
00675     // Schedule propagator
00676     return ES_NOFIX;
00677   }
00678 
00679 
00680   /*
00681    * Post function
00682    */
00683   template<class View>
00684   ExecStatus
00685   postposcompact(Home home, ViewArray<View>& x, const TupleSet& ts) {
00686     if (ts.tuples() == 0)
00687       return (x.size() == 0) ? ES_OK : ES_FAILED;
00688     
00689     // All variables pruned to correct domain
00690     for (int i=0; i<x.size(); i++) {
00691       TupleSet::Ranges r(ts,i);
00692       GECODE_ME_CHECK(x[i].inter_r(home, r, false));
00693     }
00694 
00695     if ((x.size() <= 1) || (ts.tuples() <= 1))
00696       return ES_OK;
00697 
00698     // Choose the right bit set implementation
00699     switch (ts.words()) {
00700     case 0U:
00701       GECODE_NEVER; return ES_OK;
00702     case 1U:
00703       return PosCompact<View,TinyBitSet<1U>>::post(home,x,ts);
00704     case 2U:
00705       return PosCompact<View,TinyBitSet<2U>>::post(home,x,ts);
00706     case 3U:
00707       return PosCompact<View,TinyBitSet<3U>>::post(home,x,ts);
00708     case 4U:
00709       return PosCompact<View,TinyBitSet<4U>>::post(home,x,ts);
00710     default:
00711       switch (Gecode::Support::u_type(ts.words())) {
00712       case Gecode::Support::IT_CHAR:
00713         return PosCompact<View,BitSet<unsigned char>>
00714           ::post(home,x,ts);
00715       case Gecode::Support::IT_SHRT:
00716         return PosCompact<View,BitSet<unsigned short int>>
00717           ::post(home,x,ts);
00718       case Gecode::Support::IT_INT:
00719         return PosCompact<View,BitSet<unsigned int>>
00720           ::post(home,x,ts);
00721       default: GECODE_NEVER;
00722       }
00723     }
00724     GECODE_NEVER;
00725     return ES_OK;
00726   }
00727 
00728   
00729   /*
00730    * The negative propagator
00731    *
00732    */
00733   template<class View, class Table>
00734   template<class TableProp>
00735   forceinline
00736   NegCompact<View,Table>::NegCompact(Space& home, TableProp& p)
00737     : Compact<View,false>(home,p), table(home,p.table) {
00738     assert(!table.empty());
00739   }
00740 
00741   template<class View, class Table>
00742   Actor*
00743   NegCompact<View,Table>::copy(Space& home) {
00744     assert((table.words() > 0U) && (table.width() >= table.words()));
00745     if (table.words() <= 4U) {
00746       switch (table.width()) {
00747       case 0U:
00748         GECODE_NEVER; break;
00749       case 1U:
00750         return new (home) NegCompact<View,TinyBitSet<1U>>(home,*this);
00751       case 2U:
00752         return new (home) NegCompact<View,TinyBitSet<2U>>(home,*this);
00753       case 3U:
00754         return new (home) NegCompact<View,TinyBitSet<3U>>(home,*this);
00755       case 4U:
00756         return new (home) NegCompact<View,TinyBitSet<4U>>(home,*this);
00757       default:
00758         break;
00759       }
00760     }
00761     if (std::is_same<Table,BitSet<unsigned char>>::value) {
00762       goto copy_char;
00763     } else if (std::is_same<Table,BitSet<unsigned short int>>::value) {
00764       switch (Gecode::Support::u_type(table.width())) {
00765       case Gecode::Support::IT_CHAR: goto copy_char;
00766       case Gecode::Support::IT_SHRT: goto copy_short;
00767       case Gecode::Support::IT_INT:  GECODE_NEVER;
00768       default:                       GECODE_NEVER;
00769       }
00770     } else {
00771       switch (Gecode::Support::u_type(table.width())) {
00772       case Gecode::Support::IT_CHAR: goto copy_char;
00773       case Gecode::Support::IT_SHRT: goto copy_short;
00774       case Gecode::Support::IT_INT:  goto copy_int;
00775       default: GECODE_NEVER;
00776       }
00777       GECODE_NEVER;
00778       return nullptr;
00779     }
00780   copy_char:
00781     return new (home) NegCompact<View,BitSet<unsigned char>>(home,*this);
00782   copy_short:
00783     return new (home) NegCompact<View,BitSet<unsigned short int>>(home,*this);
00784   copy_int:
00785     return new (home) NegCompact<View,BitSet<unsigned int>>(home,*this);
00786   }
00787 
00788   template<class View, class Table>
00789   forceinline
00790   NegCompact<View,Table>::NegCompact(Home home, ViewArray<View>& x,
00791                                      const TupleSet& ts)
00792     : Compact<View,false>(home,ts), table(home,ts.words()) {
00793     setup(home,table,x);
00794   }
00795       
00796   template<class View, class Table>
00797   forceinline ExecStatus
00798   NegCompact<View,Table>::post(Home home, ViewArray<View>& x,
00799                                const TupleSet& ts) {
00800     auto ct = new (home) NegCompact(home,x,ts);
00801     return ct->full(ct->table) ? ES_FAILED : ES_OK;
00802   }
00803 
00804   template<class View, class Table>
00805   forceinline size_t
00806   NegCompact<View,Table>::dispose(Space& home) {
00807     (void) Compact<View,false>::dispose(home);
00808     return sizeof(*this);
00809   }
00810 
00811   template<class View, class Table>
00812   void
00813   NegCompact<View,Table>::reschedule(Space& home) {
00814     View::schedule(home,*this,ME_INT_DOM);
00815   }
00816 
00817   template<class View, class Table>
00818   ExecStatus
00819   NegCompact<View,Table>::propagate(Space& home, const ModEventDelta&) {
00820 #ifndef NDEBUG
00821     if (!table.empty()) {
00822       // Check that all views have at least one value with support
00823       for (Advisors<CTAdvisor> as(c); as(); ++as) {
00824         ValidSupports vs(*this,as.advisor());
00825         assert(vs());
00826       }
00827     }
00828 #endif
00829 
00830     if (table.empty())
00831       return home.ES_SUBSUMED(*this);
00832 
00833     // Estimate whether any pruning will be possible
00834     unsigned long long int x_size = 1U;
00835     unsigned long long int x_max = 1U;
00836     /* The size of the Cartesian product will be x_size times x_max,
00837      * where x_max is the size of the largest variable domain.
00838      */
00839     for (Advisors<CTAdvisor> as(c); as(); ++as) {
00840       unsigned long long int n = as.advisor().view().size();
00841       if (n > x_max) {
00842         x_size *= x_max; x_max = n;
00843       } else {
00844         x_size *= n;
00845       }
00846       if (x_size > table.bits())
00847         return ES_FIX;
00848     }
00849     if (x_size > table.ones())
00850       return ES_FIX;
00851 
00852     {
00853       // Adjust to size of the Cartesian product
00854       x_size *= x_max;
00855       
00856       Region r;
00857 
00858       for (Advisors<CTAdvisor> as(c); as(); ++as) {
00859         assert(!table.empty());
00860         CTAdvisor& a = as.advisor();
00861         View x = a.view();
00862         
00863         // Adjust for the current variable domain
00864         x_size /= static_cast<unsigned long long int>(x.size());
00865         
00866         if ((x_size <= table.bits()) && (x_size <= table.ones())) {
00867           // How many values to remove
00868           int* nq = r.alloc<int>(x.size());
00869           unsigned int n_nq = 0U;
00870         
00871           for (ValidSupports vs(*this,a); vs(); ++vs)
00872             if (x_size == table.ones(vs.supports()))
00873               nq[n_nq++] = vs.val();
00874         
00875           // Remove collected values
00876           if (n_nq > 0U) {
00877             if (n_nq == 1U) {
00878               GECODE_ME_CHECK(x.nq(home,nq[0]));
00879             } else {
00880               Iter::Values::Array rnq(nq,n_nq);
00881               GECODE_ASSUME(n_nq >= 2U);
00882               GECODE_ME_CHECK(x.minus_v(home,rnq,false));
00883             }
00884             if (table.empty())
00885               return home.ES_SUBSUMED(*this);
00886             a.adjust();
00887           }
00888           r.free();
00889         }
00890         // Re-adjust size
00891         x_size *= static_cast<unsigned long long int>(x.size());
00892       }
00893     }
00894 
00895     if (table.ones() == x_size)
00896       return ES_FAILED;
00897     if (table.empty() || atmostone())
00898       return home.ES_SUBSUMED(*this);
00899     return ES_FIX;
00900   }
00901 
00902   template<class View, class Table>
00903   ExecStatus
00904   NegCompact<View,Table>::advise(Space& home, Advisor& a0, const Delta&) {
00905     CTAdvisor& a = static_cast<CTAdvisor&>(a0);
00906 
00907     // We are subsumed
00908     if (table.empty())
00909       return home.ES_NOFIX_DISPOSE(c,a);
00910       
00911     View x = a.view();
00912       
00913     a.adjust();
00914 
00915     if (x.assigned()) {
00916       // Variable is assigned -- intersect with its value
00917       if (const BitSetData* s = supports(a,x.val()))
00918         table.template intersect_with_mask<true>(s);
00919       else
00920         table.flush(); // Mark as subsumed
00921       return home.ES_NOFIX_DISPOSE(c,a);
00922     }
00923       
00924     {
00925       ValidSupports vs(*this,a);
00926       if (!vs()) {
00927         table.flush(); // Mark as subsumed
00928         return home.ES_NOFIX_DISPOSE(c,a);
00929       }
00930 
00931       Region r;
00932       BitSetData* mask = r.alloc<BitSetData>(table.size());
00933       // Collect all tuples to be kept in a temporary mask
00934       table.clear_mask(mask);
00935       do {
00936         table.add_to_mask(vs.supports(),mask);
00937         ++vs;
00938       } while (vs());
00939       table.template intersect_with_mask<false>(mask);
00940     }
00941     
00942     if (table.empty())
00943       return home.ES_NOFIX_DISPOSE(c,a);
00944     
00945     // Schedule propagator
00946     return ES_NOFIX;
00947   }
00948 
00949 
00950   /*
00951    * Post function
00952    */
00953   template<class View>
00954   ExecStatus
00955   postnegcompact(Home home, ViewArray<View>& x, const TupleSet& ts) {
00956     if (ts.tuples() == 0)
00957       return ES_OK;
00958 
00959     // Check whether a variable does not overlap with supported values
00960     for (int i=0; i<x.size(); i++) {
00961       TupleSet::Ranges rs(ts,i);
00962       ViewRanges<View> rx(x[i]);
00963       if (Iter::Ranges::disjoint(rs,rx))
00964         return ES_OK;
00965     }
00966 
00967     // Choose the right bit set implementation
00968     switch (ts.words()) {
00969     case 0U:
00970       GECODE_NEVER; return ES_OK;
00971     case 1U:
00972       return NegCompact<View,TinyBitSet<1U>>::post(home,x,ts);
00973     case 2U:
00974       return NegCompact<View,TinyBitSet<2U>>::post(home,x,ts);
00975     case 3U:
00976       return NegCompact<View,TinyBitSet<3U>>::post(home,x,ts);
00977     case 4U:
00978       return NegCompact<View,TinyBitSet<4U>>::post(home,x,ts);
00979     default:
00980       switch (Gecode::Support::u_type(ts.words())) {
00981       case Gecode::Support::IT_CHAR:
00982         return NegCompact<View,BitSet<unsigned char>>
00983           ::post(home,x,ts);
00984       case Gecode::Support::IT_SHRT:
00985         return NegCompact<View,BitSet<unsigned short int>>
00986           ::post(home,x,ts);
00987       case Gecode::Support::IT_INT:
00988         return NegCompact<View,BitSet<unsigned int>>
00989           ::post(home,x,ts);
00990       default: GECODE_NEVER;
00991       }
00992     }
00993     GECODE_NEVER;
00994     return ES_OK;
00995   }
00996 
00997 
00998   /*
00999    * The reified propagator
01000    *
01001    */
01002   template<class View, class Table, class CtrlView, ReifyMode rm>
01003   template<class TableProp>
01004   forceinline
01005   ReCompact<View,Table,CtrlView,rm>::ReCompact(Space& home, TableProp& p)
01006     : Compact<View,false>(home,p), table(home,p.table) {
01007     b.update(home,p.b);
01008     y.update(home,p.y);
01009     assert(!table.empty());
01010   }
01011 
01012   template<class View, class Table, class CtrlView, ReifyMode rm>
01013   Actor*
01014   ReCompact<View,Table,CtrlView,rm>::copy(Space& home) {
01015     assert((table.words() > 0U) && (table.width() >= table.words()));
01016     if (table.words() <= 4U) {
01017       switch (table.width()) {
01018       case 0U:
01019         GECODE_NEVER; break;
01020       case 1U:
01021         return new (home) ReCompact<View,TinyBitSet<1U>,CtrlView,rm>
01022           (home,*this);
01023       case 2U:
01024         return new (home) ReCompact<View,TinyBitSet<2U>,CtrlView,rm>
01025           (home,*this);
01026       case 3U:
01027         return new (home) ReCompact<View,TinyBitSet<3U>,CtrlView,rm>
01028           (home,*this);
01029       case 4U:
01030         return new (home) ReCompact<View,TinyBitSet<4U>,CtrlView,rm>
01031           (home,*this);
01032       default:
01033         break;
01034       }
01035     }
01036     if (std::is_same<Table,BitSet<unsigned char>>::value) {
01037       goto copy_char;
01038     } else if (std::is_same<Table,BitSet<unsigned short int>>::value) {
01039       switch (Gecode::Support::u_type(table.width())) {
01040       case Gecode::Support::IT_CHAR: goto copy_char;
01041       case Gecode::Support::IT_SHRT: goto copy_short;
01042       case Gecode::Support::IT_INT:  GECODE_NEVER;
01043       default:                       GECODE_NEVER;
01044       }
01045     } else {
01046       switch (Gecode::Support::u_type(table.width())) {
01047       case Gecode::Support::IT_CHAR: goto copy_char;
01048       case Gecode::Support::IT_SHRT: goto copy_short;
01049       case Gecode::Support::IT_INT:  goto copy_int;
01050       default: GECODE_NEVER;
01051       }
01052       GECODE_NEVER;
01053       return nullptr;
01054     }
01055   copy_char:
01056     return new (home) ReCompact<View,BitSet<unsigned char>,CtrlView,rm>
01057       (home,*this);
01058   copy_short:
01059     return new (home) ReCompact<View,BitSet<unsigned short int>,CtrlView,rm>
01060       (home,*this);
01061   copy_int:
01062     return new (home) ReCompact<View,BitSet<unsigned int>,CtrlView,rm>
01063       (home,*this);
01064   }
01065 
01066   template<class View, class Table, class CtrlView, ReifyMode rm>
01067   forceinline
01068   ReCompact<View,Table,CtrlView,rm>::ReCompact(Home home, ViewArray<View>& x,
01069                                                const TupleSet& ts, CtrlView b0)
01070     : Compact<View,false>(home,ts), table(home,ts.words()), b(b0), y(x) {
01071     b.subscribe(home,*this,PC_BOOL_VAL);
01072     setup(home,table,x);
01073   }
01074       
01075   template<class View, class Table, class CtrlView, ReifyMode rm>
01076   forceinline ExecStatus
01077   ReCompact<View,Table,CtrlView,rm>::post(Home home, ViewArray<View>& x,
01078                                           const TupleSet& ts, CtrlView b) {
01079     if (b.one()) {
01080       if (rm == RM_PMI)
01081         return ES_OK;
01082       return postposcompact(home,x,ts);
01083     }
01084     if (b.zero()) {
01085       if (rm == RM_IMP)
01086         return ES_OK;
01087       return postnegcompact(home,x,ts);
01088     }
01089     (void) new (home) ReCompact(home,x,ts,b);
01090     return ES_OK;
01091   }
01092 
01093   template<class View, class Table, class CtrlView, ReifyMode rm>
01094   forceinline size_t
01095   ReCompact<View,Table,CtrlView,rm>::dispose(Space& home) {
01096     b.cancel(home,*this,PC_BOOL_VAL);
01097     (void) Compact<View,false>::dispose(home);
01098     return sizeof(*this);
01099   }
01100 
01101   template<class View, class Table, class CtrlView, ReifyMode rm>
01102   void
01103   ReCompact<View,Table,CtrlView,rm>::reschedule(Space& home) {
01104     View::schedule(home,*this,ME_INT_DOM);
01105   }
01106 
01107   template<class View, class Table, class CtrlView, ReifyMode rm>
01108   ExecStatus
01109   ReCompact<View,Table,CtrlView,rm>::propagate(Space& home,
01110                                                const ModEventDelta&) {
01111     if (b.one()) {
01112       if (rm == RM_PMI)
01113         return home.ES_SUBSUMED(*this);
01114       TupleSet keep(ts);
01115       GECODE_REWRITE(*this,postposcompact(home(*this),y,keep));
01116     }
01117     if (b.zero()) {
01118       if (rm == RM_IMP)
01119         return home.ES_SUBSUMED(*this);
01120       TupleSet keep(ts);
01121       GECODE_REWRITE(*this,postnegcompact(home(*this),y,keep));
01122     }
01123 
01124     if (table.empty()) {
01125       if (rm != RM_PMI)
01126         GECODE_ME_CHECK(b.zero_none(home));
01127       return home.ES_SUBSUMED(*this);
01128     }
01129     if (full(table)) {
01130       if (rm != RM_IMP)
01131         GECODE_ME_CHECK(b.one_none(home));
01132       return home.ES_SUBSUMED(*this);
01133     }      
01134 
01135     return ES_FIX;
01136   }
01137 
01138   template<class View, class Table, class CtrlView, ReifyMode rm>
01139   ExecStatus
01140   ReCompact<View,Table,CtrlView,rm>::advise(Space& home,
01141                                             Advisor& a0, const Delta&) {
01142     CTAdvisor& a = static_cast<CTAdvisor&>(a0);
01143 
01144     // We are subsumed
01145     if (table.empty() || b.assigned())
01146       return home.ES_NOFIX_DISPOSE(c,a);
01147       
01148     View x = a.view();
01149       
01150     a.adjust();
01151     
01152     if (x.assigned()) {
01153       // Variable is assigned -- intersect with its value
01154       if (const BitSetData* s = supports(a,x.val()))
01155         table.template intersect_with_mask<true>(s);
01156       else
01157         table.flush(); // Mark as failed
01158       return home.ES_NOFIX_DISPOSE(c,a);
01159     }
01160       
01161     {
01162       ValidSupports vs(*this,a);
01163       if (!vs()) {
01164         table.flush(); // Mark as failed
01165         return home.ES_NOFIX_DISPOSE(c,a);
01166       }
01167 
01168       Region r;
01169       BitSetData* mask = r.alloc<BitSetData>(table.size());
01170       // Collect all tuples to be kept in a temporary mask
01171       table.clear_mask(mask);
01172       do {
01173         table.add_to_mask(vs.supports(),mask);
01174         ++vs;
01175       } while (vs());
01176       table.template intersect_with_mask<false>(mask);
01177     }
01178     
01179     if (table.empty())
01180       return home.ES_NOFIX_DISPOSE(c,a);
01181     
01182     // Schedule propagator
01183     return ES_NOFIX;
01184   }
01185 
01186 
01187   /*
01188    * Post function
01189    */
01190   template<class View, class CtrlView, ReifyMode rm>
01191   ExecStatus
01192   postrecompact(Home home, ViewArray<View>& x, const TupleSet& ts,
01193                 CtrlView b) {
01194     // Enforce invariant that there is at least one tuple...
01195     if (ts.tuples() == 0) {
01196       if (x.size() != 0) {
01197         if (rm != RM_PMI)
01198           GECODE_ME_CHECK(b.zero(home));
01199       } else {
01200         if (rm != RM_IMP)
01201           GECODE_ME_CHECK(b.one(home));
01202       }
01203       return ES_OK;
01204     }
01205     // Check whether a variable does not overlap with supported values
01206     for (int i=0; i<x.size(); i++) {
01207       TupleSet::Ranges rs(ts,i);
01208       ViewRanges<View> rx(x[i]);
01209       if (Iter::Ranges::disjoint(rs,rx)) {
01210         if (rm != RM_PMI)
01211           GECODE_ME_CHECK(b.zero(home));
01212         return ES_OK;
01213       }
01214     }
01215     // Choose the right bit set implementation
01216     switch (ts.words()) {
01217     case 0U:
01218       GECODE_NEVER; return ES_OK;
01219     case 1U:
01220       return ReCompact<View,TinyBitSet<1U>,CtrlView,rm>::post(home,x,ts,b);
01221     case 2U:
01222       return ReCompact<View,TinyBitSet<2U>,CtrlView,rm>::post(home,x,ts,b);
01223     case 3U:
01224       return ReCompact<View,TinyBitSet<3U>,CtrlView,rm>::post(home,x,ts,b);
01225     case 4U:
01226       return ReCompact<View,TinyBitSet<4U>,CtrlView,rm>::post(home,x,ts,b);
01227     default:
01228       switch (Gecode::Support::u_type(ts.words())) {
01229       case Gecode::Support::IT_CHAR:
01230         return ReCompact<View,BitSet<unsigned char>,CtrlView,rm>
01231           ::post(home,x,ts,b);
01232       case Gecode::Support::IT_SHRT:
01233         return ReCompact<View,BitSet<unsigned short int>,CtrlView,rm>
01234           ::post(home,x,ts,b);
01235       case Gecode::Support::IT_INT:
01236         return ReCompact<View,BitSet<unsigned int>,CtrlView,rm>
01237           ::post(home,x,ts,b);
01238       default: GECODE_NEVER;
01239       }
01240     }
01241     GECODE_NEVER;
01242     return ES_OK;
01243   }
01244 
01245 }}}
01246 
01247 // STATISTICS: int-prop