Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
distinct.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  * 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_DISTINCT_HH__
41 #define __GECODE_INT_DISTINCT_HH__
42 
43 #include <gecode/int.hh>
44 
46 #include <gecode/int/rel.hh>
47 
53 namespace Gecode { namespace Int { namespace Distinct {
54 
63  template<class View>
64  class Val : public NaryPropagator<View,PC_INT_VAL> {
65  protected:
67 
69  Val(Home home, ViewArray<View>& x);
71  Val(Space& home, Val<View>& p);
72  public:
74  virtual Actor* copy(Space& home);
76  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
78  static ExecStatus post(Home home, ViewArray<View>& x);
79  };
80 
94  template<class View, bool complete>
96 
97 
98 
124  template<class View>
125  class Bnd : public Propagator {
126  protected:
132  int min_x;
134  int max_x;
136  Bnd(Home home, ViewArray<View>& x);
138  Bnd(Space& home, Bnd<View>& p);
139  public:
141  static ExecStatus post(Home home, ViewArray<View>& x);
143  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
150  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
152  virtual void reschedule(Space& home);
154  virtual Actor* copy(Space& home);
156  virtual size_t dispose(Space& home);
157  };
158 
167  template<class View>
168  ExecStatus prop_bnd(Space& home, ViewArray<View>& x, int& min_x, int& max_x);
169 
178  template<class View>
180 
181 
183  template<class View>
184  class Graph : public ViewValGraph::Graph<View> {
185  public:
194  Graph(void);
198  bool mark(void);
200  ExecStatus prune(Space& home, bool& assigned);
202  bool sync(void);
203  };
204 
215  template<class View>
216  class DomCtrl {
217  protected:
220  public:
222  DomCtrl(void);
224  bool available(void);
228  ExecStatus sync(void);
230  ExecStatus propagate(Space& home, bool& assigned);
231  };
232 
248  template<class View>
249  class Dom : public NaryPropagator<View,PC_INT_DOM> {
250  protected:
255  Dom(Space& home, Dom<View>& p);
257  Dom(Home home, ViewArray<View>& x);
258  public:
260  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
267  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
269  virtual Actor* copy(Space& home);
271  static ExecStatus post(Home home, ViewArray<View>& x);
272  };
273 
280  template<class View>
281  class TerDom : public TernaryPropagator<View,PC_INT_DOM> {
282  protected:
286 
288  TerDom(Space& home, TerDom<View>& p);
290  TerDom(Home home, View x0, View x1, View x2);
291  public:
293  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
295  virtual Actor* copy(Space& home);
297  static ExecStatus post(Home home, View x0, View x1, View x2);
298  };
299 
308  class EqIte : public BinaryPropagator<IntView,PC_INT_DOM> {
309  protected:
313  int c0, c1;
315  EqIte(Space& home, EqIte& p);
317  EqIte(Home home, IntView x0, IntView x1, int c0, int c1);
318  public:
321  virtual Actor* copy(Space& home);
324  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
327  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
329  static ExecStatus post(Home home, IntView x0, IntView x1, int c0, int c1);
330  };
331 
332 }}}
333 
341 
342 #endif
343 
344 // STATISTICS: int-prop
345 
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:163
DomCtrl< View > dc
Propagation controller.
Definition: distinct.hh:253
int min_x
Minimum (approximation) of view in x.
Definition: distinct.hh:132
ViewArray< View > x
Views on which to perform bounds-propagation.
Definition: distinct.hh:128
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: pattern.hpp:513
Val(Home home, ViewArray< View > &x)
Constructor for posting.
Definition: val.hpp:147
View-value graph for propagation.
Definition: distinct.hh:184
Domain consistent distinct propagator.
Definition: distinct.hh:249
ViewArray< View > x
Array of views.
Definition: pattern.hpp:145
Base-class for propagators.
Definition: core.hpp:1023
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Computation spaces.
Definition: core.hpp:1701
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:264
Base-class for both propagators and branchers.
Definition: core.hpp:627
Graph< View > g
Propagation is performed on a view-value graph.
Definition: distinct.hh:219
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ViewArray< View > y
Views on which to perform value-propagation (subset of x)
Definition: distinct.hh:130
Binary propagator.
Definition: pattern.hpp:84
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: pattern.hpp:500
Ternary propagator.
Definition: pattern.hpp:113
n-ary propagator
Definition: pattern.hpp:142
View arrays.
Definition: array.hpp:224
View-value graph base class.
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition: val.hpp:170
ExecStatus prop_val(Space &home, ViewArray< View > &x)
Eliminate singletons by naive value propagation.
Definition: val.hpp:42
Naive value distinct propagator.
Definition: distinct.hh:64
Integer view for integer variables.
Definition: view.hpp:129
Ternary domain consistent distinct propagator.
Definition: distinct.hh:281
Propagation cost.
Definition: core.hpp:485
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
int max_x
Maximum (approximation) of view in x.
Definition: distinct.hh:134
Equal-if-then-else domain-consistent propagator.
Definition: distinct.hh:308
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: val.hpp:157
Bounds consistent distinct propagator.
Definition: distinct.hh:125
Gecode toplevel namespace
#define GECODE_INT_EXPORT
Definition: int.hh:77
virtual void reschedule(Space &home)
Schedule function.
Definition: pattern.hpp:506
ExecStatus prop_bnd(Space &home, ViewArray< View > &x, int *minsorted, int *maxsorted)
Definition: bnd.hpp:197
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
Propagation controller for domain consistent distinct.
Definition: distinct.hh:216