dune-common  2.2.0
arraylist.hh
Go to the documentation of this file.
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