List.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "Misc/AssertionMacros.h"
#include "Templates/UnrealTemplate.h"
 
template <class ContainerType>
class TLinkedListIteratorBase
{
public:
    [[nodiscard]] explicit TLinkedListIteratorBase(ContainerType* FirstLink)
        : CurrentLink(FirstLink)
    {
    }
 
    inline void Next()
    {
        checkSlow(CurrentLink);
        CurrentLink = (ContainerType*)CurrentLink->GetNextLink();
    }
 
    inline TLinkedListIteratorBase& operator++()
    {
        Next();
        return *this;
    }
 
    inline TLinkedListIteratorBase operator++(int)
    {
        auto Tmp = *this;
        Next();
        return Tmp;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT explicit operator bool() const
    { 
        return CurrentLink != nullptr;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT bool operator==(const TLinkedListIteratorBase& Rhs) const { return CurrentLink == Rhs.CurrentLink; }
    [[nodiscard]] UE_FORCEINLINE_HINT bool operator!=(const TLinkedListIteratorBase& Rhs) const { return CurrentLink != Rhs.CurrentLink; }
protected:
 
    ContainerType* CurrentLink;
};
 
template <class ContainerType, class ElementType>
class TLinkedListIterator : public TLinkedListIteratorBase<ContainerType>
{
    typedef TLinkedListIteratorBase<ContainerType> Super;
 
public:
    [[nodiscard]] explicit TLinkedListIterator(ContainerType* FirstLink)
        : Super(FirstLink)
    {
    }
 
    // Accessors.
    inline ElementType& operator->() const
    {
        checkSlow(this->CurrentLink);
        return **(this->CurrentLink);
    }
 
    inline ElementType& operator*() const
    {
        checkSlow(this->CurrentLink);
        return **(this->CurrentLink);
    }
};
 
template <class ContainerType, class ElementType>
class TIntrusiveLinkedListIterator : public TLinkedListIteratorBase<ElementType>
{
    typedef TLinkedListIteratorBase<ElementType> Super;
 
public:
    [[nodiscard]] explicit TIntrusiveLinkedListIterator(ElementType* FirstLink)
        : Super(FirstLink)
    {
    }
 
    // Accessors.
    inline ElementType& operator->() const
    {
        checkSlow(this->CurrentLink);
        return *(this->CurrentLink);
    }
 
    inline 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;
 
 
    [[nodiscard]] TLinkedListBase()
        : NextLink(NULL)
        , PrevLink(NULL)
    {
    }
 
    inline void Unlink()
    {
        if( NextLink )
        {
            NextLink->PrevLink = PrevLink;
        }
        if( PrevLink )
        {
            *PrevLink = NextLink;
        }
        // Make it safe to call Unlink again.
        NextLink = nullptr;
        PrevLink = nullptr;
    }
 
 
    inline void LinkBefore(ContainerType* Before)
    {
        checkSlow(Before != NULL);
 
        PrevLink = Before->PrevLink;
        Before->PrevLink = &NextLink;
 
        NextLink = Before;
 
        if (PrevLink != NULL)
        {
            *PrevLink = (ContainerType*)this;
        }
    }
 
    inline void LinkAfter(ContainerType* After)
    {
        checkSlow(After != NULL);
 
        PrevLink = &After->NextLink;
        NextLink = *PrevLink;
        *PrevLink = (ContainerType*)this;
 
        if (NextLink != NULL)
        {
            NextLink->PrevLink = &NextLink;
        }
    }
 
    inline 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;
    }
 
 
    inline void LinkHead(ContainerType*& Head)
    {
        if (Head != NULL)
        {
            Head->PrevLink = &NextLink;
        }
 
        NextLink = Head;
        PrevLink = &Head;
        Head = (ContainerType*)this;
    }
 
 
    [[nodiscard]] UE_FORCEINLINE_HINT bool IsLinked()
    {
        return PrevLink != nullptr;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ContainerType** GetPrevLink() const
    {
        return PrevLink;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ContainerType* GetNextLink() const
    {
        return NextLink;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ContainerType* Next()
    {
        return NextLink;
    }
 
private:
    ContainerType*  NextLink;
 
    ContainerType** PrevLink;
 
 
    [[nodiscard]] UE_FORCEINLINE_HINT friend TIterator      begin(      ContainerType& List) { return TIterator     (&List); }
    [[nodiscard]] UE_FORCEINLINE_HINT friend TConstIterator begin(const ContainerType& List) { return TConstIterator(const_cast<ContainerType*>(&List)); }
    [[nodiscard]] UE_FORCEINLINE_HINT friend TIterator      end  (      ContainerType& List) { return TIterator     (nullptr); }
    [[nodiscard]] UE_FORCEINLINE_HINT 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:
    [[nodiscard]] TLinkedList()
        : Super()
    {
    }
 
    [[nodiscard]] explicit TLinkedList(const ElementType& InElement)
        : Super()
        , Element(InElement)
    {
    }
 
 
    // Accessors.
    [[nodiscard]] UE_FORCEINLINE_HINT ElementType* operator->()
    {
        return &Element;
    }
    [[nodiscard]] UE_FORCEINLINE_HINT const ElementType* operator->() const
    {
        return &Element;
    }
    [[nodiscard]] UE_FORCEINLINE_HINT ElementType& operator*()
    {
        return Element;
    }
    [[nodiscard]] UE_FORCEINLINE_HINT 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:
    [[nodiscard]] TIntrusiveLinkedList()
        : Super()
    {
    }
};
 
 
template <class NodeType, class ElementType>
class TDoubleLinkedListIterator
{
public:
 
    [[nodiscard]] explicit TDoubleLinkedListIterator(NodeType* StartingNode)
        : CurrentNode(StartingNode)
    {
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT 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.
    [[nodiscard]] ElementType& operator->() const
    {
        checkSlow(CurrentNode);
        return CurrentNode->GetValue();
    }
 
    [[nodiscard]] ElementType& operator*() const
    {
        checkSlow(CurrentNode);
        return CurrentNode->GetValue();
    }
 
    [[nodiscard]] NodeType* GetNode() const
    {
        checkSlow(CurrentNode);
        return CurrentNode;
    }
 
    [[nodiscard]] bool operator==(const TDoubleLinkedListIterator& Rhs) const { return CurrentNode == Rhs.CurrentNode; }
    [[nodiscard]] bool operator!=(const TDoubleLinkedListIterator& Rhs) const { return CurrentNode != Rhs.CurrentNode; }
 
private:
    NodeType* CurrentNode;
};
 
 
template <class ElementType>
class TDoubleLinkedList
{
public:
    class TDoubleLinkedListNode
    {
    public:
        friend class TDoubleLinkedList;
 
        [[nodiscard]] TDoubleLinkedListNode( const ElementType& InValue )
            : Value(InValue), NextNode(nullptr), PrevNode(nullptr)
        {
        }
 
        [[nodiscard]] const ElementType& GetValue() const
        {
            return Value;
        }
 
        [[nodiscard]] ElementType& GetValue()
        {
            return Value;
        }
 
        [[nodiscard]] TDoubleLinkedListNode* GetNextNode()
        {
            return NextNode;
        }
 
        [[nodiscard]] const TDoubleLinkedListNode* GetNextNode() const
        {
            return NextNode;
        }
 
        [[nodiscard]] TDoubleLinkedListNode* GetPrevNode()
        {
            return PrevNode;
        }
 
        [[nodiscard]] const TDoubleLinkedListNode* GetPrevNode() const
        {
            return PrevNode;
        }
 
    protected:
        ElementType            Value;
        TDoubleLinkedListNode* NextNode;
        TDoubleLinkedListNode* PrevNode;
    };
 
    typedef TDoubleLinkedListIterator<TDoubleLinkedListNode,       ElementType> TIterator;
    typedef TDoubleLinkedListIterator<TDoubleLinkedListNode, const ElementType> TConstIterator;
 
    [[nodiscard]] TDoubleLinkedList()
        : HeadNode(nullptr)
        , TailNode(nullptr)
        , ListSize(0)
    {
    }
 
    virtual ~TDoubleLinkedList()
    {
        Empty();
    }
 
    // Can't copy
    TDoubleLinkedList(const TDoubleLinkedList&) = delete;
    TDoubleLinkedList& operator=(const TDoubleLinkedList&) = delete;
 
    [[nodiscard]] TDoubleLinkedList(TDoubleLinkedList&& Other)
        : TDoubleLinkedList()
    {
        Swap(HeadNode, Other.HeadNode);
        Swap(TailNode, Other.TailNode);
        Swap(ListSize, Other.ListSize);
    }
    
    TDoubleLinkedList& operator=(TDoubleLinkedList&& Other)
    {
        Swap(HeadNode, Other.HeadNode);
        Swap(TailNode, Other.TailNode);
        Swap(ListSize, Other.ListSize);
        return *this;
    }
 
    // 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.
 
    [[nodiscard]] TDoubleLinkedListNode* GetHead() const
    {
        return HeadNode;
    }
 
    [[nodiscard]] TDoubleLinkedListNode* GetTail() const
    {
        return TailNode;
    }
 
    [[nodiscard]] TDoubleLinkedListNode* FindNode( const ElementType& InElement )
    {
        TDoubleLinkedListNode* Node = HeadNode;
        while ( Node != nullptr )
        {
            if ( Node->GetValue() == InElement )
            {
                break;
            }
 
            Node = Node->NextNode;
        }
 
        return Node;
    }
 
    [[nodiscard]] bool Contains( const ElementType& InElement )
    {
        return (FindNode(InElement) != nullptr);
    }
 
    [[nodiscard]] bool IsEmpty() const
    {
        return ListSize == 0;
    }
 
    [[nodiscard]] int32 Num() const
    {
        return ListSize;
    }
 
protected:
 
    virtual void SetListSize( int32 NewListSize )
    {
        ListSize = NewListSize;
    }
 
private:
    TDoubleLinkedListNode* HeadNode;
    TDoubleLinkedListNode* TailNode;
    int32 ListSize;
 
    [[nodiscard]] friend TIterator      begin(      TDoubleLinkedList& List) { return TIterator     (List.GetHead()); }
    [[nodiscard]] friend TConstIterator begin(const TDoubleLinkedList& List) { return TConstIterator(List.GetHead()); }
    [[nodiscard]] friend TIterator      end  (      TDoubleLinkedList& List) { return TIterator     (nullptr); }
    [[nodiscard]] 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.
 
    [[nodiscard]] TList(const ElementType &InElement, TList<ElementType>* InNext = nullptr)
    {
        Element = InElement;
        Next = InNext;
    }
};