Generated on Tue Jun 4 2019 05:23:33 for Gecode by doxygen 1.8.15
element.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, 2004
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2010-05-03 18:31:57 +0200 (Mon, 03 May 2010) $ by $Author: schulte $
13  * $Revision: 10846 $
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_ELEMENT_HH__
41 #define __GECODE_INT_ELEMENT_HH__
42 
43 #include <gecode/int.hh>
44 #include <gecode/int/rel.hh>
45 
51 namespace Gecode { namespace Int { namespace Element {
52 
59  template<class V0, class V1, class Idx, class Val>
60  class Int : public Propagator {
61  protected:
70  class IdxVal {
71  public:
72  Idx idx_next;
73  Idx val_next;
74  Idx idx;
75  Val val;
76  void mark(void);
79  bool marked(void) const;
80  };
87  class IterIdxUnmark {
88  private:
89  IdxVal* iv;
90  Idx i;
91  public:
93  IterIdxUnmark(IdxVal* iv);
95  bool operator ()(void) const;
97  void operator ++(void);
99  Idx val(void) const;
100  };
107  class IterVal {
108  private:
109  IdxVal* iv;
110  Idx i;
111  public:
113  IterVal(IdxVal* iv);
115  bool operator ()(void) const;
117  void operator ++(void);
119  Val val(void) const;
120  };
130  private:
131  IdxVal* iv;
132  Idx i;
133  public:
135  IterValUnmark(IdxVal* iv);
137  bool operator ()(void) const;
139  void operator ++(void);
141  Val val(void) const;
142  };
144  class ByVal {
145  protected:
146  const IdxVal* iv;
147  public:
149  ByVal(const IdxVal* iv);
151  bool operator ()(Idx& i, Idx& j);
152  };
153 
155  V0 x0;
161  V1 x1;
171  void prune_idx(void);
173  void prune_val(void);
175  static ExecStatus assigned_val(Space& home, IntSharedArray& c,
176  V0 x0, V1 x1);
178  Int(Space& home, bool shared, Int& p);
180  Int(Home home, IntSharedArray& i, V0 x0, V1 x1);
181  public:
183  virtual Actor* copy(Space& home, bool share);
185  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
187  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
189  static ExecStatus post(Home home, IntSharedArray& i, V0 x0, V1 x1);
191  virtual size_t dispose(Space& home);
192  };
193 
195  template<class V0, class V1>
196  ExecStatus post_int(Home home, IntSharedArray& c, V0 x0, V1 x1);
197 
198 
203  template<class ViewB> class IdxView;
204 
206  template<class View>
207  class ViewToVarArg {};
208 
213  template<class View>
214  class IdxViewArray {
215  private:
217  IdxView<View>* xs;
219  int n;
220  public:
222  IdxViewArray(void);
226  IdxViewArray(Space& home, const typename ViewToVarArg<View>::argtype& x);
228  IdxViewArray(Space& home, int n);
229 
231  int size(void) const;
233  void size(int n);
234 
238  const IdxView<View>& operator [](int) const;
239 
244  void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
249  void cancel(Space& home, Propagator& p, PropCond pc);
250 
252  void update(Space& home, bool share, IdxViewArray<View>& x);
253  };
254 
259  template<class VA, class VB, class VC, PropCond pc_ac>
260  class View : public Propagator {
261  protected:
265  VB x0;
267  VC x1;
269  View(Space& home, bool share, View& p);
271  View(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
272  public:
273  // Cost function (defined as low linear)
274  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
276  virtual size_t dispose(Space& home);
277  };
278 
279 
286  template<class VA, class VB, class VC>
287  class ViewBnd : public View<VA,VB,VC,PC_INT_BND> {
288  protected:
292 
294  ViewBnd(Space& home, bool share, ViewBnd& p);
296  ViewBnd(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
297  public:
299  virtual Actor* copy(Space& home, bool share);
301  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
303  static ExecStatus post(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
304  };
305 
316  template<class VA, class VB, class VC>
317  class ViewDom : public View<VA,VB,VC,PC_INT_DOM> {
318  protected:
322 
324  ViewDom(Space& home, bool share, ViewDom& p);
326  ViewDom(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
327  public:
329  virtual Actor* copy(Space& home, bool share);
337  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
339  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
341  static ExecStatus post(Home home, IdxViewArray<VA>& iv,
342  VB x0, VC x1);
343  };
344 
353  : public TernaryPropagator<IntView,PC_INT_DOM> {
354  protected:
359  int w;
361  Pair(Space& home, bool share, Pair& p);
362  public:
364  Pair(Home home, IntView x0, IntView x1, IntView x2, int w);
366  static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2,
367  int w, int h);
369  GECODE_INT_EXPORT virtual Actor* copy(Space& home, bool share);
371  GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
372  };
373 
374 }}}
375 
379 
380 #endif
381 
382 
383 // STATISTICS: int-prop
384 
Domain consistent element propagator for array of views.
Definition: element.hh:317
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:104
int size(void) const
Return the current size.
Definition: view.hpp:107
IdxVal * iv
The index-value data structure.
Definition: element.hh:169
bool marked(void) const
Return whether this pair is marked for removal.
Definition: int.hpp:49
IdxView< View > & operator [](int n)
Access element n.
Definition: view.hpp:119
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
IdxSize s0
Size of x0 at last execution.
Definition: element.hh:159
Value iterator for values in index-value map.
Definition: element.hh:107
View(Space &home, bool share, View &p)
Constructor for cloning p.
Definition: view.hpp:240
Linked index-value pairs.
Definition: element.hh:70
Idx val(void) const
Return index of current index value pair.
Definition: int.hpp:81
VC x1
View for result.
Definition: element.hh:267
void operator++(void)
Move to next index value pair (next value)
Definition: int.hpp:128
IterValUnmark(IdxVal *iv)
Initialize with start.
Definition: int.hpp:113
Int(Space &home, bool shared, Int &p)
Constructor for cloning p.
Definition: int.hpp:195
IterVal(IdxVal *iv)
Initialize with start.
Definition: int.hpp:90
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: view.hpp:133
const IdxVal * iv
Index-value pairs.
Definition: element.hh:146
Base-class for propagators.
Definition: core.hpp:755
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:67
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:394
ValSize s1
Size of x1 at last execution.
Definition: element.hh:165
V1 x1
View for result.
Definition: element.hh:161
Value iterator for indices in index-value map.
Definition: element.hh:87
IntSharedArray c
Shared array of integer values.
Definition: element.hh:167
Computation spaces.
Definition: core.hpp:1325
Base-class for both propagators and branchers.
Definition: core.hpp:666
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:94
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: int.hpp:204
void update(Space &home, bool share, IdxViewArray< View > &x)
Cloning.
Definition: view.hpp:148
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: view.hpp:498
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void cancel(Space &home, Propagator &p, PropCond pc)
Definition: view.hpp:141
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for value size.
Definition: element.hh:163
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:476
IdxViewArray< VA > iv
Current index-view map.
Definition: element.hh:263
Val val
The value Mark that this pair should be removed.
Definition: element.hh:75
Value iterator for values in index-value map.
Definition: element.hh:129
Idx idx_next
The position of the next pair in index order.
Definition: element.hh:72
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
void prune_val(void)
Prune values according to x1.
Definition: int.hpp:242
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
Ternary propagator.
Definition: propagator.hpp:115
Gecode::Support::IntTypeTraits< Idx >::utype IdxSize
Type for index size.
Definition: element.hh:157
V0 x0
View for index.
Definition: element.hh:155
static ExecStatus post(Home home, IntSharedArray &i, V0 x0, V1 x1)
Post propagator for .
Definition: int.hpp:182
Base-class for element propagator for array of views.
Definition: element.hh:260
void operator++(void)
Move to next index value pair (next index)
Definition: int.hpp:72
Traits to for information about integer types.
Definition: int-type.hpp:56
ByVal(const IdxVal *iv)
Initialize with index value pairs.
Definition: int.hpp:147
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: view.hpp:416
VB x0
View for index.
Definition: element.hh:265
Integer view for integer variables.
Definition: view.hpp:129
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Const function (defined as high binary)
Definition: int.hpp:210
Domain consistent pair propagator.
Definition: element.hh:352
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:422
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: view.hpp:258
ViewBnd(Space &home, bool share, ViewBnd &p)
Constructor for cloning p.
Definition: view.hpp:411
Class for pair of index and view.
Definition: view.hpp:64
Propagation cost.
Definition: core.hpp:537
An array of IndexView pairs.
Definition: element.hh:214
ExecStatus
Definition: core.hpp:523
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int.hpp:171
ViewDom(Space &home, bool share, ViewDom &p)
Constructor for cloning p.
Definition: view.hpp:493
Class to get VarArg type for view.
Definition: element.hh:207
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:137
ExecStatus post_int(Home home, IntSharedArray &c, V0 x0, V1 x1)
Post propagator with apropriate index and value types.
Definition: int.hpp:403
void prune_idx(void)
Prune index according to x0.
Definition: int.hpp:220
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:505
void operator++(void)
Move to next index value pair (next value)
Definition: int.hpp:99
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:662
IterIdxUnmark(IdxVal *iv)
Initialize with start.
Definition: int.hpp:57
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:123
IdxViewArray(void)
Default constructor.
Definition: view.hpp:78
Idx val_next
The position of the next pair in value order.
Definition: element.hh:73
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:512
Sorting pointers to (index,value) pairs in value order.
Definition: element.hh:144
#define GECODE_INT_EXPORT
Definition: int.hh:76
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:249
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Element propagator for array of integers
Definition: element.hh:60
Home class for posting propagators
Definition: core.hpp:717
static ExecStatus assigned_val(Space &home, IntSharedArray &c, V0 x0, V1 x1)
Prune when x1 is assigned.
Definition: int.hpp:265
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int.hpp:280
Bounds consistent element propagator for array of views.
Definition: element.hh:287
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition: int.hpp:151