Generated on Sat Feb 7 2015 02:01:22 for Gecode by doxygen 1.8.9.1
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: 2015-01-16 14:10:48 +0100 (Fri, 16 Jan 2015) $ by $Author: schulte $
13  * $Revision: 14362 $
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;
160  IdxSize s0;
162  V1 x1;
166  ValSize s1;
172  void prune_idx(void);
174  void prune_val(void);
176  static ExecStatus assigned_val(Space& home, IntSharedArray& c,
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 ExecStatus propagate(Space& home, const ModEventDelta& med);
190  static ExecStatus post(Home home, IntSharedArray& i, V0 x0, V1 x1);
192  virtual size_t dispose(Space& home);
193  };
194 
196  template<class V0, class V1>
197  ExecStatus post_int(Home home, IntSharedArray& c, V0 x0, V1 x1);
198 
199 
204  template<class VA, class VB, class VC, PropCond pc_ac>
205  class View : public Propagator {
206  protected:
210  VB x0;
212  VC x1;
214  View(Space& home, bool share, View& p);
216  View(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
217  public:
218  // Cost function (defined as low linear)
219  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
221  virtual size_t dispose(Space& home);
222  };
223 
224 
231  template<class VA, class VB, class VC>
232  class ViewBnd : public View<VA,VB,VC,PC_INT_BND> {
233  protected:
237 
239  ViewBnd(Space& home, bool share, ViewBnd& p);
241  ViewBnd(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
242  public:
244  virtual Actor* copy(Space& home, bool share);
246  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
248  static ExecStatus post(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
249  };
250 
261  template<class VA, class VB, class VC>
262  class ViewDom : public View<VA,VB,VC,PC_INT_DOM> {
263  protected:
267 
269  ViewDom(Space& home, bool share, ViewDom& p);
271  ViewDom(Home home, IdxViewArray<VA>& iv, VB x0, VC x1);
272  public:
274  virtual Actor* copy(Space& home, bool share);
282  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
284  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
286  static ExecStatus post(Home home, IdxViewArray<VA>& iv,
287  VB x0, VC x1);
288  };
289 
298  : public TernaryPropagator<IntView,PC_INT_DOM> {
299  protected:
304  int w;
306  Pair(Space& home, bool share, Pair& p);
307  public:
309  Pair(Home home, IntView x0, IntView x1, IntView x2, int w);
311  static ExecStatus post(Home home, IntView x0, IntView x1, IntView x2,
312  int w, int h);
314  GECODE_INT_EXPORT virtual Actor* copy(Space& home, bool share);
316  GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
317  };
318 
319 }}}
320 
324 
325 #endif
326 
327 
328 // STATISTICS: int-prop
329 
Domain consistent element propagator for array of views.
Definition: element.hh:262
IdxVal * iv
The index-value data structure.
Definition: element.hh:170
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
Idx val(void) const
Return index of current index value pair.
Definition: int.hpp:81
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
VC x1
View for result.
Definition: element.hh:212
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
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:137
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
const IdxVal * iv
Index-value pairs.
Definition: element.hh:147
Base-class for propagators.
Definition: core.hpp:755
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition: view.hpp:280
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:123
ValSize s1
Size of x1 at last execution.
Definition: element.hh:166
V1 x1
View for result.
Definition: element.hh:162
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:104
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:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: int.hpp:204
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:135
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: view.hpp:384
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)
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Const function (defined as high binary)
Definition: int.hpp:210
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:362
IdxViewArray< VA > iv
Current index-view map.
Definition: element.hh:208
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
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:67
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: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:205
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:302
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:94
VB x0
View for index.
Definition: element.hh:210
Integer view for integer variables.
Definition: view.hpp:129
Domain consistent pair propagator.
Definition: element.hh:297
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:308
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: view.hpp:144
ViewBnd(Space &home, bool share, ViewBnd &p)
Constructor for cloning p.
Definition: view.hpp:297
Propagation cost.
Definition: core.hpp:537
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:379
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
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
Idx val_next
The position of the next pair in value order.
Definition: element.hh:74
bool marked(void) const
Return whether this pair is marked for removal.
Definition: int.hpp:49
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: view.hpp:398
Sorting pointers to (index,value) pairs in value order.
Definition: element.hh:145
#define GECODE_INT_EXPORT
Definition: int.hh:78
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: view.hpp:391
Element propagator for array of integers
Definition: element.hh:61
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:232
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition: int.hpp:151