dune-istl
2.2.0
|
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