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 * Contributing authors:
8 * Gabor Szokoli <szokoli@gecode.org>
9 *
10 * Copyright:
11 * Christian Schulte, 2002
12 * Guido Tack, 2004
13 * Gabor Szokoli, 2003
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#ifndef GECODE_INT_REL_HH
41#define GECODE_INT_REL_HH
42
43#include <gecode/int.hh>
44
45/**
46 * \namespace Gecode::Int::Rel
47 * \brief Simple relation propagators
48 */
49
50namespace Gecode { namespace Int { namespace Rel {
51
52 /*
53 * Equality propagators
54 *
55 */
56
57 /**
58 * \brief Binary domain consistent equality propagator
59 *
60 * Uses staging by first performing bounds propagation and only
61 * then domain propagation.
62 *
63 * Requires \code #include <gecode/int/rel.hh> \endcode
64 * \ingroup FuncIntProp
65 */
66 template<class View0,class View1>
67 class EqDom :
68 public MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM> {
69 protected:
70 using MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>::x0;
71 using MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>::x1;
72
73 /// Constructor for cloning \a p
74 EqDom(Space& home, EqDom<View0,View1>& p);
75 public:
76 /// Constructor for posting
77 EqDom(Home home, View0 x0, View1 x1);
78 /// Constructor for rewriting \a p during cloning
79 EqDom(Space& home, Propagator& p, View0 x0, View1 x1);
80 /// Copy propagator during cloning
81 virtual Actor* copy(Space& home);
82 /**
83 * \brief Cost function
84 *
85 * If a view has been assigned, the cost is low unary.
86 * If in stage for bounds propagation, the cost is
87 * low binary. Otherwise it is high binary.
88 */
89 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
90 /// Perform propagation
91 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
92 /// Post domain consistent propagator \f$ x_0 = x_1\f$
93 static ExecStatus post(Home home, View0 x0, View1 x1);
94 };
95
96 /**
97 * \brief Binary value propagation equality propagator
98 *
99 * Requires \code #include <gecode/int/rel.hh> \endcode
100 * \ingroup FuncIntProp
101 */
102 template<class View0, class View1>
103 class EqVal :
104 public MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL> {
105 protected:
106 using MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL>::x0;
107 using MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL>::x1;
108
109 /// Constructor for cloning \a p
110 EqVal(Space& home, EqVal<View0,View1>& p);
111 public:
112 /// Constructor for posting
113 EqVal(Home home, View0 x0, View1 x1);
114 /// Constructor for rewriting \a p during cloning
115 EqVal(Space& home, Propagator& p, View0 x0, View1 x1);
116 /// Copy propagator during cloning
117 virtual Actor* copy(Space& home);
118 /// Cost function: low unary.
119 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
120 /// Perform propagation
121 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
122 /// Post value propagation propagator \f$ x_0 = x_1\f$
123 static ExecStatus post(Home home, View0 x0, View1 x1);
124 };
125
126 /**
127 * \brief Binary bounds consistent equality propagator
128 *
129 * Requires \code #include <gecode/int/rel.hh> \endcode
130 * \ingroup FuncIntProp
131 */
132 template<class View0, class View1>
133 class EqBnd :
134 public MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND> {
135 protected:
136 using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x0;
137 using MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>::x1;
138
139 /// Constructor for cloning \a p
140 EqBnd(Space& home, EqBnd<View0,View1>& p);
141 public:
142 /// Constructor for posting
143 EqBnd(Home home, View0 x0, View1 x1);
144 /// Constructor for rewriting \a p during cloning
145 EqBnd(Space& home, Propagator& p, View0 x0, View1 x1);
146 /// Copy propagator during cloning
147 virtual Actor* copy(Space& home);
148 /// Perform propagation
149 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
150 /// Post bounds consistent propagator \f$ x_0 = x_1\f$
151 static ExecStatus post(Home home, View0 x0, View1 x1);
152 };
153
154 /**
155 * \brief n-ary domain consistent equality propagator
156 *
157 * Uses staging by first performing bounds propagation and only
158 * then domain propagation.
159 *
160 * Requires \code #include <gecode/int/rel.hh> \endcode
161 * \ingroup FuncIntProp
162 */
163 template<class View>
164 class NaryEqDom : public NaryPropagator<View,PC_INT_DOM> {
165 protected:
166 using NaryPropagator<View,PC_INT_DOM>::x;
167
168 /// Constructor for cloning \a p
169 NaryEqDom(Space& home, NaryEqDom<View>& p);
170 /// Constructor for posting
171 NaryEqDom(Home home, ViewArray<View>&);
172 public:
173 /// Copy propagator during cloning
174 virtual Actor* copy(Space& home);
175 /**
176 * \brief Cost function
177 *
178 * If a view has been assigned, the cost is low unary.
179 * If in stage for bounds propagation, the cost is
180 * low linear. Otherwise it is high linear.
181 */
182 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
183 /// Perform propagation
184 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
185 /// Post domain consistent propagator \f$ x_0 = x_1=\ldots =x_{|x|-1}\f$
186 static ExecStatus post(Home home, ViewArray<View>& x);
187 };
188
189 /**
190 * \brief n-ary bounds consistent equality propagator
191 *
192 * Requires \code #include <gecode/int/rel.hh> \endcode
193 * \ingroup FuncIntProp
194 */
195 template<class View>
196 class NaryEqBnd : public NaryPropagator<View,PC_INT_BND> {
197 protected:
198 using NaryPropagator<View,PC_INT_BND>::x;
199
200 /// Constructor for cloning \a p
201 NaryEqBnd(Space& home, NaryEqBnd<View>& p);
202 /// Constructor for posting
203 NaryEqBnd(Home home, ViewArray<View>&);
204 public:
205 /// Copy propagator during cloning
206 virtual Actor* copy(Space& home);
207 /**
208 * \brief Cost function
209 *
210 * If a view has been assigned, the cost is low unary.
211 * Otherwise it is low linear.
212 */
213 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
214 /// Perform propagation
215 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
216 /// Post bounds consistent propagator \f$ x_0 = x_1=\ldots =x_{|x|-1}\f$
217 static ExecStatus post(Home home, ViewArray<View>& x);
218 };
219
220 /**
221 * \brief n-ary less and less or equal propagator
222 *
223 * If \a o is 0, less or equal is propagated, if \a o is 1 less is
224 * propagated.
225 *
226 * Requires \code #include <gecode/int/rel.hh> \endcode
227 * \ingroup FuncIntProp
228 */
229 template<class View, int o>
230 class NaryLqLe : public NaryPropagator<View,PC_INT_NONE> {
231 protected:
232 using NaryPropagator<View,PC_INT_NONE>::x;
233 /// %Advisors for views (by position in array)
234 class Index : public Advisor {
235 public:
236 /// The position of the view in the view array
237 int i;
238 /// Create index advisor
239 Index(Space& home, Propagator& p, Council<Index>& c, int i);
240 /// Clone index advisor \a a
241 Index(Space& home, Index& a);
242 };
243 /// The advisor council
244 Council<Index> c;
245 /// Positions in view array that have to be propagated
246 class Pos : public FreeList {
247 public:
248 /// Position of view in view array
249 int p;
250
251 /// \name Constructor
252 //@{
253 /// Initialize with position \a p and next position \a n
254 Pos(int p, Pos* n);
255 //@}
256
257 /// \name Linkage access
258 //@{
259 /// Return next position
260 Pos* next(void) const;
261 //@}
262
263 /// \name Memory management
264 //@{
265 /// Free memory for this position
266 void dispose(Space& home);
267
268 /// Allocate memory from space
269 static void* operator new(size_t s, Space& home);
270 /// No-op (for exceptions)
271 static void operator delete(void* p);
272 /// No-op (use dispose instead)
273 static void operator delete(void* p, Space& home);
274 //@}
275 };
276 /// Stack of positions
277 Pos* pos;
278 /// Whether no more positions must be propagated
279 bool empty(void) const;
280 /// Pop a position to be propagated and return it
281 int pop(Space& home);
282 /// Push a new position \a p to be propagated
283 void push(Space& home, int p);
284 /// Whether the propagator is currently running
285 bool run;
286 /// Number of already subsumed advisors (or views)
287 int n_subsumed;
288 /// Compact during cloning when more advisors than that are subsumed
289 static const int n_threshold = 7;
290 /// Constructor for cloning \a p
291 NaryLqLe(Space& home, NaryLqLe<View,o>& p);
292 /// Constructor for posting
293 NaryLqLe(Home home, ViewArray<View>&);
294 public:
295 /// Copy propagator during cloning
296 virtual Actor* copy(Space& home);
297 /// Cost function
298 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
299 /// Schedule function
300 virtual void reschedule(Space& home);
301 /// Give advice to propagator
302 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
303 /// Perform propagation
304 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
305 /// Delete propagator and return its size
306 virtual size_t dispose(Space& home);
307 /// Post propagator for \f$ x_0 +c\leq x_1+c\leq\cdots \leq x_{|x|-1}\f$
308 static ExecStatus post(Home home, ViewArray<View>& x);
309 };
310
311 /**
312 * \brief Nary disequality propagator
313 *
314 * Requires \code #include <gecode/int/rel.hh> \endcode
315 * \ingroup FuncIntProp
316 */
317 template<class View>
318 class NaryNq : public NaryPropagator<View,PC_INT_VAL> {
319 protected:
320 using NaryPropagator<View,PC_INT_VAL>::x;
321 /// Constructor for posting
322 NaryNq(Home home, ViewArray<View>& x);
323 /// Constructor for cloning \a p
324 NaryNq(Space& home, NaryNq<View>& p);
325 public:
326 /// Copy propagator during cloning
327 virtual Actor* copy(Space& home);
328 /// Cost function
329 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
330 /// Perform propagation
331 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
332 /// Post propagator \f$ \neg\left(x_0=x_1=\cdots=x_{|x|-1}\right)\f$
333 static ExecStatus post(Home home, ViewArray<View>& x);
334 /// Delete propagator and return its size
335 virtual size_t dispose(Space& home);
336 };
337
338
339 /**
340 * \brief Reified binary domain consistent equality propagator
341 *
342 * Requires \code #include <gecode/int/rel.hh> \endcode
343 * \ingroup FuncIntProp
344 */
345 template<class View, class CtrlView, ReifyMode rm>
346 class ReEqDom : public ReBinaryPropagator<View,PC_INT_DOM,CtrlView> {
347 protected:
348 using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
349 using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::x1;
350 using ReBinaryPropagator<View,PC_INT_DOM,CtrlView>::b;
351
352 /// Constructor for cloning \a p
353 ReEqDom(Space& home, ReEqDom& p);
354 /// Constructor for posting
355 ReEqDom(Home home, View x0, View x1, CtrlView b);
356 public:
357 /// Copy propagator during cloning
358 virtual Actor* copy(Space& home);
359 /// Perform propagation
360 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
361 /// Post domain consistent propagator \f$ (x_0 = x_1)\Leftrightarrow b\f$
362 static ExecStatus post(Home home, View x0, View x1, CtrlView b);
363 };
364
365 /**
366 * \brief Reified binary bounds consistent equality propagator
367 *
368 * Requires \code #include <gecode/int/rel.hh> \endcode
369 * \ingroup FuncIntProp
370 */
371 template<class View, class CtrlView, ReifyMode rm>
372 class ReEqBnd : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
373 protected:
374 using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
375 using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
376 using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
377
378 /// Constructor for cloning \a p
379 ReEqBnd(Space& home, ReEqBnd& p);
380 /// Constructor for posting
381 ReEqBnd(Home home, View x0, View x1, CtrlView b);
382 public:
383 /// Copy propagator during cloning
384 virtual Actor* copy(Space& home);
385 /// Perform propagation
386 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
387 /// Post bounds consistent propagator \f$ (x_0 = x_1)\Leftrightarrow b\f$
388 static ExecStatus post(Home home, View x0, View x1, CtrlView b);
389 };
390
391 /**
392 * \brief Reified domain consistent equality with integer propagator
393 *
394 * Requires \code #include <gecode/int/rel.hh> \endcode
395 * \ingroup FuncIntProp
396 */
397 template<class View, class CtrlView, ReifyMode rm>
398 class ReEqDomInt : public ReUnaryPropagator<View,PC_INT_DOM,CtrlView> {
399 protected:
400 using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::x0;
401 using ReUnaryPropagator<View,PC_INT_DOM,CtrlView>::b;
402
403 /// Integer constant to check
404 int c;
405 /// Constructor for cloning \a p
406 ReEqDomInt(Space& home, ReEqDomInt& p);
407 /// Constructor for posting
408 ReEqDomInt(Home home, View x, int c, CtrlView b);
409 public:
410 /// Copy propagator during cloning
411 virtual Actor* copy(Space& home);
412 /// Perform propagation
413 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
414 /// Post domain consistent propagator \f$ (x = c)\Leftrightarrow b\f$
415 static ExecStatus post(Home home, View x, int c, CtrlView b);
416 };
417
418 /**
419 * \brief Reified bounds consistent equality with integer propagator
420 *
421 * Requires \code #include <gecode/int/rel.hh> \endcode
422 * \ingroup FuncIntProp
423 */
424 template<class View, class CtrlView, ReifyMode rm>
425 class ReEqBndInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
426 protected:
427 using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
428 using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
429
430 /// Integer constant to check
431 int c;
432 /// Constructor for cloning \a p
433 ReEqBndInt(Space& home, ReEqBndInt& p);
434 /// Constructor for posting
435 ReEqBndInt(Home home, View x, int c, CtrlView b);
436 public:
437 /// Copy propagator during cloning
438 virtual Actor* copy(Space& home);
439 /// Perform propagation
440 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
441 /// Post bounds consistent propagator \f$ (x = c)\Leftrightarrow b\f$
442 static ExecStatus post(Home home, View x, int c, CtrlView b);
443 };
444
445
446
447
448 /*
449 * Disequality propagators
450 *
451 */
452
453 /**
454 * \brief Binary disequality propagator
455 *
456 * Requires \code #include <gecode/int/rel.hh> \endcode
457 * \ingroup FuncIntProp
458 */
459 template<class V0, class V1>
460 class Nq : public MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL> {
461 protected:
462 using MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>::x0;
463 using MixBinaryPropagator<V0,PC_INT_VAL,V1,PC_INT_VAL>::x1;
464
465 /// Constructor for cloning \a p
466 Nq(Space& home, Nq<V0,V1>& p);
467 /// Constructor for posting
468 Nq(Home home, V0 x0, V1 x1);
469 public:
470 /// Copy propagator during cloning
471 virtual Actor* copy(Space& home);
472 /// Cost function (defined as low unary)
473 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
474 /// Perform propagation
475 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
476 /// Post propagator \f$x_0\neq x_1\f$
477 static ExecStatus post(Home home, V0 x0, V1 x1);
478 };
479
480 /*
481 * Order propagators
482 *
483 */
484
485 /**
486 * \brief Less or equal propagator
487 *
488 * Requires \code #include <gecode/int/rel.hh> \endcode
489 * \ingroup FuncIntProp
490 */
491
492 template<class V0, class V1>
493 class Lq : public MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND> {
494 protected:
495 using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x0;
496 using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x1;
497 /// Constructor for cloning \a p
498 Lq(Space& home, Lq& p);
499 /// Constructor for posting
500 Lq(Home home, V0 x0, V1 x1);
501 public:
502 /// Copy propagator during cloning
503 virtual Actor* copy(Space& home);
504 /// Perform propagation
505 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
506 /// Post propagator \f$x_0 \leq x_1\f$
507 static ExecStatus post(Home home, V0 x0, V1 x1);
508 };
509
510 /**
511 * \brief Less propagator
512 *
513 * Requires \code #include <gecode/int/rel.hh> \endcode
514 * \ingroup FuncIntProp
515 */
516 template<class V0, class V1>
517 class Le : public MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND> {
518 protected:
519 using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x0;
520 using MixBinaryPropagator<V0,PC_INT_BND,V1,PC_INT_BND>::x1;
521 /// Constructor for cloning \a p
522 Le(Space& home, Le& p);
523 /// Constructor for posting
524 Le(Home home, V0 x0, V1 x1);
525 public:
526 /// Copy propagator during cloning
527 virtual Actor* copy(Space& home);
528 /// Perform propagation
529 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
530 /// Post propagator \f$x_0 \le x_1\f$
531 static ExecStatus post(Home home, V0 x0, V1 x1);
532 };
533
534
535 /*
536 * Reified order propagators
537 *
538 */
539
540 /**
541 * \brief Reified less or equal propagator
542 *
543 * Requires \code #include <gecode/int/rel.hh> \endcode
544 * \ingroup FuncIntProp
545 */
546
547 template<class View, class CtrlView, ReifyMode rm>
548 class ReLq : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
549 protected:
550 using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x0;
551 using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::x1;
552 using ReBinaryPropagator<View,PC_INT_BND,CtrlView>::b;
553
554 /// Constructor for cloning \a p
555 ReLq(Space& home, ReLq& p);
556 /// Constructor for posting
557 ReLq(Home home, View x0, View x1, CtrlView b);
558 public:
559 /// Copy propagator during cloning
560 virtual Actor* copy(Space& home);
561 /// Perform propagation
562 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
563 /// Post propagator for \f$ (x_0 \leq x_1)\Leftrightarrow b\f$
564 static ExecStatus post(Home home, View x0, View x1, CtrlView b);
565 };
566
567 /**
568 * \brief Reified less or equal with integer propagator
569 *
570 * Requires \code #include <gecode/int/rel.hh> \endcode
571 * \ingroup FuncIntProp
572 */
573
574 template<class View, class CtrlView, ReifyMode rm>
575 class ReLqInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
576 protected:
577 using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::x0;
578 using ReUnaryPropagator<View,PC_INT_BND,CtrlView>::b;
579
580 /// Integer constant to check
581 int c;
582 /// Constructor for cloning \a p
583 ReLqInt(Space& home, ReLqInt& p);
584 /// Constructor for posting
585 ReLqInt(Home home, View x, int c, CtrlView b);
586 public:
587 /// Copy propagator during cloning
588 virtual Actor* copy(Space& home);
589 /// Perform propagation
590 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
591 /// Post propagator for \f$ (x \leq c)\Leftrightarrow b\f$
592 static ExecStatus post(Home home, View x, int c, CtrlView b);
593 };
594
595
596
597
598
599 /**
600 * \brief Lexical ordering propagator
601 *
602 * The propagator uses the algorithm (and also the automaton)
603 * from:
604 * Mats Carlsson, Nicolas Beldiceanu, Revisiting the
605 * Lexicographic Ordering Constraint. SICS Technical
606 * Report T2002:17, SICS, Sweden, 2002.
607 *
608 * It deviates in the following two main aspects:
609 * - Assigned variables are eagerly eliminated
610 * This yields the same incremental behaviour with
611 * respect to states 1 and 2 of the automaton.
612 * With respect to the values of \a q and \a r in the report:
613 * - \a q is always 0 after elimination
614 * - \a r is always 1 after elimination
615 *
616 * - It is not incremental with respect to states 3 and 4
617 * as no propagation event information is available
618 *
619 * Requires \code #include <gecode/int/rel.hh> \endcode
620 * \ingroup FuncIntProp
621 */
622 template<class VX, class VY>
623 class LexLqLe : public Propagator {
624 protected:
625 /// View arrays
626 ViewArray<VX> x;
627 ViewArray<VY> y;
628 /// Determines whether propagator is strict or not
629 bool strict;
630 /// Constructor for cloning \a p
631 LexLqLe(Space& home, LexLqLe<VX,VY>& p);
632 /// Constructor for posting
633 LexLqLe(Home home, ViewArray<VX>& x, ViewArray<VY>& y, bool strict);
634 public:
635 /// Copy propagator during cloning
636 virtual Actor* copy(Space& home);
637 /// Cost function (defined as low linear)
638 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
639 /// Schedule function
640 virtual void reschedule(Space& home);
641 /// Perform propagation
642 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
643 /// Post propagator for lexical order between \a x and \a y
644 static ExecStatus post(Home home, ViewArray<VX>& x, ViewArray<VY>& y,
645 bool strict);
646 /// Delete propagator and return its size
647 virtual size_t dispose(Space& home);
648 };
649
650 /**
651 * \brief Lexical disequality propagator
652 *
653 * Requires \code #include <gecode/int/rel.hh> \endcode
654 * \ingroup FuncIntProp
655 */
656 template<class VX, class VY>
657 class LexNq : public Propagator {
658 protected:
659 /// View currently subscribed to
660 VX x0;
661 /// View currently subscribed to
662 VY y0;
663 /// View currently subscribed to
664 VX x1;
665 /// View currently subscribed to
666 VY y1;
667 /// Views not yet subscribed to
668 ViewArray<VX> x;
669 /// Views not yet subscribed to
670 ViewArray<VY> y;
671 /// Update subscription
672 ExecStatus resubscribe(Space& home,
673 RelTest rt, VX& x0, VY& y0, VX x1, VY y1);
674 /// Constructor for posting
675 LexNq(Home home, ViewArray<VX>& x, ViewArray<VY>& y);
676 /// Constructor for cloning \a p
677 LexNq(Space& home, LexNq<VX,VY>& p);
678 public:
679 /// Copy propagator during cloning
680 virtual Actor* copy(Space& home);
681 /// Cost function
682 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
683 /// Schedule function
684 virtual void reschedule(Space& home);
685 /// Perform propagation
686 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
687 /// Post propagator \f$ x\neq y\f$
688 static ExecStatus post(Home home, ViewArray<VX>& x, ViewArray<VY>& y);
689 /// Delete propagator and return its size
690 virtual size_t dispose(Space& home);
691 };
692
693}}}
694
695#include <gecode/int/rel/eq.hpp>
696#include <gecode/int/rel/nq.hpp>
697#include <gecode/int/rel/lq-le.hpp>
698#include <gecode/int/rel/lex.hpp>
699
700#endif
701
702
703// STATISTICS: int-prop
704