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