Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

hull.cc

Go to the documentation of this file.
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: 2005-11-24 18:03:01 +0100 (Thu, 24 Nov 2005) $ by $Author: tack $
00016  *     $Revision: 2639 $
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 #include "set.hh"
00029 #include "set/convex.hh"
00030 
00031 namespace Gecode { namespace Set { namespace Convex {
00032 
00033   Actor*
00034   ConvexHull::copy(Space* home, bool share) {
00035     return new (home) ConvexHull(home,share,*this);
00036   }
00037 
00038   PropCost
00039   ConvexHull::cost(void) const {
00040     return PC_BINARY_HI;
00041   }
00042 
00043   ConvexHull::~ConvexHull(void) {
00044     x0.cancel(this,PC_SET_CGLB);
00045     x1.cancel(this,PC_SET_ANY);
00046   }
00047 
00048   ExecStatus
00049   ConvexHull::propagate(Space* home) {
00050     //x1 is the convex hull of x0
00051 
00052     GECODE_ME_CHECK( x1.cardMin(home,x0.cardMin()) );
00053     GECODE_ME_CHECK( x0.cardMax(home,x1.cardMax()) );
00054 
00055     do {
00056 
00057       //intersect x1 with (x0.lubMin(),x0.lubMax())
00058       //This empties x1 if x0.ub is empty. twice.
00059       GECODE_ME_CHECK( x1.exclude(home,Limits::Set::int_min,
00060                                   x0.lubMin()-1) );
00061       GECODE_ME_CHECK( x1.exclude(home,x0.lubMax()+1,
00062                                   Limits::Set::int_max) );
00063 
00064       int minElement = std::min(x1.glbMin(),x0.glbMin());
00065       int maxElement = std::max(x1.glbMax(),x0.glbMax());
00066 
00067       if (minElement<maxElement) {
00068         GECODE_ME_CHECK( x1.include(home, minElement, maxElement));
00069       }
00070 
00071       unsigned int cardMin = x1.cardMin();
00072 
00073       LubRanges<SetView> ubRangeIt(x1);
00074       Iter::Ranges::Cache< LubRanges<SetView> > ubRangeItC(ubRangeIt);
00075       for (;ubRangeItC();++ubRangeItC){
00076         if (ubRangeItC.width() < cardMin
00077             || ubRangeItC.min() > minElement //No need to test for empty lb.
00078             || ubRangeItC.max() < maxElement
00079             ) {
00080           GECODE_ME_CHECK( x1.exclude(home,
00081                                       ubRangeItC.min(), ubRangeItC.max()) );
00082         }
00083       }
00084 
00085       LubRanges<SetView> ubRangeIt2(x1);
00086       GECODE_ME_CHECK(x0.intersectI(home,ubRangeIt2) );
00087 
00088       if (x1.lubMin()!=BndSet::MIN_OF_EMPTY) {
00089         if(x1.lubMin()==x1.glbMin()) {
00090               GECODE_ME_CHECK(x0.include(home,x1.lubMin()));
00091         }
00092         if(x1.lubMax()==x1.glbMax()) {
00093               GECODE_ME_CHECK(x0.include(home,x1.lubMax()));
00094         }
00095       }
00096     } while(x0.assigned()&&!x1.assigned());
00097     
00098     //If x0 is assigned, x1 should be too.
00099     assert(x1.assigned() || !x0.assigned());
00100 
00101     if (x1.assigned()) {
00102       return ES_SUBSUMED;
00103     }
00104 
00105     return shared(x0,x1) ? ES_NOFIX : ES_FIX;
00106   }
00107 
00108 }}}
00109 
00110 // STATISTICS: set-prop