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

union.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 union" propagator
00044    *
00045    */
00046 
00047   template<class View0, class View1, class View2>
00048   forceinline
00049   Union<View0,View1,View2>::Union(Home home, View0 y0,View1 y1,View2 y2)
00050     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00051                              View2,PC_SET_ANY>(home,y0,y1,y2) {}
00052 
00053   template<class View0, class View1, class View2>
00054   forceinline
00055   Union<View0,View1,View2>::Union(Space& home,
00056                                   Union<View0,View1,View2>& p)
00057     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00058                              View2,PC_SET_ANY>(home,p) {}
00059 
00060   template<class View0, class View1, class View2>
00061   ExecStatus Union<View0,View1,View2>::post(Home home, View0 x0,
00062                                          View1 x1, View2 x2) {
00063     (void) new (home) Union<View0,View1,View2>(home,x0,x1,x2);
00064     return ES_OK;
00065   }
00066 
00067   template<class View0, class View1, class View2>
00068   Actor*
00069   Union<View0,View1,View2>::copy(Space& home) {
00070     return new (home) Union(home,*this);
00071   }
00072 
00073   template<class View0, class View1, class View2>
00074   ExecStatus
00075   Union<View0,View1,View2>::propagate(Space& home, const ModEventDelta& med) {
00076     // This propagator implements the constraint
00077     // x2 = x0 u x1
00078 
00079     bool x0ass = x0.assigned();
00080     bool x1ass = x1.assigned();
00081     bool x2ass = x2.assigned();
00082 
00083     ModEvent me0 = View0::me(med);
00084     ModEvent me1 = View1::me(med);
00085     ModEvent me2 = View2::me(med);
00086 
00087     bool x0ubmod = false;
00088     bool x1ubmod = false;
00089     bool modified = false;
00090 
00091     do {
00092 
00093       modified = false;
00094       do {
00095         // 4) lub(x2) <= lub(x0) u lub(x1)
00096         {
00097           LubRanges<View0> x0ub(x0);
00098           LubRanges<View1> x1ub(x1);
00099           Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u2(x0ub,x1ub);
00100           GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,u2) );
00101         }
00102 
00103         if (modified || Rel::testSetEventUB(me2) )
00104           {
00105             modified = false;
00106             // 5) x0 <= x2
00107             LubRanges<View2> x2ub1(x2);
00108             GECODE_ME_CHECK_MODIFIED(modified, x0.intersectI(home,x2ub1) );
00109             x0ubmod |= modified;
00110 
00111             // 6) x1 <= x2
00112             bool modified2=false;
00113             LubRanges<View2> x2ub2(x2);
00114             GECODE_ME_CHECK_MODIFIED(modified2, x1.intersectI(home,x2ub2) );
00115             x1ubmod |= modified2;
00116             modified |= modified2;
00117           }
00118 
00119       } while (modified);
00120 
00121       modified = false;
00122       do {
00123         bool modifiedOld = modified;
00124         modified = false;
00125 
00126         if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me0)
00127              || x0ubmod || modifiedOld)
00128           {
00129             // 1) glb(x0) \ lub(x1) <= glb(x2)
00130             GlbRanges<View2> x2lb(x2);
00131             LubRanges<View0> x0ub(x0);
00132             Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View0> >
00133               diff(x2lb, x0ub);
00134             GECODE_ME_CHECK_MODIFIED(modified, x1.includeI(home,diff) );
00135           }
00136 
00137         if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me1)
00138             || x1ubmod || modifiedOld)
00139           {
00140             // 2) glb(x0) \ lub(x2) <= glb(x1)
00141             GlbRanges<View2> x2lb(x2);
00142             LubRanges<View1> x1ub(x1);
00143             Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View1> >
00144               diff(x2lb, x1ub);
00145             GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,diff) );
00146           }
00147 
00148          if (Rel::testSetEventLB(me0,me1) || modified)
00149           {
00150             //            modified = false;
00151             // 3) glb(x1) u glb(x2) <= glb(x0)
00152             GlbRanges<View0> x0lb(x0);
00153             GlbRanges<View1> x1lb(x1);
00154             Iter::Ranges::Union<GlbRanges<View0>, GlbRanges<View1> >
00155               u1(x0lb,x1lb);
00156             GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,u1) );
00157           }
00158 
00159       } while(modified);
00160 
00161       modified = false;
00162       {
00163         // cardinality
00164         ExecStatus ret = unionCard(home,modified, x0, x1, x2);
00165         GECODE_ES_CHECK(ret);
00166       }
00167 
00168       if (x2.cardMax() == 0) {
00169         GECODE_ME_CHECK( x0.cardMax(home, 0) );
00170         GECODE_ME_CHECK( x1.cardMax(home, 0) );
00171         return home.ES_SUBSUMED(*this);
00172       }
00173 
00174       if (x0.cardMax() == 0)
00175         GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2)));
00176       if (x1.cardMax() == 0)
00177         GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2)));
00178 
00179     } while(modified);
00180 
00181     if (shared(x0,x1,x2)) {
00182       return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00183     } else {
00184       if (x0ass && x1ass && x2ass)
00185         return home.ES_SUBSUMED(*this);
00186       if (x0ass != x0.assigned() ||
00187           x1ass != x1.assigned() ||
00188           x2ass != x2.assigned()) {
00189         return ES_NOFIX;
00190       } else {
00191          return ES_FIX;
00192       }
00193     }
00194   }
00195 
00196 
00197   /*
00198    * "Nary union" propagator
00199    *
00200    */
00201 
00202   template<class View0, class View1>
00203   forceinline
00204   UnionN<View0,View1>::UnionN(Home home, ViewArray<View0>& x, View1 y)
00205     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00206     shared = Gecode::shared(x) || viewarrayshared(x,y);
00207   }
00208 
00209   template<class View0, class View1>
00210   forceinline
00211   UnionN<View0,View1>::UnionN(Home home, ViewArray<View0>& x,
00212                               const IntSet& z, View1 y)
00213     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00214     shared = Gecode::shared(x) || viewarrayshared(x,y);
00215     IntSetRanges rz(z);
00216     unionOfDets.includeI(home, rz);
00217   }
00218 
00219   template<class View0, class View1>
00220   forceinline
00221   UnionN<View0,View1>::UnionN(Space& home, UnionN& p)
00222     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p),
00223       shared(p.shared) {
00224     unionOfDets.update(home,p.unionOfDets);
00225   }
00226 
00227   template<class View0, class View1>
00228   Actor*
00229   UnionN<View0,View1>::copy(Space& home) {
00230     return new (home) UnionN<View0,View1>(home,*this);
00231   }
00232 
00233   template<class View0, class View1>
00234   ExecStatus
00235   UnionN<View0,View1>::post(Home home, ViewArray<View0>& x, View1 y) {
00236     switch (x.size()) {
00237     case 0:
00238       GECODE_ME_CHECK(y.cardMax(home, 0));
00239       return ES_OK;
00240     case 1:
00241       return Rel::Eq<View0,View1>::post(home, x[0], y);
00242     case 2:
00243       return Union<View0,View0,View1>::post(home, x[0], x[1], y);
00244     default:
00245       (void) new (home) UnionN<View0,View1>(home,x,y);
00246       return ES_OK;
00247     }
00248   }
00249 
00250   template<class View0, class View1>
00251   ExecStatus
00252   UnionN<View0,View1>::post(Home home, ViewArray<View0>& x,
00253                             const IntSet& z, View1 y) {
00254     (void) new (home) UnionN<View0,View1>(home,x,z,y);
00255     return ES_OK;
00256   }
00257 
00258   template<class View0, class View1>
00259   PropCost
00260   UnionN<View0,View1>::cost(const Space&, const ModEventDelta&) const {
00261     return PropCost::quadratic(PropCost::LO, x.size()+1);
00262   }
00263 
00264   template<class View0, class View1>
00265   ExecStatus
00266   UnionN<View0,View1>::propagate(Space& home, const ModEventDelta& med) {
00267     ModEvent me0 = View0::me(med);
00268     ModEvent me1 = View1::me(med);
00269     bool ubevent = Rel::testSetEventUB(me0, me1);
00270     bool lbevent = Rel::testSetEventLB(me0, me1);
00271     bool anybevent = Rel::testSetEventAnyB(me0, me1);
00272     bool cardevent = Rel::testSetEventCard(me0, me1);
00273 
00274     bool modified = false;
00275     bool oldModified = false;
00276 
00277     do {
00278       do {
00279         oldModified = modified;
00280         modified = false;
00281         if (modified || oldModified || ubevent)
00282           GECODE_ES_CHECK(unionNXiUB(home, modified, x, y,unionOfDets));
00283         if (modified || oldModified || ubevent)
00284           GECODE_ES_CHECK(partitionNYUB(home, modified, x, y,unionOfDets));
00285         if (modified || oldModified || anybevent)
00286           GECODE_ES_CHECK(partitionNXiLB(home, modified, x, y,unionOfDets));
00287         if (modified || oldModified || lbevent)
00288           GECODE_ES_CHECK(partitionNYLB(home, modified, x, y,unionOfDets));
00289         if (modified || oldModified || cardevent || ubevent) {
00290           GECODE_ES_CHECK(unionNCard(home, modified, x, y, unionOfDets));
00291         }
00292       } while (modified);
00293 
00294       for(int i=0;i<x.size();i++) {
00295         //Do not reverse! Eats away the end of the array!
00296         while (i<x.size() && x[i].assigned()) {
00297           GlbRanges<View0> det(x[i]);
00298           unionOfDets.includeI(home,det);
00299           x.move_lst(i);
00300           modified = true;
00301         }
00302       }
00303 
00304     } while (modified);
00305     // When we run out of variables, make a final check and disolve:
00306     if (x.size()==0) {
00307       BndSetRanges all1(unionOfDets);
00308       GECODE_ME_CHECK( y.intersectI(home,all1) );
00309       BndSetRanges all2(unionOfDets);
00310       GECODE_ME_CHECK( y.includeI(home,all2) );
00311       unionOfDets.dispose(home);
00312       return home.ES_SUBSUMED(*this);
00313     }
00314 
00315     return shared ? ES_NOFIX : ES_FIX;
00316   }
00317 
00318 }}}
00319 
00320 // STATISTICS: set-prop