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 50 namespace 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 705