Generated on Sun Feb 17 15:24:26 2019 for Gecode by doxygen 1.6.3

range-list.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Guido Tack <tack@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2004
00011  *     Guido Tack, 2004
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode {
00039 
00049   class RangeList : public FreeList {
00050   protected:
00052     int        _min;
00054     int        _max;
00055   public:
00057 
00058 
00059     RangeList(void);
00061     RangeList(int min, int max);
00063     RangeList(int min, int max, RangeList* n);
00065 
00067 
00068 
00069     int min(void) const;
00071     int max(void) const;
00073     unsigned int width(void) const;
00074 
00076     RangeList* next(void) const;
00078     RangeList** nextRef(void);
00080 
00082 
00083 
00084     void min(int n);
00086     void max(int n);
00088     void next(RangeList* n);
00090 
00092 
00093 
00094     template<class Iter>
00095     static void copy(Space& home, RangeList*& r, Iter& i);
00097     template<class Iter>
00098     static void overwrite(Space& home, RangeList*& r, Iter& i);
00100     template<class I>
00101     static void insert(Space& home, RangeList*& r, I& i);
00103 
00105 
00106 
00107     void dispose(Space& home, RangeList* l);
00109     void dispose(Space& home);
00110 
00112     static void* operator new(size_t s, Space& home);
00114     static void* operator new(size_t s, void* p);
00116     static void  operator delete(void*);
00118     static void  operator delete(void*, Space& home);
00120     static void  operator delete(void*, void*);
00122   };
00123 
00124   /*
00125    * Range lists
00126    *
00127    */
00128 
00129   forceinline
00130   RangeList::RangeList(void) {}
00131 
00132   forceinline
00133   RangeList::RangeList(int min, int max, RangeList* n)
00134     : FreeList(n), _min(min), _max(max) {}
00135 
00136   forceinline
00137   RangeList::RangeList(int min, int max)
00138     : _min(min), _max(max) {}
00139 
00140   forceinline RangeList*
00141   RangeList::next(void) const {
00142     return static_cast<RangeList*>(FreeList::next());
00143   }
00144 
00145   forceinline RangeList**
00146   RangeList::nextRef(void) {
00147     return reinterpret_cast<RangeList**>(FreeList::nextRef());
00148   }
00149 
00150   forceinline void
00151   RangeList::min(int n) {
00152     _min = n;
00153   }
00154   forceinline void
00155   RangeList::max(int n) {
00156     _max = n;
00157   }
00158   forceinline void
00159   RangeList::next(RangeList* n) {
00160     FreeList::next(n);
00161   }
00162 
00163   forceinline int
00164   RangeList::min(void) const {
00165     return _min;
00166   }
00167   forceinline int
00168   RangeList::max(void) const {
00169     return _max;
00170   }
00171   forceinline unsigned int
00172   RangeList::width(void) const {
00173     return static_cast<unsigned int>(_max - _min + 1);
00174   }
00175 
00176 
00177   forceinline void
00178   RangeList::operator delete(void*) {}
00179 
00180   forceinline void
00181   RangeList::operator delete(void*, Space&) {
00182     GECODE_NEVER;
00183   }
00184 
00185   forceinline void
00186   RangeList::operator delete(void*, void*) {
00187     GECODE_NEVER;
00188   }
00189 
00190   forceinline void*
00191   RangeList::operator new(size_t, Space& home) {
00192     return home.fl_alloc<sizeof(RangeList)>();
00193   }
00194 
00195   forceinline void*
00196   RangeList::operator new(size_t, void* p) {
00197     return p;
00198   }
00199 
00200   forceinline void
00201   RangeList::dispose(Space& home, RangeList* l) {
00202     home.fl_dispose<sizeof(RangeList)>(this,l);
00203   }
00204 
00205   forceinline void
00206   RangeList::dispose(Space& home) {
00207     RangeList* l = this;
00208     while (l->next() != NULL)
00209       l=l->next();
00210     dispose(home,l);
00211   }
00212 
00213   template<class Iter>
00214   forceinline void
00215   RangeList::copy(Space& home, RangeList*& r, Iter& i) {
00216     RangeList sentinel; sentinel.next(r);
00217     RangeList* p = &sentinel;
00218     while (i()) {
00219       RangeList* n = new (home) RangeList(i.min(),i.max());
00220       p->next(n); p=n; ++i;
00221     }
00222     p->next(NULL);
00223     r = sentinel.next();
00224   }
00225 
00226   template<class Iter>
00227   forceinline void
00228   RangeList::overwrite(Space& home, RangeList*& r, Iter& i) {
00229     RangeList sentinel; sentinel.next(r);
00230     RangeList* p = &sentinel;
00231     RangeList* c = p->next();
00232     while ((c != NULL) && i()) {
00233       c->min(i.min()); c->max(i.max());
00234       p=c; c=c->next(); ++i;
00235     }
00236     if ((c == NULL) && !i())
00237       return;
00238     if (c == NULL) {
00239       assert(i());
00240       // New elements needed
00241       do {
00242         RangeList* n = new (home) RangeList(i.min(),i.max());
00243         p->next(n); p=n; ++i;
00244       } while (i());
00245     } else {
00246       // Dispose excess elements
00247       while (c->next() != NULL)
00248         c=c->next();
00249       p->next()->dispose(home,c);
00250     }
00251     p->next(NULL);
00252     r = sentinel.next();
00253   }
00254 
00255   template<class I>
00256   forceinline void
00257   RangeList::insert(Space& home, RangeList*& r, I& i) {
00258     RangeList sentinel;
00259     sentinel.next(r);
00260     RangeList* p = &sentinel;
00261     RangeList* c = p->next();
00262     while ((c != NULL) && i()) {
00263       if ((c->max()+1 < i.min())) {
00264         p=c; c=c->next();
00265       } else if (i.max()+1 < c->min()) {
00266         RangeList* n = new (home) RangeList(i.min(),i.max(),c);
00267         p->next(n); p=n; ++i;
00268       } else {
00269         int min = std::min(c->min(),i.min());
00270         int max = std::max(c->max(),i.max());
00271         RangeList* f=c;
00272         p=c; c=c->next(); ++i;
00273       next:
00274         if ((c != NULL) && (c->min() <= max+1)) {
00275           max = std::max(max,c->max());
00276           p=c; c=c->next();
00277           goto next;
00278         }
00279         if (i() && (i.min() <= max+1)) {
00280           max = std::max(max,i.max());
00281           ++i;
00282           goto next;
00283         }
00284         // Dispose now unused elements
00285         if (f->next() != p)
00286           f->next()->dispose(home,p);
00287         f->min(min); f->max(max); f->next(c);
00288       }
00289     }
00290     if (c == NULL) {
00291       while (i()) {
00292         RangeList* n = new (home) RangeList(i.min(),i.max());
00293         p->next(n); p=n;
00294         ++i;
00295       }
00296       p->next(NULL);
00297     }
00298     r = sentinel.next();
00299   }
00300 
00301 }
00302 // STATISTICS: kernel-other