How can I convert a text-file outline list into a recursive collection of objects?

Question

How can I convert this text file content into a recursive collection of objects that I can bind to a TreeView? i.e. I want to end up with a collection of 3 objects, the first one called countries which has a collection of three child objects: france, germany, italy, and so on...

ANSWER: thanks to all who helped out on this, here's my code that successfully parses this text outline into a XAML tree: http://tanguay.info/web/index.php?pg=codeExamples&id=358

countries
-france
--paris
--bordeaux
-germany
-italy
subjects
-math
--algebra
--calculus
-science
--chemistry
--biology
other
-this
-that

The code below is as far as I got it, but it is not dealing with multiple children of parents correctly.

using System;
using System.Collections.Generic;
using System.Text;

namespace TestRecursive2342
{
    class Program
    {
        static void Main(string[] args)
        {
            List<OutlineObject> outlineObjects = new List<OutlineObject>();

            //convert file contents to object collection
            List<string> lines = Helpers.GetFileAsLines();
            Stack<OutlineObject> stack = new Stack<OutlineObject>();
            foreach (var line in lines)
            {
                OutlineObject oo = new OutlineObject(line);

                if (stack.Count > 0)
                {
                    OutlineObject topObject = stack.Peek();
                    if (topObject.Indent < oo.Indent)
                    {
                        topObject.OutlineObjects.Add(oo);
                        stack.Push(oo);
                    }
                    else
                    {
                        stack.Pop();
                        stack.Push(oo);                        
                    }

                }
                else
                {
                    stack.Push(oo);
                }

                if(oo.Indent == 0)
                    outlineObjects.Add(oo);
            }

            outlineObjects.ForEach(oo => Console.WriteLine(oo.Line));

            Console.ReadLine();
        }
    }

    public class OutlineObject
    {
        public List<OutlineObject> OutlineObjects { get; set; }
        public string Line { get; set; }
        public int Indent { get; set; }

        public OutlineObject(string rawLine)
        {
            OutlineObjects = new List<OutlineObject>();
            Indent = rawLine.CountPrecedingDashes();
            Line = rawLine.Trim(new char[] { '-', ' ', '\t' });
        }
    }

    public static class Helpers
    {
        public static List<string> GetFileAsLines()
        {
            return new List<string> {
                "countries",
                "-france",
                "--paris",
                "--bordeaux",
                "-germany",
                "-italy",
                "subjects",
                "-math",
                "--algebra",
                "--calculus",
                "-science",
                "--chemistry",
                "--biology",
                "other",
                "-this",
                "-that"};
        }

        public static int CountPrecedingDashes(this string line)
        {
            int tabs = 0;
            StringBuilder sb = new StringBuilder();
            foreach (var c in line)
            {
                if (c == '-')
                    tabs++;
                else
                    break;
            }
            return tabs;
        }
    }
}

Answer 1

You should make your OutlineObject contain a list of child OutlineObjects. This way you can bind to the child collection in tree views.

Look here for an example. Or here.

---

For parsing, you should maintain a Stack<OutlineObject> of your nested objects. When you read next OutlineObject, look at the depth of the last OutlineObject in the stack. If your level is greater, you add yourself as a child of that OutlineObject, and push your OutlineObject onto the stack. If your level is the same, you remove that OutlineObject and push your object instead. If your level is bigger, you remove that top stack OutlineObject, and repeat the check.

---

Regarding your change to add

if (topObject.Indent < oo.Indent) 
{ 
  topObject.OutlineObjects.Add(oo); 
  stack.Push(oo); 
} 
else 
{ 
  stack.Pop(); 
  stack.Push(oo); 
}

...this code doesn't check for the case when the level of new object is smaller than the level of stack top. You'll need:

...
else if (topObject.Indent == oo.Indent) 
{ 
  stack.Pop(); 
  stack.Push(oo); 
} 
else 
{ 
  while (stack.Top().Indent >= oo.Indent) 
    stack.Pop(); 
  stack.Push(oo); 
}

Answer 2

Simple.

Create a list of OutlineObject objects, one for each level, these will serve as the parents.

So, the algorithm:

1. Create the object from the line
2. Find the level of indentation (which will be 0 for root objects)
3. If the list of parents has less than level+1 number of elements, add "null" elements until it has enough (which means that for the first root object, add a "null" element to make it have 1 element)
4. Replace element #level in that list with the new object you created in 1. (since the list is 0-based, the root objects will be the first ones)
5. If level is > 0, add it as a child to parents[level-1], if level == 0, add it as a root object

This should give you your tree structure. You will need to keep a child-list in each object.

Also note that the above list will need additional error checking if you want it to handle errors in the file, like this:

root
-child 1
--child 2
another root
--child 3 (note that we skipped a level)

In this case, the last child there will be added as a child of "child 1", not of "another root".

Answer 3

The Composite pattern is the first thing that comes to mind for me...

Answer 4

public class Item
{
    public string Name;
    public Item Parent;
}

List<Item> Collection = new List<Item>();

