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-09-01 12:35:28 +0200 (Wed, 01 Sep 2010) $ by $Author: zayenz $ 00013 * $Revision: 11372 $ 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 BranchFilter bf; 00087 Pos pos(Space& home); 00089 typename ViewSel::View view(const Pos& p) const; 00091 ViewBrancher(Space& home, bool share, ViewBrancher& b); 00093 ViewBrancher(Home home, ViewArray<typename ViewSel::View>& x, 00094 ViewSel& vi_s, BranchFilter bf0=NULL); 00095 public: 00097 virtual bool status(const Space& home) const; 00099 virtual size_t dispose(Space& home); 00100 }; 00101 00102 00112 template<class ViewSel, class ValSel> 00113 class ViewValBrancher : public ViewBrancher<ViewSel> { 00114 protected: 00115 using ViewBrancher<ViewSel>::viewsel; 00116 using ViewBrancher<ViewSel>::x; 00118 ValSel valsel; 00120 ViewValBrancher(Space& home, bool share, ViewValBrancher& b); 00122 ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x, 00123 ViewSel& vi_s, ValSel& va_s, BranchFilter bf0); 00124 public: 00126 virtual const Choice* choice(Space& home); 00128 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a); 00130 virtual Actor* copy(Space& home, bool share); 00132 virtual size_t dispose(Space& home); 00134 static void post(Home home, ViewArray<typename ViewSel::View>& x, 00135 ViewSel& vi_s, ValSel& va_s, BranchFilter bf=NULL); 00136 00137 }; 00138 00139 00141 template<class ViewSel> 00142 class GECODE_VTABLE_EXPORT PosChoice : public Choice { 00143 private: 00145 const Pos _pos; 00147 const typename ViewSel::Choice _viewchoice; 00148 public: 00150 PosChoice(const Brancher& b, unsigned int a, const Pos& p, 00151 const typename ViewSel::Choice& viewc); 00153 const Pos& pos(void) const; 00155 const typename ViewSel::Choice& viewchoice(void) const; 00157 virtual size_t size(void) const; 00158 }; 00159 00161 template<class ViewSel, class ValSel> 00162 class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice<ViewSel> { 00163 private: 00165 const typename ValSel::Choice _valchoice; 00167 const typename ValSel::Val _val; 00168 public: 00170 PosValChoice(const Brancher& b, const Pos& p, 00171 const typename ViewSel::Choice& viewc, 00172 const typename ValSel::Choice& valc, 00173 const typename ValSel::Val& n); 00175 const typename ValSel::Choice& valchoice(void) const; 00177 const typename ValSel::Val& val(void) const; 00179 virtual size_t size(void) const; 00180 }; 00182 00183 00184 00185 00186 /* 00187 * Position information 00188 * 00189 */ 00190 forceinline 00191 Pos::Pos(int p) : pos(p) {} 00192 00193 00194 /* 00195 * Choice with position 00196 * 00197 */ 00198 template<class ViewSel> 00199 forceinline 00200 PosChoice<ViewSel>::PosChoice(const Brancher& b, unsigned int a, 00201 const Pos& p, 00202 const typename ViewSel::Choice& viewc) 00203 : Choice(b,a), _pos(p), _viewchoice(viewc) {} 00204 template<class ViewSel> 00205 forceinline const Pos& 00206 PosChoice<ViewSel>::pos(void) const { 00207 return _pos; 00208 } 00209 template<class ViewSel> 00210 forceinline const typename ViewSel::Choice& 00211 PosChoice<ViewSel>::viewchoice(void) const { 00212 return _viewchoice; 00213 } 00214 template<class ViewSel> 00215 forceinline size_t 00216 PosChoice<ViewSel>::size(void) const { 00217 return sizeof(PosChoice<ViewSel>) + _viewchoice.size(); 00218 } 00219 00220 00221 /* 00222 * %Choice with position and value 00223 * 00224 */ 00225 template<class ViewSel, class ValSel> 00226 forceinline 00227 PosValChoice<ViewSel,ValSel> 00228 ::PosValChoice(const Brancher& b, const Pos& p, 00229 const typename ViewSel::Choice& viewc, 00230 const typename ValSel::Choice& valc, 00231 const typename ValSel::Val& n) 00232 : PosChoice<ViewSel>(b,ValSel::alternatives,p,viewc), 00233 _valchoice(valc), _val(n) {} 00234 00235 template<class ViewSel, class ValSel> 00236 forceinline const typename ValSel::Choice& 00237 PosValChoice<ViewSel,ValSel>::valchoice(void) const { 00238 return _valchoice; 00239 } 00240 00241 template<class ViewSel, class ValSel> 00242 forceinline const typename ValSel::Val& 00243 PosValChoice<ViewSel,ValSel>::val(void) const { 00244 return _val; 00245 } 00246 00247 template<class ViewSel, class ValSel> 00248 forceinline size_t 00249 PosValChoice<ViewSel, ValSel>::size(void) const { 00250 return sizeof(PosValChoice<ViewSel,ValSel>) + _valchoice.size(); 00251 } 00252 00253 00254 /* 00255 * Generic brancher based on view selection 00256 * 00257 */ 00258 00259 template<class ViewSel> 00260 forceinline 00261 ViewBrancher<ViewSel>::ViewBrancher(Home home, 00262 ViewArray<typename ViewSel::View>& x0, 00263 ViewSel& vi_s, BranchFilter bf0) 00264 : Brancher(home), x(x0), start(0), viewsel(vi_s), bf(bf0) {} 00265 00266 00267 template<class ViewSel> 00268 forceinline 00269 ViewBrancher<ViewSel>::ViewBrancher(Space& home, bool share, 00270 ViewBrancher& b) 00271 : Brancher(home,share,b), start(b.start), bf(b.bf) { 00272 x.update(home,share,b.x); 00273 viewsel.update(home,share,b.viewsel); 00274 } 00275 00276 template<class ViewSel> 00277 bool 00278 ViewBrancher<ViewSel>::status(const Space& home) const { 00279 if (bf == NULL) { 00280 for (int i=start; i < x.size(); i++) 00281 if (!x[i].assigned()) { 00282 start = i; 00283 return true; 00284 } 00285 } else { 00286 for (int i=start; i < x.size(); i++) { 00287 typename ViewSel::View::VarType y(x[i].varimp()); 00288 if (!x[i].assigned() && bf(home,i,y)) { 00289 start = i; 00290 return true; 00291 } 00292 } 00293 } 00294 return false; 00295 } 00296 00297 template<class ViewSel> 00298 forceinline Pos 00299 ViewBrancher<ViewSel>::pos(Space& home) { 00300 assert(!x[start].assigned()); 00301 int i = start; 00302 int b = i++; 00303 if (viewsel.init(home,x[b]) != VSS_BEST) 00304 for (; i < x.size(); i++) 00305 if (!x[i].assigned()) 00306 switch (viewsel.select(home,x[i])) { 00307 case VSS_BETTER: b=i; break; 00308 case VSS_BEST: b=i; goto create; 00309 case VSS_TIE: case VSS_WORSE: break; 00310 default: GECODE_NEVER; 00311 } 00312 create: 00313 Pos p(b); 00314 return p; 00315 } 00316 00317 template<class ViewSel> 00318 forceinline typename ViewSel::View 00319 ViewBrancher<ViewSel>::view(const Pos& p) const { 00320 return x[p.pos]; 00321 } 00322 00323 template<class ViewSel> 00324 forceinline size_t 00325 ViewBrancher<ViewSel>::dispose(Space& home) { 00326 viewsel.dispose(home); 00327 (void) Brancher::dispose(home); 00328 return sizeof(ViewBrancher<ViewSel>); 00329 } 00330 00331 00332 00333 /* 00334 * Generic brancher based on variable/value selection 00335 * 00336 */ 00337 00338 template<class ViewSel, class ValSel> 00339 forceinline 00340 ViewValBrancher<ViewSel,ValSel>:: 00341 ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x, 00342 ViewSel& vi_s, ValSel& va_s, BranchFilter bf) 00343 : ViewBrancher<ViewSel>(home,x,vi_s,bf), valsel(va_s) {} 00344 00345 template<class ViewSel, class ValSel> 00346 void 00347 ViewValBrancher<ViewSel,ValSel>:: 00348 post(Home home, ViewArray<typename ViewSel::View>& x, 00349 ViewSel& vi_s, ValSel& va_s, BranchFilter bf) { 00350 (void) new (home) ViewValBrancher<ViewSel,ValSel>(home,x,vi_s,va_s,bf); 00351 } 00352 00353 template<class ViewSel, class ValSel> 00354 forceinline 00355 ViewValBrancher<ViewSel,ValSel>:: 00356 ViewValBrancher(Space& home, bool share, ViewValBrancher& b) 00357 : ViewBrancher<ViewSel>(home,share,b) { 00358 valsel.update(home,share,b.valsel); 00359 } 00360 00361 template<class ViewSel, class ValSel> 00362 Actor* 00363 ViewValBrancher<ViewSel,ValSel>::copy(Space& home, bool share) { 00364 return new (home) 00365 ViewValBrancher<ViewSel,ValSel>(home,share,*this); 00366 } 00367 00368 template<class ViewSel, class ValSel> 00369 const Choice* 00370 ViewValBrancher<ViewSel,ValSel>::choice(Space& home) { 00371 Pos p = ViewBrancher<ViewSel>::pos(home); 00372 typename ValSel::View v(ViewBrancher<ViewSel>::view(p).varimp()); 00373 typename ValSel::Val val(valsel.val(home,v)); 00374 return new PosValChoice<ViewSel,ValSel> 00375 (*this,p, 00376 viewsel.choice(home),valsel.choice(home),val); 00377 } 00378 00379 template<class ViewSel, class ValSel> 00380 ExecStatus 00381 ViewValBrancher<ViewSel,ValSel> 00382 ::commit(Space& home, const Choice& c, unsigned int a) { 00383 const PosValChoice<ViewSel,ValSel>& pvc 00384 = static_cast<const PosValChoice<ViewSel,ValSel>&>(c); 00385 typename ValSel::View 00386 v(ViewBrancher<ViewSel>::view(pvc.pos()).varimp()); 00387 viewsel.commit(home, pvc.viewchoice(), a); 00388 valsel.commit(home, pvc.valchoice(), a); 00389 return me_failed(valsel.tell(home,a,v,pvc.val())) ? ES_FAILED : ES_OK; 00390 } 00391 00392 template<class ViewSel, class ValSel> 00393 forceinline size_t 00394 ViewValBrancher<ViewSel,ValSel>::dispose(Space& home) { 00395 valsel.dispose(home); 00396 (void) ViewBrancher<ViewSel>::dispose(home); 00397 return sizeof(ViewValBrancher<ViewSel,ValSel>); 00398 } 00399 00400 } 00401 00402 // STATISTICS: kernel-branch