nrr_ill.h

#pragma once

// Intrusive Linked List (or Internal Linked List, etc)
// by Nathan Reed, 2020-01-18. Licensed CC0 https://creativecommons.org/publicdomain/zero/1.0/
//
// Use it like:
//
// class MyClass
// {
//     ...
//     ILL<MyClass>::Node node;
// };
//
// ILL<MyClass> list(&MyClass::node);
// 
// list.Append(...)
// list.Insert(...)
// list.Remove(...)
// for (MyClass& myclass : list)
// {
//     ...
// }

#include <nrr_assert.h>

namespace nrr
{
    template <typename T>
    class ILL
    {
    public:
        class Node;
        class Iterator;
        class ConstIterator;

        explicit ILL(Node T::* offset);
        ~ILL();
        ILL(ILL&) = delete;
        ILL(ILL&&);
        ILL& operator = (ILL&) = delete;
        ILL& operator = (ILL&&);

        bool IsEmpty() const;
        void Append(T&);
        void Insert(T& before, T& elem);
        void Remove(T&);
        void Clear();

        Iterator begin();
        Iterator end();
        ConstIterator begin() const;
        ConstIterator end() const;

        class Node
        {
        public:
            Node() = default;
            ~Node();
            Node(const Node&);
            Node& operator = (const Node&);

        private:
            friend class ILL;
            T* next = nullptr;
            T* prev = nullptr;
        };

        class Iterator
        {
        public:
            bool operator == (const Iterator&);
            bool operator != (const Iterator&);
            Iterator& operator ++ ();
            T& operator * () const;
            T& operator -> () const;

        private:
            friend class ILL;
            Iterator(T*, Node T::* offset);
            T* head;
            T* elem;
            Node T::* offset;
        };

        class ConstIterator
        {
        public:
            bool operator == (const ConstIterator&);
            bool operator != (const ConstIterator&);
            ConstIterator& operator ++ ();
            const T& operator * () const;
            const T& operator -> () const;

        private:
            friend class ILL;
            ConstIterator(T*, Node T::* offset);
            const T* head;
            const T* elem;
            Node T::* offset;
        };

    private:
        T* head;
        Node T::* offset;
    };



    // Implementation

    template <typename T>
    ILL<T>::ILL(ILL<T>::Node T::* offset_)
        : head(nullptr),
          offset(offset_)
    {
        NRR_ASSERT(offset != nullptr);
    }

    template <typename T>
    ILL<T>::~ILL()
    {
        Clear();
    }

    template <typename T>
    ILL<T>::ILL(ILL&& other)
        : head(other.head), offset(other.offset)
    {
        other.head = nullptr;
    }

    template <typename T>
    ILL<T>& ILL<T>::operator = (ILL&& other)
    {
        head = other.head;
        offset = other.offset;
        other.head = nullptr;
        return *this;
    }

    template <typename T>
    bool ILL<T>::IsEmpty() const
    {
        return (head == nullptr);
    }

    template <typename T>
    void ILL<T>::Append(T& elem)
    {
        auto& node = elem.*offset;
        NRR_ASSERTF(node.next == nullptr && node.prev == nullptr, "Can't append an item that's already on a list");

        if (head)
        {
            auto& headNode = head->*offset;
            (headNode.prev->*offset).next = &elem;
            node.prev = headNode.prev;
            node.next = head;
            headNode.prev = &elem;
        }
        else
        {
            head = &elem;
            node.next = &elem;
            node.prev = &elem;
        }
    }

    template <typename T>
    void ILL<T>::Insert(T& before, T& elem)
    {
        auto& beforeNode = before.*offset;
        NRR_ASSERTF(beforeNode.next != nullptr && beforeNode.prev != nullptr, "Can't insert before an item that's not on a list");
        auto& node = elem.*offset;
        NRR_ASSERTF(node.next == nullptr && node.prev == nullptr, "Can't insert an item that's already on a list");

        (beforeNode.prev->*offset).next = &elem;
        node.prev = beforeNode.prev;
        node.next = &before;
        beforeNode.prev = &elem;
    }

