Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2011-09-07 16:15:16 +0200 (Wed, 07 Sep 2011) $ by $Author: schulte $
11  * $Revision: 12394 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_INT_NVALUES_HH__
39 #define __GECODE_INT_NVALUES_HH__
40 
41 #include <gecode/int.hh>
42 #include <gecode/int/val-set.hh>
43 
49 namespace Gecode { namespace Int { namespace NValues {
50 
54  RET_FST = 0,
56  RET_LST = 1,
58  RET_END = 2
59  };
60 
62  class RangeEvent {
63  public:
67  int val;
69  int view;
71  bool operator <(RangeEvent re) const;
72  };
73 
75  class SymBitMatrix : public Support::BitSet<Region> {
76  protected:
78  int n;
80  int pos(int x, int y) const;
81  public:
83  SymBitMatrix(Region& r, int n);
85  bool get(int x, int y) const;
87  void set(int x, int y);
88  };
89 
90 }}}
91 
94 
96 
97 namespace Gecode { namespace Int { namespace NValues {
98 
100  class Graph : public ViewValGraph::Graph<IntView> {
101  protected:
104  public:
106  Graph(void);
108  int size(void) const;
110  void init(Space& home, const ValSet& vs, const ViewArray<IntView>& x);
112  void sync(Space& home);
113  /*
114  * \brief Mark all edges used that can appear in some maximal matching
115  *
116  * Return true, if any edge can be in fact pruned.
117  */
118  bool mark(Space& home);
120  ExecStatus prune(Space& home);
121  };
122 
123 }}}
124 
126 
127 namespace Gecode { namespace Int { namespace NValues {
128 
135  template<class VY>
136  class IntBase
137  : public MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> {
138  protected:
144  IntBase(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
146  IntBase(Space& home, bool share, IntBase<VY>& p);
148  void add(Space& home);
154  void disjoint(Space& home, Region& r, int*& dis, int& n_dis);
156  void eliminate(Space& home);
158  int size(Space& home) const;
169  ExecStatus prune_lower(Space& home, int* dis, int n_dis);
176  ExecStatus prune_upper(Space& home, Graph& g);
177  public:
179  virtual PropCost cost(const Space&, const ModEventDelta&) const;
181  virtual size_t dispose(Space& home);
182  };
183 
190  template<class VY>
191  class EqInt : public IntBase<VY> {
192  protected:
193  using IntBase<VY>::x;
194  using IntBase<VY>::y;
195  using IntBase<VY>::vs;
196  using IntBase<VY>::add;
198  using IntBase<VY>::disjoint;
204  EqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
206  EqInt(Space& home, bool share, EqInt<VY>& p);
207  public:
209  virtual Propagator* copy(Space& home, bool share);
211  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
213  static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
215  virtual size_t dispose(Space& home);
216  };
217 
224  template<class VY>
225  class LqInt : public IntBase<VY> {
226  protected:
227  using IntBase<VY>::x;
228  using IntBase<VY>::y;
229  using IntBase<VY>::vs;
230  using IntBase<VY>::add;
232  using IntBase<VY>::disjoint;
236  LqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
238  LqInt(Space& home, bool share, LqInt<VY>& p);
239  public:
241  virtual Propagator* copy(Space& home, bool share);
243  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
245  static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
247  virtual size_t dispose(Space& home);
248  };
249 
256  template<class VY>
257  class GqInt : public IntBase<VY> {
258  protected:
259  using IntBase<VY>::x;
260  using IntBase<VY>::y;
261  using IntBase<VY>::vs;
262  using IntBase<VY>::add;
264  using IntBase<VY>::disjoint;
271  GqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
273  GqInt(Space& home, bool share, GqInt<VY>& p);
274  public:
276  virtual Propagator* copy(Space& home, bool share);
278  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
280  static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
281  };
282 
283 }}}
284 
289 
290 namespace Gecode { namespace Int { namespace NValues {
291 
298  template<class VY>
299  class BoolBase : public Propagator {
300  protected:
302  static const int VS_ZERO = 1 << 0;
304  static const int VS_ONE = 1 << 1;
306  int status;
310  VY y;
312  BoolBase(Home home, int status, ViewArray<BoolView>& x, VY y);
314  BoolBase(Space& home, bool share, BoolBase<VY>& p);
315  public:
317  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
319  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
321  virtual size_t dispose(Space& home);
322  };
323 
330  template<class VY>
331  class EqBool : public BoolBase<VY> {
332  protected:
333  using BoolBase<VY>::VS_ZERO;
334  using BoolBase<VY>::VS_ONE;
335  using BoolBase<VY>::status;
336  using BoolBase<VY>::c;
337  using BoolBase<VY>::y;
339  EqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
341  EqBool(Space& home, bool share, EqBool<VY>& p);
342  public:
344  virtual Actor* copy(Space& home, bool share);
346  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
353  static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
354  };
355 
362  template<class VY>
363  class LqBool : public BoolBase<VY> {
364  protected:
365  using BoolBase<VY>::VS_ZERO;
366  using BoolBase<VY>::VS_ONE;
367  using BoolBase<VY>::status;
368  using BoolBase<VY>::c;
369  using BoolBase<VY>::y;
371  LqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
373  LqBool(Space& home, bool share, LqBool<VY>& p);
374  public:
376  virtual Actor* copy(Space& home, bool share);
378  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
385  static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
386  };
387 
394  template<class VY>
395  class GqBool : public BoolBase<VY> {
396  protected:
397  using BoolBase<VY>::VS_ZERO;
398  using BoolBase<VY>::VS_ONE;
399  using BoolBase<VY>::status;
400  using BoolBase<VY>::c;
401  using BoolBase<VY>::y;
403  GqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
405  GqBool(Space& home, bool share, GqBool<VY>& p);
406  public:
408  virtual Actor* copy(Space& home, bool share);
410  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
417  static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
418  };
419 
420 }}}
421 
426 
427 #endif
428 
429 // STATISTICS: int-prop
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition: int-base.hpp:155
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-lq.hpp:116
Council of advisors
Definition: core.hpp:226
static const int VS_ONE
View status: a one has already been encountered.
Definition: nvalues.hh:304
Greater or equal to number of values propagator for integer views.
Definition: nvalues.hh:257
Graph g
View-value graph.
Definition: nvalues.hh:269
Event for range-based overlap analysis.
Definition: nvalues.hh:62
void add(Space &home)
Add values of assigned views to value set.
Definition: int-base.hpp:72
int size(Space &home) const
Return a size estimate based on the union of all values.
Definition: int-base.hpp:124
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-gq.hpp:108
int n_matched
Number of matched edges.
Definition: nvalues.hh:103
int pos(int x, int y) const
Return position in matrix.
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition: bool-eq.hpp:61
Less or equal to number of values propagator for Boolean views.
Definition: nvalues.hh:363
GqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-gq.hpp:45
Graph(void)
Construct graph as not yet initialized.
Definition: graph.hpp:41
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-base.hpp:57
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-lq.hpp:108
Mixed (n+1)-ary propagator.
Definition: propagator.hpp:268
EqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-eq.hpp:45
LqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-lq.hpp:45
Equal to number of values propagator for integer views.
Definition: nvalues.hh:191
Base-class for propagators.
Definition: core.hpp:755
int val
The value for the range (first or last value, depending on type)
Definition: nvalues.hh:67
Base-class for advisors.
Definition: core.hpp:926
No further events.
Definition: nvalues.hh:58
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: bool-lq.hpp:54
LqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-lq.hpp:44
void eliminate(Space &home)
Eliminate subsumed views (all values included in the value set vs)
Definition: int-base.hpp:111
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-eq.hpp:120
Handle to region.
Definition: region.hpp:61
EqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-eq.hpp:45
Computation spaces.
Definition: core.hpp:1362
Graph g
View-value graph.
Definition: nvalues.hh:202
Base-class for both propagators and branchers.
Definition: core.hpp:666
int status
Status information about the views.
Definition: nvalues.hh:306
Gecode::IntSet d(v, 7)
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition: bool-gq.hpp:60
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: bool-gq.hpp:54
VY y
The view for counting the number of values.
Definition: nvalues.hh:310
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition: int-base.hpp:145
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: bool-base.hpp:68
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
IntBase(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-base.hpp:44
ExecStatus prune_upper(Space &home, Graph &g)
Definition: int-base.hpp:321
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
int view
Which view does this range belong to.
Definition: nvalues.hh:69
Number of values propagator for Boolean views base class.
Definition: nvalues.hh:299
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition: bool-lq.hpp:60
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: bool-eq.hpp:55
virtual Propagator * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: int-eq.hpp:106
GqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-gq.hpp:44
static const int VS_ZERO
View status: a zero has already been encountered.
Definition: nvalues.hh:302
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition: int-gq.hpp:50
View-value graph for propagation of upper bound.
Definition: nvalues.hh:100
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition: graph.hpp:45
bool mark(Space &home)
Definition: graph.hpp:155
virtual Propagator * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: int-lq.hpp:102
View-value graph base class.
ValSet vs
Value set storing the values of already assigned views.
Definition: nvalues.hh:142
void sync(Space &home)
Synchronize graph with new view domains.
Definition: graph.hpp:94
RangeEventType
Event type for range-based overlap analysis.
Definition: nvalues.hh:52
void set(int x, int y)
Set bit at position x, y.
Less or equal to number of values propagator for integer views.
Definition: nvalues.hh:225
void disjoint(Space &home, Region &r, int *&dis, int &n_dis)
Definition: int-base.hpp:84
bool operator<(RangeEvent re) const
Order events: first by val, then by event type.
Definition: range-event.hpp:41
RangeEventType ret
The event type.
Definition: nvalues.hh:65
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:275
Propagation cost.
Definition: core.hpp:537
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-eq.hpp:122
ExecStatus
Definition: core.hpp:523
Symmetric diagonal bit matrix.
Definition: nvalues.hh:75
Greater or equal to number of values propagator for Boolean views.
Definition: nvalues.hh:395
A range starts.
Definition: nvalues.hh:54
Simple bitsets.
Definition: bitset.hpp:49
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-gq.hpp:113
Class for storing values of already assigned views.
Definition: val-set.hh:48
SymBitMatrix(Region &r, int n)
Initialize matrix for dimension n by n.
Equal to number of values propagator for Boolean views.
Definition: nvalues.hh:331
Gecode toplevel namespace
BoolBase(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition: bool-base.hpp:42
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: bool-base.hpp:89
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bool-lq.hpp:115
Number of values propagator for integer views base class.
Definition: nvalues.hh:136
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition: int-base.hpp:66
Council< ViewAdvisor< BoolView > > c
The advisor council.
Definition: nvalues.hh:308
Home class for posting propagators
Definition: core.hpp:717
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-eq.hpp:112
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition: int-eq.hpp:52
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition: int-lq.hpp:52
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition: graph.hpp:50
virtual Propagator * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: int-gq.hpp:102
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary)
Definition: bool-base.hpp:62
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition: graph.hpp:258