Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.9.1
nvalues.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  *
6  * Copyright:
7  * Christian Schulte, 2011
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #ifndef __GECODE_INT_NVALUES_HH__
35 #define __GECODE_INT_NVALUES_HH__
36 
37 #include <gecode/int.hh>
38 #include <gecode/int/val-set.hh>
39 
45 namespace Gecode { namespace Int { namespace NValues {
46 
50  RET_FST = 0,
52  RET_LST = 1,
54  RET_END = 2
55  };
56 
58  class RangeEvent {
59  public:
63  int val;
65  int view;
67  bool operator <(RangeEvent re) const;
68  };
69 
71  class SymBitMatrix : public Support::BitSet<Region> {
72  protected:
74  int n;
76  int pos(int x, int y) const;
77  public:
79  SymBitMatrix(Region& r, int n);
81  bool get(int x, int y) const;
83  void set(int x, int y);
84  };
85 
86 }}}
87 
90 
92 
93 namespace Gecode { namespace Int { namespace NValues {
94 
96  class Graph : public ViewValGraph::Graph<IntView> {
97  protected:
99  int n_matched;
100  public:
102  Graph(void);
104  int size(void) const;
106  void init(Space& home, const ValSet& vs, const ViewArray<IntView>& x);
108  void sync(void);
109  /*
110  * \brief Mark all edges used that can appear in some maximal matching
111  *
112  * Return true, if any edge can be in fact pruned.
113  */
114  bool mark(void);
116  ExecStatus prune(Space& home);
117  };
118 
119 }}}
120 
122 
123 namespace Gecode { namespace Int { namespace NValues {
124 
131  template<class VY>
132  class IntBase
133  : public MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> {
134  protected:
140  IntBase(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
142  IntBase(Space& home, IntBase<VY>& p);
144  void add(Space& home);
150  void disjoint(Space& home, Region& r, int*& dis, int& n_dis);
152  void eliminate(Space& home);
163  ExecStatus prune_lower(Space& home, int* dis, int n_dis);
170  ExecStatus prune_upper(Space& home, Graph& g);
171  public:
173  virtual PropCost cost(const Space&, const ModEventDelta&) const;
175  virtual size_t dispose(Space& home);
176  };
177 
184  template<class VY>
185  class EqInt : public IntBase<VY> {
186  protected:
187  using IntBase<VY>::x;
188  using IntBase<VY>::y;
189  using IntBase<VY>::vs;
190  using IntBase<VY>::add;
192  using IntBase<VY>::disjoint;
198  EqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
200  EqInt(Space& home, EqInt<VY>& p);
201  public:
203  virtual Propagator* copy(Space& home);
205  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
207  static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
209  virtual size_t dispose(Space& home);
210  };
211 
218  template<class VY>
219  class LqInt : public IntBase<VY> {
220  protected:
221  using IntBase<VY>::x;
222  using IntBase<VY>::y;
223  using IntBase<VY>::vs;
224  using IntBase<VY>::add;
226  using IntBase<VY>::disjoint;
230  LqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
232  LqInt(Space& home, LqInt<VY>& p);
233  public:
235  virtual Propagator* copy(Space& home);
237  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
239  static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
241  virtual size_t dispose(Space& home);
242  };
243 
250  template<class VY>
251  class GqInt : public IntBase<VY> {
252  protected:
253  using IntBase<VY>::x;
254  using IntBase<VY>::y;
255  using IntBase<VY>::vs;
256  using IntBase<VY>::add;
258  using IntBase<VY>::disjoint;
265  GqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
267  GqInt(Space& home, GqInt<VY>& p);
268  public:
270  virtual Propagator* copy(Space& home);
272  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
274  static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
275  };
276 
277 }}}
278 
283 
284 namespace Gecode { namespace Int { namespace NValues {
285 
292  template<class VY>
293  class BoolBase : public Propagator {
294  protected:
296  static const int VS_ZERO = 1 << 0;
298  static const int VS_ONE = 1 << 1;
300  int status;
304  VY y;
306  BoolBase(Home home, int status, ViewArray<BoolView>& x, VY y);
308  BoolBase(Space& home, BoolBase<VY>& p);
309  public:
311  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
313  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
315  virtual void reschedule(Space& home);
317  virtual size_t dispose(Space& home);
318  };
319 
326  template<class VY>
327  class EqBool : public BoolBase<VY> {
328  protected:
329  using BoolBase<VY>::VS_ZERO;
330  using BoolBase<VY>::VS_ONE;
331  using BoolBase<VY>::status;
332  using BoolBase<VY>::c;
333  using BoolBase<VY>::y;
335  EqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
337  EqBool(Space& home, EqBool<VY>& p);
338  public:
340  virtual Actor* copy(Space& home);
342  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
349  static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
350  };
351 
358  template<class VY>
359  class LqBool : public BoolBase<VY> {
360  protected:
361  using BoolBase<VY>::VS_ZERO;
362  using BoolBase<VY>::VS_ONE;
363  using BoolBase<VY>::status;
364  using BoolBase<VY>::c;
365  using BoolBase<VY>::y;
367  LqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
369  LqBool(Space& home, LqBool<VY>& p);
370  public:
372  virtual Actor* copy(Space& home);
374  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
381  static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
382  };
383 
390  template<class VY>
391  class GqBool : public BoolBase<VY> {
392  protected:
393  using BoolBase<VY>::VS_ZERO;
394  using BoolBase<VY>::VS_ONE;
395  using BoolBase<VY>::status;
396  using BoolBase<VY>::c;
397  using BoolBase<VY>::y;
399  GqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
401  GqBool(Space& home, GqBool<VY>& p);
402  public:
404  virtual Actor* copy(Space& home);
406  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
413  static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
414  };
415 
416 }}}
417 
422 
423 #endif
424 
425 // STATISTICS: int-prop
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Base-class for both propagators and branchers.
Definition: core.hpp:628
Base-class for advisors.
Definition: core.hpp:1292
Council of advisors
Definition: core.hpp:1241
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Home class for posting propagators
Definition: core.hpp:856
Number of values propagator for Boolean views base class.
Definition: nvalues.hh:293
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: bool-base.hpp:91
Council< ViewAdvisor< BoolView > > c
The advisor council.
Definition: nvalues.hh:302
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary)
Definition: bool-base.hpp:58
BoolBase(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-base.hpp:38
static const int VS_ONE
View status: a one has already been encountered.
Definition: nvalues.hh:298
VY y
The view for counting the number of values.
Definition: nvalues.hh:304
virtual void reschedule(Space &home)
Schedule function.
Definition: bool-base.hpp:64
static const int VS_ZERO
View status: a zero has already been encountered.
Definition: nvalues.hh:296
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: bool-base.hpp:70
int status
Status information about the views.
Definition: nvalues.hh:300
Equal to number of values propagator for Boolean views.
Definition: nvalues.hh:327
EqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-eq.hpp:41
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition: bool-eq.hpp:57
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-eq.hpp:118
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: bool-eq.hpp:51
Equal to number of values propagator for integer views.
Definition: nvalues.hh:185
EqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-eq.hpp:41
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: int-eq.hpp:102
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-eq.hpp:108
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition: int-eq.hpp:48
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-eq.hpp:116
Graph g
View-value graph.
Definition: nvalues.hh:196
Greater or equal to number of values propagator for Boolean views.
Definition: nvalues.hh:391
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-gq.hpp:109
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: bool-gq.hpp:50
GqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-gq.hpp:40
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition: bool-gq.hpp:56
Greater or equal to number of values propagator for integer views.
Definition: nvalues.hh:251
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition: int-gq.hpp:46
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: int-gq.hpp:98
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-gq.hpp:104
GqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-gq.hpp:41
Graph g
View-value graph.
Definition: nvalues.hh:263
View-value graph for propagation of upper bound.
Definition: nvalues.hh:96
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition: graph.hpp:46
void sync(void)
Synchronize graph with new view domains.
Definition: graph.hpp:90
Graph(void)
Construct graph as not yet initialized.
Definition: graph.hpp:37
int n_matched
Number of matched edges.
Definition: nvalues.hh:99
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition: graph.hpp:255
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition: graph.hpp:41
Number of values propagator for integer views base class.
Definition: nvalues.hh:133
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-base.hpp:53
ValSet vs
Value set storing the values of already assigned views.
Definition: nvalues.hh:138
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition: int-base.hpp:130
void disjoint(Space &home, Region &r, int *&dis, int &n_dis)
Definition: int-base.hpp:80
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition: int-base.hpp:62
void add(Space &home)
Add values of assigned views to value set.
Definition: int-base.hpp:68
void eliminate(Space &home)
Eliminate subsumed views (all values included in the value set vs)
Definition: int-base.hpp:107
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition: int-base.hpp:120
ExecStatus prune_upper(Space &home, Graph &g)
Definition: int-base.hpp:298
IntBase(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-base.hpp:40
Less or equal to number of values propagator for Boolean views.
Definition: nvalues.hh:359
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: bool-lq.hpp:50
LqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-lq.hpp:40
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition: bool-lq.hpp:56
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-lq.hpp:111
Less or equal to number of values propagator for integer views.
Definition: nvalues.hh:219
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition: int-lq.hpp:48
LqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-lq.hpp:41
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-lq.hpp:104
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-lq.hpp:112
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: int-lq.hpp:98
Event for range-based overlap analysis.
Definition: nvalues.hh:58
RangeEventType ret
The event type.
Definition: nvalues.hh:61
int view
Which view does this range belong to.
Definition: nvalues.hh:65
int val
The value for the range (first or last value, depending on type)
Definition: nvalues.hh:63
bool operator<(RangeEvent re) const
Order events: first by val, then by event type.
Definition: range-event.hpp:37
Symmetric diagonal bit matrix.
Definition: nvalues.hh:71
bool get(int x, int y) const
Is bit at position x, y set?
int pos(int x, int y) const
Return position in matrix.
void set(int x, int y)
Set bit at position x, y.
SymBitMatrix(Region &r, int n)
Initialize matrix for dimension n by n.
Class for storing values of already assigned views.
Definition: val-set.hh:44
View-value graph base class.
Mixed (n+1)-ary propagator.
Definition: pattern.hpp:272
Propagation cost.
Definition: core.hpp:486
Base-class for propagators.
Definition: core.hpp:1064
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
Simple bitsets.
Definition: bitset.hpp:45
View arrays.
Definition: array.hpp:253
ExecStatus
Definition: core.hpp:472
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
RangeEventType
Event type for range-based overlap analysis.
Definition: nvalues.hh:48
@ RET_FST
A range starts.
Definition: nvalues.hh:50
@ RET_LST
A range ends.
Definition: nvalues.hh:52
@ RET_END
No further events.
Definition: nvalues.hh:54
Gecode::IntSet d(v, 7)