Generated on Sat Feb 7 2015 02:01:22 for Gecode by doxygen 1.8.9.1
int.hpp
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, 2004
8  *
9  * Last modified:
10  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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 namespace Gecode { namespace Int { namespace Element {
39 
40 
41  // Index value pairs
42  template<class V0, class V1, class Idx, class Val>
43  forceinline void
45  idx = -1;
46  }
47  template<class V0, class V1, class Idx, class Val>
48  forceinline bool
50  return idx<0;
51  }
52 
53 
54  // Index iterator
55  template<class V0, class V1, class Idx, class Val>
58  : iv(iv0) {
59  Idx p=0;
60  i = iv[p].idx_next;
61  while ((i != 0) && iv[i].marked())
62  i=iv[i].idx_next;
63  iv[p].idx_next=i;
64  }
65  template<class V0, class V1, class Idx, class Val>
66  forceinline bool
68  return i != 0;
69  }
70  template<class V0, class V1, class Idx, class Val>
71  forceinline void
73  int p=i;
74  i = iv[p].idx_next;
75  while ((i != 0) && iv[i].marked())
76  i=iv[i].idx_next;
77  iv[p].idx_next=i;
78  }
79  template<class V0, class V1, class Idx, class Val>
80  forceinline Idx
82  assert(!iv[i].marked());
83  return iv[i].idx;
84  }
85 
86 
87 
88  template<class V0, class V1, class Idx, class Val>
91  : iv(iv0), i(iv[0].val_next) {}
92  template<class V0, class V1, class Idx, class Val>
93  forceinline bool
95  return i != 0;
96  }
97  template<class V0, class V1, class Idx, class Val>
98  forceinline void
100  i=iv[i].val_next;
101  }
102  template<class V0, class V1, class Idx, class Val>
103  forceinline Val
105  assert(!iv[i].marked());
106  return iv[i].val;
107  }
108 
109 
110 
111  template<class V0, class V1, class Idx, class Val>
114  : iv(iv0) {
115  Idx p=0;
116  i = iv[p].val_next;
117  while ((i != 0) && iv[i].marked())
118  i=iv[i].val_next;
119  iv[p].val_next=i;
120  }
121  template<class V0, class V1, class Idx, class Val>
122  forceinline bool
124  return i != 0;
125  }
126  template<class V0, class V1, class Idx, class Val>
127  forceinline void
129  int p=i;
130  i = iv[p].val_next;
131  while ((i != 0) && iv[i].marked())
132  i=iv[i].val_next;
133  iv[p].val_next=i;
134  }
135  template<class V0, class V1, class Idx, class Val>
136  forceinline Val
138  assert(!iv[i].marked());
139  return iv[i].val;
140  }
141 
142 
143 
144  // Sort function
145  template<class V0, class V1, class Idx, class Val>
148  : iv(iv0) {}
149  template<class V0, class V1, class Idx, class Val>
150  forceinline bool
152  return iv[i].val < iv[j].val;
153  }
154 
155 
156  /*
157  * Element propagator proper
158  *
159  */
160  template<class V0, class V1, class Idx, class Val>
162  Int<V0,V1,Idx,Val>::Int(Home home, IntSharedArray& c0, V0 y0, V1 y1)
163  : Propagator(home), x0(y0), s0(0), x1(y1), s1(0), c(c0), iv(NULL) {
164  home.notice(*this,AP_DISPOSE);
165  x0.subscribe(home,*this,PC_INT_DOM);
166  x1.subscribe(home,*this,PC_INT_DOM);
167  }
168 
169  template<class V0, class V1, class Idx, class Val>
170  forceinline size_t
172  home.ignore(*this,AP_DISPOSE);
173  x0.cancel(home,*this,PC_INT_DOM);
174  x1.cancel(home,*this,PC_INT_DOM);
175  c.~IntSharedArray();
176  (void) Propagator::dispose(home);
177  return sizeof(*this);
178  }
179 
180  template<class V0, class V1, class Idx, class Val>
181  ExecStatus
183  if (x0.assigned()) {
184  GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
185  } else if (x1.assigned()) {
186  GECODE_ES_CHECK(assigned_val(home,c,x0,x1));
187  } else {
188  (void) new (home) Int<V0,V1,Idx,Val>(home,c,x0,x1);
189  }
190  return ES_OK;
191  }
192 
193  template<class V0, class V1, class Idx, class Val>
195  Int<V0,V1,Idx,Val>::Int(Space& home, bool share, Int& p)
196  : Propagator(home,share,p), s0(0), s1(0), iv(NULL) {
197  c.update(home,share,p.c);
198  x0.update(home,share,p.x0);
199  x1.update(home,share,p.x1);
200  }
201 
202  template<class V0, class V1, class Idx, class Val>
203  Actor*
204  Int<V0,V1,Idx,Val>::copy(Space& home, bool share) {
205  return new (home) Int<V0,V1,Idx,Val>(home,share,*this);
206  }
207 
208  template<class V0, class V1, class Idx, class Val>
209  PropCost
210  Int<V0,V1,Idx,Val>::cost(const Space&, const ModEventDelta& med) const {
211  if ((V0::me(med) == ME_INT_VAL) ||
212  (V1::me(med) == ME_INT_VAL))
214  else
216  }
217 
218  template<class V0, class V1, class Idx, class Val>
219  void
221  Idx p = 0;
222  Idx i = iv[p].idx_next;
223  ViewRanges<V0> v(x0);
224  while (v() && (i != 0)) {
225  assert(!iv[i].marked());
226  if (iv[i].idx < v.min()) {
227  iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
228  } else if (iv[i].idx > v.max()) {
229  ++v;
230  } else {
231  p=i; i=iv[i].idx_next;
232  }
233  }
234  iv[p].idx_next = 0;
235  while (i != 0) {
236  iv[i].mark(); i=iv[i].idx_next;
237  }
238  }
239 
240  template<class V0, class V1, class Idx, class Val>
241  void
243  Idx p = 0;
244  Idx i = iv[p].val_next;
245  ViewRanges<V1> v(x1);
246  while (v() && (i != 0)) {
247  if (iv[i].marked()) {
248  i=iv[i].val_next; iv[p].val_next=i;
249  } else if (iv[i].val < v.min()) {
250  iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
251  } else if (iv[i].val > v.max()) {
252  ++v;
253  } else {
254  p=i; i=iv[i].val_next;
255  }
256  }
257  iv[p].val_next = 0;
258  while (i != 0) {
259  iv[i].mark(); i=iv[i].val_next;
260  }
261  }
262 
263  template<class V0, class V1, class Idx, class Val>
264  ExecStatus
266  V0 x0, V1 x1) {
267  Region r(home);
268  int* v = r.alloc<int>(x0.size());
269  int n = 0;
270  for (ViewValues<V0> i(x0); i(); ++i)
271  if (c[i.val()] != x1.val())
272  v[n++]=i.val();
273  Iter::Values::Array iv(v,n);
274  GECODE_ME_CHECK(x0.minus_v(home,iv,false));
275  return ES_OK;
276  }
277 
278  template<class V0, class V1, class Idx, class Val>
279  ExecStatus
281  if (x0.assigned()) {
282  GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
283  return home.ES_SUBSUMED(*this);
284  }
285 
286  if (x1.assigned() && (iv == NULL)) {
287  GECODE_ES_CHECK(assigned_val(home,c,x0,x1));
288  return home.ES_SUBSUMED(*this);
289  }
290 
291  if ((static_cast<ValSize>(x1.size()) == s1) &&
292  (static_cast<IdxSize>(x0.size()) != s0)) {
293  assert(iv != NULL);
294  assert(!shared(x0,x1));
295 
296  prune_idx();
297 
298  IterValUnmark v(iv);
299  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
300 
301  s1=static_cast<ValSize>(x1.size());
302 
303  assert(!x0.assigned());
304  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
305  }
306 
307  if ((static_cast<IdxSize>(x0.size()) == s0) &&
308  (static_cast<ValSize>(x1.size()) != s1)) {
309  assert(iv != NULL);
310  assert(!shared(x0,x1));
311 
312  prune_val();
313 
314  IterIdxUnmark i(iv);
315  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
316 
317  s0=static_cast<IdxSize>(x0.size());
318 
319  return (x0.assigned() || x1.assigned()) ?
320  home.ES_SUBSUMED(*this) : ES_FIX;
321  }
322 
323  bool assigned = x0.assigned() && x1.assigned();
324  if (iv == NULL) {
325  // Initialize data structure
326  iv = home.alloc<IdxVal>(x0.size() + 1);
327 
328  // The first element in iv[0] is used as sentinel
329  // Enter information sorted by idx
330  IdxVal* by_idx = &iv[1];
331  Idx size = 0;
332  for (ViewValues<V0> v(x0); v(); ++v)
333  if ((x1.min() <= c[v.val()]) && (x1.max() >= c[v.val()])) {
334  by_idx[size].idx = static_cast<Idx>(v.val());
335  by_idx[size].val = static_cast<Val>(c[v.val()]);
336  size++;
337  }
338  if (size == 0)
339  return ES_FAILED;
340  // Create val links sorted by val
341  Region r(home);
342  Idx* by_val = r.alloc<Idx>(size);
343  if (x1.width() <= 128) {
344  int n_buckets = static_cast<int>(x1.width());
345  int* pos = r.alloc<int>(n_buckets);
346  int* buckets = pos - x1.min();
347  for (int i=n_buckets; i--; )
348  pos[i]=0;
349  for (Idx i=size; i--; )
350  buckets[by_idx[i].val]++;
351  int p=0;
352  for (int i=0; i<n_buckets; i++) {
353  int n=pos[i]; pos[i]=p; p+=n;
354  }
355  assert(p == size);
356  for (Idx i=size; i--; )
357  by_val[buckets[by_idx[i].val]++] = i+1;
358  } else {
359  for (Idx i = size; i--; )
360  by_val[i] = i+1;
361  ByVal less(iv);
362  Support::quicksort<Idx>(by_val,size,less);
363  }
364  // Create val links
365  for (Idx i = size-1; i--; ) {
366  by_idx[i].idx_next = i+2;
367  iv[by_val[i]].val_next = by_val[i+1];
368  }
369  by_idx[size-1].idx_next = 0;
370  iv[by_val[size-1]].val_next = 0;
371  // Set up sentinel element: iv[0]
372  iv[0].idx_next = 1;
373  iv[0].val_next = by_val[0];
374  } else {
375  prune_idx();
376  }
377 
378  // Prune values
379  prune_val();
380 
381  // Peform tell
382  {
383  IterIdxUnmark i(iv);
384  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
385  IterVal v(iv);
386  if (shared(x0,x1)) {
387  GECODE_ME_CHECK(x1.inter_v(home,v,false));
388  s0=static_cast<IdxSize>(x0.size());
389  s1=static_cast<ValSize>(x1.size());
390  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
391  } else {
392  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
393  s0=static_cast<IdxSize>(x0.size());
394  s1=static_cast<ValSize>(x1.size());
395  return (x0.assigned() || x1.assigned()) ?
396  home.ES_SUBSUMED(*this) : ES_FIX;
397  }
398  }
399  }
400 
401  template<class V0, class V1>
403  post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
404  assert(c.size() > 0);
405  GECODE_ME_CHECK(x0.gq(home,0));
406  GECODE_ME_CHECK(x0.le(home,c.size()));
407  Support::IntType idx_type = Support::s_type(c.size());
408  int min = c[0];
409  int max = c[0];
410  for (int i=1; i<c.size(); i++) {
411  min = std::min(c[i],min); max = std::max(c[i],max);
412  }
413  GECODE_ME_CHECK(x1.gq(home,min));
414  GECODE_ME_CHECK(x1.lq(home,max));
415  Support::IntType val_type =
417  switch (idx_type) {
418  case Support::IT_CHAR:
419  switch (val_type) {
420  case Support::IT_CHAR:
421  return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
422  case Support::IT_SHRT:
424  default: break;
425  }
426  break;
427  case Support::IT_SHRT:
428  switch (val_type) {
429  case Support::IT_CHAR:
430  case Support::IT_SHRT:
432  default: break;
433  }
434  break;
435  default: break;
436  }
437  return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
438  }
439 
440 }}}
441 
442 // STATISTICS: int-prop
443 
bool marked(void *p)
Check whether p is marked.
IdxVal * iv
The index-value data structure.
Definition: element.hh:170
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
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
Linked index-value pairs.
Definition: element.hh:71
Actor must always be disposed.
Definition: core.hpp:610
void operator++(void)
Move to next index value pair (next value)
Definition: int.hpp:128
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
IterValUnmark(IdxVal *iv)
Initialize with start.
Definition: int.hpp:113
Value iterator for array of integers
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
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
IterVal(IdxVal *iv)
Initialize with start.
Definition: int.hpp:90
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
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
Handle to region.
Definition: region.hpp:61
Value iterator for integer views.
Definition: view.hpp:94
Propagation has computed fixpoint.
Definition: core.hpp:528
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4058
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
Range iterator for integer views.
Definition: view.hpp:54
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: int.hpp:204
IntType s_type(signed int n)
Return type required to represent n.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
char integer type
Definition: int-type.hpp:44
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
int min(void) const
Return smallest value of range.
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
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for value size.
Definition: element.hh:164
Val val
The value Mark that this pair should be removed.
Definition: element.hh:76
Execution has resulted in failure.
Definition: core.hpp:525
Value iterator for values in index-value map.
Definition: element.hh:130
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
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
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
void prune_val(void)
Prune values according to x1.
Definition: int.hpp:242
unsigned int size(I &i)
Size of all ranges of range iterator i.
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
int size(void) const
Return number of elements.
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
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
void operator++(void)
Move to next index value pair (next index)
Definition: int.hpp:72
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
ByVal(const IdxVal *iv)
Initialize with index value pairs.
Definition: int.hpp:147
const int v[7]
Definition: distinct.cpp:207
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:94
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:2656
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:169
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
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
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
Execution is okay.
Definition: core.hpp:527
ExecStatus post_int(Home home, IntSharedArray &c, V0 x0, V1 x1)
Post propagator with apropriate index and value types.
Definition: int.hpp:403
Propagation has not computed fixpoint.
Definition: core.hpp:526
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
int max(void) const
Return largest value of range.
bool marked(void) const
Return whether this pair is marked for removal.
Definition: int.hpp:49
Gecode toplevel namespace
Sorting pointers to (index,value) pairs in value order.
Definition: element.hh:145
IntType
Description of integer types.
Definition: int-type.hpp:43
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
short integer type
Definition: int-type.hpp:45
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
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4054
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int.hpp:280
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition: int.hpp:151