arraylist.hh

Go to the documentation of this file.

// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
 
#ifndef DUNE_COMMON_ARRAYLIST_HH
#define DUNE_COMMON_ARRAYLIST_HH
 
#include <array>
#include <cassert>
#include <memory>
#include <vector>
#include "iteratorfacades.hh"
 
namespace Dune
{
  // forward declaration
  template<class T, int N, class A>
  class ArrayListIterator;
 
  template<class T, int N, class A>
  class ConstArrayListIterator;
 
  template<class T, int N=100, class A=std::allocator<T> >
  class ArrayList
  {
  public:
    typedef T MemberType;
 
    typedef T value_type;
 
    typedef T& reference;
 
    typedef const T& const_reference;
 
    typedef T* pointer;
 
    typedef const T* const_pointer;
 
    enum
    {
      chunkSize_ = (N > 0) ? N : 1
    };
 
    typedef ArrayListIterator<MemberType,N,A> iterator;
 
    typedef ConstArrayListIterator<MemberType,N,A> const_iterator;
 
    typedef std::size_t size_type;
 
    typedef std::ptrdiff_t difference_type;
 
    iterator begin();
 
    const_iterator begin() const;
 
    iterator end();
 
    const_iterator end() const;
 
    inline void push_back(const_reference entry);
 
    inline reference operator[](size_type i);
 
    inline const_reference operator[](size_type i) const;
 
    inline size_type size() const;
 
    inline void purge();
 
    inline void clear();
    ArrayList();
 
  private:
 
    typedef typename A::template rebind<std::shared_ptr<std::array<MemberType,chunkSize_> > >::other
    SmartPointerAllocator;
 
    typedef typename A::template rebind<std::array<MemberType,chunkSize_> >::other
    ArrayAllocator;
 
    friend class ArrayListIterator<T,N,A>;
    friend class ConstArrayListIterator<T,N,A>;
 
    std::vector<std::shared_ptr<std::array<MemberType,chunkSize_> >,
        SmartPointerAllocator> chunks_;
    size_type capacity_;
    size_type size_;
    size_type start_;
    inline reference elementAt(size_type i);
 
    inline const_reference elementAt(size_type i) const;
  };
 
 
  template<class T, int N, class A>
  class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>,
                                typename A::value_type,
                                typename A::reference,
                                typename A::difference_type>
  {
 
    friend class ArrayList<T,N,A>;
    friend class ConstArrayListIterator<T,N,A>;
  public:
    typedef typename A::value_type MemberType;
 
    typedef typename A::difference_type difference_type;
 
    typedef typename A::size_type size_type;
 
    typedef typename A::reference reference;
 
    typedef typename A::const_reference const_reference;
 
    enum
    {
      chunkSize_ = (N > 0) ? N : 1
    };
 
 
    inline bool equals(const ArrayListIterator<MemberType,N,A>& other) const;
 
    inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
 
    inline void increment();
 
    inline void decrement();
 
    inline reference elementAt(size_type i) const;
 
    inline reference dereference() const;
 
    inline void eraseToHere();
 
    inline size_type position(){return position_;}
 
    inline void advance(difference_type n);
 
    inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other) const;
 
    inline ArrayListIterator<T,N,A>& operator=(const ArrayListIterator<T,N,A>& other);
 
    inline ArrayListIterator() : position_(0), list_(nullptr)
    {}
 
