Generated on Wed Jan 4 17:49:14 2006 for Gecode by doxygen 1.4.6

re-subset.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *     Christian Schulte, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-11-29 18:02:48 +0100 (Tue, 29 Nov 2005) $ by $Author: tack $
00012  *     $Revision: 2665 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 namespace Gecode { namespace Set { namespace Rel {
00025 
00026   template <class View0, class View1>
00027   forceinline
00028   ReSubset<View0,View1>::ReSubset(Space* home, View0 y0,
00029                                 View1 y1, Gecode::Int::BoolView y2)
00030     : Propagator(home, View0::destruct() || View1::destruct()),
00031       x0(y0), x1(y1), b(y2) {
00032 
00033     b.subscribe(home,this, Gecode::Int::PC_INT_VAL);
00034     x0.subscribe(home,this, PC_SET_ANY);
00035     x1.subscribe(home,this, PC_SET_ANY);
00036   }
00037 
00038   template <class View0, class View1>
00039   forceinline
00040   ReSubset<View0,View1>::ReSubset(Space* home, bool share, ReSubset& p)
00041     : Propagator(home,share,p) {
00042     x0.update(home,share,p.x0);
00043     x1.update(home,share,p.x1);
00044     b.update(home,share,p.b);
00045   }
00046 
00047   template <class View0, class View1>
00048   PropCost
00049   ReSubset<View0,View1>::cost(void) const {
00050     return PC_TERNARY_LO;
00051   }
00052 
00053   template <class View0, class View1>
00054   ReSubset<View0,View1>::~ReSubset(void) {
00055     b.cancel(this, Gecode::Int::PC_INT_VAL);
00056     x0.cancel(this, PC_SET_ANY);
00057     x1.cancel(this, PC_SET_ANY);
00058   }
00059 
00060   template <class View0, class View1>
00061   ExecStatus
00062   ReSubset<View0,View1>::post(Space* home, View0 x0, View1 x1,
00063                              Gecode::Int::BoolView b) {
00064     (void) new (home) ReSubset<View0,View1>(home,x0,x1,b);
00065     return ES_OK;
00066   }
00067 
00068   template <class View0, class View1>
00069   Actor*
00070   ReSubset<View0,View1>::copy(Space* home, bool share) {
00071     return new (home) ReSubset<View0,View1>(home,share,*this);
00072   }
00073 
00074   template <class View0, class View1>
00075   ExecStatus
00076   ReSubset<View0,View1>::propagate(Space* home) {
00077 
00078     if (b.one()) {
00079       GECODE_ES_CHECK((SubSet<View0,View1>::post(home,x0,x1)));
00080       return ES_SUBSUMED;
00081     }
00082     if (b.zero()) {
00083       GECODE_ES_CHECK((NoSubSet<View0,View1>::post(home,x0,x1)));
00084       return ES_SUBSUMED;
00085     }
00086 
00087     // check whether cardinalities still allow subset
00088     if (x0.cardMin() > x1.cardMax()) {
00089       b.t_zero_none(home);
00090       return ES_SUBSUMED;
00091     }
00092 
00093     // check lub(x0) subset glb(x1)
00094     LubRanges<View0> x0ub(x0);
00095     GlbRanges<View1> x1lb(x1);
00096     Iter::Ranges::Diff<LubRanges<View0>,GlbRanges<View1> > diff1(x0ub, x1lb);
00097     if ( !(diff1()) ) {
00098       b.t_one_none(home);
00099       return ES_SUBSUMED;
00100     }
00101 
00102     // check glb(x0) subset lub(x1)
00103     GlbRanges<View0> x0lb(x0);
00104     LubRanges<View1> x1ub(x1);
00105     Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View1> > diff2(x0lb, x1ub);
00106     if ( diff2() ) {
00107       b.t_zero_none(home);
00108       return ES_SUBSUMED;
00109     } else if (x0.assigned() && x1.assigned()) {
00110       b.t_one_none(home);
00111       return ES_SUBSUMED;
00112     } else {
00113       return ES_FIX;
00114     }
00115   }
00116 
00117 }}}
00118 
00119 // STATISTICS: set-prop