    template <typename T>
    void ILL<T>::Remove(T& elem)
    {
        auto& node = elem.*offset;
        NRR_ASSERTF(node.next != nullptr && node.prev != nullptr, "Can't remove an item that's not on a list");

        if (node.next == &elem && node.prev == &elem)
        {
            NRR_ASSERT(head == &elem);
            head = nullptr;
        }
        else
        {
            (node.next->*offset).prev = node.prev;
            (node.prev->*offset).next = node.next;

            if (head == &elem)
            {
                head = node.next;
            }
        }

        node.next = nullptr;
        node.prev = nullptr;
    }

    template <typename T>
    void ILL<T>::Clear()
    {
        if (!head)
            return;

        for (T* elem = head;;)
        {
            T* next = (elem->*offset).next;
            (elem->*offset).next = nullptr;
            (elem->*offset).prev = nullptr;
            if (next == head)
                break;
            elem = next;
        }

        head = nullptr;
    }

    template <typename T>
    typename ILL<T>::Iterator ILL<T>::begin()
    {
        return Iterator(head, offset);
    }

    template <typename T>
    typename ILL<T>::Iterator ILL<T>::end()
    {
        return Iterator(nullptr, offset);
    }

    template <typename T>
    typename ILL<T>::ConstIterator ILL<T>::begin() const
    {
        return ConstIterator(head, offset);
    }

    template <typename T>
    typename ILL<T>::ConstIterator ILL<T>::end() const
    {
        return ConstIterator(nullptr, offset);
    }

    template <typename T>
    ILL<T>::Node::~Node()
    {
        // Remove(*this);
        NRR_ASSERTF(next == nullptr && prev == nullptr, "Destroying an object that's still on a linked list");
    }

    template <typename T>
    ILL<T>::Node::Node(const Node&)
        : Node()    // Don't copy the next & prev pointers from the source Node
    {
    }

    template <typename T>
    typename ILL<T>::Node& ILL<T>::Node::operator = (const Node&)
    {
        // Don't copy the next & prev pointers from the source Node
        return *this;
    }

    template <typename T>
    ILL<T>::Iterator::Iterator(T* elem_, Node T::* offset_)
        : head(elem_), elem(elem_), offset(offset_)
    {
    }

    template <typename T>
    bool ILL<T>::Iterator::operator == (const Iterator& other)
    {
        return (head == other.head && elem == other.elem);
    }

    template <typename T>
    bool ILL<T>::Iterator::operator != (const Iterator& other)
    {
        return (head != other.head || elem != other.elem);
    }

    template <typename T>
    typename ILL<T>::Iterator& ILL<T>::Iterator::operator ++ ()
    {
        if (elem)
        {
            elem = (elem->*offset).next;
            if (elem == head)
            {
                head = nullptr;
                elem = nullptr;
            }
        }

        return *this;
    }

    template <typename T>
    T& ILL<T>::Iterator::operator * () const
    {
        return *elem;
    }

    template <typename T>
    T& ILL<T>::Iterator::operator -> () const
    {
        return *elem;
    }

    template <typename T>
    ILL<T>::ConstIterator::ConstIterator(T* elem_, Node T::* offset_)
        : head(elem_), elem(elem_), offset(offset_)
    {
    }

    template <typename T>
    bool ILL<T>::ConstIterator::operator == (const ConstIterator& other)
    {
        return (head == other.head && elem == other.elem);
    }

    template <typename T>
    bool ILL<T>::ConstIterator::operator != (const ConstIterator& other)
    {
        return (head != other.head || elem != other.elem);
    }

    template <typename T>
    typename ILL<T>::ConstIterator& ILL<T>::ConstIterator::operator ++ ()
    {
        if (elem)
        {
            elem = (elem->*offset).next;
            if (elem == head)
            {
                head = nullptr;
                elem = nullptr;
            }
        }

        return *this;
    }

    template <typename T>
    const T& ILL<T>::ConstIterator::operator * () const
    {
        return *elem;
    }

    template <typename T>
    const T& ILL<T>::ConstIterator::operator -> () const
    {
        return *elem;
    }
}