Generated on Sat Jan 20 2018 22:21:18 for Gecode by doxygen 1.8.13
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: 2017-04-01 20:27:10 +0200 (Sat, 01 Apr 2017) $ by $Author: schulte $
16  * $Revision: 15623 $
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  {
104  int i=0;
105  for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++i) {
106  ub[2*i] = ubr.min();
107  ub[2*i+1] = ubr.max();
108  }
109  }
110  unsigned int x0cm = x0.cardMin()-1;
111  for (unsigned int i=size; i--;) {
112  unsigned int width = static_cast<unsigned int>(ub[2*i+1]-ub[2*i]+1);
113  if (width > x0cm) {
114  maxN = static_cast<int>(ub[2*i+1]-x0cm);
115  break;
116  }
117  x0cm -= width;
118  }
119  GECODE_ME_CHECK(x1.lq(home,maxN));
120  }
121 
122  GECODE_ME_CHECK( x0.exclude(home,
123  Limits::min, x1.min()-1) );
124 
125  if (x1.assigned()) {
126  GECODE_ME_CHECK(x0.include(home,x1.val()));
127  GECODE_ME_CHECK(x0.exclude(home,
128  Limits::min, x1.val()-1));
129  return home.ES_SUBSUMED(*this);
130  }
131 
132  return ES_FIX;
133  }
134 
135 
136  template<class View>
141  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
142 
143  template<class View>
146  (void) new (home) NotMinElement(home,x0,x1);
147  return ES_OK;
148  }
149 
150  template<class View>
153  NotMinElement& p)
155  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, share, p) {}
156 
157  template<class View>
158  Actor*
159  NotMinElement<View>::copy(Space& home, bool share) {
160  return new (home) NotMinElement(home,share,*this);
161  }
162 
163  template<class View>
164  ExecStatus
166  // cheap tests for entailment:
167  // if x0 is empty, then entailed
168  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed
169  // if min(x0.glb) < min(x1), then entailed
170  if ((x0.cardMax() == 0) ||
171  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
172  ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
173  return home.ES_SUBSUMED(*this);
174  // if x1 is determined and = x0.lub.min: remove it from x0,
175  // then entailed
176  if (x1.assigned() && x1.val()==x0.lubMin()) {
177  GECODE_ME_CHECK(x0.exclude(home,x1.val()));
178  return home.ES_SUBSUMED(*this);
179  }
180  // if min(x0) is decided: remove min(x0) from the domain of x1
181  // then entailed
182  if (x0.glbMin() == x0.lubMin()) {
183  GECODE_ME_CHECK(x1.nq(home,x0.glbMin()));
184  return home.ES_SUBSUMED(*this);
185  }
186  // if x1 is determined and = x0.glb.min, then we need at least
187  // one more element; if there is only one below, then we must
188  // take it.
189  if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMin()) {
190  unsigned int oldGlbSize = x0.glbSize();
191  // if there is only 1 unknown below x1, then we must take it
193  assert(ur());
194  // the iterator is not empty: otherwise x0 would be determined
195  // and min(x0) would have been decided and the preceding if
196  // would have caught it. Also, the first range is not above
197  // x1 otherwise the very first if would have caught it.
198  // so let's check if the very first range of unknowns is of
199  // size 1 and there is no second one or it starts above x1.
200  if (ur.width()==1) {
201  int i=ur.min();
202  ++ur;
203  if (!ur() || ur.min()>x1.val()) {
204  GECODE_ME_CHECK(x0.include(home,i));
205  return home.ES_SUBSUMED(*this);
206  }
207  }
208  GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
209  }
210  // if dom(x1) and lub(x0) are disjoint, then entailed;
211  {
212  LubRanges<View> ub(x0);
216  if (!ir()) return home.ES_SUBSUMED(*this);
217  }
218  // x0 is fated to eventually contain at least x0.cardMin elements.
219  // therefore min(x0) <= x0.cardMin-th largest element of x0.lub
220  // if x1 > than that, then entailed.
221  {
222  // to find the x0.cardMin-th largest element of x0.lub, we need
223  // some sort of reverse range iterator. we will need to fake one
224  // by storing the ranges of the forward iterator in an array.
225  // first we need to know how large the array needs to be. so, let's
226  // count the ranges:
227  int num_ranges = 0;
228  for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {}
229  // create an array for storing min and max of each range
230  Region r(home);
231  int* _ur = r.alloc<int>(num_ranges*2);
232  // now, we fill the array:
233  int i = 0;
234  for (LubRanges<View> ur(x0); ur(); ++ur, ++i) {
235  _ur[2*i ] = ur.min();
236  _ur[2*i+1] = ur.max();
237  }
238  // now we search from the top the range that contains the
239  // nth largest value.
240  unsigned int n = x0.cardMin();
241  int nth_largest = BndSet::MAX_OF_EMPTY;
242  for (int i=num_ranges; i--; ) {
243  // number of values in range
244  unsigned int num_values = static_cast<unsigned int>(_ur[2*i+1]-_ur[2*i]+1);
245  // does the range contain the value?
246  if (num_values >= n) {
247  // record it and exit the loop
248  nth_largest = static_cast<int>(_ur[2*i+1]-n+1);
249  break;
250  }
251  // otherwise, we skipped num_values
252  n -= num_values;
253  }
254  // if x1.min > nth_largest, then entailed
255  if (x1.min() > nth_largest)
256  return home.ES_SUBSUMED(*this);
257  }
258  return ES_FIX;
259  }
260 
261  template<class View, ReifyMode rm>
267  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
268  Gecode::Int::BoolView> (home, y0, y1, b2) {}
269 
270  template<class View, ReifyMode rm>
274  (void) new (home) ReMinElement(home,x0,x1,b2);
275  return ES_OK;
276  }
277 
278  template<class View, ReifyMode rm>
281  ReMinElement& p)
283  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
284  Gecode::Int::BoolView> (home, share, p) {}
285 
286  template<class View, ReifyMode rm>
287  Actor*
288  ReMinElement<View,rm>::copy(Space& home, bool share) {
289  return new (home) ReMinElement(home,share,*this);
290  }
291 
292  template<class View, ReifyMode rm>
293  ExecStatus
295  // check if b is determined
296  if (b.one()) {
297  if (rm == RM_PMI)
298  return home.ES_SUBSUMED(*this);
299  GECODE_REWRITE(*this, (MinElement<View>::post(home(*this),x0,x1)));
300  }
301  if (b.zero()) {
302  if (rm == RM_IMP)
303  return home.ES_SUBSUMED(*this);
304  GECODE_REWRITE(*this, (NotMinElement<View>::post(home(*this),x0,x1)));
305  }
306  // cheap tests for => b=0
307  // if x0 is empty, then b=0 and entailed
308  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed
309  // if min(x0.glb) < min(x1), then b=0 and entailed
310  if ((x0.cardMax() == 0) ||
311  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
312  ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
313  {
314  if (rm != RM_PMI)
315  GECODE_ME_CHECK(b.zero(home));
316  return home.ES_SUBSUMED(*this);
317  }
318  // if min(x0) is decided
319  if (x0.glbMin() == x0.lubMin()) {
320  // if x1 is det: check if = min(x0), assign b, entailed
321  if (x1.assigned()) {
322  if (x1.val() == x0.glbMin()) {
323  if (rm != RM_IMP)
324  GECODE_ME_CHECK(b.one(home));
325  } else {
326  if (rm != RM_PMI)
327  GECODE_ME_CHECK(b.zero(home));
328  }
329  return home.ES_SUBSUMED(*this);
330  }
331  // if min(x0) not in dom(x1): b=0, entailed
332  else if ((x0.glbMin() < x1.min()) ||
333  (x0.glbMin() > x1.max()) ||
334  !x1.in(x0.glbMin()))
335  {
336  if (rm != RM_PMI)
337  GECODE_ME_CHECK(b.zero(home));
338  return home.ES_SUBSUMED(*this);
339  }
340  }
341  // // if dom(x1) and lub(x0) are disjoint, then b=0, entailed;
342  // {
343  // LubRanges<View> ub(x0);
344  // Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
345  // Gecode::Iter::Ranges::Inter<LubRanges<View>,
346  // Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
347  // if (!ir()) {
348  // GECODE_ME_CHECK(b.zero(home));
349  // return home.ES_SUBSUMED(*this);
350  // }
351  // }
352  // // x0 is fated to eventually contain at least x0.cardMin elements.
353  // // therefore min(x0) <= x0.cardMin-th largest element of x0.lub
354  // // if x1 > than that, then b=0 and entailed.
355  // {
356  // // to find the x0.cardMin-th largest element of x0.lub, we need
357  // // some sort of reverse range iterator. we will need to fake one
358  // // by storing the ranges of the forward iterator in an array.
359  // // first we need to know how large the array needs to be. so, let's
360  // // count the ranges:
361  // int num_ranges = 0;
362  // for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {}
363  // // create an array for storing min and max of each range
364  // Region re(home);
365  // int* _ur = re.alloc<int>(num_ranges*2);
366  // // now, we fill the array:
367  // int i = 0;
368  // for (LubRanges<View> ur(x0); ur(); ++ur, ++i) {
369  // _ur[2*i ] = ur.min();
370  // _ur[2*i+1] = ur.max();
371  // }
372  // // now we search from the top the range that contains the
373  // // nth largest value.
374  // int n = x0.cardMin();
375  // int nth_largest = BndSet::MAX_OF_EMPTY;
376  // for (int i=num_ranges; i--; ) {
377  // // number of values in range
378  // int num_values = _ur[2*i+1]-_ur[2*i]+1;
379  // // does the range contain the value?
380  // if (num_values >= n)
381  // {
382  // // record it and exit the loop
383  // nth_largest = _ur[2*i+1]-n+1;
384  // break;
385  // }
386  // // otherwise, we skipped num_values
387  // n -= num_values;
388  // }
389  // // if x1.min > nth_largest, then entailed
390  // if (x1.min() > nth_largest) {
391  // GECODE_ME_CHECK(b.zero(home));
392  // return home.ES_SUBSUMED(*this);
393  // }
394  // }
395  return ES_FIX;
396  }
397 
398  template<class View>
402  Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, y0, y1) {}
403 
404  template<class View>
408  Gecode::Int::IntView,Gecode::Int::PC_INT_BND> (home, share, p) {}
409 
410  template<class View>
411  ExecStatus
414  GECODE_ME_CHECK(x0.cardMin(home,1));
415  (void) new (home) MaxElement(home,x0,x1);
416  return ES_OK;
417  }
418 
419  template<class View>
420  Actor*
421  MaxElement<View>::copy(Space& home, bool share) {
422  return new (home) MaxElement(home,share,*this);
423  }
424 
425  template<class View>
426  ExecStatus
428  LubRanges<View> ub(x0);
429  GECODE_ME_CHECK(x1.inter_r(home,ub,false));
430  GECODE_ME_CHECK(x1.gq(home,x0.glbMax()));
431  assert(x0.cardMin()>=1);
432  GECODE_ME_CHECK(x1.gq(home,x0.lubMinN(x0.cardMin()-1)));
433  GECODE_ME_CHECK(x0.exclude(home,
434  x1.max()+1,Limits::max) );
435 
436  if (x1.assigned()) {
437  GECODE_ME_CHECK(x0.include(home,x1.val()));
438  GECODE_ME_CHECK( x0.exclude(home,
439  x1.val()+1,Limits::max) );
440  return home.ES_SUBSUMED(*this);
441  }
442 
443  return ES_FIX;
444  }
445 
446  template<class View>
451  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
452 
453  template<class View>
456  NotMaxElement& p)
458  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM> (home, share, p) {}
459 
460  template<class View>
461  ExecStatus
463  (void) new (home) NotMaxElement(home,x0,x1);
464  return ES_OK;
465  }
466 
467  template<class View>
468  Actor*
469  NotMaxElement<View>::copy(Space& home, bool share) {
470  return new (home) NotMaxElement(home,share,*this);
471  }
472 
473  template<class View>
474  ExecStatus
476  // cheap tests for entailment:
477  // if x0 is empty, then entailed
478  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed
479  // if max(x0.glb) > max(x1), then entailed
480  if ((x0.cardMax() == 0) ||
481  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
482  ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
483  return home.ES_SUBSUMED(*this);
484  // if x1 is determined and = max(x0.lub): remove it from x0,
485  // then entailed
486  if (x1.assigned() && x1.val()==x0.lubMax()) {
487  GECODE_ME_CHECK(x0.exclude(home,x1.val()));
488  return home.ES_SUBSUMED(*this);
489  }
490  // if max(x0) is decided: remove max(x0) from the domain of x1
491  // then entailed
492  if (x0.glbMax() == x0.lubMax()) {
493  GECODE_ME_CHECK(x1.nq(home,x0.glbMax()));
494  return home.ES_SUBSUMED(*this);
495  }
496  // if x1 is determined and = max(x0.glb), then we need at least
497  // one more element; if there is only one above, then we must
498  // take it.
499  if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMax()) {
500  unsigned int oldGlbSize = x0.glbSize();
501  // if there is only 1 unknown above x1, then we must take it
503  // there is at least one unknown above x1 otherwise it would
504  // have been caught by the if for x1=max(x0.lub)
505  while (ur.max() < x1.val()) {
506  assert(ur());
507  ++ur;
508  };
509  // if the first range above x1 contains just 1 element,
510  // and is the last range, then take that element
511  if (ur.width() == 1) {
512  int i = ur.min();
513  ++ur;
514  if (!ur()) {
515  // last range
516  GECODE_ME_CHECK(x0.include(home,i));
517  return home.ES_SUBSUMED(*this);
518  }
519  }
520  GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
521  }
522  // if dom(x1) and lub(x0) are disjoint, then entailed
523  {
524  LubRanges<View> ub(x0);
528  if (!ir()) return home.ES_SUBSUMED(*this);
529  }
530  // x0 is fated to eventually contain at least x0.cardMin elements.
531  // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub.
532  // if x1 < than that, then entailed.
533  {
534  unsigned int n = x0.cardMin();
535  int nth_smallest = BndSet::MIN_OF_EMPTY;
536  for (LubRanges<View> ur(x0); ur(); ++ur) {
537  if (ur.width() >= n) {
538  // record it and exit the loop
539  nth_smallest = static_cast<int>(ur.min() + n - 1);
540  break;
541  }
542  // otherwise, we skipped ur.width() values
543  n -= ur.width();
544  }
545  // if x1.max < nth_smallest, then entailed
546  if (x1.max() < nth_smallest)
547  return home.ES_SUBSUMED(*this);
548  }
549  return ES_FIX;
550  }
551 
552  template<class View, ReifyMode rm>
558  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
559  Gecode::Int::BoolView> (home, y0, y1, b2) {}
560 
561  template<class View, ReifyMode rm>
564  ReMaxElement& p)
566  Gecode::Int::IntView,Gecode::Int::PC_INT_DOM,
567  Gecode::Int::BoolView> (home, share, p) {}
568 
569  template<class View, ReifyMode rm>
570  ExecStatus
574  (void) new (home) ReMaxElement(home,x0,x1,b2);
575  return ES_OK;
576  }
577 
578  template<class View, ReifyMode rm>
579  Actor*
580  ReMaxElement<View,rm>::copy(Space& home, bool share) {
581  return new (home) ReMaxElement(home,share,*this);
582  }
583 
584  template<class View, ReifyMode rm>
585  ExecStatus
587  // check if b is determined
588  if (b.one()) {
589  if (rm == RM_PMI)
590  return home.ES_SUBSUMED(*this);
591  GECODE_REWRITE(*this, (MaxElement<View>::post(home(*this),x0,x1)));
592  }
593  if (b.zero()) {
594  if (rm == RM_IMP)
595  return home.ES_SUBSUMED(*this);
596  GECODE_REWRITE(*this, (NotMaxElement<View>::post(home(*this),x0,x1)));
597  }
598  // cheap tests for => b=0
599  // if x0 is empty, then b=0 and entailed
600  // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed
601  // if max(x0.glb) > max(x1), then b=0 and entailed
602  if ((x0.cardMax() == 0) ||
603  ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
604  ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
605  {
606  if (rm != RM_PMI)
607  GECODE_ME_CHECK(b.zero(home));
608  return home.ES_SUBSUMED(*this);
609  }
610  // if max(x0) is decided
611  if (x0.glbMax() == x0.lubMax()) {
612  // if x1 is det: check if = max(x0), assign b, entailed
613  if (x1.assigned()) {
614  if (x1.val() == x0.glbMax()) {
615  if (rm != RM_IMP)
616  GECODE_ME_CHECK(b.one(home));
617  } else {
618  if (rm != RM_PMI)
619  GECODE_ME_CHECK(b.zero(home));
620  }
621  return home.ES_SUBSUMED(*this);
622  }
623  // if max(x0) not in dom(x1): b=0, entailed
624  else if ((x0.glbMax() < x1.min()) ||
625  (x0.glbMax() > x1.max()) ||
626  !x1.in(x0.glbMax()))
627  {
628  if (rm != RM_PMI)
629  GECODE_ME_CHECK(b.zero(home));
630  return home.ES_SUBSUMED(*this);
631  }
632  }
633  // if dom(x1) and lub(x0) are disjoint, then b=0, entailed
634  {
635  LubRanges<View> ub(x0);
639  if (!ir()) {
640  if (rm != RM_PMI)
641  GECODE_ME_CHECK(b.zero(home));
642  return home.ES_SUBSUMED(*this);
643  }
644  }
645  // x0 is fated to eventually contain at least x0.cardMin elements.
646  // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub.
647  // if x1 < than that, then b=0, entailed.
648  {
649  unsigned int n = x0.cardMin();
650  int nth_smallest = BndSet::MIN_OF_EMPTY;
651  for (LubRanges<View> ur(x0); ur(); ++ur) {
652  if (ur.width() >= n)
653  {
654  // record it and exit the loop
655  nth_smallest = static_cast<int>(ur.min() + n - 1);
656  break;
657  }
658  // otherwise, we skipped ur.width() values
659  n -= ur.width();
660  }
661  // if x1.max < nth_smallest, then entailed
662  if (x1.max() < nth_smallest) {
663  if (rm != RM_PMI)
664  GECODE_ME_CHECK(b.zero(home));
665  return home.ES_SUBSUMED(*this);
666  }
667  }
668  return ES_FIX;
669  }
670 
671 }}}
672 
673 // STATISTICS: set-prop
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:180
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:151
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:70
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is the minimal element of s.
Definition: minmax.hpp:57
bool zero(void) const
Test whether view is assigned to be zero.
Definition: bool.hpp:214
Inverse implication for reification.
Definition: int.hh:850
Range iterator for the unknown set.
Definition: var-imp.hpp:406
const int min
Smallest allowed integer in integer set.
Definition: set.hh:103
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: minmax.hpp:421
Propagator for not maximum element
Definition: int.hh:174
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
bool one(void) const
Test whether view is assigned to be one.
Definition: bool.hpp:218
ReMinElement(Space &home, bool share, ReMinElement &p)
Constructor for cloning p.
Definition: minmax.hpp:280
Reified mixed binary propagator.
Definition: propagator.hpp:128
int max(void) const
Return largest value of range.
Handle to region.
Definition: region.hpp:61
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:116
Propagation has computed fixpoint.
Definition: core.hpp:545
const int max
Largest allowed integer in integer set.
Definition: set.hh:101
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is not the minimal element of s.
Definition: minmax.hpp:145
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
Propagator for reified minimum element
Definition: int.hh:115
Gecode::IntSet d(v, 7)
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:114
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:101
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: minmax.hpp:294
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: minmax.hpp:469
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: minmax.hpp:586
Propagator for not minimum element
Definition: int.hh:87
static ExecStatus post(Home home, View s, Gecode::Int::IntView x, Gecode::Int::BoolView b)
Post reified propagator for b iff x is the minimal element of s.
Definition: minmax.hpp:272
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
Range iterator for computing intersection (binary)
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
int min(void) const
Return minimum of domain.
Definition: int.hpp:58
MaxElement(Space &home, bool share, MaxElement &p)
Constructor for cloning p.
Definition: minmax.hpp:406
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1105
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is the largest element of s.
Definition: minmax.hpp:412
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: minmax.hpp:288
ReMaxElement(Space &home, bool share, ReMaxElement &p)
Constructor for cloning p.
Definition: minmax.hpp:563
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: minmax.hpp:165
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
NotMaxElement(Space &home, bool share, NotMaxElement &p)
Constructor for cloning p.
Definition: minmax.hpp:455
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: minmax.hpp:76
Propagator for maximum element
Definition: int.hh:147
Integer view for integer variables.
Definition: view.hpp:129
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:478
Mixed binary propagator.
Definition: propagator.hpp:213
ExecStatus
Definition: core.hpp:540
Reified propagator for maximum element
Definition: int.hh:202
#define forceinline
Definition: config.hpp:173
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
MinElement(Space &home, bool share, MinElement &p)
Constructor for cloning p.
Definition: minmax.hpp:65
Execution is okay.
Definition: core.hpp:544
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: minmax.hpp:159
NotMinElement(Space &home, bool share, NotMinElement &p)
Constructor for cloning p.
Definition: minmax.hpp:152
Gecode toplevel namespace
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
Implication for reification.
Definition: int.hh:843
int min(void) const
Return smallest value of range.
static ExecStatus post(Home home, View s, Gecode::Int::IntView x, Gecode::Int::BoolView b)
Post reified propagator for b iff x is the largest element of s.
Definition: minmax.hpp:571
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: minmax.hpp:70
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: minmax.hpp:475
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
static ExecStatus post(Home home, View s, Gecode::Int::IntView x)
Post propagator for x is not the largest element of s.
Definition: minmax.hpp:462
Propagator for minimum element
Definition: int.hh:59
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: minmax.hpp:427
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: minmax.hpp:580
Boolean view for Boolean variables.
Definition: view.hpp:1315