algorithm - Build a UrlTree from Vec<String>

Question

i'm need to make url tree struct, like a sitemap. Input: Vec - list of url Expected Output: struct with nested hierarhy of url's, from root to endpoints.

Does it already existed crate or i need to make it myself?

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"
}

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,
                       }
                   }
        }
    }
}

question from:https://stackoverflow.com/questions/65879934/build-a-urltree-from-vecstring

Answer 1

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.