brancher.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 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2004 00009 * Guido Tack, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2010-06-03 13:46:55 +0200 (Thu, 03 Jun 2010) $ by $Author: schulte $ 00013 * $Revision: 11014 $ 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 { 00041 00050 00051 enum ViewSelStatus { 00052 VSS_BEST, 00053 VSS_BETTER, 00054 VSS_TIE, 00055 VSS_WORSE 00056 }; 00057 00059 class Pos { 00060 public: 00062 const int pos; 00064 Pos(int p); 00065 }; 00066 00075 template<class ViewSel> 00076 class ViewBrancher : public Brancher { 00077 protected: 00079 ViewArray<typename ViewSel::View> x; 00081 mutable int start; 00083 ViewSel viewsel; 00085 Pos pos(Space& home); 00087 typename ViewSel::View view(const Pos& p) const; 00089 ViewBrancher(Space& home, bool share, ViewBrancher& b); 00091 ViewBrancher(Home home, ViewArray<typename ViewSel::View>& x, 00092 ViewSel& vi_s); 00093 public: 00095 virtual bool status(const Space& home) const; 00097 virtual size_t dispose(Space& home); 00098 }; 00099 00100 00110 template<class ViewSel, class ValSel> 00111 class ViewValBrancher : public ViewBrancher<ViewSel> { 00112 protected: 00113 using ViewBrancher<ViewSel>::viewsel; 00114 using ViewBrancher<ViewSel>::x; 00116 ValSel valsel; 00118 ViewValBrancher(Space& home, bool share, ViewValBrancher& b); 00120 ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x, 00121 ViewSel& vi_s, ValSel& va_s); 00122 public: 00124 virtual const Choice* choice(Space& home); 00126 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a); 00128 virtual Actor* copy(Space& home, bool share); 00130 virtual size_t dispose(Space& home); 00132 static void post(Home home, ViewArray<typename ViewSel::View>& x, 00133 ViewSel& vi_s, ValSel& va_s); 00134 00135 }; 00136 00137 00139 template<class ViewSel> 00140 class GECODE_VTABLE_EXPORT PosChoice : public Choice { 00141 private: 00143 const Pos _pos; 00145 const typename ViewSel::Choice _viewchoice; 00146 public: 00148 PosChoice(const Brancher& b, unsigned int a, const Pos& p, 00149 const typename ViewSel::Choice& viewc); 00151 const Pos& pos(void) const; 00153 const typename ViewSel::Choice& viewchoice(void) const; 00155 virtual size_t size(void) const; 00156 }; 00157 00159 template<class ViewSel, class ValSel> 00160 class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice<ViewSel> { 00161 private: 00163 const typename ValSel::Choice _valchoice; 00165 const typename ValSel::Val _val; 00166 public: 00168 PosValChoice(const Brancher& b, const Pos& p, 00169 const typename ViewSel::Choice& viewc, 00170 const typename ValSel::Choice& valc, 00171 const typename ValSel::Val& n); 00173 const typename ValSel::Choice& valchoice(void) const; 00175 const typename ValSel::Val& val(void) const; 00177 virtual size_t size(void) const; 00178 }; 00180 00181 00182 00183 00184 /* 00185 * Position information 00186 * 00187 */ 00188 forceinline 00189 Pos::Pos(int p) : pos(p) {} 00190 00191 00192 /* 00193 * Choice with position 00194 * 00195 */ 00196 template<class ViewSel> 00197 forceinline 00198 PosChoice<ViewSel>::PosChoice(const Brancher& b, unsigned int a, 00199 const Pos& p, 00200 const typename ViewSel::Choice& viewc) 00201 : Choice(b,a), _pos(p), _viewchoice(viewc) {} 00202 template<class ViewSel> 00203 forceinline const Pos& 00204 PosChoice<ViewSel>::pos(void) const { 00205 return _pos; 00206 } 00207 template<class ViewSel> 00208 forceinline const typename ViewSel::Choice& 00209 PosChoice<ViewSel>::viewchoice(void) const { 00210 return _viewchoice; 00211 } 00212 template<class ViewSel> 00213 forceinline size_t 00214 PosChoice<ViewSel>::size(void) const { 00215 return sizeof(PosChoice<ViewSel>) + _viewchoice.size(); 00216 } 00217 00218 00219 /* 00220 * %Choice with position and value 00221 * 00222 */ 00223 template<class ViewSel, class ValSel> 00224 forceinline 00225 PosValChoice<ViewSel,ValSel> 00226 ::PosValChoice(const Brancher& b, const Pos& p, 00227 const typename ViewSel::Choice& viewc, 00228 const typename ValSel::Choice& valc, 00229 const typename ValSel::Val& n) 00230 : PosChoice<ViewSel>(b,ValSel::alternatives,p,viewc), 00231 _valchoice(valc), _val(n) {} 00232 00233 template<class ViewSel, class ValSel> 00234 forceinline const typename ValSel::Choice& 00235 PosValChoice<ViewSel,ValSel>::valchoice(void) const { 00236 return _valchoice; 00237 } 00238 00239 template<class ViewSel, class ValSel> 00240 forceinline const typename ValSel::Val& 00241 PosValChoice<ViewSel,ValSel>::val(void) const { 00242 return _val; 00243 } 00244 00245 template<class ViewSel, class ValSel> 00246 forceinline size_t 00247 PosValChoice<ViewSel, ValSel>::size(void) const { 00248 return sizeof(PosValChoice<ViewSel,ValSel>) + _valchoice.size(); 00249 } 00250 00251 00252 /* 00253 * Generic brancher based on view selection 00254 * 00255 */ 00256 00257 template<class ViewSel> 00258 forceinline 00259 ViewBrancher<ViewSel>::ViewBrancher(Home home, 00260 ViewArray<typename ViewSel::View>& x0, 00261 ViewSel& vi_s) 00262 : Brancher(home), x(x0), start(0), viewsel(vi_s) {} 00263 00264 00265 template<class ViewSel> 00266 forceinline 00267 ViewBrancher<ViewSel>::ViewBrancher(Space& home, bool share, 00268 ViewBrancher& b) 00269 : Brancher(home,share,b), start(b.start) { 00270 x.update(home,share,b.x); 00271 viewsel.update(home,share,b.viewsel); 00272 } 00273 00274 template<class ViewSel> 00275 bool 00276 ViewBrancher<ViewSel>::status(const Space&) const { 00277 for (int i=start; i < x.size(); i++) 00278 if (!x[i].assigned()) { 00279 start = i; 00280 return true; 00281 } 00282 return false; 00283 } 00284 00285 template<class ViewSel> 00286 forceinline Pos 00287 ViewBrancher<ViewSel>::pos(Space& home) { 00288 assert(!x[start].assigned()); 00289 int i = start; 00290 int b = i++; 00291 if (viewsel.init(home,x[b]) != VSS_BEST) 00292 for (; i < x.size(); i++) 00293 if (!x[i].assigned()) 00294 switch (viewsel.select(home,x[i])) { 00295 case VSS_BETTER: b=i; break; 00296 case VSS_BEST: b=i; goto create; 00297 case VSS_TIE: case VSS_WORSE: break; 00298 default: GECODE_NEVER; 00299 } 00300 create: 00301 Pos p(b); 00302 return p; 00303 } 00304 00305 template<class ViewSel> 00306 forceinline typename ViewSel::View 00307 ViewBrancher<ViewSel>::view(const Pos& p) const { 00308 return x[p.pos]; 00309 } 00310 00311 template<class ViewSel> 00312 forceinline size_t 00313 ViewBrancher<ViewSel>::dispose(Space& home) { 00314 viewsel.dispose(home); 00315 (void) Brancher::dispose(home); 00316 return sizeof(ViewBrancher<ViewSel>); 00317 } 00318 00319 00320 00321 /* 00322 * Generic brancher based on variable/value selection 00323 * 00324 */ 00325 00326 template<class ViewSel, class ValSel> 00327 forceinline 00328 ViewValBrancher<ViewSel,ValSel>:: 00329 ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x, 00330 ViewSel& vi_s, ValSel& va_s) 00331 : ViewBrancher<ViewSel>(home,x,vi_s), valsel(va_s) {} 00332 00333 template<class ViewSel, class ValSel> 00334 void 00335 ViewValBrancher<ViewSel,ValSel>:: 00336 post(Home home, ViewArray<typename ViewSel::View>& x, 00337 ViewSel& vi_s, ValSel& va_s) { 00338 (void) new (home) ViewValBrancher<ViewSel,ValSel>(home,x,vi_s,va_s); 00339 } 00340 00341 template<class ViewSel, class ValSel> 00342 forceinline 00343 ViewValBrancher<ViewSel,ValSel>:: 00344 ViewValBrancher(Space& home, bool share, ViewValBrancher& b) 00345 : ViewBrancher<ViewSel>(home,share,b) { 00346 valsel.update(home,share,b.valsel); 00347 } 00348 00349 template<class ViewSel, class ValSel> 00350 Actor* 00351 ViewValBrancher<ViewSel,ValSel>::copy(Space& home, bool share) { 00352 return new (home) 00353 ViewValBrancher<ViewSel,ValSel>(home,share,*this); 00354 } 00355 00356 template<class ViewSel, class ValSel> 00357 const Choice* 00358 ViewValBrancher<ViewSel,ValSel>::choice(Space& home) { 00359 Pos p = ViewBrancher<ViewSel>::pos(home); 00360 typename ValSel::View v(ViewBrancher<ViewSel>::view(p).varimp()); 00361 typename ValSel::Val val(valsel.val(home,v)); 00362 return new PosValChoice<ViewSel,ValSel> 00363 (*this,p, 00364 viewsel.choice(home),valsel.choice(home),val); 00365 } 00366 00367 template<class ViewSel, class ValSel> 00368 ExecStatus 00369 ViewValBrancher<ViewSel,ValSel> 00370 ::commit(Space& home, const Choice& c, unsigned int a) { 00371 const PosValChoice<ViewSel,ValSel>& pvc 00372 = static_cast<const PosValChoice<ViewSel,ValSel>&>(c); 00373 typename ValSel::View 00374 v(ViewBrancher<ViewSel>::view(pvc.pos()).varimp()); 00375 viewsel.commit(home, pvc.viewchoice(), a); 00376 valsel.commit(home, pvc.valchoice(), a); 00377 return me_failed(valsel.tell(home,a,v,pvc.val())) ? ES_FAILED : ES_OK; 00378 } 00379 00380 template<class ViewSel, class ValSel> 00381 forceinline size_t 00382 ViewValBrancher<ViewSel,ValSel>::dispose(Space& home) { 00383 valsel.dispose(home); 00384 (void) ViewBrancher<ViewSel>::dispose(home); 00385 return sizeof(ViewValBrancher<ViewSel,ValSel>); 00386 } 00387 00388 } 00389 00390 // STATISTICS: kernel-branch