ClassTree.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
/*=============================================================================
    ClassTree.h: Class hierarchy management classes.
=============================================================================*/
 
#pragma once
 
#include "CoreMinimal.h"
#include "UObject/Object.h"
#include "UObject/Class.h"
#include "Containers/List.h"
#include "UObject/UObjectHash.h"
#include "UObject/UObjectIterator.h"
 
enum EClassFlagMatchType
{
    MATCH_Any,
 
    MATCH_All,
};
 
class FClassTree
{
    UClass* Class;
    FClassTree* Parent;
    TArray<FClassTree*> Children;
    TDoubleLinkedList<UObject*> Instances;
 
    //@name Utility functions used for internal management of class tree
 
    bool AddChildClass( UClass* ChildClass )
    {
        check(ChildClass);
 
        // if the new class is already in the tree, don't add it again
        if ( ChildClass == Class )
            return true;
 
        // if the new class isn't a child of the current node, check to see if we need to insert
        // the new class into the tree at this node's location (i.e. the new class is actually the parent
        // of the current node's class)
        if ( !ChildClass->IsChildOf(Class) )
        {
            if ( Parent )
            {
                if ( ChildClass != Parent->GetClass() &&    // if our parent node's class is not the same as the new class
                    Class->IsChildOf(ChildClass) )          // and the new class is a parent class of this node's class
                {
                    // make the new class our parent node
                    Parent->ReplaceChild(ChildClass,this);
                    return true;
                }
            }
 
            return false;
        }
 
        // the new class belongs on this branch - find out if it belongs in any of our child nodes
        for ( int32 ChildIndex = 0; ChildIndex < Children.Num(); ChildIndex++ )
        {
            if ( Children[ChildIndex]->AddChildClass(ChildClass) )
                return 1;
        }
 
        // none of our child nodes accepted the new class - so it'll be a child of this node
        FClassTree* NewChild = new FClassTree( ChildClass );
        AddChildNode(NewChild);
        return 1;
    }
 
    int32 AddChildNode( FClassTree* NewChild )
    {
        check(NewChild);
 
        NewChild->Parent = this;
        int32 i = Children.Find(NewChild);
        if ( i == INDEX_NONE )
        {
            for ( i = 0; i < Children.Num(); i++ )
            {
                FClassTree* Child = Children[i];
 
                // insert this class sorted alphabetically
                if ( FCString::Stricmp(*Child->GetClass()->GetName(), *NewChild->GetClass()->GetName()) >= 0 )
                {
                    break;
                }
            }
 
            Children.InsertUninitialized(i);
            Children[i] = NewChild;
        }
 
        return i;
    }
 
    void ReplaceChild( UClass* NewChild, FClassTree* CurrentChild )
    {
        FClassTree* NewChildNode = new FClassTree( NewChild );
 
        // find the index of the old child
        int32 OldIndex = Children.Find(CurrentChild);
 
        // remove it from our list of children
        Children.RemoveAt(OldIndex);
 
        // then check to see if any existing children really belong under this new child
        for ( int32 ChildIndex = Children.Num() - 1; ChildIndex >= 0; ChildIndex-- )
        {
            FClassTree* ChildNode = Children[ChildIndex];
            UClass* ChildClass = ChildNode->GetClass();
            if ( ChildClass->IsChildOf(NewChild) )
            {
                // remove this class from our list of Children
                Children.RemoveAt(ChildIndex);
 
                // and insert it under the new child
                NewChildNode->AddChildNode(ChildNode);
            }
        }
 
        // add a child node for the new class
        int32 NewIndex = AddChildNode(NewChildNode);
 
        // add the old node to the new node as a child
        Children[NewIndex]->AddChildNode(CurrentChild);
    }
 
 
    FClassTree* GetNode( UClass* SearchClass, bool bBruteForce )
    {
        FClassTree* Result(NULL);
 
        if ( SearchClass == Class )
            Result = this;
 
        else if ( bBruteForce || SearchClass->IsChildOf(Class) )
        {
            for ( int32 i = 0; i < Children.Num(); i++ )
            {
                Result = Children[i]->GetNode(SearchClass,bBruteForce);
                if ( Result != NULL )
                    break;
            }
        }
 
        return Result;
    }
 
