Generated on Fri Aug 24 2012 04:52:19 for Gecode by doxygen 1.8.1.1
brancher.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2004
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
13  * $Revision: 12001 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode {
41 
50 
56  };
57 
59  class Pos {
60  public:
62  const int pos;
64  Pos(int p);
65  };
66 
75  template<class ViewSel>
76  class ViewBrancher : public Brancher {
77  protected:
81  mutable int start;
83  ViewSel viewsel;
87  Pos pos(Space& home);
89  typename ViewSel::View view(const Pos& p) const;
91  ViewBrancher(Space& home, bool share, ViewBrancher& b);
94  ViewSel& vi_s, BranchFilter bf0=NULL);
95  public:
97  virtual bool status(const Space& home) const;
99  virtual size_t dispose(Space& home);
100  };
101 
102 
112  template<class ViewSel, class ValSel>
113  class ViewValBrancher : public ViewBrancher<ViewSel> {
114  protected:
118  ValSel valsel;
120  ViewValBrancher(Space& home, bool share, ViewValBrancher& b);
123  ViewSel& vi_s, ValSel& va_s, BranchFilter bf0);
124  public:
126  virtual const Choice* choice(Space& home);
128  virtual const Choice* choice(const Space& home, Archive& e);
130  virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
132  virtual Actor* copy(Space& home, bool share);
134  virtual size_t dispose(Space& home);
136  static void post(Home home, ViewArray<typename ViewSel::View>& x,
137  ViewSel& vi_s, ValSel& va_s, BranchFilter bf=NULL);
138 
139  };
140 
141 
143  template<class ViewSel>
145  private:
147  const Pos _pos;
149  const typename ViewSel::Choice _viewchoice;
150  public:
152  PosChoice(const Brancher& b, unsigned int a, const Pos& p,
153  const typename ViewSel::Choice& viewc);
155  const Pos& pos(void) const;
157  const typename ViewSel::Choice& viewchoice(void) const;
159  virtual size_t size(void) const;
161  virtual void archive(Archive& e) const;
162  };
163 
165  template<class ViewSel, class ValSel>
166  class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice<ViewSel> {
167  private:
169  const typename ValSel::Choice _valchoice;
171  const typename ValSel::Val _val;
172  public:
174  PosValChoice(const Brancher& b, const Pos& p,
175  const typename ViewSel::Choice& viewc,
176  const typename ValSel::Choice& valc,
177  const typename ValSel::Val& n);
179  const typename ValSel::Choice& valchoice(void) const;
181  const typename ValSel::Val& val(void) const;
183  virtual size_t size(void) const;
185  virtual void archive(Archive& e) const;
186  };
188 
189 
190 
191 
192  /*
193  * Position information
194  *
195  */
197  Pos::Pos(int p) : pos(p) {}
198 
199 
200  /*
201  * Choice with position
202  *
203  */
204  template<class ViewSel>
206  PosChoice<ViewSel>::PosChoice(const Brancher& b, unsigned int a,
207  const Pos& p,
208  const typename ViewSel::Choice& viewc)
209  : Choice(b,a), _pos(p), _viewchoice(viewc) {}
210  template<class ViewSel>
211  forceinline const Pos&
213  return _pos;
214  }
215  template<class ViewSel>
216  forceinline const typename ViewSel::Choice&
218  return _viewchoice;
219  }
220  template<class ViewSel>
221  forceinline size_t
223  return sizeof(PosChoice<ViewSel>) + _viewchoice.size();
224  }
225  template<class ViewSel>
226  forceinline void
228  Choice::archive(e);
229  e << _pos.pos;
230  _viewchoice.archive(e);
231  }
232 
233  /*
234  * %Choice with position and value
235  *
236  */
237  template<class ViewSel, class ValSel>
240  ::PosValChoice(const Brancher& b, const Pos& p,
241  const typename ViewSel::Choice& viewc,
242  const typename ValSel::Choice& valc,
243  const typename ValSel::Val& n)
244  : PosChoice<ViewSel>(b,ValSel::alternatives,p,viewc),
245  _valchoice(valc), _val(n) {}
246 
247  template<class ViewSel, class ValSel>
248  forceinline const typename ValSel::Choice&
250  return _valchoice;
251  }
252 
253  template<class ViewSel, class ValSel>
254  forceinline const typename ValSel::Val&
256  return _val;
257  }
258 
259  template<class ViewSel, class ValSel>
260  forceinline size_t
262  return sizeof(PosValChoice<ViewSel,ValSel>) + _valchoice.size();
263  }
264 
265  template<class ViewSel, class ValSel>
266  forceinline void
269  _valchoice.archive(e);
270  e << _val;
271  }
272 
273  /*
274  * Generic brancher based on view selection
275  *
276  */
277 
278  template<class ViewSel>
282  ViewSel& vi_s, BranchFilter bf0)
283  : Brancher(home), x(x0), start(0), viewsel(vi_s), bf(bf0) {}
284 
285 
286  template<class ViewSel>
289  ViewBrancher& b)
290  : Brancher(home,share,b), start(b.start), bf(b.bf) {
291  x.update(home,share,b.x);
292  viewsel.update(home,share,b.viewsel);
293  }
294 
295  template<class ViewSel>
296  bool
298  if (bf == NULL) {
299  for (int i=start; i < x.size(); i++)
300  if (!x[i].assigned()) {
301  start = i;
302  return true;
303  }
304  } else {
305  for (int i=start; i < x.size(); i++) {
306  typename ViewSel::View::VarType y(x[i].varimp());
307  if (!x[i].assigned() && bf(home,i,y)) {
308  start = i;
309  return true;
310  }
311  }
312  }
313  return false;
314  }
315 
316  template<class ViewSel>
319  assert(!x[start].assigned());
320  int i = start;
321  int b = i++;
322  if (viewsel.init(home,x[b]) != VSS_BEST)
323  for (; i < x.size(); i++)
324  if (!x[i].assigned())
325  switch (viewsel.select(home,x[i])) {
326  case VSS_BETTER: b=i; break;
327  case VSS_BEST: b=i; goto create;
328  case VSS_TIE: case VSS_WORSE: break;
329  default: GECODE_NEVER;
330  }
331  create:
332  Pos p(b);
333  return p;
334  }
335 
336  template<class ViewSel>
337  forceinline typename ViewSel::View
339  return x[p.pos];
340  }
341 
342  template<class ViewSel>
343  forceinline size_t
345  viewsel.dispose(home);
346  (void) Brancher::dispose(home);
347  return sizeof(ViewBrancher<ViewSel>);
348  }
349 
350 
351 
352  /*
353  * Generic brancher based on variable/value selection
354  *
355  */
356 
357  template<class ViewSel, class ValSel>
361  ViewSel& vi_s, ValSel& va_s, BranchFilter bf)
362  : ViewBrancher<ViewSel>(home,x,vi_s,bf), valsel(va_s) {}
363 
364  template<class ViewSel, class ValSel>
365  void
368  ViewSel& vi_s, ValSel& va_s, BranchFilter bf) {
369  (void) new (home) ViewValBrancher<ViewSel,ValSel>(home,x,vi_s,va_s,bf);
370  }
371 
372  template<class ViewSel, class ValSel>
376  : ViewBrancher<ViewSel>(home,share,b) {
377  valsel.update(home,share,b.valsel);
378  }
379 
380  template<class ViewSel, class ValSel>
381  Actor*
383  return new (home)
384  ViewValBrancher<ViewSel,ValSel>(home,share,*this);
385  }
386 
387  template<class ViewSel, class ValSel>
388  const Choice*
391  typename ValSel::View v(ViewBrancher<ViewSel>::view(p).varimp());
392  typename ValSel::Val val(valsel.val(home,v));
394  (*this,p,
395  viewsel.choice(home),valsel.choice(home),val);
396  }
397 
398  template<class ViewSel, class ValSel>
399  const Choice*
401  int p; e >> p;
402  typename ViewSel::Choice viewsc = viewsel.choice(home,e);
403  typename ValSel::Choice valsc = valsel.choice(home,e);
404  typename ValSel::Val val; e >> val;
405  return new PosValChoice<ViewSel,ValSel>(*this,p,viewsc,valsc,val);
406  }
407 
408  template<class ViewSel, class ValSel>
409  ExecStatus
411  ::commit(Space& home, const Choice& c, unsigned int a) {
413  = static_cast<const PosValChoice<ViewSel,ValSel>&>(c);
414  typename ValSel::View
415  v(ViewBrancher<ViewSel>::view(pvc.pos()).varimp());
416  viewsel.commit(home, pvc.viewchoice(), a);
417  valsel.commit(home, pvc.valchoice(), a);
418  return me_failed(valsel.tell(home,a,v,pvc.val())) ? ES_FAILED : ES_OK;
419  }
420 
421  template<class ViewSel, class ValSel>
422  forceinline size_t
424  valsel.dispose(home);
425  (void) ViewBrancher<ViewSel>::dispose(home);
426  return sizeof(ViewValBrancher<ViewSel,ValSel>);
427  }
428 
429 }
430 
431 // STATISTICS: kernel-branch