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