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:
// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception

#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;

    constexpr static int 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:

    using SmartPointerAllocator = typename std::allocator_traits<A>::template rebind_alloc< std::shared_ptr< std::array<MemberType,chunkSize_> > >;

    using ArrayAllocator = typename std::allocator_traits<A>::template rebind_alloc< std::array<MemberType,chunkSize_> >;

    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::value_type &,
                                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;

    using reference = typename A::value_type &;

    using const_reference = typename A::value_type const&;

    constexpr static int 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() : 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::value_type const&,
          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;

    using reference = typename A::value_type const&;

    using const_reference = typename A::value_type const&;

    constexpr static int 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 reference elementAt(size_type i) const;

    inline reference dereference() const;

    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>::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>::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>
  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