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 int
00140 SetVarImp::glbMin(const Delta& d) {
00141 return static_cast<const SetDelta&>(d).glbMin();
00142 }
00143 forceinline int
00144 SetVarImp::glbMax(const Delta& d) {
00145 return static_cast<const SetDelta&>(d).glbMax();
00146 }
00147 forceinline bool
00148 SetVarImp::glbAny(const Delta& d) {
00149 return static_cast<const SetDelta&>(d).glbAny();
00150 }
00151 forceinline int
00152 SetVarImp::lubMin(const Delta& d) {
00153 return static_cast<const SetDelta&>(d).lubMin();
00154 }
00155 forceinline int
00156 SetVarImp::lubMax(const Delta& d) {
00157 return static_cast<const SetDelta&>(d).lubMax();
00158 }
00159 forceinline bool
00160 SetVarImp::lubAny(const Delta& d) {
00161 return static_cast<const SetDelta&>(d).lubAny();
00162 }
00163
00164 forceinline ModEvent
00165 SetVarImp::cardMin(Space& home,unsigned int newMin) {
00166 if (cardMin() >= newMin)
00167 return ME_SET_NONE;
00168 if (newMin > cardMax())
00169 return ME_SET_FAILED;
00170 glb.card(newMin);
00171 return cardMin_full(home);
00172 }
00173
00174 forceinline ModEvent
00175 SetVarImp::cardMax(Space& home,unsigned int newMax) {
00176 if (cardMax() <= newMax)
00177 return ME_SET_NONE;
00178 if (cardMin() > newMax)
00179 return ME_SET_FAILED;
00180 lub.card(newMax);
00181 return cardMax_full(home);
00182 }
00183
00184 forceinline ModEvent
00185 SetVarImp::intersect(Space& home,int i, int j) {
00186 BndSetRanges lb(glb);
00187 Iter::Ranges::Singleton s(i,j);
00188 Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s);
00189 if (probe())
00190 return ME_SET_FAILED;
00191 if (assigned())
00192 return ME_SET_NONE;
00193 int oldMin = lub.min();
00194 int oldMax = lub.max();
00195 if (lub.intersect(home, i, j)) {
00196 SetDelta d;
00197 if (i == oldMin) {
00198 d._lubMin = lub.max()+1;
00199 d._lubMax = oldMax;
00200 } else if (j == oldMax) {
00201 d._lubMin = oldMin;
00202 d._lubMax = lub.min()-1;
00203 }
00204 return processLubChange(home, d);
00205 }
00206 return ME_SET_NONE;
00207 }
00208
00209 forceinline ModEvent
00210 SetVarImp::intersect(Space& home,int i) {
00211 return intersect(home, i, i);
00212 }
00213
00214 template<class I>
00215 inline ModEvent
00216 SetVarImp::intersectI(Space& home, I& iterator) {
00217 if (assigned()) {
00218 BndSetRanges lbi(glb);
00219 Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
00220 if (probe())
00221 return ME_SET_FAILED;
00222 return ME_SET_NONE;
00223 }
00224 if (!iterator()) {
00225 if (cardMin() > 0)
00226 return ME_SET_FAILED;
00227 lub.card(0);
00228 SetDelta d(1, 0, lub.min(), lub.max());
00229 lub.excludeAll(home);
00230 return notify(home, ME_SET_VAL, d);
00231 }
00232 int mi=iterator.min();
00233 int ma=iterator.max();
00234 ++iterator;
00235 if (iterator())
00236 return intersectI_full(home, mi, ma, iterator);
00237 else
00238 return intersect(home, mi, ma);
00239 }
00240
00241 template<class I>
00242 ModEvent
00243 SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
00244 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00245 if (lub.intersectI(home, si)) {
00246 BndSetRanges ub(lub);
00247 BndSetRanges lb(glb);
00248 if (!Iter::Ranges::subset(lb,ub)) {
00249 glb.become(home, lub);
00250 glb.card(glb.size());
00251 lub.card(glb.size());
00252 return ME_SET_FAILED;
00253 }
00254 ModEvent me = ME_SET_LUB;
00255 if (cardMax() > lub.size()) {
00256 lub.card(lub.size());
00257 if (cardMin() > cardMax()) {
00258 glb.become(home, lub);
00259 glb.card(glb.size());
00260 lub.card(glb.size());
00261 return ME_SET_FAILED;
00262 }
00263 me = ME_SET_CLUB;
00264 }
00265 if (cardMax() == lub.size() && cardMin() == cardMax()) {
00266 glb.become(home, lub);
00267 me = ME_SET_VAL;
00268 }
00269 SetDelta d;
00270 return notify(home, me, d);
00271 }
00272 return ME_SET_NONE;
00273 }
00274
00275 forceinline ModEvent
00276 SetVarImp::include(Space& home, int i, int j) {
00277 if (j<i)
00278 return ME_SET_NONE;
00279 BndSetRanges ub(lub);
00280 Iter::Ranges::Singleton sij(i,j);
00281 if (!Iter::Ranges::subset(sij,ub)) {
00282 return ME_SET_FAILED;
00283 }
00284 SetDelta d;
00285 if (glb.include(home, i, j, d))
00286 return processGlbChange(home, d);
00287 return ME_SET_NONE;
00288 }
00289
00290 forceinline ModEvent
00291 SetVarImp::include(Space& home, int i) {
00292 return include(home, i, i);
00293 }
00294
00295 template<class I> forceinline ModEvent
00296 SetVarImp::includeI(Space& home, I& iterator) {
00297 if (!iterator()) {
00298 return ME_SET_NONE;
00299 }
00300 if (assigned()) {
00301 BndSetRanges lbi(glb);
00302 Iter::Ranges::Diff<I,BndSetRanges>
00303 probe(iterator,lbi);
00304 return probe() ? ME_SET_FAILED : ME_SET_NONE;
00305 }
00306 int mi=iterator.min();
00307 int ma=iterator.max();
00308 ++iterator;
00309 if (iterator())
00310 return includeI_full(home, mi, ma, iterator);
00311 else
00312 return include(home, mi, ma);
00313 }
00314
00315 template<class I>
00316 ModEvent
00317 SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
00318 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00319 if (glb.includeI(home, si)) {
00320 BndSetRanges ub(lub);
00321 BndSetRanges lb(glb);
00322 if (!Iter::Ranges::subset(lb,ub)) {
00323 glb.become(home, lub);
00324 glb.card(glb.size());
00325 lub.card(glb.size());
00326 return ME_SET_FAILED;
00327 }
00328 ModEvent me = ME_SET_GLB;
00329 if (cardMin() < glb.size()) {
00330 glb.card(glb.size());
00331 if (cardMin() > cardMax()) {
00332 glb.become(home, lub);
00333 glb.card(glb.size());
00334 lub.card(glb.size());
00335 return ME_SET_FAILED;
00336 }
00337 me = ME_SET_CGLB;
00338 }
00339 if (cardMin() == glb.size() && cardMin() == cardMax()) {
00340 lub.become(home, glb);
00341 me = ME_SET_VAL;
00342 }
00343 SetDelta d;
00344 return notify(home, me, d);
00345 }
00346 return ME_SET_NONE;
00347 }
00348
00349 forceinline ModEvent
00350 SetVarImp::exclude(Space& home, int i, int j) {
00351 if (j<i)
00352 return ME_SET_NONE;
00353 Iter::Ranges::Singleton sij(i,j);
00354 BndSetRanges lb(glb);
00355 Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb);
00356 if (probe())
00357 return ME_SET_FAILED;
00358 SetDelta d;
00359 if (lub.exclude(home, i, j, d))
00360 return processLubChange(home, d);
00361 return ME_SET_NONE;
00362 }
00363
00364 forceinline ModEvent
00365 SetVarImp::exclude(Space& home, int i) {
00366 return exclude(home, i, i);
00367 }
00368
00369 template<class I>
00370 inline ModEvent
00371 SetVarImp::excludeI(Space& home, I& iterator) {
00372 if (!iterator())
00373 return ME_SET_NONE;
00374 if (assigned()) {
00375 BndSetRanges ubi(lub);
00376 Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
00377 return probe() ? ME_SET_FAILED : ME_SET_NONE;
00378 }
00379 int mi=iterator.min();
00380 int ma=iterator.max();
00381 ++iterator;
00382 if (iterator())
00383 return excludeI_full(home, mi, ma, iterator);
00384 else
00385 return exclude(home, mi, ma);
00386 }
00387
00388 template<class I>
00389 ModEvent
00390 SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) {
00391 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00392 if (lub.excludeI(home, si)) {
00393 BndSetRanges ub(lub);
00394 BndSetRanges lb(glb);
00395 if (!Iter::Ranges::subset(lb,ub)) {
00396 glb.become(home, lub);
00397 glb.card(glb.size());
00398 lub.card(glb.size());
00399 return ME_SET_FAILED;
00400 }
00401 ModEvent me = ME_SET_LUB;
00402 if (cardMax() > lub.size()) {
00403 lub.card(lub.size());
00404 if (cardMin() > cardMax()) {
00405 glb.become(home, lub);
00406 glb.card(glb.size());
00407 lub.card(glb.size());
00408 return ME_SET_FAILED;
00409 }
00410 me = ME_SET_CLUB;
00411 }
00412 if (cardMax() == lub.size() && cardMin() == cardMax()) {
00413 glb.become(home, lub);
00414 me = ME_SET_VAL;
00415 }
00416 SetDelta d;
00417 return notify(home, me, d);
00418 }
00419 return ME_SET_NONE;
00420 }
00421
00422
00423
00424
00425
00426
00427 forceinline SetVarImp*
00428 SetVarImp::copy(Space& home, bool share) {
00429 return copied() ?
00430 static_cast<SetVarImp*>(forward()) :
00431 perform_copy(home,share);
00432 }
00433
00434
00435
00436
00437
00438
00447 template<>
00448 class LubRanges<SetVarImp*> : public BndSetRanges {
00449 public:
00451
00452
00453 LubRanges(void);
00455 LubRanges(const SetVarImp*);
00457 void init(const SetVarImp*);
00459 };
00460
00461 forceinline
00462 LubRanges<SetVarImp*>::LubRanges(void) {}
00463
00464 forceinline
00465 LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x)
00466 : BndSetRanges(x->lub) {}
00467
00468 forceinline void
00469 LubRanges<SetVarImp*>::init(const SetVarImp* x) {
00470 BndSetRanges::init(x->lub);
00471 }
00472
00481 template<>
00482 class GlbRanges<SetVarImp*> : public BndSetRanges {
00483 public:
00485
00486
00487 GlbRanges(void);
00489 GlbRanges(const SetVarImp* x);
00491 void init(const SetVarImp*);
00493 };
00494
00495 forceinline
00496 GlbRanges<SetVarImp*>::GlbRanges(void) {}
00497
00498 forceinline
00499 GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x)
00500 : BndSetRanges(x->glb) {}
00501
00502 forceinline void
00503 GlbRanges<SetVarImp*>::init(const SetVarImp* x) {
00504 BndSetRanges::init(x->glb);
00505 }
00506
00507
00508
00509
00510
00511
00512 forceinline void
00513 SetVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) {
00514 SetVarImpBase::subscribe(home,p,pc,assigned(),schedule);
00515 }
00516 forceinline void
00517 SetVarImp::cancel(Space& home, Propagator& p, PropCond pc) {
00518 SetVarImpBase::cancel(home,p,pc,assigned());
00519 }
00520 forceinline void
00521 SetVarImp::subscribe(Space& home, Advisor& a) {
00522 SetVarImpBase::subscribe(home,a,assigned());
00523 }
00524 forceinline void
00525 SetVarImp::cancel(Space& home, Advisor& a) {
00526 SetVarImpBase::cancel(home,a,assigned());
00527 }
00528
00529 }}
00530
00531