dune-istl  2.2.0
basearray.hh
Go to the documentation of this file.
00001 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
00002 // vi: set et ts=4 sw=2 sts=2:
00003 #ifndef DUNE_BASEARRAY_HH
00004 #define DUNE_BASEARRAY_HH
00005 
00006 #include "assert.h"
00007 #include<cmath>
00008 #include<complex>
00009 #include<cstddef>
00010 #include<memory>
00011 
00012 #include "istlexception.hh"
00013 #include <dune/common/iteratorfacades.hh>
00014 
00019 namespace Dune {
00020    
00039   template<class B, class A=std::allocator<B> >
00040   class base_array_unmanaged
00041   {
00042   public:
00043 
00044         //===== type definitions and constants
00045 
00047         typedef B member_type;
00048 
00050         typedef A allocator_type;
00051 
00053     typedef typename A::size_type size_type;
00054     
00055 
00056         //===== access to components
00057 
00059         B& operator[] (size_type i)
00060         {
00061 #ifdef DUNE_ISTL_WITH_CHECKING
00062           if (i>=n) DUNE_THROW(ISTLError,"index out of range");
00063 #endif
00064           return p[i];
00065         }
00066 
00068         const B& operator[] (size_type i) const
00069         {
00070 #ifdef DUNE_ISTL_WITH_CHECKING
00071           if (i>=n) DUNE_THROW(ISTLError,"index out of range");
00072 #endif
00073           return p[i];
00074         }
00075 
00077     template<class T>
00078     class RealIterator 
00079       :  public RandomAccessIteratorFacade<RealIterator<T>, T>
00080     {
00081     public:
00083       typedef typename remove_const<T>::type ValueType;
00084       
00085       friend class RandomAccessIteratorFacade<RealIterator<const ValueType>, const ValueType>;
00086       friend class RandomAccessIteratorFacade<RealIterator<ValueType>, ValueType>;
00087       friend class RealIterator<const ValueType>;
00088       friend class RealIterator<ValueType>;
00089       
00091       RealIterator ()
00092         : p(0), i(0)
00093       {}
00094       
00095       RealIterator (const B* _p, B* _i) : p(_p), i(_i)
00096       {   }
00097       
00098       RealIterator(const RealIterator<ValueType>& it)
00099         : p(it.p), i(it.i)
00100       {}
00101            
00103       size_type index () const
00104       {
00105         return i-p;
00106       }
00107             
00109       bool equals (const RealIterator<ValueType>& other) const
00110       {
00111         assert(other.p==p);
00112         return i==other.i;
00113       }
00114       
00116       bool equals (const RealIterator<const ValueType>& other) const
00117       {
00118         assert(other.p==p);
00119         return i==other.i;
00120       }
00121 
00122       std::ptrdiff_t distanceTo(const RealIterator& o) const
00123       {
00124         return o.i-i;
00125       }
00126 
00127     private:
00129       void increment()
00130       {
00131         ++i;
00132       }
00133       
00135       void decrement()
00136       {
00137         --i;
00138       }
00139 
00141       B& dereference () const
00142       {
00143         return *i;
00144       }
00145 
00146       void advance(std::ptrdiff_t d)
00147       {
00148         i+=d;
00149       }
00150       
00151       const B* p;
00152       B* i;
00153     };
00154 
00156     typedef RealIterator<B> iterator;
00157     
00158     
00160         iterator begin ()
00161         {
00162           return iterator(p,p);
00163         }
00164 
00166         iterator end ()
00167         {
00168           return iterator(p,p+n);
00169         }
00170 
00173         iterator beforeEnd ()
00174         {
00175           return iterator(p,p+n-1);
00176         }
00177 
00180         iterator beforeBegin ()
00181         {
00182           return iterator(p,p-1);
00183         }
00184 
00186         iterator find (size_type i)
00187         {
00188           if (i<n)
00189                 return iterator(p,p+i);
00190           else
00191                 return iterator(p,p+n);
00192         }
00193 
00195     typedef RealIterator<const B> const_iterator;
00196 
00198         const_iterator begin () const
00199         {
00200           return const_iterator(p,p+0);
00201         }
00202 
00204         const_iterator end () const
00205         {
00206           return const_iterator(p,p+n);
00207         }
00208 
00211         const_iterator beforeEnd () const
00212         {
00213           return const_iterator(p,p+n-1);
00214         }
00215 
00218         const_iterator beforeBegin () const
00219         {
00220           return const_iterator(p,p-1);
00221         }
00222 
00224         const_iterator find (size_type i) const
00225         {
00226           if (i<n)
00227                 return const_iterator(p,p+i);
00228           else
00229                 return const_iterator(p,p+n);
00230         }
00231 
00232 
00233         //===== sizes
00234 
00236         size_type size () const
00237         {
00238           return n;
00239         }
00240 
00241   protected:
00243     base_array_unmanaged ()
00244       : n(0), p(0)
00245     {}
00247     base_array_unmanaged (size_type n_, B* p_)
00248       : n(n_), p(p_)
00249     {}
00250         size_type n; // number of elements in array
00251         B *p;  // pointer to dynamically allocated built-in array
00252   };
00253 
00254 
00255 
00270   template<class B, class A=std::allocator<B> >
00271   class base_array_window : public base_array_unmanaged<B,A>
00272   {
00273   public:
00274 
00275         //===== type definitions and constants
00276 
00278         typedef B member_type;
00279 
00281         typedef A allocator_type;
00282 
00284         typedef typename base_array_unmanaged<B,A>::iterator iterator;
00285 
00287         typedef typename base_array_unmanaged<B,A>::const_iterator const_iterator;
00288 
00290     typedef typename base_array_unmanaged<B,A>::size_type size_type;
00291 
00293     typedef typename A::difference_type difference_type;
00294     
00295         //===== constructors and such
00296 
00298     base_array_window ()
00299       : base_array_unmanaged<B,A>()
00300     {   }
00301 
00303     base_array_window (B* _p, size_type _n)
00304       : base_array_unmanaged<B,A>(_n ,_p)
00305     {}
00306 
00307         //===== window manipulation methods
00308 
00310         void set (size_type _n, B* _p)
00311         {
00312           this->n = _n;
00313           this->p = _p;
00314         }
00315 
00317         void advance (difference_type newsize)
00318         {
00319           this->p += this->n;
00320           this->n = newsize;
00321         }
00322 
00324         void move (difference_type offset, size_type newsize)
00325         {
00326           this->p += offset;
00327           this->n = newsize;
00328         }
00329 
00331         void move (difference_type offset)
00332         {
00333           this->p += offset;
00334         }
00335 
00337         B* getptr ()
00338         {
00339           return this->p;
00340         }
00341   };
00342 
00343 
00344 
00360   template<class B, class A=std::allocator<B> >
00361   class base_array : public base_array_unmanaged<B,A>
00362   {
00363   public:
00364 
00365         //===== type definitions and constants
00366 
00368         typedef B member_type;
00369 
00371         typedef A allocator_type;
00372 
00374         typedef typename base_array_unmanaged<B,A>::iterator iterator;
00375 
00377         typedef typename base_array_unmanaged<B,A>::const_iterator const_iterator;
00378    
00380     typedef typename base_array_unmanaged<B,A>::size_type size_type;
00381 
00383     typedef typename A::difference_type difference_type;
00384     
00385         //===== constructors and such
00386 
00388     base_array ()
00389       : base_array_unmanaged<B,A>()
00390     {}
00391 
00393         base_array (size_type _n)
00394           : base_array_unmanaged<B,A>(_n, 0)
00395         {
00396             if (this->n>0) {
00397                 this->p = allocator_.allocate(this->n);
00398                 new (this->p) B[this->n];
00399             } else
00400                 {
00401                   this->n = 0;
00402                   this->p = 0;
00403                 }
00404         }
00405 
00407         base_array (const base_array& a)
00408         {
00409           // allocate memory with same size as a
00410           this->n = a.n;
00411 
00412           if (this->n>0) {
00413               this->p = allocator_.allocate(this->n);
00414               new (this->p) B[this->n];
00415           } else
00416                 {
00417                   this->n = 0;
00418                   this->p = 0;
00419                 }
00420 
00421           // and copy elements
00422           for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
00423         }
00424 
00426         base_array (const base_array_unmanaged<B,A>& _a) 
00427         {
00428           const base_array& a = static_cast<const base_array&>(_a);
00429 
00430           // allocate memory with same size as a
00431           this->n = a.n;
00432           if (this->n>0) {
00433                 this->p = allocator_.allocate(this->n);
00434                 new (this->p) B[this->n];
00435           } else
00436                 {
00437                   this->n = 0;
00438                   this->p = 0;
00439                 }
00440 
00441           // and copy elements
00442           for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
00443         }
00444 
00445 
00447         ~base_array () 
00448         { 
00449             if (this->n>0) {
00450                 int i=this->n;
00451                 while (i)
00452                     this->p[--i].~B();
00453                 allocator_.deallocate(this->p,this->n);
00454             }
00455         }
00456 
00458         void resize (size_type _n)
00459         {
00460           if (this->n==_n) return;
00461 
00462           if (this->n>0) {
00463               int i=this->n;
00464               while (i)
00465                   this->p[--i].~B();
00466               allocator_.deallocate(this->p,this->n); 
00467           }
00468           this->n = _n;
00469           if (this->n>0) {
00470                 this->p = allocator_.allocate(this->n);
00471                 new (this->p) B[this->n];
00472           } else
00473                 {
00474                   this->n = 0;
00475                   this->p = 0;
00476                 }
00477         }
00478 
00480         base_array& operator= (const base_array& a)
00481         {
00482           if (&a!=this) // check if this and a are different objects
00483                 {
00484                   // adjust size of array
00485                   if (this->n!=a.n) // check if size is different
00486                         {
00487                             if (this->n>0) {
00488                                 int i=this->n;
00489                                 while (i)
00490                                     this->p[--i].~B();
00491                                 allocator_.deallocate(this->p,this->n); // delete old memory
00492                             }
00493                           this->n = a.n;
00494                           if (this->n>0) {
00495                                 this->p = allocator_.allocate(this->n);
00496                                 new (this->p) B[this->n];
00497                           } else
00498                                 {
00499                                   this->n = 0;
00500                                   this->p = 0;
00501                                 }
00502                         }
00503                   // copy data
00504                   for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
00505                 }
00506           return *this;
00507         }
00508 
00510         base_array& operator= (const base_array_unmanaged<B,A>& a)
00511         {
00512           return this->operator=(static_cast<const base_array&>(a));
00513         }
00514 
00515         protected:
00516 
00517         A allocator_;
00518   };
00519 
00520 
00521 
00522 
00542   template<class B, class A=std::allocator<B> >
00543   class compressed_base_array_unmanaged
00544   {
00545   public:
00546 
00547         //===== type definitions and constants
00548 
00550         typedef B member_type;
00551 
00553         typedef A allocator_type;
00554 
00556     typedef typename A::size_type size_type;
00557 
00558         //===== access to components
00559 
00561         B& operator[] (size_type i)
00562         {
00563           size_type l=0, r=n-1;
00564           while (l<r)
00565                 {
00566                   size_type q = (l+r)/2;
00567                   if (i <= j[q]) r=q;
00568                   else l = q+1;
00569                 }
00570           if (j[l]!=i){
00571              DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
00572           }       
00573           return p[l];
00574         }
00575 
00577         const B& operator[] (size_type i) const
00578         {
00579           size_type l=0, r=n-1;
00580           while (l<r)
00581                 {
00582                   size_type q = (l+r)/2;
00583                   if (i <= j[q]) r=q;
00584                   else l = q+1;
00585                 }
00586           if (j[l]!=i){
00587              DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
00588           }
00589           return p[l];
00590         }
00591 
00593     template<class T>
00594     class RealIterator
00595       : public BidirectionalIteratorFacade<RealIterator<T>, T>
00596         {
00597         public:
00599           typedef typename remove_const<T>::type ValueType;
00600 
00601           friend class BidirectionalIteratorFacade<RealIterator<const ValueType>, const ValueType>;
00602           friend class BidirectionalIteratorFacade<RealIterator<ValueType>, ValueType>;
00603           friend class RealIterator<const ValueType>;
00604           friend class RealIterator<ValueType>;
00605 
00607           RealIterator ()
00608             : p(0), j(0), i(0)
00609           {}
00610 
00612           RealIterator (B* _p, size_type* _j, size_type _i) 
00613             : p(_p), j(_j), i(_i)
00614           {       }
00615 
00619           RealIterator(const RealIterator<ValueType>& it)
00620             : p(it.p), j(it.j), i(it.i)
00621           {}
00622           
00623           
00625           bool equals (const RealIterator<ValueType>& it) const
00626           {
00627                 assert(p==it.p);
00628                 return (i)==(it.i);
00629           }
00630 
00632           bool equals (const RealIterator<const ValueType>& it) const
00633           {
00634                 assert(p==it.p);
00635                 return (i)==(it.i);
00636           }
00637 
00638 
00640           size_type index () const
00641           {
00642                 return j[i];
00643           }
00644 
00646           void setindex (size_type k)
00647           {
00648                 return j[i] = k;
00649           }
00650           
00658           size_type offset () const
00659           {
00660             return i;
00661           }
00662           
00663         private:
00665           void increment()
00666           {
00667             ++i;
00668           }
00669           
00671           void decrement()
00672           {
00673             --i;
00674           }
00675 
00677           B& dereference () const
00678           {
00679             return p[i];
00680           }
00681 
00682           B* p;
00683           size_type* j;
00684           size_type i;
00685         };
00686 
00688     typedef RealIterator<B> iterator;
00689     
00691         iterator begin ()
00692         {
00693           return iterator(p,j,0);
00694         }
00695 
00697         iterator end ()
00698         {
00699           return iterator(p,j,n);
00700         }
00701 
00704         iterator beforeEnd ()
00705         {
00706           return iterator(p,j,n-1);
00707         }
00708 
00711         iterator beforeBegin ()
00712         {
00713           return iterator(p,j,-1);
00714         }
00715 
00717         iterator find (size_type i)
00718         {
00719           size_type l=0, r=n-1;
00720           while (l<r)
00721                 {
00722                   size_type q = (l+r)/2;
00723                   if (i <= j[q]) r=q;
00724                   else l = q+1;
00725                 }
00726 
00727           if (n && i==j[l])
00728                 return iterator(p,j,l);
00729           else
00730                 return iterator(p,j,n);
00731         }
00732 
00734     typedef RealIterator<const B> const_iterator;
00735     
00737         const_iterator begin () const
00738         {
00739           return const_iterator(p,j,0);
00740         }
00741 
00743         const_iterator end () const
00744         {
00745           return const_iterator(p,j,n);
00746         }
00747 
00750         const_iterator beforeEnd () const
00751         {
00752           return const_iterator(p,j,n-1);
00753         }
00754 
00757         const_iterator beforeBegin () const
00758         {
00759           return const_iterator(p,j,-1);
00760         }
00761 
00763         const_iterator find (size_type i) const
00764         {
00765           size_type l=0, r=n-1;
00766           while (l<r)
00767                 {
00768                   size_type q = (l+r)/2;
00769                   if (i <= j[q]) r=q;
00770                   else l = q+1;
00771                 }
00772 
00773           if (n && i==j[l])
00774                 return const_iterator(p,j,l);
00775           else
00776                 return const_iterator(p,j,n);
00777         }
00778 
00779         //===== sizes
00780 
00782         size_type size () const
00783         {
00784           return n;
00785         }
00786 
00787   protected:
00789         compressed_base_array_unmanaged ()
00790           : n(0), p(0), j(0)
00791         {}
00792 
00793         size_type n;  // number of elements in array
00794         B *p;   // pointer to dynamically allocated built-in array
00795         size_type* j; // the index set
00796   };
00797 
00798 } // end namespace
00799 
00800 #endif