Generated on Mon Aug 25 11:35:43 2008 for Gecode by doxygen 1.5.6

union.icc

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: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
00017  *     $Revision: 6017 $
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(Space* 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(Space* 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   Support::Symbol
00079   Union<View0,View1,View2>::ati(void) {
00080     return Reflection::mangle<View0,View1,View2>("Gecode::Set::RelOp::Union");
00081   }
00082 
00083   template <class View0, class View1, class View2>
00084   Reflection::ActorSpec
00085   Union<View0,View1,View2>::spec(const Space* home,
00086                                  Reflection::VarMap& m) const {
00087     return MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00088       View2,PC_SET_ANY>::spec(home, m, ati());
00089   }
00090 
00091   template <class View0, class View1, class View2>
00092   void
00093   Union<View0,View1,View2>::post(Space* home,
00094                                  Reflection::VarMap& vars,
00095                                  const Reflection::ActorSpec& spec) {
00096     spec.checkArity(3);
00097     View0 x0(home, vars, spec[0]);
00098     View1 x1(home, vars, spec[1]);
00099     View2 x2(home, vars, spec[2]);
00100     (void) new (home) Union(home,x0,x1,x2);
00101   }
00102 
00103   template <class View0, class View1, class View2>
00104   ExecStatus
00105   Union<View0,View1,View2>::propagate(Space* home, ModEventDelta med) {
00106     // This propagator implements the constraint
00107     // x2 = x0 u x1
00108 
00109     bool x0ass = x0.assigned();
00110     bool x1ass = x1.assigned();
00111     bool x2ass = x2.assigned();
00112 
00113     ModEvent me0 = View0::me(med);
00114     ModEvent me1 = View1::me(med);
00115     ModEvent me2 = View2::me(med);
00116 
00117     bool x0ubmod = false;
00118     bool x1ubmod = false;
00119     bool modified = false;
00120 
00121     do {
00122 
00123       modified = false;
00124       do {
00125         // 4) lub(x2) <= lub(x0) u lub(x1)
00126         {
00127           LubRanges<View0> x0ub(x0);
00128           LubRanges<View1> x1ub(x1);
00129           Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u2(x0ub,x1ub);
00130           GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,u2) );
00131         }
00132 
00133         if (modified || Rel::testSetEventUB(me2) )
00134           {
00135             modified = false;
00136             // 5) x0 <= x2
00137             LubRanges<View2> x2ub1(x2);
00138             GECODE_ME_CHECK_MODIFIED(modified, x0.intersectI(home,x2ub1) );
00139             x0ubmod |= modified;
00140 
00141             // 6) x1 <= x2
00142             bool modified2=false;
00143             LubRanges<View2> x2ub2(x2);
00144             GECODE_ME_CHECK_MODIFIED(modified2, x1.intersectI(home,x2ub2) );
00145             x1ubmod |= modified2;
00146             modified |= modified2;
00147           }
00148 
00149       } while (modified);
00150 
00151       modified = false;
00152       do {
00153         bool modifiedOld = modified;
00154         modified = false;
00155 
00156         if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me0)
00157              || x0ubmod || modifiedOld)
00158           {
00159             // 1) glb(x0) \ lub(x1) <= glb(x2)
00160             GlbRanges<View2> x2lb(x2);
00161             LubRanges<View0> x0ub(x0);
00162             Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View0> >
00163               diff(x2lb, x0ub);
00164             GECODE_ME_CHECK_MODIFIED(modified, x1.includeI(home,diff) );
00165           }
00166 
00167         if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me1)
00168             || x1ubmod || modifiedOld)
00169           {
00170             // 2) glb(x0) \ lub(x2) <= glb(x1)
00171             GlbRanges<View2> x2lb(x2);
00172             LubRanges<View1> x1ub(x1);
00173             Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View1> >
00174               diff(x2lb, x1ub);
00175             GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,diff) );
00176           }
00177 
00178          if (Rel::testSetEventLB(me0,me1) || modified)
00179           {
00180             //            modified = false;
00181             // 3) glb(x1) u glb(x2) <= glb(x0)
00182             GlbRanges<View0> x0lb(x0);
00183             GlbRanges<View1> x1lb(x1);
00184             Iter::Ranges::Union<GlbRanges<View0>, GlbRanges<View1> >
00185               u1(x0lb,x1lb);
00186             GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,u1) );
00187           }
00188 
00189       } while(modified);
00190 
00191       modified = false;
00192       {
00193         // cardinality
00194         ExecStatus ret = unionCard(home,modified, x0, x1, x2);
00195         GECODE_ES_CHECK(ret);
00196       }
00197 
00198       if (x2.cardMax() == 0) {
00199         GECODE_ME_CHECK( x0.cardMax(home, 0) );
00200         GECODE_ME_CHECK( x1.cardMax(home, 0) );
00201         return ES_SUBSUMED(this,home);
00202       }
00203 
00204       if (x0.cardMax() == 0)
00205         GECODE_REWRITE(this,(Rel::Eq<View1,View2>::post(home,x1,x2)));
00206       if (x1.cardMax() == 0)
00207         GECODE_REWRITE(this,(Rel::Eq<View0,View2>::post(home,x0,x2)));
00208 
00209     } while(modified);
00210 
00211     if (shared(x0,x1,x2)) {
00212       return (x0ass && x1ass && x2ass) ? ES_SUBSUMED(this,home) : ES_NOFIX;
00213     } else {
00214       if (x0ass && x1ass && x2ass)
00215         return ES_SUBSUMED(this,home);
00216       if (x0ass != x0.assigned() ||
00217           x1ass != x1.assigned() ||
00218           x2ass != x2.assigned()) {
00219         return ES_NOFIX;
00220       } else {
00221          return ES_FIX;
00222       }
00223     }
00224   }
00225 
00226 
00227   /*
00228    * "Nary union" propagator
00229    *
00230    */
00231 
00232   template <class View0, class View1>
00233   forceinline
00234   UnionN<View0,View1>::UnionN(Space* home, ViewArray<View0>& x, View1 y)
00235     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00236     shared = x.shared() || viewarrayshared(x,y);
00237   }
00238 
00239   template <class View0, class View1>
00240   forceinline
00241   UnionN<View0,View1>::UnionN(Space* home, ViewArray<View0>& x,
00242                               const IntSet& z, View1 y)
00243     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
00244     shared = x.shared() || viewarrayshared(x,y);
00245     IntSetRanges rz(z);
00246     unionOfDets.includeI(home, rz);
00247   }
00248 
00249   template <class View0, class View1>
00250   forceinline
00251   UnionN<View0,View1>::UnionN(Space* home, bool share, UnionN& p)
00252     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p),
00253       shared(p.shared) {
00254     unionOfDets.update(home,p.unionOfDets);
00255   }
00256 
00257   template <class View0, class View1>
00258   Actor*
00259   UnionN<View0,View1>::copy(Space* home, bool share) {
00260     return new (home) UnionN<View0,View1>(home,share,*this);
00261   }
00262 
00263   template <class View0, class View1>
00264   ExecStatus 
00265   UnionN<View0,View1>::post(Space* home, ViewArray<View0>& x, View1 y) {
00266     switch (x.size()) {
00267     case 0:
00268       GECODE_ME_CHECK(y.cardMax(home, 0));
00269       return ES_OK;
00270     case 1:
00271       return Rel::Eq<View0,View1>::post(home, x[0], y);
00272     case 2:
00273       return Union<View0,View0,View1>::post(home, x[0], x[1], y);
00274     default:
00275       (void) new (home) UnionN<View0,View1>(home,x,y);
00276       return ES_OK;
00277     }
00278   }
00279 
00280   template <class View0, class View1>
00281   ExecStatus 
00282   UnionN<View0,View1>::post(Space* home, ViewArray<View0>& x,
00283                             const IntSet& z, View1 y) {
00284     (void) new (home) UnionN<View0,View1>(home,x,z,y);
00285     return ES_OK;
00286   }
00287 
00288   template <class View0, class View1>
00289   PropCost
00290   UnionN<View0,View1>::cost(ModEventDelta) const {
00291     return PC_QUADRATIC_LO;
00292   }
00293 
00294   template <class View0, class View1>
00295   Support::Symbol
00296   UnionN<View0,View1>::ati(void) {
00297     return Reflection::mangle<View0,View1>("Gecode::Set::RelOp::UnionN");
00298   }
00299 
00300   template <class View0, class View1>
00301   Reflection::ActorSpec
00302   UnionN<View0,View1>::spec(const Space* home,
00303                             Reflection::VarMap& m) const {
00304     Reflection::ActorSpec s =
00305       MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>
00306         ::spec(home, m, ati());
00307     int count = 0;
00308     for (BndSetRanges uod(unionOfDets); uod(); ++uod)
00309       count++;
00310     Reflection::IntArrayArg* a = Reflection::Arg::newIntArray(count*2);
00311     count = 0;
00312     for (BndSetRanges uod(unionOfDets); uod(); ++uod) {
00313       (*a)[count++] = uod.min();
00314       (*a)[count++] = uod.max();
00315     }
00316     return s << a;
00317   }
00318 
00319   template <class View0, class View1>
00320   void
00321   UnionN<View0,View1>::post(Space* home,
00322                             Reflection::VarMap& vars,
00323                             const Reflection::ActorSpec& spec) {
00324     spec.checkArity(3);
00325     ViewArray<View0> x0(home, vars, spec[0]);
00326     View1 x1(home, vars, spec[1]);
00327     Reflection::IntArrayArgRanges zr(spec[2]->toIntArray());
00328     IntSet z(zr);
00329     (void) new (home) UnionN(home,x0,z,x1);
00330   }
00331 
00332   template <class View0, class View1>
00333   ExecStatus
00334   UnionN<View0,View1>::propagate(Space* home, ModEventDelta med) {
00335     ModEvent me0 = View0::me(med);
00336     ModEvent me1 = View1::me(med);
00337     bool ubevent = Rel::testSetEventUB(me0, me1);
00338     bool lbevent = Rel::testSetEventLB(me0, me1);
00339     bool anybevent = Rel::testSetEventAnyB(me0, me1);
00340     bool cardevent = Rel::testSetEventCard(me0, me1);
00341 
00342     bool modified = false;
00343     bool oldModified = false;
00344 
00345     do {
00346       oldModified = modified;
00347       modified = false;
00348       if (modified || oldModified || ubevent)
00349         GECODE_ME_CHECK(unionNXiUB(home, modified, x, y,unionOfDets));
00350       if (modified || oldModified || ubevent)
00351         GECODE_ME_CHECK(partitionNYUB(home, modified, x, y,unionOfDets));
00352       if (modified || oldModified || anybevent)
00353         GECODE_ME_CHECK(partitionNXiLB(home, modified, x, y,unionOfDets));
00354       if (modified || oldModified || lbevent)
00355         GECODE_ME_CHECK(partitionNYLB(home, modified, x, y,unionOfDets));
00356       if (modified || oldModified || cardevent || ubevent)
00357         GECODE_ME_CHECK(unionNCard(home, modified, x, y, unionOfDets));
00358     } while (modified);
00359 
00360     for(int i=0;i<x.size();i++){
00361       //Do not reverse! Eats away the end of the array!
00362       while (i<x.size() && x[i].assigned()) {
00363         GlbRanges<View0> det(x[i]);
00364         unionOfDets.includeI(home,det);
00365         x.move_lst(i);
00366       }
00367     }
00368     // When we run out of variables, make a final check and disolve:
00369     if (x.size()==0) {
00370       BndSetRanges all1(unionOfDets);
00371       GECODE_ME_CHECK( y.intersectI(home,all1) );
00372       BndSetRanges all2(unionOfDets);
00373       GECODE_ME_CHECK( y.includeI(home,all2) );
00374       unionOfDets.dispose(home);
00375       return ES_SUBSUMED(this,home);
00376     }
00377 
00378     return shared ? ES_NOFIX : ES_FIX;
00379   }
00380 
00381 }}}
00382 
00383 // STATISTICS: set-prop