List.h

// Snake Game, Copyright LifeEXE. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Misc/AssertionMacros.h"
 
namespace SnakeGame
{
 
template <class ContainerType>
class TLinkedListIteratorBase
{
public:
    explicit TLinkedListIteratorBase(ContainerType* FirstLink) : CurrentLink(FirstLink) {}
 
    FORCEINLINE void Next()
    {
        checkSlow(CurrentLink);
        CurrentLink = (ContainerType*)CurrentLink->GetNextLink();
    }
 
    FORCEINLINE TLinkedListIteratorBase& operator++()
    {
        Next();
        return *this;
    }
 
    FORCEINLINE TLinkedListIteratorBase operator++(int)
    {
        auto Tmp = *this;
        Next();
        return Tmp;
    }
 
    FORCEINLINE explicit operator bool() const { return CurrentLink != nullptr; }
 
protected:
    ContainerType* CurrentLink;
 
    FORCEINLINE friend bool operator==(const TLinkedListIteratorBase& Lhs, const TLinkedListIteratorBase& Rhs)
    {
        return Lhs.CurrentLink == Rhs.CurrentLink;
    }
    FORCEINLINE friend bool operator!=(const TLinkedListIteratorBase& Lhs, const TLinkedListIteratorBase& Rhs)
    {
        return Lhs.CurrentLink != Rhs.CurrentLink;
    }
};
 
template <class ContainerType, class ElementType>
class TLinkedListIterator : public TLinkedListIteratorBase<ContainerType>
{
    typedef TLinkedListIteratorBase<ContainerType> Super;
 
public:
    explicit TLinkedListIterator(ContainerType* FirstLink) : Super(FirstLink) {}
 
    // Accessors.
    FORCEINLINE ElementType& operator->() const
    {
        checkSlow(this->CurrentLink);
        return **(this->CurrentLink);
    }
 
    FORCEINLINE ElementType& operator*() const
    {
        checkSlow(this->CurrentLink);
        return **(this->CurrentLink);
    }
};
 
template <class ContainerType, class ElementType>
class TIntrusiveLinkedListIterator : public TLinkedListIteratorBase<ElementType>
{
    typedef TLinkedListIteratorBase<ElementType> Super;
 
public:
    explicit TIntrusiveLinkedListIterator(ElementType* FirstLink) : Super(FirstLink) {}
 
    // Accessors.
    FORCEINLINE ElementType& operator->() const
    {
        checkSlow(this->CurrentLink);
        return *(this->CurrentLink);
    }
 
    FORCEINLINE ElementType& operator*() const
    {
        checkSlow(this->CurrentLink);
        return *(this->CurrentLink);
    }
};
 
template <class ContainerType, class ElementType, template <class, class> class IteratorType>
class TLinkedListBase
{
public:
    typedef IteratorType<ContainerType, ElementType> TIterator;
    typedef IteratorType<ContainerType, const ElementType> TConstIterator;
 
    TLinkedListBase() : NextLink(NULL), PrevLink(NULL) {}
 
    FORCEINLINE void Unlink()
    {
        if (NextLink)
        {
            NextLink->PrevLink = PrevLink;
        }
        if (PrevLink)
        {
            *PrevLink = NextLink;
        }
        // Make it safe to call Unlink again.
        NextLink = nullptr;
        PrevLink = nullptr;
    }
 
    FORCEINLINE void LinkBefore(ContainerType* Before)
    {
        checkSlow(Before != NULL);
 
        PrevLink = Before->PrevLink;
        Before->PrevLink = &NextLink;
 
        NextLink = Before;
 
        if (PrevLink != NULL)
        {
            *PrevLink = (ContainerType*)this;
        }
    }
 
    FORCEINLINE void LinkAfter(ContainerType* After)
    {
        checkSlow(After != NULL);
 
        PrevLink = &After->NextLink;
        NextLink = *PrevLink;
        *PrevLink = (ContainerType*)this;
 
        if (NextLink != NULL)
        {
            NextLink->PrevLink = &NextLink;
        }
    }
 
