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