How can I build a directory tree from a list of paths?

I'm need to make tree structure from URLs like a sitemap. I have the URLs as a Vec<String> and want a nested hierarchy of those URLs from root to endpoint.

Example input:

"https://exapmle.com"
"https://exapmle.com/aa"
"https://exapmle.com/ab"
"https://exapmle.com/v"
"https://exapmle.com/zac"
"https://exapmle.com/zac/acf"
"https://exapmle.com/zac/acf/adr"
"https://exapmle.com/zac/axx"

Theoretical output:

UrlTree {
    root: "https://exapmle.com",
    Nodes: {
        {
            node: "aa",
            Nodes: None,
        },
        {
            node: "ab",
            Nodes: None,
        },
        {
            node: "v",
            Nodes: None,
        },
        {
            node: "zac",
            Nodes: {
                       {
                            node: "acf",
                            Nodes: {
                                       node: "adr",
                                       Nodes: None,
                                   }   
                       },
                       {
                            node: "axx",
                            Nodes: None,
                       }
                   }
        }
    }
}

Does it already exist as a crate or do I need to make it myself?

Solution

I think you will have to code something yourself. While you could use a radix trie, as mentioned by Sven Marnach, you will have the problem that it might split on a folder name and not only the /. Abc/df and abd/df would be saved as (an, c/df, d/df).

Do making something yourself, you have to ask, how big your input size will be, the length or your vec, how performant does your code need to be?

If performance is not that big of a problem then a vec of struts would be finde. On each insert just check if the current folder is already in the hashmap and add or go down a step. After you have build the structure map it to your desired output.

If you need something performant, you could implement something like the radix trie, the structure is not too hard to implement sinceyyou only have to care about splitting on "/" you could use this as inspiration https://www.cs.usfca.edu/~galles/visualization/RadixTree.html.