channel-bool.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 * 00006 * Copyright: 00007 * Guido Tack, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-10 11:36:44 +0100 (Wed, 10 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10387 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/int.hh> 00039 00040 namespace Gecode { namespace Set { namespace Int { 00041 00042 template<class View> 00043 template<class A> 00044 forceinline 00045 ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home, 00046 ChannelBool<View>& p, 00047 Council<A>& c, int index) 00048 : Advisor(home,p,c), idx(index) { 00049 if (idx == -1) 00050 p.y.subscribe(home,*this); 00051 else { 00052 p.x[idx].subscribe(home,*this); 00053 } 00054 } 00055 00056 template<class View> 00057 forceinline 00058 ChannelBool<View>::IndexAdvisor::IndexAdvisor(Space& home, bool share, 00059 IndexAdvisor& a) 00060 : Advisor(home,share,a), idx(a.idx) {} 00061 00062 template<class View> 00063 forceinline int 00064 ChannelBool<View>::IndexAdvisor::index(void) const { 00065 return idx; 00066 } 00067 00068 template<class View> 00069 template<class A> 00070 forceinline void 00071 ChannelBool<View>::IndexAdvisor::dispose(Space& home, Council<A>& c) { 00072 ChannelBool<View>& p = static_cast<ChannelBool<View>&>(propagator()); 00073 if (idx == -1) 00074 p.y.cancel(home,*this); 00075 else { 00076 p.x[idx].cancel(home,*this); 00077 } 00078 Advisor::dispose(home,c); 00079 } 00080 00081 template<class View> 00082 forceinline 00083 ChannelBool<View>::ChannelBool(Home home, 00084 ViewArray<Gecode::Int::BoolView>& x0, 00085 View y0) 00086 : Super(home,x0,y0), co(home), running(false) { 00087 bool assigned = false; 00088 for (int i=x.size(); i--;) { 00089 if (x[i].zero()) { 00090 assigned = true; 00091 SetDelta d; 00092 zeros.include(home, i, i, d); 00093 } else if (x[i].one()) { 00094 assigned = true; 00095 SetDelta d; 00096 ones.include(home, i, i, d); 00097 } else { 00098 (void) new (home) IndexAdvisor(home,*this,co,i); 00099 } 00100 } 00101 if (assigned) 00102 Gecode::Int::BoolView::schedule(home, *this, Gecode::Int::ME_BOOL_VAL); 00103 View::schedule(home, *this, y.assigned() ? ME_SET_VAL : ME_SET_BB); 00104 (void) new (home) IndexAdvisor(home,*this,co,-1); 00105 } 00106 00107 template<class View> 00108 forceinline 00109 ChannelBool<View>::ChannelBool(Space& home, bool share, ChannelBool& p) 00110 : Super(home,share,p), running(false) { 00111 co.update(home, share, p.co); 00112 } 00113 00114 template<class View> 00115 forceinline ExecStatus 00116 ChannelBool<View>::post(Home home, ViewArray<Gecode::Int::BoolView>& x, 00117 View y) { 00118 GECODE_ME_CHECK(y.intersect(home, 0, x.size()-1)); 00119 (void) new (home) ChannelBool(home,x,y); 00120 return ES_OK; 00121 } 00122 00123 template<class View> 00124 PropCost 00125 ChannelBool<View>::cost(const Space&, const ModEventDelta&) const { 00126 return PropCost::quadratic(PropCost::LO, x.size()+1); 00127 } 00128 00129 template<class View> 00130 forceinline size_t 00131 ChannelBool<View>::dispose(Space& home) { 00132 co.dispose(home); 00133 (void) Super::dispose(home); 00134 return sizeof(*this); 00135 } 00136 00137 template<class View> 00138 Actor* 00139 ChannelBool<View>::copy(Space& home, bool share) { 00140 return new (home) ChannelBool(home,share,*this); 00141 } 00142 00143 template<class View> 00144 ExecStatus 00145 ChannelBool<View>::propagate(Space& home, const ModEventDelta&) { 00146 running = true; 00147 if (zeros.size() > 0) { 00148 BndSetRanges zi(zeros); 00149 GECODE_ME_CHECK(y.excludeI(home, zi)); 00150 zeros.init(home); 00151 } 00152 if (ones.size() > 0) { 00153 BndSetRanges oi(ones); 00154 GECODE_ME_CHECK(y.includeI(home, oi)); 00155 ones.init(home); 00156 } 00157 running = false; 00158 00159 if (delta.glbMin() != 1 || delta.glbMax() != 0) { 00160 if (!delta.glbAny()) { 00161 for (int i=delta.glbMin(); i<=delta.glbMax(); i++) 00162 GECODE_ME_CHECK(x[i].one(home)); 00163 } else { 00164 GlbRanges<View> glb(y); 00165 for (Iter::Ranges::ToValues<GlbRanges<View> > gv(glb); gv(); ++gv) { 00166 GECODE_ME_CHECK(x[gv.val()].one(home)); 00167 } 00168 } 00169 } 00170 if (delta.lubMin() != 1 || delta.lubMax() != 0) { 00171 if (!delta.lubAny()) { 00172 for (int i=delta.lubMin(); i<=delta.lubMax(); i++) 00173 GECODE_ME_CHECK(x[i].zero(home)); 00174 } else { 00175 int cur = 0; 00176 for (LubRanges<View> lub(y); lub(); ++lub) { 00177 for (; cur < lub.min(); cur++) { 00178 GECODE_ME_CHECK(x[cur].zero(home)); 00179 } 00180 cur = lub.max() + 1; 00181 } 00182 for (; cur < x.size(); cur++) { 00183 GECODE_ME_CHECK(x[cur].zero(home)); 00184 } 00185 } 00186 } 00187 00188 new (&delta) SetDelta(); 00189 00190 return y.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX; 00191 } 00192 00193 template<class View> 00194 ExecStatus 00195 ChannelBool<View>::advise(Space& home, Advisor& _a, const Delta& _d) { 00196 IndexAdvisor& a = static_cast<IndexAdvisor&>(_a); 00197 const SetDelta& d = static_cast<const SetDelta&>(_d); 00198 00199 ModEvent me = View::modevent(d); 00200 int index = a.index(); 00201 if ( (running && index == -1 && me != ME_SET_VAL) 00202 || (index == -1 && me == ME_SET_CARD) ) { 00203 return ES_OK; 00204 } 00205 00206 if (index >= 0) { 00207 if (x[index].zero()) { 00208 SetDelta dummy; 00209 zeros.include(home, index, index, dummy); 00210 } else { 00211 assert(x[index].one()); 00212 SetDelta dummy; 00213 ones.include(home, index, index, dummy); 00214 } 00215 return home.ES_NOFIX_DISPOSE( co, a); 00216 } 00217 00218 if ((a.index() == -1) && Rel::testSetEventLB(me)) { 00219 if (d.glbAny()) { 00220 new (&delta) 00221 SetDelta(2,0, delta.lubMin(), delta.lubMax()); 00222 } else { 00223 if (delta.glbMin() == 1 && delta.glbMax() == 0) { 00224 new (&delta) 00225 SetDelta(d.glbMin(), d.glbMax(), 00226 delta.lubMin(), delta.lubMax()); 00227 } else { 00228 if (delta.glbMin() != 2 || delta.glbMax() != 0) { 00229 if ((delta.glbMin() <= d.glbMin() && delta.glbMax() >= d.glbMin()) 00230 || 00231 (delta.glbMin() <= d.glbMax() && delta.glbMax() >= d.glbMax()) 00232 ) { 00233 new (&delta) 00234 SetDelta(std::min(delta.glbMin(), d.glbMin()), 00235 std::max(delta.glbMax(), d.glbMax()), 00236 delta.lubMin(), delta.lubMax()); 00237 } else { 00238 new (&delta) 00239 SetDelta(2, 0, delta.lubMin(), delta.lubMax()); 00240 } 00241 } 00242 } 00243 } 00244 } 00245 if ((a.index() == -1) && Rel::testSetEventUB(me)) { 00246 if (d.lubAny()) { 00247 new (&delta) 00248 SetDelta(delta.glbMin(), delta.glbMax(), 2,0); 00249 } else { 00250 if (delta.lubMin() == 1 && delta.lubMax() == 0) { 00251 new (&delta) 00252 SetDelta(delta.glbMin(), delta.glbMax(), 00253 d.lubMin(), d.lubMax()); 00254 } else { 00255 if (delta.lubMin() != 2 || delta.lubMax() != 0) { 00256 if ((delta.lubMin() <= d.lubMin() && delta.lubMax() >= d.lubMin()) 00257 || 00258 (delta.lubMin() <= d.lubMax() && delta.lubMax() >= d.lubMax()) 00259 ) { 00260 new (&delta) 00261 SetDelta(delta.lubMin(), delta.lubMax(), 00262 std::min(delta.lubMin(), d.lubMin()), 00263 std::max(delta.lubMax(), d.lubMax()) 00264 ); 00265 } else { 00266 new (&delta) 00267 SetDelta(delta.glbMin(), delta.glbMax(), 2, 0); 00268 } 00269 } 00270 } 00271 } 00272 } 00273 00274 if (y.assigned()) 00275 return home.ES_NOFIX_DISPOSE( co, a); 00276 else 00277 return ES_NOFIX; 00278 } 00279 00280 }}} 00281 00282 // STATISTICS: set-prop