Generated on Mon Nov 30 23:53:35 2009 for Gecode by doxygen 1.6.1

minmax.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *     Gabor Szokoli <szokoli@gecode.org>
00007  *     Denys Duchier <denys.duchier@univ-orleans.fr>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004
00011  *     Christian Schulte, 2004
00012  *     Gabor Szokoli, 2004
00013  *
00014  *  Last modified:
00015  *     $Date: 2009-10-14 12:19:49 +0200 (Wed, 14 Oct 2009) $ by $Author: schulte $
00016  *     $Revision: 9909 $
00017  *
00018  *  This file is part of Gecode, the generic constraint
00019  *  development environment:
00020  *     http://www.gecode.org
00021  *
00022  *  Permission is hereby granted, free of charge, to any person obtaining
00023  *  a copy of this software and associated documentation files (the
00024  *  "Software"), to deal in the Software without restriction, including
00025  *  without limitation the rights to use, copy, modify, merge, publish,
00026  *  distribute, sublicense, and/or sell copies of the Software, and to
00027  *  permit persons to whom the Software is furnished to do so, subject to
00028  *  the following conditions:
00029  *
00030  *  The above copyright notice and this permission notice shall be
00031  *  included in all copies or substantial portions of the Software.
00032  *
00033  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00034  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00035  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00036  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00037  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00038  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00039  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00040  *
00041  */
00042 
00043 
00044 
00045 #include <gecode/set.hh>
00046 #include <gecode/int.hh>
00047 
00048 namespace Gecode { namespace Set { namespace Int {
00049 
00050   template<class View>
00051   forceinline
00052   MinElement<View>::MinElement(Home home, View y0, Gecode::Int::IntView y1)
00053     : IntSetPropagator<View,PC_SET_ANY,
00054                        Gecode::Int::PC_INT_BND> (home, y0, y1) {}
00055 
00056   template<class View>
00057   forceinline ExecStatus
00058   MinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00059     GECODE_ME_CHECK(x0.cardMin(home,1));
00060     (void) new (home) MinElement(home,x0,x1);
00061     return ES_OK;
00062   }
00063 
00064   template<class View>
00065   forceinline
00066   MinElement<View>::MinElement(Space& home, bool share, MinElement& p)
00067     : IntSetPropagator<View,PC_SET_ANY,
00068                        Gecode::Int::PC_INT_BND> (home, share, p) {}
00069 
00070   template<class View>
00071   Actor*
00072   MinElement<View>::copy(Space& home, bool share) {
00073    return new (home) MinElement(home,share,*this);
00074   }
00075 
00076   template<class View>
00077   ExecStatus
00078   MinElement<View>::propagate(Space& home, const ModEventDelta&) {
00079     //x1 is an element of x0.ub
00080     //x1 =< smallest element of x0.lb
00081     //x1 =< x0.cardinialityMin-est largest element of x0.ub
00082     //(these 2 take care of determined x0)
00083     //No element in x0 is smaller than x1
00084     //if x1 is determined, it is part of the ub.
00085 
00086     //Consequently:
00087     //The domain of x1 is a subset of x0.ub up to the first element in x0.lb.
00088     //x0 lacks everything smaller than smallest possible x1.
00089 
00090     {
00091       LubRanges<View> ub(x0);
00092       GECODE_ME_CHECK(x1.inter_r(home,ub,false));
00093     }
00094     GECODE_ME_CHECK(x1.lq(home,x0.glbMin()));
00095     //if cardMin>lbSize?
00096     assert(x0.cardMin()>=1);
00097 
00098     {
00100       int size = 0;
00101       int maxN = BndSet::MAX_OF_EMPTY;
00102       for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++size) {}
00103       Region r(home);
00104       int* ub = r.alloc<int>(size*2);
00105       int i=0;
00106       for (LubRanges<View> ubr(x0); ubr(); ++ubr, ++i) {
00107         ub[2*i]   = ubr.min();
00108         ub[2*i+1] = ubr.max();
00109       }
00110       int x0cm = x0.cardMin()-1;
00111       for (int i=size; i--;) {
00112         int width = ub[2*i+1]-ub[2*i]+1;
00113         if (width > x0cm) {
00114           maxN = ub[2*i+1]-x0cm;
00115           break;
00116         }
00117         x0cm -= width;
00118       }
00119       GECODE_ME_CHECK(x1.lq(home,maxN));
00120     }
00121 
00122     GECODE_ME_CHECK( x0.exclude(home,
00123                                 Limits::min, x1.min()-1) );
00124 
00125     if (x1.assigned()) {
00126       GECODE_ME_CHECK(x0.include(home,x1.val()));
00127       GECODE_ME_CHECK(x0.exclude(home,
00128                                  Limits::min, x1.val()-1));
00129       return ES_SUBSUMED(*this,home);
00130     }
00131 
00132     return ES_FIX;
00133   }
00134 
00135 
00136   template<class View>
00137   forceinline
00138   NotMinElement<View>::NotMinElement(Home home, View y0,
00139                                      Gecode::Int::IntView y1)
00140     : IntSetPropagator<View,PC_SET_ANY,
00141                        Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
00142 
00143   template<class View>
00144   forceinline ExecStatus
00145   NotMinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00146     (void) new (home) NotMinElement(home,x0,x1);
00147     return ES_OK;
00148   }
00149 
00150   template<class View>
00151   forceinline
00152   NotMinElement<View>::NotMinElement(Space& home, bool share,
00153                                      NotMinElement& p)
00154     : IntSetPropagator<View,PC_SET_ANY,
00155                        Gecode::Int::PC_INT_DOM> (home, share, p) {}
00156 
00157   template<class View>
00158   Actor*
00159   NotMinElement<View>::copy(Space& home, bool share) {
00160     return new (home) NotMinElement(home,share,*this);
00161   }
00162 
00163   template<class View>
00164   ExecStatus
00165   NotMinElement<View>::propagate(Space& home, const ModEventDelta&) {
00166     // cheap tests for entailment:
00167     // if x0 is empty, then entailed
00168     // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed
00169     // if min(x0.glb) < min(x1), then entailed
00170     if ((x0.cardMax() == 0) ||
00171         ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00172         ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
00173       return ES_SUBSUMED(*this, home);
00174     // if x1 is determined and = x0.lub.min: remove it from x0,
00175     // then entailed
00176     if (x1.assigned() && x1.val()==x0.lubMin()) {
00177       GECODE_ME_CHECK(x0.exclude(home,x1.val()));
00178       return ES_SUBSUMED(*this, home);
00179     }
00180     // if min(x0) is decided: remove min(x0) from the domain of x1
00181     // then entailed
00182     if (x0.glbMin() == x0.lubMin()) {
00183       GECODE_ME_CHECK(x1.nq(home,x0.glbMin()));
00184       return ES_SUBSUMED(*this, home);
00185     }
00186     // if x1 is determined and = x0.glb.min, then we need at least
00187     // one more element; if there is only one below, then we must
00188     // take it.
00189     if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMin()) {
00190       unsigned int oldGlbSize = x0.glbSize();
00191       // if there is only 1 unknown below x1, then we must take it
00192       UnknownRanges<View> ur(x0);
00193       assert(ur());
00194       // the iterator is not empty: otherwise x0 would be determined
00195       // and min(x0) would have been decided and the preceding if
00196       // would have caught it.  Also, the first range is not above
00197       // x1 otherwise the very first if would have caught it.
00198       // so let's check if the very first range of unknowns is of
00199       // size 1 and there is no second one or it starts above x1.
00200       if (ur.width()==1) {
00201         int i=ur.min();
00202         ++ur;
00203         if (!ur() || ur.min()>x1.val()) {
00204           GECODE_ME_CHECK(x0.include(home,i));
00205           return ES_SUBSUMED(*this, home);
00206         }
00207       }
00208       GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
00209     }
00210     // if dom(x1) and lub(x0) are disjoint, then entailed;
00211     {
00212       LubRanges<View> ub(x0);
00213       Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00214       Gecode::Iter::Ranges::Inter<LubRanges<View>,
00215         Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00216       if (!ir()) return ES_SUBSUMED(*this, home);
00217     }
00218     // x0 is fated to eventually contain at least x0.cardMin elements.
00219     // therefore min(x0) <= x0.cardMin-th largest element of x0.lub
00220     // if x1 > than that, then entailed.
00221     {
00222       // to find the x0.cardMin-th largest element of x0.lub, we need
00223       // some sort of reverse range iterator. we will need to fake one
00224       // by storing the ranges of the forward iterator in an array.
00225       // first we need to know how large the array needs to be. so, let's
00226       // count the ranges:
00227       int num_ranges = 0;
00228       for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {}
00229       // create an array for storing min and max of each range
00230       Region r(home);
00231       int* _ur = r.alloc<int>(num_ranges*2);
00232       // now, we fill the array:
00233       int i = 0;
00234       for (LubRanges<View> ur(x0); ur(); ++ur, ++i) {
00235         _ur[2*i  ] = ur.min();
00236         _ur[2*i+1] = ur.max();
00237       }
00238       // now we search from the top the range that contains the
00239       // nth largest value.
00240       int n = x0.cardMin();
00241       int nth_largest = BndSet::MAX_OF_EMPTY;
00242       for (int i=num_ranges; i--; ) {
00243         // number of values in range
00244         int num_values = _ur[2*i+1]-_ur[2*i]+1;
00245         // does the range contain the value?
00246         if (num_values >= n) {
00247           // record it and exit the loop
00248           nth_largest = _ur[2*i+1]-n+1;
00249           break;
00250         }
00251         // otherwise, we skipped num_values
00252         n -= num_values;
00253       }
00254       // if x1.min > nth_largest, then entailed
00255       if (x1.min() > nth_largest)
00256         return ES_SUBSUMED(*this, home);
00257     }
00258     return ES_FIX;
00259   }
00260 
00261   template<class View>
00262   forceinline
00263   ReMinElement<View>::ReMinElement(Home home, View y0, Gecode::Int::IntView y1,
00264                                    Gecode::Int::BoolView b2)
00265     : IntSetRePropagator<View,PC_SET_ANY,
00266                          Gecode::Int::PC_INT_DOM> (home, y0, y1, b2) {}
00267 
00268   template<class View>
00269   forceinline ExecStatus
00270   ReMinElement<View>::post(Home home, View x0, Gecode::Int::IntView x1,
00271                            Gecode::Int::BoolView b2) {
00272     (void) new (home) ReMinElement(home,x0,x1,b2);
00273     return ES_OK;
00274   }
00275 
00276   template<class View>
00277   forceinline
00278   ReMinElement<View>::ReMinElement(Space& home, bool share, ReMinElement& p)
00279     : IntSetRePropagator<View,PC_SET_ANY,
00280                        Gecode::Int::PC_INT_DOM> (home, share, p) {}
00281 
00282   template<class View>
00283   Actor*
00284   ReMinElement<View>::copy(Space& home, bool share) {
00285    return new (home) ReMinElement(home,share,*this);
00286   }
00287 
00288   template<class View>
00289   ExecStatus
00290   ReMinElement<View>::propagate(Space& home, const ModEventDelta&) {
00291     // check if b is determined
00292     if (b.one())
00293       GECODE_REWRITE(*this, (MinElement<View>::post(home(*this),x0,x1)));
00294     if (b.zero())
00295       GECODE_REWRITE(*this, (NotMinElement<View>::post(home(*this),x0,x1)));
00296     // cheap tests for => b=0
00297     // if x0 is empty, then b=0 and entailed
00298     // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed
00299     // if min(x0.glb) < min(x1), then b=0 and entailed
00300     if ((x0.cardMax() == 0) ||
00301         ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00302         ((x0.glbSize() > 0) && (x0.glbMin() < x1.min())))
00303       {
00304         GECODE_ME_CHECK(b.zero(home));
00305         return ES_SUBSUMED(*this, home);
00306       }
00307     // if min(x0) is decided
00308     if (x0.glbMin() == x0.lubMin()) {
00309       // if x1 is det: check if = min(x0), assign b, entailed
00310       if (x1.assigned()) {
00311         if (x1.val() == x0.glbMin()) {
00312           GECODE_ME_CHECK(b.one(home));
00313         } else {
00314           GECODE_ME_CHECK(b.zero(home));
00315         }
00316         return ES_SUBSUMED(*this, home);
00317       }
00318       // if min(x0) not in dom(x1): b=0, entailed
00319       else if ((x0.glbMin() < x1.min()) ||
00320                (x0.glbMin() > x1.max()) ||
00321                !x1.in(x0.glbMin()))
00322         {
00323           GECODE_ME_CHECK(b.zero(home));
00324           return ES_SUBSUMED(*this, home);
00325         }
00326     }
00327     // // if dom(x1) and lub(x0) are disjoint, then b=0, entailed;
00328     // {
00329     //   LubRanges<View> ub(x0);
00330     //   Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00331     //   Gecode::Iter::Ranges::Inter<LubRanges<View>,
00332     //     Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00333     //   if (!ir()) {
00334     //     GECODE_ME_CHECK(b.zero(home));
00335     //     return ES_SUBSUMED(*this, home);
00336     //   }
00337     // }
00338     // // x0 is fated to eventually contain at least x0.cardMin elements.
00339     // // therefore min(x0) <= x0.cardMin-th largest element of x0.lub
00340     // // if x1 > than that, then b=0 and entailed.
00341     // {
00342     //   // to find the x0.cardMin-th largest element of x0.lub, we need
00343     //   // some sort of reverse range iterator. we will need to fake one
00344     //   // by storing the ranges of the forward iterator in an array.
00345     //   // first we need to know how large the array needs to be. so, let's
00346     //   // count the ranges:
00347     //   int num_ranges = 0;
00348     //   for (LubRanges<View> ur(x0); ur(); ++ur, ++num_ranges) {}
00349     //   // create an array for storing min and max of each range
00350     //   Region re(home);
00351     //   int* _ur = re.alloc<int>(num_ranges*2);
00352     //   // now, we fill the array:
00353     //   int i = 0;
00354     //   for (LubRanges<View> ur(x0); ur(); ++ur, ++i) {
00355     //     _ur[2*i  ] = ur.min();
00356     //     _ur[2*i+1] = ur.max();
00357     //   }
00358     //   // now we search from the top the range that contains the
00359     //   // nth largest value.
00360     //   int n = x0.cardMin();
00361     //   int nth_largest = BndSet::MAX_OF_EMPTY;
00362     //   for (int i=num_ranges; i--; ) {
00363     //     // number of values in range
00364     //     int num_values = _ur[2*i+1]-_ur[2*i]+1;
00365     //     // does the range contain the value?
00366     //     if (num_values >= n)
00367     //       {
00368     //         // record it and exit the loop
00369     //         nth_largest = _ur[2*i+1]-n+1;
00370     //         break;
00371     //       }
00372     //     // otherwise, we skipped num_values
00373     //     n -= num_values;
00374     //   }
00375     //   // if x1.min > nth_largest, then entailed
00376     //   if (x1.min() > nth_largest) {
00377     //     GECODE_ME_CHECK(b.zero(home));
00378     //     return ES_SUBSUMED(*this, home);
00379     //   }
00380     // }
00381     return ES_FIX;
00382   }
00383 
00384   template<class View>
00385   forceinline
00386   MaxElement<View>::MaxElement(Home home, View y0, Gecode::Int::IntView y1)
00387     : IntSetPropagator<View,PC_SET_ANY,
00388                        Gecode::Int::PC_INT_BND> (home, y0, y1) {}
00389 
00390   template<class View>
00391   forceinline
00392   MaxElement<View>::MaxElement(Space& home, bool share, MaxElement& p)
00393     : IntSetPropagator<View,PC_SET_ANY,
00394                        Gecode::Int::PC_INT_BND> (home, share, p) {}
00395 
00396   template<class View>
00397   ExecStatus
00398   MaxElement<View>::post(Home home, View x0,
00399                               Gecode::Int::IntView x1) {
00400     GECODE_ME_CHECK(x0.cardMin(home,1));
00401     (void) new (home) MaxElement(home,x0,x1);
00402     return ES_OK;
00403   }
00404 
00405   template<class View>
00406   Actor*
00407   MaxElement<View>::copy(Space& home, bool share) {
00408     return new (home) MaxElement(home,share,*this);
00409   }
00410 
00411   template<class View>
00412   ExecStatus
00413   MaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00414     LubRanges<View> ub(x0);
00415     GECODE_ME_CHECK(x1.inter_r(home,ub,false));
00416     GECODE_ME_CHECK(x1.gq(home,x0.glbMax()));
00417     assert(x0.cardMin()>=1);
00418     GECODE_ME_CHECK(x1.gq(home,x0.lubMinN(x0.cardMin()-1)));
00419     GECODE_ME_CHECK(x0.exclude(home,
00420                                x1.max()+1,Limits::max) );
00421 
00422     if (x1.assigned()) {
00423       GECODE_ME_CHECK(x0.include(home,x1.val()));
00424       GECODE_ME_CHECK( x0.exclude(home,
00425                                   x1.val()+1,Limits::max) );
00426       return ES_SUBSUMED(*this,home);
00427     }
00428 
00429     return ES_FIX;
00430   }
00431 
00432   template<class View>
00433   forceinline
00434   NotMaxElement<View>::NotMaxElement(Home home, View y0,
00435                                      Gecode::Int::IntView y1)
00436     : IntSetPropagator<View,PC_SET_ANY,
00437                        Gecode::Int::PC_INT_DOM> (home, y0, y1) {}
00438 
00439   template<class View>
00440   forceinline
00441   NotMaxElement<View>::NotMaxElement(Space& home, bool share,
00442                                      NotMaxElement& p)
00443     : IntSetPropagator<View,PC_SET_ANY,
00444                        Gecode::Int::PC_INT_DOM> (home, share, p) {}
00445 
00446   template<class View>
00447   ExecStatus
00448   NotMaxElement<View>::post(Home home, View x0, Gecode::Int::IntView x1) {
00449     (void) new (home) NotMaxElement(home,x0,x1);
00450     return ES_OK;
00451   }
00452 
00453   template<class View>
00454   Actor*
00455   NotMaxElement<View>::copy(Space& home, bool share) {
00456     return new (home) NotMaxElement(home,share,*this);
00457   }
00458 
00459   template<class View>
00460   ExecStatus
00461   NotMaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00462     // cheap tests for entailment:
00463     // if x0 is empty, then entailed
00464     // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then entailed
00465     // if max(x0.glb) > max(x1), then entailed
00466     if ((x0.cardMax() == 0) ||
00467         ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00468         ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
00469       return ES_SUBSUMED(*this, home);
00470     // if x1 is determined and = max(x0.lub): remove it from x0,
00471     // then entailed
00472     if (x1.assigned() && x1.val()==x0.lubMax()) {
00473       GECODE_ME_CHECK(x0.exclude(home,x1.val()));
00474       return ES_SUBSUMED(*this, home);
00475     }
00476     // if max(x0) is decided: remove max(x0) from the domain of x1
00477     // then entailed
00478     if (x0.glbMax() == x0.lubMax()) {
00479       GECODE_ME_CHECK(x1.nq(home,x0.glbMax()));
00480       return ES_SUBSUMED(*this, home);
00481     }
00482     // if x1 is determined and = max(x0.glb), then we need at least
00483     // one more element; if there is only one above, then we must
00484     // take it.
00485     if (x1.assigned() && x0.glbSize() > 0 && x1.val()==x0.glbMax()) {
00486       unsigned int oldGlbSize = x0.glbSize();
00487       // if there is only 1 unknown above x1, then we must take it
00488       UnknownRanges<View> ur(x0);
00489       // there is at least one unknown above x1 otherwise it would
00490       // have been caught by the if for x1=max(x0.lub)
00491       while (ur.max() < x1.val()) {
00492         assert(ur());
00493         ++ur;
00494       };
00495       // if the first range above x1 contains just 1 element,
00496       // and is the last range, then take that element
00497       if (ur.width() == 1) {
00498         int i = ur.min();
00499         ++ur;
00500         if (!ur()) {
00501           // last range
00502           GECODE_ME_CHECK(x0.include(home,i));
00503           return ES_SUBSUMED(*this, home);
00504         }
00505       }
00506       GECODE_ME_CHECK(x0.cardMin(home, oldGlbSize+1));
00507     }
00508     // if dom(x1) and lub(x0) are disjoint, then entailed
00509     {
00510       LubRanges<View> ub(x0);
00511       Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00512       Gecode::Iter::Ranges::Inter<LubRanges<View>,
00513         Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00514       if (!ir()) return ES_SUBSUMED(*this, home);
00515     }
00516     // x0 is fated to eventually contain at least x0.cardMin elements.
00517     // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub.
00518     // if x1 < than that, then entailed.
00519     {
00520       unsigned int n = x0.cardMin();
00521       int nth_smallest = BndSet::MIN_OF_EMPTY;
00522       for (LubRanges<View> ur(x0); ur(); ++ur) {
00523         if (ur.width() >= n) {
00524           // record it and exit the loop
00525           nth_smallest = ur.min() + n - 1;
00526           break;
00527         }
00528         // otherwise, we skipped ur.width() values
00529         n -= ur.width();
00530       }
00531       // if x1.max < nth_smallest, then entailed
00532       if (x1.max() < nth_smallest)
00533         return ES_SUBSUMED(*this, home);
00534     }
00535     return ES_FIX;
00536   }
00537 
00538   template<class View>
00539   forceinline
00540   ReMaxElement<View>::ReMaxElement(Home home, View y0, Gecode::Int::IntView y1,
00541                                    Gecode::Int::BoolView b2)
00542     : IntSetRePropagator<View,PC_SET_ANY,
00543                          Gecode::Int::PC_INT_DOM> (home, y0, y1, b2) {}
00544 
00545   template<class View>
00546   forceinline
00547   ReMaxElement<View>::ReMaxElement(Space& home, bool share, ReMaxElement& p)
00548     : IntSetRePropagator<View,PC_SET_ANY,
00549                        Gecode::Int::PC_INT_DOM> (home, share, p) {}
00550 
00551   template<class View>
00552   ExecStatus
00553   ReMaxElement<View>::post(Home home, View x0,
00554                            Gecode::Int::IntView x1,
00555                            Gecode::Int::BoolView b2) {
00556     (void) new (home) ReMaxElement(home,x0,x1,b2);
00557     return ES_OK;
00558   }
00559 
00560   template<class View>
00561   Actor*
00562   ReMaxElement<View>::copy(Space& home, bool share) {
00563     return new (home) ReMaxElement(home,share,*this);
00564   }
00565 
00566   template<class View>
00567   ExecStatus
00568   ReMaxElement<View>::propagate(Space& home, const ModEventDelta&) {
00569     // check if b is determined
00570     if (b.one())
00571       GECODE_REWRITE(*this, (MaxElement<View>::post(home(*this),x0,x1)));
00572     if (b.zero())
00573       GECODE_REWRITE(*this, (NotMaxElement<View>::post(home(*this),x0,x1)));
00574     // cheap tests for => b=0
00575     // if x0 is empty, then b=0 and entailed
00576     // if max(x1) < min(x0.lub) or min(x1) > max(x0.lub), then b=0 and entailed
00577     // if max(x0.glb) > max(x1), then b=0 and entailed
00578     if ((x0.cardMax() == 0) ||
00579         ((x1.max() < x0.lubMin()) || (x1.min() > x0.lubMax())) ||
00580         ((x0.glbSize() > 0) && (x0.glbMax() > x1.max())))
00581       {
00582         GECODE_ME_CHECK(b.zero(home));
00583         return ES_SUBSUMED(*this, home);
00584       }
00585     // if max(x0) is decided
00586     if (x0.glbMax() == x0.lubMax()) {
00587       // if x1 is det: check if = max(x0), assign b, entailed
00588       if (x1.assigned()) {
00589         if (x1.val() == x0.glbMax()) {
00590           GECODE_ME_CHECK(b.one(home));
00591         } else {
00592           GECODE_ME_CHECK(b.zero(home));
00593         }
00594         return ES_SUBSUMED(*this, home);
00595       }
00596       // if max(x0) not in dom(x1): b=0, entailed
00597       else if ((x0.glbMax() < x1.min()) ||
00598                (x0.glbMax() > x1.max()) ||
00599                !x1.in(x0.glbMax()))
00600         {
00601           GECODE_ME_CHECK(b.zero(home));
00602           return ES_SUBSUMED(*this, home);
00603         }
00604     }
00605     // if dom(x1) and lub(x0) are disjoint, then b=0, entailed
00606     {
00607       LubRanges<View> ub(x0);
00608       Gecode::Int::ViewRanges<Gecode::Int::IntView> d(x1);
00609       Gecode::Iter::Ranges::Inter<LubRanges<View>,
00610         Gecode::Int::ViewRanges<Gecode::Int::IntView> > ir(ub,d);
00611       if (!ir()) {
00612         GECODE_ME_CHECK(b.zero(home));
00613         return ES_SUBSUMED(*this, home);
00614       }
00615     }
00616     // x0 is fated to eventually contain at least x0.cardMin elements.
00617     // therefore max(x0) >= x0.cardMin-th smallest element of x0.lub.
00618     // if x1 < than that, then b=0, entailed.
00619     {
00620       unsigned int n = x0.cardMin();
00621       int nth_smallest = BndSet::MIN_OF_EMPTY;
00622       for (LubRanges<View> ur(x0); ur(); ++ur) {
00623         if (ur.width() >= n)
00624           {
00625             // record it and exit the loop
00626             nth_smallest = ur.min() + n - 1;
00627             break;
00628           }
00629         // otherwise, we skipped ur.width() values
00630         n -= ur.width();
00631       }
00632       // if x1.max < nth_smallest, then entailed
00633       if (x1.max() < nth_smallest) {
00634         GECODE_ME_CHECK(b.zero(home));
00635         return ES_SUBSUMED(*this, home);
00636       }
00637     }
00638     return ES_FIX;
00639   }
00640 
00641 }}}
00642 
00643 // STATISTICS: set-prop