hull.cpp
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
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #include <gecode/set/convex.hh>
00041
00042 namespace Gecode { namespace Set { namespace Convex {
00043
00044 Actor*
00045 ConvexHull::copy(Space& home) {
00046 return new (home) ConvexHull(home,*this);
00047 }
00048
00049 ExecStatus
00050 ConvexHull::propagate(Space& home, const ModEventDelta&) {
00051
00052
00053 GECODE_ME_CHECK( x1.cardMin(home,x0.cardMin()) );
00054 GECODE_ME_CHECK( x0.cardMax(home,x1.cardMax()) );
00055
00056 do {
00057
00058
00059
00060 GECODE_ME_CHECK( x1.exclude(home,Limits::min,
00061 x0.lubMin()-1) );
00062 GECODE_ME_CHECK( x1.exclude(home,x0.lubMax()+1,
00063 Limits::max) );
00064
00065 int minElement = std::min(x1.glbMin(),x0.glbMin());
00066 int maxElement = std::max(x1.glbMax(),x0.glbMax());
00067
00068 if (minElement<maxElement) {
00069 GECODE_ME_CHECK( x1.include(home, minElement, maxElement));
00070 }
00071
00072 unsigned int cardMin = x1.cardMin();
00073
00074 Region r;
00075 LubRanges<SetView> ubRangeIt(x1);
00076 Iter::Ranges::Cache ubRangeItC(r,ubRangeIt);
00077 for (;ubRangeItC();++ubRangeItC) {
00078 if (ubRangeItC.width() < cardMin
00079 || ubRangeItC.min() > minElement
00080 || ubRangeItC.max() < maxElement
00081 ) {
00082 GECODE_ME_CHECK( x1.exclude(home,
00083 ubRangeItC.min(), ubRangeItC.max()) );
00084 }
00085 }
00086
00087 LubRanges<SetView> ubRangeIt2(x1);
00088 GECODE_ME_CHECK(x0.intersectI(home,ubRangeIt2) );
00089
00090 if (x1.lubMin()!=BndSet::MIN_OF_EMPTY) {
00091 if(x1.lubMin()==x1.glbMin()) {
00092 GECODE_ME_CHECK(x0.include(home,x1.lubMin()));
00093 }
00094 if(x1.lubMax()==x1.glbMax()) {
00095 GECODE_ME_CHECK(x0.include(home,x1.lubMax()));
00096 }
00097 }
00098 } while(x0.assigned()&&!x1.assigned());
00099
00100
00101 assert(x1.assigned() || !x0.assigned());
00102
00103 if (x1.assigned()) {
00104 return home.ES_SUBSUMED(*this);
00105 }
00106
00107 return ES_NOFIX;
00108 }
00109
00110 }}}
00111
00112