re-eq.hpp
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 * Bugfixes provided by: 00008 * Grégoire Dooms <dooms@info.ucl.ac.be> 00009 * 00010 * Copyright: 00011 * Guido Tack, 2004 00012 * Christian Schulte, 2004 00013 * 00014 * Last modified: 00015 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00016 * $Revision: 10364 $ 00017 * 00018 * This file is part of Gecode, the generic constraint 00019 * development environment: 00020 * http://www.gecode.org 00021 * 00022 * Permission is hereby granted, free of charge, to any person obtaining 00023 * a copy of this software and associated documentation files (the 00024 * "Software"), to deal in the Software without restriction, including 00025 * without limitation the rights to use, copy, modify, merge, publish, 00026 * distribute, sublicense, and/or sell copies of the Software, and to 00027 * permit persons to whom the Software is furnished to do so, subject to 00028 * the following conditions: 00029 * 00030 * The above copyright notice and this permission notice shall be 00031 * included in all copies or substantial portions of the Software. 00032 * 00033 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00034 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00035 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00036 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00037 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00038 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00039 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00040 * 00041 */ 00042 00043 namespace Gecode { namespace Set { namespace Rel { 00044 00045 template<class View0, class View1> 00046 forceinline 00047 ReEq<View0,View1>::ReEq(Home home, View0 y0, View1 y1, 00048 Gecode::Int::BoolView y2) 00049 : Propagator(home), x0(y0), x1(y1), b(y2) { 00050 b.subscribe(home,*this, Gecode::Int::PC_INT_VAL); 00051 x0.subscribe(home,*this, PC_SET_ANY); 00052 x1.subscribe(home,*this, PC_SET_ANY); 00053 } 00054 00055 template<class View0, class View1> 00056 forceinline 00057 ReEq<View0,View1>::ReEq(Space& home, bool share, ReEq& p) 00058 : Propagator(home,share,p) { 00059 x0.update(home,share,p.x0); 00060 x1.update(home,share,p.x1); 00061 b.update(home,share,p.b); 00062 } 00063 00064 template<class View0, class View1> 00065 PropCost 00066 ReEq<View0,View1>::cost(const Space&, const ModEventDelta&) const { 00067 return PropCost::ternary(PropCost::LO); 00068 } 00069 00070 template<class View0, class View1> 00071 forceinline size_t 00072 ReEq<View0,View1>::dispose(Space& home) { 00073 b.cancel(home,*this, Gecode::Int::PC_INT_VAL); 00074 x0.cancel(home,*this, PC_SET_ANY); 00075 x1.cancel(home,*this, PC_SET_ANY); 00076 (void) Propagator::dispose(home); 00077 return sizeof(*this); 00078 } 00079 00080 template<class View0, class View1> 00081 ExecStatus 00082 ReEq<View0,View1>::post(Home home, View0 x0, View1 x1, 00083 Gecode::Int::BoolView b) { 00084 (void) new (home) ReEq<View0,View1>(home,x0,x1,b); 00085 return ES_OK; 00086 } 00087 00088 template<class View0, class View1> 00089 Actor* 00090 ReEq<View0,View1>::copy(Space& home, bool share) { 00091 return new (home) ReEq<View0,View1>(home,share,*this); 00092 } 00093 00094 template<class View0, class View1> 00095 ExecStatus 00096 ReEq<View0,View1>::propagate(Space& home, const ModEventDelta&) { 00097 if (b.one()) 00098 GECODE_REWRITE(*this,(Eq<View0,View1>::post(home(*this),x0,x1))); 00099 if (b.zero()) 00100 GECODE_REWRITE(*this,(Distinct<View0,View1>::post(home(*this),x0,x1))); 00101 00102 if (x0.assigned() && x1.assigned()) { 00103 // directly test x0==x1 00104 GlbRanges<View0> x0lb(x0); 00105 GlbRanges<View1> x1lb(x1); 00106 for (; x0lb() && x1lb(); ++x0lb, ++x1lb) { 00107 if (x0lb.min() != x1lb.min() || 00108 x0lb.max() != x1lb.max()) { 00109 GECODE_ME_CHECK(b.zero_none(home)); 00110 return home.ES_SUBSUMED(*this); 00111 } 00112 } 00113 if (!x0lb() && !x1lb()) { 00114 GECODE_ME_CHECK(b.one_none(home)); 00115 return home.ES_SUBSUMED(*this); 00116 } else { 00117 GECODE_ME_CHECK(b.zero_none(home)); 00118 return home.ES_SUBSUMED(*this); 00119 } 00120 } 00121 00122 // check whether cardinalities still allow equality 00123 if (x0.cardMin() > x1.cardMax() || 00124 x1.cardMin() > x0.cardMax()) { 00125 GECODE_ME_CHECK(b.zero_none(home)); 00126 return home.ES_SUBSUMED(*this); 00127 } 00128 00129 // check glb(x0) subset lub(x1) 00130 GlbRanges<View0> x0lb(x0); 00131 LubRanges<View1> x1ub(x1); 00132 Iter::Ranges::Diff<GlbRanges<View0>, LubRanges<View1> > diff1(x0lb, x1ub); 00133 if ( diff1() ) { 00134 GECODE_ME_CHECK(b.zero_none(home)); 00135 return home.ES_SUBSUMED(*this); 00136 } 00137 00138 // check glb(x1) subset lub(x0) 00139 GlbRanges<View1> x1lb(x1); 00140 LubRanges<View0> x0ub(x0); 00141 Iter::Ranges::Diff<GlbRanges<View1>, LubRanges<View0> > diff2(x1lb, x0ub); 00142 if ( diff2() ) { 00143 GECODE_ME_CHECK(b.zero_none(home)); 00144 return home.ES_SUBSUMED(*this); 00145 } 00146 00147 return ES_FIX; 00148 } 00149 00150 }}} 00151 00152 // STATISTICS: set-prop