re-subset.icc

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: 2006-05-29 09:42:21 +0200 (Mon, 29 May 2006) $ by $Author: schulte $
00012  *     $Revision: 3246 $
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), x0(y0), x1(y1), b(y2) {
00031     b.subscribe(home,this, Gecode::Int::PC_INT_VAL);
00032     x0.subscribe(home,this, PC_SET_ANY);
00033     x1.subscribe(home,this, PC_SET_ANY);
00034   }
00035 
00036   template <class View0, class View1>
00037   forceinline
00038   ReSubset<View0,View1>::ReSubset(Space* home, bool share, ReSubset& p)
00039     : Propagator(home,share,p) {
00040     x0.update(home,share,p.x0);
00041     x1.update(home,share,p.x1);
00042     b.update(home,share,p.b);
00043   }
00044 
00045   template <class View0, class View1>
00046   PropCost
00047   ReSubset<View0,View1>::cost(void) const {
00048     return PC_TERNARY_LO;
00049   }
00050 
00051   template <class View0, class View1>
00052   size_t
00053   ReSubset<View0,View1>::dispose(Space* home) {
00054     assert(!home->failed());
00055     b.cancel(home,this, Gecode::Int::PC_INT_VAL);
00056     x0.cancel(home,this, PC_SET_ANY);
00057     x1.cancel(home,this, PC_SET_ANY);
00058     (void) Propagator::dispose(home);
00059     return sizeof(*this);
00060   }
00061 
00062   template <class View0, class View1>
00063   ExecStatus
00064   ReSubset<View0,View1>::post(Space* home, View0 x0, View1 x1,
00065                               Gecode::Int::BoolView b) {
00066     (void) new (home) ReSubset<View0,View1>(home,x0,x1,b);
00067     return ES_OK;
00068   }
00069 
00070   template <class View0, class View1>
00071   Actor*
00072   ReSubset<View0,View1>::copy(Space* home, bool share) {
00073     return new (home) ReSubset<View0,View1>(home,share,*this);
00074   }
00075 
00076   template <class View0, class View1>
00077   ExecStatus
00078   ReSubset<View0,View1>::propagate(Space* home) {
00079 
00080     if (b.one()) {
00081       GECODE_ES_CHECK((SubSet<View0,View1>::post(home,x0,x1)));
00082       return ES_SUBSUMED;
00083     }
00084     if (b.zero()) {
00085       GECODE_ES_CHECK((NoSubSet<View0,View1>::post(home,x0,x1)));
00086       return ES_SUBSUMED;
00087     }
00088 
00089     // check whether cardinalities still allow subset
00090     if (x0.cardMin() > x1.cardMax()) {
00091       b.t_zero_none(home);
00092       return ES_SUBSUMED;
00093     }
00094 
00095     // check lub(x0) subset glb(x1)
00096     LubRanges<View0> x0ub(x0);
00097     GlbRanges<View1> x1lb(x1);
00098     Iter::Ranges::Diff<LubRanges<View0>,GlbRanges<View1> > diff1(x0ub, x1lb);
00099     if ( !(diff1()) ) {
00100       b.t_one_none(home);
00101       return ES_SUBSUMED;
00102     }
00103 
00104     // check glb(x0) subset lub(x1)
00105     GlbRanges<View0> x0lb(x0);
00106     LubRanges<View1> x1ub(x1);
00107     Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View1> > diff2(x0lb, x1ub);
00108     if ( diff2() ) {
00109       b.t_zero_none(home);
00110       return ES_SUBSUMED;
00111     } else if (x0.assigned() && x1.assigned()) {
00112       b.t_one_none(home);
00113       return ES_SUBSUMED;
00114     } else {
00115       return ES_FIX;
00116     }
00117   }
00118 
00119 }}}
00120 
00121 // STATISTICS: set-prop