    FORCEINLINE void LinkReplace(ContainerType* Replace)
    {
        checkSlow(Replace != NULL);
 
        ContainerType**& ReplacePrev = Replace->PrevLink;
        ContainerType*& ReplaceNext = Replace->NextLink;
 
        PrevLink = ReplacePrev;
        NextLink = ReplaceNext;
 
        if (PrevLink != NULL)
        {
            *PrevLink = (ContainerType*)this;
        }
 
        if (NextLink != NULL)
        {
            NextLink->PrevLink = &NextLink;
        }
 
        ReplacePrev = NULL;
        ReplaceNext = NULL;
    }
 
    FORCEINLINE void LinkHead(ContainerType*& Head)
    {
        if (Head != NULL)
        {
            Head->PrevLink = &NextLink;
        }
 
        NextLink = Head;
        PrevLink = &Head;
        Head = (ContainerType*)this;
    }
 
    FORCEINLINE bool IsLinked() { return PrevLink != nullptr; }
 
    FORCEINLINE ContainerType** GetPrevLink() const { return PrevLink; }
 
    FORCEINLINE ContainerType* GetNextLink() const { return NextLink; }
 
    FORCEINLINE ContainerType* Next() { return NextLink; }
 
private:
    ContainerType* NextLink;
 
    ContainerType** PrevLink;
 
    FORCEINLINE friend TIterator begin(ContainerType& List) { return TIterator(&List); }
    FORCEINLINE friend TConstIterator begin(const ContainerType& List) { return TConstIterator(const_cast<ContainerType*>(&List)); }
    FORCEINLINE friend TIterator end(ContainerType& List) { return TIterator(nullptr); }
    FORCEINLINE friend TConstIterator end(const ContainerType& List) { return TConstIterator(nullptr); }
};
 
template <class ElementType>
class TLinkedList : public TLinkedListBase<TLinkedList<ElementType>, ElementType, TLinkedListIterator>
{
    typedef TLinkedListBase<TLinkedList<ElementType>, ElementType, TLinkedListIterator> Super;
 
public:
    TLinkedList() : Super() {}
 
    explicit TLinkedList(const ElementType& InElement) : Super(), Element(InElement) {}
 
    // Accessors.
    FORCEINLINE ElementType* operator->() { return &Element; }
    FORCEINLINE const ElementType* operator->() const { return &Element; }
    FORCEINLINE ElementType& operator*() { return Element; }
    FORCEINLINE const ElementType& operator*() const { return Element; }
 
private:
    ElementType Element;
};
 
template <class ElementType>
class TIntrusiveLinkedList : public TLinkedListBase<ElementType, ElementType, TIntrusiveLinkedListIterator>
{
    typedef TLinkedListBase<ElementType, ElementType, TIntrusiveLinkedListIterator> Super;
 
public:
    TIntrusiveLinkedList() : Super() {}
};
 
template <class NodeType, class ElementType>
class TDoubleLinkedListIterator
{
public:
    explicit TDoubleLinkedListIterator(NodeType* StartingNode) : CurrentNode(StartingNode) {}
 
    FORCEINLINE explicit operator bool() const { return CurrentNode != nullptr; }
 
    TDoubleLinkedListIterator& operator++()
    {
        checkSlow(CurrentNode);
        CurrentNode = CurrentNode->GetNextNode();
        return *this;
    }
 
    TDoubleLinkedListIterator operator++(int)
    {
        auto Tmp = *this;
        ++(*this);
        return Tmp;
    }
 
    TDoubleLinkedListIterator& operator--()
    {
        checkSlow(CurrentNode);
        CurrentNode = CurrentNode->GetPrevNode();
        return *this;
    }
 
    TDoubleLinkedListIterator operator--(int)
    {
        auto Tmp = *this;
        --(*this);
        return Tmp;
    }
 
    // Accessors.
    ElementType& operator->() const
    {
        checkSlow(CurrentNode);
        return CurrentNode->GetValue();
    }
 
    ElementType& operator*() const
    {
        checkSlow(CurrentNode);
        return CurrentNode->GetValue();
    }
 
    NodeType* GetNode() const
    {
        checkSlow(CurrentNode);
        return CurrentNode;
    }
 
private:
    NodeType* CurrentNode;
 
