this repo has no description
dekker.one
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
36#ifndef GECODE_INT_ARITHMETIC_HH
37#define GECODE_INT_ARITHMETIC_HH
38
39#include <gecode/int.hh>
40
41#include <gecode/int/idx-view.hh>
42#include <gecode/int/rel.hh>
43#include <gecode/int/linear.hh>
44
45/**
46 * \namespace Gecode::Int::Arithmetic
47 * \brief Numerical (arithmetic) propagators
48 */
49
50namespace Gecode { namespace Int { namespace Arithmetic {
51
52 /**
53 * \brief Bounds consistent absolute value propagator
54 *
55 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
56 * \ingroup FuncIntProp
57 */
58 template<class View>
59 class AbsBnd : public BinaryPropagator<View,PC_INT_BND> {
60 protected:
61 using BinaryPropagator<View,PC_INT_BND>::x0;
62 using BinaryPropagator<View,PC_INT_BND>::x1;
63
64 /// Constructor for cloning \a p
65 AbsBnd(Space& home, AbsBnd& p);
66 /// Constructor for posting
67 AbsBnd(Home home, View x0, View x1);
68 public:
69
70 /// Copy propagator during cloning
71 virtual Actor* copy(Space& home);
72 /**
73 * \brief Cost function
74 *
75 * If a view has been assigned, the cost is low unary.
76 * Otherwise it is low binary.
77 */
78 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
79 /// Perform propagation
80 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
81 /// Post bounds consistent propagator \f$ |x_0|=x_1\f$
82 static ExecStatus post(Home home, View x0, View x1);
83 };
84
85 /**
86 * \brief Domain consistent absolute value propagator
87 *
88 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
89 * \ingroup FuncIntProp
90 */
91 template<class View>
92 class AbsDom : public BinaryPropagator<View,PC_INT_DOM> {
93 protected:
94 using BinaryPropagator<View,PC_INT_DOM>::x0;
95 using BinaryPropagator<View,PC_INT_DOM>::x1;
96
97 /// Constructor for cloning \a p
98 AbsDom(Space& home, AbsDom& p);
99 /// Constructor for posting
100 AbsDom(Home home, View x0, View x1);
101 public:
102 /// Copy propagator during cloning
103 virtual Actor* copy(Space& home);
104 /**
105 * \brief Cost function
106 *
107 * If a view has been assigned, the cost is low binary.
108 * If in stage for bounds propagation, the cost is
109 * low binary. Otherwise it is high binary.
110 */
111 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
112 /// Perform propagation
113 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
114 /// Post domain consistent propagator \f$ |x_0|=x_1\f$
115 static ExecStatus post(Home home, View x0, View x1);
116 };
117
118}}}
119
120#include <gecode/int/arithmetic/abs.hpp>
121
122namespace Gecode { namespace Int { namespace Arithmetic {
123
124 /**
125 * \brief Bounds consistent ternary maximum propagator
126 *
127 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
128 * \ingroup FuncIntProp
129 */
130 template<class View>
131 class MaxBnd : public TernaryPropagator<View,PC_INT_BND> {
132 protected:
133 using TernaryPropagator<View,PC_INT_BND>::x0;
134 using TernaryPropagator<View,PC_INT_BND>::x1;
135 using TernaryPropagator<View,PC_INT_BND>::x2;
136
137 /// Constructor for cloning \a p
138 MaxBnd(Space& home, MaxBnd& p);
139 /// Constructor for posting
140 MaxBnd(Home home, View x0, View x1, View x2);
141 public:
142 /// Constructor for rewriting \a p during cloning
143 MaxBnd(Space& home, Propagator& p, View x0, View x1, View x2);
144 /// Copy propagator during cloning
145 virtual Actor* copy(Space& home);
146 /// Perform propagation
147 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
148 /// Post propagator \f$ \max\{x_0,x_1\}=x_2\f$
149 static ExecStatus post(Home home, View x0, View x1, View x2);
150 };
151
152 /**
153 * \brief Bounds consistent n-ary maximum propagator
154 *
155 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
156 * \ingroup FuncIntProp
157 */
158 template<class View>
159 class NaryMaxBnd : public NaryOnePropagator<View,PC_INT_BND> {
160 protected:
161 using NaryOnePropagator<View,PC_INT_BND>::x;
162 using NaryOnePropagator<View,PC_INT_BND>::y;
163
164 /// Constructor for cloning \a p
165 NaryMaxBnd(Space& home, NaryMaxBnd& p);
166 /// Constructor for posting
167 NaryMaxBnd(Home home, ViewArray<View>& x, View y);
168 public:
169 /// Copy propagator during cloning
170 virtual Actor* copy(Space& home);
171 /// Perform propagation
172 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
173 /// Post propagator \f$ \max x=y\f$
174 static ExecStatus post(Home home, ViewArray<View>& x, View y);
175 };
176
177 /**
178 * \brief Domain consistent ternary maximum propagator
179 *
180 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
181 * \ingroup FuncIntProp
182 */
183 template<class View>
184 class MaxDom : public TernaryPropagator<View,PC_INT_DOM> {
185 protected:
186 using TernaryPropagator<View,PC_INT_DOM>::x0;
187 using TernaryPropagator<View,PC_INT_DOM>::x1;
188 using TernaryPropagator<View,PC_INT_DOM>::x2;
189
190 /// Constructor for cloning \a p
191 MaxDom(Space& home, MaxDom& p);
192 /// Constructor for posting
193 MaxDom(Home home, View x0, View x1, View x2);
194 public:
195 /// Constructor for rewriting \a p during cloning
196 MaxDom(Space& home, Propagator& p, View x0, View x1, View x2);
197 /// Copy propagator during cloning
198 virtual Actor* copy(Space& home);
199 /**
200 * \brief Cost function
201 *
202 * If in stage for bounds propagation, the cost is
203 * low ternary. Otherwise it is high ternary.
204 */
205 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
206 /// Perform propagation
207 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
208 /// Post propagator \f$ \max\{x_0,x_1\}=x_2\f$
209 static ExecStatus post(Home home, View x0, View x1, View x2);
210 };
211
212 /**
213 * \brief Domain consistent n-ary maximum propagator
214 *
215 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
216 * \ingroup FuncIntProp
217 */
218 template<class View>
219 class NaryMaxDom : public NaryOnePropagator<View,PC_INT_DOM> {
220 protected:
221 using NaryOnePropagator<View,PC_INT_DOM>::x;
222 using NaryOnePropagator<View,PC_INT_DOM>::y;
223
224 /// Constructor for cloning \a p
225 NaryMaxDom(Space& home, NaryMaxDom& p);
226 /// Constructor for posting
227 NaryMaxDom(Home home, ViewArray<View>& x, View y);
228 public:
229 /// Copy propagator during cloning
230 virtual Actor* copy(Space& home);
231 /**
232 * \brief Cost function
233 *
234 * If in stage for bounds propagation, the cost is
235 * low linear. Otherwise it is high linear.
236 */
237 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
238 /// Perform propagation
239 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
240 /// Post propagator \f$ \max x=y\f$
241 static ExecStatus post(Home home, ViewArray<View>& x, View y);
242 };
243
244}}}
245
246#include <gecode/int/arithmetic/max.hpp>
247
248namespace Gecode { namespace Int { namespace Arithmetic {
249
250 /**
251 * \brief Argument maximum propagator
252 *
253 * Tiebreaking is used if \a tiebreak is true and views can be shared
254 * if \a shread is true.
255 *
256 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
257 * \ingroup FuncIntProp
258 */
259 template<class VA, class VB, bool tiebreak>
260 class ArgMax : public Propagator {
261 protected:
262 /// Map of index and views
263 IdxViewArray<VA> x;
264 /// Position of maximum view (maximal argument)
265 VB y;
266 /// Constructor for cloning \a p
267 ArgMax(Space& home, ArgMax& p);
268 /// Constructor for posting
269 ArgMax(Home home, IdxViewArray<VA>& x, VB y);
270 public:
271 /// Copy propagator during cloning
272 virtual Actor* copy(Space& home);
273 // Cost function (defined as low linear)
274 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
275 /// Schedule function
276 virtual void reschedule(Space& home);
277 /// Perform propagation
278 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
279 /// Delete propagator and return its size
280 virtual size_t dispose(Space& home);
281 /**
282 * \brief Post propagator \f$ \operatorname{argmax} x=y\f$
283 *
284 * Note that \a y must be constrained to be in the proper range
285 * for the index values in \a x.
286 */
287 static ExecStatus post(Home home, IdxViewArray<VA>& x, VB y);
288 };
289
290}}}
291
292#include <gecode/int/arithmetic/argmax.hpp>
293
294namespace Gecode { namespace Int { namespace Arithmetic {
295
296 /**
297 * \brief Operations for square and square-root propagators
298 *
299 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
300 * \ingroup FuncIntProp
301 */
302 class SqrOps {
303 public:
304 /// Return whether exponent is even
305 bool even(void) const;
306 /// Return exponent
307 int exp(void) const;
308 /// Set exponent to \a m
309 void exp(int m);
310 /// Return \f$x^2\f$
311 template<class IntType>
312 IntType pow(IntType x) const;
313 /// Return \f$x^2\f$ truncated to integer limits
314 int tpow(int x) const;
315 /// Return \f$\lfloor \sqrt{x}\rfloor\f$ where \a x must be non-negative and \f$n>0\f$
316 int fnroot(int x) const;
317 /// Return \f$\lceil \sqrt{x}\rceil\f$ where \a x must be non-negative and \f$n>0\f$
318 int cnroot(int x) const;
319 };
320
321 /**
322 * \brief Operations for power and nroot propagators
323 *
324 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
325 * \ingroup FuncIntProp
326 */
327 class PowOps {
328 protected:
329 /// The exponent and root index
330 int n;
331 /// Return whether \a m is even
332 static bool even(int m);
333 /// Test whether \f$r^n>x\f$
334 bool powgr(long long int r, int x) const;
335 /// Test whether \f$r^n<x\f$
336 bool powle(long long int r, int x) const;
337 public:
338 /// Initialize with exponent \a n
339 PowOps(int n);
340 /// Return whether exponent is even
341 bool even(void) const;
342 /// Return exponent
343 int exp(void) const;
344 /// Set exponent to \a m
345 void exp(int m);
346 /// Return \f$x^n\f$ where \f$n>0\f$
347 template<class IntType>
348 IntType pow(IntType x) const;
349 /// Return \f$x^n\f$ where \f$n>0\f$ truncated to integer limits
350 int tpow(int x) const;
351 /// Return \f$\lfloor \sqrt[n]{x}\rfloor\f$ where \a x must be non-negative and \f$n>0\f$
352 int fnroot(int x) const;
353 /// Return \f$\lceil \sqrt[n]{x}\rceil\f$ where \a x must be non-negative and \f$n>0\f$
354 int cnroot(int x) const;
355 };
356
357}}}
358
359#include <gecode/int/arithmetic/pow-ops.hpp>
360
361namespace Gecode { namespace Int { namespace Arithmetic {
362
363 /**
364 * \brief Bounds consistent positive power propagator
365 *
366 * This propagator is for positive views only.
367 */
368 template<class VA, class VB, class Ops>
369 class PowPlusBnd : public MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND> {
370 protected:
371 using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x0;
372 using MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>::x1;
373 /// Operations
374 Ops ops;
375 /// Constructor for posting
376 PowPlusBnd(Home home, VA x0, VB x1, const Ops& ops);
377 /// Constructor for cloning \a p
378 PowPlusBnd(Space& home, PowPlusBnd<VA,VB,Ops>& p);
379 public:
380 /// Copy propagator during cloning
381 virtual Actor* copy(Space& home);
382 /// Perform propagation
383 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
384 /// Post propagator
385 static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
386 };
387
388 /**
389 * \brief Bounds consistent power propagator
390 *
391 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
392 * \ingroup FuncIntProp
393 */
394 template<class Ops>
395 class PowBnd : public BinaryPropagator<IntView,PC_INT_BND> {
396 protected:
397 using BinaryPropagator<IntView,PC_INT_BND>::x0;
398 using BinaryPropagator<IntView,PC_INT_BND>::x1;
399 /// Operations
400 Ops ops;
401 /// Constructor for cloning \a p
402 PowBnd(Space& home, PowBnd& p);
403 /// Constructor for posting
404 PowBnd(Home home, IntView x0, IntView x1, const Ops& ops);
405 public:
406 /// Copy propagator during cloning
407 virtual Actor* copy(Space& home);
408 /// Perform propagation
409 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
410 /// Post propagator
411 static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
412 };
413
414 /**
415 * \brief Domain consistent positive power propagator
416 *
417 * This propagator is for positive views only.
418 */
419 template<class VA, class VB, class Ops>
420 class PowPlusDom : public MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM> {
421 protected:
422 using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x0;
423 using MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>::x1;
424 /// Operations
425 Ops ops;
426 /// Constructor for posting
427 PowPlusDom(Home home, VA x0, VB x1, const Ops& ops);
428 /// Constructor for cloning \a p
429 PowPlusDom(Space& home, PowPlusDom<VA,VB,Ops>& p);
430 public:
431 /// Copy propagator during cloning
432 virtual Actor* copy(Space& home);
433 /**
434 * \brief Cost function
435 *
436 * If a view has been assigned, the cost is low unary.
437 * If in stage for bounds propagation, the cost is
438 * low binary. Otherwise it is high binary.
439 */
440 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
441 /// Perform propagation
442 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
443 /// Post propagator
444 static ExecStatus post(Home home, VA x0, VB x1, Ops ops);
445 };
446
447 /**
448 * \brief Domain consistent power propagator
449 *
450 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
451 * \ingroup FuncIntProp
452 */
453 template<class Ops>
454 class PowDom : public BinaryPropagator<IntView,PC_INT_DOM> {
455 protected:
456 using BinaryPropagator<IntView,PC_INT_DOM>::x0;
457 using BinaryPropagator<IntView,PC_INT_DOM>::x1;
458 /// Operations
459 Ops ops;
460 /// Constructor for cloning \a p
461 PowDom(Space& home, PowDom<Ops>& p);
462 /// Constructor for posting
463 PowDom(Home home, IntView x0, IntView x1, const Ops& ops);
464 public:
465 /// Copy propagator during cloning
466 virtual Actor* copy(Space& home);
467 /// Perform propagation
468 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
469 /**
470 * \brief Cost function
471 *
472 * If a view has been assigned, the cost is low unary.
473 * If in stage for bounds propagation, the cost is
474 * low binary. Otherwise it is high binary.
475 */
476 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
477 /// Post propagator
478 static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
479 };
480
481}}}
482
483#include <gecode/int/arithmetic/pow.hpp>
484
485namespace Gecode { namespace Int { namespace Arithmetic {
486
487 /**
488 * \brief Positive bounds consistent n-th root propagator
489 *
490 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
491 * \ingroup FuncIntProp
492 */
493 template<class Ops, bool minus>
494 class NrootPlusBnd : public BinaryPropagator<IntView,PC_INT_BND> {
495 protected:
496 using BinaryPropagator<IntView,PC_INT_BND>::x0;
497 using BinaryPropagator<IntView,PC_INT_BND>::x1;
498 /// Operations
499 Ops ops;
500 /// Constructor for cloning \a p
501 NrootPlusBnd(Space& home, NrootPlusBnd<Ops,minus>& p);
502 /// Constructor for posting
503 NrootPlusBnd(Home home, IntView x0, IntView x1, const Ops& ops);
504 public:
505 /// Copy propagator during cloning
506 virtual Actor* copy(Space& home);
507 /// Perform propagation
508 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
509 /// Post propagator
510 static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
511 };
512
513 /**
514 * \brief Bounds consistent n-th root propagator
515 *
516 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
517 * \ingroup FuncIntProp
518 */
519 template<class Ops>
520 class NrootBnd : public BinaryPropagator<IntView,PC_INT_BND> {
521 protected:
522 using BinaryPropagator<IntView,PC_INT_BND>::x0;
523 using BinaryPropagator<IntView,PC_INT_BND>::x1;
524 /// Operations
525 Ops ops;
526 /// Constructor for cloning \a p
527 NrootBnd(Space& home, NrootBnd<Ops>& p);
528 /// Constructor for posting
529 NrootBnd(Home home, IntView x0, IntView x1, const Ops& ops);
530 public:
531 /// Copy propagator during cloning
532 virtual Actor* copy(Space& home);
533 /// Perform propagation
534 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
535 /// Post propagator
536 static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
537 };
538
539 /**
540 * \brief Domain consistent n-th root propagator
541 *
542 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
543 * \ingroup FuncIntProp
544 */
545 template<class Ops, bool minus>
546 class NrootPlusDom : public BinaryPropagator<IntView,PC_INT_DOM> {
547 protected:
548 using BinaryPropagator<IntView,PC_INT_DOM>::x0;
549 using BinaryPropagator<IntView,PC_INT_DOM>::x1;
550 /// Operations
551 Ops ops;
552 /// Constructor for cloning \a p
553 NrootPlusDom(Space& home, NrootPlusDom<Ops,minus>& p);
554 /// Constructor for posting
555 NrootPlusDom(Home home, IntView x0, IntView x1, const Ops& ops);
556 public:
557 /// Copy propagator during cloning
558 virtual Actor* copy(Space& home);
559 /// Perform propagation
560 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
561 /**
562 * \brief Cost function
563 *
564 * If a view has been assigned, the cost is low unary.
565 * If in stage for bounds propagation, the cost is
566 * low binary. Otherwise it is high binary.
567 */
568 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
569 /// Post propagator
570 static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
571 };
572
573 /**
574 * \brief Domain consistent n-th root propagator
575 *
576 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
577 * \ingroup FuncIntProp
578 */
579 template<class Ops>
580 class NrootDom : public BinaryPropagator<IntView,PC_INT_DOM> {
581 protected:
582 using BinaryPropagator<IntView,PC_INT_DOM>::x0;
583 using BinaryPropagator<IntView,PC_INT_DOM>::x1;
584 /// Operations
585 Ops ops;
586 /// Constructor for cloning \a p
587 NrootDom(Space& home, NrootDom<Ops>& p);
588 /// Constructor for posting
589 NrootDom(Home home, IntView x0, IntView x1, const Ops& ops);
590 public:
591 /// Copy propagator during cloning
592 virtual Actor* copy(Space& home);
593 /// Perform propagation
594 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
595 /**
596 * \brief Cost function
597 *
598 * If a view has been assigned, the cost is low unary.
599 * If in stage for bounds propagation, the cost is
600 * low binary. Otherwise it is high binary.
601 */
602 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
603 /// Post propagator
604 static ExecStatus post(Home home, IntView x0, IntView x1, Ops ops);
605 };
606
607}}}
608
609#include <gecode/int/arithmetic/nroot.hpp>
610
611namespace Gecode { namespace Int { namespace Arithmetic {
612
613 /**
614 * \brief Bounds or domain consistent propagator for \f$x_0\times x_1=x_0\f$
615 *
616 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
617 * \ingroup FuncIntProp
618 */
619 template<class View, PropCond pc>
620 class MultZeroOne : public BinaryPropagator<View,pc> {
621 protected:
622 using BinaryPropagator<View,pc>::x0;
623 using BinaryPropagator<View,pc>::x1;
624
625 /// Constructor for cloning \a p
626 MultZeroOne(Space& home, MultZeroOne<View,pc>& p);
627 /// Constructor for posting
628 MultZeroOne(Home home, View x0, View x1);
629 /// Test whether \a x is equal to \a n
630 static RelTest equal(View x, int n);
631 public:
632 /// Copy propagator during cloning
633 virtual Actor* copy(Space& home);
634 /// Perform propagation
635 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
636 /// Post propagator \f$x_0\cdot x_1=x_0\f$
637 static ExecStatus post(Home home, View x0, View x1);
638 };
639
640
641
642 /**
643 * \brief Bounds consistent positive multiplication propagator
644 *
645 * This propagator provides multiplication for positive views only.
646 */
647 template<class VA, class VB, class VC>
648 class MultPlusBnd :
649 public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
650 protected:
651 using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
652 using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
653 using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
654 public:
655 /// Constructor for posting
656 MultPlusBnd(Home home, VA x0, VB x1, VC x2);
657 /// Constructor for cloning \a p
658 MultPlusBnd(Space& home, MultPlusBnd<VA,VB,VC>& p);
659 /// Post propagator \f$x_0\cdot x_1=x_2\f$
660 static ExecStatus post(Home home, VA x0, VB x1, VC x2);
661 /// Copy propagator during cloning
662 virtual Actor* copy(Space& home);
663 /// Perform propagation
664 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
665 };
666
667 /**
668 * \brief Bounds consistent multiplication propagator
669 *
670 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
671 *
672 * \ingroup FuncIntProp
673 */
674 class MultBnd : public TernaryPropagator<IntView,PC_INT_BND> {
675 protected:
676 using TernaryPropagator<IntView,PC_INT_BND>::x0;
677 using TernaryPropagator<IntView,PC_INT_BND>::x1;
678 using TernaryPropagator<IntView,PC_INT_BND>::x2;
679 /// Constructor for cloning \a p
680 MultBnd(Space& home, MultBnd& p);
681 public:
682 /// Constructor for posting
683 MultBnd(Home home, IntView x0, IntView x1, IntView x2);
684 /// Post propagator \f$x_0\cdot x_1=x_2\f$
685 GECODE_INT_EXPORT
686 static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
687 /// Copy propagator during cloning
688 GECODE_INT_EXPORT
689 virtual Actor* copy(Space& home);
690 /// Perform propagation
691 GECODE_INT_EXPORT
692 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
693 };
694
695
696
697 /**
698 * \brief Domain consistent positive multiplication propagator
699 *
700 * This propagator provides multiplication for positive views only.
701 */
702 template<class VA, class VB, class VC>
703 class MultPlusDom :
704 public MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM> {
705 protected:
706 using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x0;
707 using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x1;
708 using MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>::x2;
709 public:
710 /// Constructor for posting
711 MultPlusDom(Home home, VA x0, VB x1, VC x2);
712 /// Constructor for cloning \a p
713 MultPlusDom(Space& home, MultPlusDom<VA,VB,VC>& p);
714 /// Post propagator \f$x_0\cdot x_1=x_2\f$
715 static ExecStatus post(Home home, VA x0, VB x1, VC x2);
716 /// Copy propagator during cloning
717 virtual Actor* copy(Space& home);
718 /**
719 * \brief Cost function
720 *
721 * If in stage for bounds propagation, the cost is
722 * low ternary. Otherwise it is high ternary.
723 */
724 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
725 /// Perform propagation
726 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
727 };
728
729 /**
730 * \brief Domain consistent multiplication propagator
731 *
732 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
733 *
734 * \ingroup FuncIntProp
735 */
736 class MultDom : public TernaryPropagator<IntView,PC_INT_DOM> {
737 protected:
738 using TernaryPropagator<IntView,PC_INT_DOM>::x0;
739 using TernaryPropagator<IntView,PC_INT_DOM>::x1;
740 using TernaryPropagator<IntView,PC_INT_DOM>::x2;
741 /// Constructor for cloning \a p
742 MultDom(Space& home, MultDom& p);
743 public:
744 /// Constructor for posting
745 MultDom(Home home, IntView x0, IntView x1, IntView x2);
746 /// Post propagator \f$x_0\cdot x_1=x_2\f$
747 GECODE_INT_EXPORT
748 static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2);
749 /// Copy propagator during cloning
750 GECODE_INT_EXPORT
751 virtual Actor* copy(Space& home);
752 /**
753 * \brief Cost function
754 *
755 * If in stage for bounds propagation, the cost is
756 * low ternary. Otherwise it is high ternary.
757 */
758 GECODE_INT_EXPORT
759 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
760 /// Perform propagation
761 GECODE_INT_EXPORT
762 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
763 };
764
765}}}
766
767#include <gecode/int/arithmetic/mult.hpp>
768
769namespace Gecode { namespace Int { namespace Arithmetic {
770
771 /**
772 * \brief Bounds consistent positive division propagator
773 *
774 * This propagator provides division for positive views only.
775 */
776 template<class VA, class VB, class VC>
777 class DivPlusBnd :
778 public MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND> {
779 protected:
780 using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x0;
781 using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x1;
782 using MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>::x2;
783 public:
784 /// Constructor for posting
785 DivPlusBnd(Home home, VA x0, VB x1, VC x2);
786 /// Constructor for cloning \a p
787 DivPlusBnd(Space& home, DivPlusBnd<VA,VB,VC>& p);
788 /// Post propagator \f$x_0\mathrm{div} x_1=x_2\f$ (rounding towards 0)
789 static ExecStatus post(Home home, VA x0, VB x1, VC x2);
790 /// Copy propagator during cloning
791 virtual Actor* copy(Space& home);
792 /// Perform propagation
793 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
794 };
795
796 /**
797 * \brief Bounds consistent division propagator
798 *
799 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
800 *
801 * \ingroup FuncIntProp
802 */
803 template<class View>
804 class DivBnd : public TernaryPropagator<View,PC_INT_BND> {
805 protected:
806 using TernaryPropagator<View,PC_INT_BND>::x0;
807 using TernaryPropagator<View,PC_INT_BND>::x1;
808 using TernaryPropagator<View,PC_INT_BND>::x2;
809
810 /// Constructor for cloning \a p
811 DivBnd(Space& home, DivBnd<View>& p);
812 public:
813 /// Constructor for posting
814 DivBnd(Home home, View x0, View x1, View x2);
815 /// Post propagator \f$x_0\mathrm{div} x_1=x_2\f$ (rounding towards 0)
816 static ExecStatus post(Home home, View x0, View x1, View x2);
817 /// Copy propagator during cloning
818 virtual Actor* copy(Space& home);
819 /// Perform propagation
820 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
821 };
822
823 /**
824 * \brief Integer division/modulo propagator
825 *
826 * This propagator implements the relation between divisor and
827 * modulo of an integer division.
828 *
829 * Requires \code #include <gecode/int/arithmetic.hh> \endcode
830 *
831 * \ingroup FuncIntProp
832 */
833 template<class View>
834 class DivMod : public TernaryPropagator<View,PC_INT_BND> {
835 protected:
836 using TernaryPropagator<View,PC_INT_BND>::x0;
837 using TernaryPropagator<View,PC_INT_BND>::x1;
838 using TernaryPropagator<View,PC_INT_BND>::x2;
839
840 /// Constructor for cloning \a p
841 DivMod(Space& home, DivMod<View>& p);
842 public:
843 /// Constructor for posting
844 DivMod(Home home, View x0, View x1, View x2);
845 /// Post propagator \f$x_1\neq 0 \land (x_2\neq 0\Rightarrow x_0\times x_2>0) \land \mathrm{abs}(x_2)<\mathrm{abs}(x_1)\f$
846 static ExecStatus post(Home home, View x0, View x1, View x2);
847 /// Copy propagator during cloning
848 virtual Actor* copy(Space& home);
849 /// Perform propagation
850 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
851 };
852
853}}}
854
855#include <gecode/int/arithmetic/divmod.hpp>
856
857#endif
858
859// STATISTICS: int-prop
860