List.h

Go to the documentation of this file.

#pragma once
 
 
#include "common/Traits.h"
#include "objects/containers/Allocators.h"
#include "objects/wrappers/RawPtr.h"
 
NAMESPACE_SPH_BEGIN
 
template <typename T, typename TAllocator = Mallocator>
class List;
 
template <typename T>
struct ListNode {
    using StorageType = typename WrapReferenceType<T>::Type;
 
    StorageType value;
 
    RawPtr<ListNode> next;
 
    RawPtr<ListNode> prev;
 
    template <typename U>
    ListNode(U&& value, RawPtr<ListNode> prev, RawPtr<ListNode> next)
        : value(std::forward<U>(value))
        , next(next)
        , prev(prev) {
        // update pointers of neighbouring nodes
        if (prev) {
            prev->next = this;
        }
        if (next) {
            next->prev = this;
        }
    }
 
    void detach() {
        if (prev) {
            prev->next = next;
        }
        if (next) {
            next->prev = prev;
        }
    }
};
 
template <typename T>
class ListIterator {
    template <typename, typename>
    friend class List;
 
private:
    RawPtr<ListNode<T>> node;
 
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
 
    explicit ListIterator(RawPtr<ListNode<T>> node)
        : node(node) {}
 
    INLINE ListIterator& operator++() {
        if (node) {
            node = node->next;
        }
        return *this;
    }
 
    INLINE ListIterator operator++(int) {
        ListIterator next = *this;
        ++next;
        return next;
    }
 
    INLINE ListIterator& operator--() {
        if (node) {
            node = node->prev;
        }
        return *this;
    }
 
    INLINE ListIterator operator--(int) {
        ListIterator prev = *this;
        --prev;
        return prev;
    }
 
    INLINE T& operator*() const {
        SPH_ASSERT(node);
        return node->value;
    }
 
    INLINE RawPtr<T> operator->() const {
        SPH_ASSERT(node);
        return &node->value;
    }
 
    INLINE explicit operator bool() const {
        return bool(node);
    }
 
    INLINE bool operator!() const {
        return !node;
    }
 
    bool operator==(const ListIterator& other) const {
        return node == other.node;
    }
 
    bool operator!=(const ListIterator& other) const {
        return node != other.node;
    }
};
 
template <typename T, typename TAllocator>
class List : private TAllocator, public Noncopyable {
private:
    using StorageType = typename WrapReferenceType<T>::Type;
 
    RawPtr<ListNode<T>> first;
    RawPtr<ListNode<T>> last;
 
public:
    List()
        : first(nullptr)
        , last(nullptr) {}
 
    List(std::initializer_list<StorageType> list) {
        for (const StorageType& value : list) {
            this->pushBack(value);
        }
    }
 
    List(List&& other)
        : first(other.first)
        , last(other.last) {
        other.first = other.last = nullptr;
    }
 
    ~List() {
        this->clear();
    }
 
    List& operator=(List&& other) {
        std::swap(first, other.first);
        std::swap(last, other.last);
        return *this;
    }
 
    INLINE bool empty() const {
        return first == nullptr;
    }
 
    INLINE Size size() const {
        Size counter = 0;
        for (RawPtr<ListNode<T>> ptr = first; ptr != nullptr; ptr = ptr->next) {
            ++counter;
        }
        return counter;
    }
 
    template <typename U>
    void pushBack(U&& value) {
        RawPtr<ListNode<T>> node = newNode(std::forward<U>(value), last, nullptr);
        last = node;
        if (first == nullptr) {
            // this is the first element, update also first ptr.
            first = node;
        }
    }
 
    template <typename U>
    void pushFront(U&& value) {
        RawPtr<ListNode<T>> node = newNode(std::forward<U>(value), nullptr, first);
        first = node;
        if (last == nullptr) {
            // this is the first element, update also last ptr.
            last = node;
        }
    }
 
    template <typename U>
    void insert(const ListIterator<T> iter, U&& value) {
        SPH_ASSERT(iter);
        RawPtr<ListNode<T>> node = newNode(std::forward<U>(value), iter.node, iter.node->next);
        if (iter.node == last) {
            // we added to the back of the list, update the pointer
            last = node;
        }
    }
 
    ListIterator<T> erase(const ListIterator<T> iter) {
        SPH_ASSERT(iter);
        ListIterator<T> next = iter;
        ++next;
        RawPtr<ListNode<T>> node = iter.node;
        node->detach();
        if (node == first) {
            // erasing first element, adjust pointer
            first = first->next;
        }
        if (node == last) {
            // erasing last element, adjust pointer
            last = last->prev;
        }
        if (node) {
            deleteNode(node.get());
        }
        return next;
    }
 
    void clear() {
        for (RawPtr<ListNode<T>> ptr = first; ptr != nullptr;) {
            RawPtr<ListNode<T>> next = ptr->next;
            if (ptr) {
                deleteNode(ptr.get());
            }
            ptr = next;
        }
        first = last = nullptr;
    }
 
    INLINE T& front() {
        SPH_ASSERT(!this->empty());
        return first->value;
    }
 
    INLINE const T& front() const {
        SPH_ASSERT(!this->empty());
        return first->value;
    }
 
    INLINE T& back() {
        SPH_ASSERT(!this->empty());
        return last->value;
    }
 
    INLINE const T& back() const {
        SPH_ASSERT(!this->empty());
        return last->value;
    }
 
    List clone() const {
        List copy;
        for (auto& value : *this) {
            copy.pushBack(value);
        }
        return copy;
    }
 
    ListIterator<T> begin() {
        return ListIterator<T>(first);
    }
 
    ListIterator<const T> begin() const {
        // same types, only differ by const-ness
        return ListIterator<const T>(reinterpret_cast<ListNode<const T>*>(first.get()));
    }
 
    ListIterator<T> end() {
        return ListIterator<T>(nullptr);
    }
 
    ListIterator<const T> end() const {
        return ListIterator<const T>(nullptr);
    }
 
    const TAllocator& allocator() const {
        return *this;
    }
 
    TAllocator& allocator() {
        return *this;
    }
 
    template <typename TStream>
    friend TStream& operator<<(TStream& stream, const List& array) {
        for (const T& t : array) {
            stream << t << std::endl;
        }
        return stream;
    }
 
private:
    template <typename... TArgs>
    RawPtr<ListNode<T>> newNode(TArgs&&... args) {
        MemoryBlock block = TAllocator::allocate(sizeof(ListNode<T>), alignof(ListNode<T>));
        SPH_ASSERT(block.ptr);
        return new (block.ptr) ListNode<T>(std::forward<TArgs>(args)...);
    }
 
    void deleteNode(ListNode<T>* node) {
        node->~ListNode<T>();
        MemoryBlock block(node, sizeof(ListNode<T>));
        TAllocator::deallocate(block);
    }
};
 
NAMESPACE_SPH_END