Generated on Thu Mar 16 2017 03:24:16 for Gecode by doxygen 1.8.13
rel.hh
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  * 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  * Last modified:
16  * $Date: 2016-08-17 14:21:02 +0200 (Wed, 17 Aug 2016) $ by $Author: schulte $
17  * $Revision: 15151 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #ifndef __GECODE_INT_REL_HH__
45 #define __GECODE_INT_REL_HH__
46 
47 #include <gecode/int.hh>
48 
54 namespace Gecode { namespace Int { namespace Rel {
55 
56  /*
57  * Equality propagators
58  *
59  */
60 
70  template<class View0,class View1>
71  class EqDom :
72  public MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM> {
73  protected:
76 
78  EqDom(Space& home, bool share, EqDom<View0,View1>& p);
79  public:
81  EqDom(Home home, View0 x0, View1 x1);
83  EqDom(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
85  virtual Actor* copy(Space& home, bool share);
93  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
95  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
97  static ExecStatus post(Home home, View0 x0, View1 x1);
98  };
99 
106  template<class View0, class View1>
107  class EqVal :
108  public MixBinaryPropagator<View0,PC_INT_VAL,View1,PC_INT_VAL> {
109  protected:
112 
114  EqVal(Space& home, bool share, EqVal<View0,View1>& p);
115  public:
117  EqVal(Home home, View0 x0, View1 x1);
119  EqVal(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
121  virtual Actor* copy(Space& home, bool share);
123  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
125  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
127  static ExecStatus post(Home home, View0 x0, View1 x1);
128  };
129 
136  template<class View0, class View1>
137  class EqBnd :
138  public MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND> {
139  protected:
142 
144  EqBnd(Space& home, bool share, EqBnd<View0,View1>& p);
145  public:
147  EqBnd(Home home, View0 x0, View1 x1);
149  EqBnd(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
151  virtual Actor* copy(Space& home, bool share);
153  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
155  static ExecStatus post(Home home, View0 x0, View1 x1);
156  };
157 
167  template<class View>
168  class NaryEqDom : public NaryPropagator<View,PC_INT_DOM> {
169  protected:
171 
173  NaryEqDom(Space& home, bool share, NaryEqDom<View>& p);
176  public:
178  virtual Actor* copy(Space& home, bool share);
186  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
188  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
190  static ExecStatus post(Home home, ViewArray<View>& x);
191  };
192 
199  template<class View>
200  class NaryEqBnd : public NaryPropagator<View,PC_INT_BND> {
201  protected:
203 
205  NaryEqBnd(Space& home, bool share, NaryEqBnd<View>& p);
208  public:
210  virtual Actor* copy(Space& home, bool share);
217  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
219  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
221  static ExecStatus post(Home home, ViewArray<View>& x);
222  };
223 
233  template<class View, int o>
234  class NaryLqLe : public NaryPropagator<View,PC_INT_NONE> {
235  protected:
238  class Index : public Advisor {
239  public:
241  int i;
243  Index(Space& home, Propagator& p, Council<Index>& c, int i);
245  Index(Space& home, bool share, Index& a);
246  };
250  class Pos : public FreeList {
251  public:
253  int p;
254 
256 
257  Pos(int p, Pos* n);
260 
262 
263  Pos* next(void) const;
266 
268 
269  void dispose(Space& home);
271 
273  static void* operator new(size_t s, Space& home);
275  static void operator delete(void* p);
277  static void operator delete(void* p, Space& home);
279  };
283  bool empty(void) const;
285  int pop(Space& home);
287  void push(Space& home, int p);
289  bool run;
293  static const int n_threshold = 7;
295  NaryLqLe(Space& home, bool share, NaryLqLe<View,o>& p);
297  NaryLqLe(Home home, ViewArray<View>&);
298  public:
300  virtual Actor* copy(Space& home, bool share);
302  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
304  virtual void reschedule(Space& home);
306  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
308  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
310  virtual size_t dispose(Space& home);
312  static ExecStatus post(Home home, ViewArray<View>& x);
313  };
314 
321  template<class View>
322  class NaryNq : public NaryPropagator<View,PC_INT_VAL> {
323  protected:
326  NaryNq(Home home, ViewArray<View>& x);
328  NaryNq(Space& home, bool share, NaryNq<View>& p);
329  public:
331  virtual Actor* copy(Space& home, bool share);
333  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
335  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
337  static ExecStatus post(Home home, ViewArray<View>& x);
339  virtual size_t dispose(Space& home);
340  };
341 
342 
349  template<class View, class CtrlView, ReifyMode rm>
350  class ReEqDom : public ReBinaryPropagator<View,PC_INT_DOM,CtrlView> {
351  protected:
355 
357  ReEqDom(Space& home, bool share, ReEqDom& p);
359  ReEqDom(Home home, View x0, View x1, CtrlView b);
360  public:
362  virtual Actor* copy(Space& home, bool share);
364  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
366  static ExecStatus post(Home home, View x0, View x1, CtrlView b);
367  };
368 
375  template<class View, class CtrlView, ReifyMode rm>
376  class ReEqBnd : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
377  protected:
381 
383  ReEqBnd(Space& home, bool share, ReEqBnd& p);
385  ReEqBnd(Home home, View x0, View x1, CtrlView b);
386  public:
388  virtual Actor* copy(Space& home, bool share);
390  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
392  static ExecStatus post(Home home, View x0, View x1, CtrlView b);
393  };
394 
401  template<class View, class CtrlView, ReifyMode rm>
402  class ReEqDomInt : public ReUnaryPropagator<View,PC_INT_DOM,CtrlView> {
403  protected:
406 
408  int c;
410  ReEqDomInt(Space& home, bool share, ReEqDomInt& p);
412  ReEqDomInt(Home home, View x, int c, CtrlView b);
413  public:
415  virtual Actor* copy(Space& home, bool share);
417  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
419  static ExecStatus post(Home home, View x, int c, CtrlView b);
420  };
421 
428  template<class View, class CtrlView, ReifyMode rm>
429  class ReEqBndInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
430  protected:
433 
435  int c;
437  ReEqBndInt(Space& home, bool share, ReEqBndInt& p);
439  ReEqBndInt(Home home, View x, int c, CtrlView b);
440  public:
442  virtual Actor* copy(Space& home, bool share);
444  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
446  static ExecStatus post(Home home, View x, int c, CtrlView b);
447  };
448 
449 
450 
451 
452  /*
453  * Disequality propagators
454  *
455  */
456 
463  template<class View>
464  class Nq : public BinaryPropagator<View,PC_INT_VAL> {
465  protected:
468 
470  Nq(Space& home, bool share, Nq<View>& p);
472  Nq(Home home, View x0, View x1);
473  public:
475  virtual Actor* copy(Space& home, bool share);
477  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
479  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
481  static ExecStatus post(Home home, View x0, View x1);
482  };
483 
484  /*
485  * Order propagators
486  *
487  */
488 
496  template<class View>
497  class Lq : public BinaryPropagator<View,PC_INT_BND> {
498  protected:
501 
503  Lq(Space& home, bool share, Lq& p);
505  Lq(Home home, View x0, View x1);
506  public:
508  virtual Actor* copy(Space& home, bool share);
510  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
512  static ExecStatus post(Home home, View x0, View x1);
513  };
514 
521  template<class View>
522  class Le : public BinaryPropagator<View,PC_INT_BND> {
523  protected:
526 
528  Le(Space& home, bool share, Le& p);
530  Le(Home home, View x0, View x1);
531  public:
533  virtual Actor* copy(Space& home, bool share);
535  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
537  static ExecStatus post(Home home, View x0, View x1);
538  };
539 
540 
541  /*
542  * Reified order propagators
543  *
544  */
545 
553  template<class View, class CtrlView, ReifyMode rm>
554  class ReLq : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
555  protected:
559 
561  ReLq(Space& home, bool share, ReLq& p);
563  ReLq(Home home, View x0, View x1, CtrlView b);
564  public:
566  virtual Actor* copy(Space& home, bool share);
568  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
570  static ExecStatus post(Home home, View x0, View x1, CtrlView b);
571  };
572 
580  template<class View, class CtrlView, ReifyMode rm>
581  class ReLqInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
582  protected:
585 
587  int c;
589  ReLqInt(Space& home, bool share, ReLqInt& p);
591  ReLqInt(Home home, View x, int c, CtrlView b);
592  public:
594  virtual Actor* copy(Space& home, bool share);
596  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
598  static ExecStatus post(Home home, View x, int c, CtrlView b);
599  };
600 
601 
602 
603 
604 
628  template<class View>
629  class LexLqLe : public Propagator {
630  protected:
634  bool strict;
636  LexLqLe(Space& home, bool share, LexLqLe<View>& p);
638  LexLqLe(Home home, ViewArray<View>& x, ViewArray<View>& y, bool strict);
639  public:
641  virtual Actor* copy(Space& home, bool share);
643  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
645  virtual void reschedule(Space& home);
647  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
649  static ExecStatus post(Home home, ViewArray<View>& x, ViewArray<View>& y,
650  bool strict);
652  virtual size_t dispose(Space& home);
653  };
654 
661  template<class View>
662  class LexNq : public Propagator {
663  protected:
665  View x0, y0, x1, y1;
670  RelTest rt, View& x0, View& y0, View x1, View y1);
674  LexNq(Space& home, bool share, LexNq<View>& p);
675  public:
677  virtual Actor* copy(Space& home, bool share);
679  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
681  virtual void reschedule(Space& home);
683  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
685  static ExecStatus post(Home home, ViewArray<View>& x, ViewArray<View>& y);
687  virtual size_t dispose(Space& home);
688  };
689 
690 }}}
691 
692 #include <gecode/int/rel/eq.hpp>
693 #include <gecode/int/rel/nq.hpp>
694 #include <gecode/int/rel/lq-le.hpp>
695 #include <gecode/int/rel/lex.hpp>
696 
697 #endif
698 
699 
700 // STATISTICS: int-prop
701 
Council of advisors
Definition: core.hpp:228
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: eq.hpp:227
int c
Integer constant to check.
Definition: rel.hh:435
Binary domain consistent equality propagator.
Definition: rel.hh:71
Reified unary propagator.
Definition: propagator.hpp:58
Binary value propagation equality propagator.
Definition: rel.hh:107
ViewArray< View > y
Definition: rel.hh:632
ExecStatus resubscribe(Space &home, Propagator &p, VX &x0, ViewArray< VX > &x, VY &x1, ViewArray< VY > &y)
Definition: clause.hpp:142
int n_subsumed
Number of already subsumed advisors (or views)
Definition: rel.hh:291
Reified binary propagator.
Definition: propagator.hpp:91
static ExecStatus post(Home home, View0 x0, View1 x1)
Post domain consistent propagator .
Definition: eq.hpp:180
int c
Integer constant to check.
Definition: rel.hh:587
int p
Position of view in view array.
Definition: rel.hh:253
Reified less or equal with integer propagator.
Definition: rel.hh:581
Base-class for propagators.
Definition: core.hpp:1012
Lexical disequality propagator.
Definition: rel.hh:662
Base-class for advisors.
Definition: core.hpp:1212
n-ary domain consistent equality propagator
Definition: rel.hh:168
virtual void reschedule(Space &home)
Schedule function.
Definition: propagator.hpp:631
Computation spaces.
Definition: core.hpp:1672
Base-class for both propagators and branchers.
Definition: core.hpp:682
Gecode::IntSet d(v, 7)
bool run
Whether the propagator is currently running.
Definition: rel.hh:289
Reified less or equal propagator.
Definition: rel.hh:554
Nary disequality propagator.
Definition: rel.hh:322
int c
Integer constant to check.
Definition: rel.hh:408
Gecode::FloatVal c(-8, 8)
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
ViewArray< View > y
Definition: rel.hh:667
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Binary propagator.
Definition: propagator.hpp:89
Council< Index > c
The advisor council.
Definition: rel.hh:248
RelTest
Result of testing relation.
Definition: view.hpp:1614
Reified binary domain consistent equality propagator.
Definition: rel.hh:350
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: eq.hpp:210
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1022
Binary bounds consistent equality propagator.
Definition: rel.hh:137
Less or equal propagator.
Definition: rel.hh:497
Reified binary bounds consistent equality propagator.
Definition: rel.hh:376
n-ary propagator
Definition: propagator.hpp:149
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition: core.cpp:69
EqDom(Space &home, bool share, EqDom< View0, View1 > &p)
Constructor for cloning p.
Definition: eq.hpp:198
View arrays.
Definition: array.hpp:234
n-ary less and less or equal propagator
Definition: rel.hh:234
Reified bounds consistent equality with integer propagator.
Definition: rel.hh:429
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:277
Mixed binary propagator.
Definition: propagator.hpp:213
Lexical ordering propagator.
Definition: rel.hh:629
Propagation cost.
Definition: core.hpp:550
bool strict
Determines whether propagator is strict or not.
Definition: rel.hh:634
ExecStatus
Definition: core.hpp:536
Base-class for freelist-managed objects.
Binary disequality propagator.
Definition: rel.hh:464
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: eq.hpp:216
Positions in view array that have to be propagated.
Definition: rel.hh:250
n-ary bounds consistent equality propagator
Definition: rel.hh:200
int i
The position of the view in the view array.
Definition: rel.hh:241
Gecode toplevel namespace
Advisors for views (by position in array)
Definition: rel.hh:238
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
Less propagator.
Definition: rel.hh:522
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Reified domain consistent equality with integer propagator.
Definition: rel.hh:402
Home class for posting propagators
Definition: core.hpp:905
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagator.hpp:640
Pos * pos
Stack of positions.
Definition: rel.hh:281