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 namespace Gecode { namespace Set {
00041
00042
00043
00044
00045
00046
00047 forceinline
00048 SetVarImp::SetVarImp(Space& home)
00049 : SetVarImpBase(home), lub(home), glb(home) {
00050 lub.card(Limits::card);
00051 assert(lub.card()==lub.size());
00052 }
00053
00054 forceinline
00055 SetVarImp::SetVarImp(Space& home,int lbMin,int lbMax,int ubMin,int ubMax,
00056 unsigned int cardMin, unsigned int cardMax)
00057 : SetVarImpBase(home),
00058 lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) {
00059 glb.card(std::max(cardMin, glb.size() ));
00060 lub.card(std::min(cardMax, lub.size() ));
00061 }
00062
00063 forceinline
00064 SetVarImp::SetVarImp(Space& home,
00065 const IntSet& theGlb,int ubMin,int ubMax,
00066 unsigned int cardMin, unsigned int cardMax)
00067 : SetVarImpBase(home),
00068 lub(home,ubMin,ubMax), glb(home,theGlb) {
00069 glb.card(std::max(cardMin, glb.size() ));
00070 lub.card(std::min(cardMax, lub.size() ));
00071 }
00072
00073 forceinline
00074 SetVarImp::SetVarImp(Space& home,
00075 int lbMin,int lbMax,const IntSet& theLub,
00076 unsigned int cardMin, unsigned int cardMax)
00077 : SetVarImpBase(home),
00078 lub(home,theLub), glb(home,lbMin,lbMax) {
00079 glb.card(std::max(cardMin, glb.size() ));
00080 lub.card(std::min(cardMax, lub.size() ));
00081 }
00082
00083 forceinline
00084 SetVarImp::SetVarImp(Space& home,
00085 const IntSet& theGlb,const IntSet& theLub,
00086 unsigned int cardMin, unsigned int cardMax)
00087 : SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) {
00088 glb.card(std::max(cardMin, glb.size() ));
00089 lub.card(std::min(cardMax, lub.size() ));
00090 }
00091
00092
00093 forceinline bool
00094 SetVarImp::assigned(void) const {
00095 return glb.size() == lub.size();
00096 }
00097
00098 forceinline unsigned int
00099 SetVarImp::cardMin(void) const { return glb.card(); }
00100
00101 forceinline unsigned int
00102 SetVarImp::cardMax(void) const { return lub.card(); }
00103
00104 forceinline bool
00105 SetVarImp::knownIn(int i) const { return (glb.in(i)); }
00106
00107 forceinline bool
00108 SetVarImp::knownOut(int i) const { return !(lub.in(i)); }
00109
00110 forceinline int
00111 SetVarImp::lubMin(void) const { return lub.min(); }
00112
00113 forceinline int
00114 SetVarImp::lubMax(void) const { return lub.max(); }
00115
00116 forceinline int
00117 SetVarImp::lubMinN(unsigned int n) const { return lub.minN(n); }
00118
00119 forceinline int
00120 SetVarImp::glbMin(void) const { return glb.min(); }
00121
00122 forceinline int
00123 SetVarImp::glbMax(void) const { return glb.max(); }
00124
00125 forceinline unsigned int
00126 SetVarImp::glbSize() const { return glb.size(); }
00127
00128 forceinline unsigned int
00129 SetVarImp::lubSize() const { return lub.size(); }
00130
00131
00132
00133
00134
00135 forceinline int
00136 SetVarImp::glbMin(const Delta& d) {
00137 return static_cast<const SetDelta&>(d).glbMin();
00138 }
00139 forceinline int
00140 SetVarImp::glbMax(const Delta& d) {
00141 return static_cast<const SetDelta&>(d).glbMax();
00142 }
00143 forceinline bool
00144 SetVarImp::glbAny(const Delta& d) {
00145 return static_cast<const SetDelta&>(d).glbAny();
00146 }
00147 forceinline int
00148 SetVarImp::lubMin(const Delta& d) {
00149 return static_cast<const SetDelta&>(d).lubMin();
00150 }
00151 forceinline int
00152 SetVarImp::lubMax(const Delta& d) {
00153 return static_cast<const SetDelta&>(d).lubMax();
00154 }
00155 forceinline bool
00156 SetVarImp::lubAny(const Delta& d) {
00157 return static_cast<const SetDelta&>(d).lubAny();
00158 }
00159
00160 forceinline ModEvent
00161 SetVarImp::cardMin(Space& home,unsigned int newMin) {
00162 if (cardMin() >= newMin)
00163 return ME_SET_NONE;
00164 if (newMin > cardMax())
00165 return fail(home);
00166 glb.card(newMin);
00167 return cardMin_full(home);
00168 }
00169
00170 forceinline ModEvent
00171 SetVarImp::cardMax(Space& home,unsigned int newMax) {
00172 if (cardMax() <= newMax)
00173 return ME_SET_NONE;
00174 if (cardMin() > newMax)
00175 return fail(home);
00176 lub.card(newMax);
00177 return cardMax_full(home);
00178 }
00179
00180 forceinline ModEvent
00181 SetVarImp::intersect(Space& home,int i, int j) {
00182 BndSetRanges lb(glb);
00183 Iter::Ranges::Singleton s(i,j);
00184 Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s);
00185 if (probe())
00186 return fail(home);
00187 if (assigned())
00188 return ME_SET_NONE;
00189 int oldMin = lub.min();
00190 int oldMax = lub.max();
00191 if (lub.intersect(home, i, j)) {
00192 SetDelta d;
00193 if (i == oldMin) {
00194 d._lubMin = lub.max()+1;
00195 d._lubMax = oldMax;
00196 } else if (j == oldMax) {
00197 d._lubMin = oldMin;
00198 d._lubMax = lub.min()-1;
00199 }
00200 return processLubChange(home, d);
00201 }
00202 return ME_SET_NONE;
00203 }
00204
00205 forceinline ModEvent
00206 SetVarImp::intersect(Space& home,int i) {
00207 return intersect(home, i, i);
00208 }
00209
00210 template<class I>
00211 inline ModEvent
00212 SetVarImp::intersectI(Space& home, I& iterator) {
00213 if (assigned()) {
00214 BndSetRanges lbi(glb);
00215 Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
00216 if (probe())
00217 return fail(home);
00218 return ME_SET_NONE;
00219 }
00220 if (!iterator()) {
00221 if (cardMin() > 0)
00222 return fail(home);
00223 lub.card(0);
00224 SetDelta d(1, 0, lub.min(), lub.max());
00225 lub.excludeAll(home);
00226 return notify(home, ME_SET_VAL, d);
00227 }
00228 int mi=iterator.min();
00229 int ma=iterator.max();
00230 ++iterator;
00231 if (iterator())
00232 return intersectI_full(home, mi, ma, iterator);
00233 else
00234 return intersect(home, mi, ma);
00235 }
00236
00237 template<class I>
00238 ModEvent
00239 SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
00240 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00241 if (lub.intersectI(home, si)) {
00242 BndSetRanges ub(lub);
00243 BndSetRanges lb(glb);
00244 if (!Iter::Ranges::subset(lb,ub)) {
00245 glb.become(home, lub);
00246 glb.card(glb.size());
00247 lub.card(glb.size());
00248 return fail(home);
00249 }
00250 ModEvent me = ME_SET_LUB;
00251 if (cardMax() > lub.size()) {
00252 lub.card(lub.size());
00253 if (cardMin() > cardMax()) {
00254 glb.become(home, lub);
00255 glb.card(glb.size());
00256 lub.card(glb.size());
00257 return fail(home);
00258 }
00259 me = ME_SET_CLUB;
00260 }
00261 if (cardMax() == lub.size() && cardMin() == cardMax()) {
00262 glb.become(home, lub);
00263 me = ME_SET_VAL;
00264 }
00265 SetDelta d;
00266 return notify(home, me, d);
00267 }
00268 return ME_SET_NONE;
00269 }
00270
00271 forceinline ModEvent
00272 SetVarImp::include(Space& home, int i, int j) {
00273 if (j<i)
00274 return ME_SET_NONE;
00275 BndSetRanges ub(lub);
00276 Iter::Ranges::Singleton sij(i,j);
00277 if (!Iter::Ranges::subset(sij,ub)) {
00278 return fail(home);
00279 }
00280 SetDelta d;
00281 if (glb.include(home, i, j, d))
00282 return processGlbChange(home, d);
00283 return ME_SET_NONE;
00284 }
00285
00286 forceinline ModEvent
00287 SetVarImp::include(Space& home, int i) {
00288 return include(home, i, i);
00289 }
00290
00291 template<class I> forceinline ModEvent
00292 SetVarImp::includeI(Space& home, I& iterator) {
00293 if (!iterator()) {
00294 return ME_SET_NONE;
00295 }
00296 if (assigned()) {
00297 BndSetRanges lbi(glb);
00298 Iter::Ranges::Diff<I,BndSetRanges>
00299 probe(iterator,lbi);
00300 return probe() ? fail(home) : ME_SET_NONE;
00301 }
00302 int mi=iterator.min();
00303 int ma=iterator.max();
00304 ++iterator;
00305 if (iterator())
00306 return includeI_full(home, mi, ma, iterator);
00307 else
00308 return include(home, mi, ma);
00309 }
00310
00311 template<class I>
00312 ModEvent
00313 SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
00314 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00315 if (glb.includeI(home, si)) {
00316 BndSetRanges ub(lub);
00317 BndSetRanges lb(glb);
00318 if (!Iter::Ranges::subset(lb,ub)) {
00319 glb.become(home, lub);
00320 glb.card(glb.size());
00321 lub.card(glb.size());
00322 return fail(home);
00323 }
00324 ModEvent me = ME_SET_GLB;
00325 if (cardMin() < glb.size()) {
00326 glb.card(glb.size());
00327 if (cardMin() > cardMax()) {
00328 glb.become(home, lub);
00329 glb.card(glb.size());
00330 lub.card(glb.size());
00331 return fail(home);
00332 }
00333 me = ME_SET_CGLB;
00334 }
00335 if (cardMin() == glb.size() && cardMin() == cardMax()) {
00336 lub.become(home, glb);
00337 me = ME_SET_VAL;
00338 }
00339 SetDelta d;
00340 return notify(home, me, d);
00341 }
00342 return ME_SET_NONE;
00343 }
00344
00345 forceinline ModEvent
00346 SetVarImp::exclude(Space& home, int i, int j) {
00347 if (j<i)
00348 return ME_SET_NONE;
00349 Iter::Ranges::Singleton sij(i,j);
00350 BndSetRanges lb(glb);
00351 Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb);
00352 if (probe())
00353 return fail(home);
00354 SetDelta d;
00355 if (lub.exclude(home, i, j, d))
00356 return processLubChange(home, d);
00357 return ME_SET_NONE;
00358 }
00359
00360 forceinline ModEvent
00361 SetVarImp::exclude(Space& home, int i) {
00362 return exclude(home, i, i);
00363 }
00364
00365 template<class I>
00366 inline ModEvent
00367 SetVarImp::excludeI(Space& home, I& iterator) {
00368 if (!iterator())
00369 return ME_SET_NONE;
00370 if (assigned()) {
00371 BndSetRanges ubi(lub);
00372 Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
00373 return probe() ? fail(home) : ME_SET_NONE;
00374 }
00375 int mi=iterator.min();
00376 int ma=iterator.max();
00377 ++iterator;
00378 if (iterator())
00379 return excludeI_full(home, mi, ma, iterator);
00380 else
00381 return exclude(home, mi, ma);
00382 }
00383
00384 template<class I>
00385 ModEvent
00386 SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) {
00387 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00388 if (lub.excludeI(home, si)) {
00389 BndSetRanges ub(lub);
00390 BndSetRanges lb(glb);
00391 if (!Iter::Ranges::subset(lb,ub)) {
00392 glb.become(home, lub);
00393 glb.card(glb.size());
00394 lub.card(glb.size());
00395 return fail(home);
00396 }
00397 ModEvent me = ME_SET_LUB;
00398 if (cardMax() > lub.size()) {
00399 lub.card(lub.size());
00400 if (cardMin() > cardMax()) {
00401 glb.become(home, lub);
00402 glb.card(glb.size());
00403 lub.card(glb.size());
00404 return fail(home);
00405 }
00406 me = ME_SET_CLUB;
00407 }
00408 if (cardMax() == lub.size() && cardMin() == cardMax()) {
00409 glb.become(home, lub);
00410 me = ME_SET_VAL;
00411 }
00412 SetDelta d;
00413 return notify(home, me, d);
00414 }
00415 return ME_SET_NONE;
00416 }
00417
00418
00419
00420
00421
00422
00423 forceinline SetVarImp*
00424 SetVarImp::copy(Space& home) {
00425 return copied() ?
00426 static_cast<SetVarImp*>(forward()) :
00427 perform_copy(home);
00428 }
00429
00430
00431
00432
00433
00434
00443 template<>
00444 class LubRanges<SetVarImp*> : public BndSetRanges {
00445 public:
00447
00448
00449 LubRanges(void);
00451 LubRanges(const SetVarImp*);
00453 void init(const SetVarImp*);
00455 };
00456
00457 forceinline
00458 LubRanges<SetVarImp*>::LubRanges(void) {}
00459
00460 forceinline
00461 LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x)
00462 : BndSetRanges(x->lub) {}
00463
00464 forceinline void
00465 LubRanges<SetVarImp*>::init(const SetVarImp* x) {
00466 BndSetRanges::init(x->lub);
00467 }
00468
00477 template<>
00478 class GlbRanges<SetVarImp*> : public BndSetRanges {
00479 public:
00481
00482
00483 GlbRanges(void);
00485 GlbRanges(const SetVarImp* x);
00487 void init(const SetVarImp*);
00489 };
00490
00491 forceinline
00492 GlbRanges<SetVarImp*>::GlbRanges(void) {}
00493
00494 forceinline
00495 GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x)
00496 : BndSetRanges(x->glb) {}
00497
00498 forceinline void
00499 GlbRanges<SetVarImp*>::init(const SetVarImp* x) {
00500 BndSetRanges::init(x->glb);
00501 }
00502
00503 }}
00504
00505