Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.9.1
propagator.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, 2002
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
13  * $Revision: 9878 $
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 
58  template<class View, PropCond pc>
59  class UnaryPropagator : public Propagator {
60  protected:
62  View x0;
64  UnaryPropagator(Space& home, bool share, UnaryPropagator& p);
66  UnaryPropagator(Space& home, bool share, Propagator& p,
67  View x0);
69  UnaryPropagator(Home home, View x0);
70  public:
72  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
74  virtual size_t dispose(Space& home);
75  };
76 
86  template<class View, PropCond pc>
87  class BinaryPropagator : public Propagator {
88  protected:
90  View x0, x1;
92  BinaryPropagator(Space& home, bool share, BinaryPropagator& p);
94  BinaryPropagator(Home home, View x0, View x1);
96  BinaryPropagator(Space& home, bool share, Propagator& p,
97  View x0, View x1);
98  public:
100  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
102  virtual size_t dispose(Space& home);
103  };
104 
114  template<class View, PropCond pc>
115  class TernaryPropagator : public Propagator {
116  protected:
118  View x0, x1, x2;
120  TernaryPropagator(Space& home, bool share, TernaryPropagator& p);
122  TernaryPropagator(Home home, View x0, View x1, View x2);
124  TernaryPropagator(Space& home, bool share, Propagator& p,
125  View x0, View x1, View x2);
126  public:
128  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
130  virtual size_t dispose(Space& home);
131  };
132 
142  template<class View, PropCond pc>
143  class NaryPropagator : public Propagator {
144  protected:
148  NaryPropagator(Space& home, bool share, NaryPropagator& p);
150  NaryPropagator(Space& home, bool share, Propagator& p,
151  ViewArray<View>& x);
154  public:
156  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
158  virtual size_t dispose(Space& home);
159  };
160 
171  template<class View, PropCond pc>
172  class NaryOnePropagator : public Propagator {
173  protected:
177  View y;
179  NaryOnePropagator(Space& home, bool share, NaryOnePropagator& p);
181  NaryOnePropagator(Space& home, bool share, Propagator& p,
182  ViewArray<View>& x, View y);
184  NaryOnePropagator(Home home, ViewArray<View>& x, View y);
185  public:
187  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
189  virtual size_t dispose(Space& home);
190  };
191 
202  template<class View0, PropCond pc0, class View1, PropCond pc1>
204  protected:
206  View0 x0;
208  View1 x1;
212  MixBinaryPropagator(Home home,View0,View1);
214  MixBinaryPropagator(Space& home, bool share, Propagator& p,
215  View0 x0, View1 x1);
216  public:
218  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
220  virtual size_t dispose(Space& home);
221  };
222 
233  template<class View0, PropCond pc0, class View1, PropCond pc1,
234  class View2, PropCond pc2>
236  protected:
238  View0 x0;
240  View1 x1;
242  View2 x2;
244  MixTernaryPropagator(Space& home, bool share, MixTernaryPropagator& p);
246  MixTernaryPropagator(Home home, View0 x0, View1 x1, View2 x2);
248  MixTernaryPropagator(Space& home, bool share, Propagator& p,
249  View0 x0, View1 x1, View2 x2);
250  public:
252  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
254  virtual size_t dispose(Space& home);
255  };
256 
267  template<class View0, PropCond pc0, class View1, PropCond pc1>
269  protected:
273  View1 y;
275  MixNaryOnePropagator(Space& home, bool share, MixNaryOnePropagator& p);
277  MixNaryOnePropagator(Home home, ViewArray<View0>& x, View1 y);
279  MixNaryOnePropagator(Space& home, bool share, Propagator& p,
280  ViewArray<View0>& x, View1 y);
281  public:
283  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
285  virtual size_t dispose(Space& home);
286  };
288 
289 
290  /*
291  * Unary propagators
292  *
293  */
294 
295  template<class View, PropCond pc>
297  : Propagator(home), x0(y0) {
298  if (pc != PC_GEN_NONE)
299  x0.subscribe(home,*this,pc);
300  }
301 
302  template<class View, PropCond pc>
305  (Space& home, bool share, UnaryPropagator<View,pc>& p)
306  : Propagator(home,share,p) {
307  x0.update(home,share,p.x0);
308  }
309 
310  template<class View, PropCond pc>
313  (Space& home, bool share, Propagator& p, View y0)
314  : Propagator(home,share,p) {
315  x0.update(home,share,y0);
316  }
317 
318  template<class View, PropCond pc>
319  PropCost
322  }
323 
324  template<class View, PropCond pc>
325  forceinline size_t
327  if (pc != PC_GEN_NONE)
328  x0.cancel(home,*this,pc);
329  (void) Propagator::dispose(home);
330  return sizeof(*this);
331  }
332 
333 
334  /*
335  * Binary propagators
336  *
337  */
338 
339  template<class View, PropCond pc>
341  : Propagator(home), x0(y0), x1(y1) {
342  if (pc != PC_GEN_NONE) {
343  x0.subscribe(home,*this,pc);
344  x1.subscribe(home,*this,pc);
345  }
346  }
347 
348  template<class View, PropCond pc>
351  (Space& home, bool share, BinaryPropagator<View,pc>& p)
352  : Propagator(home,share,p) {
353  x0.update(home,share,p.x0);
354  x1.update(home,share,p.x1);
355  }
356 
357  template<class View, PropCond pc>
360  (Space& home, bool share, Propagator& p, View y0, View y1)
361  : Propagator(home,share,p) {
362  x0.update(home,share,y0);
363  x1.update(home,share,y1);
364  }
365 
366  template<class View, PropCond pc>
367  PropCost
370  }
371 
372  template<class View, PropCond pc>
373  forceinline size_t
375  if (pc != PC_GEN_NONE) {
376  x0.cancel(home,*this,pc);
377  x1.cancel(home,*this,pc);
378  }
379  (void) Propagator::dispose(home);
380  return sizeof(*this);
381  }
382 
383  /*
384  * Ternary propagators
385  *
386  */
387 
388  template<class View, PropCond pc>
390  (Home home, View y0, View y1, View y2)
391  : Propagator(home), x0(y0), x1(y1), x2(y2) {
392  if (pc != PC_GEN_NONE) {
393  x0.subscribe(home,*this,pc);
394  x1.subscribe(home,*this,pc);
395  x2.subscribe(home,*this,pc);
396  }
397  }
398 
399  template<class View, PropCond pc>
402  (Space& home, bool share, TernaryPropagator<View,pc>& p)
403  : Propagator(home,share,p) {
404  x0.update(home,share,p.x0);
405  x1.update(home,share,p.x1);
406  x2.update(home,share,p.x2);
407  }
408 
409  template<class View, PropCond pc>
412  (Space& home, bool share, Propagator& p, View y0, View y1, View y2)
413  : Propagator(home,share,p) {
414  x0.update(home,share,y0);
415  x1.update(home,share,y1);
416  x2.update(home,share,y2);
417  }
418 
419  template<class View, PropCond pc>
420  PropCost
423  }
424 
425  template<class View, PropCond pc>
426  forceinline size_t
428  if (pc != PC_GEN_NONE) {
429  x0.cancel(home,*this,pc);
430  x1.cancel(home,*this,pc);
431  x2.cancel(home,*this,pc);
432  }
433  (void) Propagator::dispose(home);
434  return sizeof(*this);
435  }
436 
437  /*
438  * Nary propagators
439  *
440  */
441 
442  template<class View, PropCond pc>
445  : Propagator(home), x(y) {
446  if (pc != PC_GEN_NONE)
447  x.subscribe(home,*this,pc);
448  }
449 
450  template<class View, PropCond pc>
453  (Space& home, bool share, NaryPropagator<View,pc>& p)
454  : Propagator(home,share,p) {
455  x.update(home,share,p.x);
456  }
457 
458  template<class View, PropCond pc>
461  (Space& home, bool share, Propagator& p, ViewArray<View>& x0)
462  : Propagator(home,share,p) {
463  x.update(home,share,x0);
464  }
465 
466  template<class View, PropCond pc>
467  PropCost
469  return PropCost::linear(PropCost::LO,x.size());
470  }
471 
472  template<class View, PropCond pc>
473  forceinline size_t
475  if (pc != PC_GEN_NONE)
476  x.cancel(home,*this,pc);
477  (void) Propagator::dispose(home);
478  return sizeof(*this);
479  }
480 
481  /*
482  * NaryOne (one additional variable) propagators
483  *
484  */
485 
486  template<class View, PropCond pc>
488  (Home home, ViewArray<View>& x0, View y0)
489  : Propagator(home), x(x0), y(y0) {
490  if (pc != PC_GEN_NONE) {
491  x.subscribe(home,*this,pc);
492  y.subscribe(home,*this,pc);
493  }
494  }
495 
496  template<class View, PropCond pc>
499  (Space& home, bool share, NaryOnePropagator<View,pc>& p)
500  : Propagator(home,share,p) {
501  x.update(home,share,p.x);
502  y.update(home,share,p.y);
503  }
504 
505  template<class View, PropCond pc>
508  (Space& home, bool share, Propagator& p, ViewArray<View>& x0, View y0)
509  : Propagator(home,share,p) {
510  x.update(home,share,x0);
511  y.update(home,share,y0);
512  }
513 
514  template<class View, PropCond pc>
515  PropCost
517  return PropCost::linear(PropCost::LO,x.size()+1);
518  }
519 
520  template<class View, PropCond pc>
521  forceinline size_t
523  if (pc != PC_GEN_NONE) {
524  x.cancel(home,*this,pc);
525  y.cancel(home,*this,pc);
526  }
527  (void) Propagator::dispose(home);
528  return sizeof(*this);
529  }
530 
531  /*
532  * Mixed binary propagators
533  *
534  */
535 
536  template<class View0, PropCond pc0, class View1, PropCond pc1>
538  (Home home, View0 y0, View1 y1)
539  : Propagator(home), x0(y0), x1(y1) {
540  if (pc0 != PC_GEN_NONE)
541  x0.subscribe(home,*this,pc0);
542  if (pc1 != PC_GEN_NONE)
543  x1.subscribe(home,*this,pc1);
544  }
545 
546  template<class View0, PropCond pc0, class View1, PropCond pc1>
550  : Propagator(home,share,p) {
551  x0.update(home,share,p.x0);
552  x1.update(home,share,p.x1);
553  }
554 
555  template<class View0, PropCond pc0, class View1, PropCond pc1>
558  (Space& home, bool share, Propagator& p, View0 y0, View1 y1)
559  : Propagator(home,share,p) {
560  x0.update(home,share,y0);
561  x1.update(home,share,y1);
562  }
563 
564  template<class View0, PropCond pc0, class View1, PropCond pc1>
565  PropCost
567  const ModEventDelta&) const {
569  }
570 
571  template<class View0, PropCond pc0, class View1, PropCond pc1>
572  forceinline size_t
574  if (pc0 != PC_GEN_NONE)
575  x0.cancel(home,*this,pc0);
576  if (pc1 != PC_GEN_NONE)
577  x1.cancel(home,*this,pc1);
578  (void) Propagator::dispose(home);
579  return sizeof(*this);
580  }
581 
582  /*
583  * Mixed ternary propagators
584  *
585  */
586 
587  template<class View0, PropCond pc0, class View1, PropCond pc1,
588  class View2, PropCond pc2>
590  MixTernaryPropagator(Home home, View0 y0, View1 y1, View2 y2)
591  : Propagator(home), x0(y0), x1(y1), x2(y2) {
592  if (pc0 != PC_GEN_NONE)
593  x0.subscribe(home,*this,pc0);
594  if (pc1 != PC_GEN_NONE)
595  x1.subscribe(home,*this,pc1);
596  if (pc2 != PC_GEN_NONE)
597  x2.subscribe(home,*this,pc2);
598  }
599 
600  template<class View0, PropCond pc0, class View1, PropCond pc1,
601  class View2, PropCond pc2>
604  MixTernaryPropagator(Space& home, bool share,
605  MixTernaryPropagator<View0,pc0,View1,pc1,
606  View2,pc2>& p)
607  : Propagator(home,share,p) {
608  x0.update(home,share,p.x0);
609  x1.update(home,share,p.x1);
610  x2.update(home,share,p.x2);
611  }
612 
613  template<class View0, PropCond pc0, class View1, PropCond pc1,
614  class View2, PropCond pc2>
617  (Space& home, bool share, Propagator& p, View0 y0, View1 y1, View2 y2)
618  : Propagator(home,share,p) {
619  x0.update(home,share,y0);
620  x1.update(home,share,y1);
621  x2.update(home,share,y2);
622  }
623 
624  template<class View0, PropCond pc0, class View1, PropCond pc1,
625  class View2, PropCond pc2>
626  PropCost
628  cost(const Space&, const ModEventDelta&) const {
630  }
631 
632  template<class View0, PropCond pc0, class View1, PropCond pc1,
633  class View2, PropCond pc2>
634  forceinline size_t
636  if (pc0 != PC_GEN_NONE)
637  x0.cancel(home,*this,pc0);
638  if (pc1 != PC_GEN_NONE)
639  x1.cancel(home,*this,pc1);
640  if (pc2 != PC_GEN_NONE)
641  x2.cancel(home,*this,pc2);
642  (void) Propagator::dispose(home);
643  return sizeof(*this);
644  }
645 
646  /*
647  * MixNaryOne (one additional variable) propagators
648  *
649  */
650 
651  template<class View0, PropCond pc0, class View1, PropCond pc1>
653  (Home home, ViewArray<View0>& x0, View1 y0)
654  : Propagator(home), x(x0), y(y0) {
655  if (pc0 != PC_GEN_NONE)
656  x.subscribe(home,*this,pc0);
657  if (pc1 != PC_GEN_NONE)
658  y.subscribe(home,*this,pc1);
659  }
660 
661  template<class View0, PropCond pc0, class View1, PropCond pc1>
665  : Propagator(home,share,p) {
666  x.update(home,share,p.x);
667  y.update(home,share,p.y);
668  }
669 
670  template<class View0, PropCond pc0, class View1, PropCond pc1>
673  (Space& home, bool share, Propagator& p, ViewArray<View0>& x0, View1 y0)
674  : Propagator(home,share,p) {
675  x.update(home,share,x0);
676  y.update(home,share,y0);
677  }
678 
679  template<class View0, PropCond pc0, class View1, PropCond pc1>
680  PropCost
682  const ModEventDelta&) const {
683  return PropCost::linear(PropCost::LO,x.size()+1);
684  }
685 
686  template<class View0, PropCond pc0, class View1, PropCond pc1>
687  forceinline size_t
689  if (pc0 != PC_GEN_NONE)
690  x.cancel(home,*this,pc0);
691  if (pc1 != PC_GEN_NONE)
692  y.cancel(home,*this,pc1);
693  (void) Propagator::dispose(home);
694  return sizeof(*this);
695  }
696 
697 }
698 
699 // STATISTICS: kernel-prop
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:158
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
NaryOnePropagator(Space &home, bool share, NaryOnePropagator &p)
Constructor for cloning p.
Definition: propagator.hpp:499
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low ternary)
Definition: propagator.hpp:628
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
ViewArray< View > x
Array of views.
Definition: propagator.hpp:175
TernaryPropagator(Space &home, bool share, TernaryPropagator &p)
Constructor for cloning p.
Definition: propagator.hpp:402
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:474
View0 x0
View of type View0.
Definition: propagator.hpp:206
Unary propagator.
Definition: propagator.hpp:59
View y
Single view.
Definition: propagator.hpp:177
View2 x2
View of type View2.
Definition: propagator.hpp:242
Mixed (n+1)-ary propagator.
Definition: propagator.hpp:268
ViewArray< View > x
Array of views.
Definition: propagator.hpp:146
Base-class for propagators.
Definition: core.hpp:755
MixBinaryPropagator(Space &home, bool, MixBinaryPropagator &)
Constructor for cloning.
Definition: propagator.hpp:549
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:374
View x0
Three views.
Definition: propagator.hpp:118
View x0
Two views.
Definition: propagator.hpp:90
ViewArray< View0 > x
Array of views.
Definition: propagator.hpp:271
View x0
Single view.
Definition: propagator.hpp:62
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4058
View1 x1
View of type View1.
Definition: propagator.hpp:208
Computation spaces.
Definition: core.hpp:1362
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low binary)
Definition: propagator.hpp:566
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:427
View0 x0
View of type View0.
Definition: propagator.hpp:238
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Binary propagator.
Definition: propagator.hpp:87
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
Mixed ternary propagator.
Definition: propagator.hpp:235
MixNaryOnePropagator(Space &home, bool share, MixNaryOnePropagator &p)
Constructor for cloning p.
Definition: propagator.hpp:664
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low binary)
Definition: propagator.hpp:368
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low ternary)
Definition: propagator.hpp:421
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:688
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: propagator.hpp:516
UnaryPropagator(Space &home, bool share, UnaryPropagator &p)
Constructor for cloning p.
Definition: propagator.hpp:305
Ternary propagator.
Definition: propagator.hpp:115
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_UNARY_LO)
Definition: propagator.hpp:320
n-ary propagator
Definition: propagator.hpp:143
(n+1)-ary propagator
Definition: propagator.hpp:172
View arrays.
Definition: array.hpp:234
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1408
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:326
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Mixed binary propagator.
Definition: propagator.hpp:203
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: propagator.hpp:681
Propagation cost.
Definition: core.hpp:537
#define forceinline
Definition: config.hpp:132
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: propagator.hpp:468
NaryPropagator(Space &home, bool share, NaryPropagator &p)
Constructor for cloning p.
Definition: propagator.hpp:453
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4050
Gecode toplevel namespace
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:635
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:522
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:573
BinaryPropagator(Space &home, bool share, BinaryPropagator &p)
Constructor for cloning p.
Definition: propagator.hpp:351
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4054
View1 x1
View of type View1.
Definition: propagator.hpp:240
MixTernaryPropagator(Space &home, bool share, MixTernaryPropagator &p)
Constructor for cloning.
Definition: propagator.hpp:604