00001
00002
00003
00004 #ifndef DUNE_COMMON_ARRAYLIST_HH
00005 #define DUNE_COMMON_ARRAYLIST_HH
00006
00007 #include <array>
00008 #include <cassert>
00009 #include <memory>
00010 #include <vector>
00011 #include "iteratorfacades.hh"
00012
00013 namespace Dune
00014 {
00015
00016 template<class T, int N, class A>
00017 class ArrayListIterator;
00018
00019 template<class T, int N, class A>
00020 class ConstArrayListIterator;
00021
00058 template<class T, int N=100, class A=std::allocator<T> >
00059 class ArrayList
00060 {
00061 public:
00067 typedef T MemberType;
00068
00072 typedef T value_type;
00073
00077 typedef T& reference;
00078
00082 typedef const T& const_reference;
00083
00087 typedef T* pointer;
00088
00092 typedef const T* const_pointer;
00093
00094 enum
00095 {
00100 chunkSize_ = (N > 0) ? N : 1
00101 };
00102
00106 typedef ArrayListIterator<MemberType,N,A> iterator;
00107
00111 typedef ConstArrayListIterator<MemberType,N,A> const_iterator;
00112
00116 typedef std::size_t size_type;
00117
00121 typedef std::ptrdiff_t difference_type;
00122
00127 iterator begin();
00128
00134 const_iterator begin() const;
00135
00140 iterator end();
00141
00146 const_iterator end() const;
00147
00152 inline void push_back(const_reference entry);
00153
00159 inline reference operator[](size_type i);
00160
00166 inline const_reference operator[](size_type i) const;
00167
00172 inline size_type size() const;
00173
00181 inline void purge();
00182
00186 inline void clear();
00190 ArrayList();
00191
00192 private:
00193
00197 typedef typename A::template rebind<std::shared_ptr<std::array<MemberType,chunkSize_> > >::other
00198 SmartPointerAllocator;
00199
00203 typedef typename A::template rebind<std::array<MemberType,chunkSize_> >::other
00204 ArrayAllocator;
00205
00209 friend class ArrayListIterator<T,N,A>;
00210 friend class ConstArrayListIterator<T,N,A>;
00211
00213 std::vector<std::shared_ptr<std::array<MemberType,chunkSize_> >,
00214 SmartPointerAllocator> chunks_;
00223 size_type capacity_;
00225 size_type size_;
00227 size_type start_;
00236 inline reference elementAt(size_type i);
00237
00246 inline const_reference elementAt(size_type i) const;
00247 };
00248
00249
00253 template<class T, int N, class A>
00254 class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>,
00255 typename A::value_type,
00256 typename A::reference,
00257 typename A::difference_type>
00258 {
00259
00260 friend class ArrayList<T,N,A>;
00261 friend class ConstArrayListIterator<T,N,A>;
00262 public:
00266 typedef typename A::value_type MemberType;
00267
00268 typedef typename A::difference_type difference_type;
00269
00270 typedef typename A::size_type size_type;
00271
00272 typedef typename A::reference reference;
00273
00274 typedef typename A::const_reference const_reference;
00275
00276 enum
00277 {
00283 chunkSize_ = (N > 0) ? N : 1
00284 };
00285
00286
00292 inline bool equals(const ArrayListIterator<MemberType,N,A>& other) const;
00293
00299 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
00300
00304 inline void increment();
00305
00309 inline void decrement();
00310
00315 inline reference elementAt(size_type i) const;
00316
00321 inline reference dereference() const;
00322
00334 inline void eraseToHere();
00335
00337 inline size_type position(){return position_;}
00338
00340 inline void advance(difference_type n);
00341
00343 inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other) const;
00344
00346 inline ArrayListIterator<T,N,A>& operator=(const ArrayListIterator<T,N,A>& other);
00347
00349 inline ArrayListIterator() : position_(0)
00350 {}
00351
00352 private:
00358 inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position);
00359
00363 size_type position_;
00367 ArrayList<T,N,A>* list_;
00368 };
00369
00373 template<class T, int N, class A>
00374 class ConstArrayListIterator
00375 : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>,
00376 const typename A::value_type,
00377 typename A::const_reference,
00378 typename A::difference_type>
00379 {
00380
00381 friend class ArrayList<T,N,A>;
00382 friend class ArrayListIterator<T,N,A>;
00383
00384 public:
00388 typedef typename A::value_type MemberType;
00389
00390 typedef typename A::difference_type difference_type;
00391
00392 typedef typename A::size_type size_type;
00393
00394 typedef typename A::reference reference;
00395
00396 typedef typename A::const_reference const_reference;
00397 enum
00398 {
00404 chunkSize_ = (N > 0) ? N : 1
00405 };
00406
00412 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
00413
00417 inline void increment();
00418
00422 inline void decrement();
00423
00425 inline void advance(difference_type n);
00426
00428 inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other) const;
00429
00434 inline const_reference elementAt(size_type i) const;
00435
00440 inline const_reference dereference() const;
00441
00442 inline const ConstArrayListIterator<T,N,A>& operator=(const ConstArrayListIterator<T,N,A>& other);
00443
00444 inline ConstArrayListIterator() : position_(0)
00445 {}
00446
00447 inline ConstArrayListIterator(const ArrayListIterator<T,N,A>& other);
00448
00449 private:
00450
00456 inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position);
00457
00461 size_type position_;
00465 const ArrayList<T,N,A>* list_;
00466 };
00467
00468
00469 template<class T, int N, class A>
00470 ArrayList<T,N,A>::ArrayList()
00471 : capacity_(0), size_(0), start_(0)
00472 {
00473 chunks_.reserve(100);
00474 }
00475
00476 template<class T, int N, class A>
00477 void ArrayList<T,N,A>::clear(){
00478 capacity_=0;
00479 size_=0;
00480 start_=0;
00481 chunks_.clear();
00482 }
00483
00484 template<class T, int N, class A>
00485 size_t ArrayList<T,N,A>::size() const
00486 {
00487 return size_;
00488 }
00489
00490 template<class T, int N, class A>
00491 void ArrayList<T,N,A>::push_back(const_reference entry)
00492 {
00493 size_t index=start_+size_;
00494 if(index==capacity_)
00495 {
00496 chunks_.push_back(std::make_shared<std::array<MemberType,chunkSize_> >());
00497 capacity_ += chunkSize_;
00498 }
00499 elementAt(index)=entry;
00500 ++size_;
00501 }
00502
00503 template<class T, int N, class A>
00504 typename ArrayList<T,N,A>::reference ArrayList<T,N,A>::operator[](size_type i)
00505 {
00506 return elementAt(start_+i);
00507 }
00508
00509
00510 template<class T, int N, class A>
00511 typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::operator[](size_type i) const
00512 {
00513 return elementAt(start_+i);
00514 }
00515
00516 template<class T, int N, class A>
00517 typename ArrayList<T,N,A>::reference ArrayList<T,N,A>::elementAt(size_type i)
00518 {
00519 return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
00520 }
00521
00522
00523 template<class T, int N, class A>
00524 typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::elementAt(size_type i) const
00525 {
00526 return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
00527 }
00528
00529 template<class T, int N, class A>
00530 ArrayListIterator<T,N,A> ArrayList<T,N,A>::begin()
00531 {
00532 return ArrayListIterator<T,N,A>(*this, start_);
00533 }
00534
00535 template<class T, int N, class A>
00536 ConstArrayListIterator<T,N,A> ArrayList<T,N,A>::begin() const
00537 {
00538 return ConstArrayListIterator<T,N,A>(*this, start_);
00539 }
00540
00541 template<class T, int N, class A>
00542 ArrayListIterator<T,N,A> ArrayList<T,N,A>::end()
00543 {
00544 return ArrayListIterator<T,N,A>(*this, start_+size_);
00545 }
00546
00547 template<class T, int N, class A>
00548 ConstArrayListIterator<T,N,A> ArrayList<T,N,A>::end() const
00549 {
00550 return ConstArrayListIterator<T,N,A>(*this, start_+size_);
00551 }
00552
00553 template<class T, int N, class A>
00554 void ArrayList<T,N,A>::purge()
00555 {
00556
00557 size_t distance = start_/chunkSize_;
00558 if(distance>0) {
00559
00560 size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ );
00561
00562
00563 std::copy(chunks_.begin()+distance,
00564 chunks_.begin()+(distance+chunks), chunks_.begin());
00565
00566
00567 start_ = start_ % chunkSize_;
00568
00569 }
00570 }
00571
00572 template<class T, int N, class A>
00573 void ArrayListIterator<T,N,A>::advance(difference_type i)
00574 {
00575 position_+=i;
00576 }
00577
00578 template<class T, int N, class A>
00579 void ConstArrayListIterator<T,N,A>::advance(difference_type i)
00580 {
00581 position_+=i;
00582 }
00583
00584
00585 template<class T, int N, class A>
00586 bool ArrayListIterator<T,N,A>::equals(const ArrayListIterator<MemberType,N,A>& other) const
00587 {
00588
00589 assert(list_==(other.list_));
00590 return position_==other.position_ ;
00591 }
00592
00593
00594 template<class T, int N, class A>
00595 bool ArrayListIterator<T,N,A>::equals(const ConstArrayListIterator<MemberType,N,A>& other) const
00596 {
00597
00598 assert(list_==(other.list_));
00599 return position_==other.position_ ;
00600 }
00601
00602
00603 template<class T, int N, class A>
00604 bool ConstArrayListIterator<T,N,A>::equals(const ConstArrayListIterator<MemberType,N,A>& other) const
00605 {
00606
00607 assert(list_==(other.list_));
00608 return position_==other.position_ ;
00609 }
00610
00611 template<class T, int N, class A>
00612 void ArrayListIterator<T,N,A>::increment()
00613 {
00614 ++position_;
00615 }
00616
00617 template<class T, int N, class A>
00618 void ConstArrayListIterator<T,N,A>::increment()
00619 {
00620 ++position_;
00621 }
00622
00623 template<class T, int N, class A>
00624 void ArrayListIterator<T,N,A>::decrement()
00625 {
00626 --position_;
00627 }
00628
00629 template<class T, int N, class A>
00630 void ConstArrayListIterator<T,N,A>::decrement()
00631 {
00632 --position_;
00633 }
00634
00635 template<class T, int N, class A>
00636 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::elementAt(size_type i) const
00637 {
00638 return list_->elementAt(i+position_);
00639 }
00640
00641 template<class T, int N, class A>
00642 typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::elementAt(size_type i) const
00643 {
00644 return list_->elementAt(i+position_);
00645 }
00646
00647 template<class T, int N, class A>
00648 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::dereference() const
00649 {
00650 return list_->elementAt(position_);
00651 }
00652
00653 template<class T, int N, class A>
00654 typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::dereference() const
00655 {
00656 return list_->elementAt(position_);
00657 }
00658
00659 template<class T, int N, class A>
00660 typename ArrayListIterator<T,N,A>::difference_type ArrayListIterator<T,N,A>::distanceTo(const ArrayListIterator<T,N,A>& other) const
00661 {
00662
00663 assert(list_==(other.list_));
00664 return other.position_ - position_;
00665 }
00666
00667 template<class T, int N, class A>
00668 typename ConstArrayListIterator<T,N,A>::difference_type ConstArrayListIterator<T,N,A>::distanceTo(const ConstArrayListIterator<T,N,A>& other) const
00669 {
00670
00671 assert(list_==(other.list_));
00672 return other.position_ - position_;
00673 }
00674
00675 template<class T, int N, class A>
00676 ArrayListIterator<T,N,A>& ArrayListIterator<T,N,A>::operator=(const ArrayListIterator<T,N,A>& other)
00677 {
00678 position_=other.position_;
00679 list_=other.list_;
00680 return *this;
00681 }
00682
00683 template<class T, int N, class A>
00684 const ConstArrayListIterator<T,N,A>& ConstArrayListIterator<T,N,A>::operator=(const ConstArrayListIterator<T,N,A>& other)
00685 {
00686 position_=other.position_;
00687 list_=other.list_;
00688 return *this;
00689 }
00690
00691 template<class T, int N, class A>
00692 void ArrayListIterator<T,N,A>::eraseToHere()
00693 {
00694 list_->size_ -= ++position_ - list_->start_;
00695
00696 size_t posChunkStart = position_ / chunkSize_;
00697
00698 size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_)
00699 / chunkSize_;
00700 list_->start_ = position_;
00701
00702
00703 for(size_t chunk=0; chunk<chunks; chunk++) {
00704 --posChunkStart;
00705 list_->chunks_[posChunkStart].reset();
00706 }
00707
00708
00709
00710 assert(list_->start_+list_->size_<=list_->capacity_);
00711 }
00712
00713 template<class T, int N, class A>
00714 ArrayListIterator<T,N,A>::ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position)
00715 : position_(position), list_(&arrayList)
00716 {}
00717
00718
00719 template<class T, int N, class A>
00720 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList,
00721 size_type position)
00722 : position_(position), list_(&arrayList)
00723 {}
00724
00725 template<class T, int N, class A>
00726 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayListIterator<T,N,A>& other)
00727 : position_(other.position_), list_(other.list_)
00728 {}
00729
00730
00732 }
00733 #endif