Generated on Mon Sep 17 2012 22:20:38 for Gecode by doxygen 1.8.1.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: 2011-09-19 22:02:26 +1000 (Mon, 19 Sep 2011) $ by $Author: schulte $
11  * $Revision: 12400 $
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