Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.1
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: 2011-09-20 13:58:39 +0200 (Tue, 20 Sep 2011) $ by $Author: schulte $
13  * $Revision: 12404 $
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  enum ViewTypeDesc {
62  };
64  template<class VY>
65  ViewTypeDesc vtd(VY y);
66 
68  template<class VY>
69  void subscribe(Space& home, Propagator& p, VY y);
71  template<class VY>
72  void cancel(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>
94  template<class VX>
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>
107  template<class VX>
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>
120  template<class VX>
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 size_t dispose(Space& home);
158  };
159 
170  template<class VX, class VY>
171  class EqInt : public IntBase<VX,VY> {
172  protected:
173  using IntBase<VX,VY>::x;
174  using IntBase<VX,VY>::n_s;
175  using IntBase<VX,VY>::y;
176  using IntBase<VX,VY>::c;
178  EqInt(Space& home, bool share, EqInt& p);
180  EqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
181  public:
183  virtual Actor* copy(Space& home, bool share);
185  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
187  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
188  };
189 
200  template<class VX, class VY>
201  class GqInt : public IntBase<VX,VY> {
202  protected:
203  using IntBase<VX,VY>::x;
204  using IntBase<VX,VY>::n_s;
205  using IntBase<VX,VY>::y;
206  using IntBase<VX,VY>::c;
208  GqInt(Space& home, bool share, GqInt& p);
210  GqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
211  public:
213  virtual Actor* copy(Space& home, bool share);
215  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
217  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
218  };
219 
230  template<class VX, class VY>
231  class LqInt : public IntBase<VX,VY> {
232  protected:
233  using IntBase<VX,VY>::x;
234  using IntBase<VX,VY>::n_s;
235  using IntBase<VX,VY>::y;
236  using IntBase<VX,VY>::c;
238  LqInt(Space& home, bool share, LqInt& p);
240  LqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c);
241  public:
243  virtual Actor* copy(Space& home, bool share);
245  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
247  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, int c);
248  };
249 
250 }}}
251 
256 
257 
258 namespace Gecode { namespace Int { namespace Count {
259 
264  template<class VX, class VY, class VZ>
265  class ViewBase : public Propagator {
266  protected:
270  VY y;
272  VZ z;
274  int c;
276  ViewBase(Space& home, bool share, ViewBase& p);
278  ViewBase(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
279  public:
281  virtual size_t dispose(Space& home);
283  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
284  protected:
286  void count(Space& home);
288  int atleast(void) const;
290  int atmost(void) const;
292  static bool sharing(const ViewArray<VX>& x, const VY& y, const VZ& z);
293  };
294 
305  template<class VX, class VY, class VZ, bool shr, bool dom>
306  class EqView : public ViewBase<VX,VY,VZ> {
307  protected:
308  using ViewBase<VX,VY,VZ>::x;
309  using ViewBase<VX,VY,VZ>::z;
310  using ViewBase<VX,VY,VZ>::c;
311  using ViewBase<VX,VY,VZ>::y;
316 
318  EqView(Space& home, bool share, EqView& p);
319  public:
321  EqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
323  virtual Actor* copy(Space& home, bool share);
325  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
327  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
328  };
329 
340  template<class VX, class VY, class VZ, bool shr>
341  class LqView : public ViewBase<VX,VY,VZ> {
342  protected:
343  using ViewBase<VX,VY,VZ>::x;
344  using ViewBase<VX,VY,VZ>::z;
345  using ViewBase<VX,VY,VZ>::c;
346  using ViewBase<VX,VY,VZ>::y;
351 
353  LqView(Space& home, bool share, LqView& p);
354  public:
356  LqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
358  virtual Actor* copy(Space& home, bool share);
360  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
362  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
363  };
364 
375  template<class VX, class VY, class VZ, bool shr, bool dom>
376  class GqView : public ViewBase<VX,VY,VZ> {
377  protected:
378  using ViewBase<VX,VY,VZ>::x;
379  using ViewBase<VX,VY,VZ>::z;
380  using ViewBase<VX,VY,VZ>::c;
381  using ViewBase<VX,VY,VZ>::y;
386 
388  GqView(Space& home, bool share, GqView& p);
389  public:
391  GqView(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
393  virtual Actor* copy(Space& home, bool share);
395  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
397  static ExecStatus post(Home home, ViewArray<VX>& x, VY y, VZ z, int c);
398  };
399 
400 }}}
401 
406 
407 #endif
408 
409 // STATISTICS: int-prop
410 
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
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:84
VZ z
View which yields result of counting.
Definition: count.hh:272
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:119
int atleast(void) const
How many views are at least equal.
Definition: view-base.hpp:102
Base-class for count propagators (view)
Definition: count.hh:265
RelTest holds(VX x, ConstIntView y)
Test whether x and y are equal.
Definition: rel.hpp:96
Base-class for propagators.
Definition: core.hpp:755
Baseclass for count propagators (integer)
Definition: count.hh:139
ViewTypeDesc
Description of view type.
Definition: count.hh:58
Propagator for counting views (equal to number of equal views)
Definition: count.hh:306
Computation spaces.
Definition: core.hpp:1362
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:245
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:666
Propagator for counting views (less or equal integer to number of equal views)
Definition: count.hh:231
Propagator for counting views (greater or equal to number of equal views)
Definition: count.hh:376
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:270
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:171
ViewArray< VX > x
Views still to count.
Definition: count.hh:268
int c
Number of views which are equal and have been eliminated.
Definition: count.hh:274
RelTest
Result of testing relation.
Definition: view.hpp:1614
void count(Space &home)
Count how many views are equal now.
Definition: view-base.hpp:81
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:74
ViewTypeDesc vtd(VY y)
Return the view type description of y.
Definition: rel.hpp:49
GqInt(Space &home, bool share, GqInt &p)
Constructor for cloning p.
Definition: int-gq.hpp:77
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: int-base.hpp:74
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
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:341
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
Integer sets.
Definition: int.hh:171
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:201
int atmost(void) const
How many views are at most equal.
Definition: view-base.hpp:108
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view-lq.hpp:74
Zero integer view.
Definition: view.hpp:959
Constant integer view.
Definition: view.hpp:804
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Propagation cost.
Definition: core.hpp:537
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:523
LqInt(Space &home, bool share, LqInt &p)
Constructor for cloning p.
Definition: int-lq.hpp:75
Gecode toplevel namespace
ExecStatus post_false(Home home, VX x, ConstIntView y)
Definition: rel.hpp:175
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: view-base.hpp:63
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: view-base.hpp:69
static ExecStatus post(Home home, ViewArray< VX > &x, VY y, int c)
Post propagator for .
Definition: int-gq.hpp:47
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
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:132