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:
#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 SLListConstIterator<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(const SLListModifyIterator<T,A>& other)
      : beforeIterator_(other.beforeIterator_), iterator_(other.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