Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
bnd.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  * Guido Tack <tack@gecode.org>
9  *
10  * Copyright:
11  * Patrick Pekczynski, 2004/2005
12  * Christian Schulte, 2009
13  * Guido Tack, 2009
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Int { namespace GCC {
41 
42  template<class Card>
46  bool cf, bool nolbc) :
47  Propagator(home), x(x0), y(home, x0), k(k0),
48  card_fixed(cf), skip_lbc(nolbc) {
49  y.subscribe(home, *this, PC_INT_BND);
50  k.subscribe(home, *this, PC_INT_BND);
51  }
52 
53  template<class Card>
57  : Propagator(home, p),
59  x.update(home, p.x);
60  y.update(home, p.y);
61  k.update(home, p.k);
62  }
63 
64  template<class Card>
65  forceinline size_t
67  y.cancel(home,*this, PC_INT_BND);
68  k.cancel(home,*this, PC_INT_BND);
69  (void) Propagator::dispose(home);
70  return sizeof(*this);
71  }
72 
73  template<class Card>
74  Actor*
76  return new (home) Bnd<Card>(home,*this);
77  }
78 
79  template<class Card>
80  PropCost
82  const ModEventDelta& med) const {
83  int n_k = Card::propagate ? k.size() : 0;
84  if (IntView::me(med) == ME_INT_VAL)
85  return PropCost::linear(PropCost::LO, y.size() + n_k);
86  else
87  return PropCost::quadratic(PropCost::LO, x.size() + n_k);
88  }
89 
90 
91  template<class Card>
92  void
94  y.reschedule(home, *this, PC_INT_BND);
95  k.reschedule(home, *this, PC_INT_BND);
96  }
97 
98  template<class Card>
100  Bnd<Card>::lbc(Space& home, int& nb,
101  HallInfo hall[], Rank rank[], int mu[], int nu[]) {
102  int n = x.size();
103 
104  /*
105  * Let I(S) denote the number of variables whose domain intersects
106  * the set S and C(S) the number of variables whose domain is containded
107  * in S. Let further min_cap(S) be the minimal number of variables
108  * that must be assigned to values, that is
109  * min_cap(S) is the sum over all l[i] for a value v_i that is an
110  * element of S.
111  *
112  * A failure set is a set F if
113  * I(F) < min_cap(F)
114  * An unstable set is a set U if
115  * I(U) = min_cap(U)
116  * A stable set is a set S if
117  * C(S) > min_cap(S) and S intersetcs nor
118  * any failure set nor any unstable set
119  * forall unstable and failure sets
120  *
121  * failure sets determine the satisfiability of the LBC
122  * unstable sets have to be pruned
123  * stable set do not have to be pruned
124  *
125  * hall[].ps ~ stores the unstable
126  * sets that have to be pruned
127  * hall[].s ~ stores sets that must not be pruned
128  * hall[].h ~ contains stable and unstable sets
129  * hall[].d ~ contains the difference between interval bounds, i.e.
130  * the minimal capacity of the interval
131  * hall[].t ~ contains the critical capacity pointer, pointing to the
132  * values
133  */
134 
135  // LBC lower bounds
136 
137  int i = 0;
138  int j = 0;
139  int w = 0;
140  int z = 0;
141  int v = 0;
142 
143  //initialization of the tree structure
144  int rightmost = nb + 1; // rightmost accesible value in bounds
145  int bsize = nb + 2;
146  w = rightmost;
147 
148  // test
149  // unused but uninitialized
150  hall[0].d = 0;
151  hall[0].s = 0;
152  hall[0].ps = 0;
153 
154  for (i = bsize; --i; ) { // i must not be zero
155  int pred = i - 1;
156  hall[i].s = pred;
157  hall[i].ps = pred;
158  hall[i].d = lps.sumup(hall[pred].bounds, hall[i].bounds - 1);
159 
160  /* Let [hall[i].bounds,hall[i-1].bounds]=:I
161  * If the capacity is zero => min_cap(I) = 0
162  * => I cannot be a failure set
163  * => I is an unstable set
164  */
165  if (hall[i].d == 0) {
166  hall[pred].h = w;
167  } else {
168  hall[w].h = pred;
169  w = pred;
170  }
171  }
172 
173  w = rightmost;
174  for (i = bsize; i--; ) { // i can be zero
175  hall[i].t = i - 1;
176  if (hall[i].d == 0) {
177  hall[i].t = w;
178  } else {
179  hall[w].t = i;
180  w = i;
181  }
182  }
183 
184  /*
185  * The algorithm assigns to each value v in bounds
186  * empty buckets corresponding to the minimal capacity l[i] to be
187  * filled for v. (the buckets correspond to hall[].d containing the
188  * difference between the interval bounds) Processing it
189  * searches for the smallest value v in dom(x_i) that has an
190  * empty bucket, i.e. if all buckets are filled it is guaranteed
191  * that there are at least l[i] variables that will be
192  * instantiated to v. Since the buckets are initially empty,
193  * they are considered as FAILURE SETS
194  */
195 
196  for (i = 0; i < n; i++) {
197  // visit intervals in increasing max order
198  int x0 = rank[mu[i]].min;
199  int y = rank[mu[i]].max;
200  int succ = x0 + 1;
201  z = pathmax_t(hall, succ);
202  j = hall[z].t;
203 
204  /*
205  * POTENTIALLY STABLE SET:
206  * z \neq succ \Leftrigharrow z>succ, i.e.
207  * min(D_{\mu(i)}) is guaranteed to occur min(K_i) times
208  * \Rightarrow [x0, min(y,z)] is potentially stable
209  */
210 
211  if (z != succ) {
212  w = pathmax_ps(hall, succ);
213  v = hall[w].ps;
214  pathset_ps(hall, succ, w, w);
215  w = std::min(y, z);
216  pathset_ps(hall, hall[w].ps, v, w);
217  hall[w].ps = v;
218  }
219 
220  /*
221  * STABLE SET:
222  * being stable implies being potentially stable, i.e.
223  * [hall[y].ps, hall[y].bounds-1] is the largest stable subset of
224  * [hall[j].bounds, hall[y].bounds-1].
225  */
226 
227  if (hall[z].d <= lps.sumup(hall[y].bounds, hall[z].bounds - 1)) {
228  w = pathmax_s(hall, hall[y].ps);
229  pathset_s(hall, hall[y].ps, w, w);
230  // Path compression
231  v = hall[w].s;
232  pathset_s(hall, hall[y].s, v, y);
233  hall[y].s = v;
234  } else {
235  /*
236  * FAILURE SET:
237  * If the considered interval [x0,y] is neither POTENTIALLY STABLE
238  * nor STABLE there are still buckets that can be filled,
239  * therefore d can be decreased. If d equals zero the intervals
240  * minimum capacity is met and thepath can be compressed to the
241  * next value having an empty bucket.
242  * see DOMINATION in "ubc"
243  */
244  if (--hall[z].d == 0) {
245  hall[z].t = z + 1;
246  z = pathmax_t(hall, hall[z].t);
247  hall[z].t = j;
248  }
249 
250  /*
251  * FINDING NEW LOWER BOUND:
252  * If the lower bound belongs to an unstable or a stable set,
253  * remind the new value we might assigned to the lower bound
254  * in case the variable doesn't belong to a stable set.
255  */
256  if (hall[x0].h > x0) {
257  hall[i].newBound = pathmax_h(hall, x0);
258  w = hall[i].newBound;
259  pathset_h(hall, x0, w, w); // path compression
260  } else {
261  // Do not shrink the variable: take old min as new min
262  hall[i].newBound = x0;
263  }
264 
265  /* UNSTABLE SET
266  * If an unstable set is discovered
267  * the difference between the interval bounds is equal to the
268  * number of variables whose domain intersect the interval
269  * (see ZEROTEST in "gcc")
270  */
271  // CLEARLY THIS WAS NOT STABLE == UNSTABLE
272  if (hall[z].d == lps.sumup(hall[y].bounds, hall[z].bounds - 1)) {
273  if (hall[y].h > y)
274  /*
275  * y is not the end of the potentially stable set
276  * thus ensure that the potentially stable superset is marked
277  */
278  y = hall[y].h;
279  // Equivalent to pathmax since the path is fully compressed
280  pathset_h(hall, hall[y].h, j-1, y);
281  // mark the new unstable set [j,y]
282  hall[y].h = j-1;
283  }
284  }
285  pathset_t(hall, succ, z, z); // path compression
286  }
287 
288  /* If there is a FAILURE SET left the minimum occurences of the values
289  * are not guaranteed. In order to satisfy the LBC the last value
290  * in the stable and unstable datastructure hall[].h must point to
291  * the sentinel at the beginning of bounds.
292  */
293  if (hall[nb].h != 0)
294  return ES_FAILED;
295 
296  // Perform path compression over all elements in
297  // the stable interval data structure. This data
298  // structure will no longer be modified and will be
299  // accessed n or 2n times. Therefore, we can afford
300  // a linear time compression.
301  for (i = bsize; --i;)
302  if (hall[i].s > i)
303  hall[i].s = w;
304  else
305  w = i;
306 
307  /*
308  * UPDATING LOWER BOUND:
309  * For all variables that are not a subset of a stable set,
310  * shrink the lower bound, i.e. forall stable sets S we have:
311  * x0 < S_min <= y <=S_max or S_min <= x0 <= S_max < y
312  * that is [x0,y] is NOT a proper subset of any stable set S
313  */
314  for (i = n; i--; ) {
315  int x0 = rank[mu[i]].min;
316  int y = rank[mu[i]].max;
317  // update only those variables that are not contained in a stable set
318  if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
319  // still have to check this out, how skipping works (consider dominated indices)
320  int m = lps.skipNonNullElementsRight(hall[hall[i].newBound].bounds);
321  GECODE_ME_CHECK(x[mu[i]].gq(home, m));
322  }
323  }
324 
325  // LBC narrow upper bounds
326  w = 0;
327  for (i = 0; i <= nb; i++) {
328  hall[i].d = lps.sumup(hall[i].bounds, hall[i + 1].bounds - 1);
329  if (hall[i].d == 0) {
330  hall[i].t = w;
331  } else {
332  hall[w].t = i;
333  w = i;
334  }
335  }
336  hall[w].t = i;
337 
338  w = 0;
339  for (i = 1; i <= nb; i++)
340  if (hall[i - 1].d == 0) {
341  hall[i].h = w;
342  } else {
343  hall[w].h = i;
344  w = i;
345  }
346  hall[w].h = i;
347 
348  for (i = n; i--; ) {
349  // visit intervals in decreasing min order
350  // i.e. minsorted from right to left
351  int x0 = rank[nu[i]].max;
352  int y = rank[nu[i]].min;
353  int pred = x0 - 1; // predecessor of x0 in the indices
354  z = pathmin_t(hall, pred);
355  j = hall[z].t;
356 
357  /* If the variable is not in a discovered stable set
358  * (see above condition for STABLE SET)
359  */
360  if (hall[z].d > lps.sumup(hall[z].bounds, hall[y].bounds - 1)) {
361  // FAILURE SET
362  if (--hall[z].d == 0) {
363  hall[z].t = z - 1;
364  z = pathmin_t(hall, hall[z].t);
365  hall[z].t = j;
366  }
367  // FINDING NEW UPPER BOUND
368  if (hall[x0].h < x0) {
369  w = pathmin_h(hall, hall[x0].h);
370  hall[i].newBound = w;
371  pathset_h(hall, x0, w, w); // path compression
372  } else {
373  hall[i].newBound = x0;
374  }
375  // UNSTABLE SET
376  if (hall[z].d == lps.sumup(hall[z].bounds, hall[y].bounds - 1)) {
377  if (hall[y].h < y) {
378  y = hall[y].h;
379  }
380  int succj = j + 1;
381  // mark new unstable set [y,j]
382  pathset_h(hall, hall[y].h, succj, y);
383  hall[y].h = succj;
384  }
385  }
386  pathset_t(hall, pred, z, z);
387  }
388 
389  // UPDATING UPPER BOUND
390  for (i = n; i--; ) {
391  int x0 = rank[nu[i]].min;
392  int y = rank[nu[i]].max;
393  if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
394  int m = lps.skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
395  GECODE_ME_CHECK(x[nu[i]].lq(home, m));
396  }
397  }
398  return ES_OK;
399  }
400 
401 
402  template<class Card>
404  Bnd<Card>::ubc(Space& home, int& nb,
405  HallInfo hall[], Rank rank[], int mu[], int nu[]) {
406  int rightmost = nb + 1; // rightmost accesible value in bounds
407  int bsize = nb + 2; // number of unique bounds including sentinels
408 
409  //Narrow lower bounds (UBC)
410 
411  /*
412  * Initializing tree structure with the values from bounds
413  * and the interval capacities of neighboured values
414  * from left to right
415  */
416 
417 
418  hall[0].h = 0;
419  hall[0].t = 0;
420  hall[0].d = 0;
421 
422  for (int i = bsize; --i; ) {
423  hall[i].h = hall[i].t = i-1;
424  hall[i].d = ups.sumup(hall[i-1].bounds, hall[i].bounds - 1);
425  }
426 
427  int n = x.size();
428 
429  for (int i = 0; i < n; i++) {
430  // visit intervals in increasing max order
431  int x0 = rank[mu[i]].min;
432  int succ = x0 + 1;
433  int y = rank[mu[i]].max;
434  int z = pathmax_t(hall, succ);
435  int j = hall[z].t;
436 
437  /* DOMINATION:
438  * v^i_j denotes
439  * unused values in the current interval. If the difference d
440  * between to critical capacities v^i_j and v^i_z
441  * is equal to zero, j dominates z
442  *
443  * i.e. [hall[l].bounds, hall[nb+1].bounds] is not left-maximal and
444  * [hall[j].bounds, hall[l].bounds] is a Hall set iff
445  * [hall[j].bounds, hall[l].bounds] processing a variable x_i uses up a value in the interval
446  * [hall[z].bounds,hall[z+1].bounds] according to the intervals
447  * capacity. Therefore, if d = 0
448  * the considered value has already been used by processed variables
449  * m-times, where m = u[i] for value v_i. Since this value must not
450  * be reconsidered the path can be compressed
451  */
452  if (--hall[z].d == 0) {
453  hall[z].t = z + 1;
454  z = pathmax_t(hall, hall[z].t);
455  if (z >= bsize)
456  z--;
457  hall[z].t = j;
458  }
459  pathset_t(hall, succ, z, z); // path compression
460 
461  /* NEGATIVE CAPACITY:
462  * A negative capacity results in a failure.Since a
463  * negative capacity signals that the number of variables
464  * whose domain is contained in the set S is larger than
465  * the maximum capacity of S => UBC is not satisfiable,
466  * i.e. there are more variables than values to instantiate them
467  */
468  if (hall[z].d < ups.sumup(hall[y].bounds, hall[z].bounds - 1))
469  return ES_FAILED;
470 
471  /* UPDATING LOWER BOUND:
472  * If the lower bound min_i lies inside a Hall interval [a,b]
473  * i.e. a <= min_i <=b <= max_i
474  * min_i is set to min_i := b+1
475  */
476  if (hall[x0].h > x0) {
477  int w = pathmax_h(hall, hall[x0].h);
478  int m = hall[w].bounds;
479  GECODE_ME_CHECK(x[mu[i]].gq(home, m));
480  pathset_h(hall, x0, w, w); // path compression
481  }
482 
483  /* ZEROTEST:
484  * (using the difference between capacity pointers)
485  * zero capacity => the difference between critical capacity
486  * pointers is equal to the maximum capacity of the interval,i.e.
487  * the number of variables whose domain is contained in the
488  * interval is equal to the sum over all u[i] for a value v_i that
489  * lies in the Hall-Intervall which can also be thought of as a
490  * Hall-Set
491  *
492  * ZeroTestLemma: Let k and l be succesive critical indices.
493  * v^i_k=0 => v^i_k = max_i+1-l+d
494  * <=> v^i_k = y + 1 - z + d
495  * <=> d = z-1-y
496  * if this equation holds the interval [j,z-1] is a hall intervall
497  */
498 
499  if (hall[z].d == ups.sumup(hall[y].bounds, hall[z].bounds - 1)) {
500  /*
501  *mark hall interval [j,z-1]
502  * hall pointers form a path to the upper bound of the interval
503  */
504  int predj = j - 1;
505  pathset_h(hall, hall[y].h, predj, y);
506  hall[y].h = predj;
507  }
508  }
509 
510  /* Narrow upper bounds (UBC)
511  * symmetric to the narrowing of the lower bounds
512  */
513  for (int i = 0; i < rightmost; i++) {
514  hall[i].h = hall[i].t = i+1;
515  hall[i].d = ups.sumup(hall[i].bounds, hall[i+1].bounds - 1);
516  }
517 
518  for (int i = n; i--; ) {
519  // visit intervals in decreasing min order
520  int x0 = rank[nu[i]].max;
521  int pred = x0 - 1;
522  int y = rank[nu[i]].min;
523  int z = pathmin_t(hall, pred);
524  int j = hall[z].t;
525 
526  // DOMINATION:
527  if (--hall[z].d == 0) {
528  hall[z].t = z - 1;
529  z = pathmin_t(hall, hall[z].t);
530  hall[z].t = j;
531  }
532  pathset_t(hall, pred, z, z);
533 
534  // NEGATIVE CAPACITY:
535  if (hall[z].d < ups.sumup(hall[z].bounds,hall[y].bounds-1))
536  return ES_FAILED;
537 
538  /* UPDATING UPPER BOUND:
539  * If the upper bound max_i lies inside a Hall interval [a,b]
540  * i.e. min_i <= a <= max_i < b
541  * max_i is set to max_i := a-1
542  */
543  if (hall[x0].h < x0) {
544  int w = pathmin_h(hall, hall[x0].h);
545  int m = hall[w].bounds - 1;
546  GECODE_ME_CHECK(x[nu[i]].lq(home, m));
547  pathset_h(hall, x0, w, w);
548  }
549 
550  // ZEROTEST
551  if (hall[z].d == ups.sumup(hall[z].bounds, hall[y].bounds - 1)) {
552  //mark hall interval [y,j]
553  pathset_h(hall, hall[y].h, j+1, y);
554  hall[y].h = j+1;
555  }
556  }
557  return ES_OK;
558  }
559 
560  template<class Card>
561  ExecStatus
563  // Remove all values with 0 max occurrence
564  // and remove corresponding occurrence variables from k
565 
566  // The number of zeroes
567  int n_z = 0;
568  for (int i=k.size(); i--;)
569  if (k[i].max() == 0)
570  n_z++;
571 
572  if (n_z > 0) {
573  Region r;
574  int* z = r.alloc<int>(n_z);
575  n_z = 0;
576  int n_k = 0;
577  for (int i=0; i<k.size(); i++)
578  if (k[i].max() == 0) {
579  z[n_z++] = k[i].card();
580  } else {
581  k[n_k++] = k[i];
582  }
583  k.size(n_k);
584  Support::quicksort(z,n_z);
585  for (int i=x.size(); i--;) {
586  Iter::Values::Array zi(z,n_z);
587  GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
588  }
589  lps.reinit(); ups.reinit();
590  }
591  return ES_OK;
592  }
593 
594  template<class Card>
595  ExecStatus
597  if (IntView::me(med) == ME_INT_VAL) {
598  GECODE_ES_CHECK(prop_val<Card>(home,*this,y,k));
599  return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_BND));
600  }
601 
602  if (Card::propagate)
604 
605  Region r;
606  int* count = r.alloc<int>(k.size());
607 
608  for (int i = k.size(); i--; )
609  count[i] = 0;
610  bool all_assigned = true;
611  int noa = 0;
612  for (int i = x.size(); i--; ) {
613  if (x[i].assigned()) {
614  noa++;
615  int idx;
616  // reduction is essential for order on value nodes in dom
617  // hence introduce test for failed lookup
618  if (!lookupValue(k,x[i].val(),idx))
619  return ES_FAILED;
620  count[idx]++;
621  } else {
622  all_assigned = false;
623  // We only need the counts in the view case or when all
624  // x are assigned
625  if (!Card::propagate)
626  break;
627  }
628  }
629 
630  if (Card::propagate) {
631  // before propagation performs inferences on cardinality variables:
632  if (noa > 0)
633  for (int i = k.size(); i--; )
634  if (!k[i].assigned()) {
635  GECODE_ME_CHECK(k[i].lq(home, x.size() - (noa - count[i])));
636  GECODE_ME_CHECK(k[i].gq(home, count[i]));
637  }
638 
639  if (!card_consistent<Card>(x, k))
640  return ES_FAILED;
641 
642  GECODE_ES_CHECK(prop_card<Card>(home, x, k));
643 
644  // Cardinalities may have been modified, so recompute
645  // count and all_assigned
646  for (int i = k.size(); i--; )
647  count[i] = 0;
648  all_assigned = true;
649  for (int i = x.size(); i--; ) {
650  if (x[i].assigned()) {
651  int idx;
652  // reduction is essential for order on value nodes in dom
653  // hence introduce test for failed lookup
654  if (!lookupValue(k,x[i].val(),idx))
655  return ES_FAILED;
656  count[idx]++;
657  } else {
658  // We won't need the remaining counts, they're only used when
659  // all x are assigned
660  all_assigned = false;
661  break;
662  }
663  }
664  }
665 
666  if (all_assigned) {
667  for (int i = k.size(); i--; )
668  GECODE_ME_CHECK(k[i].eq(home, count[i]));
669  return home.ES_SUBSUMED(*this);
670  }
671 
672  if (Card::propagate)
674 
675  int n = x.size();
676 
677  int* mu = r.alloc<int>(n);
678  int* nu = r.alloc<int>(n);
679 
680  for (int i = n; i--; )
681  nu[i] = mu[i] = i;
682 
683  // Create sorting permutation mu according to the variables upper bounds
684  MaxInc<IntView> max_inc(x);
685  Support::quicksort<int, MaxInc<IntView> >(mu, n, max_inc);
686 
687  // Create sorting permutation nu according to the variables lower bounds
688  MinInc<IntView> min_inc(x);
689  Support::quicksort<int, MinInc<IntView> >(nu, n, min_inc);
690 
691  // Sort the cardinality bounds by index
692  MinIdx<Card> min_idx;
693  Support::quicksort<Card, MinIdx<Card> >(&k[0], k.size(), min_idx);
694 
695  if (!lps) {
696  assert(!ups);
697  lps.init(home, k, false);
698  ups.init(home, k, true);
699  } else if (Card::propagate) {
700  // if there has been a change to the cardinality variables
701  // reconstruction of the partial sum structure is necessary
702  if (lps.check_update_min(k))
703  lps.init(home, k, false);
704  if (ups.check_update_max(k))
705  ups.init(home, k, true);
706  }
707 
708  // assert that the minimal value of the partial sum structure for
709  // LBC is consistent with the smallest value a variable can take
710  assert(lps.minValue() <= x[nu[0]].min());
711  // assert that the maximal value of the partial sum structure for
712  // UBC is consistent with the largest value a variable can take
713 
714  /*
715  * Setup rank and bounds info
716  * Since this implementation is based on the theory of Hall Intervals
717  * additional datastructures are needed in order to represent these
718  * intervals and the "partial-sum" data structure (cf."gcc/bnd-sup.hpp")
719  *
720  */
721 
722  HallInfo* hall = r.alloc<HallInfo>(2 * n + 2);
723  Rank* rank = r.alloc<Rank>(n);
724 
725  int nb = 0;
726  // setup bounds and rank
727  int min = x[nu[0]].min();
728  int max = x[mu[0]].max() + 1;
729  int last = lps.firstValue + 1; //equivalent to last = min -2
730  hall[0].bounds = last;
731 
732  /*
733  * First the algorithm merges the arrays minsorted and maxsorted
734  * into bounds i.e. hall[].bounds contains the ordered union
735  * of the lower and upper domain bounds including two sentinels
736  * at the beginning and at the end of the set
737  * ( the upper variable bounds in this union are increased by 1 )
738  */
739 
740  {
741  int i = 0;
742  int j = 0;
743  while (true) {
744  if (i < n && min < max) {
745  if (min != last) {
746  last = min;
747  hall[++nb].bounds = last;
748  }
749  rank[nu[i]].min = nb;
750  if (++i < n)
751  min = x[nu[i]].min();
752  } else {
753  if (max != last) {
754  last = max;
755  hall[++nb].bounds = last;
756  }
757  rank[mu[j]].max = nb;
758  if (++j == n)
759  break;
760  max = x[mu[j]].max() + 1;
761  }
762  }
763  }
764 
765  int rightmost = nb + 1; // rightmost accesible value in bounds
766  hall[rightmost].bounds = ups.lastValue + 1 ;
767 
768  if (Card::propagate) {
769  skip_lbc = true;
770  for (int i = k.size(); i--; )
771  if (k[i].min() != 0) {
772  skip_lbc = false;
773  break;
774  }
775  }
776 
777  if (!card_fixed && !skip_lbc)
778  GECODE_ES_CHECK((lbc(home, nb, hall, rank, mu, nu)));
779 
780  GECODE_ES_CHECK((ubc(home, nb, hall, rank, mu, nu)));
781 
782  if (Card::propagate)
783  GECODE_ES_CHECK(prop_card<Card>(home, x, k));
784 
785  for (int i = k.size(); i--; )
786  count[i] = 0;
787  for (int i = x.size(); i--; )
788  if (x[i].assigned()) {
789  int idx;
790  if (!lookupValue(k,x[i].val(),idx))
791  return ES_FAILED;
792  count[idx]++;
793  } else {
794  // We won't need the remaining counts, they're only used when
795  // all x are assigned
796  return ES_NOFIX;
797  }
798 
799  for (int i = k.size(); i--; )
800  GECODE_ME_CHECK(k[i].eq(home, count[i]));
801 
802  return home.ES_SUBSUMED(*this);
803  }
804 
805 
806  template<class Card>
807  ExecStatus
810  bool cardfix = true;
811  for (int i=k.size(); i--; )
812  if (!k[i].assigned()) {
813  cardfix = false; break;
814  }
815  bool nolbc = true;
816  for (int i=k.size(); i--; )
817  if (k[i].min() != 0) {
818  nolbc = false; break;
819  }
820 
821  GECODE_ES_CHECK(postSideConstraints<Card>(home, x, k));
822 
823  if (isDistinct<Card>(x,k))
824  return Distinct::Bnd<IntView>::post(home,x);
825 
826  (void) new (home) Bnd<Card>(home,x,k,cardfix,nolbc);
827  return ES_OK;
828  }
829 
830 }}}
831 
832 // STATISTICS: int-prop
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
Definition: bnd.hpp:81
int d
Difference between critical capacities.
Definition: bnd-sup.hpp:473
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1352
NodeType t
Type of node.
Definition: bool-expr.cpp:230
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4714
Container class provding information about the Hall structure of the problem variables.
Definition: bnd-sup.hpp:456
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4723
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1310
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
Value iterator for array of integers
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3503
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition: view.hpp:45
void pathset_s(HallInfo hall[], int start, int end, int to)
Path compression for stable set structure.
Definition: bnd-sup.hpp:515
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
void pathset_h(HallInfo hall[], int start, int end, int to)
Path compression for hall pointer structure.
Definition: bnd-sup.hpp:531
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:120
Base-class for propagators.
Definition: core.hpp:1023
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1323
int h
Hall set pointer.
Definition: bnd-sup.hpp:482
PartialSum< Card > lps
Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval c...
Definition: gcc.hh:126
Handle to region.
Definition: region.hpp:55
int pathmax_t(const HallInfo hall[], int i)
Path maximum for capacity pointer structure.
Definition: bnd-sup.hpp:579
int pathmin_h(const HallInfo hall[], int i)
Path minimum for hall pointer structure.
Definition: bnd-sup.hpp:549
#define forceinline
Definition: config.hpp:185
int pathmin_t(const HallInfo hall[], int i)
Path minimum for capacity pointer structure.
Definition: bnd-sup.hpp:556
Computation spaces.
Definition: core.hpp:1701
Base-class for both propagators and branchers.
Definition: core.hpp:627
Compares two indices i, j of two views according to the ascending order of the views lower bounds...
Definition: bnd-sup.hpp:199
Gecode::IntSet d(v, 7)
int pathmax_h(const HallInfo hall[], int i)
Path maximum for hall pointer structure.
Definition: bnd-sup.hpp:572
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: bnd.hpp:75
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
PartialSum< Card > ups
Data structure storing the sum of the views upper bounds.
Definition: gcc.hh:128
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition: bnd.hpp:476
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int t
Critical capacity pointer t represents a predecessor function where denotes the predecessor of i in ...
Definition: bnd-sup.hpp:465
Compares two indices i, j of two views according to the ascending order of the views upper bounds...
Definition: bnd-sup.hpp:176
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
Definition: core.hpp:473
virtual size_t dispose(Space &home)
Destructor.
Definition: bnd.hpp:66
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.hpp:66
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
int pathmax_ps(const HallInfo hall[], int i)
Path maximum for potentially stable set pointer structure.
Definition: bnd-sup.hpp:594
ExecStatus ubc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Upper Bounds constraint (UBC) stating Hence the ubc constraints the variables such that no value occ...
Definition: bnd.hpp:404
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition: var-type.hpp:65
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: bnd.hpp:808
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1331
ExecStatus pruneCards(Space &home)
Prune cardinality variables with 0 maximum occurrence.
Definition: bnd.hpp:562
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
int bounds
Represents the union of all lower and upper domain bounds.
Definition: bnd-sup.hpp:459
void pathset_t(HallInfo hall[], int start, int end, int to)
Path compression for capacity pointer structure.
Definition: bnd-sup.hpp:523
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
const int v[7]
Definition: distinct.cpp:259
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
int newBound
Bound update.
Definition: bnd-sup.hpp:493
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Maps domain bounds to their position in hall[].bounds.
Definition: bnd-sup.hpp:154
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3209
Propagation cost.
Definition: core.hpp:485
Bnd(Space &home, Bnd< Card > &p)
Constructor for cloning p.
Definition: bnd.hpp:56
ExecStatus
Definition: core.hpp:471
int s
Stable Set pointer.
Definition: bnd-sup.hpp:484
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
int pathmax_s(const HallInfo hall[], int i)
Path maximum for stable set pointer structure.
Definition: bnd-sup.hpp:587
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
Propagation has not computed fixpoint.
Definition: core.hpp:474
ViewArray< IntView > y
Views on which to perform value-propagation (subset of x)
Definition: gcc.hh:118
int ps
Potentially Stable Set pointer.
Definition: bnd-sup.hpp:486
Gecode toplevel namespace
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: bnd.hpp:596
ViewArray< IntView > x
Views on which to perform bounds-propagation.
Definition: gcc.hh:116
bool skip_lbc
Stores whether the minium required occurences of the cardinalities are all zero. If so...
Definition: gcc.hh:141
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Compares two cardinality views according to the index.
Definition: bnd-sup.hpp:221
Home class for posting propagators
Definition: core.hpp:853
Bounds consistent global cardinality propagator.
Definition: gcc.hh:113
bool card_fixed
Stores whether cardinalities are all assigned.
Definition: gcc.hh:135
ExecStatus lbc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Lower Bounds constraint (LBC) stating Hence the lbc constraints the variables such that every value ...
Definition: bnd.hpp:100
void pathset_ps(HallInfo hall[], int start, int end, int to)
Path compression for potentially stable set structure.
Definition: bnd-sup.hpp:507
virtual void reschedule(Space &home)
Schedule function.
Definition: bnd.hpp:93