Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
pattern.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$ by $Author$
13  * $Revision$
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;
66  UnaryPropagator(Space& home, Propagator& p, View x0);
68  UnaryPropagator(Home home, View x0);
69  public:
71  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
73  virtual void reschedule(Space& home);
75  virtual size_t dispose(Space& home);
76  };
77 
87  template<class View, PropCond pc>
88  class BinaryPropagator : public Propagator {
89  protected:
91  View x0, x1;
95  BinaryPropagator(Home home, View x0, View x1);
97  BinaryPropagator(Space& home, Propagator& p, View x0, View x1);
98  public:
100  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
102  virtual void reschedule(Space& home);
104  virtual size_t dispose(Space& home);
105  };
106 
116  template<class View, PropCond pc>
117  class TernaryPropagator : public Propagator {
118  protected:
120  View x0, x1, x2;
124  TernaryPropagator(Home home, View x0, View x1, View x2);
126  TernaryPropagator(Space& home, Propagator& p, View x0, View x1, View x2);
127  public:
129  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
131  virtual void reschedule(Space& home);
133  virtual size_t dispose(Space& home);
134  };
135 
145  template<class View, PropCond pc>
146  class NaryPropagator : public Propagator {
147  protected:
156  public:
158  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
160  virtual void reschedule(Space& home);
162  virtual size_t dispose(Space& home);
163  };
164 
175  template<class View, PropCond pc>
176  class NaryOnePropagator : public Propagator {
177  protected:
181  View y;
185  NaryOnePropagator(Space& home, Propagator& p, ViewArray<View>& x, View y);
187  NaryOnePropagator(Home home, ViewArray<View>& x, View y);
188  public:
190  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
192  virtual void reschedule(Space& home);
194  virtual size_t dispose(Space& home);
195  };
196 
207  template<class View0, PropCond pc0, class View1, PropCond pc1>
209  protected:
211  View0 x0;
213  View1 x1;
217  MixBinaryPropagator(Home home, View0 x0, View1 x1);
219  MixBinaryPropagator(Space& home, Propagator& p, View0 x0, View1 x1);
220  public:
222  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
224  virtual void reschedule(Space& home);
226  virtual size_t dispose(Space& home);
227  };
228 
239  template<class View0, PropCond pc0, class View1, PropCond pc1,
240  class View2, PropCond pc2>
242  protected:
244  View0 x0;
246  View1 x1;
248  View2 x2;
252  MixTernaryPropagator(Home home, View0 x0, View1 x1, View2 x2);
255  View0 x0, View1 x1, View2 x2);
256  public:
258  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
260  virtual void reschedule(Space& home);
262  virtual size_t dispose(Space& home);
263  };
264 
275  template<class View0, PropCond pc0, class View1, PropCond pc1>
277  protected:
281  View1 y;
285  MixNaryOnePropagator(Home home, ViewArray<View0>& x, View1 y);
288  ViewArray<View0>& x, View1 y);
289  public:
291  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
293  virtual void reschedule(Space& home);
295  virtual size_t dispose(Space& home);
296  };
298 
299 
300  /*
301  * Unary propagators
302  *
303  */
304 
305  template<class View, PropCond pc>
307  : Propagator(home), x0(y0) {
308  if (pc != PC_GEN_NONE)
309  x0.subscribe(home,*this,pc);
310  }
311 
312  template<class View, PropCond pc>
316  : Propagator(home,p) {
317  x0.update(home,p.x0);
318  }
319 
320  template<class View, PropCond pc>
323  (Space& home, Propagator& p, View y0)
324  : Propagator(home,p) {
325  x0.update(home,y0);
326  }
327 
328  template<class View, PropCond pc>
329  PropCost
331  return PropCost::unary(PropCost::LO);
332  }
333 
334  template<class View, PropCond pc>
335  void
337  if (pc != PC_GEN_NONE)
338  x0.reschedule(home,*this,pc);
339  }
340 
341  template<class View, PropCond pc>
342  forceinline size_t
344  if (pc != PC_GEN_NONE)
345  x0.cancel(home,*this,pc);
346  (void) Propagator::dispose(home);
347  return sizeof(*this);
348  }
349 
350 
351  /*
352  * Binary propagators
353  *
354  */
355 
356  template<class View, PropCond pc>
358  : Propagator(home), x0(y0), x1(y1) {
359  if (pc != PC_GEN_NONE) {
360  x0.subscribe(home,*this,pc);
361  x1.subscribe(home,*this,pc);
362  }
363  }
364 
365  template<class View, PropCond pc>
369  : Propagator(home,p) {
370  x0.update(home,p.x0);
371  x1.update(home,p.x1);
372  }
373 
374  template<class View, PropCond pc>
377  (Space& home, Propagator& p, View y0, View y1)
378  : Propagator(home,p) {
379  x0.update(home,y0);
380  x1.update(home,y1);
381  }
382 
383  template<class View, PropCond pc>
384  PropCost
386  return PropCost::binary(PropCost::LO);
387  }
388 
389  template<class View, PropCond pc>
390  void
392  if (pc != PC_GEN_NONE) {
393  x0.reschedule(home,*this,pc);
394  x1.reschedule(home,*this,pc);
395  }
396  }
397 
398  template<class View, PropCond pc>
399  forceinline size_t
401  if (pc != PC_GEN_NONE) {
402  x0.cancel(home,*this,pc);
403  x1.cancel(home,*this,pc);
404  }
405  (void) Propagator::dispose(home);
406  return sizeof(*this);
407  }
408 
409  /*
410  * Ternary propagators
411  *
412  */
413 
414  template<class View, PropCond pc>
416  (Home home, View y0, View y1, View y2)
417  : Propagator(home), x0(y0), x1(y1), x2(y2) {
418  if (pc != PC_GEN_NONE) {
419  x0.subscribe(home,*this,pc);
420  x1.subscribe(home,*this,pc);
421  x2.subscribe(home,*this,pc);
422  }
423  }
424 
425  template<class View, PropCond pc>
429  : Propagator(home,p) {
430  x0.update(home,p.x0);
431  x1.update(home,p.x1);
432  x2.update(home,p.x2);
433  }
434 
435  template<class View, PropCond pc>
438  (Space& home, Propagator& p, View y0, View y1, View y2)
439  : Propagator(home,p) {
440  x0.update(home,y0);
441  x1.update(home,y1);
442  x2.update(home,y2);
443  }
444 
445  template<class View, PropCond pc>
446  PropCost
448  return PropCost::ternary(PropCost::LO);;
449  }
450 
451  template<class View, PropCond pc>
452  void
454  if (pc != PC_GEN_NONE) {
455  x0.reschedule(home,*this,pc);
456  x1.reschedule(home,*this,pc);
457  x2.reschedule(home,*this,pc);
458  }
459  }
460 
461  template<class View, PropCond pc>
462  forceinline size_t
464  if (pc != PC_GEN_NONE) {
465  x0.cancel(home,*this,pc);
466  x1.cancel(home,*this,pc);
467  x2.cancel(home,*this,pc);
468  }
469  (void) Propagator::dispose(home);
470  return sizeof(*this);
471  }
472 
473  /*
474  * Nary propagators
475  *
476  */
477 
478  template<class View, PropCond pc>
481  : Propagator(home), x(y) {
482  if (pc != PC_GEN_NONE)
483  x.subscribe(home,*this,pc);
484  }
485 
486  template<class View, PropCond pc>
490  : Propagator(home,p) {
491  x.update(home,p.x);
492  }
493 
494  template<class View, PropCond pc>
498  : Propagator(home,p) {
499  x.update(home,x0);
500  }
501 
502  template<class View, PropCond pc>
503  PropCost
505  return PropCost::linear(PropCost::LO,x.size());
506  }
507 
508  template<class View, PropCond pc>
509  void
511  if (pc != PC_GEN_NONE)
512  x.reschedule(home,*this,pc);
513  }
514 
515  template<class View, PropCond pc>
516  forceinline size_t
518  if (pc != PC_GEN_NONE)
519  x.cancel(home,*this,pc);
520  (void) Propagator::dispose(home);
521  return sizeof(*this);
522  }
523 
524  /*
525  * NaryOne (one additional variable) propagators
526  *
527  */
528 
529  template<class View, PropCond pc>
531  (Home home, ViewArray<View>& x0, View y0)
532  : Propagator(home), x(x0), y(y0) {
533  if (pc != PC_GEN_NONE) {
534  x.subscribe(home,*this,pc);
535  y.subscribe(home,*this,pc);
536  }
537  }
538 
539  template<class View, PropCond pc>
543  : Propagator(home,p) {
544  x.update(home,p.x);
545  y.update(home,p.y);
546  }
547 
548  template<class View, PropCond pc>
551  (Space& home, Propagator& p, ViewArray<View>& x0, View y0)
552  : Propagator(home,p) {
553  x.update(home,x0);
554  y.update(home,y0);
555  }
556 
557  template<class View, PropCond pc>
558  PropCost
560  return PropCost::linear(PropCost::LO,x.size()+1);
561  }
562 
563  template<class View, PropCond pc>
564  void
566  if (pc != PC_GEN_NONE) {
567  x.reschedule(home,*this,pc);
568  y.reschedule(home,*this,pc);
569  }
570  }
571 
572  template<class View, PropCond pc>
573  forceinline size_t
575  if (pc != PC_GEN_NONE) {
576  x.cancel(home,*this,pc);
577  y.cancel(home,*this,pc);
578  }
579  (void) Propagator::dispose(home);
580  return sizeof(*this);
581  }
582 
583  /*
584  * Mixed binary propagators
585  *
586  */
587 
588  template<class View0, PropCond pc0, class View1, PropCond pc1>
590  (Home home, View0 y0, View1 y1)
591  : Propagator(home), x0(y0), x1(y1) {
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  }
597 
598  template<class View0, PropCond pc0, class View1, PropCond pc1>
602  : Propagator(home,p) {
603  x0.update(home,p.x0);
604  x1.update(home,p.x1);
605  }
606 
607  template<class View0, PropCond pc0, class View1, PropCond pc1>
610  (Space& home, Propagator& p, View0 y0, View1 y1)
611  : Propagator(home,p) {
612  x0.update(home,y0);
613  x1.update(home,y1);
614  }
615 
616  template<class View0, PropCond pc0, class View1, PropCond pc1>
617  PropCost
619  const ModEventDelta&) const {
620  return PropCost::binary(PropCost::LO);
621  }
622 
623  template<class View0, PropCond pc0, class View1, PropCond pc1>
624  void
626  if (pc0 != PC_GEN_NONE)
627  x0.reschedule(home,*this,pc0);
628  if (pc1 != PC_GEN_NONE)
629  x1.reschedule(home,*this,pc1);
630  }
631 
632  template<class View0, PropCond pc0, class View1, PropCond pc1>
633  forceinline size_t
635  if (pc0 != PC_GEN_NONE)
636  x0.cancel(home,*this,pc0);
637  if (pc1 != PC_GEN_NONE)
638  x1.cancel(home,*this,pc1);
639  (void) Propagator::dispose(home);
640  return sizeof(*this);
641  }
642 
643  /*
644  * Mixed ternary propagators
645  *
646  */
647 
648  template<class View0, PropCond pc0, class View1, PropCond pc1,
649  class View2, PropCond pc2>
651  MixTernaryPropagator(Home home, View0 y0, View1 y1, View2 y2)
652  : Propagator(home), x0(y0), x1(y1), x2(y2) {
653  if (pc0 != PC_GEN_NONE)
654  x0.subscribe(home,*this,pc0);
655  if (pc1 != PC_GEN_NONE)
656  x1.subscribe(home,*this,pc1);
657  if (pc2 != PC_GEN_NONE)
658  x2.subscribe(home,*this,pc2);
659  }
660 
661  template<class View0, PropCond pc0, class View1, PropCond pc1,
662  class View2, PropCond pc2>
666  MixTernaryPropagator<View0,pc0,View1,pc1,
667  View2,pc2>& p)
668  : Propagator(home,p) {
669  x0.update(home,p.x0);
670  x1.update(home,p.x1);
671  x2.update(home,p.x2);
672  }
673 
674  template<class View0, PropCond pc0, class View1, PropCond pc1,
675  class View2, PropCond pc2>
678  (Space& home, Propagator& p, View0 y0, View1 y1, View2 y2)
679  : Propagator(home,p) {
680  x0.update(home,y0);
681  x1.update(home,y1);
682  x2.update(home,y2);
683  }
684 
685  template<class View0, PropCond pc0, class View1, PropCond pc1,
686  class View2, PropCond pc2>
687  PropCost
689  cost(const Space&, const ModEventDelta&) const {
690  return PropCost::ternary(PropCost::LO);
691  }
692 
693  template<class View0, PropCond pc0, class View1, PropCond pc1,
694  class View2, PropCond pc2>
695  void
697  if (pc0 != PC_GEN_NONE)
698  x0.reschedule(home,*this,pc0);
699  if (pc1 != PC_GEN_NONE)
700  x1.reschedule(home,*this,pc1);
701  if (pc2 != PC_GEN_NONE)
702  x2.reschedule(home,*this,pc2);
703  }
704 
705  template<class View0, PropCond pc0, class View1, PropCond pc1,
706  class View2, PropCond pc2>
707  forceinline size_t
709  if (pc0 != PC_GEN_NONE)
710  x0.cancel(home,*this,pc0);
711  if (pc1 != PC_GEN_NONE)
712  x1.cancel(home,*this,pc1);
713  if (pc2 != PC_GEN_NONE)
714  x2.cancel(home,*this,pc2);
715  (void) Propagator::dispose(home);
716  return sizeof(*this);
717  }
718 
719  /*
720  * MixNaryOne (one additional variable) propagators
721  *
722  */
723 
724  template<class View0, PropCond pc0, class View1, PropCond pc1>
726  (Home home, ViewArray<View0>& x0, View1 y0)
727  : Propagator(home), x(x0), y(y0) {
728  if (pc0 != PC_GEN_NONE)
729  x.subscribe(home,*this,pc0);
730  if (pc1 != PC_GEN_NONE)
731  y.subscribe(home,*this,pc1);
732  }
733 
734  template<class View0, PropCond pc0, class View1, PropCond pc1>
738  : Propagator(home,p) {
739  x.update(home,p.x);
740  y.update(home,p.y);
741  }
742 
743  template<class View0, PropCond pc0, class View1, PropCond pc1>
746  (Space& home, Propagator& p, ViewArray<View0>& x0, View1 y0)
747  : Propagator(home,p) {
748  x.update(home,x0);
749  y.update(home,y0);
750  }
751 
752  template<class View0, PropCond pc0, class View1, PropCond pc1>
753  PropCost
755  const ModEventDelta&) const {
756  return PropCost::linear(PropCost::LO,x.size()+1);
757  }
758 
759  template<class View0, PropCond pc0, class View1, PropCond pc1>
760  void
762  if (pc0 != PC_GEN_NONE)
763  x.reschedule(home,*this,pc0);
764  if (pc1 != PC_GEN_NONE)
765  y.reschedule(home,*this,pc1);
766  }
767 
768  template<class View0, PropCond pc0, class View1, PropCond pc1>
769  forceinline size_t
771  if (pc0 != PC_GEN_NONE)
772  x.cancel(home,*this,pc0);
773  if (pc1 != PC_GEN_NONE)
774  y.cancel(home,*this,pc1);
775  (void) Propagator::dispose(home);
776  return sizeof(*this);
777  }
778 
779 }
780 
781 // STATISTICS: kernel-prop
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:76
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1417
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1375
ViewArray< View > x
Array of views.
Definition: pattern.hpp:179
View1 y
Single view.
Definition: pattern.hpp:281
View0 x0
View of type View0.
Definition: pattern.hpp:211
Unary propagator.
Definition: pattern.hpp:59
View y
Single view.
Definition: pattern.hpp:181
View2 x2
View of type View2.
Definition: pattern.hpp:248
Mixed (n+1)-ary propagator.
Definition: pattern.hpp:276
ViewArray< View > x
Array of views.
Definition: pattern.hpp:149
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:1016
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1388
View x0
Three views.
Definition: pattern.hpp:120
View x0
Two views.
Definition: pattern.hpp:91
ViewArray< View0 > x
Array of views.
Definition: pattern.hpp:279
View x0
Single view.
Definition: pattern.hpp:62
#define forceinline
Definition: config.hpp:182
View1 x1
View of type View1.
Definition: pattern.hpp:213
Computation spaces.
Definition: core.hpp:1668
virtual void reschedule(Space &home)
Schedule function.
Definition: pattern.hpp:336
View0 x0
View of type View0.
Definition: pattern.hpp:244
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Binary propagator.
Definition: pattern.hpp:88
Mixed ternary propagator.
Definition: pattern.hpp:241
int PropCond
Type for propagation conditions.
Definition: core.hpp:74
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_UNARY_LO)
Definition: pattern.hpp:330
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1027
UnaryPropagator(Space &home, UnaryPropagator &p)
Constructor for cloning p.
Definition: pattern.hpp:315
Ternary propagator.
Definition: pattern.hpp:117
n-ary propagator
Definition: pattern.hpp:146
(n+1)-ary propagator
Definition: pattern.hpp:176
View arrays.
Definition: array.hpp:228
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1396
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: pattern.hpp:343
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Mixed binary propagator.
Definition: pattern.hpp:208
Propagation cost.
Definition: core.hpp:478
Gecode toplevel namespace
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846
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: pattern.hpp:246