Generated on Mon May 5 05:54:04 2008 for Gecode by doxygen 1.5.5

inter.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-02-20 17:07:56 +0100 (Wed, 20 Feb 2008) $ by $Author: tack $
00017  *     $Revision: 6251 $
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(Space* 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   Support::Symbol
00066   Intersection<View0,View1,View2>::ati(void) {
00067     return Reflection::mangle<View0,View1,View2>("Gecode::Set::RelOp::Intersection");
00068   }
00069 
00070   template <class View0, class View1, class View2>
00071   Reflection::ActorSpec
00072   Intersection<View0,View1,View2>::spec(const Space* home,
00073                                         Reflection::VarMap& m) const {
00074     return MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00075       View2,PC_SET_ANY>::spec(home, m, ati());
00076   }
00077 
00078   template <class View0, class View1, class View2>
00079   void
00080   Intersection<View0,View1,View2>::post(Space* home,
00081                                         Reflection::VarMap& vars,
00082                                         const Reflection::ActorSpec& spec) {
00083     spec.checkArity(3);
00084     View0 x0(home, vars, spec[0]);
00085     View1 x1(home, vars, spec[1]);
00086     View2 x2(home, vars, spec[2]);
00087     (void) new (home) Intersection(home,x0,x1,x2);
00088   }
00089 
00090   template <class View0, class View1, class View2>
00091   ExecStatus
00092   Intersection<View0,View1,View2>::propagate(Space* home, ModEventDelta) {
00093 
00094     bool x0ass=x0.assigned();
00095     bool x1ass=x1.assigned();
00096     bool x2ass=x2.assigned();
00097 
00098     {
00099       GlbRanges<View2> x2lb(x2);
00100       GECODE_ME_CHECK( x0.includeI(home,x2lb) );
00101     }
00102     {
00103       GlbRanges<View2> x2lb(x2);
00104       GECODE_ME_CHECK( x1.includeI(home,x2lb) );
00105     }
00106     {
00107       GlbRanges<View0> x0lb(x0);
00108       LubRanges<View2> x2ub(x2);
00109       Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View2> > m1(x0lb,x2ub);
00110       GECODE_ME_CHECK( x1.excludeI(home,m1) );
00111     }
00112     {
00113       GlbRanges<View1> x1lb(x1);
00114       LubRanges<View2> x2ub(x2);
00115 
00116       Iter::Ranges::Diff<GlbRanges<View1>,LubRanges<View2> > m2(x1lb,x2ub);
00117       GECODE_ME_CHECK( x0.excludeI(home,m2) );
00118     }
00119     {
00120       GlbRanges<View0> x0lb(x0);
00121       GlbRanges<View1> x1lb(x1);
00122       Iter::Ranges::Inter<GlbRanges<View0>,GlbRanges<View1> > i1(x0lb,x1lb);
00123       GECODE_ME_CHECK( x2.includeI(home,i1) );
00124     }
00125     {
00126       LubRanges<View0> x0ub(x0);
00127       LubRanges<View1> x1ub(x1);
00128       Iter::Ranges::Inter<LubRanges<View0>,LubRanges<View1> > i2(x0ub,x1ub);
00129       GECODE_ME_CHECK( x2.intersectI(home,i2) );
00130     }
00131     unsigned int m, n;
00132     {
00133       LubRanges<View0> x0ub(x0);
00134       LubRanges<View1> x1ub(x1);
00135       Iter::Ranges::Union<LubRanges<View0>,LubRanges<View1> > u1(x0ub,x1ub);
00136       m = Iter::Ranges::size(u1);
00137       n = x0.cardMin()+x1.cardMin();
00138       if (n>m)
00139         GECODE_ME_CHECK( x2.cardMin(home,n-m) );
00140     }
00141     unsigned int s2;
00142     {
00143       LubRanges<View0> x0ub(x0);
00144       GlbRanges<View1> x1lb(x1);
00145       Iter::Ranges::Diff<GlbRanges<View1>,LubRanges<View0> > d2(x1lb,x0ub);
00146       s2 = Iter::Ranges::size(d2);
00147       assert (s2 <= x1.cardMax());
00148       GECODE_ME_CHECK( x2.cardMax(home,x1.cardMax()-s2) );
00149     }
00150     {
00151       LubRanges<View1> x1ub(x1);
00152       GlbRanges<View0> x0lb(x0);
00153       Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View1> > d1 (x0lb,x1ub);
00154       unsigned int s1 = Iter::Ranges::size(d1);
00155       assert (s1 <= x0.cardMax());
00156       GECODE_ME_CHECK( x2.cardMax(home,x0.cardMax()-s1) );
00157       if (m+x2.cardMax() > x1.cardMin())
00158         GECODE_ME_CHECK( x0.cardMax(home,m+x2.cardMax()-x1.cardMin()) );
00159       //I might have to recaluclate m here?
00160       if (m+x2.cardMax() > x0.cardMin())
00161         GECODE_ME_CHECK( x1.cardMax(home,m+x2.cardMax()-x0.cardMin()) );
00162       //s1 and s2 could be outdated too...
00163       GECODE_ME_CHECK( x0.cardMin(home,s1+x2.cardMin()) );
00164       GECODE_ME_CHECK( x1.cardMin(home,s2+x2.cardMin()) );
00165     }
00166     if ( x0ass + x1ass + x2ass >= 2 ) return ES_SUBSUMED(this,home);
00167 
00168     return ES_NOFIX;
00169   }
00170 
00171   template <class View0, class View1, class View2>
00172   forceinline
00173   Intersection<View0,View1,View2>::Intersection(Space* home,
00174                                              View0 y0,View1 y1,View2 y2)
00175     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00176                              View2,PC_SET_ANY>(home,y0,y1,y2) {}
00177 
00178   template <class View0, class View1, class View2>
00179   forceinline
00180   Intersection<View0,View1,View2>::Intersection(Space* home, bool share,
00181                                              Intersection<View0,View1,View2>& p)
00182     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00183                              View2,PC_SET_ANY>(home,share,p) {}
00184 
00185   /*
00186    * "Nary intersection" propagator
00187    *
00188    */
00189 
00190   template <class View0, class View1>
00191   forceinline
00192   IntersectionN<View0,View1>::IntersectionN(Space* home, ViewArray<View0>& x,
00193                                             View1 y)
00194     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00195       intOfDets(home) {
00196     shared = x.shared() || viewarrayshared(x,y);
00197   }
00198 
00199   template <class View0, class View1>
00200   forceinline
00201   IntersectionN<View0,View1>::IntersectionN(Space* home, ViewArray<View0>& x,
00202                                             const IntSet& z, View1 y)
00203     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
00204       intOfDets(home) {
00205     shared = x.shared() || viewarrayshared(x,y);
00206     IntSetRanges rz(z);
00207     intOfDets.intersectI(home, rz);
00208   }
00209 
00210   template <class View0, class View1>
00211   forceinline
00212   IntersectionN<View0,View1>::IntersectionN(Space* home, bool share,
00213                                             IntersectionN& p)
00214     : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p),
00215       shared(p.shared),
00216       intOfDets() {
00217     intOfDets.update(home, p.intOfDets);
00218   }
00219 
00220   template <class View0, class View1>
00221   ExecStatus
00222   IntersectionN<View0,View1>::post(Space* home,
00223                                    ViewArray<View0>& x, View1 y) {
00224     switch (x.size()) {
00225     case 0:
00226       GECODE_ME_CHECK(y.cardMin(home, Limits::card));
00227       return ES_OK;
00228     case 1:
00229       return Rel::Eq<View0,View1>::post(home, x[0], y);
00230     case 2:
00231       return Intersection<View0,View0,View1>::post(home, x[0], x[1], y);
00232     default:
00233       (void) new (home) IntersectionN<View0,View1>(home,x,y);
00234       return ES_OK;
00235     }
00236   }
00237 
00238   template <class View0, class View1>
00239   ExecStatus
00240   IntersectionN<View0,View1>::post(Space* home, ViewArray<View0>& x,
00241                                    const IntSet& z, View1 y) {
00242     (void) new (home) IntersectionN<View0,View1>(home,x,z,y);
00243     return ES_OK;
00244   }
00245 
00246   template <class View0, class View1>
00247   Actor*
00248   IntersectionN<View0,View1>::copy(Space* home, bool share) {
00249     return new (home) IntersectionN<View0,View1>(home,share,*this);
00250   }
00251 
00252   template <class View0, class View1>
00253   PropCost
00254   IntersectionN<View0,View1>::cost(ModEventDelta) const {
00255     return PC_QUADRATIC_LO;
00256   }
00257 
00258   template <class View0, class View1>
00259   Support::Symbol
00260   IntersectionN<View0,View1>::ati(void) {
00261     return Reflection::mangle<View0,View1>("Gecode::Set::RelOp::IntersectionN");
00262   }
00263 
00264   template <class View0, class View1>
00265   Reflection::ActorSpec
00266   IntersectionN<View0,View1>::spec(const Space* home,
00267                                    Reflection::VarMap& m) const {
00268     Reflection::ActorSpec s =
00269       MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>
00270         ::spec(home, m, ati());
00271     int count = 0;
00272     for (BndSetRanges iod(intOfDets); iod(); ++iod)
00273       count++;
00274     Reflection::IntArrayArg* a = Reflection::Arg::newIntArray(count*2);
00275     count = 0;
00276     for (BndSetRanges iod(intOfDets); iod(); ++iod) {
00277       (*a)[count++] = iod.min();
00278       (*a)[count++] = iod.max();
00279     }
00280     return s << a;
00281   }
00282 
00283   template <class View0, class View1>
00284   void
00285   IntersectionN<View0,View1>::post(Space* home,
00286                                    Reflection::VarMap& vars,
00287                                    const Reflection::ActorSpec& spec) {
00288     spec.checkArity(3);
00289     ViewArray<View0> x0(home, vars, spec[0]);
00290     View1 x1(home, vars, spec[1]);
00291     Reflection::IntArrayArgRanges zr(spec[2]->toIntArray());
00292     IntSet z(zr);
00293     (void) new (home) IntersectionN(home,x0,z,x1);
00294   }
00295 
00296   template <class View0, class View1>
00297   ExecStatus
00298   IntersectionN<View0,View1>::propagate(Space* home, ModEventDelta) {
00299 
00300     bool repeat = false;
00301     do {
00302       repeat = false;
00303       int xsize = x.size();
00304       if (xsize == 0)
00305         goto size0;
00306       for (int i = xsize; i--; ) {
00307         GECODE_ME_CHECK( y.cardMax(home,x[i].cardMax()) );
00308         GECODE_ME_CHECK( x[i].cardMin(home,y.cardMin()) );
00309         if (x[i].cardMax()==0) {
00310           GECODE_ME_CHECK( y.cardMax(home, 0));
00311           intOfDets.dispose(home);
00312           return ES_SUBSUMED(this,home);
00313         }
00314       }
00315       {
00316         GECODE_AUTOARRAY(GlbRanges<View0>,xLBs,xsize);
00317         GECODE_AUTOARRAY(LubRanges<View0>,xUBs,xsize);
00318         for (int i = xsize; i--; ) {
00319           GlbRanges<View0> lb(x[i]);
00320           LubRanges<View0> ub(x[i]);
00321           xLBs[i]=lb;
00322           xUBs[i]=ub;
00323         }
00324         Iter::Ranges::NaryInter<GlbRanges<View0> > lbi(xLBs,xsize);
00325         BndSetRanges dets1(intOfDets);
00326         Iter::Ranges::Inter< Iter::Ranges::NaryInter<GlbRanges<View0> >,
00327           BndSetRanges >
00328           lbiAll(lbi,dets1);
00329         GECODE_ME_CHECK( y.includeI(home,lbiAll) );
00330 
00331         Iter::Ranges::NaryInter<LubRanges<View0> > ubi(xUBs,xsize);
00332         BndSetRanges dets2(intOfDets);
00333         Iter::Ranges::Inter< Iter::Ranges::NaryInter<LubRanges<View0> >,
00334           BndSetRanges >
00335           ubiAll(ubi,dets2);
00336         GECODE_ME_CHECK( y.intersectI(home,ubiAll) );
00337       }
00338 
00339       for (int i = xsize; i--; ) {
00340         GlbRanges<View1> ylb(y);
00341         GECODE_ME_CHECK( x[i].includeI(home,ylb) );
00342       }
00343 
00344       // xi.exclude (Intersection(xj.lb) - y.ub)
00345       {
00346         GECODE_AUTOARRAY(GLBndSet, rightSet, xsize);
00347         new (&rightSet[xsize-1]) GLBndSet(home);
00348         rightSet[xsize-1].update(home,intOfDets);
00349         for (int i=xsize-1;i--;) {
00350           GlbRanges<View0> xilb(x[i+1]);
00351           BndSetRanges prev(rightSet[i+1]);
00352           Iter::Ranges::Inter<GlbRanges<View0>,
00353             BndSetRanges> inter(xilb,prev);
00354           new (&rightSet[i]) GLBndSet(home);
00355           rightSet[i].includeI(home,inter);
00356         }
00357 
00358         LUBndSet leftAcc(home);
00359 
00360         for (int i=0;i<xsize;i++) {
00361           BndSetRanges left(leftAcc);
00362           BndSetRanges right(rightSet[i]);
00363           Iter::Ranges::Inter<BndSetRanges,
00364             BndSetRanges> inter(left, right);
00365           LubRanges<View1> yub(y);
00366           Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges,
00367             BndSetRanges>, LubRanges<View1> >
00368             forbidden(inter, yub);
00369           GECODE_ME_CHECK( x[i].excludeI(home,forbidden) );
00370           GlbRanges<View0> xlb(x[i]);
00371           leftAcc.intersectI(home,xlb);
00372         }
00373         for (int i=xsize; i--;)
00374           rightSet[i].dispose(home);
00375         leftAcc.dispose(home);
00376       }
00377 
00378 
00379       for(int i=0;i<x.size();i++){
00380         //Do not reverse! Eats away the end of the array!
00381         while (i<x.size() && x[i].assigned()) {
00382           GlbRanges<View0> det(x[i]);
00383           if (intOfDets.intersectI(home,det)) {repeat = true;}
00384           x.move_lst(i);
00385           if (intOfDets.size()==0) {
00386             GECODE_ME_CHECK( y.cardMax(home,0) );
00387             intOfDets.dispose(home);
00388             return ES_SUBSUMED(this,home);
00389           }
00390         }
00391       }
00392     size0:
00393       if (x.size()==0) {
00394         BndSetRanges all1(intOfDets);
00395         GECODE_ME_CHECK( y.intersectI(home,all1) );
00396         BndSetRanges all2(intOfDets);
00397         GECODE_ME_CHECK( y.includeI(home,all2) );
00398         intOfDets.dispose(home);
00399         return ES_SUBSUMED(this,home);
00400       }
00401 
00402     } while (repeat);
00403 
00404     return shared ? ES_NOFIX : ES_FIX;
00405   }
00406 
00407 }}}
00408 
00409 // STATISTICS: set-prop