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 "gecode/set.hh"
00029 #include "gecode/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 ExecStatus
00039 ConvexHull::propagate(Space* home) {
00040
00041
00042 GECODE_ME_CHECK( x1.cardMin(home,x0.cardMin()) );
00043 GECODE_ME_CHECK( x0.cardMax(home,x1.cardMax()) );
00044
00045 do {
00046
00047
00048
00049 GECODE_ME_CHECK( x1.exclude(home,Limits::Set::int_min,
00050 x0.lubMin()-1) );
00051 GECODE_ME_CHECK( x1.exclude(home,x0.lubMax()+1,
00052 Limits::Set::int_max) );
00053
00054 int minElement = std::min(x1.glbMin(),x0.glbMin());
00055 int maxElement = std::max(x1.glbMax(),x0.glbMax());
00056
00057 if (minElement<maxElement) {
00058 GECODE_ME_CHECK( x1.include(home, minElement, maxElement));
00059 }
00060
00061 unsigned int cardMin = x1.cardMin();
00062
00063 LubRanges<SetView> ubRangeIt(x1);
00064 Iter::Ranges::Cache< LubRanges<SetView> > ubRangeItC(ubRangeIt);
00065 for (;ubRangeItC();++ubRangeItC){
00066 if (ubRangeItC.width() < cardMin
00067 || ubRangeItC.min() > minElement
00068 || ubRangeItC.max() < maxElement
00069 ) {
00070 GECODE_ME_CHECK( x1.exclude(home,
00071 ubRangeItC.min(), ubRangeItC.max()) );
00072 }
00073 }
00074
00075 LubRanges<SetView> ubRangeIt2(x1);
00076 GECODE_ME_CHECK(x0.intersectI(home,ubRangeIt2) );
00077
00078 if (x1.lubMin()!=BndSet::MIN_OF_EMPTY) {
00079 if(x1.lubMin()==x1.glbMin()) {
00080 GECODE_ME_CHECK(x0.include(home,x1.lubMin()));
00081 }
00082 if(x1.lubMax()==x1.glbMax()) {
00083 GECODE_ME_CHECK(x0.include(home,x1.lubMax()));
00084 }
00085 }
00086 } while(x0.assigned()&&!x1.assigned());
00087
00088
00089 assert(x1.assigned() || !x0.assigned());
00090
00091 if (x1.assigned()) {
00092 return ES_SUBSUMED;
00093 }
00094
00095 return ES_NOFIX;
00096 }
00097
00098 }}}
00099
00100