Loading...
Searching...
No Matches
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
iteratorfacades.hh
This file implements iterator facade classes for writing stl conformant iterators.
Dune::ArrayList::operator[]
reference operator[](size_type i)
Get the element at specific position.
Definition arraylist.hh:489
Dune::ArrayList::begin
iterator begin()
Get an iterator that is positioned at the first element.
Definition arraylist.hh:515
Dune::ArrayListIterator::equals
bool equals(const ArrayListIterator< MemberType, N, A > &other) const
Compares two iterators.
Definition arraylist.hh:571
Dune::ArrayListIterator::increment
void increment()
Increment the iterator.
Definition arraylist.hh:597
Dune::ArrayList::size
size_type size() const
Get the number of elements in the list.
Definition arraylist.hh:470
Dune::ConstArrayListIterator::ConstArrayListIterator
ConstArrayListIterator(const ArrayListIterator< T, N, A > &other)
Definition arraylist.hh:695
Dune::ArrayList::purge
void purge()
Purge the list.
Definition arraylist.hh:539
Dune::ArrayListIterator::decrement
void decrement()
decrement the iterator.
Definition arraylist.hh:609
Dune::ArrayListIterator::eraseToHere
void eraseToHere()
Erase all entries before the current position and the one at the current position.
Definition arraylist.hh:661
Dune::ArrayList::ArrayList
ArrayList()
Constructs an Array list with one chunk.
Definition arraylist.hh:455
Dune::ArrayList::begin
const_iterator begin() const
Get a random access iterator that is positioned at the first element.
Definition arraylist.hh:521
Dune::ConstArrayListIterator::increment
void increment()
Increment the iterator.
Definition arraylist.hh:603
Dune::ConstArrayListIterator::elementAt
reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition arraylist.hh:627
Dune::ArrayList::end
iterator end()
Get a random access iterator positioned after the last element.
Definition arraylist.hh:527
Dune::ConstArrayListIterator::dereference
reference dereference() const
Access the element at the current position.
Definition arraylist.hh:639
Dune::ArrayList::operator[]
const_reference operator[](size_type i) const
Get the element at specific position.
Definition arraylist.hh:496
Dune::ConstArrayListIterator::decrement
void decrement()
decrement the iterator.
Definition arraylist.hh:615
Dune::ConstArrayListIterator::advance
void advance(difference_type n)
Definition arraylist.hh:564
Dune::ArrayListIterator::equals
bool equals(const ConstArrayListIterator< MemberType, N, A > &other) const
Compares two iterators.
Definition arraylist.hh:580
Dune::ArrayList::end
const_iterator end() const
Get a random access iterator positioned after the last element.
Definition arraylist.hh:533
Dune::ArrayList::clear
void clear()
Delete all entries from the list.
Definition arraylist.hh:462
Dune::ArrayListIterator< MemberType, N, A >::elementAt
reference elementAt(size_type i) const
Dune::ConstArrayListIterator::equals
bool equals(const ConstArrayListIterator< MemberType, N, A > &other) const
Compares to iterators.
Definition arraylist.hh:589
Dune::ArrayListIterator::advance
void advance(difference_type n)
Definition arraylist.hh:558
Dune::ConstArrayListIterator::distanceTo
difference_type distanceTo(const ConstArrayListIterator< T, N, A > &other) const
Definition arraylist.hh:653
Dune::ArrayListIterator::dereference
reference dereference() const
Access the element at the current position.
Definition arraylist.hh:633
Dune::ArrayList::push_back
void push_back(const_reference entry)
Append an entry to the list.
Definition arraylist.hh:476
Dune::ArrayListIterator::distanceTo
difference_type distanceTo(const ArrayListIterator< T, N, A > &other) const
Definition arraylist.hh:645
Dune
Dune namespace
Definition alignedallocator.hh:13
Dune::ArrayListIterator
A random access iterator for the Dune::ArrayList class.
Definition arraylist.hh:255
Dune::ArrayListIterator::position
size_type position()
Definition arraylist.hh:329
Dune::ArrayListIterator< MemberType, N, A >::MemberType
A::value_type MemberType
Definition arraylist.hh:263
Dune::ArrayListIterator::ArrayListIterator
ArrayListIterator()
Standard constructor.
Definition arraylist.hh:338
Dune::ArrayListIterator< MemberType, N, A >::difference_type
A::difference_type difference_type
Definition arraylist.hh:265
Dune::ArrayListIterator< MemberType, N, A >::chunkSize_
static constexpr int chunkSize_
Definition arraylist.hh:278
Dune::ArrayListIterator< MemberType, N, A >::size_type
A::size_type size_type
Definition arraylist.hh:267
Dune::ArrayListIterator< MemberType, N, A >::const_reference
typename A::value_type const & const_reference
Definition arraylist.hh:271
Dune::ArrayListIterator< MemberType, N, A >::reference
typename A::value_type & reference
Definition arraylist.hh:269
Dune::ConstArrayListIterator
A constant random access iterator for the Dune::ArrayList class.
Definition arraylist.hh:368
Dune::ConstArrayListIterator< MemberType, N, A >::chunkSize_
static constexpr int chunkSize_
Definition arraylist.hh:392
Dune::ConstArrayListIterator::ConstArrayListIterator
ConstArrayListIterator()
Definition arraylist.hh:429
Dune::ConstArrayListIterator< MemberType, N, A >::reference
typename A::value_type const & reference
Definition arraylist.hh:383
Dune::ConstArrayListIterator< MemberType, N, A >::MemberType
A::value_type MemberType
Definition arraylist.hh:377
Dune::ConstArrayListIterator< MemberType, N, A >::difference_type
A::difference_type difference_type
Definition arraylist.hh:379
Dune::ConstArrayListIterator< MemberType, N, A >::const_reference
typename A::value_type const & const_reference
Definition arraylist.hh:385
Dune::ConstArrayListIterator< MemberType, N, A >::size_type
A::size_type size_type
Definition arraylist.hh:381
Dune::ArrayList
A dynamically growing random access list.
Definition arraylist.hh:62
Dune::ArrayList::value_type
T value_type
Value type for stl compliance.
Definition arraylist.hh:74
Dune::iterator::chunkSize_
static constexpr int chunkSize_
Definition arraylist.hh:100
Dune::ArrayList::const_pointer
const T * const_pointer
The type of a const pointer to the type we store.
Definition arraylist.hh:94
Dune::ArrayList::iterator
ArrayListIterator< MemberType, N, A > iterator
A random access iterator.
Definition arraylist.hh:105
Dune::ArrayList::const_reference
const T & const_reference
The type of a const reference to the type we store.
Definition arraylist.hh:84
Dune::ArrayList::reference
T & reference
The type of a reference to the type we store.
Definition arraylist.hh:79
Dune::ArrayList::size_type
std::size_t size_type
The size type.
Definition arraylist.hh:115
Dune::ArrayList::MemberType
T MemberType
The member type that is stored.
Definition arraylist.hh:69
Dune::ArrayList::pointer
T * pointer
The type of a pointer to the type we store.
Definition arraylist.hh:89
Dune::ArrayList::const_iterator
ConstArrayListIterator< MemberType, N, A > const_iterator
A constant random access iterator.
Definition arraylist.hh:110
Dune::ArrayList::difference_type
std::ptrdiff_t difference_type
The difference type.
Definition arraylist.hh:120
Dune::RandomAccessIteratorFacade
Base class for stl conformant forward iterators.
Definition iteratorfacades.hh:435