dune-common  2.3.1
arraylist.hh
Go to the documentation of this file.
1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=4 sw=2 sts=2:
3 // $Id$
4 
5 #ifndef DUNE_ARRAYLIST_HH
6 #define DUNE_ARRAYLIST_HH
7 
8 #include <cassert>
9 #include <vector>
10 #include "shared_ptr.hh"
11 #include "array.hh"
12 #include "iteratorfacades.hh"
13 
14 namespace Dune
15 {
16  // forward declaration
17  template<class T, int N, class A>
19 
20  template<class T, int N, class A>
22 
59  template<class T, int N=100, class A=std::allocator<T> >
60  class ArrayList
61  {
62  public:
68  typedef T MemberType;
69 
73  typedef T value_type;
74 
78  typedef T& reference;
79 
83  typedef const T& const_reference;
84 
88  typedef T* pointer;
89 
93  typedef const T* const_pointer;
94 
95  enum
96  {
101  chunkSize_ = (N > 0) ? N : 1
102  };
103 
108 
113 
117  typedef std::size_t size_type;
118 
122  typedef std::ptrdiff_t difference_type;
123 
128  iterator begin();
129 
135  const_iterator begin() const;
136 
141  iterator end();
142 
147  const_iterator end() const;
148 
153  inline void push_back(const_reference entry);
154 
160  inline reference operator[](size_type i);
161 
167  inline const_reference operator[](size_type i) const;
168 
173  inline size_type size() const;
174 
182  inline void purge();
183 
187  inline void clear();
191  ArrayList();
192 
193  private:
194 
198  typedef typename A::template rebind<shared_ptr<array<MemberType,chunkSize_> > >::other
199  SmartPointerAllocator;
200 
204  typedef typename A::template rebind<array<MemberType,chunkSize_> >::other
205  ArrayAllocator;
206 
210  friend class ArrayListIterator<T,N,A>;
211  friend class ConstArrayListIterator<T,N,A>;
212 
214  std::vector<shared_ptr<array<MemberType,chunkSize_> >,
215  SmartPointerAllocator> chunks_;
224  size_type capacity_;
226  size_type size_;
228  size_type start_;
237  inline reference elementAt(size_type i);
238 
247  inline const_reference elementAt(size_type i) const;
248  };
249 
250 
254  template<class T, int N, class A>
255  class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>,
256  typename A::value_type,
257  typename A::reference,
258  typename A::difference_type>
259  {
260 
261  friend class ArrayList<T,N,A>;
262  friend class ConstArrayListIterator<T,N,A>;
263  public:
267  typedef typename A::value_type MemberType;
268 
269  typedef typename A::difference_type difference_type;
270 
271  typedef typename A::size_type size_type;
272 
273  typedef typename A::reference reference;
274 
275  typedef typename A::const_reference const_reference;
276 
277  enum
278  {
284  chunkSize_ = (N > 0) ? N : 1
285  };
286 
287 
293  inline bool equals(const ArrayListIterator<MemberType,N,A>& other) const;
294 
300  inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
301 
305  inline void increment();
306 
310  inline void decrement();
311 
316  inline reference elementAt(size_type i) const;
317 
322  inline reference dereference() const;
323 
335  inline void eraseToHere();
336 
338  inline size_type position(){return position_;}
339 
341  inline void advance(difference_type n);
342 
344  inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other) const;
345 
347  inline ArrayListIterator<T,N,A>& operator=(const ArrayListIterator<T,N,A>& other);
348 
351  {}
352 
353  private:
359  inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position);
360 
364  size_type position_;
368  ArrayList<T,N,A>* list_;
369  };
370 
374  template<class T, int N, class A>
375  class ConstArrayListIterator
376  : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>,
377  const typename A::value_type,
378  typename A::const_reference,
379  typename A::difference_type>
380  {
381 
382  friend class ArrayList<T,N,A>;
383  friend class ArrayListIterator<T,N,A>;
384 
385  public:
389  typedef typename A::value_type MemberType;
390 
391  typedef typename A::difference_type difference_type;
392 
393  typedef typename A::size_type size_type;
394 
395  typedef typename A::reference reference;
396 
397  typedef typename A::const_reference const_reference;
398  enum
399  {
405  chunkSize_ = (N > 0) ? N : 1
406  };
407 
413  inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
414 
418  inline void increment();
419 
423  inline void decrement();
424 
426  inline void advance(difference_type n);
427 
429  inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other) const;
430 
435  inline const_reference elementAt(size_type i) const;
436 
441  inline const_reference dereference() const;
442 
443  inline const ConstArrayListIterator<T,N,A>& operator=(const ConstArrayListIterator<T,N,A>& other);
444 
446  {}
447 
449 
450  private:
451 
457  inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position);
458 
462  size_type position_;
466  const ArrayList<T,N,A>* list_;
467  };
468 
469 
470  template<class T, int N, class A>
472  : capacity_(0), size_(0), start_(0)
473  {
474  chunks_.reserve(100);
475  }
476 
477  template<class T, int N, class A>
479  capacity_=0;
480  size_=0;
481  start_=0;
482  chunks_.clear();
483  }
484 
485  template<class T, int N, class A>
486  size_t ArrayList<T,N,A>::size() const
487  {
488  return size_;
489  }
490 
491  template<class T, int N, class A>
492  void ArrayList<T,N,A>::push_back(const_reference entry)
493  {
494  size_t index=start_+size_;
495  if(index==capacity_)
496  {
498  capacity_ += chunkSize_;
499  }
500  elementAt(index)=entry;
501  ++size_;
502  }
503 
504  template<class T, int N, class A>
506  {
507  return elementAt(start_+i);
508  }
509 
510 
511  template<class T, int N, class A>
513  {
514  return elementAt(start_+i);
515  }
516 
517  template<class T, int N, class A>
519  {
520  return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
521  }
522 
523 
524  template<class T, int N, class A>
525  typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::elementAt(size_type i) const
526  {
527  return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
528  }
529 
530  template<class T, int N, class A>
532  {
533  return ArrayListIterator<T,N,A>(*this, start_);
534  }
535 
536  template<class T, int N, class A>
538  {
539  return ConstArrayListIterator<T,N,A>(*this, start_);
540  }
541 
542  template<class T, int N, class A>
544  {
545  return ArrayListIterator<T,N,A>(*this, start_+size_);
546  }
547 
548  template<class T, int N, class A>
550  {
551  return ConstArrayListIterator<T,N,A>(*this, start_+size_);
552  }
553 
554  template<class T, int N, class A>
556  {
557  // Distance to copy to the left.
558  size_t distance = start_/chunkSize_;
559  if(distance>0) {
560  // Number of chunks with entries in it;
561  size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ );
562 
563  // Copy chunks to the left.
564  std::copy(chunks_.begin()+distance,
565  chunks_.begin()+(distance+chunks), chunks_.begin());
566 
567  // Calculate new parameters
568  start_ = start_ % chunkSize_;
569  //capacity += distance * chunkSize_;
570  }
571  }
572 
573  template<class T, int N, class A>
574  void ArrayListIterator<T,N,A>::advance(difference_type i)
575  {
576  position_+=i;
577  }
578 
579  template<class T, int N, class A>
581  {
582  position_+=i;
583  }
584 
585 
586  template<class T, int N, class A>
588  {
589  // Makes only sense if we reference a common list
590  assert(list_==(other.list_));
591  return position_==other.position_ ;
592  }
593 
594 
595  template<class T, int N, class A>
597  {
598  // Makes only sense if we reference a common list
599  assert(list_==(other.list_));
600  return position_==other.position_ ;
601  }
602 
603 
604  template<class T, int N, class A>
606  {
607  // Makes only sense if we reference a common list
608  assert(list_==(other.list_));
609  return position_==other.position_ ;
610  }
611 
612  template<class T, int N, class A>
614  {
615  ++position_;
616  }
617 
618  template<class T, int N, class A>
620  {
621  ++position_;
622  }
623 
624  template<class T, int N, class A>
626  {
627  --position_;
628  }
629 
630  template<class T, int N, class A>
632  {
633  --position_;
634  }
635 
636  template<class T, int N, class A>
638  {
639  return list_->elementAt(i+position_);
640  }
641 
642  template<class T, int N, class A>
644  {
645  return list_->elementAt(i+position_);
646  }
647 
648  template<class T, int N, class A>
650  {
651  return list_->elementAt(position_);
652  }
653 
654  template<class T, int N, class A>
656  {
657  return list_->elementAt(position_);
658  }
659 
660  template<class T, int N, class A>
662  {
663  // Makes only sense if we reference a common list
664  assert(list_==(other.list_));
665  return other.position_ - position_;
666  }
667 
668  template<class T, int N, class A>
670  {
671  // Makes only sense if we reference a common list
672  assert(list_==(other.list_));
673  return other.position_ - position_;
674  }
675 
676  template<class T, int N, class A>
678  {
679  position_=other.position_;
680  list_=other.list_;
681  return *this;
682  }
683 
684  template<class T, int N, class A>
686  {
687  position_=other.position_;
688  list_=other.list_;
689  return *this;
690  }
691 
692  template<class T, int N, class A>
694  {
695  list_->size_ -= ++position_ - list_->start_;
696  // chunk number of the new position.
697  size_t posChunkStart = position_ / chunkSize_;
698  // number of chunks to deallocate
699  size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_)
700  / chunkSize_;
701  list_->start_ = position_;
702 
703  // Deallocate memory not needed any more.
704  for(size_t chunk=0; chunk<chunks; chunk++) {
705  --posChunkStart;
706  list_->chunks_[posChunkStart].reset();
707  }
708 
709  // Capacity stays the same as the chunks before us
710  // are still there. They null pointers.
711  assert(list_->start_+list_->size_<=list_->capacity_);
712  }
713 
714  template<class T, int N, class A>
715  ArrayListIterator<T,N,A>::ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position)
716  : position_(position), list_(&arrayList)
717  {}
718 
719 
720  template<class T, int N, class A>
721  ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList,
722  size_type position)
723  : position_(position), list_(&arrayList)
724  {}
725 
726  template<class T, int N, class A>
728  : position_(other.position_), list_(other.list_)
729  {}
730 
731 
733 }
734 #endif
difference_type distanceTo(const ConstArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:669
T & reference
The type of a reference to the type we store.
Definition: arraylist.hh:78
A::size_type size_type
Definition: arraylist.hh:393
std::size_t size_type
The size type.
Definition: arraylist.hh:117
const ConstArrayListIterator< T, N, A > & operator=(const ConstArrayListIterator< T, N, A > &other)
Definition: arraylist.hh:685
iterator end()
Get a random access iterator positioned after the last element.
Definition: arraylist.hh:543
Dune namespace.
Definition: alignment.hh:13
difference_type distanceTo(const ArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:661
bool equals(const ConstArrayListIterator< MemberType, N, A > &other) const
Comares to iterators.
Definition: arraylist.hh:605
T value_type
Value type for stl compliance.
Definition: arraylist.hh:73
const_reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:655
size_type position()
Definition: arraylist.hh:338
void advance(difference_type n)
Definition: arraylist.hh:580
std::size_t size_
The size of the buffer.
Definition: variablesizecommunicator.hh:132
void eraseToHere()
Erase all entries before the current position and the one at the current position.
Definition: arraylist.hh:693
A constant random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:21
A::difference_type difference_type
Definition: arraylist.hh:391
ArrayList()
Constructs an Array list with one chunk.
Definition: arraylist.hh:471
const_reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:643
std::size_t position_
The current position in the buffer.
Definition: variablesizecommunicator.hh:136
A::reference reference
Definition: arraylist.hh:273
A::reference reference
Definition: arraylist.hh:395
std::ptrdiff_t difference_type
The difference type.
Definition: arraylist.hh:122
T MemberType
The member type that is stored.
Definition: arraylist.hh:68
reference operator[](size_type i)
Get the element at specific position.
Definition: arraylist.hh:505
size_type size() const
Get the number of elements in the list.
Definition: arraylist.hh:486
void decrement()
decrement the iterator.
Definition: arraylist.hh:625
The number of elements in one chunk of the list. This has to be at least one. The default is 100...
Definition: arraylist.hh:101
bool equals(const ArrayListIterator< MemberType, N, A > &other) const
Comares two iterators.
Definition: arraylist.hh:587
ArrayListIterator< T, N, A > & operator=(const ArrayListIterator< T, N, A > &other)
Definition: arraylist.hh:677
void increment()
Increment the iterator.
Definition: arraylist.hh:613
A::value_type MemberType
The member type.
Definition: arraylist.hh:267
A::const_reference const_reference
Definition: arraylist.hh:275
A::difference_type difference_type
Definition: arraylist.hh:269
This file implements the class shared_ptr (a reference counting pointer), for those systems that don'...
ConstArrayListIterator()
Definition: arraylist.hh:445
void increment()
Increment the iterator.
Definition: arraylist.hh:619
A random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:18
Fallback implementation of the std::array class (a static array)
A::const_reference const_reference
Definition: arraylist.hh:397
void push_back(const_reference entry)
Append an entry to the list.
Definition: arraylist.hh:492
void purge()
Purge the list.
Definition: arraylist.hh:555
ArrayListIterator()
Standard constructor.
Definition: arraylist.hh:350
A reference counting smart pointer.
Definition: shared_ptr.hh:63
A::size_type size_type
Definition: arraylist.hh:271
ConstArrayListIterator< MemberType, N, A > const_iterator
A constant random access iterator.
Definition: arraylist.hh:112
const T & const_reference
The type of a const reference to the type we store.
Definition: arraylist.hh:83
iterator begin()
Get an iterator that is positioned at the first element.
Definition: arraylist.hh:531
const T * const_pointer
The type of a const pointer to the type we store.
Definition: arraylist.hh:93
ArrayListIterator< MemberType, N, A > iterator
A random access iterator.
Definition: arraylist.hh:107
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:425
T * pointer
The type of a pointer to the type we store.
Definition: arraylist.hh:88
A::value_type MemberType
The member type.
Definition: arraylist.hh:389
reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:649
void advance(difference_type n)
Definition: arraylist.hh:574
This file implements iterator facade classes for writing stl conformant iterators.
void decrement()
decrement the iterator.
Definition: arraylist.hh:631
reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:637
A dynamically growing random access list.
Definition: arraylist.hh:60
void clear()
Delete all entries from the list.
Definition: arraylist.hh:478