Generated on Thu Jan 31 2019 20:56:35 for Gecode by doxygen 1.8.15
count.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  * Copyright:
8  * Christian Schulte, 2002
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
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_COUNT_HH__
41 #define __GECODE_INT_COUNT_HH__
42 
43 #include <gecode/int.hh>
44 
50 namespace Gecode { namespace Int { namespace Count {
51 
57  template<class VY>
59  bool isintset(VY y);
61  template<class VY>
62  bool isval(VY y);
63 
65  template<class VY>
66  void subscribe(Space& home, Propagator& p, VY y);
68  template<class VY>
69  void cancel(Space& home, Propagator& p, VY y);
71  template<class VY>
72  void reschedule(Space& home, Propagator& p, VY y);
73 
75  template<class VX>
76  RelTest holds(VX x, VX y);
78  template<class VX>
79  RelTest holds(VX x, ConstIntView y);
81  template<class VX>
82  RelTest holds(VX x, ZeroIntView y);
84  template<class VX>
85  RelTest holds(VX x, const IntSet& y);
86 
88  template<class VX>
89  ExecStatus post_true(Home home, ViewArray<VX>& x, VX y);
91  template<class VX>
92  ExecStatus post_true(Home home, ViewArray<VX>& x, ConstIntView y);
94  template<class VX>
95  ExecStatus post_true(Home home, ViewArray<VX>& x, ZeroIntView y);
97  template<class VX>
98  ExecStatus post_true(Home home, ViewArray<VX>& x, const IntSet& y);
99 
101  template<class VX>
102  ExecStatus post_false(Home home, ViewArray<VX>& x, VX y);
104  template<class VX>
105  ExecStatus post_false(Home home, ViewArray<VX>& x, ConstIntView y);
107  template<class VX>
108  ExecStatus post_false(Home home, ViewArray<VX>& x, ZeroIntView y);
110  template<class VX>
111  ExecStatus post_false(Home home, ViewArray<VX>& x, const IntSet& y);
112 
114  template<class VX>
115  ExecStatus prune(Home home, ViewArray<VX>& x, VX y);
117  template<class VX>
118  ExecStatus prune(Home home, ViewArray<VX>& x, ConstIntView y);
120  template<class VX>
121  ExecStatus prune(Home home, ViewArray<VX>& x, ZeroIntView y);
123  template<class VX>
124  ExecStatus prune(Home home, ViewArray<VX>& x, const IntSet& y);
126 
127 }}}
128 
129 #include <gecode/int/count/rel.hpp>
130 
131 
132 namespace Gecode { namespace Int { namespace Count {
133 
138  template<class VX, class VY>
139  class IntBase : public Propagator {
140  protected:
144  int n_s;
146  VY y;
148  int c;
150  IntBase(Space& home, bool share, IntBase& p);
152  IntBase(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
153  public:
155  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
157  virtual void reschedule(Space& home);
159  virtual size_t dispose(Space& home);
160  };
161 
172  template<class VX, class VY>
173  class EqInt : public IntBase<VX,VY> {
174  protected:
175  using IntBase<VX,VY>::x;
176  using IntBase<VX,VY>::n_s;
177  using IntBase<VX,VY>::y;
178  using IntBase<VX,VY>::c;
180  EqInt(Space& home, bool share, EqInt& p);
182  EqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
183  public:
185  virtual Actor* copy(Space& home, bool share);
187  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
189  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
190  };
191 
202  template<class VX, class VY>
203  class GqInt : public IntBase<VX,VY> {
204  protected:
205  using IntBase<VX,VY>::x;
206  using IntBase<VX,VY>::n_s;
207  using IntBase<VX,VY>::y;
208  using IntBase<VX,VY>::c;
210  GqInt(Space& home, bool share, GqInt& p);
212  GqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
213  public:
215  virtual Actor* copy(Space& home, bool share);
217  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
219  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
220  };
221 
232  template<class VX, class VY>
233  class LqInt : public IntBase<VX,VY> {
234  protected:
235  using IntBase<VX,VY>::x;
236  using IntBase<VX,VY>::n_s;
237  using IntBase<VX,VY>::y;
238  using IntBase<VX,VY>::c;
240  LqInt(Space& home, bool share, LqInt& p);
242  LqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
243  public:
245  virtual Actor* copy(Space& home, bool share);
247  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
249  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
250  };
251 
252 }}}
253 
258 
259 
260 namespace Gecode { namespace Int { namespace Count {
261 
266  template<class VX, class VY, class VZ>
267  class ViewBase : public Propagator {
268  protected:
272  VY y;
274  VZ z;
276  int c;
278  ViewBase(Space& home, bool share, ViewBase& p);
280  ViewBase(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
281  public:
283  virtual size_t dispose(Space& home);
285  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
287  virtual void reschedule(Space& home);
288  protected:
290  void count(Space& home);
292  int atleast(void) const;
294  int atmost(void) const;
296  static bool sharing(const ViewArray<VX>& x, const VY& y, const VZ& z);
297  };
298 
309  template<class VX, class VY, class VZ, bool shr, bool dom>
310  class EqView : public ViewBase<VX,VY,VZ> {
311  protected:
312  using ViewBase<VX,VY,VZ>::x;
313  using ViewBase<VX,VY,VZ>::z;
314  using ViewBase<VX,VY,VZ>::c;
315  using ViewBase<VX,VY,VZ>::y;
320 
322  EqView(Space& home, bool share, EqView& p);
323  public:
325  EqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
327  virtual Actor* copy(Space& home, bool share);
329  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
331  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
332  };
333 
344  template<class VX, class VY, class VZ, bool shr>
345  class LqView : public ViewBase<VX,VY,VZ> {
346  protected:
347  using ViewBase<VX,VY,VZ>::x;
348  using ViewBase<VX,VY,VZ>::z;
349  using ViewBase<VX,VY,VZ>::c;
350  using ViewBase<VX,VY,VZ>::y;
355 
357  LqView(Space& home, bool share, LqView& p);
358  public:
360  LqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
362  virtual Actor* copy(Space& home, bool share);
364  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
366  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
367  };
368 
379  template<class VX, class VY, class VZ, bool shr, bool dom>
380  class GqView : public ViewBase<VX,VY,VZ> {
381  protected:
382  using ViewBase<VX,VY,VZ>::x;
383  using ViewBase<VX,VY,VZ>::z;
384  using ViewBase<VX,VY,VZ>::c;
385  using ViewBase<VX,VY,VZ>::y;
390 
392  GqView(Space& home, bool share, GqView& p);
393  public:
395  GqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
397  virtual Actor* copy(Space& home, bool share);
399  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
401  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
402  };
403 
404 }}}
405 
410 
411 #endif
412 
413 // STATISTICS: int-prop
414 
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-lq.hpp:80
VY y
View to compare to.
Definition: count.hh:146
int atleast(void) const
How many views are at least equal.
Definition: view-base.hpp:110
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view-eq.hpp:75
ViewArray< VX > x
Views still to count.
Definition: count.hh:142
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: view-eq.hpp:69
LqView(Space &home, bool share, LqView &p)
Constructor for cloning p.
Definition: view-lq.hpp:62
static ExecStatus post(Home home, ViewArray< VX > &x, VY y, int c)
Post propagator for .
Definition: int-eq.hpp:47
int n_s
Views from x[0] ... x[n_s-1] have subscriptions.
Definition: count.hh:144
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:85
VZ z
View which yields result of counting.
Definition: count.hh:274
static bool sharing(const ViewArray< VX > &x, const VY &y, const VZ &z)
Test whether there is sharing of z with x or y.
Definition: view-base.hpp:127
Base-class for count propagators (view)
Definition: count.hh:267
RelTest holds(VX x, ConstIntView y)
Test whether x and y are equal.
Definition: rel.hpp:108
Base-class for propagators.
Definition: core.hpp:1092
Baseclass for count propagators (integer)
Definition: count.hh:139
bool isval(VY y)
Return whether y is a value.
Definition: rel.hpp:63
Propagator for counting views (equal to number of equal views)
Definition: count.hh:310
Computation spaces.
Definition: core.hpp:1748
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:257
EqInt(Space &home, bool share, EqInt &p)
Constructor for cloning p.
Definition: int-eq.hpp:80
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-eq.hpp:85
static ExecStatus post(Home home, ViewArray< VX > &x, VY y, int c)
Post propagator for .
Definition: int-lq.hpp:47
Base-class for both propagators and branchers.
Definition: core.hpp:696
Propagator for counting views (less or equal integer to number of equal views)
Definition: count.hh:233
Propagator for counting views (greater or equal to number of equal views)
Definition: count.hh:380
EqView(Space &home, bool share, EqView &p)
Constructor for cloning p.
Definition: view-eq.hpp:63
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
VY y
View to compare to.
Definition: count.hh:272
ViewBase(Space &home, bool share, ViewBase &p)
Constructor for cloning p.
Definition: view-base.hpp:54
Propagator for counting views (equal integer to number of equal views)
Definition: count.hh:173
ViewArray< VX > x
Views still to count.
Definition: count.hh:270
int c
Number of views which are equal and have been eliminated.
Definition: count.hh:276
RelTest
Result of testing relation.
Definition: view.hpp:1614
void count(Space &home)
Count how many views are equal now.
Definition: view-base.hpp:89
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
GqInt(Space &home, bool share, GqInt &p)
Constructor for cloning p.
Definition: int-gq.hpp:77
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
static ExecStatus post(Home home, ViewArray< VX > &x, VY y, VZ z, int c)
Post propagator for .
Definition: view-eq.hpp:48
static ExecStatus post(Home home, ViewArray< VX > &x, VY y, VZ z, int c)
Post propagator for .
Definition: view-lq.hpp:48
Propagator for counting views (less or equal to number of equal views)
Definition: count.hh:345
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-lq.hpp:86
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-gq.hpp:82
int c
Number of views which are equal and have been eliminated.
Definition: count.hh:148
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-eq.hpp:91
virtual void reschedule(Space &home)
Schedule function.
Definition: int-base.hpp:80
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: view-lq.hpp:68
static ExecStatus post(Home home, ViewArray< VX > &x, VY y, VZ z, int c)
Post propagator for .
Definition: view-gq.hpp:47
Propagator for counting views (greater or equal integer to number of equal views)
Definition: count.hh:203
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view-lq.hpp:74
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
virtual void reschedule(Space &home)
Schedule function.
Definition: view-base.hpp:69
Propagation cost.
Definition: core.hpp:554
IntBase(Space &home, bool share, IntBase &p)
Constructor for cloning p.
Definition: int-base.hpp:66
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-base.hpp:54
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-gq.hpp:88
ExecStatus
Definition: core.hpp:540
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: view-base.hpp:63
Post propagator for SetVar x
Definition: set.hh:784
bool isintset(VY y)
Return whether y is an integer set.
Definition: rel.hpp:49
int atmost(void) const
How many views are at most equal.
Definition: view-base.hpp:116
LqInt(Space &home, bool share, LqInt &p)
Constructor for cloning p.
Definition: int-lq.hpp:75
Gecode toplevel namespace
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: int-base.hpp:74
ExecStatus post_false(Home home, VX x, ConstIntView y)
Definition: rel.hpp:187
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: view-base.hpp:77
static ExecStatus post(Home home, ViewArray< VX > &x, VY y, int c)
Post propagator for .
Definition: int-gq.hpp:47
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view-gq.hpp:73
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: view-gq.hpp:67
GqView(Space &home, bool share, GqView &p)
Constructor for cloning p.
Definition: view-gq.hpp:61
ExecStatus post_true(Home home, VX x, ConstIntView y)
Definition: rel.hpp:144