public void Main()
{
    var DataSource = data.InnerText;

    StreamReader Reader = new StreamReader(MapPath("_test2.txt"));
    int LastLevel = 0;

    while (Reader.EndOfStream == false) {
        var line = Reader.ReadLine();
        var Level = line.Where((System.Object c) => c == "-").Count;
        Item LastItem = default(Item);

        if (Collection.Count != 0) {
            LastItem = Collection.Last();
        }

        if (Level == 0) {
            Collection.Add(new Item { Name = line });
            LastLevel = 0;
        }
        else if (Level - LastLevel == 1) {
            Collection.Add(new Item { Name = line, Parent = LastItem });
            LastLevel += 1;
        }
        else if (Level == LastLevel) {
            Collection.Add(new Item { Name = line, Parent = LastItem.Parent });
        }
        else if (Level < LastLevel) {
            var LevelDiff = LastLevel - Level;
            Item Parent = LastItem;

            for (i = 0; i <= LevelDiff; i++) {
                Parent = Parent.Parent;
            }

            LastLevel = Level;
            Collection.Add(new Item { Name = line, Parent = Parent });
        }
    }

    Reader.Close();
}

This should do the trick. I tested it on your text file. There might be some bugs. Test it and tell if it works.

EDIT: Actually after further testing it turns out this does not work as expected. You need to add more logic to make it work. I leave that to you.

EDIT: After testing the code a bit more I have come to a version that works better. I still cannot guarantee that It will work under all circumstances.

Answer 5

Here's my attempt which is a combination of your original effort plus diamandiev's approach. I also added a recursive Output() method which will effectively reproduce the original input file.

Unfortunately I couldn't quite fathom the stack approach, but would be interested to see a working example.

Note that this only allows for your given example of nodes being nested 3 levels deep. Any more than that will require a modification to the else if ((oo.Indent - lastItem.Indent) < 0) check.

using System;
using System.Collections.Generic;
using System.Text;

namespace TestRecursive2342
{
    class Program
    {
        static void Main(string[] args)
        {
            List<OutlineObject> outlineObjects = new List<OutlineObject>();

            //convert file contents to object collection 
            List<string> lines = Helpers.GetFileAsLines();

            OutlineObject lastItem = new OutlineObject();
            bool processOk = true;

            foreach (var line in lines)
            {
                OutlineObject oo = new OutlineObject(line);

                if (lastItem.Indent != -1)
                {
                    if (oo.Indent == 0 && lastItem.Indent != 0)
                    {
                        // we've got a new root node item, so add the last item's top level parent to the list
                        while (lastItem.parent != null)
                            lastItem = lastItem.parent;

                        outlineObjects.Add(lastItem);
                    }
                    else if ((oo.Indent - lastItem.Indent) == 1)
                    {
                        // new item is one level lower than the last item
                        oo.parent = lastItem;
                        lastItem.OutlineObjects.Add(oo);
                    }
                    else if (oo.Indent == lastItem.Indent)
                    {
                        // new item is at the same level as the last item
                        oo.parent = lastItem.parent;
                        lastItem.parent.OutlineObjects.Add(oo);
                    }
                    else if ((oo.Indent - lastItem.Indent) < 0)
                    {
                        // new item is above the last item, but not a root node
                        // NB: this only allows for an item to be two levels above the last item
                        oo.parent = lastItem.parent.parent;
                        lastItem.parent.parent.OutlineObjects.Add(oo);
                    }
                    else if ((oo.Indent - lastItem.Indent) > 1)
                    {
                        // missing node check
                        Console.WriteLine("ERROR: missing node in input file between \"{0}\" and \"{1}\"", lastItem.Line, oo.Line);
                        processOk = false;
                        break;
                    }
                }

                lastItem = oo;
            }

            if (processOk)
            {
                // flush the last item
                while (lastItem.parent != null)
                    lastItem = lastItem.parent;

                outlineObjects.Add(lastItem);

                outlineObjects.ForEach(oo => oo.Output());
            }

            Console.ReadLine();
        }
    }

    public class OutlineObject
    {
        public OutlineObject parent { get; set; }
        public List<OutlineObject> OutlineObjects { get; set; }

        public string Line { get; set; }
        public int Indent { get; set; }

        public void Output()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append('-', this.Indent);
            sb.Append(this.Line);

            Console.WriteLine(sb);

            foreach (OutlineObject oChild in this.OutlineObjects)
            {
                oChild.Output();
            }
        }

        public OutlineObject()
        {
            parent = null;
            OutlineObjects = new List<OutlineObject>();
            Line = "";
            Indent = -1;
        }

        public OutlineObject(string rawLine)
        {
            OutlineObjects = new List<OutlineObject>();
            Indent = rawLine.CountPrecedingDashes();
            Line = rawLine.Trim(new char[] { '-', ' ', '\t' });
        }
    }

    public static class Helpers
    {
        public static List<string> GetFileAsLines()
        {
            return new List<string> { 
                "countries", 
                "-france", 
                "--paris", 
                "--bordeaux", 
                "-germany", 
                "-italy", 
                "subjects", 
                "-math", 
                "--algebra", 
                "--calculus", 
                "-science", 
                "--chemistry", 
                "--biology", 
                "other", 
                "-this", 
                "-that"};
        }

        public static int CountPrecedingDashes(this string line)
        {
            int tabs = 0;

            foreach (var c in line)
            {
                if (c == '-')
                    tabs++;
                else
                    break;
            }
            return tabs;
        }
    }
}