Dune Core Modules (2.6.0)

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 
4 #ifndef DUNE_COMMON_ARRAYLIST_HH
5 #define DUNE_COMMON_ARRAYLIST_HH
6 
7 #include <array>
8 #include <cassert>
9 #include <memory>
10 #include <vector>
11 #include "iteratorfacades.hh"
12 
13 namespace Dune
14 {
15  // forward declaration
16  template<class T, int N, class A>
17  class ArrayListIterator;
18 
19  template<class T, int N, class A>
20  class ConstArrayListIterator;
21 
58  template<class T, int N=100, class A=std::allocator<T> >
59  class ArrayList
60  {
61  public:
67  typedef T MemberType;
68 
72  typedef T value_type;
73 
77  typedef T& reference;
78 
82  typedef const T& const_reference;
83 
87  typedef T* pointer;
88 
92  typedef const T* const_pointer;
93 
94  enum
95  {
100  chunkSize_ = (N > 0) ? N : 1
101  };
102 
107 
112 
116  typedef std::size_t size_type;
117 
121  typedef std::ptrdiff_t difference_type;
122 
128 
135 
141 
147 
152  inline void push_back(const_reference entry);
153 
160 
167 
172  inline size_type size() const;
173 
181  inline void purge();
182 
186  inline void clear();
191 
192  private:
193 
197  typedef typename A::template rebind<std::shared_ptr<std::array<MemberType,chunkSize_> > >::other
198  SmartPointerAllocator;
199 
203  typedef typename A::template rebind<std::array<MemberType,chunkSize_> >::other
204  ArrayAllocator;
205 
209  friend class ArrayListIterator<T,N,A>;
210  friend class ConstArrayListIterator<T,N,A>;
211 
213  std::vector<std::shared_ptr<std::array<MemberType,chunkSize_> >,
214  SmartPointerAllocator> chunks_;
223  size_type capacity_;
225  size_type size_;
227  size_type start_;
236  inline reference elementAt(size_type i);
237 
246  inline const_reference elementAt(size_type i) const;
247  };
248 
249 
253  template<class T, int N, class A>
254  class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>,
255  typename A::value_type,
256  typename A::reference,
257  typename A::difference_type>
258  {
259 
260  friend class ArrayList<T,N,A>;
261  friend class ConstArrayListIterator<T,N,A>;
262  public:
266  typedef typename A::value_type MemberType;
267 
268  typedef typename A::difference_type difference_type;
269 
270  typedef typename A::size_type size_type;
271 
272  typedef typename A::reference reference;
273 
274  typedef typename A::const_reference const_reference;
275 
276  enum
277  {
283  chunkSize_ = (N > 0) ? N : 1
284  };
285 
286 
292  inline bool equals(const ArrayListIterator<MemberType,N,A>& other) const;
293 
299  inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
300 
304  inline void increment();
305 
309  inline void decrement();
310 
315  inline reference elementAt(size_type i) const;
316 
321  inline reference dereference() const;
322 
334  inline void eraseToHere();
335 
337  inline size_type position(){return position_;}
338 
340  inline void advance(difference_type n);
341 
343  inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other) const;
344 
347 
349  inline ArrayListIterator() : position_(0), list_(nullptr)
350  {}
351 
352  private:
358  inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position);
359 
363  size_type position_;
367  ArrayList<T,N,A>* list_;
368  };
369 
373  template<class T, int N, class A>
375  : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>,
376  const typename A::value_type,
377  typename A::const_reference,
378  typename A::difference_type>
379  {
380 
381  friend class ArrayList<T,N,A>;
382  friend class ArrayListIterator<T,N,A>;
383 
384  public:
388  typedef typename A::value_type MemberType;
389 
390  typedef typename A::difference_type difference_type;
391 
392  typedef typename A::size_type size_type;
393 
394  typedef typename A::reference reference;
395 
396  typedef typename A::const_reference const_reference;
397  enum
398  {
404  chunkSize_ = (N > 0) ? N : 1
405  };
406 
412  inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
413 
417  inline void increment();
418 
422  inline void decrement();
423 
425  inline void advance(difference_type n);
426 
428  inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other) const;
429 
434  inline const_reference elementAt(size_type i) const;
435 
440  inline const_reference dereference() const;
441 
442  inline const ConstArrayListIterator<T,N,A>& operator=(const ConstArrayListIterator<T,N,A>& other);
443 
444  inline ConstArrayListIterator() : position_(0), list_(nullptr)
445  {}
446 
448 
449  private:
450 
456  inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position);
457 
461  size_type position_;
465  const ArrayList<T,N,A>* list_;
466  };
467 
468 
469  template<class T, int N, class A>
471  : capacity_(0), size_(0), start_(0)
472  {
473  chunks_.reserve(100);
474  }
475 
476  template<class T, int N, class A>
478  capacity_=0;
479  size_=0;
480  start_=0;
481  chunks_.clear();
482  }
483 
484  template<class T, int N, class A>
485  size_t ArrayList<T,N,A>::size() const
486  {
487  return size_;
488  }
489 
490  template<class T, int N, class A>
492  {
493  size_t index=start_+size_;
494  if(index==capacity_)
495  {
496  chunks_.push_back(std::make_shared<std::array<MemberType,chunkSize_> >());
497  capacity_ += chunkSize_;
498  }
499  elementAt(index)=entry;
500  ++size_;
501  }
502 
503  template<class T, int N, class A>
505  {
506  return elementAt(start_+i);
507  }
508 
509 
510  template<class T, int N, class A>
512  {
513  return elementAt(start_+i);
514  }
515 
516  template<class T, int N, class A>
518  {
519  return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
520  }
521 
522 
523  template<class T, int N, class A>
525  {
526  return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
527  }
528 
529  template<class T, int N, class A>
531  {
532  return ArrayListIterator<T,N,A>(*this, start_);
533  }
534 
535  template<class T, int N, class A>
537  {
538  return ConstArrayListIterator<T,N,A>(*this, start_);
539  }
540 
541  template<class T, int N, class A>
543  {
544  return ArrayListIterator<T,N,A>(*this, start_+size_);
545  }
546 
547  template<class T, int N, class A>
549  {
550  return ConstArrayListIterator<T,N,A>(*this, start_+size_);
551  }
552 
553  template<class T, int N, class A>
555  {
556  // Distance to copy to the left.
557  size_t distance = start_/chunkSize_;
558  if(distance>0) {
559  // Number of chunks with entries in it;
560  size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ );
561 
562  // Copy chunks to the left.
563  std::copy(chunks_.begin()+distance,
564  chunks_.begin()+(distance+chunks), chunks_.begin());
565 
566  // Calculate new parameters
567  start_ = start_ % chunkSize_;
568  //capacity += distance * chunkSize_;
569  }
570  }
571 
572  template<class T, int N, class A>
573  void ArrayListIterator<T,N,A>::advance(difference_type i)
574  {
575  position_+=i;
576  }
577 
578  template<class T, int N, class A>
580  {
581  position_+=i;
582  }
583 
584 
585  template<class T, int N, class A>
587  {
588  // Makes only sense if we reference a common list
589  assert(list_==(other.list_));
590  return position_==other.position_ ;
591  }
592 
593 
594  template<class T, int N, class A>
596  {
597  // Makes only sense if we reference a common list
598  assert(list_==(other.list_));
599  return position_==other.position_ ;
600  }
601 
602 
603  template<class T, int N, class A>
605  {
606  // Makes only sense if we reference a common list
607  assert(list_==(other.list_));
608  return position_==other.position_ ;
609  }
610 
611  template<class T, int N, class A>
613  {
614  ++position_;
615  }
616 
617  template<class T, int N, class A>
619  {
620  ++position_;
621  }
622 
623  template<class T, int N, class A>
625  {
626  --position_;
627  }
628 
629  template<class T, int N, class A>
631  {
632  --position_;
633  }
634 
635  template<class T, int N, class A>
636  typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::elementAt(size_type i) const
637  {
638  return list_->elementAt(i+position_);
639  }
640 
641  template<class T, int N, class A>
642  typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::elementAt(size_type i) const
643  {
644  return list_->elementAt(i+position_);
645  }
646 
647  template<class T, int N, class A>
648  typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::dereference() const
649  {
650  return list_->elementAt(position_);
651  }
652 
653  template<class T, int N, class A>
654  typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::dereference() const
655  {
656  return list_->elementAt(position_);
657  }
658 
659  template<class T, int N, class A>
660  typename ArrayListIterator<T,N,A>::difference_type ArrayListIterator<T,N,A>::distanceTo(const ArrayListIterator<T,N,A>& other) const
661  {
662  // Makes only sense if we reference a common list
663  assert(list_==(other.list_));
664  return other.position_ - position_;
665  }
666 
667  template<class T, int N, class A>
668  typename ConstArrayListIterator<T,N,A>::difference_type ConstArrayListIterator<T,N,A>::distanceTo(const ConstArrayListIterator<T,N,A>& other) const
669  {
670  // Makes only sense if we reference a common list
671  assert(list_==(other.list_));
672  return other.position_ - position_;
673  }
674 
675  template<class T, int N, class A>
677  {
678  position_=other.position_;
679  list_=other.list_;
680  return *this;
681  }
682 
683  template<class T, int N, class A>
685  {
686  position_=other.position_;
687  list_=other.list_;
688  return *this;
689  }
690 
691  template<class T, int N, class A>
693  {
694  list_->size_ -= ++position_ - list_->start_;
695  // chunk number of the new position.
696  size_t posChunkStart = position_ / chunkSize_;
697  // number of chunks to deallocate
698  size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_)
699  / chunkSize_;
700  list_->start_ = position_;
701 
702  // Deallocate memory not needed any more.
703  for(size_t chunk=0; chunk<chunks; chunk++) {
704  --posChunkStart;
705  list_->chunks_[posChunkStart].reset();
706  }
707 
708  // Capacity stays the same as the chunks before us
709  // are still there. They null pointers.
710  assert(list_->start_+list_->size_<=list_->capacity_);
711  }
712 
713  template<class T, int N, class A>
714  ArrayListIterator<T,N,A>::ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position)
715  : position_(position), list_(&arrayList)
716  {}
717 
718 
719  template<class T, int N, class A>
720  ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList,
721  size_type position)
722  : position_(position), list_(&arrayList)
723  {}
724 
725  template<class T, int N, class A>
726  ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayListIterator<T,N,A>& other)
727  : position_(other.position_), list_(other.list_)
728  {}
729 
730 
732 }
733 #endif
A random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:258
size_type position()
Definition: arraylist.hh:337
A::value_type MemberType
The member type.
Definition: arraylist.hh:266
ArrayListIterator()
Standard constructor.
Definition: arraylist.hh:349
@ chunkSize_
The number of elements in one chunk of the list.
Definition: arraylist.hh:283
A dynamically growing random access list.
Definition: arraylist.hh:60
T value_type
Value type for stl compliance.
Definition: arraylist.hh:72
@ chunkSize_
The number of elements in one chunk of the list. This has to be at least one. The default is 100.
Definition: arraylist.hh:100
const T * const_pointer
The type of a const pointer to the type we store.
Definition: arraylist.hh:92
ArrayListIterator< MemberType, N, A > iterator
A random access iterator.
Definition: arraylist.hh:106
const T & const_reference
The type of a const reference to the type we store.
Definition: arraylist.hh:82
T & reference
The type of a reference to the type we store.
Definition: arraylist.hh:77
std::size_t size_type
The size type.
Definition: arraylist.hh:116
T MemberType
The member type that is stored.
Definition: arraylist.hh:67
T * pointer
The type of a pointer to the type we store.
Definition: arraylist.hh:87
ConstArrayListIterator< MemberType, N, A > const_iterator
A constant random access iterator.
Definition: arraylist.hh:111
std::ptrdiff_t difference_type
The difference type.
Definition: arraylist.hh:121
A constant random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:379
A::value_type MemberType
The member type.
Definition: arraylist.hh:388
@ chunkSize_
The number of elements in one chunk of the list.
Definition: arraylist.hh:404
A pair consisting of a global and local index.
Definition: indexset.hh:84
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:433
reference operator[](size_type i)
Get the element at specific position.
Definition: arraylist.hh:504
iterator begin()
Get an iterator that is positioned at the first element.
Definition: arraylist.hh:530
bool equals(const ArrayListIterator< MemberType, N, A > &other) const
Comares two iterators.
Definition: arraylist.hh:586
void increment()
Increment the iterator.
Definition: arraylist.hh:612
size_type size() const
Get the number of elements in the list.
Definition: arraylist.hh:485
void purge()
Purge the list.
Definition: arraylist.hh:554
void decrement()
decrement the iterator.
Definition: arraylist.hh:624
void eraseToHere()
Erase all entries before the current position and the one at the current position.
Definition: arraylist.hh:692
ArrayList()
Constructs an Array list with one chunk.
Definition: arraylist.hh:470
const_iterator begin() const
Get a random access iterator that is positioned at the first element.
Definition: arraylist.hh:536
void increment()
Increment the iterator.
Definition: arraylist.hh:618
iterator end()
Get a random access iterator positioned after the last element.
Definition: arraylist.hh:542
const_reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:642
const_reference operator[](size_type i) const
Get the element at specific position.
Definition: arraylist.hh:511
void decrement()
decrement the iterator.
Definition: arraylist.hh:630
void advance(difference_type n)
Definition: arraylist.hh:579
const_iterator end() const
Get a random access iterator positioned after the last element.
Definition: arraylist.hh:548
const_reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:654
void clear()
Delete all entries from the list.
Definition: arraylist.hh:477
reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:636
bool equals(const ConstArrayListIterator< MemberType, N, A > &other) const
Comares to iterators.
Definition: arraylist.hh:604
void advance(difference_type n)
Definition: arraylist.hh:573
ArrayListIterator< T, N, A > & operator=(const ArrayListIterator< T, N, A > &other)
Definition: arraylist.hh:676
difference_type distanceTo(const ConstArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:668
reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:648
void push_back(const_reference entry)
Append an entry to the list.
Definition: arraylist.hh:491
difference_type distanceTo(const ArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:660
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:435
constexpr decltype(auto) elementAt(Container &&c, Index &&i)
Get element at given position from container.
Definition: hybridutilities.hh:133
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:10
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.80.0 (Mar 28, 23:30, 2024)