    int32 FindChildIndex( UClass* SearchClass ) const
    {
        for ( int32 i = 0; i < Children.Num(); i++ )
        {
            if ( Children[i]->GetClass() == SearchClass )
                return i;
        }
 
        return INDEX_NONE;
    }
 
 
public:
 
    void PopulateTree()
    {
        FClassTree* RootNode = GetRootNode();
        for ( TObjectIterator<UClass> It; It; ++It )
        {
            RootNode->AddClass(*It);
        }
    }
 
    bool AddClass( UClass* ChildClass )
    {
        // in order to ensure that all classes are placed into the correct locations in the tree,
        // only the root node can accept new classes
        FClassTree* ReceivingNode;
        for ( ReceivingNode = this; ReceivingNode->Parent != NULL; ReceivingNode = ReceivingNode->Parent );
 
        return ReceivingNode->AddChildClass(ChildClass);
    }
 
    UClass* GetClass() const
    {
        return Class;
    }
 
private:
    struct FScopedRecurseDepthCounter
    {
        int32* Counter;
        FScopedRecurseDepthCounter(int32* InCounter)
            : Counter(InCounter)
        {
            (*Counter)++;
        }
        ~FScopedRecurseDepthCounter()
        {
            (*Counter)--;
        }
    };
public:
 
    void GetChildClasses( TArray<FClassTree*>& ChildClasses, bool bRecurse=false )
    {
        static int32 RecurseDepth = 0;
        if (RecurseDepth == 0)
        {
            ChildClasses.Empty();
        }
        for ( int32 i = 0; i < Children.Num(); i++ )
        {
            ChildClasses.Add( Children[i] );
        }
 
        if ( bRecurse )
        {
            FScopedRecurseDepthCounter Counter(&RecurseDepth);
            for ( int32 i = 0; i < Children.Num(); i++ )
            {
                Children[i]->GetChildClasses(ChildClasses, bRecurse);
            }
        }
    }
 
    void GetChildClasses( TArray<const FClassTree*>& ChildClasses, bool bRecurse=false ) const
    {
        static int32 RecurseDepth = 0;
        if (RecurseDepth == 0)
        {
            ChildClasses.Empty();
        }
        for ( int32 i = 0; i < Children.Num(); i++ )
        {
            ChildClasses.Add( Children[i] );
        }
 
        if ( bRecurse )
        {
            FScopedRecurseDepthCounter Counter(&RecurseDepth);
            for ( int32 i = 0; i < Children.Num(); i++ )
            {
                Children[i]->GetChildClasses(ChildClasses, bRecurse);
            }
        }
    }
 
    template< class Comparator >
    void GetChildClasses( TArray<UClass*>& ChildClasses, const Comparator& Mask, bool bRecurse=false ) const
    {
        for ( int32 i = 0; i < Children.Num(); i++ )
        {
            FClassTree* ChildNode = Children[i];
            if ( Mask(ChildNode->GetClass()) )
            {
                ChildClasses.Add( ChildNode->GetClass() );
            }
 
            if ( bRecurse )
            {
                ChildNode->GetChildClasses(ChildClasses, Mask, bRecurse);
            }
        }
    }
 
    template< class Comparator >
    FClassTree* GenerateMaskedClassTree( const Comparator& Mask ) const
    {
        FClassTree* ResultTree = NULL;
        if ( Mask.IsValidClass(this) )
        {
            ResultTree = new FClassTree(Class);
            for ( int32 ChildIndex = 0; ChildIndex < Children.Num(); ChildIndex++ )
            {
                FClassTree* ChildNode = Children[ChildIndex]->GenerateMaskedClassTree(Mask);
                if ( ChildNode != NULL )
                {
                    ChildNode->Parent = ResultTree;
                    ResultTree->Children.Add(ChildNode);
                }
            }
        }
 
        return ResultTree;
    }
 
    FClassTree* GetRootNode()
    {
        FClassTree* RootNode;
        for ( RootNode = this; RootNode->Parent != NULL; RootNode = RootNode->Parent );
        return RootNode;
    }
 
    const FClassTree* GetRootNode() const
    {
        const FClassTree* RootNode;
        for ( RootNode = this; RootNode->Parent != NULL; RootNode = RootNode->Parent );
        return RootNode;
    }
 
