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

subofunion.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   template <class View0, class View1, class View2>
00047   Actor*
00048   SubOfUnion<View0,View1,View2>::copy(Space* home, bool share) {
00049     return new (home) SubOfUnion(home,share,*this);
00050   }
00051 
00052   template <class View0, class View1, class View2>
00053   Support::Symbol
00054   SubOfUnion<View0,View1,View2>::ati(void) {
00055     return Reflection::mangle<View0,View1,View2>("Gecode::Set::RelOp::SubOfUnion");
00056   }
00057 
00058   template <class View0, class View1, class View2>
00059   Reflection::ActorSpec
00060   SubOfUnion<View0,View1,View2>::spec(const Space* home,
00061                                       Reflection::VarMap& m) const {
00062     return MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00063       View2,PC_SET_ANY>::spec(home, m, ati());
00064   }
00065 
00066   template <class View0, class View1, class View2>
00067   void
00068   SubOfUnion<View0,View1,View2>::post(Space* home,
00069                                       Reflection::VarMap& vars,
00070                                       const Reflection::ActorSpec& spec) {
00071     spec.checkArity(3);
00072     View0 x0(home, vars, spec[0]);
00073     View1 x1(home, vars, spec[1]);
00074     View2 x2(home, vars, spec[2]);
00075     (void) new (home) SubOfUnion(home,x0,x1,x2);
00076   }
00077 
00078   template <class View0, class View1, class View2>
00079   ExecStatus
00080   SubOfUnion<View0,View1,View2>::propagate(Space* home, ModEventDelta med) {
00081 
00082     bool allassigned = x0.assigned() && x1.assigned() && x2.assigned();
00083 
00084     ModEvent me0 = View0::me(med);
00085     ModEvent me1 = View1::me(med);
00086     ModEvent me2 = View2::me(med);
00087 
00088     bool modified=false;
00089 
00090     do {
00091       // lub(x2) <= lub(x0) u lub(x1)
00092       if (modified || Rel::testSetEventUB(me0,me1))
00093         {
00094           LubRanges<View0> ub0(x0);
00095           LubRanges<View1> ub1(x1);
00096           Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u(ub0,ub1);
00097           GECODE_ME_CHECK(x2.intersectI(home,u));
00098         }
00099 
00100       // x1 <= glb(x2)-lub(x0)
00101       // x0 <= glb(x2)-lub(x1)
00102       if (modified || Rel::testSetEventAnyB(me0,me1,me2)) {
00103         {
00104           modified = false;
00105           GlbRanges<View2> lb2(x2);
00106           LubRanges<View0> ub0(x0);
00107           Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View0> >
00108             diff(lb2,ub0);
00109           GECODE_ME_CHECK_MODIFIED(modified, x1.includeI(home,diff));
00110         }
00111         {
00112           GlbRanges<View2> lb2(x2);
00113           LubRanges<View1> ub1(x1);
00114           Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View1> >
00115             diff(lb2,ub1);
00116           GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,diff));
00117         }
00118       } else {
00119         modified = false;
00120       }
00121 
00122       // cardinality propagation
00123       if (modified ||
00124           Rel::testSetEventCard(me0,me1,me2) ||
00125           Rel::testSetEventLB(me0,me1)
00126           ) {
00127         GlbRanges<View0> lb0c(x0);
00128         GlbRanges<View1> lb1c(x1);
00129         Iter::Ranges::Inter<GlbRanges<View0>, GlbRanges<View1> >
00130           inter(lb0c,lb1c);
00131 
00132         unsigned int m = Iter::Ranges::size(inter);
00133 
00134         if (m < x0.cardMax()+x1.cardMax()) {
00135           GECODE_ME_CHECK_MODIFIED(modified,
00136                             x2.cardMax( home,
00137                                         x0.cardMax()+x1.cardMax() - m ) );
00138         }
00139         if (m + x2.cardMin() > x1.cardMax()) {
00140           GECODE_ME_CHECK_MODIFIED(modified,
00141                             x0.cardMin( home,
00142                                         m+x2.cardMin()-x1.cardMax() )  );
00143         }
00144         if (m + x2.cardMin() > x0.cardMax()) {
00145           GECODE_ME_CHECK_MODIFIED(modified,
00146                             x1.cardMin( home,
00147                                         m+x2.cardMin()-x0.cardMax() )  );
00148         }
00149       }
00150 
00151     } while (modified);
00152 
00153     if (shared(x0,x1,x2)) {
00154       if (allassigned) {
00155         return ES_SUBSUMED(this,home);
00156       } else {
00157         return ES_NOFIX;
00158       }
00159     } else {
00160       if (x0.assigned() + x1.assigned() + x2.assigned() >= 2) {
00161          return ES_SUBSUMED(this,home);
00162       } else {
00163         return ES_FIX;
00164       }
00165     }
00166 
00167   }
00168 
00169   template <class View0, class View1, class View2>
00170   forceinline
00171   SubOfUnion<View0,View1,View2>::SubOfUnion(Space* home, View0 y0,
00172                                          View1 y1, View2 y2)
00173     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00174                              View2,PC_SET_ANY>(home,y0,y1,y2) {}
00175 
00176   template <class View0, class View1, class View2>
00177   forceinline
00178   SubOfUnion<View0,View1,View2>::SubOfUnion
00179   (Space* home, bool share, SubOfUnion<View0,View1,View2>& p)
00180     : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY,
00181                              View2,PC_SET_ANY>(home,share,p) {}
00182 
00183   template <class View0, class View1, class View2>
00184   ExecStatus SubOfUnion<View0,View1,View2>::post
00185   (Space* home, View0 x0, View1 x1, View2 x2) {
00186     (void) new (home) SubOfUnion<View0,View1,View2>(home,x0, x1, x2);
00187     return ES_OK;
00188   }
00189 
00190 }}}
00191 
00192 // STATISTICS: set-prop