  private:
    inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position);
 
    size_type position_;
    ArrayList<T,N,A>* list_;
  };
 
  template<class T, int N, class A>
  class ConstArrayListIterator
    : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>,
          const typename A::value_type,
          typename A::const_reference,
          typename A::difference_type>
  {
 
    friend class ArrayList<T,N,A>;
    friend class ArrayListIterator<T,N,A>;
 
  public:
    typedef typename A::value_type MemberType;
 
    typedef typename A::difference_type difference_type;
 
    typedef typename A::size_type size_type;
 
    typedef typename A::reference reference;
 
    typedef typename A::const_reference const_reference;
    enum
    {
      chunkSize_ = (N > 0) ? N : 1
    };
 
    inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
 
    inline void increment();
 
    inline void decrement();
 
    inline void advance(difference_type n);
 
    inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other) const;
 
    inline const_reference elementAt(size_type i) const;
 
    inline const_reference dereference() const;
 
    inline const ConstArrayListIterator<T,N,A>& operator=(const ConstArrayListIterator<T,N,A>& other);
 
    inline ConstArrayListIterator() : position_(0), list_(nullptr)
    {}
 
    inline ConstArrayListIterator(const ArrayListIterator<T,N,A>& other);
 
  private:
 
    inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position);
 
    size_type position_;
    const ArrayList<T,N,A>* list_;
  };
 
 
  template<class T, int N, class A>
  ArrayList<T,N,A>::ArrayList()
    : capacity_(0), size_(0), start_(0)
  {
    chunks_.reserve(100);
  }
 
  template<class T, int N, class A>
  void ArrayList<T,N,A>::clear(){
    capacity_=0;
    size_=0;
    start_=0;
    chunks_.clear();
  }
 
  template<class T, int N, class A>
  size_t ArrayList<T,N,A>::size() const
  {
    return size_;
  }
 
  template<class T, int N, class A>
  void ArrayList<T,N,A>::push_back(const_reference entry)
  {
    size_t index=start_+size_;
    if(index==capacity_)
    {
      chunks_.push_back(std::make_shared<std::array<MemberType,chunkSize_> >());
      capacity_ += chunkSize_;
    }
    elementAt(index)=entry;
    ++size_;
  }
 
  template<class T, int N, class A>
  typename ArrayList<T,N,A>::reference ArrayList<T,N,A>::operator[](size_type i)
  {
    return elementAt(start_+i);
  }
 
 
  template<class T, int N, class A>
  typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::operator[](size_type i) const
  {
    return elementAt(start_+i);
  }
 
  template<class T, int N, class A>
  typename ArrayList<T,N,A>::reference ArrayList<T,N,A>::elementAt(size_type i)
  {
    return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
  }
 
 
  template<class T, int N, class A>
  typename ArrayList<T,N,A>::const_reference ArrayList<T,N,A>::elementAt(size_type i) const
  {
    return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
  }
 
  template<class T, int N, class A>
  ArrayListIterator<T,N,A> ArrayList<T,N,A>::begin()
  {
    return ArrayListIterator<T,N,A>(*this, start_);
  }
 
  template<class T, int N, class A>
  ConstArrayListIterator<T,N,A> ArrayList<T,N,A>::begin() const
  {
    return ConstArrayListIterator<T,N,A>(*this, start_);
  }
 
  template<class T, int N, class A>
  ArrayListIterator<T,N,A> ArrayList<T,N,A>::end()
  {
    return ArrayListIterator<T,N,A>(*this, start_+size_);
  }
 
  template<class T, int N, class A>
  ConstArrayListIterator<T,N,A> ArrayList<T,N,A>::end() const
  {
    return ConstArrayListIterator<T,N,A>(*this, start_+size_);
  }
 
  template<class T, int N, class A>
  void ArrayList<T,N,A>::purge()
  {
    // Distance to copy to the left.
    size_t distance = start_/chunkSize_;
    if(distance>0) {
      // Number of chunks with entries in it;
      size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ );
 
      // Copy chunks to the left.
      std::copy(chunks_.begin()+distance,
                chunks_.begin()+(distance+chunks), chunks_.begin());
 
      // Calculate new parameters
      start_ = start_ % chunkSize_;
      //capacity += distance * chunkSize_;
    }
  }
 
  template<class T, int N, class A>
  void ArrayListIterator<T,N,A>::advance(difference_type i)
  {
    position_+=i;
  }
 
  template<class T, int N, class A>
  void ConstArrayListIterator<T,N,A>::advance(difference_type i)
  {
    position_+=i;
  }
 
 
  template<class T, int N, class A>
  bool ArrayListIterator<T,N,A>::equals(const ArrayListIterator<MemberType,N,A>& other) const
  {
    // Makes only sense if we reference a common list
    assert(list_==(other.list_));
    return position_==other.position_ ;
  }
 
 
  template<class T, int N, class A>
  bool ArrayListIterator<T,N,A>::equals(const ConstArrayListIterator<MemberType,N,A>& other) const
  {
    // Makes only sense if we reference a common list
    assert(list_==(other.list_));
    return position_==other.position_ ;
  }
 
 
  template<class T, int N, class A>
  bool ConstArrayListIterator<T,N,A>::equals(const ConstArrayListIterator<MemberType,N,A>& other) const
  {
    // Makes only sense if we reference a common list
    assert(list_==(other.list_));
    return position_==other.position_ ;
  }
 
  template<class T, int N, class A>
  void ArrayListIterator<T,N,A>::increment()
  {
    ++position_;
  }
 
  template<class T, int N, class A>
  void ConstArrayListIterator<T,N,A>::increment()
  {
    ++position_;
  }
 
  template<class T, int N, class A>
  void ArrayListIterator<T,N,A>::decrement()
  {
    --position_;
  }
 
  template<class T, int N, class A>
  void ConstArrayListIterator<T,N,A>::decrement()
  {
    --position_;
  }
 
  template<class T, int N, class A>
  typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::elementAt(size_type i) const
  {
    return list_->elementAt(i+position_);
  }
 
  template<class T, int N, class A>
  typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::elementAt(size_type i) const
  {
    return list_->elementAt(i+position_);
  }
 
  template<class T, int N, class A>
  typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::dereference() const
  {
    return list_->elementAt(position_);
  }
 
  template<class T, int N, class A>
  typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::dereference() const
  {
    return list_->elementAt(position_);
  }
 
  template<class T, int N, class A>
  typename ArrayListIterator<T,N,A>::difference_type ArrayListIterator<T,N,A>::distanceTo(const ArrayListIterator<T,N,A>& other) const
  {
    // Makes only sense if we reference a common list
    assert(list_==(other.list_));
    return other.position_ - position_;
  }
 
  template<class T, int N, class A>
  typename ConstArrayListIterator<T,N,A>::difference_type ConstArrayListIterator<T,N,A>::distanceTo(const ConstArrayListIterator<T,N,A>& other) const
  {
    // Makes only sense if we reference a common list
    assert(list_==(other.list_));
    return other.position_ - position_;
  }
 
  template<class T, int N, class A>
  ArrayListIterator<T,N,A>& ArrayListIterator<T,N,A>::operator=(const ArrayListIterator<T,N,A>& other)
  {
    position_=other.position_;
    list_=other.list_;
    return *this;
  }
 
  template<class T, int N, class A>
  const ConstArrayListIterator<T,N,A>& ConstArrayListIterator<T,N,A>::operator=(const ConstArrayListIterator<T,N,A>& other)
  {
    position_=other.position_;
    list_=other.list_;
    return *this;
  }
 
  template<class T, int N, class A>
  void ArrayListIterator<T,N,A>::eraseToHere()
  {
    list_->size_ -= ++position_ - list_->start_;
    // chunk number of the new position.
    size_t posChunkStart = position_ / chunkSize_;
    // number of chunks to deallocate
    size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_)
                    / chunkSize_;
    list_->start_ = position_;
 
    // Deallocate memory not needed any more.
    for(size_t chunk=0; chunk<chunks; chunk++) {
      --posChunkStart;
      list_->chunks_[posChunkStart].reset();
    }
 
    // Capacity stays the same as the chunks before us
    // are still there. They null pointers.
    assert(list_->start_+list_->size_<=list_->capacity_);
  }
 
  template<class T, int N, class A>
  ArrayListIterator<T,N,A>::ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position)
    : position_(position), list_(&arrayList)
  {}
 
 
  template<class T, int N, class A>
  ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList,
                                                        size_type position)
    : position_(position), list_(&arrayList)
  {}
 
  template<class T, int N, class A>
  ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayListIterator<T,N,A>& other)
    : position_(other.position_), list_(other.list_)
  {}
 
 
}
#endif