    FClassTree* GetNode( UClass* SearchClass )
    {
        return GetNode(SearchClass,false);
    }
 
    const FClassTree* FindNode( UClass* SearchClass ) const
    {
        if ( SearchClass == Class )
            return this;
 
        if (!SearchClass->IsChildOf(Class))
            return NULL;
 
        for (auto Child : Children)
        {
            if (auto Result = Child->FindNode(SearchClass))
                return Result;
        }
 
        return NULL;
    }
 
    bool ChangeParentClass( UClass* SearchClass, UClass* InNewParentClass=NULL )
    {
        // in order to ensure that all classes are placed into the correct locations in the tree,
        // only the root node can accept new classes
        if ( Parent != NULL )
        {
            FClassTree* ReceivingNode;
            for ( ReceivingNode = this; ReceivingNode->Parent != NULL; ReceivingNode = ReceivingNode->Parent );
 
            return ReceivingNode->ChangeParentClass(SearchClass);
        }
 
        check(SearchClass);
 
        UClass* NewParentClass = InNewParentClass ? InNewParentClass : SearchClass->GetSuperClass();
 
        // find the node associated with SearchClass's new SuperClass
        FClassTree* NewParentNode = GetNode(NewParentClass);
        if (!NewParentNode)
        {
            // if that class hasn't been added yet, add it now.
            if (!AddClass(NewParentClass))
                return false;
 
            NewParentNode = GetNode(NewParentClass);
        }
        check(NewParentNode);
 
        // find the node for the class that changed SuperClass
        if (FClassTree* ClassNode = GetNode(SearchClass,true))
        {
            // if the node has an existing parent, remove it from the parent's Children array
            if (ClassNode->Parent)
            {
                ClassNode->Parent->Children.RemoveSingle(ClassNode);
            }
 
            // move the node to the new SuperClass
            return NewParentNode->AddChildNode(ClassNode) != INDEX_NONE;
        }
 
        return AddClass(SearchClass);
    }
 
 
    int32 Num() const
    {
        int32 Count = 1;
        for ( int32 i = 0; i < Children.Num(); i++ )
        {
            Count += Children[i]->Num();
        }
 
        return Count;
    }
 
    void Validate() const
    {
        if ( Parent == NULL )
        {
            // verify that we have a parent - only the UObject class is allowed to have no parents
            check(Class==UObject::StaticClass());
        }
 
        // if our parent is Object, verify that none of object's children could have been our parent
        else if ( Parent->GetClass() == UObject::StaticClass() )
        {
            TArray<const FClassTree*> ChildClasses;
            Parent->GetChildClasses(ChildClasses);
 
            for ( int32 i = 0; i < ChildClasses.Num(); i++ )
            {
                // skip ourselves
                if ( ChildClasses[i] != this )
                {
                    UClass* OtherClass = ChildClasses[i]->GetClass();
                    check(OtherClass);
 
                    // verify that the other class is not a parent of this one
                    check(!Class->IsChildOf(OtherClass));
                }
            }
        }
        else
        {
            // otherwise, our parent node should be the node for our class's parent class
            check(Class->GetSuperClass() == Parent->GetClass());
        }
    }
 
    FClassTree( UClass* BaseClass ) : Class(BaseClass), Parent(NULL)
    {
        check(Class);
    }
 
    ~FClassTree()
    {
        Class = NULL;
 
        // clear the memory allocated by this branch
        for ( int32 i = 0; i < Children.Num(); i++ )
        {
            FClassTree* p = Children[i];
            if ( p != NULL )
            {
                delete p;
            }
        }
 
        Children.Empty();
    }
 
    void DumpClassTree( int32 IndentCount, FOutputDevice& Ar )
    {
        Ar.Logf(TEXT("%s%s"), FCString::Spc(IndentCount), *Class->GetName());
        for ( int32 ChildIndex = 0; ChildIndex < Children.Num(); ChildIndex++ )
        {
            FClassTree* ChildNode = Children[ChildIndex];
            ChildNode->DumpClassTree(IndentCount + 2, Ar);
        }
    }
 
    UE_FORCEINLINE_HINT int32 NumChildren() const
    {
        return Children.Num();
    }
 
    UE_FORCEINLINE_HINT const FClassTree* GetChild(int32 Index) const
    {
        return Children[Index];
    }
};