    friend bool operator==(const TDoubleLinkedListIterator& Lhs, const TDoubleLinkedListIterator& Rhs)
    {
        return Lhs.CurrentNode == Rhs.CurrentNode;
    }
    friend bool operator!=(const TDoubleLinkedListIterator& Lhs, const TDoubleLinkedListIterator& Rhs)
    {
        return Lhs.CurrentNode != Rhs.CurrentNode;
    }
};
 
template <class ElementType>
class TDoubleLinkedList
{
public:
    class TDoubleLinkedListNode
    {
    public:
        friend class TDoubleLinkedList;
 
        TDoubleLinkedListNode(const ElementType& InValue) : Value(InValue), NextNode(nullptr), PrevNode(nullptr) {}
 
        const ElementType& GetValue() const { return Value; }
 
        ElementType& GetValue() { return Value; }
 
        TDoubleLinkedListNode* GetNextNode() { return NextNode; }
 
        const TDoubleLinkedListNode* GetNextNode() const { return NextNode; }
 
        TDoubleLinkedListNode* GetPrevNode() { return PrevNode; }
 
        const TDoubleLinkedListNode* GetPrevNode() const { return PrevNode; }
 
    protected:
        ElementType Value;
        TDoubleLinkedListNode* NextNode;
        TDoubleLinkedListNode* PrevNode;
    };
 
    typedef TDoubleLinkedListIterator<TDoubleLinkedListNode, ElementType> TIterator;
    typedef TDoubleLinkedListIterator<TDoubleLinkedListNode, const ElementType> TConstIterator;
 
    TDoubleLinkedList() : HeadNode(nullptr), TailNode(nullptr), ListSize(0) {}
 
    virtual ~TDoubleLinkedList() { Empty(); }
 
    // Adding/Removing methods
 
    bool AddHead(const ElementType& InElement) { return AddHead(new TDoubleLinkedListNode(InElement)); }
 
    bool AddHead(TDoubleLinkedListNode* NewNode)
    {
        if (NewNode == nullptr)
        {
            return false;
        }
 
        // have an existing head node - change the head node to point to this one
        if (HeadNode != nullptr)
        {
            NewNode->NextNode = HeadNode;
            HeadNode->PrevNode = NewNode;
            HeadNode = NewNode;
        }
        else
        {
            HeadNode = TailNode = NewNode;
        }
 
        SetListSize(ListSize + 1);
        return true;
    }
 
    bool AddTail(const ElementType& InElement) { return AddTail(new TDoubleLinkedListNode(InElement)); }
 
    bool AddTail(TDoubleLinkedListNode* NewNode)
    {
        if (NewNode == nullptr)
        {
            return false;
        }
 
        if (TailNode != nullptr)
        {
            TailNode->NextNode = NewNode;
            NewNode->PrevNode = TailNode;
            TailNode = NewNode;
        }
        else
        {
            HeadNode = TailNode = NewNode;
        }
 
        SetListSize(ListSize + 1);
        return true;
    }
 
    bool InsertNode(const ElementType& InElement, TDoubleLinkedListNode* NodeToInsertBefore = nullptr)
    {
        return InsertNode(new TDoubleLinkedListNode(InElement), NodeToInsertBefore);
    }
 
    bool InsertNode(TDoubleLinkedListNode* NewNode, TDoubleLinkedListNode* NodeToInsertBefore = nullptr)
    {
        if (NewNode == nullptr)
        {
            return false;
        }
 
        if (NodeToInsertBefore == nullptr || NodeToInsertBefore == HeadNode)
        {
            return AddHead(NewNode);
        }
 
        NewNode->PrevNode = NodeToInsertBefore->PrevNode;
        NewNode->NextNode = NodeToInsertBefore;
 
        NodeToInsertBefore->PrevNode->NextNode = NewNode;
        NodeToInsertBefore->PrevNode = NewNode;
 
        SetListSize(ListSize + 1);
        return true;
    }
 
    void RemoveNode(const ElementType& InElement)
    {
        TDoubleLinkedListNode* ExistingNode = FindNode(InElement);
        RemoveNode(ExistingNode);
    }
 
