hull.cc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
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
00051
00052 GECODE_ME_CHECK( x1.cardMin(home,x0.cardMin()) );
00053 GECODE_ME_CHECK( x0.cardMax(home,x1.cardMax()) );
00054
00055 do {
00056
00057
00058
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
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
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