val.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Contributing authors: 00007 * Mikael Lagerkvist <lagerkvist@gecode.org> 00008 * 00009 * Copyright: 00010 * Christian Schulte, 2006 00011 * Mikael Lagerkvist, 2006 00012 * 00013 * Last modified: 00014 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00015 * $Revision: 10364 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 namespace Gecode { namespace Int { namespace Channel { 00043 00048 template<class View> 00049 class ValInfo { 00050 public: 00052 View view; 00054 bool a; 00056 void init(View x, int n); 00058 void update(Space& home, bool share, ValInfo<View>& vi); 00060 bool doval(void) const; 00062 bool dodom(void) const; 00064 void assigned(void); 00066 void removed(int i); 00068 void done(void); 00069 }; 00070 00071 template<class View> 00072 forceinline void 00073 ValInfo<View>::init(View x, int) { 00074 view = x; a = false; 00075 } 00076 00077 template<class View> 00078 forceinline void 00079 ValInfo<View>::update(Space& home, bool share, ValInfo<View>& vi) { 00080 view.update(home,share,vi.view); a = vi.a; 00081 } 00082 00083 template<class View> 00084 forceinline bool 00085 ValInfo<View>::doval(void) const { 00086 return !a && view.assigned(); 00087 } 00088 00089 template<class View> 00090 forceinline bool 00091 ValInfo<View>::dodom(void) const { 00092 return false; 00093 } 00094 00095 template<class View> 00096 forceinline void 00097 ValInfo<View>::assigned(void) { 00098 a = true; 00099 } 00100 00101 template<class View> 00102 forceinline void 00103 ValInfo<View>::removed(int) {} 00104 00105 template<class View> 00106 forceinline void 00107 ValInfo<View>::done(void) {} 00108 00109 00110 // Propagate assigned views for x 00111 template<class View, class Info> 00112 ExecStatus 00113 doprop_val(Space& home, int n, Info* x, Info* y, 00114 int& n_na, ProcessStack& xa, ProcessStack& ya) { 00115 do { 00116 int i = xa.pop(); 00117 int j = x[i].view.val(); 00118 // Assign the y variable to i (or test if already assigned!) 00119 { 00120 ModEvent me = y[j].view.eq(home,i); 00121 if (me_failed(me)) 00122 return ES_FAILED; 00123 // Record that y[j] has been assigned and must be propagated 00124 if (me_modified(me)) 00125 ya.push(j); 00126 } 00127 // Prune the value j from all x variables 00128 for (int k=i; k--; ) { 00129 ModEvent me = x[k].view.nq(home,j); 00130 if (me_failed(me)) 00131 return ES_FAILED; 00132 if (me_modified(me)) { 00133 if (me == ME_INT_VAL) { 00134 // Record that x[k] has been assigned and must be propagated 00135 xa.push(k); 00136 } else { 00137 // One value has been removed and this removal does not need 00138 // to be propagated again: after all y[j] = i, so it holds 00139 // that y[j] != k. 00140 x[k].removed(j); 00141 } 00142 } 00143 } 00144 // The same for the other views 00145 for (int k=i+1; k<n; k++) { 00146 ModEvent me = x[k].view.nq(home,j); 00147 if (me_failed(me)) 00148 return ES_FAILED; 00149 if (me_modified(me)) { 00150 if (me == ME_INT_VAL) { 00151 // Record that x[k] has been assigned and must be propagated 00152 xa.push(k); 00153 } else { 00154 // One value has been removed and this removal does not need 00155 // to be propagated again: after all y[j] = i, so it holds 00156 // that y[j] != k. 00157 x[k].removed(j); 00158 } 00159 } 00160 } 00161 x[i].assigned(); n_na--; 00162 } while (!xa.empty()); 00163 return ES_OK; 00164 } 00165 00166 // Just do a test whether a call to the routine is necessary 00167 template<class View, class Info> 00168 forceinline ExecStatus 00169 prop_val(Space& home, int n, Info* x, Info* y, 00170 int& n_na, ProcessStack& xa, ProcessStack& ya) { 00171 if (xa.empty()) 00172 return ES_OK; 00173 return doprop_val<View,Info>(home,n,x,y,n_na,xa,ya); 00174 } 00175 00176 /* 00177 * The actual propagator 00178 * 00179 */ 00180 template<class View, bool shared> 00181 forceinline 00182 Val<View,shared>::Val(Home home, int n, ValInfo<View>* xy) 00183 : Base<ValInfo<View>,PC_INT_VAL>(home,n,xy) {} 00184 00185 template<class View, bool shared> 00186 forceinline 00187 Val<View,shared>::Val(Space& home, bool share, Val<View,shared>& p) 00188 : Base<ValInfo<View>,PC_INT_VAL>(home,share,p) {} 00189 00190 template<class View, bool shared> 00191 Actor* 00192 Val<View,shared>::copy(Space& home, bool share) { 00193 return new (home) Val<View,shared>(home,share,*this); 00194 } 00195 00196 template<class View, bool shared> 00197 ExecStatus 00198 Val<View,shared>::propagate(Space& home, const ModEventDelta&) { 00199 Region r(home); 00200 ProcessStack xa(r,n); 00201 ProcessStack ya(r,n); 00202 00203 ValInfo<View>* x = xy; 00204 ValInfo<View>* y = xy+n; 00205 00206 // Scan x and y for assigned but not yet propagated views 00207 for (int i = n; i--; ) { 00208 if (x[i].doval()) xa.push(i); 00209 if (y[i].doval()) ya.push(i); 00210 } 00211 00212 do { 00213 // Propagate assigned views for x 00214 GECODE_ES_CHECK((prop_val<View,ValInfo<View> >(home,n,x,y,n_na,xa,ya))); 00215 // Propagate assigned views for y 00216 GECODE_ES_CHECK((prop_val<View,ValInfo<View> >(home,n,y,x,n_na,ya,xa))); 00217 assert(ya.empty()); 00218 } while (!xa.empty()); 00219 00220 if (n_na == 0) 00221 return home.ES_SUBSUMED(*this); 00222 return shared ? ES_NOFIX : ES_FIX; 00223 } 00224 00225 template<class View, bool shared> 00226 ExecStatus 00227 Val<View,shared>::post(Home home, int n, ValInfo<View>* xy) { 00228 assert(n > 0); 00229 if (n == 1) { 00230 GECODE_ME_CHECK(xy[0].view.eq(home,0)); 00231 GECODE_ME_CHECK(xy[1].view.eq(home,0)); 00232 return ES_OK; 00233 } 00234 for (int i=2*n; i--; ) { 00235 GECODE_ME_CHECK(xy[i].view.gq(home,0)); 00236 GECODE_ME_CHECK(xy[i].view.le(home,n)); 00237 } 00238 (void) new (home) Val<View,shared>(home,n,xy); 00239 return ES_OK; 00240 } 00241 00242 }}} 00243 00244 // STATISTICS: int-prop 00245