list.h

Go to the documentation of this file.

 
#ifndef CPPCOMMON_CONTAINERS_LIST_H
#define CPPCOMMON_CONTAINERS_LIST_H
 
#include <cassert>
#include <cstddef>
#include <iterator>
 
namespace CppCommon {
 
template <typename T>
class ListIterator;
template <typename T>
class ListConstIterator;
template <typename T>
class ListReverseIterator;
template <typename T>
class ListConstReverseIterator;
 
 
 
template <typename T>
class List
{
public:
    // Standard container type definitions
    typedef T value_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef ListIterator<T> iterator;
    typedef ListConstIterator<T> const_iterator;
    typedef ListReverseIterator<T> reverse_iterator;
    typedef ListConstReverseIterator<T> const_reverse_iterator;
 
    struct Node
    {
        T* next;    
        T* prev;    
 
        Node() : next(nullptr), prev(nullptr) {}
    };
 
    List() noexcept : _size(0), _front(nullptr), _back(nullptr) {}
    template <class InputIterator>
    List(InputIterator first, InputIterator last) noexcept;
    List(const List&) noexcept = default;
    List(List&&) noexcept = default;
    ~List() noexcept = default;
 
    List& operator=(const List&) noexcept = default;
    List& operator=(List&&) noexcept = default;
 
    explicit operator bool() const noexcept { return !empty(); }
 
    bool empty() const noexcept { return _front == nullptr; }
 
    size_t size() const noexcept { return _size; }
 
    T* front() noexcept { return _front; }
    const T* front() const noexcept { return _front; }
    T* back() noexcept { return _back; }
    const T* back() const noexcept { return _back; }
 
    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    const_iterator cbegin() const noexcept;
    iterator end() noexcept;
    const_iterator end() const noexcept;
    const_iterator cend() const noexcept;
 
    reverse_iterator rbegin() noexcept;
    const_reverse_iterator rbegin() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend() noexcept;
    const_reverse_iterator rend() const noexcept;
    const_reverse_iterator crend() const noexcept;
 
 
    void push_front(T& item) noexcept;
 
    void push_back(T& item) noexcept;
 
    void push_next(T& base, T& item) noexcept;
 
    void push_prev(T& base, T& item) noexcept;
 
 
    T* pop_front() noexcept;
 
    T* pop_back() noexcept;
 
    T* pop_current(T& base) noexcept;
 
    T* pop_next(T& base) noexcept;
 
    T* pop_prev(T& base) noexcept;
 
    void reverse() noexcept;
 
    void clear() noexcept;
 
    void swap(List& list) noexcept;
    template <typename U>
    friend void swap(List<U>& list1, List<U>& list2) noexcept;
 
private:
    size_t _size;   // List size
    T* _front;      // List front node
    T* _back;       // List back node
};
 
 
template <typename T>
class ListIterator
{
    friend ListConstIterator<T>;
 
public:
    // Standard iterator type definitions
    typedef T value_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef std::bidirectional_iterator_tag iterator_category;
 
    ListIterator() noexcept : _node(nullptr) {}
    explicit ListIterator(T* node) noexcept : _node(node) {}
    ListIterator(const ListIterator& it) noexcept = default;
    ListIterator(ListIterator&& it) noexcept = default;
    ~ListIterator() noexcept = default;
 
    ListIterator& operator=(const ListIterator& it) noexcept = default;
    ListIterator& operator=(ListIterator&& it) noexcept = default;
 
    friend bool operator==(const ListIterator& it1, const ListIterator& it2) noexcept
    { return it1._node == it2._node; }
    friend bool operator!=(const ListIterator& it1, const ListIterator& it2) noexcept
    { return it1._node != it2._node; }
 
    ListIterator& operator++() noexcept;
    ListIterator operator++(int) noexcept;
 
    reference operator*() noexcept;
    pointer operator->() noexcept;
 
    explicit operator bool() const noexcept { return _node != nullptr; }
 
    void swap(ListIterator& it) noexcept;
    template <typename U>
    friend void swap(ListIterator<U>& it1, ListIterator<U>& it2) noexcept;
 
private:
    T* _node;
};
 
 
template <typename T>
class ListConstIterator
{
public:
    // Standard iterator type definitions
    typedef T value_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef std::bidirectional_iterator_tag iterator_category;
 
    ListConstIterator() noexcept : _node(nullptr) {}
    explicit ListConstIterator(const T* node) noexcept : _node(node) {}
    ListConstIterator(const ListIterator<T>& it) noexcept : _node(it._node) {}
    ListConstIterator(const ListConstIterator& it) noexcept = default;
    ListConstIterator(ListConstIterator&& it) noexcept = default;
    ~ListConstIterator() noexcept = default;
 
