Structuring/organizing a linked list of filesystem folders

Question

TLDR:

I need to know how I can represent a filesystem using a linked-list struct, when the node traversal is in a weirdly reversed depth-first, alphabetical order, knowing only two things at a time:

• The full file (or folder) path, and:
• Is this node a file, or a folder?

Details:

UE4 supports built-in, cross-platform filesystem operations via IPlatformFile.
For filesystem traversal, they've included the following methods:

• IPlatformFile::IterateDirectory
• IPlatformFile::IterateDirectoryRecursively
• IPlatformFile::IterateDirectoryStat
• IPlatformFile::IterateDirectoryStatRecursively

My goal is to fill in the following structure:

struct FFolderNode
{
public:
    FFolderNode() : FFolderNode(nullptr, TEXT(""), TEXT("")) {};
    FFolderNode(const FString& Path, const FString& Name) : FFolderNode(nullptr, Path, Name) {};
    FFolderNode(FFolderNode *ParentNode, const FString& Path, const FString& Name) : ParentNode(ParentNode), Path(Path), Name(Name)
    {
        ID = FGuid::NewGuid();
    };

    // Makes it easier to identify, map & find this node
    FGuid ID;
    // The name of this directory
    FString Name;
    // The path of this directory
    FString Path;
    // The filenames this directory contains
    TArray<FString> FileNames;
    // The upwards directory (equivalent to the path "..")
    FFolderNode *ParentNode;
    // The subfolders (if any) contained within this directory
    TArray<FFolderNode*> ChildNodes;
};

The issue I'm having...
I pass my project's Contents folder path to IPlatformFile::IterateDirectory, and it does this:

Looks like alphabetical order? So I'm not sure where to start.
It seems like I need to be able to create nodes before creating & assigning their parents, and without any real prior knowledge of ownership, aside from the currently visited node being either a file or folder, and it's full path as a string.

IPlatformFile::FDirectoryVisitor::Visit is the recursive function called by IterateDirectory... The engine source seems to make an inline class which subclasses FDirectoryVisitor and overrides this method, so that's what I've done in my code:

FFolderNode UDSAssetManager::GetContentTree()
{
    static auto ContentPath = FPaths::ConvertRelativePathToFull(FPaths::GameContentDir());

    class FFolderVisitor : public IPlatformFile::FDirectoryVisitor
    {
    public:
        IPlatformFile& PlatformFile;

        FFolderVisitor(IPlatformFile& InPlatformFile) :
            PlatformFile(InPlatformFile), RootNode(nullptr), PreviousNode(nullptr),
            FolderDepth(-1), PreviousDepth(-1) {};

        FFolderNode *CreateRootNode(const FString& Path, const FString& Name)
        {
            VisitedNodes.Empty();
            if (RootNode != nullptr)
                delete RootNode; // TODO: Traverse entire tree, releasing memory for all child nodes

            TArray<FString> SubPath;
            Path.ParseIntoArray(SubPath, TEXT("/"));
            if (SubPath.Num() > 0 && SubPath[SubPath.Num() - 1] == Name)
                SubPath.RemoveAt(SubPath.Num() - 1);

            return RootNode = new FFolderNode(FString::Join(SubPath, TEXT("/")), Name);
        };

        virtual bool Visit(const TCHAR* FilenameOrDirectory, bool bIsDirectory) override
        {
            auto Path = FString(FilenameOrDirectory);
            auto Result = PlatformFile.IterateDirectory(FilenameOrDirectory, *this);

            if (RootNode == nullptr)
                return false;

            FFolderNode *ThisNode = nullptr;
            if (VisitedNodes.Num() < 1)
                ThisNode = RootNode;
            else
                ThisNode = new FFolderNode();

            auto TempPath = Path.Replace(*ContentPath, TEXT(""));
            TArray<FString> PathArray;
            TempPath.ParseIntoArray(PathArray, TEXT("/"));
            FolderDepth = PathArray.Num();

            //
            // DO SOMETHING here, even though RootNode is NOT guaranteed
            // to be the actual root of the tree... ?
            //

            PreviousNode = ThisNode;
            PreviousDepth = FolderDepth;
            VisitedNodes.Add(ThisNode);

            return true;
        };

        FORCEINLINE FFolderNode GetRootNode() const {
            if (RootNode == nullptr)
                return FFolderNode();
            return *RootNode;
        };

    private:
        FFolderNode *RootNode;
        FFolderNode *PreviousNode;
        int32 FolderDepth;
        int32 PreviousDepth;
        TArray<FFolderNode*> VisitedNodes;
    };

    FFolderVisitor FolderList(FPlatformFileManager::Get().GetPlatformFile());
    auto RootNode = FolderList.CreateRootNode(ContentPath, TEXT("Content"));
    FolderList.PlatformFile.IterateDirectory(*ContentPath, FolderList);

    return *RootNode;
}

How can I properly build a linked list with the way the engine traverses file structures?

Answer 1

It would seem that calling IterateDirectory from within FFolderVisitor::Visit is actually causing the strange order of traversal. After creating a separate method to handle initialization of the root node, and calling IterateDirectory from there instead, the traversal occurs in the correct DFS order.