Generated on Fri Jul 13 2018 06:08:27 for Gecode by doxygen 1.8.14
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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
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 #include <gecode/int/idx-view.hh>
46 
52 namespace Gecode { namespace Int { namespace Element {
53 
60  template<class V0, class V1, class Idx, class Val>
61  class Int : public Propagator {
62  protected:
71  class IdxVal {
72  public:
73  Idx idx_next;
74  Idx val_next;
75  Idx idx;
76  Val val;
77  void mark(void);
80  bool marked(void) const;
81  };
88  class IterIdxUnmark {
89  private:
90  IdxVal* iv;
91  Idx i;
92  public:
94  IterIdxUnmark(IdxVal* iv);
96  bool operator ()(void) const;
98  void operator ++(void);
100  Idx val(void) const;
101  };
108  class IterVal {
109  private:
110  IdxVal* iv;
111  Idx i;
112  public:
114  IterVal(IdxVal* iv);
116  bool operator ()(void) const;
118  void operator ++(void);
120  Val val(void) const;
121  };
131  private:
132  IdxVal* iv;
133  Idx i;
134  public:
136  IterValUnmark(IdxVal* iv);
138  bool operator ()(void) const;
140  void operator ++(void);
142  Val val(void) const;
143  };
145  class ByVal {
146  protected:
147  const IdxVal* iv;
148  public:
150  ByVal(const IdxVal* iv);
152  bool operator ()(Idx& i, Idx& j);
153  };
154 
156  V0 x0;
162  V1 x1;
172  void prune_idx(void);
174  void prune_val(void);
177  V0 x0, V1 x1);
179  Int(Space& home, bool shared, Int& p);
181  Int(Home home, IntSharedArray& i, V0 x0, V1 x1);
182  public:
184  virtual Actor* copy(Space& home, bool share);
186  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
188  virtual void reschedule(Space& home);
190  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
192  static ExecStatus post(Home home, IntSharedArray& i, V0 x0, V1 x1);
194  virtual size_t dispose(Space& home);
195  };
196 
198  template<class V0, class V1>
199  ExecStatus post_int(Home home, IntSharedArray& c, V0 x0, V1 x1);
200 
201 
206  template<class VA, class VB, class VC, PropCond pc_ac>
207  class View : public Propagator {
208  protected:
212  VB x0;
214  VC x1;
216  View(Space& home, bool share, View& p);
218  View(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
219  public:
220  // Cost function (defined as low linear)
221  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
223  virtual void reschedule(Space& home);
225  virtual size_t dispose(Space& home);
226  };
227 
228 
235  template<class VA, class VB, class VC>
236  class ViewBnd : public View<VA,VB,VC,PC_INT_BND> {
237  protected:
241 
243  ViewBnd(Space& home, bool share, ViewBnd& p);
245  ViewBnd(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
246  public:
248  virtual Actor* copy(Space& home, bool share);
250  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
252  static ExecStatus post(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
253  };
254 
265  template<class VA, class VB, class VC>
266  class ViewDom : public View<VA,VB,VC,PC_INT_DOM> {
267  protected:
271 
273  ViewDom(Space& home, bool share, ViewDom& p);
275  ViewDom(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
276  public:
278  virtual Actor* copy(Space& home, bool share);
286  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
288  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
290  static ExecStatus post(Home home, IdxViewArray<VA>& iv,
291  VB x0, VC x1);
292  };
293 
302  : public TernaryPropagator<IntView,PC_INT_DOM> {
303  protected:
308  int w;
310  Pair(Space& home, bool share, Pair& p);
311  public:
313  Pair(Home home, IntView x0, IntView x1, IntView x2, int w);
315  static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2,
316  int w, int h);
318  GECODE_INT_EXPORT virtual Actor* copy(Space& home, bool share);
320  GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
321  };
322 
323 }}}
324 
328 
329 #endif
330 
331 
332 // STATISTICS: int-prop
333 
Domain consistent element propagator for array of views.
Definition: element.hh:266
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:104
IdxVal * iv
The index-value data structure.
Definition: element.hh:170
bool marked(void) const
Return whether this pair is marked for removal.
Definition: int.hpp:49
IdxSize s0
Size of x0 at last execution.
Definition: element.hh:160
Value iterator for values in index-value map.
Definition: element.hh:108
View(Space &home, bool share, View &p)
Constructor for cloning p.
Definition: view.hpp:126
Linked index-value pairs.
Definition: element.hh:71
Idx val(void) const
Return index of current index value pair.
Definition: int.hpp:81
VC x1
View for result.
Definition: element.hh:214
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
virtual void reschedule(Space &home)
Schedule function.
Definition: int.hpp:220
const IdxVal * iv
Index-value pairs.
Definition: element.hh:147
Base-class for propagators.
Definition: core.hpp:1092
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:288
ValSize s1
Size of x1 at last execution.
Definition: element.hh:166
V1 x1
View for result.
Definition: element.hh:162
Value iterator for indices in index-value map.
Definition: element.hh:88
IntSharedArray c
Shared array of integer values.
Definition: element.hh:168
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
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
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: view.hpp:392
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)
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for value size.
Definition: element.hh:164
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:370
IdxViewArray< VA > iv
Current index-view map.
Definition: element.hh:210
Val val
The value Mark that this pair should be removed.
Definition: element.hh:76
Value iterator for values in index-value map.
Definition: element.hh:130
Idx idx_next
The position of the next pair in index order.
Definition: element.hh:73
void prune_val(void)
Prune values according to x1.
Definition: int.hpp:249
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1103
Ternary propagator.
Definition: propagator.hpp:119
Gecode::Support::IntTypeTraits< Idx >::utype IdxSize
Type for index size.
Definition: element.hh:158
V0 x0
View for index.
Definition: element.hh:156
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:207
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 void reschedule(Space &home)
Schedule function.
Definition: view.hpp:144
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: view.hpp:310
VB x0
View for index.
Definition: element.hh:212
Integer view for integer variables.
Definition: view.hpp:129
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high binary)
Definition: int.hpp:210
Domain consistent pair propagator.
Definition: element.hh:301
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:316
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: view.hpp:152
ViewBnd(Space &home, bool share, ViewBnd &p)
Constructor for cloning p.
Definition: view.hpp:305
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
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:387
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:410
void prune_idx(void)
Prune index according to x0.
Definition: int.hpp:227
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:399
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:702
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
Idx val_next
The position of the next pair in value order.
Definition: element.hh:74
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:406
Sorting pointers to (index,value) pairs in value order.
Definition: element.hh:145
#define GECODE_INT_EXPORT
Definition: int.hh:81
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:135
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Element propagator for array of integers
Definition: element.hh:61
Home class for posting propagators
Definition: core.hpp:922
static ExecStatus assigned_val(Space &home, IntSharedArray &c, V0 x0, V1 x1)
Prune when x1 is assigned.
Definition: int.hpp:272
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int.hpp:287
Bounds consistent element propagator for array of views.
Definition: element.hh:236
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition: int.hpp:151