    void RemoveNode(TDoubleLinkedListNode* NodeToRemove, bool bDeleteNode = true)
    {
        if (NodeToRemove != nullptr)
        {
            // if we only have one node, just call Clear() so that we don't have to do lots of extra checks in the code below
            if (Num() == 1)
            {
                checkSlow(NodeToRemove == HeadNode);
                if (bDeleteNode)
                {
                    Empty();
                }
                else
                {
                    NodeToRemove->NextNode = NodeToRemove->PrevNode = nullptr;
                    HeadNode = TailNode = nullptr;
                    SetListSize(0);
                }
                return;
            }
 
            if (NodeToRemove == HeadNode)
            {
                HeadNode = HeadNode->NextNode;
                HeadNode->PrevNode = nullptr;
            }
 
            else if (NodeToRemove == TailNode)
            {
                TailNode = TailNode->PrevNode;
                TailNode->NextNode = nullptr;
            }
            else
            {
                NodeToRemove->NextNode->PrevNode = NodeToRemove->PrevNode;
                NodeToRemove->PrevNode->NextNode = NodeToRemove->NextNode;
            }
 
            if (bDeleteNode)
            {
                delete NodeToRemove;
            }
            else
            {
                NodeToRemove->NextNode = NodeToRemove->PrevNode = nullptr;
            }
            SetListSize(ListSize - 1);
        }
    }
 
    void Empty()
    {
        TDoubleLinkedListNode* Node;
        while (HeadNode != nullptr)
        {
            Node = HeadNode->NextNode;
            delete HeadNode;
            HeadNode = Node;
        }
 
        HeadNode = TailNode = nullptr;
        SetListSize(0);
    }
 
    // Accessors.
 
    TDoubleLinkedListNode* GetHead() const { return HeadNode; }
 
    TDoubleLinkedListNode* GetTail() const { return TailNode; }
 
    TDoubleLinkedListNode* FindNode(const ElementType& InElement)
    {
        TDoubleLinkedListNode* Node = HeadNode;
        while (Node != nullptr)
        {
            if (Node->GetValue() == InElement)
            {
                break;
            }
 
            Node = Node->NextNode;
        }
 
        return Node;
    }
 
    bool Contains(const ElementType& InElement) { return (FindNode(InElement) != nullptr); }
 
    bool IsEmpty() const { return ListSize == 0; }
 
    int32 Num() const { return ListSize; }
 
    void MoveTailAfterHead()
    {
        TailNode->PrevNode->NextNode = nullptr;
        auto* NewTailNode = TailNode->PrevNode;
 
        TailNode->NextNode = HeadNode->NextNode;
        HeadNode->NextNode->PrevNode = TailNode;
 
        TailNode->PrevNode = HeadNode;
        HeadNode->NextNode = TailNode;
 
        TailNode = NewTailNode;
    }
 
protected:
    virtual void SetListSize(int32 NewListSize) { ListSize = NewListSize; }
 
private:
    TDoubleLinkedListNode* HeadNode;
    TDoubleLinkedListNode* TailNode;
    int32 ListSize;
 
    TDoubleLinkedList(const TDoubleLinkedList&);
    // TDoubleLinkedList& operator=(const TDoubleLinkedList&);
 
    friend TIterator begin(TDoubleLinkedList& List) { return TIterator(List.GetHead()); }
    friend TConstIterator begin(const TDoubleLinkedList& List) { return TConstIterator(List.GetHead()); }
    friend TIterator end(TDoubleLinkedList& List) { return TIterator(nullptr); }
    friend TConstIterator end(const TDoubleLinkedList& List) { return TConstIterator(nullptr); }
};
 
/*----------------------------------------------------------------------------
    TList.
----------------------------------------------------------------------------*/
 
//
// Simple single-linked list template.
//
template <class ElementType>
class TList
{
public:
    ElementType Element;
    TList<ElementType>* Next;
 
    // Constructor.
 
    TList(const ElementType& InElement, TList<ElementType>* InNext = nullptr)
    {
        Element = InElement;
        Next = InNext;
    }
};
 
}  // namespace SnakeGame