List.h

#pragma once
 
#include <cstddef>
#include <iterator>
#include <type_traits>
 
namespace beast {
 
template <typename, typename>
class List;
 
namespace detail {

template <typename T, typename U>
struct CopyConst
{
    explicit CopyConst() = default;
 
    using type = std::remove_const_t<U>;
};
 
template <typename T, typename U>
struct CopyConst<T const, U>
{
    explicit CopyConst() = default;
 
    using type = std::remove_const<U>::type const;
};

 
// This is the intrusive portion of the doubly linked list.
// One derivation per list that the object may appear on
// concurrently is required.
//
template <typename T, typename Tag>
class ListNode
{
    ListNode() = default;
 
    using value_type = T;
 
    friend T;
    friend class List<T, Tag>;
 
    template <typename>
    friend class ListIterator;
 
    ListNode* next_ = nullptr;
    ListNode* prev_ = nullptr;
};
 
//------------------------------------------------------------------------------
 
template <typename N>
class ListIterator
{
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = beast::detail::CopyConst<N, typename N::value_type>::type;
    using difference_type = std::ptrdiff_t;
    using pointer = value_type*;
    using reference = value_type&;
    using size_type = std::size_t;
 
    ListIterator(N* node = nullptr) noexcept : node_(node)
    {
    }
 
    template <typename M>
    ListIterator(ListIterator<M> const& other) noexcept : node_(other.node_)
    {
    }
 
    template <typename M>
    bool
    operator==(ListIterator<M> const& other) const noexcept
    {
        return node_ == other.node_;
    }
 
    reference
    operator*() const noexcept
    {
        return dereference();
    }
 
    pointer
    operator->() const noexcept
    {
        return &dereference();
    }
 
    ListIterator&
    operator++() noexcept
    {
        increment();
        return *this;
    }
 
    ListIterator
    operator++(int) noexcept
    {
        ListIterator result(*this);
        increment();
        return result;
    }
 
    ListIterator&
    operator--() noexcept
    {
        decrement();
        return *this;
    }
 
    ListIterator
    operator--(int) noexcept
    {
        ListIterator result(*this);
        decrement();
        return result;
    }
 
private:
    [[nodiscard]] reference
    dereference() const noexcept
    {
        return static_cast<reference>(*node_);
    }
 
    void
    increment() noexcept
    {
        node_ = node_->next_;
    }
 
    void
    decrement() noexcept
    {
        node_ = node_->prev_;
    }
 
    N* node_;
};
 
}  // namespace detail

template <typename T, typename Tag = void>
class List
{
public:
    using Node = detail::ListNode<T, Tag>;
 
    using value_type = T;
    using pointer = value_type*;
    using reference = value_type&;
    using const_pointer = value_type const*;
    using const_reference = value_type const&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
 
    using iterator = detail::ListIterator<Node>;
    using const_iterator = detail::ListIterator<Node const>;

    List()
    {
        head_.prev_ = nullptr;  // identifies the head
        tail_.next_ = nullptr;  // identifies the tail
        clear();
    }
 
    List(List const&) = delete;
    List&
    operator=(List const&) = delete;

    [[nodiscard]] bool
    empty() const noexcept
    {
        return size() == 0;
    }

    [[nodiscard]] size_type
    size() const noexcept
    {
        return size_;
    }

    reference
    front() noexcept
    {
        return element_from(head_.next_);
    }

    [[nodiscard]] const_reference
    front() const noexcept
    {
        return element_from(head_.next_);
    }

    reference
    back() noexcept
    {
        return element_from(tail_.prev_);
    }

    [[nodiscard]] const_reference
    back() const noexcept
    {
        return element_from(tail_.prev_);
    }

    iterator
    begin() noexcept
    {
        return iterator(head_.next_);
    }

    [[nodiscard]] const_iterator
    begin() const noexcept
    {
        return const_iterator(head_.next_);
    }

    [[nodiscard]] const_iterator
    cbegin() const noexcept
    {
        return const_iterator(head_.next_);
    }

    iterator
    end() noexcept
    {
        return iterator(&tail_);
    }

    [[nodiscard]] const_iterator
    end() const noexcept
    {
        return const_iterator(&tail_);
    }

    [[nodiscard]] const_iterator
    cend() const noexcept
    {
        return const_iterator(&tail_);
    }

    void
    clear() noexcept
    {
        head_.next_ = &tail_;
        tail_.prev_ = &head_;
        size_ = 0;
    }

    iterator
    insert(iterator pos, T& element) noexcept
    {
        Node* node = static_cast<Node*>(&element);
        node->next_ = &*pos;
        node->prev_ = node->next_->prev_;
        node->next_->prev_ = node;
        node->prev_->next_ = node;
        ++size_;
        return iterator(node);
    }

    void
    insert(iterator pos, List& other) noexcept
    {
        if (!other.empty())
        {
            Node* before = &*pos;
            other.head_.next_->prev_ = before->prev_;
            before->prev_->next_ = other.head_.next_;
            other.tail_.prev_->next_ = before;
            before->prev_ = other.tail_.prev_;
            size_ += other.size_;
            other.clear();
        }
    }

    iterator
    erase(iterator pos) noexcept
    {
        Node const* node = &*pos;
        ++pos;
        node->next_->prev_ = node->prev_;
        node->prev_->next_ = node->next_;
        --size_;
        return pos;
    }

    iterator
    pushFront(T& element) noexcept
    {
        return insert(begin(), element);
    }

    T&
    popFront() noexcept
    {
        T& element(front());
        erase(begin());
        return element;
    }

    iterator
    pushBack(T& element) noexcept
    {
        return insert(end(), element);
    }

    T&
    popBack() noexcept
    {
        T& element(back());
        erase(--end());
        return element;
    }

    void
    swap(List& other) noexcept
    {
        List temp;
        temp.append(other);
        other.append(*this);
        append(temp);
    }

    iterator
    prepend(List& list) noexcept
    {
        return insert(begin(), list);
    }

    iterator
    append(List& list) noexcept
    {
        return insert(end(), list);
    }

    iterator
    iteratorTo(T& element) const noexcept
    {
        return iterator(static_cast<Node*>(&element));
    }

    [[nodiscard]] const_iterator
    constIteratorTo(T const& element) const noexcept
    {
        return const_iterator(static_cast<Node const*>(&element));
    }
 
private:
    reference
    elementFrom(Node* node) noexcept
    {
        return *(static_cast<pointer>(node));
    }
 
    const_reference
    elementFrom(Node const* node) const noexcept
    {
        return *(static_cast<const_pointer>(node));
    }
 
private:
    size_type size_ = 0u;
    Node head_;
    Node tail_;
};
 
}  // namespace beast