range-list.hpp
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
00041
00042 namespace Gecode {
00043
00053 class RangeList : public FreeList {
00054 protected:
00056 int _min;
00058 int _max;
00059 public:
00061
00062
00063 RangeList(void);
00065 RangeList(int min, int max);
00067 RangeList(int min, int max, RangeList* n);
00069
00071
00072
00073 int min(void) const;
00075 int max(void) const;
00077 unsigned int width(void) const;
00078
00080 RangeList* next(void) const;
00082 RangeList** nextRef(void);
00084
00086
00087
00088 void min(int n);
00090 void max(int n);
00092 void next(RangeList* n);
00094
00096
00097
00098 template<class Iter>
00099 static void copy(Space& home, RangeList*& r, Iter& i);
00101 template<class Iter>
00102 static void overwrite(Space& home, RangeList*& r, Iter& i);
00104 template<class I>
00105 static void insert(Space& home, RangeList*& r, I& i);
00107
00109
00110
00111 void dispose(Space& home, RangeList* l);
00113 void dispose(Space& home);
00114
00116 static void* operator new(size_t s, Space& home);
00118 static void* operator new(size_t s, void* p);
00120 static void operator delete(void*);
00122 static void operator delete(void*, Space& home);
00124 static void operator delete(void*, void*);
00126 };
00127
00128
00129
00130
00131
00132
00133 forceinline
00134 RangeList::RangeList(void) {}
00135
00136 forceinline
00137 RangeList::RangeList(int min, int max, RangeList* n)
00138 : FreeList(n), _min(min), _max(max) {}
00139
00140 forceinline
00141 RangeList::RangeList(int min, int max)
00142 : _min(min), _max(max) {}
00143
00144 forceinline RangeList*
00145 RangeList::next(void) const {
00146 return static_cast<RangeList*>(FreeList::next());
00147 }
00148
00149 forceinline RangeList**
00150 RangeList::nextRef(void) {
00151 return reinterpret_cast<RangeList**>(FreeList::nextRef());
00152 }
00153
00154 forceinline void
00155 RangeList::min(int n) {
00156 _min = n;
00157 }
00158 forceinline void
00159 RangeList::max(int n) {
00160 _max = n;
00161 }
00162 forceinline void
00163 RangeList::next(RangeList* n) {
00164 FreeList::next(n);
00165 }
00166
00167 forceinline int
00168 RangeList::min(void) const {
00169 return _min;
00170 }
00171 forceinline int
00172 RangeList::max(void) const {
00173 return _max;
00174 }
00175 forceinline unsigned int
00176 RangeList::width(void) const {
00177 return static_cast<unsigned int>(_max - _min + 1);
00178 }
00179
00180
00181 forceinline void
00182 RangeList::operator delete(void*) {}
00183
00184 forceinline void
00185 RangeList::operator delete(void*, Space&) {
00186 GECODE_NEVER;
00187 }
00188
00189 forceinline void
00190 RangeList::operator delete(void*, void*) {
00191 GECODE_NEVER;
00192 }
00193
00194 forceinline void*
00195 RangeList::operator new(size_t, Space& home) {
00196 return home.fl_alloc<sizeof(RangeList)>();
00197 }
00198
00199 forceinline void*
00200 RangeList::operator new(size_t, void* p) {
00201 return p;
00202 }
00203
00204 forceinline void
00205 RangeList::dispose(Space& home, RangeList* l) {
00206 home.fl_dispose<sizeof(RangeList)>(this,l);
00207 }
00208
00209 forceinline void
00210 RangeList::dispose(Space& home) {
00211 RangeList* l = this;
00212 while (l->next() != NULL)
00213 l=l->next();
00214 dispose(home,l);
00215 }
00216
00217 template<class Iter>
00218 forceinline void
00219 RangeList::copy(Space& home, RangeList*& r, Iter& i) {
00220 RangeList sentinel; sentinel.next(r);
00221 RangeList* p = &sentinel;
00222 while (i()) {
00223 RangeList* n = new (home) RangeList(i.min(),i.max());
00224 p->next(n); p=n; ++i;
00225 }
00226 p->next(NULL);
00227 r = sentinel.next();
00228 }
00229
00230 template<class Iter>
00231 forceinline void
00232 RangeList::overwrite(Space& home, RangeList*& r, Iter& i) {
00233 RangeList sentinel; sentinel.next(r);
00234 RangeList* p = &sentinel;
00235 RangeList* c = p->next();
00236 while ((c != NULL) && i()) {
00237 c->min(i.min()); c->max(i.max());
00238 p=c; c=c->next(); ++i;
00239 }
00240 if ((c == NULL) && !i())
00241 return;
00242 if (c == NULL) {
00243 assert(i());
00244
00245 do {
00246 RangeList* n = new (home) RangeList(i.min(),i.max());
00247 p->next(n); p=n; ++i;
00248 } while (i());
00249 } else {
00250
00251 while (c->next() != NULL)
00252 c=c->next();
00253 p->next()->dispose(home,c);
00254 }
00255 p->next(NULL);
00256 r = sentinel.next();
00257 }
00258
00259 template<class I>
00260 forceinline void
00261 RangeList::insert(Space& home, RangeList*& r, I& i) {
00262 RangeList sentinel;
00263 sentinel.next(r);
00264 RangeList* p = &sentinel;
00265 RangeList* c = p->next();
00266 while ((c != NULL) && i()) {
00267 if ((c->max()+1 < i.min())) {
00268 p=c; c=c->next();
00269 } else if (i.max()+1 < c->min()) {
00270 RangeList* n = new (home) RangeList(i.min(),i.max(),c);
00271 p->next(n); p=n; ++i;
00272 } else {
00273 int min = std::min(c->min(),i.min());
00274 int max = std::max(c->max(),i.max());
00275 RangeList* f=c;
00276 p=c; c=c->next(); ++i;
00277 next:
00278 if ((c != NULL) && (c->min() <= max+1)) {
00279 max = std::max(max,c->max());
00280 p=c; c=c->next();
00281 goto next;
00282 }
00283 if (i() && (i.min() <= max+1)) {
00284 max = std::max(max,i.max());
00285 ++i;
00286 goto next;
00287 }
00288
00289 if (f->next() != p)
00290 f->next()->dispose(home,p);
00291 f->min(min); f->max(max); f->next(c);
00292 }
00293 }
00294 if (c == NULL) {
00295 while (i()) {
00296 RangeList* n = new (home) RangeList(i.min(),i.max());
00297 p->next(n); p=n;
00298 ++i;
00299 }
00300 p->next(NULL);
00301 }
00302 r = sentinel.next();
00303 }
00304
00305 }
00306