Generated on Sat Aug 25 2012 03:32:52 for Gecode by doxygen 1.8.1.2
brancher-tiebreak.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main author:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2008
8  *
9  * Last modified:
10  * $Date: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
11  * $Revision: 12001 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode {
39 
49  template<class A, class B>
51  protected:
53  A a;
55  B b;
56  public:
58  typedef typename A::View View;
60  class Choice {
61  public:
63  typename A::Choice a;
65  typename B::Choice b;
67  Choice(const typename A::Choice& a, const typename B::Choice& b);
69  size_t size(void) const;
71  void archive(Archive& e) const;
72  };
76  ViewSelTieBreakStatic(Space& home, A& a, B& b);
78  ViewSelStatus init(Space& home, typename A::View x);
80  ViewSelStatus select(Space& home, typename A::View x);
82  Choice choice(Space& home);
84  Choice choice(const Space& home, Archive& e);
86  void commit(Space& home, const Choice& c, unsigned int a);
88  void update(Space& home, bool share, ViewSelTieBreakStatic& vs);
90  void dispose(Space& home);
91  };
92 
97  public:
99  virtual ChoiceVirtualBase* copy(void) const = 0;
101  virtual size_t size(void) const = 0;
105  virtual void archive(Archive& e) const = 0;
107 
108 
109  static void* operator new(size_t s);
111  static void operator delete(void*);
113  };
114 
118  template<class View>
120  public:
122  virtual ViewSelStatus init(Space& home, View x) = 0;
124  virtual ViewSelStatus select(Space& home, View x) = 0;
126  virtual ChoiceVirtualBase* choice(Space& home) = 0;
128  virtual ChoiceVirtualBase* choice(const Space& home, Archive& e) = 0;
130  virtual void commit(Space& home, const ChoiceVirtualBase* c,
131  unsigned int a) = 0;
133  virtual ViewSelVirtualBase<View>* copy(Space& home, bool share) = 0;
135  virtual size_t dispose(Space& home) = 0;
137 
138 
139  static void* operator new(size_t s, Space& home);
141  static void operator delete(void* p, Space& home);
143  static void operator delete(void*);
145  };
146 
150  template<class Choice>
152  public:
156  ChoiceVirtual(const Choice& c);
158  virtual ChoiceVirtualBase* copy(void) const;
160  virtual size_t size(void) const;
162  virtual ~ChoiceVirtual(void);
164  virtual void archive(Archive& e) const;
165  };
166 
170  template<class ViewSel>
171  class ViewSelVirtual : public ViewSelVirtualBase<typename ViewSel::View> {
172  protected:
174  ViewSel viewsel;
175  public:
177  ViewSelVirtual(Space& home, const VarBranchOptions& vbo);
179  ViewSelVirtual(Space& home, bool share, ViewSelVirtual& vsv);
181  virtual ViewSelStatus init(Space& home, typename ViewSel::View x);
183  virtual ViewSelStatus select(Space& home, typename ViewSel::View x);
185  virtual ChoiceVirtualBase* choice(Space& home);
187  virtual ChoiceVirtualBase* choice(const Space& home, Archive& e);
189  virtual void commit(Space& home, const ChoiceVirtualBase* d,
190  unsigned int a);
193  copy(Space& home, bool share);
195  virtual size_t dispose(Space& home);
196  };
197 
201  template<class _View>
203  protected:
205  int n;
208  public:
210  typedef _View View;
212  class Choice {
213  public:
215  int n;
219  Choice(Space& home, ViewSelVirtualBase<_View>** tb, int n0);
221  Choice(const Space& home, Archive& e,
222  ViewSelVirtualBase<_View>** tb, int n0);
224  Choice(const Choice& ce);
226  const Choice& operator =(const Choice& ce);
228  void commit(Space& home, unsigned int a,
229  ViewSelVirtualBase<_View>** tb) const;
231  size_t size(void) const;
233  ~Choice(void);
235  void archive(Archive& e) const;
236  };
241  int n);
243  ViewSelStatus init(Space& home, _View x);
245  ViewSelStatus select(Space& home, _View x);
247  Choice choice(Space& home);
249  Choice choice(const Space& home, Archive& e);
251  void commit(Space& home,
253  unsigned int a);
255  void update(Space& home, bool share, ViewSelTieBreakDynamic& vs);
257  void dispose(Space& home);
258  };
260 
261 
262  // Select variable with static tie breaking
263  template<class A, class B>
265  ViewSelTieBreakStatic<A,B>::Choice::Choice(const typename A::Choice& a0,
266  const typename B::Choice& b0)
267  : a(a0), b(b0) {}
268  template<class A, class B>
269  forceinline size_t
271  return a.size() + b.size();
272  }
273  template<class A, class B>
274  forceinline void
276  a.archive(e);
277  b.archive(e);
278  }
279 
280  template<class A, class B>
283  template<class A, class B>
287  : a(a0), b(b0) {}
288  template<class A, class B>
290  ViewSelTieBreakStatic<A,B>::init(Space& home, typename A::View x) {
291  ViewSelStatus s = a.init(home,x);
292  return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : s;
293  }
294  template<class A, class B>
296  ViewSelTieBreakStatic<A,B>::select(Space& home, typename A::View x) {
297  switch (a.select(home,x)) {
298  case VSS_BEST:
299  return (b.init(home,x) != VSS_BEST) ? VSS_BETTER : VSS_BEST;
300  case VSS_BETTER:
301  (void) b.init(home,x);
302  return VSS_BETTER;
303  case VSS_WORSE:
304  return VSS_WORSE;
305  case VSS_TIE:
306  switch (b.select(home,x)) {
307  case VSS_BEST: return VSS_BETTER;
308  case VSS_BETTER: return VSS_BETTER;
309  case VSS_TIE: return VSS_TIE;
310  case VSS_WORSE: return VSS_WORSE;
311  default: GECODE_NEVER;
312  }
313  default: GECODE_NEVER;
314  return VSS_WORSE;
315  }
316  }
317  template<class A, class B>
318  inline typename ViewSelTieBreakStatic<A,B>::Choice
320  typename ViewSelTieBreakStatic<A,B>::Choice c(a.choice(home),
321  b.choice(home));
322  return c;
323  }
324  template<class A, class B>
325  inline typename ViewSelTieBreakStatic<A,B>::Choice
327  typename ViewSelTieBreakStatic<A,B>::Choice c(a.choice(home,e),
328  b.choice(home,e));
329  return c;
330  }
331  template<class A, class B>
332  forceinline void
334  unsigned int al) {
335  a.commit(home, c.a, al);
336  b.commit(home, c.b, al);
337  }
338  template<class A, class B>
339  forceinline void
342  a.update(home,share,vstb.a);
343  b.update(home,share,vstb.b);
344  }
345  template<class A, class B>
346  forceinline void
348  a.dispose(home);
349  b.dispose(home);
350  }
351 
352 
353  // Virtualized view selection
354  template<class View>
355  forceinline void
357  template<class View>
358  forceinline void
360  template<class View>
361  forceinline void*
363  return home.ralloc(s);
364  }
365 
366  // Virtualized choice
367  forceinline void
368  ChoiceVirtualBase::operator delete(void* p) {
369  heap.rfree(p);
370  }
371  forceinline void*
372  ChoiceVirtualBase::operator new(size_t s) {
373  return heap.ralloc(s);
374  }
377  }
378 
379 
380  template<class Choice>
383  : choice(c) {}
384  template<class Choice>
387  return new ChoiceVirtual<Choice>(choice);
388  }
389  template<class Choice>
390  forceinline size_t
392  return sizeof(ChoiceVirtual<Choice>);
393  }
394  template<class Choice>
396  template<class Choice> void
398  choice.archive(e);
399  }
400 
401  template<class ViewSel>
404  const VarBranchOptions& vbo)
405  : viewsel(home,vbo) {}
406  template<class ViewSel>
410  viewsel.update(home,share,vsv.viewsel);
411  }
412  template<class ViewSel>
414  ViewSelVirtual<ViewSel>::init(Space& home, typename ViewSel::View x) {
415  return viewsel.init(home,x);
416  }
417  template<class ViewSel>
419  ViewSelVirtual<ViewSel>::select(Space& home, typename ViewSel::View x) {
420  return viewsel.select(home,x);
421  }
422  template<class ViewSel>
425  return new ChoiceVirtual<typename ViewSel::Choice>(viewsel.choice(home));
426  }
427  template<class ViewSel>
430  return new ChoiceVirtual<typename ViewSel::Choice>(viewsel.choice(home,e));
431  }
432  template<class ViewSel>
433  void
435  unsigned int a) {
437  static_cast<const ChoiceVirtual<typename ViewSel::Choice>*>(_c);
438  viewsel.commit(home, c->choice, a);
439  }
440  template<class ViewSel>
443  return new (home) ViewSelVirtual<ViewSel>(home,share,*this);
444  }
445  template<class ViewSel>
446  size_t
448  viewsel.dispose(home);
449  return sizeof(ViewSelVirtual<ViewSel>);
450  }
451 
452 
453  // Choice for dynamic tie breaking
454  template<class View>
457  (Space& home, ViewSelVirtualBase<View>** tb, int n0)
458  : n(n0), c(heap.alloc<ChoiceVirtualBase*>(n)) {
459  for (int i=n; i--; )
460  c[i] = tb[i]->choice(home);
461  }
462  template<class View>
465  (const Space& home, Archive& e, ViewSelVirtualBase<View>** tb,
466  int n0)
467  : n(n0), c(heap.alloc<ChoiceVirtualBase*>(n)) {
468  for (int i=n; i--; )
469  c[i] = tb[i]->choice(home,e);
470  }
471  template<class View>
474  : n(ce.n), c(heap.alloc<ChoiceVirtualBase*>(n)) {
475  for (int i=n; i--; )
476  c[i] = ce.c[i]->copy();
477  }
478  template<class View>
481  if (&ce != this) {
482  assert(ce.n == n);
483  for (int i=n; i--; ) {
484  delete c[i]; c[i] = ce.c[i]->copy();
485  }
486  }
487  return *this;
488  }
489  template<class View>
490  forceinline void
492  (Space& home, unsigned int a, ViewSelVirtualBase<View>** tb) const {
493  for (int i=n; i--; )
494  tb[i]->commit(home, c[i], a);
495  }
496  template<class View>
497  forceinline size_t
499  size_t s = (sizeof(typename ViewSelTieBreakDynamic<View>::Choice) +
500  n * sizeof(ChoiceVirtualBase*));
501  for (int i=n; i--; )
502  s += c[i]->size();
503  return s;
504  }
505  template<class View>
508  for (int i=n; i--; )
509  delete c[i];
510  heap.free(c,n);
511  }
512  template<class View>
513  forceinline void
515  {
516  for (int i=0; i<n; i++)
517  c[i]->archive(e);
518  }
519 
520 
521  // Select variable with dynamic tie breaking
522  template<class View>
525  template<class View>
529  : n(n0), tb(home.alloc<ViewSelVirtualBase<View>*>(n)) {
530  for (int i=0; i<n; i++)
531  tb[i]=vsv[i];
532  assert(n > 0);
533  }
534  template<class View>
538  for (int i=0; i<n; i++)
539  if (tb[i]->init(home,x) != VSS_BEST)
540  s = VSS_BETTER;
541  return s;
542  }
543  template<class View>
546  switch (tb[0]->select(home,x)) {
547  case VSS_BEST:
548  {
550  for (int i=1; i<n; i++)
551  if (tb[i]->init(home,x) != VSS_BEST)
552  s = VSS_BETTER;
553  return s;
554  }
555  case VSS_BETTER:
556  for (int i=1; i<n; i++)
557  (void) tb[i]->init(home,x);
558  return VSS_BETTER;
559  case VSS_WORSE:
560  return VSS_WORSE;
561  case VSS_TIE:
562  for (int i=1; i<n; i++)
563  switch (tb[i]->select(home,x)) {
564  case VSS_BEST: case VSS_BETTER:
565  for (int j=i+1; j<n; j++)
566  (void) tb[j]->init(home,x);
567  return VSS_BETTER;
568  case VSS_TIE: break;
569  case VSS_WORSE: return VSS_WORSE;
570  default: GECODE_NEVER;
571  }
572  return VSS_TIE;
573  default: GECODE_NEVER;
574  return VSS_WORSE;
575  }
576  }
577  template<class _View>
580  Choice c(home,tb,n);
581  return c;
582  }
583  template<class _View>
586  Choice c(home,e,tb,n);
587  return c;
588  }
589  template<class _View>
590  forceinline void
593  unsigned int a) {
594  c.commit(home,a,tb);
595  }
596  template<class _View>
597  forceinline void
600  n = vstb.n;
601  tb = home.alloc<ViewSelVirtualBase<View>*>(n);
602  for (int i=0; i<n; i++)
603  tb[i] = vstb.tb[i]->copy(home,share);
604  }
605  template<class _View>
606  forceinline void
608  for (int i=0; i<n; i++)
609  home.rfree(tb[i],tb[i]->dispose(home));
610  home.free<ViewSelVirtualBase<_View>*>(tb,n);
611  }
612 
613 }
614 
615 // STATISTICS: kernel-branch