Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Int { namespace Element {
35 
36 
37  // Index value pairs
38  template<class V0, class V1, class Idx, class Val>
39  forceinline void
41  idx = -1;
42  }
43  template<class V0, class V1, class Idx, class Val>
44  forceinline bool
46  return idx<0;
47  }
48 
49 
50  // Index iterator
51  template<class V0, class V1, class Idx, class Val>
54  : iv(iv0) {
55  Idx p=0;
56  i = iv[p].idx_next;
57  while ((i != 0) && iv[i].marked())
58  i=iv[i].idx_next;
59  iv[p].idx_next=i;
60  }
61  template<class V0, class V1, class Idx, class Val>
62  forceinline bool
64  return i != 0;
65  }
66  template<class V0, class V1, class Idx, class Val>
67  forceinline void
69  int p=i;
70  i = iv[p].idx_next;
71  while ((i != 0) && iv[i].marked())
72  i=iv[i].idx_next;
73  iv[p].idx_next=i;
74  }
75  template<class V0, class V1, class Idx, class Val>
76  forceinline Idx
78  assert(!iv[i].marked());
79  return iv[i].idx;
80  }
81 
82 
83 
84  template<class V0, class V1, class Idx, class Val>
87  : iv(iv0), i(iv[0].val_next) {}
88  template<class V0, class V1, class Idx, class Val>
89  forceinline bool
91  return i != 0;
92  }
93  template<class V0, class V1, class Idx, class Val>
94  forceinline void
96  i=iv[i].val_next;
97  }
98  template<class V0, class V1, class Idx, class Val>
99  forceinline Val
101  assert(!iv[i].marked());
102  return iv[i].val;
103  }
104 
105 
106 
107  template<class V0, class V1, class Idx, class Val>
110  : iv(iv0) {
111  Idx p=0;
112  i = iv[p].val_next;
113  while ((i != 0) && iv[i].marked())
114  i=iv[i].val_next;
115  iv[p].val_next=i;
116  }
117  template<class V0, class V1, class Idx, class Val>
118  forceinline bool
120  return i != 0;
121  }
122  template<class V0, class V1, class Idx, class Val>
123  forceinline void
125  int p=i;
126  i = iv[p].val_next;
127  while ((i != 0) && iv[i].marked())
128  i=iv[i].val_next;
129  iv[p].val_next=i;
130  }
131  template<class V0, class V1, class Idx, class Val>
132  forceinline Val
134  assert(!iv[i].marked());
135  return iv[i].val;
136  }
137 
138 
139 
140  // Sort function
141  template<class V0, class V1, class Idx, class Val>
144  : iv(iv0) {}
145  template<class V0, class V1, class Idx, class Val>
146  forceinline bool
148  return iv[i].val < iv[j].val;
149  }
150 
151 
152  /*
153  * Element propagator proper
154  *
155  */
156  template<class V0, class V1, class Idx, class Val>
158  Int<V0,V1,Idx,Val>::Int(Home home, IntSharedArray& c0, V0 y0, V1 y1)
159  : Propagator(home), x0(y0), s0(0), x1(y1), s1(0), c(c0), iv(NULL) {
160  home.notice(*this,AP_DISPOSE);
161  x0.subscribe(home,*this,PC_INT_DOM);
162  x1.subscribe(home,*this,PC_INT_DOM);
163  }
164 
165  template<class V0, class V1, class Idx, class Val>
166  forceinline size_t
168  home.ignore(*this,AP_DISPOSE);
169  x0.cancel(home,*this,PC_INT_DOM);
170  x1.cancel(home,*this,PC_INT_DOM);
171  c.~IntSharedArray();
172  (void) Propagator::dispose(home);
173  return sizeof(*this);
174  }
175 
176  template<class V0, class V1, class Idx, class Val>
177  ExecStatus
179  if (x0.assigned()) {
180  GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
181  } else if (x1.assigned()) {
182  GECODE_ES_CHECK(assigned_val(home,c,x0,x1));
183  } else {
184  (void) new (home) Int<V0,V1,Idx,Val>(home,c,x0,x1);
185  }
186  return ES_OK;
187  }
188 
189  template<class V0, class V1, class Idx, class Val>
192  : Propagator(home,p), s0(0), s1(0), c(p.c), iv(NULL) {
193  x0.update(home,p.x0);
194  x1.update(home,p.x1);
195  }
196 
197  template<class V0, class V1, class Idx, class Val>
198  Actor*
200  return new (home) Int<V0,V1,Idx,Val>(home,*this);
201  }
202 
203  template<class V0, class V1, class Idx, class Val>
204  PropCost
205  Int<V0,V1,Idx,Val>::cost(const Space&, const ModEventDelta& med) const {
206  if ((V0::me(med) == ME_INT_VAL) ||
207  (V1::me(med) == ME_INT_VAL))
209  else
211  }
212 
213  template<class V0, class V1, class Idx, class Val>
214  void
216  x0.reschedule(home,*this,PC_INT_DOM);
217  x1.reschedule(home,*this,PC_INT_DOM);
218  }
219 
220  template<class V0, class V1, class Idx, class Val>
221  void
223  Idx p = 0;
224  Idx i = iv[p].idx_next;
225  ViewRanges<V0> v(x0);
226  while (v() && (i != 0)) {
227  assert(!iv[i].marked());
228  if (iv[i].idx < v.min()) {
229  iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
230  } else if (iv[i].idx > v.max()) {
231  ++v;
232  } else {
233  p=i; i=iv[i].idx_next;
234  }
235  }
236  iv[p].idx_next = 0;
237  while (i != 0) {
238  iv[i].mark(); i=iv[i].idx_next;
239  }
240  }
241 
242  template<class V0, class V1, class Idx, class Val>
243  void
245  Idx p = 0;
246  Idx i = iv[p].val_next;
247  ViewRanges<V1> v(x1);
248  while (v() && (i != 0)) {
249  if (iv[i].marked()) {
250  i=iv[i].val_next; iv[p].val_next=i;
251  } else if (iv[i].val < v.min()) {
252  iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
253  } else if (iv[i].val > v.max()) {
254  ++v;
255  } else {
256  p=i; i=iv[i].val_next;
257  }
258  }
259  iv[p].val_next = 0;
260  while (i != 0) {
261  iv[i].mark(); i=iv[i].val_next;
262  }
263  }
264 
265  template<class V0, class V1, class Idx, class Val>
266  ExecStatus
268  V0 x0, V1 x1) {
269  Region r;
270  int* v = r.alloc<int>(x0.size());
271  int n = 0;
272  for (ViewValues<V0> i(x0); i(); ++i)
273  if (c[i.val()] != x1.val())
274  v[n++]=i.val();
275  Iter::Values::Array iv(v,n);
276  GECODE_ME_CHECK(x0.minus_v(home,iv,false));
277  return ES_OK;
278  }
279 
280  template<class V0, class V1, class Idx, class Val>
281  ExecStatus
283  if (x0.assigned()) {
284  GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
285  return home.ES_SUBSUMED(*this);
286  }
287 
288  if (x1.assigned() && (iv == NULL)) {
289  GECODE_ES_CHECK(assigned_val(home,c,x0,x1));
290  return home.ES_SUBSUMED(*this);
291  }
292 
293  if ((static_cast<ValSize>(x1.size()) == s1) &&
294  (static_cast<IdxSize>(x0.size()) != s0)) {
295  assert(iv != NULL);
296  assert(!shared(x0,x1));
297 
298  prune_idx();
299 
300  IterValUnmark v(iv);
301  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
302 
303  s1=static_cast<ValSize>(x1.size());
304 
305  assert(!x0.assigned());
306  return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
307  }
308 
309  if ((static_cast<IdxSize>(x0.size()) == s0) &&
310  (static_cast<ValSize>(x1.size()) != s1)) {
311  assert(iv != NULL);
312  assert(!shared(x0,x1));
313 
314  prune_val();
315 
316  IterIdxUnmark i(iv);
317  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
318 
319  s0=static_cast<IdxSize>(x0.size());
320 
321  return (x0.assigned() || x1.assigned()) ?
322  home.ES_SUBSUMED(*this) : ES_FIX;
323  }
324 
325  bool assigned = x0.assigned() && x1.assigned();
326  if (iv == NULL) {
327  // Initialize data structure
328  iv = home.alloc<IdxVal>(x0.size() + 1);
329 
330  // The first element in iv[0] is used as sentinel
331  // Enter information sorted by idx
332  IdxVal* by_idx = &iv[1];
333  Idx size = 0;
334  for (ViewValues<V0> v(x0); v(); ++v)
335  if ((x1.min() <= c[v.val()]) && (x1.max() >= c[v.val()])) {
336  by_idx[size].idx = static_cast<Idx>(v.val());
337  by_idx[size].val = static_cast<Val>(c[v.val()]);
338  size++;
339  }
340  if (size == 0)
341  return ES_FAILED;
342  // Create val links sorted by val
343  Region r;
344  Idx* by_val = r.alloc<Idx>(size);
345  if (x1.width() <= 128) {
346  int n_buckets = static_cast<int>(x1.width());
347  int* pos = r.alloc<int>(n_buckets);
348  int* buckets = pos - x1.min();
349  for (int i=0; i<n_buckets; i++)
350  pos[i]=0;
351  for (Idx i=0; i<size; i++)
352  buckets[by_idx[i].val]++;
353  int p=0;
354  for (int i=0; i<n_buckets; i++) {
355  int n=pos[i]; pos[i]=p; p+=n;
356  }
357  assert(p == size);
358  for (Idx i=0; i<size; i++)
359  by_val[buckets[by_idx[i].val]++] = i+1;
360  } else {
361  for (Idx i=0; i<size; i++)
362  by_val[i] = i+1;
363  ByVal less(iv);
364  Support::quicksort<Idx>(by_val,size,less);
365  }
366  // Create val links
367  for (Idx i=0; i<size-1; i++) {
368  by_idx[i].idx_next = i+2;
369  iv[by_val[i]].val_next = by_val[i+1];
370  }
371  by_idx[size-1].idx_next = 0;
372  iv[by_val[size-1]].val_next = 0;
373  // Set up sentinel element: iv[0]
374  iv[0].idx_next = 1;
375  iv[0].val_next = by_val[0];
376  } else {
377  prune_idx();
378  }
379 
380  // Prune values
381  prune_val();
382 
383  // Peform tell
384  {
385  IterIdxUnmark i(iv);
386  GECODE_ME_CHECK(x0.narrow_v(home,i,false));
387  IterVal v(iv);
388  if (shared(x0,x1)) {
389  GECODE_ME_CHECK(x1.inter_v(home,v,false));
390  s0=static_cast<IdxSize>(x0.size());
391  s1=static_cast<ValSize>(x1.size());
392  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
393  } else {
394  GECODE_ME_CHECK(x1.narrow_v(home,v,false));
395  s0=static_cast<IdxSize>(x0.size());
396  s1=static_cast<ValSize>(x1.size());
397  return (x0.assigned() || x1.assigned()) ?
398  home.ES_SUBSUMED(*this) : ES_FIX;
399  }
400  }
401  }
402 
403  template<class V0, class V1>
405  post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
406  assert(c.size() > 0);
407  GECODE_ME_CHECK(x0.gq(home,0));
408  GECODE_ME_CHECK(x0.le(home,c.size()));
409  Support::IntType idx_type = Support::s_type(c.size());
410  int min = c[0];
411  int max = c[0];
412  for (int i=1; i<c.size(); i++) {
413  min = std::min(c[i],min); max = std::max(c[i],max);
414  }
415  GECODE_ME_CHECK(x1.gq(home,min));
416  GECODE_ME_CHECK(x1.lq(home,max));
417  Support::IntType val_type =
419  switch (idx_type) {
420  case Support::IT_CHAR:
421  switch (val_type) {
422  case Support::IT_CHAR:
423  return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
424  case Support::IT_SHRT:
426  default: break;
427  }
428  break;
429  case Support::IT_SHRT:
430  switch (val_type) {
431  case Support::IT_CHAR:
432  case Support::IT_SHRT:
434  default: break;
435  }
436  break;
437  default: break;
438  }
439  return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
440  }
441 
442 }}}
443 
444 // STATISTICS: int-prop
445 
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Base-class for both propagators and branchers.
Definition: core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition: val.hpp:78
Home class for posting propagators
Definition: core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
Sorting pointers to (index,value) pairs in value order.
Definition: element.hh:141
bool operator()(Idx &i, Idx &j)
Compare pairs at positions i and j.
Definition: int.hpp:147
ByVal(const IdxVal *iv)
Initialize with index value pairs.
Definition: int.hpp:143
Linked index-value pairs.
Definition: element.hh:67
Idx val_next
The position of the next pair in value order.
Definition: element.hh:70
Val val
The value Mark that this pair should be removed.
Definition: element.hh:72
bool marked(void) const
Return whether this pair is marked for removal.
Definition: int.hpp:45
Idx idx_next
The position of the next pair in index order.
Definition: element.hh:69
Value iterator for indices in index-value map.
Definition: element.hh:84
Idx val(void) const
Return index of current index value pair.
Definition: int.hpp:77
void operator++(void)
Move to next index value pair (next index)
Definition: int.hpp:68
IterIdxUnmark(IdxVal *iv)
Initialize with start.
Definition: int.hpp:53
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:63
Value iterator for values in index-value map.
Definition: element.hh:126
void operator++(void)
Move to next index value pair (next value)
Definition: int.hpp:124
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:119
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:133
IterValUnmark(IdxVal *iv)
Initialize with start.
Definition: int.hpp:109
Value iterator for values in index-value map.
Definition: element.hh:104
bool operator()(void) const
Test whether more pairs to be iterated.
Definition: int.hpp:90
IterVal(IdxVal *iv)
Initialize with start.
Definition: int.hpp:86
Val val(void) const
Return value of current index value pair.
Definition: int.hpp:100
void operator++(void)
Move to next index value pair (next value)
Definition: int.hpp:95
Element propagator for array of integers
Definition: element.hh:57
Int(Space &home, Int &p)
Constructor for cloning p.
Definition: int.hpp:191
ValSize s1
Size of x1 at last execution.
Definition: element.hh:162
void prune_val(void)
Prune values according to x1.
Definition: int.hpp:244
IntSharedArray c
Shared array of integer values.
Definition: element.hh:164
V1 x1
View for result.
Definition: element.hh:158
static ExecStatus post(Home home, IntSharedArray &i, V0 x0, V1 x1)
Post propagator for .
Definition: int.hpp:178
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition: int.hpp:199
virtual void reschedule(Space &home)
Schedule function.
Definition: int.hpp:215
static ExecStatus assigned_val(Space &home, IntSharedArray &c, V0 x0, V1 x1)
Prune when x1 is assigned.
Definition: int.hpp:267
IdxSize s0
Size of x0 at last execution.
Definition: element.hh:156
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int.hpp:282
IdxVal * iv
The index-value data structure.
Definition: element.hh:166
Gecode::Support::IntTypeTraits< Idx >::utype IdxSize
Type for index size.
Definition: element.hh:154
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for value size.
Definition: element.hh:160
V0 x0
View for index.
Definition: element.hh:152
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high binary)
Definition: int.hpp:205
void prune_idx(void)
Prune index according to x0.
Definition: int.hpp:222
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int.hpp:167
Range iterator for integer views.
Definition: view.hpp:54
Value iterator for integer views.
Definition: view.hpp:94
Value iterator for array of integers
Propagation cost.
Definition: core.hpp:486
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4813
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4809
@ LO
Cheap.
Definition: core.hpp:513
@ HI
Expensive.
Definition: core.hpp:514
Base-class for propagators.
Definition: core.hpp:1064
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
bool shared(const IntSet &, VX)
Definition: view-base.hpp:118
ExecStatus post_int(Home home, IntSharedArray &c, V0 x0, V1 x1)
Post propagator with apropriate index and value types.
Definition: int.hpp:405
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
unsigned int size(I &i)
Size of all ranges of range iterator i.
IntType s_type(signed int n)
Return type required to represent n.
IntType
Description of integer types.
Definition: int-type.hpp:39
@ IT_CHAR
char integer type
Definition: int-type.hpp:40
@ IT_SHRT
short integer type
Definition: int-type.hpp:41
bool marked(void *p)
Check whether p is marked.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
const int v[7]
Definition: distinct.cpp:259
#define forceinline
Definition: config.hpp:192