Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
11  * $Revision$
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>
196  : Propagator(home,p), s0(0), s1(0), c(p.c), iv(NULL) {
197  x0.update(home,p.x0);
198  x1.update(home,p.x1);
199  }
200 
201  template<class V0, class V1, class Idx, class Val>
202  Actor*
204  return new (home) Int<V0,V1,Idx,Val>(home,*this);
205  }
206 
207  template<class V0, class V1, class Idx, class Val>
208  PropCost
210  if ((V0::me(med) == ME_INT_VAL) ||
211  (V1::me(med) == ME_INT_VAL))
213  else
215  }
216 
217  template<class V0, class V1, class Idx, class Val>
218  void
220  x0.reschedule(home,*this,PC_INT_DOM);
221  x1.reschedule(home,*this,PC_INT_DOM);
222  }
223 
224  template<class V0, class V1, class Idx, class Val>
225  void
227  Idx p = 0;
228  Idx i = iv[p].idx_next;
230  while (v() && (i != 0)) {
231  assert(!iv[i].marked());
232  if (iv[i].idx < v.min()) {
233  iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
234  } else if (iv[i].idx > v.max()) {
235  ++v;
236  } else {
237  p=i; i=iv[i].idx_next;
238  }
239  }
240  iv[p].idx_next = 0;
241  while (i != 0) {
242  iv[i].mark(); i=iv[i].idx_next;
243  }
244  }
245 
246  template<class V0, class V1, class Idx, class Val>
247  void
249  Idx p = 0;
250  Idx i = iv[p].val_next;
252  while (v() && (i != 0)) {
253  if (iv[i].marked()) {
254  i=iv[i].val_next; iv[p].val_next=i;
255  } else if (iv[i].val < v.min()) {
256  iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
257  } else if (iv[i].val > v.max()) {
258  ++v;
259  } else {
260  p=i; i=iv[i].val_next;
261  }
262  }
263  iv[p].val_next = 0;
264  while (i != 0) {
265  iv[i].mark(); i=iv[i].val_next;
266  }
267  }
268 
269  template<class V0, class V1, class Idx, class Val>
270  ExecStatus
272  V0 x0, V1 x1) {
273  Region r;
274  int* v = r.alloc<int>(x0.size());
275  int n = 0;
276  for (ViewValues<V0> i(x0); i(); ++i)
277  if (c[i.val()] != x1.val())
278  v[n++]=i.val();
279  Iter::Values::Array iv(v,n);
280  GECODE_ME_CHECK(x0.minus_v(home,iv,false));
281  return ES_OK;
282  }
283 
284  template<class V0, class V1, class Idx, class Val>
285  ExecStatus
287  if (x0.assigned()) {
288  GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
289  return home.ES_SUBSUMED(*this);
290  }
291 
292  if (x1.assigned() && (iv == NULL)) {
294  return home.ES_SUBSUMED(*this);
295  }
296 
297  if ((static_cast<ValSize>(x1.size()) == s1) &&
298  (static_cast<IdxSize>(x0.size()) != s0)) {
299  assert(iv != NULL);
300  assert(!shared(x0,x1));
301 
302  prune_idx();
303 
304  IterValUnmark v(iv);
305  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
306 
307  s1=static_cast<ValSize>(x1.size());
308 
309  assert(!x0.assigned());
310  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
311  }
312 
313  if ((static_cast<IdxSize>(x0.size()) == s0) &&
314  (static_cast<ValSize>(x1.size()) != s1)) {
315  assert(iv != NULL);
316  assert(!shared(x0,x1));
317 
318  prune_val();
319 
320  IterIdxUnmark i(iv);
321  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
322 
323  s0=static_cast<IdxSize>(x0.size());
324 
325  return (x0.assigned() || x1.assigned()) ?
326  home.ES_SUBSUMED(*this) : ES_FIX;
327  }
328 
329  bool assigned = x0.assigned() && x1.assigned();
330  if (iv == NULL) {
331  // Initialize data structure
332  iv = home.alloc<IdxVal>(x0.size() + 1);
333 
334  // The first element in iv[0] is used as sentinel
335  // Enter information sorted by idx
336  IdxVal* by_idx = &iv[1];
337  Idx size = 0;
338  for (ViewValues<V0> v(x0); v(); ++v)
339  if ((x1.min() <= c[v.val()]) && (x1.max() >= c[v.val()])) {
340  by_idx[size].idx = static_cast<Idx>(v.val());
341  by_idx[size].val = static_cast<Val>(c[v.val()]);
342  size++;
343  }
344  if (size == 0)
345  return ES_FAILED;
346  // Create val links sorted by val
347  Region r;
348  Idx* by_val = r.alloc<Idx>(size);
349  if (x1.width() <= 128) {
350  int n_buckets = static_cast<int>(x1.width());
351  int* pos = r.alloc<int>(n_buckets);
352  int* buckets = pos - x1.min();
353  for (int i=n_buckets; i--; )
354  pos[i]=0;
355  for (Idx i=size; i--; )
356  buckets[by_idx[i].val]++;
357  int p=0;
358  for (int i=0; i<n_buckets; i++) {
359  int n=pos[i]; pos[i]=p; p+=n;
360  }
361  assert(p == size);
362  for (Idx i=size; i--; )
363  by_val[buckets[by_idx[i].val]++] = i+1;
364  } else {
365  for (Idx i = size; i--; )
366  by_val[i] = i+1;
367  ByVal less(iv);
368  Support::quicksort<Idx>(by_val,size,less);
369  }
370  // Create val links
371  for (Idx i = size-1; i--; ) {
372  by_idx[i].idx_next = i+2;
373  iv[by_val[i]].val_next = by_val[i+1];
374  }
375  by_idx[size-1].idx_next = 0;
376  iv[by_val[size-1]].val_next = 0;
377  // Set up sentinel element: iv[0]
378  iv[0].idx_next = 1;
379  iv[0].val_next = by_val[0];
380  } else {
381  prune_idx();
382  }
383 
384  // Prune values
385  prune_val();
386 
387  // Peform tell
388  {
389  IterIdxUnmark i(iv);
390  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
391  IterVal v(iv);
392  if (shared(x0,x1)) {
393  GECODE_ME_CHECK(x1.inter_v(home,v,false));
394  s0=static_cast<IdxSize>(x0.size());
395  s1=static_cast<ValSize>(x1.size());
396  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
397  } else {
398  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
399  s0=static_cast<IdxSize>(x0.size());
400  s1=static_cast<ValSize>(x1.size());
401  return (x0.assigned() || x1.assigned()) ?
402  home.ES_SUBSUMED(*this) : ES_FIX;
403  }
404  }
405  }
406 
407  template<class V0, class V1>
409  post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
410  assert(c.size() > 0);
411  GECODE_ME_CHECK(x0.gq(home,0));
412  GECODE_ME_CHECK(x0.le(home,c.size()));
413  Support::IntType idx_type = Support::s_type(c.size());
414  int min = c[0];
415  int max = c[0];
416  for (int i=1; i<c.size(); i++) {
417  min = std::min(c[i],min); max = std::max(c[i],max);
418  }
419  GECODE_ME_CHECK(x1.gq(home,min));
420  GECODE_ME_CHECK(x1.lq(home,max));
421  Support::IntType val_type =
423  switch (idx_type) {
424  case Support::IT_CHAR:
425  switch (val_type) {
426  case Support::IT_CHAR:
427  return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
428  case Support::IT_SHRT:
430  default: break;
431  }
432  break;
433  case Support::IT_SHRT:
434  switch (val_type) {
435  case Support::IT_CHAR:
436  case Support::IT_SHRT:
438  default: break;
439  }
440  break;
441  default: break;
442  }
443  return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
444  }
445 
446 }}}
447 
448 // STATISTICS: int-prop
449 
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:3433
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:554
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:384
IterValUnmark(IdxVal *iv)
Initialize with start.
Definition: int.hpp:113
Value iterator for array of integers
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:219
const IdxVal * iv
Index-value pairs.
Definition: element.hh:147
Base-class for propagators.
Definition: core.hpp:1016
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:57
Value iterator for integer views.
Definition: view.hpp:94
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4660
IntSharedArray c
Shared array of integer values.
Definition: element.hh:168
Computation spaces.
Definition: core.hpp:1668
Base-class for both propagators and branchers.
Definition: core.hpp:620
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:94
Range iterator for integer views.
Definition: view.hpp:54
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:2757
#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
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:466
Value iterator for values in index-value map.
Definition: element.hh:130
int size(void) const
Return number of elements.
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:248
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1027
int min(void) const
Return smallest value of range.
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1029
Expensive.
Definition: core.hpp:506
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:3139
ByVal(const IdxVal *iv)
Initialize with index value pairs.
Definition: int.hpp:147
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
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
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high binary)
Definition: int.hpp:209
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:3944
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition: int.hpp:203
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3172
Propagation cost.
Definition: core.hpp:478
ExecStatus
Definition: core.hpp:464
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
Int(Space &home, Int &p)
Constructor for cloning p.
Definition: int.hpp:195
int max(void) const
Return largest value of range.
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:137
Execution is okay.
Definition: core.hpp:468
ExecStatus post_int(Home home, IntSharedArray &c, V0 x0, V1 x1)
Post propagator with apropriate index and value types.
Definition: int.hpp:409
Propagation has not computed fixpoint.
Definition: core.hpp:467
void prune_idx(void)
Prune index according to x0.
Definition: int.hpp:226
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
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:91
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:846
static ExecStatus assigned_val(Space &home, IntSharedArray &c, V0 x0, V1 x1)
Prune when x1 is assigned.
Definition: int.hpp:271
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4656
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int.hpp:286
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition: int.hpp:151