00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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
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
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
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
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
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