dune-common
2.2.0
|
00001 // $Id: arraylist.hh 6785 2012-05-31 22:07:47Z sander $ 00002 00003 #ifndef DUNE_ARRAYLIST_HH 00004 #define DUNE_ARRAYLIST_HH 00005 00006 #include<cassert> 00007 #include<vector> 00008 #include"shared_ptr.hh" 00009 #include"array.hh" 00010 #include"iteratorfacades.hh" 00011 00012 namespace Dune 00013 { 00014 // forward declaration 00015 template<class T, int N, class A> 00016 class ArrayListIterator; 00017 00018 template<class T, int N, class A> 00019 class ConstArrayListIterator; 00020 00057 template<class T, int N=100, class A=std::allocator<T> > 00058 class ArrayList 00059 { 00060 public: 00066 typedef T MemberType; 00067 00071 typedef T value_type; 00072 00076 typedef T& reference; 00077 00081 typedef const T& const_reference; 00082 00086 typedef T* pointer; 00087 00091 typedef const T* const_pointer; 00092 00093 enum 00094 { 00099 chunkSize_ = (N > 0)? N : 1 00100 }; 00101 00105 typedef ArrayListIterator<MemberType,N,A> iterator; 00106 00110 typedef ConstArrayListIterator<MemberType,N,A> const_iterator; 00111 00115 typedef std::size_t size_type; 00116 00120 typedef std::ptrdiff_t difference_type; 00121 00126 iterator begin(); 00127 00133 const_iterator begin() const; 00134 00139 iterator end(); 00140 00145 const_iterator end() const; 00146 00151 inline void push_back(const_reference entry); 00152 00158 inline reference operator[](size_type i); 00159 00165 inline const_reference operator[](size_type i) const; 00166 00171 inline size_type size() const; 00172 00180 inline void purge(); 00181 00185 inline void clear(); 00189 ArrayList(); 00190 00191 private: 00192 00196 typedef typename A::template rebind<shared_ptr<array<MemberType,chunkSize_> > >::other 00197 SmartPointerAllocator; 00198 00202 typedef typename A::template rebind<array<MemberType,chunkSize_> >::other 00203 ArrayAllocator; 00204 00208 friend class ArrayListIterator<T,N,A>; 00209 friend class ConstArrayListIterator<T,N,A>; 00210 00212 std::vector<shared_ptr<array<MemberType,chunkSize_> >, 00213 SmartPointerAllocator> chunks_; 00222 size_type capacity_; 00224 size_type size_; 00226 size_type start_; 00235 inline reference elementAt(size_type i); 00236 00245 inline const_reference elementAt(size_type i) const; 00246 }; 00247 00248 00252 template<class T, int N, class A> 00253 class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>, 00254 typename A::value_type, 00255 typename A::reference, 00256 typename A::difference_type> 00257 { 00258 00259 friend class ArrayList<T,N,A>; 00260 friend class ConstArrayListIterator<T,N,A>; 00261 public: 00265 typedef typename A::value_type MemberType; 00266 00267 typedef typename A::difference_type difference_type; 00268 00269 typedef typename A::size_type size_type; 00270 00271 typedef typename A::reference reference; 00272 00273 typedef typename A::const_reference const_reference; 00274 00275 enum 00276 { 00282 chunkSize_ = (N > 0)? N : 1 00283 }; 00284 00285 00291 inline bool equals(const ArrayListIterator<MemberType,N,A>& other)const; 00292 00298 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other)const; 00299 00303 inline void increment(); 00304 00308 inline void decrement(); 00309 00314 inline reference elementAt(size_type i)const; 00315 00320 inline reference dereference()const; 00321 00333 inline void eraseToHere(); 00334 00336 inline size_type position(){return position_;} 00337 00339 inline void advance(difference_type n); 00340 00342 inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other)const; 00343 00345 inline ArrayListIterator<T,N,A>& operator=(const ArrayListIterator<T,N,A>& other); 00346 00348 inline ArrayListIterator() : position_(0) 00349 {} 00350 00351 private: 00357 inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position); 00358 00362 size_type position_; 00366 ArrayList<T,N,A>* list_; 00367 }; 00368 00372 template<class T, int N, class A> 00373 class ConstArrayListIterator 00374 : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>, 00375 const typename A::value_type, 00376 typename A::const_reference, 00377 typename A::difference_type> 00378 { 00379 00380 friend class ArrayList<T,N,A>; 00381 friend class ArrayListIterator<T,N,A>; 00382 00383 public: 00387 typedef typename A::value_type MemberType; 00388 00389 typedef typename A::difference_type difference_type; 00390 00391 typedef typename A::size_type size_type; 00392 00393 typedef typename A::reference reference; 00394 00395 typedef typename A::const_reference const_reference; 00396 enum 00397 { 00403 chunkSize_ = (N > 0)? N : 1 00404 }; 00405 00411 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other)const; 00412 00416 inline void increment(); 00417 00421 inline void decrement(); 00422 00424 inline void advance(difference_type n); 00425 00427 inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other)const; 00428 00433 inline const_reference elementAt(size_type i)const; 00434 00439 inline const_reference dereference()const; 00440 00441 inline const ConstArrayListIterator<T,N,A>& operator=(const ConstArrayListIterator<T,N,A>& other); 00442 00443 inline ConstArrayListIterator() : position_(0) 00444 {} 00445 00446 inline ConstArrayListIterator(const ArrayListIterator<T,N,A>& other); 00447 00448 private: 00449 00455 inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position); 00456 00460 size_type position_; 00464 const ArrayList<T,N,A>* list_; 00465 }; 00466 00467 00468 template<class T, int N, class A> 00469 ArrayList<T,N,A>::ArrayList() 00470 : capacity_(0), size_(0), start_(0) 00471 { 00472 chunks_.reserve(100); 00473 } 00474 00475 template<class T, int N, class A> 00476 void ArrayList<T,N,A>::clear(){ 00477 capacity_=0; 00478 size_=0; 00479 start_=0; 00480 chunks_.clear(); 00481 } 00482 00483 template<class T, int N, class A> 00484 size_t ArrayList<T,N,A>::size() const 00485 { 00486 return size_; 00487 } 00488 00489 template<class T, int N, class A> 00490 void ArrayList<T,N,A>::push_back(const_reference entry) 00491 { 00492 size_t index=start_+size_; 00493 if(index==capacity_) 00494 { 00495 chunks_.push_back(shared_ptr<array<MemberType,chunkSize_> >(new array<MemberType,chunkSize_>())); 00496 capacity_ += chunkSize_; 00497 } 00498 elementAt(index)=entry; 00499 ++size_; 00500 } 00501 00502 template<class T, int N, class A> 00503 typename ArrayList<T,N,A>::reference ArrayList<T,N,A>::operator[](size_type i) 00504 { 00505 return elementAt(start_+i); 00506 } 00507 00508 00509 template<class T, int N, class A> 00510 typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::operator[](size_type i) const 00511 { 00512 return elementAt(start_+i); 00513 } 00514 00515 template<class T, int N, class A> 00516 typename ArrayList<T,N,A>::reference ArrayList<T,N,A>::elementAt(size_type i) 00517 { 00518 return chunks_[i/chunkSize_]->operator[](i%chunkSize_); 00519 } 00520 00521 00522 template<class T, int N, class A> 00523 typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::elementAt(size_type i) const 00524 { 00525 return chunks_[i/chunkSize_]->operator[](i%chunkSize_); 00526 } 00527 00528 template<class T, int N, class A> 00529 ArrayListIterator<T,N,A> ArrayList<T,N,A>::begin() 00530 { 00531 return ArrayListIterator<T,N,A>(*this, start_); 00532 } 00533 00534 template<class T, int N, class A> 00535 ConstArrayListIterator<T,N,A> ArrayList<T,N,A>::begin() const 00536 { 00537 return ConstArrayListIterator<T,N,A>(*this, start_); 00538 } 00539 00540 template<class T, int N, class A> 00541 ArrayListIterator<T,N,A> ArrayList<T,N,A>::end() 00542 { 00543 return ArrayListIterator<T,N,A>(*this, start_+size_); 00544 } 00545 00546 template<class T, int N, class A> 00547 ConstArrayListIterator<T,N,A> ArrayList<T,N,A>::end() const 00548 { 00549 return ConstArrayListIterator<T,N,A>(*this, start_+size_); 00550 } 00551 00552 template<class T, int N, class A> 00553 void ArrayList<T,N,A>::purge() 00554 { 00555 // Distance to copy to the left. 00556 size_t distance = start_/chunkSize_; 00557 if(distance>0){ 00558 // Number of chunks with entries in it; 00559 size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ ); 00560 00561 typedef typename std::vector<shared_ptr<array<MemberType, 00562 chunkSize_> > >::iterator iterator; 00563 00564 // Copy chunks to the left. 00565 std::copy(chunks_.begin()+distance, 00566 chunks_.begin()+(distance+chunks), chunks_.begin()); 00567 00568 // Calculate new parameters 00569 start_ = start_ % chunkSize_; 00570 //capacity += distance * chunkSize_; 00571 } 00572 } 00573 00574 template<class T, int N, class A> 00575 void ArrayListIterator<T,N,A>::advance(difference_type i) 00576 { 00577 position_+=i; 00578 } 00579 00580 template<class T, int N, class A> 00581 void ConstArrayListIterator<T,N,A>::advance(difference_type i) 00582 { 00583 position_+=i; 00584 } 00585 00586 00587 template<class T, int N, class A> 00588 bool ArrayListIterator<T,N,A>::equals(const ArrayListIterator<MemberType,N,A>& other)const 00589 { 00590 // Makes only sense if we reference a common list 00591 assert(list_==(other.list_)); 00592 return position_==other.position_ ; 00593 } 00594 00595 00596 template<class T, int N, class A> 00597 bool ArrayListIterator<T,N,A>::equals(const ConstArrayListIterator<MemberType,N,A>& other)const 00598 { 00599 // Makes only sense if we reference a common list 00600 assert(list_==(other.list_)); 00601 return position_==other.position_ ; 00602 } 00603 00604 00605 template<class T, int N, class A> 00606 bool ConstArrayListIterator<T,N,A>::equals(const ConstArrayListIterator<MemberType,N,A>& other)const 00607 { 00608 // Makes only sense if we reference a common list 00609 assert(list_==(other.list_)); 00610 return position_==other.position_ ; 00611 } 00612 00613 template<class T, int N, class A> 00614 void ArrayListIterator<T,N,A>::increment() 00615 { 00616 ++position_; 00617 } 00618 00619 template<class T, int N, class A> 00620 void ConstArrayListIterator<T,N,A>::increment() 00621 { 00622 ++position_; 00623 } 00624 00625 template<class T, int N, class A> 00626 void ArrayListIterator<T,N,A>::decrement() 00627 { 00628 --position_; 00629 } 00630 00631 template<class T, int N, class A> 00632 void ConstArrayListIterator<T,N,A>::decrement() 00633 { 00634 --position_; 00635 } 00636 00637 template<class T, int N, class A> 00638 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::elementAt(size_type i) const 00639 { 00640 return list_->elementAt(i+position_); 00641 } 00642 00643 template<class T, int N, class A> 00644 typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::elementAt(size_type i) const 00645 { 00646 return list_->elementAt(i+position_); 00647 } 00648 00649 template<class T, int N, class A> 00650 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::dereference() const 00651 { 00652 return list_->elementAt(position_); 00653 } 00654 00655 template<class T, int N, class A> 00656 typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::dereference() const 00657 { 00658 return list_->elementAt(position_); 00659 } 00660 00661 template<class T, int N, class A> 00662 typename ArrayListIterator<T,N,A>::difference_type ArrayListIterator<T,N,A>::distanceTo(const ArrayListIterator<T,N,A>& other) const 00663 { 00664 // Makes only sense if we reference a common list 00665 assert(list_==(other.list_)); 00666 return other.position_ - position_; 00667 } 00668 00669 template<class T, int N, class A> 00670 typename ConstArrayListIterator<T,N,A>::difference_type ConstArrayListIterator<T,N,A>::distanceTo(const ConstArrayListIterator<T,N,A>& other) const 00671 { 00672 // Makes only sense if we reference a common list 00673 assert(list_==(other.list_)); 00674 return other.position_ - position_; 00675 } 00676 00677 template<class T, int N, class A> 00678 ArrayListIterator<T,N,A>& ArrayListIterator<T,N,A>::operator=(const ArrayListIterator<T,N,A>& other) 00679 { 00680 position_=other.position_; 00681 list_=other.list_; 00682 return *this; 00683 } 00684 00685 template<class T, int N, class A> 00686 const ConstArrayListIterator<T,N,A>& ConstArrayListIterator<T,N,A>::operator=(const ConstArrayListIterator<T,N,A>& other) 00687 { 00688 position_=other.position_; 00689 list_=other.list_; 00690 return *this; 00691 } 00692 00693 template<class T, int N, class A> 00694 void ArrayListIterator<T,N,A>::eraseToHere() 00695 { 00696 list_->size_ -= ++position_ - list_->start_; 00697 // chunk number of the new position. 00698 size_t posChunkStart = position_ / chunkSize_; 00699 // number of chunks to deallocate 00700 size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_) 00701 / chunkSize_; 00702 list_->start_ = position_; 00703 00704 // Deallocate memory not needed any more. 00705 for(size_t chunk=0; chunk<chunks;chunk++) { 00706 --posChunkStart; 00707 list_->chunks_[posChunkStart].reset(); 00708 } 00709 00710 // Capacity stays the same as the chunks before us 00711 // are still there. They null pointers. 00712 assert(list_->start_+list_->size_<=list_->capacity_); 00713 } 00714 00715 template<class T, int N, class A> 00716 ArrayListIterator<T,N,A>::ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position) 00717 : position_(position), list_(&arrayList) 00718 {} 00719 00720 00721 template<class T, int N, class A> 00722 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, 00723 size_type position) 00724 : position_(position), list_(&arrayList) 00725 {} 00726 00727 template<class T, int N, class A> 00728 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayListIterator<T,N,A>& other) 00729 : position_(other.position_), list_(other.list_) 00730 {} 00731 00732 00734 } 00735 #endif