Generated on Sat Jul 29 2017 12:41:24 for Gecode by doxygen 1.8.13
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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
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 void reschedule(Space& home);
76  virtual size_t dispose(Space& home);
77  };
78 
88  template<class View, PropCond pc>
89  class BinaryPropagator : public Propagator {
90  protected:
92  View x0, x1;
94  BinaryPropagator(Space& home, bool share, BinaryPropagator& p);
96  BinaryPropagator(Home home, View x0, View x1);
98  BinaryPropagator(Space& home, bool share, Propagator& p,
99  View x0, View x1);
100  public:
102  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
104  virtual void reschedule(Space& home);
106  virtual size_t dispose(Space& home);
107  };
108 
118  template<class View, PropCond pc>
119  class TernaryPropagator : public Propagator {
120  protected:
122  View x0, x1, x2;
124  TernaryPropagator(Space& home, bool share, TernaryPropagator& p);
126  TernaryPropagator(Home home, View x0, View x1, View x2);
128  TernaryPropagator(Space& home, bool share, Propagator& p,
129  View x0, View x1, View x2);
130  public:
132  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
134  virtual void reschedule(Space& home);
136  virtual size_t dispose(Space& home);
137  };
138 
148  template<class View, PropCond pc>
149  class NaryPropagator : public Propagator {
150  protected:
154  NaryPropagator(Space& home, bool share, NaryPropagator& p);
156  NaryPropagator(Space& home, bool share, Propagator& p,
157  ViewArray<View>& x);
160  public:
162  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
164  virtual void reschedule(Space& home);
166  virtual size_t dispose(Space& home);
167  };
168 
179  template<class View, PropCond pc>
180  class NaryOnePropagator : public Propagator {
181  protected:
185  View y;
187  NaryOnePropagator(Space& home, bool share, NaryOnePropagator& p);
189  NaryOnePropagator(Space& home, bool share, Propagator& p,
190  ViewArray<View>& x, View y);
192  NaryOnePropagator(Home home, ViewArray<View>& x, View y);
193  public:
195  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
197  virtual void reschedule(Space& home);
199  virtual size_t dispose(Space& home);
200  };
201 
212  template<class View0, PropCond pc0, class View1, PropCond pc1>
214  protected:
216  View0 x0;
218  View1 x1;
222  MixBinaryPropagator(Home home,View0,View1);
224  MixBinaryPropagator(Space& home, bool share, Propagator& p,
225  View0 x0, View1 x1);
226  public:
228  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
230  virtual void reschedule(Space& home);
232  virtual size_t dispose(Space& home);
233  };
234 
245  template<class View0, PropCond pc0, class View1, PropCond pc1,
246  class View2, PropCond pc2>
248  protected:
250  View0 x0;
252  View1 x1;
254  View2 x2;
256  MixTernaryPropagator(Space& home, bool share, MixTernaryPropagator& p);
258  MixTernaryPropagator(Home home, View0 x0, View1 x1, View2 x2);
260  MixTernaryPropagator(Space& home, bool share, Propagator& p,
261  View0 x0, View1 x1, View2 x2);
262  public:
264  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
266  virtual void reschedule(Space& home);
268  virtual size_t dispose(Space& home);
269  };
270 
281  template<class View0, PropCond pc0, class View1, PropCond pc1>
283  protected:
287  View1 y;
289  MixNaryOnePropagator(Space& home, bool share, MixNaryOnePropagator& p);
291  MixNaryOnePropagator(Home home, ViewArray<View0>& x, View1 y);
293  MixNaryOnePropagator(Space& home, bool share, Propagator& p,
294  ViewArray<View0>& x, View1 y);
295  public:
297  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
299  virtual void reschedule(Space& home);
301  virtual size_t dispose(Space& home);
302  };
304 
305 
306  /*
307  * Unary propagators
308  *
309  */
310 
311  template<class View, PropCond pc>
313  : Propagator(home), x0(y0) {
314  if (pc != PC_GEN_NONE)
315  x0.subscribe(home,*this,pc);
316  }
317 
318  template<class View, PropCond pc>
321  (Space& home, bool share, UnaryPropagator<View,pc>& p)
322  : Propagator(home,share,p) {
323  x0.update(home,share,p.x0);
324  }
325 
326  template<class View, PropCond pc>
329  (Space& home, bool share, Propagator& p, View y0)
330  : Propagator(home,share,p) {
331  x0.update(home,share,y0);
332  }
333 
334  template<class View, PropCond pc>
335  PropCost
337  return PropCost::unary(PropCost::LO);
338  }
339 
340  template<class View, PropCond pc>
341  void
343  if (pc != PC_GEN_NONE)
344  x0.reschedule(home,*this,pc);
345  }
346 
347  template<class View, PropCond pc>
348  forceinline size_t
350  if (pc != PC_GEN_NONE)
351  x0.cancel(home,*this,pc);
352  (void) Propagator::dispose(home);
353  return sizeof(*this);
354  }
355 
356 
357  /*
358  * Binary propagators
359  *
360  */
361 
362  template<class View, PropCond pc>
364  : Propagator(home), x0(y0), x1(y1) {
365  if (pc != PC_GEN_NONE) {
366  x0.subscribe(home,*this,pc);
367  x1.subscribe(home,*this,pc);
368  }
369  }
370 
371  template<class View, PropCond pc>
374  (Space& home, bool share, BinaryPropagator<View,pc>& p)
375  : Propagator(home,share,p) {
376  x0.update(home,share,p.x0);
377  x1.update(home,share,p.x1);
378  }
379 
380  template<class View, PropCond pc>
383  (Space& home, bool share, Propagator& p, View y0, View y1)
384  : Propagator(home,share,p) {
385  x0.update(home,share,y0);
386  x1.update(home,share,y1);
387  }
388 
389  template<class View, PropCond pc>
390  PropCost
392  return PropCost::binary(PropCost::LO);
393  }
394 
395  template<class View, PropCond pc>
396  void
398  if (pc != PC_GEN_NONE) {
399  x0.reschedule(home,*this,pc);
400  x1.reschedule(home,*this,pc);
401  }
402  }
403 
404  template<class View, PropCond pc>
405  forceinline size_t
407  if (pc != PC_GEN_NONE) {
408  x0.cancel(home,*this,pc);
409  x1.cancel(home,*this,pc);
410  }
411  (void) Propagator::dispose(home);
412  return sizeof(*this);
413  }
414 
415  /*
416  * Ternary propagators
417  *
418  */
419 
420  template<class View, PropCond pc>
422  (Home home, View y0, View y1, View y2)
423  : Propagator(home), x0(y0), x1(y1), x2(y2) {
424  if (pc != PC_GEN_NONE) {
425  x0.subscribe(home,*this,pc);
426  x1.subscribe(home,*this,pc);
427  x2.subscribe(home,*this,pc);
428  }
429  }
430 
431  template<class View, PropCond pc>
434  (Space& home, bool share, TernaryPropagator<View,pc>& p)
435  : Propagator(home,share,p) {
436  x0.update(home,share,p.x0);
437  x1.update(home,share,p.x1);
438  x2.update(home,share,p.x2);
439  }
440 
441  template<class View, PropCond pc>
444  (Space& home, bool share, Propagator& p, View y0, View y1, View y2)
445  : Propagator(home,share,p) {
446  x0.update(home,share,y0);
447  x1.update(home,share,y1);
448  x2.update(home,share,y2);
449  }
450 
451  template<class View, PropCond pc>
452  PropCost
454  return PropCost::ternary(PropCost::LO);;
455  }
456 
457  template<class View, PropCond pc>
458  void
460  if (pc != PC_GEN_NONE) {
461  x0.reschedule(home,*this,pc);
462  x1.reschedule(home,*this,pc);
463  x2.reschedule(home,*this,pc);
464  }
465  }
466 
467  template<class View, PropCond pc>
468  forceinline size_t
470  if (pc != PC_GEN_NONE) {
471  x0.cancel(home,*this,pc);
472  x1.cancel(home,*this,pc);
473  x2.cancel(home,*this,pc);
474  }
475  (void) Propagator::dispose(home);
476  return sizeof(*this);
477  }
478 
479  /*
480  * Nary propagators
481  *
482  */
483 
484  template<class View, PropCond pc>
487  : Propagator(home), x(y) {
488  if (pc != PC_GEN_NONE)
489  x.subscribe(home,*this,pc);
490  }
491 
492  template<class View, PropCond pc>
495  (Space& home, bool share, NaryPropagator<View,pc>& p)
496  : Propagator(home,share,p) {
497  x.update(home,share,p.x);
498  }
499 
500  template<class View, PropCond pc>
503  (Space& home, bool share, Propagator& p, ViewArray<View>& x0)
504  : Propagator(home,share,p) {
505  x.update(home,share,x0);
506  }
507 
508  template<class View, PropCond pc>
509  PropCost
511  return PropCost::linear(PropCost::LO,x.size());
512  }
513 
514  template<class View, PropCond pc>
515  void
517  if (pc != PC_GEN_NONE)
518  x.reschedule(home,*this,pc);
519  }
520 
521  template<class View, PropCond pc>
522  forceinline size_t
524  if (pc != PC_GEN_NONE)
525  x.cancel(home,*this,pc);
526  (void) Propagator::dispose(home);
527  return sizeof(*this);
528  }
529 
530  /*
531  * NaryOne (one additional variable) propagators
532  *
533  */
534 
535  template<class View, PropCond pc>
537  (Home home, ViewArray<View>& x0, View y0)
538  : Propagator(home), x(x0), y(y0) {
539  if (pc != PC_GEN_NONE) {
540  x.subscribe(home,*this,pc);
541  y.subscribe(home,*this,pc);
542  }
543  }
544 
545  template<class View, PropCond pc>
548  (Space& home, bool share, NaryOnePropagator<View,pc>& p)
549  : Propagator(home,share,p) {
550  x.update(home,share,p.x);
551  y.update(home,share,p.y);
552  }
553 
554  template<class View, PropCond pc>
557  (Space& home, bool share, Propagator& p, ViewArray<View>& x0, View y0)
558  : Propagator(home,share,p) {
559  x.update(home,share,x0);
560  y.update(home,share,y0);
561  }
562 
563  template<class View, PropCond pc>
564  PropCost
566  return PropCost::linear(PropCost::LO,x.size()+1);
567  }
568 
569  template<class View, PropCond pc>
570  void
572  if (pc != PC_GEN_NONE) {
573  x.reschedule(home,*this,pc);
574  y.reschedule(home,*this,pc);
575  }
576  }
577 
578  template<class View, PropCond pc>
579  forceinline size_t
581  if (pc != PC_GEN_NONE) {
582  x.cancel(home,*this,pc);
583  y.cancel(home,*this,pc);
584  }
585  (void) Propagator::dispose(home);
586  return sizeof(*this);
587  }
588 
589  /*
590  * Mixed binary propagators
591  *
592  */
593 
594  template<class View0, PropCond pc0, class View1, PropCond pc1>
596  (Home home, View0 y0, View1 y1)
597  : Propagator(home), x0(y0), x1(y1) {
598  if (pc0 != PC_GEN_NONE)
599  x0.subscribe(home,*this,pc0);
600  if (pc1 != PC_GEN_NONE)
601  x1.subscribe(home,*this,pc1);
602  }
603 
604  template<class View0, PropCond pc0, class View1, PropCond pc1>
608  : Propagator(home,share,p) {
609  x0.update(home,share,p.x0);
610  x1.update(home,share,p.x1);
611  }
612 
613  template<class View0, PropCond pc0, class View1, PropCond pc1>
616  (Space& home, bool share, Propagator& p, View0 y0, View1 y1)
617  : Propagator(home,share,p) {
618  x0.update(home,share,y0);
619  x1.update(home,share,y1);
620  }
621 
622  template<class View0, PropCond pc0, class View1, PropCond pc1>
623  PropCost
625  const ModEventDelta&) const {
626  return PropCost::binary(PropCost::LO);
627  }
628 
629  template<class View0, PropCond pc0, class View1, PropCond pc1>
630  void
632  if (pc0 != PC_GEN_NONE)
633  x0.reschedule(home,*this,pc0);
634  if (pc1 != PC_GEN_NONE)
635  x1.reschedule(home,*this,pc1);
636  }
637 
638  template<class View0, PropCond pc0, class View1, PropCond pc1>
639  forceinline size_t
641  if (pc0 != PC_GEN_NONE)
642  x0.cancel(home,*this,pc0);
643  if (pc1 != PC_GEN_NONE)
644  x1.cancel(home,*this,pc1);
645  (void) Propagator::dispose(home);
646  return sizeof(*this);
647  }
648 
649  /*
650  * Mixed ternary propagators
651  *
652  */
653 
654  template<class View0, PropCond pc0, class View1, PropCond pc1,
655  class View2, PropCond pc2>
657  MixTernaryPropagator(Home home, View0 y0, View1 y1, View2 y2)
658  : Propagator(home), x0(y0), x1(y1), x2(y2) {
659  if (pc0 != PC_GEN_NONE)
660  x0.subscribe(home,*this,pc0);
661  if (pc1 != PC_GEN_NONE)
662  x1.subscribe(home,*this,pc1);
663  if (pc2 != PC_GEN_NONE)
664  x2.subscribe(home,*this,pc2);
665  }
666 
667  template<class View0, PropCond pc0, class View1, PropCond pc1,
668  class View2, PropCond pc2>
671  MixTernaryPropagator(Space& home, bool share,
672  MixTernaryPropagator<View0,pc0,View1,pc1,
673  View2,pc2>& p)
674  : Propagator(home,share,p) {
675  x0.update(home,share,p.x0);
676  x1.update(home,share,p.x1);
677  x2.update(home,share,p.x2);
678  }
679 
680  template<class View0, PropCond pc0, class View1, PropCond pc1,
681  class View2, PropCond pc2>
684  (Space& home, bool share, Propagator& p, View0 y0, View1 y1, View2 y2)
685  : Propagator(home,share,p) {
686  x0.update(home,share,y0);
687  x1.update(home,share,y1);
688  x2.update(home,share,y2);
689  }
690 
691  template<class View0, PropCond pc0, class View1, PropCond pc1,
692  class View2, PropCond pc2>
693  PropCost
695  cost(const Space&, const ModEventDelta&) const {
696  return PropCost::ternary(PropCost::LO);
697  }
698 
699  template<class View0, PropCond pc0, class View1, PropCond pc1,
700  class View2, PropCond pc2>
701  void
703  if (pc0 != PC_GEN_NONE)
704  x0.reschedule(home,*this,pc0);
705  if (pc1 != PC_GEN_NONE)
706  x1.reschedule(home,*this,pc1);
707  if (pc2 != PC_GEN_NONE)
708  x2.reschedule(home,*this,pc2);
709  }
710 
711  template<class View0, PropCond pc0, class View1, PropCond pc1,
712  class View2, PropCond pc2>
713  forceinline size_t
715  if (pc0 != PC_GEN_NONE)
716  x0.cancel(home,*this,pc0);
717  if (pc1 != PC_GEN_NONE)
718  x1.cancel(home,*this,pc1);
719  if (pc2 != PC_GEN_NONE)
720  x2.cancel(home,*this,pc2);
721  (void) Propagator::dispose(home);
722  return sizeof(*this);
723  }
724 
725  /*
726  * MixNaryOne (one additional variable) propagators
727  *
728  */
729 
730  template<class View0, PropCond pc0, class View1, PropCond pc1>
732  (Home home, ViewArray<View0>& x0, View1 y0)
733  : Propagator(home), x(x0), y(y0) {
734  if (pc0 != PC_GEN_NONE)
735  x.subscribe(home,*this,pc0);
736  if (pc1 != PC_GEN_NONE)
737  y.subscribe(home,*this,pc1);
738  }
739 
740  template<class View0, PropCond pc0, class View1, PropCond pc1>
744  : Propagator(home,share,p) {
745  x.update(home,share,p.x);
746  y.update(home,share,p.y);
747  }
748 
749  template<class View0, PropCond pc0, class View1, PropCond pc1>
752  (Space& home, bool share, Propagator& p, ViewArray<View0>& x0, View1 y0)
753  : Propagator(home,share,p) {
754  x.update(home,share,x0);
755  y.update(home,share,y0);
756  }
757 
758  template<class View0, PropCond pc0, class View1, PropCond pc1>
759  PropCost
761  const ModEventDelta&) const {
762  return PropCost::linear(PropCost::LO,x.size()+1);
763  }
764 
765  template<class View0, PropCond pc0, class View1, PropCond pc1>
766  void
768  if (pc0 != PC_GEN_NONE)
769  x.reschedule(home,*this,pc0);
770  if (pc1 != PC_GEN_NONE)
771  y.reschedule(home,*this,pc1);
772  }
773 
774  template<class View0, PropCond pc0, class View1, PropCond pc1>
775  forceinline size_t
777  if (pc0 != PC_GEN_NONE)
778  x.cancel(home,*this,pc0);
779  if (pc1 != PC_GEN_NONE)
780  y.cancel(home,*this,pc1);
781  (void) Propagator::dispose(home);
782  return sizeof(*this);
783  }
784 
785 }
786 
787 // STATISTICS: kernel-prop
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:154
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1429
ViewArray< View > x
Array of views.
Definition: propagator.hpp:183
View0 x0
View of type View0.
Definition: propagator.hpp:216
Unary propagator.
Definition: propagator.hpp:59
View y
Single view.
Definition: propagator.hpp:185
View2 x2
View of type View2.
Definition: propagator.hpp:254
Mixed (n+1)-ary propagator.
Definition: propagator.hpp:282
ViewArray< View > x
Array of views.
Definition: propagator.hpp:152
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:45
Base-class for propagators.
Definition: core.hpp:1092
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
View x0
Three views.
Definition: propagator.hpp:122
View x0
Two views.
Definition: propagator.hpp:92
ViewArray< View0 > x
Array of views.
Definition: propagator.hpp:285
View x0
Single view.
Definition: propagator.hpp:62
View1 x1
View of type View1.
Definition: propagator.hpp:218
Computation spaces.
Definition: core.hpp:1748
virtual void reschedule(Space &home)
Schedule function.
Definition: propagator.hpp:342
View0 x0
View of type View0.
Definition: propagator.hpp:250
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Binary propagator.
Definition: propagator.hpp:89
Mixed ternary propagator.
Definition: propagator.hpp:247
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_UNARY_LO)
Definition: propagator.hpp:336
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
UnaryPropagator(Space &home, bool share, UnaryPropagator &p)
Constructor for cloning p.
Definition: propagator.hpp:321
Ternary propagator.
Definition: propagator.hpp:119
n-ary propagator
Definition: propagator.hpp:149
(n+1)-ary propagator
Definition: propagator.hpp:180
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:349
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Mixed binary propagator.
Definition: propagator.hpp:213
Propagation cost.
Definition: core.hpp:554
#define forceinline
Definition: config.hpp:173
Gecode toplevel namespace
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl)
Post propagators for scheduling tasks on unary resources.
Definition: unary.cpp:48
View1 x1
View of type View1.
Definition: propagator.hpp:252