Generated on Tue Mar 5 2013 22:37:24 for Gecode by doxygen 1.8.3.1
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: 2011-07-07 05:56:28 +1000 (Thu, 07 Jul 2011) $ by $Author: schulte $
17  * $Revision: 12151 $
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 EqBnd :
108  public MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND> {
109  protected:
112 
114  EqBnd(Space& home, bool share, EqBnd<View0,View1>& p);
115  public:
117  EqBnd(Home home, View0 x0, View1 x1);
119  EqBnd(Space& home, bool share, Propagator& p, View0 x0, View1 x1);
121  virtual Actor* copy(Space& home, bool share);
123  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
125  static ExecStatus post(Home home, View0 x0, View1 x1);
126  };
127 
137  template<class View>
138  class NaryEqDom : public NaryPropagator<View,PC_INT_DOM> {
139  protected:
141 
143  NaryEqDom(Space& home, bool share, NaryEqDom<View>& p);
146  public:
148  virtual Actor* copy(Space& home, bool share);
156  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
158  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
160  static ExecStatus post(Home home, ViewArray<View>& x);
161  };
162 
169  template<class View>
170  class NaryEqBnd : public NaryPropagator<View,PC_INT_BND> {
171  protected:
173 
175  NaryEqBnd(Space& home, bool share, NaryEqBnd<View>& p);
178  public:
180  virtual Actor* copy(Space& home, bool share);
187  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
189  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
191  static ExecStatus post(Home home, ViewArray<View>& x);
192  };
193 
203  template<class View, int o>
204  class NaryLqLe : public NaryPropagator<View,PC_INT_NONE> {
205  protected:
208  class Index : public Advisor {
209  public:
211  int i;
213  Index(Space& home, Propagator& p, Council<Index>& c, int i);
215  Index(Space& home, bool share, Index& a);
216  };
220  class Pos : public FreeList {
221  public:
223  int p;
224 
226 
227 
228  Pos(int p, Pos* n);
230 
232 
233 
234  Pos* next(void) const;
236 
238 
239 
240  void dispose(Space& home);
241 
243  static void* operator new(size_t s, Space& home);
245  static void operator delete(void* p);
247  static void operator delete(void* p, Space& home);
249  };
253  bool empty(void) const;
255  int pop(Space& home);
257  void push(Space& home, int p);
259  bool run;
263  static const int n_threshold = 7;
265  NaryLqLe(Space& home, bool share, NaryLqLe<View,o>& p);
267  NaryLqLe(Home home, ViewArray<View>&);
268  public:
270  virtual Actor* copy(Space& home, bool share);
272  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
274  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
276  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
278  virtual size_t dispose(Space& home);
280  static ExecStatus post(Home home, ViewArray<View>& x);
281  };
282 
289  template<class View>
290  class NaryNq : public NaryPropagator<View,PC_INT_VAL> {
291  protected:
294  NaryNq(Home home, ViewArray<View>& x);
296  NaryNq(Space& home, bool share, NaryNq<View>& p);
297  public:
299  virtual Actor* copy(Space& home, bool share);
301  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
303  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
305  static ExecStatus post(Home home, ViewArray<View>& x);
307  virtual size_t dispose(Space& home);
308  };
309 
310 
317  template<class View, class CtrlView>
318  class ReEqDom : public ReBinaryPropagator<View,PC_INT_DOM,CtrlView> {
319  protected:
323 
325  ReEqDom(Space& home, bool share, ReEqDom& p);
327  ReEqDom(Home home, View x0, View x1, CtrlView b);
328  public:
330  virtual Actor* copy(Space& home, bool share);
332  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
334  static ExecStatus post(Home home, View x0, View x1, CtrlView b);
335  };
336 
343  template<class View, class CtrlView>
344  class ReEqBnd : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
345  protected:
349 
351  ReEqBnd(Space& home, bool share, ReEqBnd& p);
353  ReEqBnd(Home home, View x0, View x1, CtrlView b);
354  public:
356  virtual Actor* copy(Space& home, bool share);
358  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
360  static ExecStatus post(Home home, View x0, View x1, CtrlView b);
361  };
362 
369  template<class View, class CtrlView>
370  class ReEqDomInt : public ReUnaryPropagator<View,PC_INT_DOM,CtrlView> {
371  protected:
374 
376  int c;
378  ReEqDomInt(Space& home, bool share, ReEqDomInt& p);
380  ReEqDomInt(Home home, View x, int c, CtrlView b);
381  public:
383  virtual Actor* copy(Space& home, bool share);
385  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
387  static ExecStatus post(Home home, View x, int c, CtrlView b);
388  };
389 
396  template<class View, class CtrlView>
397  class ReEqBndInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
398  protected:
401 
403  int c;
405  ReEqBndInt(Space& home, bool share, ReEqBndInt& p);
407  ReEqBndInt(Home home, View x, int c, CtrlView b);
408  public:
410  virtual Actor* copy(Space& home, bool share);
412  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
414  static ExecStatus post(Home home, View x, int c, CtrlView b);
415  };
416 
417 
418 
419 
420  /*
421  * Disequality propagators
422  *
423  */
424 
431  template<class View>
432  class Nq : public BinaryPropagator<View,PC_INT_VAL> {
433  protected:
436 
438  Nq(Space& home, bool share, Nq<View>& p);
440  Nq(Home home, View x0, View x1);
441  public:
443  virtual Actor* copy(Space& home, bool share);
445  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
447  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
449  static ExecStatus post(Home home, View x0, View x1);
450  };
451 
452  /*
453  * Order propagators
454  *
455  */
456 
464  template<class View>
465  class Lq : public BinaryPropagator<View,PC_INT_BND> {
466  protected:
469 
471  Lq(Space& home, bool share, Lq& p);
473  Lq(Home home, View x0, View x1);
474  public:
476  virtual Actor* copy(Space& home, bool share);
478  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
480  static ExecStatus post(Home home, View x0, View x1);
481  };
482 
489  template<class View>
490  class Le : public BinaryPropagator<View,PC_INT_BND> {
491  protected:
494 
496  Le(Space& home, bool share, Le& p);
498  Le(Home home, View x0, View x1);
499  public:
501  virtual Actor* copy(Space& home, bool share);
503  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
505  static ExecStatus post(Home home, View x0, View x1);
506  };
507 
508 
509  /*
510  * Reified order propagators
511  *
512  */
513 
521  template<class View, class CtrlView>
522  class ReLq : public ReBinaryPropagator<View,PC_INT_BND,CtrlView> {
523  protected:
527 
529  ReLq(Space& home, bool share, ReLq& p);
531  ReLq(Home home, View x0, View x1, CtrlView b);
532  public:
534  virtual Actor* copy(Space& home, bool share);
536  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
538  static ExecStatus post(Home home, View x0, View x1, CtrlView b);
539  };
540 
548  template<class View, class CtrlView>
549  class ReLqInt : public ReUnaryPropagator<View,PC_INT_BND,CtrlView> {
550  protected:
553 
555  int c;
557  ReLqInt(Space& home, bool share, ReLqInt& p);
559  ReLqInt(Home home, View x, int c, CtrlView b);
560  public:
562  virtual Actor* copy(Space& home, bool share);
564  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
566  static ExecStatus post(Home home, View x, int c, CtrlView b);
567  };
568 
569 
570 
571 
572 
596  template<class View>
597  class LexLqLe : public Propagator {
598  protected:
602  bool strict;
604  LexLqLe(Space& home, bool share, LexLqLe<View>& p);
607  public:
609  virtual Actor* copy(Space& home, bool share);
611  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
613  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
616  bool strict);
618  virtual size_t dispose(Space& home);
619  };
620 
627  template<class View>
628  class LexNq : public Propagator {
629  protected:
631  View x0, y0, x1, y1;
636  RelTest rt, View& x0, View& y0, View x1, View y1);
640  LexNq(Space& home, bool share, LexNq<View>& p);
641  public:
643  virtual Actor* copy(Space& home, bool share);
645  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
647  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
651  virtual size_t dispose(Space& home);
652  };
653 
654 }}}
655 
656 #include <gecode/int/rel/eq.hpp>
657 #include <gecode/int/rel/nq.hpp>
658 #include <gecode/int/rel/lq-le.hpp>
659 #include <gecode/int/rel/lex.hpp>
660 
661 #endif
662 
663 
664 // STATISTICS: int-prop
665