minmax.cc

00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Gabor Szokoli <szokoli@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004
00011  *     Christian Schulte, 2004
00012  *     Gabor Szokoli, 2004
00013  *
00014  *  Last modified:
00015  *     $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
00016  *     $Revision: 3188 $
00017  *
00018  *  This file is part of Gecode, the generic constraint
00019  *  development environment:
00020  *     http://www.gecode.org
00021  *
00022  *  See the file "LICENSE" for information on usage and
00023  *  redistribution of this file, and for a
00024  *     DISCLAIMER OF ALL WARRANTIES.
00025  *
00026  */
00027 
00028 
00029 
00030 #include "gecode/set/int.hh"
00031 
00032 #include "gecode/iter.hh"
00033 
00034 #include "gecode/set/rel.hh"
00035 
00036 namespace Gecode { namespace Set { namespace Int {
00037 
00038   Actor*
00039   MinElement::copy(Space* home, bool share) {
00040     return new (home) MinElement(home,share,*this);
00041   }
00042 
00043   ExecStatus
00044   MinElement::propagate(Space* home) {
00045     //x1 is an element of x0.ub
00046     //x1 =< smallest element of x0.lb
00047     //x1 =< x0.cardinialityMin-est largest element of x0.ub
00048     //(these 2 take care of determined x0)
00049     //No element in x0 is smaller than x1
00050     //if x1 is determined, it is part of the ub.
00051 
00052     //Consequently:
00053     //The domain of x1 is a subset of x0.ub up to the first element in x0.lb.
00054     //x0 lacks everything smaller than smallest possible x1.
00055 
00056     LubRanges<SetView> ub(x0);
00057     GECODE_ME_CHECK(x1.inter(home,ub));
00058     GECODE_ME_CHECK(x1.lq(home,x0.glbMin()));
00059     //if cardMin>lbSize?
00060     assert(x0.cardMin()>=1);
00061     GECODE_ME_CHECK(x1.lq(home,x0.lubMaxN(x0.cardMin()-1)));
00062     GECODE_ME_CHECK( x0.exclude(home,
00063                                 Limits::Set::int_min, x1.min()-1) );
00064 
00065     if (x1.assigned()) {
00066       GECODE_ME_CHECK(x0.include(home,x1.val()));
00067       GECODE_ME_CHECK(x0.exclude(home,
00068                                  Limits::Set::int_min, x1.val()-1));
00069       return ES_SUBSUMED;
00070     }
00071 
00072     return ES_FIX;
00073   }
00074 
00075   ExecStatus MaxElement::post(Space* home, SetView x0,
00076                               Gecode::Int::IntView x1) {
00077     GECODE_ME_CHECK(x0.cardMin(home,1));
00078     (void) new (home) MaxElement(home,x0,x1);
00079     return ES_OK;
00080   }
00081 
00082   Actor*
00083   MaxElement::copy(Space* home, bool share) {
00084     return new (home) MaxElement(home,share,*this);
00085   }
00086 
00087   ExecStatus
00088   MaxElement::propagate(Space* home) {
00089     LubRanges<SetView> ub(x0);
00090     GECODE_ME_CHECK(x1.inter(home,ub));
00091     GECODE_ME_CHECK(x1.gq(home,x0.glbMax()));
00092     assert(x0.cardMin()>=1);
00093     GECODE_ME_CHECK(x1.gq(home,x0.lubMinN(x0.cardMin()-1)));
00094     GECODE_ME_CHECK(x0.exclude(home,
00095                                x1.max()+1,Limits::Set::int_max) );
00096 
00097     if (x1.assigned()) {
00098       GECODE_ME_CHECK(x0.include(home,x1.val()));
00099       GECODE_ME_CHECK( x0.exclude(home,
00100                                   x1.val()+1,Limits::Set::int_max) );
00101       return ES_SUBSUMED;
00102     }
00103 
00104     return ES_FIX;
00105   }
00106 
00107 }}}
00108 
00109 // STATISTICS: set-prop