Algorithm to index flat object list to dropdown tree?

Question

I'm having a little bit of a hard time figuring out an algorithm to index a list of string I have, to be able to order them in a tree hierarchy way.

I have an s3 bucket with thousands of files. The file's names are their path in a windows OS, for example:

root/mainfolder/folder/file.txt
root/mainfolder/folder/file1.txt
root/mainfolder/folder2/file.txt
root/mainfolder/folder3/file1.txt
root/mainfolder2/folder4/file7.txt
root/mainfolder/file.txt
....

I want to create a dropdown tree for all the files.

I will be using this template, so I have been trying to to create an object for each file with the following properties.

templateData.Value = "id";
templateData.Text = "name";
templateData.Expanded = "expanded";
templateData.HasChildren = "hasChild";
templateData.ParentValue = "pid";

My approach so far has been using the split() funtion to separate each folder and file in single strings.

item = "root/mainfolder/folder/file.txt";

string[] split = item.Split('/');

split [0] = root;
split [1] = mainfolder;
split [2] = folder;
split [3] = file.txt;

Then I iterate the split list, and create an object in a list called DropDownTree for each folder. When I get the next item in the s3 folder I would use:

(DropDownTree.FirstOrDefault(x => x.Name == split[i]) == null)

Meaning, if that folder did not existed in the DropDownTree list I am creating, I would created the object, otherwise I would just advance to the next index in the split. But is really not working and is super slow.

Which approaches are best in this case? Has anyonetried an algorithm like this?

Thank you.

score 2 · Answer 1 · answered May 15 '23 at 08:13

The first step is to parse your list of paths into a set of objects:

File objects, where each File has a Name
Directory objects, where each Directory has a collection of Files that it contains, and a collection of SubDirectories:

record Directory(string Name)
{
    public Dictionary<string, Directory> SubDirectories { get; } = new();
    public Dictionary<string, File> Files { get; } = new();
}

record File(string Name)
{
}

We'll then start with a dummy root Directory object, which contains all of the files/directories at the root:

var root = new Directory("");

We'll then go through each of the paths and split each into its parts, as you did. We'll then start walking through the parts, and walking down the directory hierarchy at the same time. So given the path a/b/c.txt, we'll start at the root directory that we created above and look for a sub-directory called a: if we don't find one, we'll create it.

We'll move down a level and look for a sub-directory called b on new Directory object for a we just found/created. Finally, we'll create a file called c.txt on the Directory object for b.

Something like:

foreach (string path in paths)
{
    var parts = path.Split('/');
    
    var currentDirectory = root;
    for (int i = 0; i < parts.Length; i++)
    {
        if (i < parts.Length - 1)
        {
            // Directory name
            if (!currentDirectory.SubDirectories.TryGetValue(parts[i], out var child))
            {
                child = new Directory(parts[i]);
                currentDirectory.SubDirectories.Add(parts[i], child);
            }
            currentDirectory = child;
        }
        else
        {
            // File name
            currentDirectory.Files.Add(parts[i], new File(parts[i]));
        }  
    }
}

Now we've got this, we can walk down it and create our template objects as necessary.

See it on SharpLab.

Thank you, it helped me to understand what I needed to do. – Joao Lima May 20 '23 at 07:23 — Joao Lima, May 20 '23 at 07:23

score 1 · Answer 2 · answered May 15 '23 at 18:48

I think it better to parse directly against the file system.

So, say this markup:

        <asp:TreeView ID="TreeView1" runat="server" ImageSet="XPFileExplorer"
            NodeIndent="15" OnTreeNodeExpanded="TreeView1_TreeNodeExpanded">
            <HoverNodeStyle Font-Underline="True" ForeColor="#6666AA" />
            <NodeStyle Font-Names="Tahoma" Font-Size="8pt" ForeColor="Black"
                HorizontalPadding="2px" NodeSpacing="0px" VerticalPadding="2px" />
            <ParentNodeStyle Font-Bold="False" />
            <SelectedNodeStyle BackColor="#B5B5B5" Font-Underline="False"
                HorizontalPadding="0px" VerticalPadding="0px" />
        </asp:TreeView>

So, our code does NOT need to be recursive.

but, we want to have a "thing" that is a folder, and in that folder we have "files", or maybe files and some folders.

So, this code works rather nice:

    string sRoot = @"c:\SERVER01";
    public class MyFolder
    {
        public FileInfo[] MyFiles;
        public DirectoryInfo[] MyFolders;
    }
    protected void Page_Load(object sender, EventArgs e)
    {
        if (!IsPostBack)
        {
            lblFolder.Text = sRoot;
            MyFolder MyFiles = GetFiles(sRoot);
            LoadTreeFiles(sRoot, MyFiles, "", null);
        }
    }

    public MyFolder GetFiles(string sRoot)

    {
        DirectoryInfo MyDir = new DirectoryInfo(sRoot); 
        MyFolder cResultFolder= new MyFolder();

        cResultFolder.MyFolders = MyDir.GetDirectories("*.*", SearchOption.TopDirectoryOnly);
        cResultFolder.MyFiles = MyDir.GetFiles("*.*", SearchOption.TopDirectoryOnly);

        return cResultFolder;
    }

    public void LoadTreeFiles(string fRootL, 
                            MyFolder lParent, 
                            string sParentID,
                            TreeNode tTreeNode)
    {
        // get all folders (if any)
        foreach (DirectoryInfo sFolder in lParent.MyFolders)
        {
            TreeNode child = new TreeNode();
            child.Text = sFolder.Name;
            child.Value = sFolder.FullName;
            child.Expanded = false;
            child.PopulateOnDemand = true;
            child.ShowCheckBox = false;

            if (sParentID == "")
                TreeView1.Nodes.Add(child);
            else
                tTreeNode.ChildNodes.Add(child);
        }
        // get all files(if any)
        foreach (FileInfo sFile in lParent.MyFiles)
        {
            TreeNode childF = new TreeNode();
            childF.Value = sFile.Name;
            childF.Value = sFile.FullName;
            childF.Expanded = false;
            childF.ShowCheckBox = true;
            childF.PopulateOnDemand = false;
            if (sParentID == "")
                TreeView1.Nodes.Add(childF);
            else
                tTreeNode.ChildNodes.Add(childF);
        }
    }

And we need one more event - the "expand" a folder bit of code.

So this:

    protected void TreeView1_TreeNodeExpanded(object sender, TreeNodeEventArgs e)
    {
        TreeNode child = e.Node;
        MyFolder dtChild = GetFiles(child.Value);
        LoadTreeFiles(child.Value, dtChild, child.Text, child);
    }

And the result is now this:

Algorithm to index flat object list to dropdown tree?

2 Answers2