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

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