Loading...
Searching...
No Matches
sllist.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_SLLIST_HH
#define DUNE_SLLIST_HH
#include <memory>
#include <cassert>
#include "iteratorfacades.hh"
#include <ostream>
namespace Dune
{
template<typename T, class A>
class SLListIterator;
template<typename T, class A>
class SLListConstIterator;
template<typename T, class A>
class SLListModifyIterator;
template<typename T, class A=std::allocator<T> >
class SLList
{
struct Element;
friend class SLListIterator<T,A>;
friend class SLListConstIterator<T,A>;
public:
typedef typename A::size_type size_type;
typedef T MemberType;
using Allocator = typename std::allocator_traits<A>::template rebind_alloc<Element>;
typedef SLListIterator<T,A> iterator;
typedef SLListConstIterator<T,A> const_iterator;
SLList();
template<typename T1, typename A1>
SLList(const SLList<T1,A1>& other);
SLList(const SLList<T,A>& other);
~SLList();
typedef SLListModifyIterator<T,A> ModifyIterator;
SLList<T,A>& operator=(const SLList<T,A>& other);
inline void push_back(const MemberType& item);
inline void push_front(const MemberType& item);
inline void pop_front();
inline void clear();
inline iterator begin();
inline const_iterator begin() const;
inline ModifyIterator beginModify();
inline ModifyIterator endModify();
inline iterator end();
inline const_iterator end() const;
inline bool empty() const;
inline int size() const;
bool operator==(const SLList& sl) const;
bool operator!=(const SLList& sl) const;
private:
struct Element
{
Element* next_;
MemberType item_;
Element(const MemberType& item, Element* next_=0);
Element();
~Element();
};
void deleteNext(Element* current);
void copyElements(const SLList<T,A>& other);
template<bool watchForTail>
void deleteNext(Element* current);
void insertAfter(Element* current, const T& item);
Element beforeHead_;
Element* tail_;
Allocator allocator_;
int size_;
};
template<typename T, class A>
class SLListIterator : public Dune::ForwardIteratorFacade<SLListIterator<T,A>, T, T&, std::size_t>
{
friend class SLListConstIterator<T,A>;
friend class SLListModifyIterator<T,A>;
friend class SLList<T,A>;
public:
inline SLListIterator(typename SLList<T,A>::Element* item,
SLList<T,A>* sllist)
: current_(item), list_(sllist)
{}
inline SLListIterator()
: current_(0), list_(0)
{}
inline SLListIterator(const SLListModifyIterator<T,A>& other)
: current_(other.iterator_.current_), list_(other.iterator_.list_)
{}
inline T& dereference() const
{
return current_->item_;
}
inline bool equals(const SLListConstIterator<T,A>& other) const
{
return current_==other.current_;
}
inline bool equals(const SLListIterator<T,A>& other) const
{
return current_==other.current_;
}
inline bool equals(const SLListModifyIterator<T,A>& other) const
{
return current_==other.iterator_.current_;
}
inline void increment()
{
current_ = current_->next_;
}
inline void insertAfter(const T& v) const
{
assert(list_ );
list_->insertAfter(current_, v);
}
inline void deleteNext() const
{
assert(list_);
list_->deleteNext(current_);
}
private:
typename SLList<T,A>::Element* current_;
SLList<T,A>* list_;
};
template<class T, class A>
class SLListConstIterator : public Dune::ForwardIteratorFacade<SLListConstIterator<T,A>, const T, const T&, std::size_t>
{
friend class SLListIterator<T,A>;
friend class SLList<T,A>;
public:
inline SLListConstIterator()
: current_(0)
{}
inline SLListConstIterator(typename SLList<T,A>::Element* item)
: current_(item)
{}
inline SLListConstIterator(const SLListIterator<T,A>& other)
: current_(other.current_)
{}
inline SLListConstIterator(const SLListModifyIterator<T,A>& other)
: current_(other.iterator_.current_)
{}
inline const T& dereference() const
{
return current_->item_;
}
inline bool equals(const SLListConstIterator<T,A>& other) const
{
return current_==other.current_;
}
inline void increment()
{
current_ = current_->next_;
}
private:
typename SLList<T,A>::Element* current_;
};
template<typename T, class A>
class SLListModifyIterator : public Dune::ForwardIteratorFacade<SLListModifyIterator<T,A>, T, T&, std::size_t>
{
friend class SLListConstIterator<T,A>;
friend class SLListIterator<T,A>;
public:
inline SLListModifyIterator(SLListIterator<T,A> beforeIterator,
SLListIterator<T,A> _iterator)
: beforeIterator_(beforeIterator), iterator_(_iterator)
{}
inline SLListModifyIterator()
: beforeIterator_(), iterator_()
{}
inline T& dereference() const
{
return *iterator_;
}
inline bool equals(const SLListConstIterator<T,A>& other) const
{
return iterator_== other;
}
inline bool equals(const SLListIterator<T,A>& other) const
{
return iterator_== other;
}
inline bool equals(const SLListModifyIterator<T,A>& other) const
{
return iterator_== other.iterator_;
}
inline void increment()
{
++iterator_;
++beforeIterator_;
}
inline void insert(const T& v)
{
beforeIterator_.insertAfter(v);
++beforeIterator_;
}
inline void remove()
{
++iterator_;
beforeIterator_.deleteNext();
}
private:
SLListIterator<T,A> beforeIterator_;
SLListIterator<T,A> iterator_;
};
template<typename T, typename A>
std::ostream& operator<<(std::ostream& os, const SLList<T,A>& sllist)
{
typedef typename SLList<T,A>::const_iterator Iterator;
Iterator end = sllist.end();
Iterator current= sllist.begin();
os << "{ ";
if(current!=end) {
os<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
++current;
for(; current != end; ++current)
os<<", "<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
}
os<<"} ";
return os;
}
template<typename T, class A>
SLList<T,A>::Element::Element(const MemberType& item, Element* next)
: next_(next), item_(item)
{}
template<typename T, class A>
SLList<T,A>::Element::Element()
: next_(0), item_()
{}
template<typename T, class A>
SLList<T,A>::Element::~Element()
{
next_=0;
}
template<typename T, class A>
SLList<T,A>::SLList()
: beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
{
beforeHead_.next_=0;
assert(&beforeHead_==tail_);
assert(tail_->next_==0);
}
template<typename T, class A>
SLList<T,A>::SLList(const SLList<T,A>& other)
: beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
{
copyElements(other);
}
template<typename T, class A>
template<typename T1, class A1>
SLList<T,A>::SLList(const SLList<T1,A1>& other)
: beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
{
copyElements(other);
}
template<typename T, typename A>
void SLList<T,A>::copyElements(const SLList<T,A>& other)
{
assert(tail_==&beforeHead_);
assert(size_==0);
typedef typename SLList<T,A>::const_iterator Iterator;
Iterator iend = other.end();
for(Iterator element=other.begin(); element != iend; ++element)
push_back(*element);
assert(other.size()==size());
}
template<typename T, class A>
SLList<T,A>::~SLList()
{
clear();
}
template<typename T, class A>
bool SLList<T,A>::operator==(const SLList& other) const
{
if(size()!=other.size())
return false;
for(const_iterator iter=begin(), oiter=other.begin();
iter != end(); ++iter, ++oiter)
if(*iter!=*oiter)
return false;
return true;
}
template<typename T, class A>
bool SLList<T,A>::operator!=(const SLList& other) const
{
if(size()==other.size()) {
for(const_iterator iter=begin(), oiter=other.begin();
iter != end(); ++iter, ++oiter)
if(*iter!=*oiter)
return true;
return false;
}else
return true;
}
template<typename T, class A>
SLList<T,A>& SLList<T,A>::operator=(const SLList<T,A>& other)
{
clear();
copyElements(other);
return *this;
}
template<typename T, class A>
inline void SLList<T,A>::push_back(const MemberType& item)
{
assert(size_>0 || tail_==&beforeHead_);
tail_->next_ = allocator_.allocate(1);
assert(size_>0 || tail_==&beforeHead_);
tail_ = tail_->next_;
::new (static_cast<void*>(&(tail_->item_)))T(item);
tail_->next_=0;
assert(tail_->next_==0);
++size_;
}
template<typename T, class A>
inline void SLList<T,A>::insertAfter(Element* current, const T& item)
{
assert(current);
#ifndef NDEBUG
bool changeTail = (current == tail_);
#endif
// Save old next element
Element* tmp = current->next_;
assert(!changeTail || !tmp);
// Allocate space
current->next_ = allocator_.allocate(1);
// Use copy constructor to initialize memory
std::allocator_traits<Allocator>::construct(allocator_, current->next_, Element(item,tmp));
//::new(static_cast<void*>(&(current->next_->item_))) T(item);
if(!current->next_->next_) {
// Update tail
assert(changeTail);
tail_ = current->next_;
}
++size_;
assert(!tail_->next_);
}
template<typename T, class A>
inline void SLList<T,A>::push_front(const MemberType& item)
{
if(tail_ == &beforeHead_) {
// list was empty
beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
::new(static_cast<void*>(&beforeHead_.next_->item_))T(item);
beforeHead_.next_->next_=0;
}else{
Element* added = allocator_.allocate(1, 0);
::new(static_cast<void*>(&added->item_))T(item);
added->next_=beforeHead_.next_;
beforeHead_.next_=added;
}
assert(tail_->next_==0);
++size_;
}
template<typename T, class A>
inline void SLList<T,A>::deleteNext(Element* current)
{
this->template deleteNext<true>(current);
}
template<typename T, class A>
template<bool watchForTail>
inline void SLList<T,A>::deleteNext(Element* current)
{
assert(current->next_);
Element* next = current->next_;
if(watchForTail)
if(next == tail_) {
// deleting last element changes tail!
tail_ = current;
}
current->next_ = next->next_;
std::allocator_traits<Allocator>::destroy(allocator_, next);
allocator_.deallocate(next, 1);
--size_;
assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
}
template<typename T, class A>
inline void SLList<T,A>::pop_front()
{
deleteNext(&beforeHead_);
}
template<typename T, class A>
inline void SLList<T,A>::clear()
{
while(beforeHead_.next_ ) {
this->template deleteNext<false>(&beforeHead_);
}
assert(size_==0);
// update the tail!
tail_ = &beforeHead_;
}
template<typename T, class A>
inline bool SLList<T,A>::empty() const
{
return (&beforeHead_ == tail_);
}
template<typename T, class A>
inline int SLList<T,A>::size() const
{
return size_;
}
template<typename T, class A>
inline SLListIterator<T,A> SLList<T,A>::begin()
{
return iterator(beforeHead_.next_, this);
}
template<typename T, class A>
inline SLListConstIterator<T,A> SLList<T,A>::begin() const
{
return const_iterator(beforeHead_.next_);
}
template<typename T, class A>
inline SLListIterator<T,A> SLList<T,A>::end()
{
return iterator();
}
template<typename T, class A>
inline SLListModifyIterator<T,A> SLList<T,A>::endModify()
{
return SLListModifyIterator<T,A>(iterator(tail_, this),iterator());
}
template<typename T, class A>
inline SLListModifyIterator<T,A> SLList<T,A>::beginModify()
{
return SLListModifyIterator<T,A>(iterator(&beforeHead_, this),
iterator(beforeHead_.next_, this));
}
template<typename T, class A>
inline SLListConstIterator<T,A> SLList<T,A>::end() const
{
return const_iterator();
}
}
#endif
iteratorfacades.hh
This file implements iterator facade classes for writing stl conformant iterators.
Dune::SLList::push_front
void push_front(const MemberType &item)
Add a new entry to the beginning of the list.
Definition sllist.hh:687
Dune::SLListConstIterator::equals
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:406
Dune::SLList::push_back
void push_back(const MemberType &item)
Add a new entry to the end of the list.
Definition sllist.hh:643
Dune::SLList::endModify
ModifyIterator endModify()
Get an iterator capable of deleting and inserting elements.
Definition sllist.hh:780
Dune::SLListModifyIterator::SLListModifyIterator
SLListModifyIterator()
Definition sllist.hh:438
Dune::SLList::Element::Element
Element()
Definition sllist.hh:557
Dune::SLListIterator::dereference
T & dereference() const
Dereferencing function for the iterator facade.
Definition sllist.hh:294
Dune::SLList::operator!=
bool operator!=(const SLList &sl) const
Definition sllist.hh:623
Dune::SLList::Element::item_
MemberType item_
The element we hold.
Definition sllist.hh:212
Dune::SLListConstIterator::SLListConstIterator
SLListConstIterator(typename SLList< T, A >::Element *item)
Definition sllist.hh:380
Dune::SLList< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator >::Allocator
typename std::allocator_traits< typename RemoteIndices::Allocator >::template rebind_alloc< Element > Allocator
Definition sllist.hh:64
Dune::SLListIterator::insertAfter
void insertAfter(const T &v) const
Insert an element in the underlying list after the current position.
Definition sllist.hh:342
Dune::SLList< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator >::iterator
SLListIterator< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator > iterator
Definition sllist.hh:69
Dune::SLListConstIterator::SLListConstIterator
SLListConstIterator(const SLListModifyIterator< T, A > &other)
Definition sllist.hh:388
Dune::SLListIterator::SLListIterator
SLListIterator()
Definition sllist.hh:282
Dune::SLList::Element::Element
Element(const MemberType &item, Element *next_=0)
Definition sllist.hh:552
Dune::SLList::Element::~Element
~Element()
Definition sllist.hh:562
Dune::SLList::operator==
bool operator==(const SLList &sl) const
Definition sllist.hh:611
Dune::SLListIterator::deleteNext
void deleteNext() const
Delete the entry after the current position.
Definition sllist.hh:353
Dune::SLList::SLList
SLList(const SLList< T, A > &other)
Copy constructor.
Definition sllist.hh:577
Dune::SLListIterator::equals
bool equals(const SLListModifyIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:324
Dune::SLListModifyIterator::dereference
T & dereference() const
Dereferencing function for the iterator facade.
Definition sllist.hh:446
Dune::SLList::size
int size() const
Get the number of elements the list contains.
Definition sllist.hh:756
Dune::SLList::begin
const_iterator begin() const
Get an iterator pointing to the first element in the list.
Definition sllist.hh:768
Dune::SLList::end
iterator end()
Get an iterator pointing to the end of the list.
Definition sllist.hh:774
Dune::SLList::clear
void clear()
Remove all elements from the list.
Definition sllist.hh:738
Dune::SLList::SLList
SLList(const SLList< T1, A1 > &other)
Copy constructor with type conversion.
Definition sllist.hh:585
Dune::SLList< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator >::MemberType
std::pair< GlobalIndex, Attribute > MemberType
Definition sllist.hh:59
Dune::SLListModifyIterator::equals
bool equals(const SLListModifyIterator< T, A > &other) const
Test whether another iterator is equal.
Definition sllist.hh:478
Dune::SLList::beginModify
ModifyIterator beginModify()
Get an iterator capable of deleting and inserting elements.
Definition sllist.hh:787
Dune::SLList::operator=
SLList< T, A > & operator=(const SLList< T, A > &other)
Assignment operator.
Definition sllist.hh:635
Dune::SLListConstIterator::SLListConstIterator
SLListConstIterator(const SLListIterator< T, A > &other)
Definition sllist.hh:384
Dune::SLList< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator >::const_iterator
SLListConstIterator< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator > const_iterator
Definition sllist.hh:74
Dune::SLList::empty
bool empty() const
Check whether the list is empty.
Definition sllist.hh:750
Dune::SLListConstIterator::SLListConstIterator
SLListConstIterator()
Definition sllist.hh:376
Dune::SLListIterator::equals
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:304
Dune::SLListModifyIterator::equals
bool equals(const SLListConstIterator< T, A > &other) const
Test whether another iterator is equal.
Definition sllist.hh:456
Dune::SLList< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator >::ModifyIterator
SLListModifyIterator< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator > ModifyIterator
Definition sllist.hh:103
Dune::SLList::end
const_iterator end() const
Get an iterator pointing to the end of the list.
Definition sllist.hh:794
Dune::SLList::SLList
SLList()
Constructor.
Definition sllist.hh:568
Dune::SLListModifyIterator::insert
void insert(const T &v)
Insert an element at the current position.
Definition sllist.hh:505
Dune::SLListIterator::SLListIterator
SLListIterator(typename SLList< T, A >::Element *item, SLList< T, A > *sllist)
Definition sllist.hh:277
Dune::SLListModifyIterator::SLListModifyIterator
SLListModifyIterator(SLListIterator< T, A > beforeIterator, SLListIterator< T, A > _iterator)
Definition sllist.hh:433
Dune::SLList::pop_front
void pop_front()
Remove the first item in the list.
Definition sllist.hh:732
Dune::SLListIterator::increment
void increment()
Increment function for the iterator facade.
Definition sllist.hh:332
Dune::SLListIterator::SLListIterator
SLListIterator(const SLListModifyIterator< T, A > &other)
Definition sllist.hh:286
Dune::SLList< std::pair< GlobalIndex, Attribute >, typename RemoteIndices::Allocator >::size_type
typename RemoteIndices::Allocator::size_type size_type
Definition sllist.hh:54
Dune::SLListModifyIterator::remove
void remove()
Delete the entry at the current position.
Definition sllist.hh:518
Dune::SLListConstIterator::dereference
const T & dereference() const
Dereferencing function for the facade.
Definition sllist.hh:396
Dune::SLList::Element::next_
Element * next_
The next element in the list.
Definition sllist.hh:208
Dune::SLListModifyIterator::increment
void increment()
Increment function for the iterator facade.
Definition sllist.hh:486
Dune::SLListConstIterator::increment
void increment()
Increment function for the iterator facade.
Definition sllist.hh:414
Dune::SLList::~SLList
~SLList()
Destructor.
Definition sllist.hh:605
Dune::SLListModifyIterator::equals
bool equals(const SLListIterator< T, A > &other) const
Test whether another iterator is equal.
Definition sllist.hh:467
Dune::SLList::begin
iterator begin()
Get an iterator pointing to the first element in the list.
Definition sllist.hh:762
Dune::SLListIterator::equals
bool equals(const SLListIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:314
Dune::operator<<
std::ostream & operator<<(std::ostream &s, const bigunsignedint< k > &x)
Definition bigunsignedint.hh:301
Dune
Dune namespace
Definition alignedallocator.hh:13
Dune::size
constexpr std::integral_constant< std::size_t, sizeof...(II)> size(std::integer_sequence< T, II... >)
Return the size of the sequence.
Definition integersequence.hh:75
Dune::push_back
constexpr HybridMultiIndex< T..., std::size_t > push_back(const HybridMultiIndex< T... > &tp, std::size_t i)
Appends a run time index to a HybridMultiIndex.
Definition hybridmultiindex.hh:249
Dune::ForwardIteratorFacade
Base class for stl conformant forward iterators.
Definition iteratorfacades.hh:142
Dune::SLListIterator
A mutable iterator for the SLList.
Definition sllist.hh:271
Dune::SLListConstIterator
A constant iterator for the SLList.
Definition sllist.hh:371
Dune::SLListModifyIterator
A mutable iterator for the SLList.
Definition sllist.hh:429
Dune::SLList
A single linked list.
Definition sllist.hh:44