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

inter.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Gabor Szokoli <szokoli@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Guido Tack, 2004
00012  *     Christian Schulte, 2004
00013  *     Gabor Szokoli, 2004
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 namespace Gecode { namespace Set { namespace RelOp {
00041 
00042   /*
00043    * "Ternary intersection" propagator
00044    *
00045    */
00046 
00047   template<class View0, class View1, class View2> ExecStatus
00048   Intersection<View0,View1,View2>::post(Home home,
00049                                         View0 x0,View1 x1,View2 x2) {
00050     (void) new (home) Intersection<View0,View1,View2>(home,x0,x1,x2);
00051     return ES_OK;
00052   }
00053 
00054   template<class View0, class View1, class View2>
00055   Actor*
00056   Intersection<View0,View1,View2>::copy(Space& home) {
00057     return new (home) Intersection(home,*this);
00058   }
00059 
00060   template<class View0, class View1, class View2>
00061   ExecStatus
00062   Intersection<View0,View1,View2>::propagate(Space& home, const ModEventDelta& med) {
00063     // This propagator implements the constraint
00064     // x2 = x0 \cap x1
00065 
00066     bool x0ass = x0.assigned();
00067     bool x1ass = x1.assigned();
00068     bool x2ass = x2.assigned();
00069 
00070     ModEvent me0 = View0::me(med);
00071     ModEvent me1 = View1::me(med);
00072     ModEvent me2 = View2::me(med);
00073 
00074     bool x0lbmod = false;
00075     bool x1lbmod = false;
00076     bool modified = false;
00077 
00078     do {
00079 
00080       modified = false;
00081       do {
00082         // 4) glb(x2) <= glb(x0) \cap glb(x1)
00083         {
00084           GlbRanges<View0> x0lb(x0);
00085           GlbRanges<View1> x1lb(x1);
00086           Iter::Ranges::Inter<GlbRanges<View0>, GlbRanges<View1> >
00087             i2(x0lb,x1lb);
00088           GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,i2) );
00089         }
00090 
00091         if (modified || Rel::testSetEventLB(me2) )
00092           {
00093             modified = false;
00094             // 5) x2 <= x0
00095             GlbRanges<View2> x2lb1(x2);
00096             GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,x2lb1) );
00097             x0lbmod |= modified;
00098 
00099             // 6) x2 <= x1
00100             bool modified2=false;
00101             GlbRanges<View2> x2lb2(x2);
00102             GECODE_ME_CHECK_MODIFIED(modified2, x1.includeI(home,x2lb2) );
00103             x1lbmod |= modified2;
00104             modified |= modified2;
00105           }
00106 
00107       } while (modified);
00108 
00109       modified = false;
00110       do {
00111         bool modifiedOld = modified;
00112         modified = false;
00113 
00114         if (Rel::testSetEventUB(me2) || Rel::testSetEventLB(me0)
00115              || x0lbmod || modifiedOld)
00116           {
00117             // 1) lub(x2) \ glb(x0) => lub(x1)
00118             GlbRanges<View0> x0lb(x0);
00119             LubRanges<View2> x2ub(x2);
00120             Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View2> >
00121               diff(x0lb, x2ub);
00122             GECODE_ME_CHECK_MODIFIED(modified, x1.excludeI(home,diff) );
00123           }
00124 
00125         if (Rel::testSetEventUB(me2) || Rel::testSetEventLB(me1)
00126             || x1lbmod || modifiedOld)
00127           {
00128             // 2) lub(x2) \ glb(x1) => lub(x0)
00129             GlbRanges<View1> x1lb(x1);
00130             LubRanges<View2> x2ub(x2);
00131             Iter::Ranges::Diff<GlbRanges<View1>, LubRanges<View2> >
00132               diff(x1lb, x2ub);
00133             GECODE_ME_CHECK_MODIFIED(modified, x0.excludeI(home,diff) );
00134           }
00135 
00136          if (Rel::testSetEventUB(me0,me1) || modified)
00137           {
00138             //            modified = false;
00139             // 3) lub(x0) \cap lub(x1) <= lub(x2)
00140             LubRanges<View0> x0ub(x0);
00141             LubRanges<View1> x1ub(x1);
00142             Iter::Ranges::Inter<LubRanges<View0>, LubRanges<View1> >
00143               i1(x0ub,x1ub);
00144             GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,i1) );
00145           }
00146 
00147       } while(modified);
00148 
00149       modified = false;
00150       {
00151         // cardinality
00152         ExecStatus ret = interCard(home,modified, x0, x1, x2);
00153         GECODE_ES_CHECK(ret);
00154       }
00155 
00156       if (x2.cardMin() == Set::Limits::card) {
00157         GECODE_ME_CHECK( x0.cardMin(home, Set::Limits::card) );
00158         GECODE_ME_CHECK( x1.cardMin(home, Set::Limits::card) );
00159         return home.ES_SUBSUMED(*this);
00160       }
00161 
00162       if (x0.cardMin() == Set::Limits::card)
00163         GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2)));
00164       if (x1.cardMin() == Set::Limits::card)
00165         GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2)));
00166 
00167     } while(modified);
00168 
00169     if (shared(x0,x1,x2)) {
00170       return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00171     } else {
00172       if (x0ass && x1ass && x2ass)
00173         return home.ES_SUBSUMED(*this);
00174       if (x0ass != x0.assigned() ||
00175           x1ass != x1.assigned() ||
00176           x2ass != x2.assigned()) {
00177         return ES_NOFIX;
00178       } else {
00179          return ES_FIX;
00180       }
00181     }
00182   }
00183 
00184   template<class View0, class View1, class View2>
00185   forceinline
00186   Intersection<View0,View1,View2>::Intersection(Home home,
00187                                              View0 y0,View1 y1,View2 y2)
00188     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00189                              View2,PC_SET_ANY>(home,y0,y1,y2) {}
00190 
00191   template<class View0, class View1, class View2>
00192   forceinline
00193   Intersection<View0,View1,View2>::Intersection(Space& home,
00194                                              Intersection<View0,View1,View2>& p)
00195     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00196                              View2,PC_SET_ANY>(home,p) {}
00197 
00198   /*
00199    * "Nary intersection" propagator
00200    *
00201    */
00202 
00203   template<class View0, class View1>
00204   forceinline
00205   IntersectionN<View0,View1>::IntersectionN(Home home, ViewArray<View0>& x,
00206                                             View1 y)
00207     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00208       intOfDets(home) {
00209     shared = Gecode::shared(x) || viewarrayshared(x,y);
00210   }
00211 
00212   template<class View0, class View1>
00213   forceinline
00214   IntersectionN<View0,View1>::IntersectionN(Home home, ViewArray<View0>& x,
00215                                             const IntSet& z, View1 y)
00216     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00217       intOfDets(home) {
00218     shared = Gecode::shared(x) || viewarrayshared(x,y);
00219     IntSetRanges rz(z);
00220     intOfDets.intersectI(home, rz);
00221   }
00222 
00223   template<class View0, class View1>
00224   forceinline
00225   IntersectionN<View0,View1>::IntersectionN(Space& home,
00226                                             IntersectionN& p)
00227     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p),
00228       shared(p.shared),
00229       intOfDets() {
00230     intOfDets.update(home, p.intOfDets);
00231   }
00232 
00233   template<class View0, class View1>
00234   ExecStatus
00235   IntersectionN<View0,View1>::post(Home home,
00236                                    ViewArray<View0>& x, View1 y) {
00237     switch (x.size()) {
00238     case 0:
00239       GECODE_ME_CHECK(y.cardMin(home, Limits::card));
00240       return ES_OK;
00241     case 1:
00242       return Rel::Eq<View0,View1>::post(home, x[0], y);
00243     case 2:
00244       return Intersection<View0,View0,View1>::post(home, x[0], x[1], y);
00245     default:
00246       (void) new (home) IntersectionN<View0,View1>(home,x,y);
00247       return ES_OK;
00248     }
00249   }
00250 
00251   template<class View0, class View1>
00252   ExecStatus
00253   IntersectionN<View0,View1>::post(Home home, ViewArray<View0>& x,
00254                                    const IntSet& z, View1 y) {
00255     (void) new (home) IntersectionN<View0,View1>(home,x,z,y);
00256     return ES_OK;
00257   }
00258 
00259   template<class View0, class View1>
00260   Actor*
00261   IntersectionN<View0,View1>::copy(Space& home) {
00262     return new (home) IntersectionN<View0,View1>(home,*this);
00263   }
00264 
00265   template<class View0, class View1>
00266   PropCost
00267   IntersectionN<View0,View1>::cost(const Space&, const ModEventDelta&) const {
00268     return PropCost::quadratic(PropCost::HI, x.size()+1);
00269   }
00270 
00271   template<class View0, class View1>
00272   ExecStatus
00273   IntersectionN<View0,View1>::propagate(Space& home, const ModEventDelta&) {
00274     bool repeat = false;
00275     do {
00276       repeat = false;
00277       int xsize = x.size();
00278       if (xsize == 0)
00279         goto size0;
00280       for (int i = xsize; i--; ) {
00281         GECODE_ME_CHECK( y.cardMax(home,x[i].cardMax()) );
00282         GECODE_ME_CHECK( x[i].cardMin(home,y.cardMin()) );
00283         if (x[i].cardMax()==0) {
00284           GECODE_ME_CHECK( y.cardMax(home, 0));
00285           intOfDets.dispose(home);
00286           return home.ES_SUBSUMED(*this);
00287         }
00288       }
00289       {
00290         Region r;
00291         GlbRanges<View0>* xLBs = r.alloc<GlbRanges<View0> >(xsize);
00292         LubRanges<View0>* xUBs = r.alloc<LubRanges<View0> >(xsize);
00293         for (int i = xsize; i--; ) {
00294           GlbRanges<View0> lb(x[i]);
00295           LubRanges<View0> ub(x[i]);
00296           xLBs[i]=lb;
00297           xUBs[i]=ub;
00298         }
00299         {
00300           Iter::Ranges::NaryInter lbi(r,xLBs,xsize);
00301           BndSetRanges dets(intOfDets);
00302           lbi &= dets;
00303           GECODE_ME_CHECK(y.includeI(home,lbi));
00304         }
00305         {
00306           Iter::Ranges::NaryInter ubi(r,xUBs,xsize);
00307           BndSetRanges dets(intOfDets);
00308           ubi &= dets;
00309           GECODE_ME_CHECK(y.intersectI(home,ubi));
00310         }
00311       }
00312 
00313       for (int i = xsize; i--; ) {
00314         GlbRanges<View1> ylb(y);
00315         GECODE_ME_CHECK( x[i].includeI(home,ylb) );
00316       }
00317 
00318       // xi.exclude (Intersection(xj.lb) - y.ub)
00319       {
00320         Region r;
00321         GLBndSet* rightSet =
00322           static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
00323         new (&rightSet[xsize-1]) GLBndSet(home);
00324         rightSet[xsize-1].update(home,intOfDets);
00325         for (int i=xsize-1;i--;) {
00326           GlbRanges<View0> xilb(x[i+1]);
00327           BndSetRanges prev(rightSet[i+1]);
00328           Iter::Ranges::Inter<GlbRanges<View0>,
00329             BndSetRanges> inter(xilb,prev);
00330           new (&rightSet[i]) GLBndSet(home);
00331           rightSet[i].includeI(home,inter);
00332         }
00333 
00334         LUBndSet leftAcc(home);
00335 
00336         for (int i=0;i<xsize;i++) {
00337           BndSetRanges left(leftAcc);
00338           BndSetRanges right(rightSet[i]);
00339           Iter::Ranges::Inter<BndSetRanges,
00340             BndSetRanges> inter(left, right);
00341           LubRanges<View1> yub(y);
00342           Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00343             BndSetRanges>, LubRanges<View1> >
00344             forbidden(inter, yub);
00345           GECODE_ME_CHECK( x[i].excludeI(home,forbidden) );
00346           GlbRanges<View0> xlb(x[i]);
00347           leftAcc.intersectI(home,xlb);
00348         }
00349         for (int i=xsize; i--;)
00350           rightSet[i].dispose(home);
00351         leftAcc.dispose(home);
00352       }
00353 
00354 
00355       for(int i=0;i<x.size();i++) {
00356         //Do not reverse! Eats away the end of the array!
00357         while (i<x.size() && x[i].assigned()) {
00358           GlbRanges<View0> det(x[i]);
00359           if (intOfDets.intersectI(home,det)) {repeat = true;}
00360           x.move_lst(i);
00361           if (intOfDets.size()==0) {
00362             GECODE_ME_CHECK( y.cardMax(home,0) );
00363             intOfDets.dispose(home);
00364             return home.ES_SUBSUMED(*this);
00365           }
00366         }
00367       }
00368     size0:
00369       if (x.size()==0) {
00370         BndSetRanges all1(intOfDets);
00371         GECODE_ME_CHECK( y.intersectI(home,all1) );
00372         BndSetRanges all2(intOfDets);
00373         GECODE_ME_CHECK( y.includeI(home,all2) );
00374         intOfDets.dispose(home);
00375         return home.ES_SUBSUMED(*this);
00376       }
00377 
00378     } while (repeat);
00379 
00380     return shared ? ES_NOFIX : ES_FIX;
00381   }
00382 
00383 }}}
00384 
00385 // STATISTICS: set-prop