nq.icc

00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Gabor Szokoli <szokoli@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004
00011  *     Christian Schulte, 2004
00012  *     Gabor Szokoli, 2004
00013  *
00014  *  Last modified:
00015  *     $Date: 2005-07-31 16:45:18 +0200 (Sun, 31 Jul 2005) $ by $Author: schulte $
00016  *     $Revision: 2096 $
00017  *
00018  *  This file is part of Gecode, the generic constraint
00019  *  development environment:
00020  *     http://www.gecode.org
00021  *
00022  *  See the file "LICENSE" for information on usage and
00023  *  redistribution of this file, and for a
00024  *     DISCLAIMER OF ALL WARRANTIES.
00025  *
00026  */
00027 
00028 namespace Gecode { namespace Set { namespace Rel {
00029 
00030   template <class View0, class View1>
00031   forceinline
00032   Distinct<View0,View1>::Distinct(Space* home, View0 x, View1 y)
00033     : InhomBinaryPropagator<View0, PC_SET_VAL, View1, PC_SET_VAL>(home,x,y) {}
00034 
00035   template <class View0, class View1>
00036   forceinline
00037   Distinct<View0,View1>::Distinct(Space* home, bool share, Distinct& p)
00038     : InhomBinaryPropagator<View0, PC_SET_VAL, View1, PC_SET_VAL>
00039         (home,share,p) {}
00040 
00041   template <class View0, class View1>
00042   ExecStatus
00043   Distinct<View0,View1>::post(Space* home, View0 x, View1 y) {
00044     if (x.assigned())
00045       GECODE_ES_CHECK((DistinctDoit<View1,View0>::post(home,y,x)));
00046     if (y.assigned())
00047       GECODE_ES_CHECK((DistinctDoit<View0,View1>::post(home,x,y)));
00048     (void) new (home) Distinct<View0,View1>(home,x,y);
00049     return ES_OK;
00050   }
00051 
00052   template <class View0, class View1>
00053   Actor*
00054   Distinct<View0,View1>::copy(Space* home, bool share) {
00055     return new (home) Distinct<View0,View1>(home,share,*this);
00056   }
00057 
00058   template <class View0, class View1>
00059   ExecStatus
00060   Distinct<View0,View1>::propagate(Space* home) {
00061     assert(x0.assigned()||x1.assigned());
00062     if (x0.assigned()) {
00063       GECODE_ES_CHECK((DistinctDoit<View1,View0>::post(home,x1,x0)));
00064     } else {
00065       GECODE_ES_CHECK((DistinctDoit<View0,View1>::post(home,x0,x1)));
00066     }
00067     return ES_SUBSUMED;
00068   }
00069 
00070   template <class View0, class View1>
00071   ExecStatus
00072   DistinctDoit<View0,View1>::post(Space* home, View0 x, View1 y) {
00073     (void) new (home) DistinctDoit<View0,View1>(home,x,y);
00074     return ES_OK;
00075   }
00076 
00077   template <class View0, class View1>
00078   Actor*
00079   DistinctDoit<View0,View1>::copy(Space* home, bool share) {
00080     return new (home) DistinctDoit<View0,View1>(home,share,*this);
00081   }
00082 
00083   template <class View0, class View1>
00084   ExecStatus
00085   DistinctDoit<View0,View1>::propagate(Space* home) {
00086     assert(y.assigned());
00087     if (x0.assigned()) {
00088       GlbRanges<View0> xi(x0);
00089       GlbRanges<View1> yi(y);
00090       if (Iter::Ranges::equal(xi,yi)) { return ES_FAILED; }
00091       else { return ES_SUBSUMED; }
00092     }
00093     assert(x0.lubSize()-x0.glbSize() >0);
00094     if (x0.cardMin()>y.cardMax()) { return ES_SUBSUMED; }
00095     if (x0.cardMax()<y.cardMin()) { return ES_SUBSUMED; }
00096     //These tests are too expensive, we should only do them
00097     //in the 1 unknown left case.
00098     GlbRanges<View0> xi1(x0);
00099     LubRanges<View1> yi1(y);
00100     if (!Iter::Ranges::subset(xi1,yi1)){ return ES_SUBSUMED; }
00101     LubRanges<View0> xi2(x0);
00102     GlbRanges<View1> yi2(y);
00103     if (!Iter::Ranges::subset(yi2,xi2)){ return ES_SUBSUMED; }
00104     // from here, we know y\subseteq lub(x) and glb(x)\subseteq y
00105 
00106     if (x0.lubSize() == y.cardMin() && x0.lubSize() > 0) {
00107       GECODE_ME_CHECK(x0.cardMax(home, x0.lubSize() - 1));
00108       return ES_SUBSUMED;
00109     }
00110     if (x0.glbSize() == y.cardMin()) {
00111       GECODE_ME_CHECK(x0.cardMin(home, x0.glbSize() + 1));
00112       return ES_SUBSUMED;
00113     }
00114     return ES_FIX;
00115   }
00116 
00117   template <class View0, class View1>
00118   forceinline
00119   DistinctDoit<View0,View1>::DistinctDoit(Space* home, View0 _x, View1 _y)
00120     : UnaryPropagator<View0, PC_SET_ANY>(home,_x), y(_y)  {}
00121 
00122   template <class View0, class View1>
00123   forceinline
00124   DistinctDoit<View0,View1>::DistinctDoit(Space* home, bool share,
00125                                           DistinctDoit<View0,View1>& p)
00126     : UnaryPropagator<View0, PC_SET_ANY>(home,share,p) {
00127     y.update(home,share,p.y);
00128   }
00129 
00130 }}}
00131 
00132 // STATISTICS: set-prop