Generated on Thu Apr 11 13:59:00 2019 for Gecode by doxygen 1.6.3

lq-le.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Gabor Szokoli <szokoli@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2003
00009  *     Gabor Szokoli, 2003
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 namespace Gecode { namespace Int { namespace Rel {
00037 
00038   /*
00039    * Less or equal propagator
00040    *
00041    */
00042 
00043   template<class V0, class V1>
00044   forceinline
00045   Lq<V0,V1>::Lq(Home home, V0 x0, V1 x1)
00046     : MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>(home,x0,x1) {}
00047 
00048   template<class V0, class V1>
00049   ExecStatus
00050   Lq<V0,V1>::post(Home home, V0 x0, V1 x1) {
00051     GECODE_ME_CHECK(x0.lq(home,x1.max()));
00052     GECODE_ME_CHECK(x1.gq(home,x0.min()));
00053     if ((x0 != x1) && (x0.max() > x1.min()))
00054       (void) new (home) Lq<V0,V1>(home,x0,x1);
00055     return ES_OK;
00056   }
00057 
00058   template<class V0, class V1>
00059   forceinline
00060   Lq<V0,V1>::Lq(Space& home, Lq<V0,V1>& p)
00061     : MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>(home,p) {}
00062 
00063   template<class V0, class V1>
00064   Actor*
00065   Lq<V0,V1>::copy(Space& home) {
00066     return new (home) Lq<V0,V1>(home,*this);
00067   }
00068 
00069   template<class V0, class V1>
00070   ExecStatus
00071   Lq<V0,V1>::propagate(Space& home, const ModEventDelta&) {
00072     GECODE_ME_CHECK(x0.lq(home,x1.max()));
00073     GECODE_ME_CHECK(x1.gq(home,x0.min()));
00074     return (x0.max() <= x1.min()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00075   }
00076 
00077 
00078 
00079 
00080   /*
00081    * Less propagator
00082    *
00083    */
00084   template<class V0, class V1>
00085   forceinline
00086   Le<V0,V1>::Le(Home home, V0 x0, V1 x1)
00087     : MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>(home,x0,x1) {}
00088 
00089   template<class V0, class V1>
00090   ExecStatus
00091   Le<V0,V1>::post(Home home, V0 x0, V1 x1) {
00092     if (x0 == x1)
00093       return ES_FAILED;
00094     GECODE_ME_CHECK(x0.le(home,x1.max()));
00095     GECODE_ME_CHECK(x1.gr(home,x0.min()));
00096     if (x0.max() >= x1.min())
00097       (void) new (home) Le<V0,V1>(home,x0,x1);
00098     return ES_OK;
00099   }
00100 
00101   template<class V0, class V1>
00102   forceinline
00103   Le<V0,V1>::Le(Space& home, Le<V0,V1>& p)
00104     : MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>(home,p) {}
00105 
00106   template<class V0, class V1>
00107   Actor*
00108   Le<V0,V1>::copy(Space& home) {
00109     return new (home) Le<V0,V1>(home,*this);
00110   }
00111 
00112   template<class V0, class V1>
00113   ExecStatus
00114   Le<V0,V1>::propagate(Space& home, const ModEventDelta&) {
00115     GECODE_ME_CHECK(x0.le(home,x1.max()));
00116     GECODE_ME_CHECK(x1.gr(home,x0.min()));
00117     return (x0.max() < x1.min()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00118   }
00119 
00120 
00121 
00122   /*
00123    * Nary less and less or equal propagator
00124    *
00125    */
00126 
00127   template<class View, int o>
00128   forceinline
00129   NaryLqLe<View,o>::Index::Index(Space& home, Propagator& p,
00130                                  Council<Index>& c, int i0)
00131     : Advisor(home,p,c), i(i0) {}
00132 
00133   template<class View, int o>
00134   forceinline
00135   NaryLqLe<View,o>::Index::Index(Space& home, Index& a)
00136     : Advisor(home,a), i(a.i) {}
00137 
00138 
00139 
00140   template<class View, int o>
00141   forceinline
00142   NaryLqLe<View,o>::Pos::Pos(int p0, Pos* n)
00143     : FreeList(n), p(p0) {}
00144 
00145   template<class View, int o>
00146   forceinline typename NaryLqLe<View,o>::Pos*
00147   NaryLqLe<View,o>::Pos::next(void) const {
00148     return static_cast<Pos*>(FreeList::next());
00149   }
00150 
00151   template<class View, int o>
00152   forceinline void
00153   NaryLqLe<View,o>::Pos::operator delete(void*) {}
00154 
00155   template<class View, int o>
00156   forceinline void
00157   NaryLqLe<View,o>::Pos::operator delete(void*, Space&) {
00158     GECODE_NEVER;
00159   }
00160 
00161   template<class View, int o>
00162   forceinline void*
00163   NaryLqLe<View,o>::Pos::operator new(size_t, Space& home) {
00164     return home.fl_alloc<sizeof(Pos)>();
00165   }
00166 
00167   template<class View, int o>
00168   forceinline void
00169   NaryLqLe<View,o>::Pos::dispose(Space& home) {
00170     home.fl_dispose<sizeof(Pos)>(this,this);
00171   }
00172 
00173 
00174   template<class View, int o>
00175   forceinline bool
00176   NaryLqLe<View,o>::empty(void) const {
00177     return pos == NULL;
00178   }
00179   template<class View, int o>
00180   forceinline void
00181   NaryLqLe<View,o>::push(Space& home, int p) {
00182     // Try to avoid entering same position twice
00183     if ((pos != NULL) && (pos->p == p))
00184       return;
00185     pos = new (home) Pos(p,pos);
00186   }
00187   template<class View, int o>
00188   forceinline int
00189   NaryLqLe<View,o>::pop(Space& home) {
00190     Pos* t = pos;
00191     int p = t->p;
00192     pos = pos->next();
00193     t->dispose(home);
00194     return p;
00195   }
00196 
00197   template<class View, int o>
00198   forceinline
00199   NaryLqLe<View,o>::NaryLqLe(Home home, ViewArray<View>& x)
00200     : NaryPropagator<View,PC_INT_NONE>(home,x),
00201       c(home), pos(NULL), run(false), n_subsumed(0) {
00202     for (int i=0; i<x.size(); i++)
00203       x[i].subscribe(home, *new (home) Index(home,*this,c,i));
00204   }
00205 
00206   template<class View, int o>
00207   ExecStatus
00208   NaryLqLe<View,o>::post(Home home, ViewArray<View>& x) {
00209     assert((o == 0) || (o == 1));
00210     // Check for sharing
00211     if (x.same()) {
00212       if (o == 1)
00213         return ES_FAILED;
00214       /*
00215        * Eliminate sharing: if a view occurs twice, all views in between
00216        * must be equal.
00217        */
00218       int n = x.size();
00219       for (int i=0; i<n; i++)
00220         for (int j=n-1; j>i; j--)
00221           if (x[i] == x[j]) {
00222             if (i+1 != j) {
00223               // Create equality propagator for elements i+1 ... j
00224               ViewArray<View> y(home,j-i);
00225               for (int k=j-i; k--; )
00226                 y[k] = x[i+1+k];
00227               GECODE_ES_CHECK(NaryEqBnd<View>::post(home,y));
00228             }
00229             for (int k=0; k<n-1-j-1+1; k++)
00230               x[i+1+k]=x[j+1+k];
00231             n -= j-i;
00232             break;
00233           }
00234       x.size(n);
00235     }
00236 
00237     // Propagate one round
00238     for (int i=1; i<x.size(); i++)
00239       GECODE_ME_CHECK(x[i].gq(home,x[i-1].min()+o));
00240     for (int i=x.size()-1; i--;)
00241       GECODE_ME_CHECK(x[i].lq(home,x[i+1].max()-o));
00242     // Eliminate redundant variables
00243     {
00244       // Eliminate at beginning
00245       {
00246         int i=0;
00247         while ((i+1 < x.size()) && (x[i].max()+o <= x[i+1].min()))
00248           i++;
00249         x.drop_fst(i);
00250       }
00251       // Eliminate at end
00252       {
00253         int i=x.size()-1;
00254         while ((i > 0) && (x[i-1].max()+o <= x[i].min()))
00255           i--;
00256         x.drop_lst(i);
00257       }
00258       // Eliminate in the middle
00259       if (x.size() > 1) {
00260         int j=1;
00261         for (int i=1; i+1<x.size(); i++)
00262           if ((x[j-1].max()+o > x[i].min()) ||
00263               (x[i].max()+o > x[i+1].min()))
00264             x[j++]=x[i];
00265         x[j++]=x[x.size()-1];
00266         x.size(j);
00267       }
00268     }
00269     if (x.size() == 2) {
00270       if (o == 0)
00271         return Lq<View,View>::post(home,x[0],x[1]);
00272       else
00273         return Le<View,View>::post(home,x[0],x[1]);
00274     } else if (x.size() >= 2) {
00275       (void) new (home) NaryLqLe<View,o>(home,x);
00276     }
00277     return ES_OK;
00278   }
00279 
00280   template<class View, int o>
00281   forceinline
00282   NaryLqLe<View,o>::NaryLqLe(Space& home, NaryLqLe<View,o>& p)
00283     : NaryPropagator<View,PC_INT_NONE>(home,p),
00284       pos(NULL), run(false), n_subsumed(p.n_subsumed) {
00285     assert(p.pos == NULL);
00286     c.update(home, p.c);
00287   }
00288 
00289   template<class View, int o>
00290   Actor*
00291   NaryLqLe<View,o>::copy(Space& home) {
00292     if (n_subsumed > n_threshold) {
00293       Region r;
00294       // Record for which views there is an advisor
00295       Support::BitSet<Region> a(r,static_cast<unsigned int>(x.size()));
00296       for (Advisors<Index> as(c); as(); ++as)
00297         a.set(static_cast<unsigned int>(as.advisor().i));
00298       // Compact view array and compute map for advisors
00299       int* m = r.alloc<int>(x.size());
00300       int j=0;
00301       for (int i=0; i<x.size(); i++)
00302         if (a.get(static_cast<unsigned int>(i))) {
00303           m[i] = j; x[j++] = x[i];
00304         }
00305       x.size(j);
00306       // Remap advisors
00307       for (Advisors<Index> as(c); as(); ++as)
00308         as.advisor().i = m[as.advisor().i];
00309 
00310       n_subsumed = 0;
00311     }
00312     return new (home) NaryLqLe<View,o>(home,*this);
00313   }
00314 
00315   template<class View, int o>
00316   PropCost
00317   NaryLqLe<View,o>::cost(const Space&, const ModEventDelta&) const {
00318     return PropCost::binary(PropCost::HI);
00319   }
00320 
00321   template<class View, int o>
00322   forceinline size_t
00323   NaryLqLe<View,o>::dispose(Space& home) {
00324     for (Advisors<Index> as(c); as(); ++as)
00325       x[as.advisor().i].cancel(home,as.advisor());
00326     c.dispose(home);
00327     while (!empty())
00328       (void) pop(home);
00329     (void) NaryPropagator<View,PC_INT_NONE>::dispose(home);
00330     return sizeof(*this);
00331   }
00332 
00333 
00334   template<class View, int o>
00335   ExecStatus
00336   NaryLqLe<View,o>::advise(Space& home, Advisor& _a, const Delta& d) {
00337     Index& a = static_cast<Index&>(_a);
00338     const int i = a.i;
00339     switch (View::modevent(d)) {
00340     case ME_INT_VAL:
00341       a.dispose(home,c);
00342       n_subsumed++;
00343       break;
00344     case ME_INT_BND:
00345       if (((i == 0) || (x[i-1].max()+o <= x[i].min())) &&
00346           ((i == x.size()-1) || (x[i].max()+o <= x[i+1].min()))) {
00347         x[i].cancel(home,a);
00348         a.dispose(home,c);
00349         n_subsumed++;
00350         return (run || (n_subsumed + 1 < x.size())) ? ES_FIX : ES_NOFIX;
00351       }
00352       break;
00353     default:
00354       return ES_FIX;
00355     }
00356     if (run)
00357       return ES_FIX;
00358     if (((i < x.size()-1) && (x[i+1].min() < x[i].min()+o)) ||
00359         ((i > 0) && (x[i-1].max() > x[i].max()-o))) {
00360       push(home,i);
00361       return ES_NOFIX;
00362     }
00363     return (n_subsumed+1 >= x.size()) ? ES_NOFIX : ES_FIX;
00364   }
00365 
00366   template<class View, int o>
00367   void
00368   NaryLqLe<View,o>::reschedule(Space& home) {
00369     View::schedule(home, *this, ME_INT_BND);
00370   }
00371 
00372   template<class View, int o>
00373   ExecStatus
00374   NaryLqLe<View,o>::propagate(Space& home, const ModEventDelta&) {
00375     run = true;
00376     int n = x.size();
00377     while (!empty()) {
00378       int p = pop(home);
00379       for (int i=p; i<n-1; i++) {
00380         ModEvent me = x[i+1].gq(home,x[i].min()+o);
00381         if (me_failed(me))
00382           return ES_FAILED;
00383         if (!me_modified(me))
00384           break;
00385       }
00386       for (int i=p; i>0; i--) {
00387         ModEvent me = x[i-1].lq(home,x[i].max()-o);
00388         if (me_failed(me))
00389           return ES_FAILED;
00390         if (!me_modified(me))
00391           break;
00392       }
00393     }
00394 #ifdef GECODE_AUDIT
00395     for (int i=0; i<n-1; i++)
00396       assert(!me_modified(x[i+1].gq(home,x[i].min()+o)));
00397     for (int i=n-1; i>0; i--)
00398       assert(!me_modified(x[i-1].lq(home,x[i].max()-o)));
00399 #endif
00400     if (n_subsumed+1 >= n)
00401       return home.ES_SUBSUMED(*this);
00402     run = false;
00403     return ES_FIX;
00404   }
00405 
00406 
00407 
00408   /*
00409    * Reified less or equal propagator
00410    *
00411    */
00412 
00413   template<class View, class CtrlView, ReifyMode rm>
00414   forceinline
00415   ReLq<View,CtrlView,rm>::ReLq(Home home, View x0, View x1, CtrlView b)
00416     : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,x0,x1,b) {}
00417 
00418   template<class View, class CtrlView, ReifyMode rm>
00419   ExecStatus
00420   ReLq<View,CtrlView,rm>::post(Home home, View x0, View x1, CtrlView b) {
00421     if (b.one()) {
00422       if (rm == RM_PMI)
00423         return ES_OK;
00424       return Lq<View,View>::post(home,x0,x1);
00425     }
00426     if (b.zero()) {
00427       if (rm == RM_IMP)
00428         return ES_OK;
00429       return Le<View,View>::post(home,x1,x0);
00430     }
00431     if (x0 != x1) {
00432       switch (rtest_lq(x0,x1)) {
00433       case RT_TRUE:
00434         if (rm != RM_IMP)
00435           GECODE_ME_CHECK(b.one_none(home));
00436         break;
00437       case RT_FALSE:
00438         if (rm != RM_PMI)
00439           GECODE_ME_CHECK(b.zero_none(home));
00440         break;
00441       case RT_MAYBE:
00442         (void) new (home) ReLq<View,CtrlView,rm>(home,x0,x1,b);
00443         break;
00444       default: GECODE_NEVER;
00445       }
00446     } else if (rm != RM_IMP) {
00447       GECODE_ME_CHECK(b.one_none(home));
00448     }
00449     return ES_OK;
00450   }
00451 
00452   template<class View, class CtrlView, ReifyMode rm>
00453   forceinline
00454   ReLq<View,CtrlView,rm>::ReLq(Space& home, ReLq& p)
00455     : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,p) {}
00456 
00457   template<class View, class CtrlView, ReifyMode rm>
00458   Actor*
00459   ReLq<View,CtrlView,rm>::copy(Space& home) {
00460     return new (home) ReLq<View,CtrlView,rm>(home,*this);
00461   }
00462 
00463   template<class View, class CtrlView, ReifyMode rm>
00464   ExecStatus
00465   ReLq<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
00466     if (b.one()) {
00467       if (rm != RM_PMI)
00468         GECODE_REWRITE(*this,(Lq<View,View>::post(home(*this),x0,x1)));
00469     } else if (b.zero()) {
00470       if (rm != RM_IMP)
00471         GECODE_REWRITE(*this,(Le<View,View>::post(home(*this),x1,x0)));
00472     } else {
00473       switch (rtest_lq(x0,x1)) {
00474       case RT_TRUE:
00475         if (rm != RM_IMP)
00476           GECODE_ME_CHECK(b.one_none(home));
00477         break;
00478       case RT_FALSE:
00479         if (rm != RM_PMI)
00480           GECODE_ME_CHECK(b.zero_none(home));
00481         break;
00482       case RT_MAYBE:
00483         return ES_FIX;
00484       default: GECODE_NEVER;
00485       }
00486     }
00487     return home.ES_SUBSUMED(*this);
00488   }
00489 
00490   /*
00491    * Reified less or equal propagator involving one variable
00492    *
00493    */
00494 
00495   template<class View, class CtrlView, ReifyMode rm>
00496   forceinline
00497   ReLqInt<View,CtrlView,rm>::ReLqInt(Home home, View x, int c0, CtrlView b)
00498     : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,x,b), c(c0) {}
00499 
00500   template<class View, class CtrlView, ReifyMode rm>
00501   ExecStatus
00502   ReLqInt<View,CtrlView,rm>::post(Home home, View x, int c, CtrlView b) {
00503     if (b.one()) {
00504       if (rm != RM_PMI)
00505         GECODE_ME_CHECK(x.lq(home,c));
00506     } else if (b.zero()) {
00507       if (rm != RM_IMP)
00508         GECODE_ME_CHECK(x.gr(home,c));
00509     } else {
00510       switch (rtest_lq(x,c)) {
00511       case RT_TRUE:
00512         if (rm != RM_IMP)
00513           GECODE_ME_CHECK(b.one_none(home));
00514         break;
00515       case RT_FALSE:
00516         if (rm != RM_PMI)
00517           GECODE_ME_CHECK(b.zero_none(home));
00518         break;
00519       case RT_MAYBE:
00520         (void) new (home) ReLqInt<View,CtrlView,rm>(home,x,c,b);
00521         break;
00522       default: GECODE_NEVER;
00523       }
00524     }
00525     return ES_OK;
00526   }
00527 
00528 
00529   template<class View, class CtrlView, ReifyMode rm>
00530   forceinline
00531   ReLqInt<View,CtrlView,rm>::ReLqInt(Space& home, ReLqInt& p)
00532     : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,p), c(p.c) {}
00533 
00534   template<class View, class CtrlView, ReifyMode rm>
00535   Actor*
00536   ReLqInt<View,CtrlView,rm>::copy(Space& home) {
00537     return new (home) ReLqInt<View,CtrlView,rm>(home,*this);
00538   }
00539 
00540   template<class View, class CtrlView, ReifyMode rm>
00541   ExecStatus
00542   ReLqInt<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
00543     if (b.one()) {
00544       if (rm != RM_PMI)
00545         GECODE_ME_CHECK(x0.lq(home,c));
00546     } else if (b.zero()) {
00547       if (rm != RM_IMP)
00548         GECODE_ME_CHECK(x0.gr(home,c));
00549     } else {
00550       switch (rtest_lq(x0,c)) {
00551       case RT_TRUE:
00552         if (rm != RM_IMP)
00553           GECODE_ME_CHECK(b.one_none(home));
00554         break;
00555       case RT_FALSE:
00556         if (rm != RM_PMI)
00557           GECODE_ME_CHECK(b.zero_none(home));
00558         break;
00559       case RT_MAYBE:
00560         return ES_FIX;
00561       default: GECODE_NEVER;
00562       }
00563     }
00564     return home.ES_SUBSUMED(*this);
00565   }
00566 
00567 }}}
00568 
00569 // STATISTICS: int-prop
00570