Generated on Sat Jul 28 2018 17:14:36 for Gecode by doxygen 1.8.14
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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
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  x0.reschedule(home,*this,PC_INT_DOM);
222  x1.reschedule(home,*this,PC_INT_DOM);
223  }
224 
225  template<class V0, class V1, class Idx, class Val>
226  void
228  Idx p = 0;
229  Idx i = iv[p].idx_next;
230  ViewRanges<V0> v(x0);
231  while (v() && (i != 0)) {
232  assert(!iv[i].marked());
233  if (iv[i].idx < v.min()) {
234  iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
235  } else if (iv[i].idx > v.max()) {
236  ++v;
237  } else {
238  p=i; i=iv[i].idx_next;
239  }
240  }
241  iv[p].idx_next = 0;
242  while (i != 0) {
243  iv[i].mark(); i=iv[i].idx_next;
244  }
245  }
246 
247  template<class V0, class V1, class Idx, class Val>
248  void
250  Idx p = 0;
251  Idx i = iv[p].val_next;
252  ViewRanges<V1> v(x1);
253  while (v() && (i != 0)) {
254  if (iv[i].marked()) {
255  i=iv[i].val_next; iv[p].val_next=i;
256  } else if (iv[i].val < v.min()) {
257  iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
258  } else if (iv[i].val > v.max()) {
259  ++v;
260  } else {
261  p=i; i=iv[i].val_next;
262  }
263  }
264  iv[p].val_next = 0;
265  while (i != 0) {
266  iv[i].mark(); i=iv[i].val_next;
267  }
268  }
269 
270  template<class V0, class V1, class Idx, class Val>
271  ExecStatus
273  V0 x0, V1 x1) {
274  Region r(home);
275  int* v = r.alloc<int>(x0.size());
276  int n = 0;
277  for (ViewValues<V0> i(x0); i(); ++i)
278  if (c[i.val()] != x1.val())
279  v[n++]=i.val();
280  Iter::Values::Array iv(v,n);
281  GECODE_ME_CHECK(x0.minus_v(home,iv,false));
282  return ES_OK;
283  }
284 
285  template<class V0, class V1, class Idx, class Val>
286  ExecStatus
288  if (x0.assigned()) {
289  GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
290  return home.ES_SUBSUMED(*this);
291  }
292 
293  if (x1.assigned() && (iv == NULL)) {
294  GECODE_ES_CHECK(assigned_val(home,c,x0,x1));
295  return home.ES_SUBSUMED(*this);
296  }
297 
298  if ((static_cast<ValSize>(x1.size()) == s1) &&
299  (static_cast<IdxSize>(x0.size()) != s0)) {
300  assert(iv != NULL);
301  assert(!shared(x0,x1));
302 
303  prune_idx();
304 
305  IterValUnmark v(iv);
306  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
307 
308  s1=static_cast<ValSize>(x1.size());
309 
310  assert(!x0.assigned());
311  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
312  }
313 
314  if ((static_cast<IdxSize>(x0.size()) == s0) &&
315  (static_cast<ValSize>(x1.size()) != s1)) {
316  assert(iv != NULL);
317  assert(!shared(x0,x1));
318 
319  prune_val();
320 
321  IterIdxUnmark i(iv);
322  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
323 
324  s0=static_cast<IdxSize>(x0.size());
325 
326  return (x0.assigned() || x1.assigned()) ?
327  home.ES_SUBSUMED(*this) : ES_FIX;
328  }
329 
330  bool assigned = x0.assigned() && x1.assigned();
331  if (iv == NULL) {
332  // Initialize data structure
333  iv = home.alloc<IdxVal>(x0.size() + 1);
334 
335  // The first element in iv[0] is used as sentinel
336  // Enter information sorted by idx
337  IdxVal* by_idx = &iv[1];
338  Idx size = 0;
339  for (ViewValues<V0> v(x0); v(); ++v)
340  if ((x1.min() <= c[v.val()]) && (x1.max() >= c[v.val()])) {
341  by_idx[size].idx = static_cast<Idx>(v.val());
342  by_idx[size].val = static_cast<Val>(c[v.val()]);
343  size++;
344  }
345  if (size == 0)
346  return ES_FAILED;
347  // Create val links sorted by val
348  Region r(home);
349  Idx* by_val = r.alloc<Idx>(size);
350  if (x1.width() <= 128) {
351  int n_buckets = static_cast<int>(x1.width());
352  int* pos = r.alloc<int>(n_buckets);
353  int* buckets = pos - x1.min();
354  for (int i=n_buckets; i--; )
355  pos[i]=0;
356  for (Idx i=size; i--; )
357  buckets[by_idx[i].val]++;
358  int p=0;
359  for (int i=0; i<n_buckets; i++) {
360  int n=pos[i]; pos[i]=p; p+=n;
361  }
362  assert(p == size);
363  for (Idx i=size; i--; )
364  by_val[buckets[by_idx[i].val]++] = i+1;
365  } else {
366  for (Idx i = size; i--; )
367  by_val[i] = i+1;
368  ByVal less(iv);
369  Support::quicksort<Idx>(by_val,size,less);
370  }
371  // Create val links
372  for (Idx i = size-1; i--; ) {
373  by_idx[i].idx_next = i+2;
374  iv[by_val[i]].val_next = by_val[i+1];
375  }
376  by_idx[size-1].idx_next = 0;
377  iv[by_val[size-1]].val_next = 0;
378  // Set up sentinel element: iv[0]
379  iv[0].idx_next = 1;
380  iv[0].val_next = by_val[0];
381  } else {
382  prune_idx();
383  }
384 
385  // Prune values
386  prune_val();
387 
388  // Peform tell
389  {
390  IterIdxUnmark i(iv);
391  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
392  IterVal v(iv);
393  if (shared(x0,x1)) {
394  GECODE_ME_CHECK(x1.inter_v(home,v,false));
395  s0=static_cast<IdxSize>(x0.size());
396  s1=static_cast<ValSize>(x1.size());
397  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
398  } else {
399  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
400  s0=static_cast<IdxSize>(x0.size());
401  s1=static_cast<ValSize>(x1.size());
402  return (x0.assigned() || x1.assigned()) ?
403  home.ES_SUBSUMED(*this) : ES_FIX;
404  }
405  }
406  }
407 
408  template<class V0, class V1>
410  post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
411  assert(c.size() > 0);
412  GECODE_ME_CHECK(x0.gq(home,0));
413  GECODE_ME_CHECK(x0.le(home,c.size()));
414  Support::IntType idx_type = Support::s_type(c.size());
415  int min = c[0];
416  int max = c[0];
417  for (int i=1; i<c.size(); i++) {
418  min = std::min(c[i],min); max = std::max(c[i],max);
419  }
420  GECODE_ME_CHECK(x1.gq(home,min));
421  GECODE_ME_CHECK(x1.lq(home,max));
422  Support::IntType val_type =
424  switch (idx_type) {
425  case Support::IT_CHAR:
426  switch (val_type) {
427  case Support::IT_CHAR:
428  return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
429  case Support::IT_SHRT:
431  default: break;
432  }
433  break;
434  case Support::IT_SHRT:
435  switch (val_type) {
436  case Support::IT_CHAR:
437  case Support::IT_SHRT:
439  default: break;
440  }
441  break;
442  default: break;
443  }
444  return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
445  }
446 
447 }}}
448 
449 // STATISTICS: int-prop
450 
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:104
bool marked(void *p)
Check whether p is marked.
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
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Linked index-value pairs.
Definition: element.hh:71
Idx val(void) const
Return index of current index value pair.
Definition: int.hpp:81
Actor must always be disposed.
Definition: core.hpp:630
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
Value iterator for array of integers
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:53
IterVal(IdxVal *iv)
Initialize with start.
Definition: int.hpp:90
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
virtual void reschedule(Space &home)
Schedule function.
Definition: int.hpp:220
Base-class for propagators.
Definition: core.hpp:1092
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:67
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
Handle to region.
Definition: region.hpp:61
Value iterator for integer views.
Definition: view.hpp:94
Propagation has computed fixpoint.
Definition: core.hpp:545
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4858
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
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:2868
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
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:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
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:542
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
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:249
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
Expensive.
Definition: core.hpp:582
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:56
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:3321
ByVal(const IdxVal *iv)
Initialize with index value pairs.
Definition: int.hpp:147
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
const int v[7]
Definition: distinct.cpp:263
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:3127
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high binary)
Definition: int.hpp:210
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
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
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:173
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:137
Execution is okay.
Definition: core.hpp:544
ExecStatus post_int(Home home, IntSharedArray &c, V0 x0, V1 x1)
Post propagator with apropriate index and value types.
Definition: int.hpp:410
Propagation has not computed fixpoint.
Definition: core.hpp:543
void prune_idx(void)
Prune index according to x0.
Definition: int.hpp:227
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
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition: val.hpp:82
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:169
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:922
static ExecStatus assigned_val(Space &home, IntSharedArray &c, V0 x0, V1 x1)
Prune when x1 is assigned.
Definition: int.hpp:272
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4854
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int.hpp:287
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition: int.hpp:151