Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36namespace Gecode {
37
43
45
54 template<class View, PropCond pc>
55 class UnaryPropagator : public Propagator {
56 protected:
65 public:
67 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
69 virtual void reschedule(Space& home);
71 virtual size_t dispose(Space& home);
72 };
73
83 template<class View, PropCond pc>
85 protected:
94 public:
96 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
98 virtual void reschedule(Space& home);
100 virtual size_t dispose(Space& home);
101 };
102
112 template<class View, PropCond pc>
114 protected:
123 public:
125 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
127 virtual void reschedule(Space& home);
129 virtual size_t dispose(Space& home);
130 };
131
141 template<class View, PropCond pc>
142 class NaryPropagator : public Propagator {
143 protected:
152 public:
154 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
156 virtual void reschedule(Space& home);
158 virtual size_t dispose(Space& home);
159 };
160
171 template<class View, PropCond pc>
173 protected:
184 public:
186 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
188 virtual void reschedule(Space& home);
190 virtual size_t dispose(Space& home);
191 };
192
203 template<class View0, PropCond pc0, class View1, PropCond pc1>
205 protected:
207 View0 x0;
209 View1 x1;
213 MixBinaryPropagator(Home home, View0 x0, View1 x1);
215 MixBinaryPropagator(Space& home, Propagator& p, View0 x0, View1 x1);
216 public:
218 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
220 virtual void reschedule(Space& home);
222 virtual size_t dispose(Space& home);
223 };
224
235 template<class View0, PropCond pc0, class View1, PropCond pc1,
236 class View2, PropCond pc2>
238 protected:
240 View0 x0;
242 View1 x1;
244 View2 x2;
248 MixTernaryPropagator(Home home, View0 x0, View1 x1, View2 x2);
251 View0 x0, View1 x1, View2 x2);
252 public:
254 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
256 virtual void reschedule(Space& home);
258 virtual size_t dispose(Space& home);
259 };
260
271 template<class View0, PropCond pc0, class View1, PropCond pc1>
273 protected:
277 View1 y;
284 ViewArray<View0>& x, View1 y);
285 public:
287 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
289 virtual void reschedule(Space& home);
291 virtual size_t dispose(Space& home);
292 };
293
294
295
296 /*
297 * Unary propagators
298 *
299 */
300
301 template<class View, PropCond pc>
303 : Propagator(home), x0(y0) {
304 if (pc != PC_GEN_NONE)
305 x0.subscribe(home,*this,pc);
306 }
307
308 template<class View, PropCond pc>
312 : Propagator(home,p) {
313 x0.update(home,p.x0);
314 }
315
316 template<class View, PropCond pc>
319 (Space& home, Propagator& p, View y0)
320 : Propagator(home,p) {
321 x0.update(home,y0);
322 }
323
324 template<class View, PropCond pc>
329
330 template<class View, PropCond pc>
331 void
333 if (pc != PC_GEN_NONE)
334 x0.reschedule(home,*this,pc);
335 }
336
337 template<class View, PropCond pc>
338 forceinline size_t
340 if (pc != PC_GEN_NONE)
341 x0.cancel(home,*this,pc);
342 (void) Propagator::dispose(home);
343 return sizeof(*this);
344 }
345
346
347 /*
348 * Binary propagators
349 *
350 */
351
352 template<class View, PropCond pc>
354 : Propagator(home), x0(y0), x1(y1) {
355 if (pc != PC_GEN_NONE) {
356 x0.subscribe(home,*this,pc);
357 x1.subscribe(home,*this,pc);
358 }
359 }
360
361 template<class View, PropCond pc>
365 : Propagator(home,p) {
366 x0.update(home,p.x0);
367 x1.update(home,p.x1);
368 }
369
370 template<class View, PropCond pc>
373 (Space& home, Propagator& p, View y0, View y1)
374 : Propagator(home,p) {
375 x0.update(home,y0);
376 x1.update(home,y1);
377 }
378
379 template<class View, PropCond pc>
384
385 template<class View, PropCond pc>
386 void
388 if (pc != PC_GEN_NONE) {
389 x0.reschedule(home,*this,pc);
390 x1.reschedule(home,*this,pc);
391 }
392 }
393
394 template<class View, PropCond pc>
395 forceinline size_t
397 if (pc != PC_GEN_NONE) {
398 x0.cancel(home,*this,pc);
399 x1.cancel(home,*this,pc);
400 }
401 (void) Propagator::dispose(home);
402 return sizeof(*this);
403 }
404
405 /*
406 * Ternary propagators
407 *
408 */
409
410 template<class View, PropCond pc>
412 (Home home, View y0, View y1, View y2)
413 : Propagator(home), x0(y0), x1(y1), x2(y2) {
414 if (pc != PC_GEN_NONE) {
415 x0.subscribe(home,*this,pc);
416 x1.subscribe(home,*this,pc);
417 x2.subscribe(home,*this,pc);
418 }
419 }
420
421 template<class View, PropCond pc>
425 : Propagator(home,p) {
426 x0.update(home,p.x0);
427 x1.update(home,p.x1);
428 x2.update(home,p.x2);
429 }
430
431 template<class View, PropCond pc>
434 (Space& home, Propagator& p, View y0, View y1, View y2)
435 : Propagator(home,p) {
436 x0.update(home,y0);
437 x1.update(home,y1);
438 x2.update(home,y2);
439 }
440
441 template<class View, PropCond pc>
446
447 template<class View, PropCond pc>
448 void
450 if (pc != PC_GEN_NONE) {
451 x0.reschedule(home,*this,pc);
452 x1.reschedule(home,*this,pc);
453 x2.reschedule(home,*this,pc);
454 }
455 }
456
457 template<class View, PropCond pc>
458 forceinline size_t
460 if (pc != PC_GEN_NONE) {
461 x0.cancel(home,*this,pc);
462 x1.cancel(home,*this,pc);
463 x2.cancel(home,*this,pc);
464 }
465 (void) Propagator::dispose(home);
466 return sizeof(*this);
467 }
468
469 /*
470 * Nary propagators
471 *
472 */
473
474 template<class View, PropCond pc>
476 (Home home, ViewArray<View>& y)
477 : Propagator(home), x(y) {
478 if (pc != PC_GEN_NONE)
479 x.subscribe(home,*this,pc);
480 }
481
482 template<class View, PropCond pc>
486 : Propagator(home,p) {
487 x.update(home,p.x);
488 }
489
490 template<class View, PropCond pc>
493 (Space& home, Propagator& p, ViewArray<View>& x0)
494 : Propagator(home,p) {
495 x.update(home,x0);
496 }
497
498 template<class View, PropCond pc>
501 return PropCost::linear(PropCost::LO,x.size());
502 }
503
504 template<class View, PropCond pc>
505 void
507 if (pc != PC_GEN_NONE)
508 x.reschedule(home,*this,pc);
509 }
510
511 template<class View, PropCond pc>
512 forceinline size_t
514 if (pc != PC_GEN_NONE)
515 x.cancel(home,*this,pc);
516 (void) Propagator::dispose(home);
517 return sizeof(*this);
518 }
519
520 /*
521 * NaryOne (one additional variable) propagators
522 *
523 */
524
525 template<class View, PropCond pc>
527 (Home home, ViewArray<View>& x0, View y0)
528 : Propagator(home), x(x0), y(y0) {
529 if (pc != PC_GEN_NONE) {
530 x.subscribe(home,*this,pc);
531 y.subscribe(home,*this,pc);
532 }
533 }
534
535 template<class View, PropCond pc>
539 : Propagator(home,p) {
540 x.update(home,p.x);
541 y.update(home,p.y);
542 }
543
544 template<class View, PropCond pc>
547 (Space& home, Propagator& p, ViewArray<View>& x0, View y0)
548 : Propagator(home,p) {
549 x.update(home,x0);
550 y.update(home,y0);
551 }
552
553 template<class View, PropCond pc>
556 return PropCost::linear(PropCost::LO,x.size()+1);
557 }
558
559 template<class View, PropCond pc>
560 void
562 if (pc != PC_GEN_NONE) {
563 x.reschedule(home,*this,pc);
564 y.reschedule(home,*this,pc);
565 }
566 }
567
568 template<class View, PropCond pc>
569 forceinline size_t
571 if (pc != PC_GEN_NONE) {
572 x.cancel(home,*this,pc);
573 y.cancel(home,*this,pc);
574 }
575 (void) Propagator::dispose(home);
576 return sizeof(*this);
577 }
578
579 /*
580 * Mixed binary propagators
581 *
582 */
583
584 template<class View0, PropCond pc0, class View1, PropCond pc1>
586 (Home home, View0 y0, View1 y1)
587 : Propagator(home), x0(y0), x1(y1) {
588 if (pc0 != PC_GEN_NONE)
589 x0.subscribe(home,*this,pc0);
590 if (pc1 != PC_GEN_NONE)
591 x1.subscribe(home,*this,pc1);
592 }
593
594 template<class View0, PropCond pc0, class View1, PropCond pc1>
598 : Propagator(home,p) {
599 x0.update(home,p.x0);
600 x1.update(home,p.x1);
601 }
602
603 template<class View0, PropCond pc0, class View1, PropCond pc1>
606 (Space& home, Propagator& p, View0 y0, View1 y1)
607 : Propagator(home,p) {
608 x0.update(home,y0);
609 x1.update(home,y1);
610 }
611
612 template<class View0, PropCond pc0, class View1, PropCond pc1>
618
619 template<class View0, PropCond pc0, class View1, PropCond pc1>
620 void
622 if (pc0 != PC_GEN_NONE)
623 x0.reschedule(home,*this,pc0);
624 if (pc1 != PC_GEN_NONE)
625 x1.reschedule(home,*this,pc1);
626 }
627
628 template<class View0, PropCond pc0, class View1, PropCond pc1>
629 forceinline size_t
631 if (pc0 != PC_GEN_NONE)
632 x0.cancel(home,*this,pc0);
633 if (pc1 != PC_GEN_NONE)
634 x1.cancel(home,*this,pc1);
635 (void) Propagator::dispose(home);
636 return sizeof(*this);
637 }
638
639 /*
640 * Mixed ternary propagators
641 *
642 */
643
644 template<class View0, PropCond pc0, class View1, PropCond pc1,
645 class View2, PropCond pc2>
647 MixTernaryPropagator(Home home, View0 y0, View1 y1, View2 y2)
648 : Propagator(home), x0(y0), x1(y1), x2(y2) {
649 if (pc0 != PC_GEN_NONE)
650 x0.subscribe(home,*this,pc0);
651 if (pc1 != PC_GEN_NONE)
652 x1.subscribe(home,*this,pc1);
653 if (pc2 != PC_GEN_NONE)
654 x2.subscribe(home,*this,pc2);
655 }
656
657 template<class View0, PropCond pc0, class View1, PropCond pc1,
658 class View2, PropCond pc2>
662 MixTernaryPropagator<View0,pc0,View1,pc1,
663 View2,pc2>& p)
664 : Propagator(home,p) {
665 x0.update(home,p.x0);
666 x1.update(home,p.x1);
667 x2.update(home,p.x2);
668 }
669
670 template<class View0, PropCond pc0, class View1, PropCond pc1,
671 class View2, PropCond pc2>
674 (Space& home, Propagator& p, View0 y0, View1 y1, View2 y2)
675 : Propagator(home,p) {
676 x0.update(home,y0);
677 x1.update(home,y1);
678 x2.update(home,y2);
679 }
680
681 template<class View0, PropCond pc0, class View1, PropCond pc1,
682 class View2, PropCond pc2>
688
689 template<class View0, PropCond pc0, class View1, PropCond pc1,
690 class View2, PropCond pc2>
691 void
693 if (pc0 != PC_GEN_NONE)
694 x0.reschedule(home,*this,pc0);
695 if (pc1 != PC_GEN_NONE)
696 x1.reschedule(home,*this,pc1);
697 if (pc2 != PC_GEN_NONE)
698 x2.reschedule(home,*this,pc2);
699 }
700
701 template<class View0, PropCond pc0, class View1, PropCond pc1,
702 class View2, PropCond pc2>
703 forceinline size_t
705 if (pc0 != PC_GEN_NONE)
706 x0.cancel(home,*this,pc0);
707 if (pc1 != PC_GEN_NONE)
708 x1.cancel(home,*this,pc1);
709 if (pc2 != PC_GEN_NONE)
710 x2.cancel(home,*this,pc2);
711 (void) Propagator::dispose(home);
712 return sizeof(*this);
713 }
714
715 /*
716 * MixNaryOne (one additional variable) propagators
717 *
718 */
719
720 template<class View0, PropCond pc0, class View1, PropCond pc1>
722 (Home home, ViewArray<View0>& x0, View1 y0)
723 : Propagator(home), x(x0), y(y0) {
724 if (pc0 != PC_GEN_NONE)
725 x.subscribe(home,*this,pc0);
726 if (pc1 != PC_GEN_NONE)
727 y.subscribe(home,*this,pc1);
728 }
729
730 template<class View0, PropCond pc0, class View1, PropCond pc1>
734 : Propagator(home,p) {
735 x.update(home,p.x);
736 y.update(home,p.y);
737 }
738
739 template<class View0, PropCond pc0, class View1, PropCond pc1>
742 (Space& home, Propagator& p, ViewArray<View0>& x0, View1 y0)
743 : Propagator(home,p) {
744 x.update(home,x0);
745 y.update(home,y0);
746 }
747
748 template<class View0, PropCond pc0, class View1, PropCond pc1>
754
755 template<class View0, PropCond pc0, class View1, PropCond pc1>
756 void
758 if (pc0 != PC_GEN_NONE)
759 x.reschedule(home,*this,pc0);
760 if (pc1 != PC_GEN_NONE)
761 y.reschedule(home,*this,pc1);
762 }
763
764 template<class View0, PropCond pc0, class View1, PropCond pc1>
765 forceinline size_t
767 if (pc0 != PC_GEN_NONE)
768 x.cancel(home,*this,pc0);
769 if (pc1 != PC_GEN_NONE)
770 y.cancel(home,*this,pc1);
771 (void) Propagator::dispose(home);
772 return sizeof(*this);
773 }
774
775}
776
777// STATISTICS: kernel-prop
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3256
Binary propagator.
Definition pattern.hpp:84
View x0
Two views.
Definition pattern.hpp:87
BinaryPropagator(Space &home, BinaryPropagator &p)
Constructor for cloning p.
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:387
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:396
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low binary)
Definition pattern.hpp:381
Home class for posting propagators
Definition core.hpp:856
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:621
View1 x1
View of type View1.
Definition pattern.hpp:209
MixBinaryPropagator(Space &home, MixBinaryPropagator &p)
Constructor for cloning.
Definition pattern.hpp:597
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low binary)
Definition pattern.hpp:614
View0 x0
View of type View0.
Definition pattern.hpp:207
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:630
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:766
MixNaryOnePropagator(Space &home, MixNaryOnePropagator &p)
Constructor for cloning p.
Definition pattern.hpp:733
MixNaryOnePropagator(Home home, ViewArray< View0 > &x, View1 y)
Constructor for creation.
Definition pattern.hpp:722
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition pattern.hpp:750
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:757
MixNaryOnePropagator(Space &home, Propagator &p, ViewArray< View0 > &x, View1 y)
Constructor for rewriting p during cloning.
Definition pattern.hpp:742
View0 x0
View of type View0.
Definition pattern.hpp:240
View1 x1
View of type View1.
Definition pattern.hpp:242
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:704
View2 x2
View of type View2.
Definition pattern.hpp:244
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:692
MixTernaryPropagator(Space &home, MixTernaryPropagator &p)
Constructor for cloning.
Definition pattern.hpp:661
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low ternary)
Definition pattern.hpp:685
(n+1)-ary propagator
Definition pattern.hpp:172
ViewArray< View > x
Array of views.
Definition pattern.hpp:175
NaryOnePropagator(Space &home, NaryOnePropagator &p)
Constructor for cloning p.
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:561
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition pattern.hpp:555
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:570
View y
Single view.
Definition pattern.hpp:177
n-ary propagator
Definition pattern.hpp:142
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:513
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition pattern.hpp:500
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:506
ViewArray< View > x
Array of views.
Definition pattern.hpp:145
NaryPropagator(Space &home, NaryPropagator &p)
Constructor for cloning p.
Propagation cost.
Definition core.hpp:486
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4820
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition core.hpp:4812
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4803
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition core.hpp:4816
Base-class for propagators.
Definition core.hpp:1066
friend class Space
Definition core.hpp:1068
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1077
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Computation spaces.
Definition core.hpp:1744
Ternary propagator.
Definition pattern.hpp:113
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:459
View x0
Three views.
Definition pattern.hpp:116
TernaryPropagator(Space &home, TernaryPropagator &p)
Constructor for cloning p.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low ternary)
Definition pattern.hpp:443
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:449
Unary propagator.
Definition pattern.hpp:55
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_UNARY_LO)
Definition pattern.hpp:326
virtual void reschedule(Space &home)
Schedule function.
Definition pattern.hpp:332
View x0
Single view.
Definition pattern.hpp:58
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:339
UnaryPropagator(Space &home, UnaryPropagator &p)
Constructor for cloning p.
View arrays.
Definition array.hpp:253
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Post propagator for SetVar x
Definition set.hh:773
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition core.hpp:74
#define forceinline
Definition config.hpp:194