    ListConstIterator& operator=(const ListIterator<T>& it) noexcept
    { _node = it._node; return *this; }
    ListConstIterator& operator=(const ListConstIterator& it) noexcept = default;
    ListConstIterator& operator=(ListConstIterator&& it) noexcept = default;
 
    friend bool operator==(const ListConstIterator& it1, const ListConstIterator& it2) noexcept
    { return it1._node == it2._node; }
    friend bool operator!=(const ListConstIterator& it1, const ListConstIterator& it2) noexcept
    { return it1._node != it2._node; }
 
    ListConstIterator& operator++() noexcept;
    ListConstIterator operator++(int) noexcept;
 
    const_reference operator*() const noexcept;
    const_pointer operator->() const noexcept;
 
    explicit operator bool() const noexcept { return _node != nullptr; }
 
    void swap(ListConstIterator& it) noexcept;
    template <typename U>
    friend void swap(ListConstIterator<U>& it1, ListConstIterator<U>& it2) noexcept;
 
private:
    const T* _node;
};
 
 
template <typename T>
class ListReverseIterator
{
    friend ListConstReverseIterator<T>;
 
public:
    // Standard iterator type definitions
    typedef T value_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef std::bidirectional_iterator_tag iterator_category;
 
    ListReverseIterator() noexcept : _node(nullptr) {}
    explicit ListReverseIterator(T* node) noexcept : _node(node) {}
    ListReverseIterator(const ListReverseIterator& it) noexcept = default;
    ListReverseIterator(ListReverseIterator&& it) noexcept = default;
    ~ListReverseIterator() noexcept = default;
 
    ListReverseIterator& operator=(const ListReverseIterator& it) noexcept = default;
    ListReverseIterator& operator=(ListReverseIterator&& it) noexcept = default;
 
    friend bool operator==(const ListReverseIterator& it1, const ListReverseIterator& it2) noexcept
    { return it1._node == it2._node; }
    friend bool operator!=(const ListReverseIterator& it1, const ListReverseIterator& it2) noexcept
    { return it1._node != it2._node; }
 
    ListReverseIterator& operator++() noexcept;
    ListReverseIterator operator++(int) noexcept;
 
    reference operator*() noexcept;
    pointer operator->() noexcept;
 
    explicit operator bool() const noexcept { return _node != nullptr; }
 
    void swap(ListReverseIterator& it) noexcept;
    template <typename U>
    friend void swap(ListReverseIterator<U>& it1, ListReverseIterator<U>& it2) noexcept;
 
private:
    T* _node;
};
 
 
template <typename T>
class ListConstReverseIterator
{
public:
    // Standard iterator type definitions
    typedef T value_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef std::bidirectional_iterator_tag iterator_category;
 
    ListConstReverseIterator() noexcept : _node(nullptr) {}
    explicit ListConstReverseIterator(const T* node) noexcept : _node(node) {}
    ListConstReverseIterator(const ListReverseIterator<T>& it) noexcept : _node(it._node) {}
    ListConstReverseIterator(const ListConstReverseIterator& it) noexcept = default;
    ListConstReverseIterator(ListConstReverseIterator&& it) noexcept = default;
    ~ListConstReverseIterator() noexcept = default;
 
    ListConstReverseIterator& operator=(const ListReverseIterator<T>& it) noexcept
    { _node = it._node; return *this; }
    ListConstReverseIterator& operator=(const ListConstReverseIterator& it) noexcept = default;
    ListConstReverseIterator& operator=(ListConstReverseIterator&& it) noexcept = default;
 
    friend bool operator==(const ListConstReverseIterator& it1, const ListConstReverseIterator& it2) noexcept
    { return it1._node == it2._node; }
    friend bool operator!=(const ListConstReverseIterator& it1, const ListConstReverseIterator& it2) noexcept
    { return it1._node != it2._node; }
 
    ListConstReverseIterator& operator++() noexcept;
    ListConstReverseIterator operator++(int) noexcept;
 
    const_reference operator*() const noexcept;
    const_pointer operator->() const noexcept;
 
    explicit operator bool() const noexcept { return _node != nullptr; }
 
    void swap(ListConstReverseIterator& it) noexcept;
    template <typename U>
    friend void swap(ListConstReverseIterator<U>& it1, ListConstReverseIterator<U>& it2) noexcept;
 
private:
    const T* _node;
};
 
} // namespace CppCommon
 
#include "list.inl"
 
#endif // CPPCOMMON_CONTAINERS_LIST_H