brancher-tiebreak.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main author: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2008 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00011 * $Revision: 10684 $ 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 namespace Gecode { 00039 00049 template<class A, class B> 00050 class ViewSelTieBreakStatic { 00051 protected: 00053 A a; 00055 B b; 00056 public: 00058 typedef typename A::View View; 00060 class Choice { 00061 public: 00063 typename A::Choice a; 00065 typename B::Choice b; 00067 Choice(const typename A::Choice& a, const typename B::Choice& b); 00069 size_t size(void) const; 00070 }; 00072 ViewSelTieBreakStatic(void); 00074 ViewSelTieBreakStatic(Space& home, A& a, B& b); 00076 ViewSelStatus init(Space& home, typename A::View x); 00078 ViewSelStatus select(Space& home, typename A::View x); 00080 Choice choice(Space& home); 00082 void commit(Space& home, const Choice& c, unsigned int a); 00084 void update(Space& home, bool share, ViewSelTieBreakStatic& vs); 00086 void dispose(Space& home); 00087 }; 00088 00092 class ChoiceVirtualBase { 00093 public: 00095 virtual ChoiceVirtualBase* copy(void) const = 0; 00097 virtual size_t size(void) const = 0; 00099 GECODE_KERNEL_EXPORT virtual ~ChoiceVirtualBase(void); 00101 00102 00103 static void* operator new(size_t s); 00105 static void operator delete(void*); 00107 }; 00108 00112 template<class View> 00113 class ViewSelVirtualBase { 00114 public: 00116 virtual ViewSelStatus init(Space& home, View x) = 0; 00118 virtual ViewSelStatus select(Space& home, View x) = 0; 00120 virtual ChoiceVirtualBase* choice(Space& home) = 0; 00122 virtual void commit(Space& home, const ChoiceVirtualBase* c, 00123 unsigned int a) = 0; 00125 virtual ViewSelVirtualBase<View>* copy(Space& home, bool share) = 0; 00127 virtual size_t dispose(Space& home) = 0; 00129 00130 00131 static void* operator new(size_t s, Space& home); 00133 static void operator delete(void* p, Space& home); 00135 static void operator delete(void*); 00137 }; 00138 00142 template<class Choice> 00143 class ChoiceVirtual : public ChoiceVirtualBase { 00144 public: 00146 Choice choice; 00148 ChoiceVirtual(const Choice& c); 00150 virtual ChoiceVirtualBase* copy(void) const; 00152 virtual size_t size(void) const; 00154 virtual ~ChoiceVirtual(void); 00155 }; 00156 00160 template<class ViewSel> 00161 class ViewSelVirtual : public ViewSelVirtualBase<typename ViewSel::View> { 00162 protected: 00164 ViewSel viewsel; 00165 public: 00167 ViewSelVirtual(Space& home, const VarBranchOptions& vbo); 00169 ViewSelVirtual(Space& home, bool share, ViewSelVirtual& vsv); 00171 virtual ViewSelStatus init(Space& home, typename ViewSel::View x); 00173 virtual ViewSelStatus select(Space& home, typename ViewSel::View x); 00175 virtual ChoiceVirtualBase* choice(Space& home); 00177 virtual void commit(Space& home, const ChoiceVirtualBase* d, 00178 unsigned int a); 00180 virtual ViewSelVirtualBase<typename ViewSel::View>* 00181 copy(Space& home, bool share); 00183 virtual size_t dispose(Space& home); 00184 }; 00185 00189 template<class _View> 00190 class ViewSelTieBreakDynamic { 00191 protected: 00193 int n; 00195 ViewSelVirtualBase<_View>** tb; 00196 public: 00198 typedef _View View; 00200 class Choice { 00201 public: 00203 int n; 00205 ChoiceVirtualBase** c; 00207 Choice(Space& home, ViewSelVirtualBase<_View>** tb, int n0); 00209 Choice(const Choice& ce); 00211 const Choice& operator =(const Choice& ce); 00213 void commit(Space& home, unsigned int a, 00214 ViewSelVirtualBase<_View>** tb) const; 00216 size_t size(void) const; 00218 ~Choice(void); 00219 }; 00221 ViewSelTieBreakDynamic(void); 00223 ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<_View>** vsv, 00224 int n); 00226 ViewSelStatus init(Space& home, _View x); 00228 ViewSelStatus select(Space& home, _View x); 00230 Choice choice(Space& home); 00232 void commit(Space& home, 00233 const typename ViewSelTieBreakDynamic<_View>::Choice& c, 00234 unsigned int a); 00236 void update(Space& home, bool share, ViewSelTieBreakDynamic& vs); 00238 void dispose(Space& home); 00239 }; 00241 00242 00243 // Select variable with static tie breaking 00244 template<class A, class B> 00245 forceinline 00246 ViewSelTieBreakStatic<A,B>::Choice::Choice(const typename A::Choice& a0, 00247 const typename B::Choice& b0) 00248 : a(a0), b(b0) {} 00249 template<class A, class B> 00250 forceinline size_t 00251 ViewSelTieBreakStatic<A,B>::Choice::size(void) const { 00252 return a.size() + b.size(); 00253 } 00254 00255 template<class A, class B> 00256 forceinline 00257 ViewSelTieBreakStatic<A,B>::ViewSelTieBreakStatic(void) {} 00258 template<class A, class B> 00259 forceinline 00260 ViewSelTieBreakStatic<A,B>:: 00261 ViewSelTieBreakStatic(Space&, A& a0, B& b0) 00262 : a(a0), b(b0) {} 00263 template<class A, class B> 00264 forceinline ViewSelStatus 00265 ViewSelTieBreakStatic<A,B>::init(Space& home, typename A::View x) { 00266 ViewSelStatus s = a.init(home,x); 00267 return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : s; 00268 } 00269 template<class A, class B> 00270 forceinline ViewSelStatus 00271 ViewSelTieBreakStatic<A,B>::select(Space& home, typename A::View x) { 00272 switch (a.select(home,x)) { 00273 case VSS_BEST: 00274 return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : VSS_BEST; 00275 case VSS_BETTER: 00276 (void) b.init(home,x); 00277 return VSS_BETTER; 00278 case VSS_WORSE: 00279 return VSS_WORSE; 00280 case VSS_TIE: 00281 switch (b.select(home,x)) { 00282 case VSS_BEST: return VSS_BETTER; 00283 case VSS_BETTER: return VSS_BETTER; 00284 case VSS_TIE: return VSS_TIE; 00285 case VSS_WORSE: return VSS_WORSE; 00286 default: GECODE_NEVER; 00287 } 00288 default: GECODE_NEVER; 00289 return VSS_WORSE; 00290 } 00291 } 00292 template<class A, class B> 00293 inline typename ViewSelTieBreakStatic<A,B>::Choice 00294 ViewSelTieBreakStatic<A,B>::choice(Space& home) { 00295 typename ViewSelTieBreakStatic<A,B>::Choice c(a.choice(home), 00296 b.choice(home)); 00297 return c; 00298 } 00299 template<class A, class B> 00300 forceinline void 00301 ViewSelTieBreakStatic<A,B>::commit(Space& home, const Choice& c, 00302 unsigned int al) { 00303 a.commit(home, c.a, al); 00304 b.commit(home, c.b, al); 00305 } 00306 template<class A, class B> 00307 forceinline void 00308 ViewSelTieBreakStatic<A,B>::update(Space& home, bool share, 00309 ViewSelTieBreakStatic<A,B>& vstb) { 00310 a.update(home,share,vstb.a); 00311 b.update(home,share,vstb.b); 00312 } 00313 template<class A, class B> 00314 forceinline void 00315 ViewSelTieBreakStatic<A,B>::dispose(Space& home) { 00316 a.dispose(home); 00317 b.dispose(home); 00318 } 00319 00320 00321 // Virtualized view selection 00322 template<class View> 00323 forceinline void 00324 ViewSelVirtualBase<View>::operator delete(void*) {} 00325 template<class View> 00326 forceinline void 00327 ViewSelVirtualBase<View>::operator delete(void*, Space&) {} 00328 template<class View> 00329 forceinline void* 00330 ViewSelVirtualBase<View>::operator new(size_t s, Space& home) { 00331 return home.ralloc(s); 00332 } 00333 00334 // Virtualized choice 00335 forceinline void 00336 ChoiceVirtualBase::operator delete(void* p) { 00337 heap.rfree(p); 00338 } 00339 forceinline void* 00340 ChoiceVirtualBase::operator new(size_t s) { 00341 return heap.ralloc(s); 00342 } 00343 forceinline 00344 ChoiceVirtualBase::~ChoiceVirtualBase(void) { 00345 } 00346 00347 00348 template<class Choice> 00349 forceinline 00350 ChoiceVirtual<Choice>::ChoiceVirtual(const Choice& c) 00351 : choice(c) {} 00352 template<class Choice> 00353 forceinline ChoiceVirtualBase* 00354 ChoiceVirtual<Choice>::copy(void) const { 00355 return new ChoiceVirtual<Choice>(choice); 00356 } 00357 template<class Choice> 00358 forceinline size_t 00359 ChoiceVirtual<Choice>::size(void) const { 00360 return sizeof(ChoiceVirtual<Choice>); 00361 } 00362 template<class Choice> 00363 ChoiceVirtual<Choice>::~ChoiceVirtual(void) {} 00364 00365 00366 template<class ViewSel> 00367 forceinline 00368 ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home, 00369 const VarBranchOptions& vbo) 00370 : viewsel(home,vbo) {} 00371 template<class ViewSel> 00372 forceinline 00373 ViewSelVirtual<ViewSel>::ViewSelVirtual(Space& home, bool share, 00374 ViewSelVirtual<ViewSel>& vsv) { 00375 viewsel.update(home,share,vsv.viewsel); 00376 } 00377 template<class ViewSel> 00378 ViewSelStatus 00379 ViewSelVirtual<ViewSel>::init(Space& home, typename ViewSel::View x) { 00380 return viewsel.init(home,x); 00381 } 00382 template<class ViewSel> 00383 ViewSelStatus 00384 ViewSelVirtual<ViewSel>::select(Space& home, typename ViewSel::View x) { 00385 return viewsel.select(home,x); 00386 } 00387 template<class ViewSel> 00388 ChoiceVirtualBase* 00389 ViewSelVirtual<ViewSel>::choice(Space& home) { 00390 return new ChoiceVirtual<typename ViewSel::Choice>(viewsel.choice(home)); 00391 } 00392 template<class ViewSel> 00393 void 00394 ViewSelVirtual<ViewSel>::commit(Space& home, const ChoiceVirtualBase* _c, 00395 unsigned int a) { 00396 const ChoiceVirtual<typename ViewSel::Choice>* c = 00397 static_cast<const ChoiceVirtual<typename ViewSel::Choice>*>(_c); 00398 viewsel.commit(home, c->choice, a); 00399 } 00400 template<class ViewSel> 00401 ViewSelVirtualBase<typename ViewSel::View>* 00402 ViewSelVirtual<ViewSel>::copy(Space& home, bool share) { 00403 return new (home) ViewSelVirtual<ViewSel>(home,share,*this); 00404 } 00405 template<class ViewSel> 00406 size_t 00407 ViewSelVirtual<ViewSel>::dispose(Space& home) { 00408 viewsel.dispose(home); 00409 return sizeof(ViewSelVirtual<ViewSel>); 00410 } 00411 00412 00413 // Choice for dynamic tie breaking 00414 template<class View> 00415 forceinline 00416 ViewSelTieBreakDynamic<View>::Choice::Choice 00417 (Space& home, ViewSelVirtualBase<View>** tb, int n0) 00418 : n(n0), c(heap.alloc<ChoiceVirtualBase*>(n)) { 00419 for (int i=n; i--; ) 00420 c[i] = tb[i]->choice(home); 00421 } 00422 template<class View> 00423 forceinline 00424 ViewSelTieBreakDynamic<View>::Choice::Choice(const Choice& ce) 00425 : n(ce.n), c(heap.alloc<ChoiceVirtualBase*>(n)) { 00426 for (int i=n; i--; ) 00427 c[i] = ce.c[i]->copy(); 00428 } 00429 template<class View> 00430 forceinline const typename ViewSelTieBreakDynamic<View>::Choice& 00431 ViewSelTieBreakDynamic<View>::Choice::operator =(const Choice& ce) { 00432 if (&ce != this) { 00433 assert(ce.n == n); 00434 for (int i=n; i--; ) { 00435 delete c[i]; c[i] = ce.c[i]->copy(); 00436 } 00437 } 00438 return *this; 00439 } 00440 template<class View> 00441 forceinline void 00442 ViewSelTieBreakDynamic<View>::Choice::commit 00443 (Space& home, unsigned int a, ViewSelVirtualBase<View>** tb) const { 00444 for (int i=n; i--; ) 00445 tb[i]->commit(home, c[i], a); 00446 } 00447 template<class View> 00448 forceinline size_t 00449 ViewSelTieBreakDynamic<View>::Choice::size(void) const { 00450 size_t s = (sizeof(typename ViewSelTieBreakDynamic<View>::Choice) + 00451 n * sizeof(ChoiceVirtualBase*)); 00452 for (int i=n; i--; ) 00453 s += c[i]->size(); 00454 return s; 00455 } 00456 template<class View> 00457 forceinline 00458 ViewSelTieBreakDynamic<View>::Choice::~Choice(void) { 00459 for (int i=n; i--; ) 00460 delete c[i]; 00461 heap.free(c,n); 00462 } 00463 00464 00465 // Select variable with dynamic tie breaking 00466 template<class View> 00467 forceinline 00468 ViewSelTieBreakDynamic<View>::ViewSelTieBreakDynamic(void) {} 00469 template<class View> 00470 forceinline 00471 ViewSelTieBreakDynamic<View>:: 00472 ViewSelTieBreakDynamic(Space& home, ViewSelVirtualBase<View>** vsv, int n0) 00473 : n(n0), tb(home.alloc<ViewSelVirtualBase<View>*>(n)) { 00474 for (int i=0; i<n; i++) 00475 tb[i]=vsv[i]; 00476 assert(n > 0); 00477 } 00478 template<class View> 00479 forceinline ViewSelStatus 00480 ViewSelTieBreakDynamic<View>::init(Space& home, View x) { 00481 ViewSelStatus s = VSS_BEST; 00482 for (int i=0; i<n; i++) 00483 if (tb[i]->init(home,x) != VSS_BEST) 00484 s = VSS_BETTER; 00485 return s; 00486 } 00487 template<class View> 00488 forceinline ViewSelStatus 00489 ViewSelTieBreakDynamic<View>::select(Space& home, View x) { 00490 switch (tb[0]->select(home,x)) { 00491 case VSS_BEST: 00492 { 00493 ViewSelStatus s = VSS_BEST; 00494 for (int i=1; i<n; i++) 00495 if (tb[i]->init(home,x) != VSS_BEST) 00496 s = VSS_BETTER; 00497 return s; 00498 } 00499 case VSS_BETTER: 00500 for (int i=1; i<n; i++) 00501 (void) tb[i]->init(home,x); 00502 return VSS_BETTER; 00503 case VSS_WORSE: 00504 return VSS_WORSE; 00505 case VSS_TIE: 00506 for (int i=1; i<n; i++) 00507 switch (tb[i]->select(home,x)) { 00508 case VSS_BEST: case VSS_BETTER: 00509 for (int j=i+1; j<n; j++) 00510 (void) tb[j]->init(home,x); 00511 return VSS_BETTER; 00512 case VSS_TIE: break; 00513 case VSS_WORSE: return VSS_WORSE; 00514 default: GECODE_NEVER; 00515 } 00516 return VSS_TIE; 00517 default: GECODE_NEVER; 00518 return VSS_WORSE; 00519 } 00520 } 00521 template<class _View> 00522 inline typename ViewSelTieBreakDynamic<_View>::Choice 00523 ViewSelTieBreakDynamic<_View>::choice(Space& home) { 00524 Choice c(home,tb,n); 00525 return c; 00526 } 00527 template<class _View> 00528 forceinline void 00529 ViewSelTieBreakDynamic<_View>::commit 00530 (Space& home, const typename ViewSelTieBreakDynamic<_View>::Choice& c, 00531 unsigned int a) { 00532 c.commit(home,a,tb); 00533 } 00534 template<class _View> 00535 forceinline void 00536 ViewSelTieBreakDynamic<_View>::update(Space& home, bool share, 00537 ViewSelTieBreakDynamic<_View>& vstb) { 00538 n = vstb.n; 00539 tb = home.alloc<ViewSelVirtualBase<View>*>(n); 00540 for (int i=0; i<n; i++) 00541 tb[i] = vstb.tb[i]->copy(home,share); 00542 } 00543 template<class _View> 00544 forceinline void 00545 ViewSelTieBreakDynamic<_View>::dispose(Space& home) { 00546 for (int i=0; i<n; i++) 00547 home.rfree(tb[i],tb[i]->dispose(home)); 00548 home.free<ViewSelVirtualBase<_View>*>(tb,n); 00549 } 00550 00551 } 00552 00553 // STATISTICS: kernel-branch