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 namespace Gecode { namespace Set {
00039
00040
00041
00042
00043
00044
00045 forceinline
00046 BndSet::BndSet(void) :
00047 first(NULL), last(NULL), _size(0), _card(0) {}
00048
00049 forceinline RangeList*
00050 BndSet::fst(void) const {
00051 return first;
00052 }
00053
00054 forceinline RangeList*
00055 BndSet::lst(void) const {
00056 return last;
00057 }
00058
00059 forceinline void
00060 BndSet::dispose(Space& home) {
00061 if (fst()!=NULL)
00062 fst()->dispose(home,lst());
00063 }
00064
00065 forceinline void
00066 BndSet::fst(RangeList* f) {
00067 first = f;
00068 }
00069
00070 forceinline void
00071 BndSet::lst(RangeList* l) {
00072 last = l;
00073 }
00074
00075 forceinline
00076 BndSet::BndSet(Space& home, int mn, int mx) {
00077 if (mn>mx) {
00078 fst(NULL); lst(NULL); _size = 0;
00079 } else {
00080 RangeList* p =
00081 new (home) RangeList(mn,mx,NULL);
00082 fst(p); lst(p);
00083 _size = static_cast<unsigned int>(mx-mn+1);
00084 }
00085 }
00086
00087 forceinline RangeList*
00088 BndSet::ranges(void) const {
00089 return fst();
00090 }
00091
00092 forceinline unsigned int
00093 BndSet::size(void) const {
00094 return _size;
00095 }
00096
00097 forceinline bool
00098 BndSet::empty(void) const {
00099 return (_size==0);
00100 }
00101
00102 forceinline int
00103 BndSet::min(void) const {
00104 if (fst()==NULL)
00105 return MIN_OF_EMPTY;
00106 else
00107 return fst()->min();
00108 }
00109
00110 forceinline int
00111 BndSet::max(void) const {
00112 if (lst()==NULL)
00113 return MAX_OF_EMPTY;
00114 else
00115 return lst()->max();
00116 }
00117
00118
00119 forceinline int
00120 BndSet::minN(unsigned int n) const {
00121 for (RangeList* c = fst(); c != NULL; c = c->next()) {
00122 if (c->width() > n)
00123 return static_cast<int>(c->min() + n);
00124 n -= c->width();
00125 }
00126 return MIN_OF_EMPTY;
00127 }
00128
00129 forceinline unsigned int
00130 BndSet::card(void) const {
00131 return _card;
00132 }
00133
00134 forceinline void
00135 BndSet::card(unsigned int c) {
00136 _card = c;
00137 }
00138
00139 forceinline void
00140 BndSet::update(Space& home, BndSet& d) {
00141 if (d.fst() == fst())
00142 return;
00143 if (fst() != NULL)
00144 fst()->dispose(home,lst());
00145 _size = d.size();
00146 if (_size == 0) {
00147 fst(NULL); lst(NULL);
00148 return;
00149 }
00150
00151 int n=0;
00152 for (RangeList* c = d.fst(); c != NULL; c = c->next())
00153 n++;
00154
00155 RangeList* r = home.alloc<RangeList>(n);
00156 fst(r); lst(r+n-1);
00157
00158 {
00159 RangeList* c = d.fst();
00160 for (int i=0; i<n; i++) {
00161 r[i].min(c->min());
00162 r[i].max(c->max());
00163 r[i].next(&r[i+1]);
00164 c = c->next();
00165 }
00166 }
00167 r[n-1].next(NULL);
00168 }
00169
00170 template<class I> forceinline bool
00171 BndSet::overwrite(Space& home, I& ri) {
00172
00173 if (!ri()) {
00174
00175 if (fst()==NULL)
00176 return false;
00177 fst()->dispose(home,lst());
00178 _size=0; fst(NULL); lst(NULL);
00179 return true;
00180 }
00181
00182 RangeList* f =
00183 new (home) RangeList(ri.min(),ri.max(),NULL);
00184 RangeList* l = f;
00185 unsigned int s = ri.width();
00186
00187 ++ri;
00188
00189 while (ri()) {
00190 RangeList *n = new (home) RangeList(ri.min(),ri.max(),NULL);
00191 l->next(n);
00192 l=n;
00193 s += ri.width();
00194 ++ri;
00195 }
00196
00197 if (fst() != NULL)
00198 fst()->dispose(home,lst());
00199 fst(f); lst(l);
00200
00201
00202
00203 if (size() == s)
00204 return false;
00205
00206 _size = s;
00207 return true;
00208 }
00209
00210 forceinline void
00211 BndSet::become(Space& home, const BndSet& that) {
00212 if (fst()!=NULL) {
00213 assert(lst()!=NULL);
00214 assert(fst()!= that.fst());
00215 fst()->dispose(home,lst());
00216 }
00217 fst(that.fst());
00218 lst(that.lst());
00219 _size = that.size();
00220 assert(isConsistent());
00221 }
00222
00223 forceinline bool
00224 BndSet::in(int i) const {
00225 for (RangeList* c = fst(); c != NULL; c = c->next()) {
00226 if (c->min() <= i && c->max() >= i)
00227 return true;
00228 if (c->min() > i)
00229 return false;
00230 }
00231 return false;
00232 }
00233
00234
00235
00236
00237
00238
00239 forceinline
00240 BndSetRanges::BndSetRanges(void) {}
00241
00242 forceinline
00243 BndSetRanges::BndSetRanges(const BndSet& s)
00244 : Iter::Ranges::RangeList(s.ranges()) {}
00245
00246 forceinline void
00247 BndSetRanges::init(const BndSet& s) {
00248 Iter::Ranges::RangeList::init(s.ranges());
00249 }
00250
00251
00252
00253
00254
00255
00256 forceinline
00257 GLBndSet::GLBndSet(void) {}
00258
00259 forceinline
00260 GLBndSet::GLBndSet(Space&) {}
00261
00262 forceinline
00263 GLBndSet::GLBndSet(Space& home, int mi, int ma)
00264 : BndSet(home,mi,ma) {}
00265
00266 forceinline
00267 GLBndSet::GLBndSet(Space& home, const IntSet& s)
00268 : BndSet(home,s) {}
00269
00270 forceinline void
00271 GLBndSet::init(Space& home) {
00272 dispose(home);
00273 fst(NULL);
00274 lst(NULL);
00275 _size = 0;
00276 }
00277
00278 forceinline bool
00279 GLBndSet::include(Space& home, int mi, int ma, SetDelta& d) {
00280 assert(ma >= mi);
00281 if (fst()==NULL) {
00282 RangeList* p = new (home) RangeList(mi,ma,NULL);
00283 fst(p);
00284 lst(p);
00285 _size=static_cast<unsigned int>(ma-mi+1);
00286 d._glbMin = mi;
00287 d._glbMax = ma;
00288 return true;
00289 }
00290 bool ret = include_full(home, mi, ma, d);
00291 assert(isConsistent());
00292 return ret;
00293 }
00294
00295 template<class I> bool
00296 GLBndSet::includeI(Space& home, I& i) {
00297 if (!i())
00298 return false;
00299 BndSetRanges j(*this);
00300 Iter::Ranges::Union<BndSetRanges,I> ij(j,i);
00301 bool me = overwrite(home, ij);
00302 assert(isConsistent());
00303 return me;
00304 }
00305
00306
00307
00308
00309
00310
00311
00312 forceinline
00313 LUBndSet::LUBndSet(void) {}
00314
00315 forceinline
00316 LUBndSet::LUBndSet(Space& home)
00317 : BndSet(home,Limits::min,Limits::max) {}
00318
00319 forceinline
00320 LUBndSet::LUBndSet(Space& home, int mi, int ma)
00321 : BndSet(home,mi,ma) {}
00322
00323 forceinline
00324 LUBndSet::LUBndSet(Space& home, const IntSet& s)
00325 : BndSet(home,s) {}
00326
00327 forceinline void
00328 LUBndSet::init(Space& home) {
00329 RangeList *p =
00330 new (home) RangeList(Limits::min,
00331 Limits::max,
00332 NULL);
00333 fst(p);
00334 lst(p);
00335 _size = Limits::card;
00336 }
00337
00338 forceinline bool
00339 LUBndSet::exclude(Space& home, int mi, int ma, SetDelta& d) {
00340 assert(ma >= mi);
00341 if ((mi > max()) || (ma < min())) { return false; }
00342 if (mi <= min() && ma >= max() ) {
00343 d._lubMin = min();
00344 d._lubMax = max();
00345 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00346 _size=0;
00347 return true;
00348 }
00349 bool ret = exclude_full(home, mi, ma, d);
00350 assert(isConsistent());
00351 return ret;
00352 }
00353
00354 forceinline bool
00355 LUBndSet::intersect(Space& home, int mi, int ma) {
00356 assert(ma >= mi);
00357 if ((mi <= min()) && (ma >= max())) { return false; }
00358 if (_size == 0) return false;
00359 if (ma < min() || mi > max() ) {
00360 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00361 _size=0;
00362 return true;
00363 }
00364 bool ret = intersect_full(home, mi, ma);
00365 assert(isConsistent());
00366 return ret;
00367 }
00368
00369 template<class I> bool
00370 LUBndSet::intersectI(Space& home, I& i) {
00371 if (fst()==NULL) { return false; }
00372 if (!i()) {
00373 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00374 _size=0;
00375 return true;
00376 }
00377 BndSetRanges j(*this);
00378 Iter::Ranges::Inter<BndSetRanges,I> ij(j,i);
00379 bool ret = overwrite(home, ij);
00380 assert(isConsistent());
00381 return ret;
00382 }
00383
00384 template<class I> bool
00385 LUBndSet::excludeI(Space& home, I& i) {
00386 if (!i()) { return false; }
00387 BndSetRanges j(*this);
00388 Iter::Ranges::Diff<BndSetRanges,I> ij(j,i);
00389 bool ret = overwrite(home, ij);
00390 assert(isConsistent());
00391 return ret;
00392 }
00393
00394 forceinline void
00395 LUBndSet::excludeAll(Space& home) {
00396 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00397 _size=0;
00398 }
00399
00400
00401
00402
00403
00404 template<class I>
00405 RangesCompl<I>::RangesCompl(void) {}
00406
00407 template<class I>
00408 RangesCompl<I>::RangesCompl(I& i)
00409 : Iter::Ranges::Compl<Limits::min,
00410 Limits::max,
00411 I>(i) {}
00412
00413 template<class I> void
00414 RangesCompl<I>::init(I& i) {
00415 Iter::Ranges::Compl<Limits::min,
00416 Limits::max,I>::init(i);
00417 }
00418
00419 }}
00420
00421
00422