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