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