dune-common  2.2.0
arraylist.hh
Go to the documentation of this file.
1 // $Id: arraylist.hh 6785 2012-05-31 22:07:47Z sander $
2 
3 #ifndef DUNE_ARRAYLIST_HH
4 #define DUNE_ARRAYLIST_HH
5 
6 #include<cassert>
7 #include<vector>
8 #include"shared_ptr.hh"
9 #include"array.hh"
10 #include"iteratorfacades.hh"
11 
12 namespace Dune
13 {
14  // forward declaration
15  template<class T, int N, class A>
16  class ArrayListIterator;
17 
18  template<class T, int N, class A>
19  class ConstArrayListIterator;
20 
57  template<class T, int N=100, class A=std::allocator<T> >
58  class ArrayList
59  {
60  public:
66  typedef T MemberType;
67 
71  typedef T value_type;
72 
76  typedef T& reference;
77 
81  typedef const T& const_reference;
82 
86  typedef T* pointer;
87 
91  typedef const T* const_pointer;
92 
93  enum
94  {
99  chunkSize_ = (N > 0)? N : 1
100  };
101 
106 
111 
115  typedef std::size_t size_type;
116 
120  typedef std::ptrdiff_t difference_type;
121 
126  iterator begin();
127 
133  const_iterator begin() const;
134 
139  iterator end();
140 
145  const_iterator end() const;
146 
151  inline void push_back(const_reference entry);
152 
158  inline reference operator[](size_type i);
159 
165  inline const_reference operator[](size_type i) const;
166 
171  inline size_type size() const;
172 
180  inline void purge();
181 
185  inline void clear();
189  ArrayList();
190 
191  private:
192 
196  typedef typename A::template rebind<shared_ptr<array<MemberType,chunkSize_> > >::other
197  SmartPointerAllocator;
198 
202  typedef typename A::template rebind<array<MemberType,chunkSize_> >::other
203  ArrayAllocator;
204 
208  friend class ArrayListIterator<T,N,A>;
209  friend class ConstArrayListIterator<T,N,A>;
210 
212  std::vector<shared_ptr<array<MemberType,chunkSize_> >,
213  SmartPointerAllocator> chunks_;
222  size_type capacity_;
224  size_type size_;
226  size_type start_;
235  inline reference elementAt(size_type i);
236 
245  inline const_reference elementAt(size_type i) const;
246  };
247 
248 
252  template<class T, int N, class A>
253  class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>,
254  typename A::value_type,
255  typename A::reference,
256  typename A::difference_type>
257  {
258 
259  friend class ArrayList<T,N,A>;
260  friend class ConstArrayListIterator<T,N,A>;
261  public:
265  typedef typename A::value_type MemberType;
266 
267  typedef typename A::difference_type difference_type;
268 
269  typedef typename A::size_type size_type;
270 
271  typedef typename A::reference reference;
272 
273  typedef typename A::const_reference const_reference;
274 
275  enum
276  {
282  chunkSize_ = (N > 0)? N : 1
283  };
284 
285 
291  inline bool equals(const ArrayListIterator<MemberType,N,A>& other)const;
292 
298  inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other)const;
299 
303  inline void increment();
304 
308  inline void decrement();
309 
314  inline reference elementAt(size_type i)const;
315 
320  inline reference dereference()const;
321 
333  inline void eraseToHere();
334 
336  inline size_type position(){return position_;}
337 
339  inline void advance(difference_type n);
340 
342  inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other)const;
343 
345  inline ArrayListIterator<T,N,A>& operator=(const ArrayListIterator<T,N,A>& other);
346 
348  inline ArrayListIterator() : position_(0)
349  {}
350 
351  private:
357  inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position);
358 
362  size_type position_;
366  ArrayList<T,N,A>* list_;
367  };
368 
372  template<class T, int N, class A>
374  : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>,
375  const typename A::value_type,
376  typename A::const_reference,
377  typename A::difference_type>
378  {
379 
380  friend class ArrayList<T,N,A>;
381  friend class ArrayListIterator<T,N,A>;
382 
383  public:
387  typedef typename A::value_type MemberType;
388 
389  typedef typename A::difference_type difference_type;
390 
391  typedef typename A::size_type size_type;
392 
393  typedef typename A::reference reference;
394 
395  typedef typename A::const_reference const_reference;
396  enum
397  {
403  chunkSize_ = (N > 0)? N : 1
404  };
405 
411  inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other)const;
412 
416  inline void increment();
417 
421  inline void decrement();
422 
424  inline void advance(difference_type n);
425 
427  inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other)const;
428 
433  inline const_reference elementAt(size_type i)const;
434 
439  inline const_reference dereference()const;
440 
441  inline const ConstArrayListIterator<T,N,A>& operator=(const ConstArrayListIterator<T,N,A>& other);
442 
443  inline ConstArrayListIterator() : position_(0)
444  {}
445 
447 
448  private:
449 
455  inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position);
456 
460  size_type position_;
464  const ArrayList<T,N,A>* list_;
465  };
466 
467 
468  template<class T, int N, class A>
470  : capacity_(0), size_(0), start_(0)
471  {
472  chunks_.reserve(100);
473  }
474 
475  template<class T, int N, class A>
477  capacity_=0;
478  size_=0;
479  start_=0;
480  chunks_.clear();
481  }
482 
483  template<class T, int N, class A>
484  size_t ArrayList<T,N,A>::size() const
485  {
486  return size_;
487  }
488 
489  template<class T, int N, class A>
491  {
492  size_t index=start_+size_;
493  if(index==capacity_)
494  {
496  capacity_ += chunkSize_;
497  }
498  elementAt(index)=entry;
499  ++size_;
500  }
501 
502  template<class T, int N, class A>
504  {
505  return elementAt(start_+i);
506  }
507 
508 
509  template<class T, int N, class A>
511  {
512  return elementAt(start_+i);
513  }
514 
515  template<class T, int N, class A>
517  {
518  return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
519  }
520 
521 
522  template<class T, int N, class A>
523  typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::elementAt(size_type i) const
524  {
525  return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
526  }
527 
528  template<class T, int N, class A>
530  {
531  return ArrayListIterator<T,N,A>(*this, start_);
532  }
533 
534  template<class T, int N, class A>
536  {
537  return ConstArrayListIterator<T,N,A>(*this, start_);
538  }
539 
540  template<class T, int N, class A>
542  {
543  return ArrayListIterator<T,N,A>(*this, start_+size_);
544  }
545 
546  template<class T, int N, class A>
548  {
549  return ConstArrayListIterator<T,N,A>(*this, start_+size_);
550  }
551 
552  template<class T, int N, class A>
554  {
555  // Distance to copy to the left.
556  size_t distance = start_/chunkSize_;
557  if(distance>0){
558  // Number of chunks with entries in it;
559  size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ );
560 
561  typedef typename std::vector<shared_ptr<array<MemberType,
562  chunkSize_> > >::iterator iterator;
563 
564  // Copy chunks to the left.
565  std::copy(chunks_.begin()+distance,
566  chunks_.begin()+(distance+chunks), chunks_.begin());
567 
568  // Calculate new parameters
569  start_ = start_ % chunkSize_;
570  //capacity += distance * chunkSize_;
571  }
572  }
573 
574  template<class T, int N, class A>
576  {
577  position_+=i;
578  }
579 
580  template<class T, int N, class A>
582  {
583  position_+=i;
584  }
585 
586 
587  template<class T, int N, class A>
589  {
590  // Makes only sense if we reference a common list
591  assert(list_==(other.list_));
592  return position_==other.position_ ;
593  }
594 
595 
596  template<class T, int N, class A>
598  {
599  // Makes only sense if we reference a common list
600  assert(list_==(other.list_));
601  return position_==other.position_ ;
602  }
603 
604 
605  template<class T, int N, class A>
607  {
608  // Makes only sense if we reference a common list
609  assert(list_==(other.list_));
610  return position_==other.position_ ;
611  }
612 
613  template<class T, int N, class A>
615  {
616  ++position_;
617  }
618 
619  template<class T, int N, class A>
621  {
622  ++position_;
623  }
624 
625  template<class T, int N, class A>
627  {
628  --position_;
629  }
630 
631  template<class T, int N, class A>
633  {
634  --position_;
635  }
636 
637  template<class T, int N, class A>
639  {
640  return list_->elementAt(i+position_);
641  }
642 
643  template<class T, int N, class A>
645  {
646  return list_->elementAt(i+position_);
647  }
648 
649  template<class T, int N, class A>
651  {
652  return list_->elementAt(position_);
653  }
654 
655  template<class T, int N, class A>
657  {
658  return list_->elementAt(position_);
659  }
660 
661  template<class T, int N, class A>
663  {
664  // Makes only sense if we reference a common list
665  assert(list_==(other.list_));
666  return other.position_ - position_;
667  }
668 
669  template<class T, int N, class A>
671  {
672  // Makes only sense if we reference a common list
673  assert(list_==(other.list_));
674  return other.position_ - position_;
675  }
676 
677  template<class T, int N, class A>
679  {
680  position_=other.position_;
681  list_=other.list_;
682  return *this;
683  }
684 
685  template<class T, int N, class A>
687  {
688  position_=other.position_;
689  list_=other.list_;
690  return *this;
691  }
692 
693  template<class T, int N, class A>
695  {
696  list_->size_ -= ++position_ - list_->start_;
697  // chunk number of the new position.
698  size_t posChunkStart = position_ / chunkSize_;
699  // number of chunks to deallocate
700  size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_)
701  / chunkSize_;
702  list_->start_ = position_;
703 
704  // Deallocate memory not needed any more.
705  for(size_t chunk=0; chunk<chunks;chunk++) {
706  --posChunkStart;
707  list_->chunks_[posChunkStart].reset();
708  }
709 
710  // Capacity stays the same as the chunks before us
711  // are still there. They null pointers.
712  assert(list_->start_+list_->size_<=list_->capacity_);
713  }
714 
715  template<class T, int N, class A>
716  ArrayListIterator<T,N,A>::ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position)
717  : position_(position), list_(&arrayList)
718  {}
719 
720 
721  template<class T, int N, class A>
722  ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList,
723  size_type position)
724  : position_(position), list_(&arrayList)
725  {}
726 
727  template<class T, int N, class A>
729  : position_(other.position_), list_(other.list_)
730  {}
731 
732 
734 }
735 #endif