c# outline numbering

Question

I am trying to develop an algorithm in C# that can take an array list of URL's and output them in an outline numbered list.

As you can imagine I need some help. Does anyone have any suggestions on the logic to use to generate this list?

Example Output:

1   - http://www.example.com/aboutus
1.2 - http://www.example.com/aboutus/page1
1.3 - http://www.example.com/aboutus/page2
1.3.1   - http://www.example.com/aboutus/page2/page3
1.3.1.1 - http://www.example.com/aboutus/page2/page3/page4
1.3.2   - http://www.example.com/aboutus/page5/page6
1.3.2.1 - http://www.example.com/aboutus/page5/page7/page9
1.3.2.2 - http://www.example.com/aboutus/page5/page8/page10

1.4 - http://www.example.com/aboutus/page10
1.4.1   - http://www.example.com/aboutus/page10/page11
1.4.2   - http://www.example.com/aboutus/page10/page12

1.1.5   - http://www.example.com/aboutus/page13

1.1.6   - http://www.example.com/aboutus/page14
1.1.6.1 - http://www.example.com/aboutus/page14/page15
1.1.6.2 - http://www.example.com/aboutus/page14/page16
1.1.6.3 - http://www.example.com/aboutus/page14/page17

... and so on

Answer 1

Take a look at the System.URI class. It should have some methods and properites that should be usefull, like the segments property that splilts the uri into its segmented parts (split by slash bascially). You could create a list of the segment arrays, sort the list, then simply iterate the list adjusting the numbers depending on wether the current list index segments match the previous list index segments.

Answer 2

You'll probably have to strip protocol and query string parameters, so +1 to the advise to use System.URI class to handle that.

As for the printing it in tree-shape - a direct approach is to use a Dictionary<string, string> to keep association of child (key) to a parent (value).

Another way is to take advantage of List<T>.Sort, e.g. like this:

public static void Print(List<string> list)
{
    var path = new Stack<string>();
    var count = new Stack<int>();
    path.Push("");
    count.Push(0);

    list.Sort(new Comparison<string>(UrlComparison));

    foreach (var x in list)
    {
        while (!x.StartsWith(path.Peek())) { path.Pop(); count.Pop(); }
        count.Push(count.Pop() + 1);
        foreach(var n in count.Reverse()) Console.Write("{0}.", n);
        Console.WriteLine(" {0}", x);
        path.Push(x);
        count.Push(0);
    }
}

Unfortunately, p.campbell is right, a custom comparison is actually required here, which makes this implementation still pretty performant, but more bulky (?:-abuse warning):

public static int UrlComparison(string x, string y)
{
    if (x == null && y == null) return 0;
    if (x == null) return -1;
    if (y == null) return 1;
    for(int n = 0; n < Math.Min(x.Length, y.Length); n++)
    {
        char cx = x[n], cy = y[n];
        if(cx == cy) continue;
        return
            (cx == '/' || cx == '.' || cx == '?') ? -1 :
            (cy == '/' || cy == '.' || cy == '?') ? 1 :
            (cx > cy) ? 1 : -1;
    }
    return (x.Length == y.Length) ? 0 : (x.Length > y.Length) ? 1 : -1;
}

PS: Just to put a disclaimer, I feel that Stacks logic is consize, but a bit more complex to understand. In a long-term project, I'd stick with a child-parent dictionary.

Answer 3

May be this Generic Tree Collection will be helpful.

There are few Tree Collections on the Code Project: one, two.