-1

I need to build a tree from hierarchical flat collection separated by dots (.) like namespaces in C# for example. Here are some entry values as a collection (ordered):

A0.A0.A0
A1
A1.A2
A2.A3.A3.A2
A3.A2
A3.A4.A5.A3
A3.A4.A5.A4
B0.B1.B0
B1.B2
B1.B2.B3
B1.B2.B4

This collection looks like namespaces in C#. So let's assume they are namespaces (as you can understand A.A.A.A namespace is really legal).

What I need?

I need a parent-child tree from this collection like this (note, we save some space concatenating some names in one):

A0.A0.A0
A1
   A2
A2.A3.A3.A2
A3
   A2
   A4.A5        
      A3
      A4
B0.B1.B0
B1.B2
     B3
     B4

In this case we will have only 6 root objects.

Here is our interface for our algorithm:

    public interface IParentChild
    {
        IEnumerable<IParentChild> Children { get; set; }
        string FullName { get; set; }
        string Name { get; set; }
    }

Any suggestions ?

alerya
  • 3,125
  • 3
  • 28
  • 50
  • 2
    It seems your tree is not correct. A3 and A4 should be move to the right one step (from under A5) – Yacoub Massad Oct 01 '15 at 21:52
  • Does the `IParentChild` interface model the result of running the algorithm? what is the difference between `FullName` and `Name`? – Yacoub Massad Oct 01 '15 at 21:54
  • What did you try to do so far? – Yacoub Massad Oct 01 '15 at 21:54
  • 1
    do you want to generate text file ? or you want to parse from text file into collection? – M.kazem Akhgary Oct 01 '15 at 21:56
  • 1
    A2 on the 6th line should be after A3 at the 5th line I guess? – venerik Oct 01 '15 at 21:58
  • So many question. Imagine we have a list of namespaces in the project. And instead of flat view of them I wanna do simply a hierarchal view. But a little bit compressed. Some nodes could be joined together to have not so deep level. For example B1.B2 in the last row could be united. Also, may be I have some formatting errors. But the idea I hope is understandable. – alerya Oct 01 '15 at 22:37
  • Andrey is asking a question very common here at SO. Ever hovered over the vote down button? The tooltip is very enlightening. – venerik Oct 01 '15 at 22:50
  • venerik, no. It's not common. And yes I know how to search and I am asking not about how to use google and other search engine. – alerya Oct 02 '15 at 05:17

1 Answers1

1

  1. Use a Trie data structure as given in this answer Parsing one terabyte of text and efficiently counting the number of occurrences of each word

  2. Modify the Trie generation code in #1 to store namespaces

  3. Walk the Trie and output the contents to the console.

If you need more detail, comment on this and I can quickly code it.

Community
  • 1
  • 1
Clay Ver Valen
  • 1,033
  • 6
  • 10
  • You could be a little briefer. Writing: 'Simply do it' :) Actually I already have done it alone. But I like your comment. It's really genius and very helpful for every stackoverflow user. I approve it as a working solution. – alerya Oct 23 '15 at 08:08