Generated on Tue Mar 5 2013 22:37:29 for Gecode by doxygen 1.8.3.1
minmax.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  * Gabor Szokoli <szokoli@gecode.org>
7  * Denys Duchier <denys.duchier@univ-orleans.fr>
8  *
9  * Copyright:
10  * Guido Tack, 2004
11  * Christian Schulte, 2004
12  * Gabor Szokoli, 2004
13  *
14  * Last modified:
15  * $Date: 2010-07-15 01:46:18 +1000 (Thu, 15 Jul 2010) $ by $Author: schulte $
16  * $Revision: 11192 $
17  *
18  * This file is part of Gecode, the generic constraint
19  * development environment:
20  * http://www.gecode.org
21  *
22  * Permission is hereby granted, free of charge, to any person obtaining
23  * a copy of this software and associated documentation files (the
24  * "Software"), to deal in the Software without restriction, including
25  * without limitation the rights to use, copy, modify, merge, publish,
26  * distribute, sublicense, and/or sell copies of the Software, and to
27  * permit persons to whom the Software is furnished to do so, subject to
28  * the following conditions:
29  *
30  * The above copyright notice and this permission notice shall be
31  * included in all copies or substantial portions of the Software.
32  *
33  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
34  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
35  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
36  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
37  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
38  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
39  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
40  *
41  */
42 
43 
44 
45 #include <gecode/set.hh>
46 #include <gecode/int.hh>
47 
48 namespace Gecode { namespace Set { namespace Int {
49 
50  template<class View>
53  : MixBinaryPropagator<View,PC_SET_ANY,Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, y0, y1) {}
54 
55  template<class View>
58  GECODE_ME_CHECK(x0.cardMin(home,1));
59  (void) new (home) MinElement(home,x0,x1);
60  return ES_OK;
61  }
62 
63  template<class View>
66  : MixBinaryPropagator<View,PC_SET_ANY,Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, share, p) {}
67 
68  template<class View>
69  Actor*
70  MinElement<View>::copy(Space& home, bool share) {
71  return new (home) MinElement(home,share,*this);
72  }
73 
74  template<class View>
77  //x1 is an element of x0.ub
78  //x1 =< smallest element of x0.lb
79  //x1 =< x0.cardinialityMin-est largest element of x0.ub
80  //(these 2 take care of determined x0)
81  //No element in x0 is smaller than x1
82  //if x1 is determined, it is part of the ub.
83 
84  //Consequently:
85  //The domain of x1 is a subset of x0.ub up to the first element in x0.lb.
86  //x0 lacks everything smaller than smallest possible x1.
87 
88  {
89  LubRanges<View> ub(x0);
90  GECODE_ME_CHECK(x1.inter_r(home,ub,false));
91  }
92  GECODE_ME_CHECK(x1.lq(home,x0.glbMin()));
93  //if cardMin>lbSize?
94  assert(x0.cardMin()>=1);
95 
96  {
98  unsigned int size = 0;
99  int maxN = BndSet::MAX_OF_EMPTY;
100  for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++size) {}
101  Region r(home);
102  int* ub = r.alloc<int>(size*2);
103  int i=0;
104  for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++i) {
105  ub[2*i] = ubr.min();
106  ub[2*i+1] = ubr.max();
107  }
108  unsigned int x0cm = x0.cardMin()-1;
109  for (unsigned int i=size; i--;) {
110  unsigned int width = static_cast<unsigned int>(ub[2*i+1]-ub[2*i]+1);
111  if (width > x0cm) {
112  maxN = static_cast<int>(ub[2*i+1]-x0cm);
113  break;
114  }
115  x0cm -= width;
116  }
117  GECODE_ME_CHECK(x1.lq(home,maxN));
118  }
119 
120  GECODE_ME_CHECK( x0.exclude(home,
121  Limits::min, x1.min()-1) );
122 
123  if (x1.assigned()) {
124  GECODE_ME_CHECK(x0.include(home,x1.val()));
125  GECODE_ME_CHECK(x0.exclude(home,
126  Limits::min, x1.val()-1));
127  return home.ES_SUBSUMED(*this);
128  }
129 
130  return ES_FIX;
131  }
132 
133 
134  template<class View>
139  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
140 
141  template<class View>
144  (void) new (home) NotMinElement(home,x0,x1);
145  return ES_OK;
146  }
147 
148  template<class View>
151  NotMinElement& p)
153  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, share, p) {}
154 
155  template<class View>
156  Actor*
157  NotMinElement<View>::copy(Space& home, bool share) {
158  return new (home) NotMinElement(home,share,*this);
159  }
160 
161  template<class View>
162  ExecStatus
164  // cheap tests for entailment:
165  // if x0 is empty, then entailed
166  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed
167  // if min(x0.glb) < min(x1), then entailed
168  if ((x0.cardMax() == 0) ||
169  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
170  ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
171  return home.ES_SUBSUMED(*this);
172  // if x1 is determined and = x0.lub.min: remove it from x0,
173  // then entailed
174  if (x1.assigned() && x1.val()==x0.lubMin()) {
175  GECODE_ME_CHECK(x0.exclude(home,x1.val()));
176  return home.ES_SUBSUMED(*this);
177  }
178  // if min(x0) is decided: remove min(x0) from the domain of x1
179  // then entailed
180  if (x0.glbMin() == x0.lubMin()) {
181  GECODE_ME_CHECK(x1.nq(home,x0.glbMin()));
182  return home.ES_SUBSUMED(*this);
183  }
184  // if x1 is determined and = x0.glb.min, then we need at least
185  // one more element; if there is only one below, then we must
186  // take it.
187  if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMin()) {
188  unsigned int oldGlbSize = x0.glbSize();
189  // if there is only 1 unknown below x1, then we must take it
190  UnknownRanges<View> ur(x0);
191  assert(ur());
192  // the iterator is not empty: otherwise x0 would be determined
193  // and min(x0) would have been decided and the preceding if
194  // would have caught it. Also, the first range is not above
195  // x1 otherwise the very first if would have caught it.
196  // so let's check if the very first range of unknowns is of
197  // size 1 and there is no second one or it starts above x1.
198  if (ur.width()==1) {
199  int i=ur.min();
200  ++ur;
201  if (!ur() || ur.min()>x1.val()) {
202  GECODE_ME_CHECK(x0.include(home,i));
203  return home.ES_SUBSUMED(*this);
204  }
205  }
206  GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
207  }
208  // if dom(x1) and lub(x0) are disjoint, then entailed;
209  {
210  LubRanges<View> ub(x0);
214  if (!ir()) return home.ES_SUBSUMED(*this);
215  }
216  // x0 is fated to eventually contain at least x0.cardMin elements.
217  // therefore min(x0) <= x0.cardMin-th largest element of x0.lub
218  // if x1 > than that, then entailed.
219  {
220  // to find the x0.cardMin-th largest element of x0.lub, we need
221  // some sort of reverse range iterator. we will need to fake one
222  // by storing the ranges of the forward iterator in an array.
223  // first we need to know how large the array needs to be. so, let's
224  // count the ranges:
225  int num_ranges = 0;
226  for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {}
227  // create an array for storing min and max of each range
228  Region r(home);
229  int* _ur = r.alloc<int>(num_ranges*2);
230  // now, we fill the array:
231  int i = 0;
232  for (LubRanges<View> ur(x0); ur(); ++ur, ++i) {
233  _ur[2*i ] = ur.min();
234  _ur[2*i+1] = ur.max();
235  }
236  // now we search from the top the range that contains the
237  // nth largest value.
238  unsigned int n = x0.cardMin();
239  int nth_largest = BndSet::MAX_OF_EMPTY;
240  for (int i=num_ranges; i--; ) {
241  // number of values in range
242  unsigned int num_values = static_cast<unsigned int>(_ur[2*i+1]-_ur[2*i]+1);
243  // does the range contain the value?
244  if (num_values >= n) {
245  // record it and exit the loop
246  nth_largest = static_cast<int>(_ur[2*i+1]-n+1);
247  break;
248  }
249  // otherwise, we skipped num_values
250  n -= num_values;
251  }
252  // if x1.min > nth_largest, then entailed
253  if (x1.min() > nth_largest)
254  return home.ES_SUBSUMED(*this);
255  }
256  return ES_FIX;
257  }
258 
259  template<class View>
263  : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
264  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
265  Gecode::Int::BoolView> (home, y0, y1, b2) {}
266 
267  template<class View>
271  (void) new (home) ReMinElement(home,x0,x1,b2);
272  return ES_OK;
273  }
274 
275  template<class View>
278  : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
279  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
280  Gecode::Int::BoolView> (home, share, p) {}
281 
282  template<class View>
283  Actor*
284  ReMinElement<View>::copy(Space& home, bool share) {
285  return new (home) ReMinElement(home,share,*this);
286  }
287 
288  template<class View>
289  ExecStatus
291  // check if b is determined
292  if (b.one())
293  GECODE_REWRITE(*this, (MinElement<View>::post(home(*this),x0,x1)));
294  if (b.zero())
295  GECODE_REWRITE(*this, (NotMinElement<View>::post(home(*this),x0,x1)));
296  // cheap tests for => b=0
297  // if x0 is empty, then b=0 and entailed
298  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed
299  // if min(x0.glb) < min(x1), then b=0 and entailed
300  if ((x0.cardMax() == 0) ||
301  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
302  ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
303  {
304  GECODE_ME_CHECK(b.zero(home));
305  return home.ES_SUBSUMED(*this);
306  }
307  // if min(x0) is decided
308  if (x0.glbMin() == x0.lubMin()) {
309  // if x1 is det: check if = min(x0), assign b, entailed
310  if (x1.assigned()) {
311  if (x1.val() == x0.glbMin()) {
312  GECODE_ME_CHECK(b.one(home));
313  } else {
314  GECODE_ME_CHECK(b.zero(home));
315  }
316  return home.ES_SUBSUMED(*this);
317  }
318  // if min(x0) not in dom(x1): b=0, entailed
319  else if ((x0.glbMin() < x1.min()) ||
320  (x0.glbMin() > x1.max()) ||
321  !x1.in(x0.glbMin()))
322  {
323  GECODE_ME_CHECK(b.zero(home));
324  return home.ES_SUBSUMED(*this);
325  }
326  }
327  // // if dom(x1) and lub(x0) are disjoint, then b=0, entailed;
328  // {
329  // LubRanges<View> ub(x0);
330  // Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
331  // Gecode::Iter::Ranges::Inter<LubRanges<View>,
332  // Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
333  // if (!ir()) {
334  // GECODE_ME_CHECK(b.zero(home));
335  // return home.ES_SUBSUMED(*this);
336  // }
337  // }
338  // // x0 is fated to eventually contain at least x0.cardMin elements.
339  // // therefore min(x0) <= x0.cardMin-th largest element of x0.lub
340  // // if x1 > than that, then b=0 and entailed.
341  // {
342  // // to find the x0.cardMin-th largest element of x0.lub, we need
343  // // some sort of reverse range iterator. we will need to fake one
344  // // by storing the ranges of the forward iterator in an array.
345  // // first we need to know how large the array needs to be. so, let's
346  // // count the ranges:
347  // int num_ranges = 0;
348  // for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {}
349  // // create an array for storing min and max of each range
350  // Region re(home);
351  // int* _ur = re.alloc<int>(num_ranges*2);
352  // // now, we fill the array:
353  // int i = 0;
354  // for (LubRanges<View> ur(x0); ur(); ++ur, ++i) {
355  // _ur[2*i ] = ur.min();
356  // _ur[2*i+1] = ur.max();
357  // }
358  // // now we search from the top the range that contains the
359  // // nth largest value.
360  // int n = x0.cardMin();
361  // int nth_largest = BndSet::MAX_OF_EMPTY;
362  // for (int i=num_ranges; i--; ) {
363  // // number of values in range
364  // int num_values = _ur[2*i+1]-_ur[2*i]+1;
365  // // does the range contain the value?
366  // if (num_values >= n)
367  // {
368  // // record it and exit the loop
369  // nth_largest = _ur[2*i+1]-n+1;
370  // break;
371  // }
372  // // otherwise, we skipped num_values
373  // n -= num_values;
374  // }
375  // // if x1.min > nth_largest, then entailed
376  // if (x1.min() > nth_largest) {
377  // GECODE_ME_CHECK(b.zero(home));
378  // return home.ES_SUBSUMED(*this);
379  // }
380  // }
381  return ES_FIX;
382  }
383 
384  template<class View>
388  Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, y0, y1) {}
389 
390  template<class View>
394  Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, share, p) {}
395 
396  template<class View>
397  ExecStatus
400  GECODE_ME_CHECK(x0.cardMin(home,1));
401  (void) new (home) MaxElement(home,x0,x1);
402  return ES_OK;
403  }
404 
405  template<class View>
406  Actor*
407  MaxElement<View>::copy(Space& home, bool share) {
408  return new (home) MaxElement(home,share,*this);
409  }
410 
411  template<class View>
412  ExecStatus
414  LubRanges<View> ub(x0);
415  GECODE_ME_CHECK(x1.inter_r(home,ub,false));
416  GECODE_ME_CHECK(x1.gq(home,x0.glbMax()));
417  assert(x0.cardMin()>=1);
418  GECODE_ME_CHECK(x1.gq(home,x0.lubMinN(x0.cardMin()-1)));
419  GECODE_ME_CHECK(x0.exclude(home,
420  x1.max()+1,Limits::max) );
421 
422  if (x1.assigned()) {
423  GECODE_ME_CHECK(x0.include(home,x1.val()));
424  GECODE_ME_CHECK( x0.exclude(home,
425  x1.val()+1,Limits::max) );
426  return home.ES_SUBSUMED(*this);
427  }
428 
429  return ES_FIX;
430  }
431 
432  template<class View>
437  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
438 
439  template<class View>
442  NotMaxElement& p)
444  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, share, p) {}
445 
446  template<class View>
447  ExecStatus
449  (void) new (home) NotMaxElement(home,x0,x1);
450  return ES_OK;
451  }
452 
453  template<class View>
454  Actor*
455  NotMaxElement<View>::copy(Space& home, bool share) {
456  return new (home) NotMaxElement(home,share,*this);
457  }
458 
459  template<class View>
460  ExecStatus
462  // cheap tests for entailment:
463  // if x0 is empty, then entailed
464  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed
465  // if max(x0.glb) > max(x1), then entailed
466  if ((x0.cardMax() == 0) ||
467  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
468  ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
469  return home.ES_SUBSUMED(*this);
470  // if x1 is determined and = max(x0.lub): remove it from x0,
471  // then entailed
472  if (x1.assigned() && x1.val()==x0.lubMax()) {
473  GECODE_ME_CHECK(x0.exclude(home,x1.val()));
474  return home.ES_SUBSUMED(*this);
475  }
476  // if max(x0) is decided: remove max(x0) from the domain of x1
477  // then entailed
478  if (x0.glbMax() == x0.lubMax()) {
479  GECODE_ME_CHECK(x1.nq(home,x0.glbMax()));
480  return home.ES_SUBSUMED(*this);
481  }
482  // if x1 is determined and = max(x0.glb), then we need at least
483  // one more element; if there is only one above, then we must
484  // take it.
485  if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMax()) {
486  unsigned int oldGlbSize = x0.glbSize();
487  // if there is only 1 unknown above x1, then we must take it
488  UnknownRanges<View> ur(x0);
489  // there is at least one unknown above x1 otherwise it would
490  // have been caught by the if for x1=max(x0.lub)
491  while (ur.max() < x1.val()) {
492  assert(ur());
493  ++ur;
494  };
495  // if the first range above x1 contains just 1 element,
496  // and is the last range, then take that element
497  if (ur.width() == 1) {
498  int i = ur.min();
499  ++ur;
500  if (!ur()) {
501  // last range
502  GECODE_ME_CHECK(x0.include(home,i));
503  return home.ES_SUBSUMED(*this);
504  }
505  }
506  GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
507  }
508  // if dom(x1) and lub(x0) are disjoint, then entailed
509  {
510  LubRanges<View> ub(x0);
514  if (!ir()) return home.ES_SUBSUMED(*this);
515  }
516  // x0 is fated to eventually contain at least x0.cardMin elements.
517  // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub.
518  // if x1 < than that, then entailed.
519  {
520  unsigned int n = x0.cardMin();
521  int nth_smallest = BndSet::MIN_OF_EMPTY;
522  for (LubRanges<View> ur(x0); ur(); ++ur) {
523  if (ur.width() >= n) {
524  // record it and exit the loop
525  nth_smallest = static_cast<int>(ur.min() + n - 1);
526  break;
527  }
528  // otherwise, we skipped ur.width() values
529  n -= ur.width();
530  }
531  // if x1.max < nth_smallest, then entailed
532  if (x1.max() < nth_smallest)
533  return home.ES_SUBSUMED(*this);
534  }
535  return ES_FIX;
536  }
537 
538  template<class View>
542  : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
543  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
544  Gecode::Int::BoolView> (home, y0, y1, b2) {}
545 
546  template<class View>
549  : Gecode::Int::ReMixBinaryPropagator<View,PC_SET_ANY,
550  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
551  Gecode::Int::BoolView> (home, share, p) {}
552 
553  template<class View>
554  ExecStatus
558  (void) new (home) ReMaxElement(home,x0,x1,b2);
559  return ES_OK;
560  }
561 
562  template<class View>
563  Actor*
564  ReMaxElement<View>::copy(Space& home, bool share) {
565  return new (home) ReMaxElement(home,share,*this);
566  }
567 
568  template<class View>
569  ExecStatus
571  // check if b is determined
572  if (b.one())
573  GECODE_REWRITE(*this, (MaxElement<View>::post(home(*this),x0,x1)));
574  if (b.zero())
575  GECODE_REWRITE(*this, (NotMaxElement<View>::post(home(*this),x0,x1)));
576  // cheap tests for => b=0
577  // if x0 is empty, then b=0 and entailed
578  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed
579  // if max(x0.glb) > max(x1), then b=0 and entailed
580  if ((x0.cardMax() == 0) ||
581  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
582  ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
583  {
584  GECODE_ME_CHECK(b.zero(home));
585  return home.ES_SUBSUMED(*this);
586  }
587  // if max(x0) is decided
588  if (x0.glbMax() == x0.lubMax()) {
589  // if x1 is det: check if = max(x0), assign b, entailed
590  if (x1.assigned()) {
591  if (x1.val() == x0.glbMax()) {
592  GECODE_ME_CHECK(b.one(home));
593  } else {
594  GECODE_ME_CHECK(b.zero(home));
595  }
596  return home.ES_SUBSUMED(*this);
597  }
598  // if max(x0) not in dom(x1): b=0, entailed
599  else if ((x0.glbMax() < x1.min()) ||
600  (x0.glbMax() > x1.max()) ||
601  !x1.in(x0.glbMax()))
602  {
603  GECODE_ME_CHECK(b.zero(home));
604  return home.ES_SUBSUMED(*this);
605  }
606  }
607  // if dom(x1) and lub(x0) are disjoint, then b=0, entailed
608  {
609  LubRanges<View> ub(x0);
613  if (!ir()) {
614  GECODE_ME_CHECK(b.zero(home));
615  return home.ES_SUBSUMED(*this);
616  }
617  }
618  // x0 is fated to eventually contain at least x0.cardMin elements.
619  // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub.
620  // if x1 < than that, then b=0, entailed.
621  {
622  unsigned int n = x0.cardMin();
623  int nth_smallest = BndSet::MIN_OF_EMPTY;
624  for (LubRanges<View> ur(x0); ur(); ++ur) {
625  if (ur.width() >= n)
626  {
627  // record it and exit the loop
628  nth_smallest = static_cast<int>(ur.min() + n - 1);
629  break;
630  }
631  // otherwise, we skipped ur.width() values
632  n -= ur.width();
633  }
634  // if x1.max < nth_smallest, then entailed
635  if (x1.max() < nth_smallest) {
636  GECODE_ME_CHECK(b.zero(home));
637  return home.ES_SUBSUMED(*this);
638  }
639  }
640  return ES_FIX;
641  }
642 
643 }}}
644 
645 // STATISTICS: set-prop