Iterate throuh list to determine hierarchy level of elements

Question

There is a List of items which contain a field called "HierarchyLevel" (type of String) which determines the hierarchy of elements like this: Link to image. The tree structure would look like this:

<ul>
<li>1</li>
<ul>
<li>1.01</li>
<ul>
<li>1.01.01</li>
<li>1.01.02</li>
</ul>
<li>1.02</li>
<ul>
<li>1.02.01</li>
</ul>
<li>1.03</li>
</ul>
<ul>

And so on.

My goal is to implement a class which would contain the information about parent and children of each element. So far I have this class:

class TreeNode<DBItem>
{
    public DBItem Value { get; private set; }
    public List<TreeNode<DBItem>> Children = new List<TreeNode<DBItem>>();
    public TreeNode<DBItem> Parent { get; private set; }

    public string Level { get; private set; }

    public TreeNode (DBItem item, string level)
    {
        this.Value = item;
        this.Level = level;
    }

    public TreeNode<DBItem> this[int i]
    {
        get { return this.Children[i]; }
    }

    public TreeNode<DBItem> AddChild(DBItem item, string level)
    {
        TreeNode<DBItem> node = new TreeNode<DBItem>(item, level) { Parent = this };
        this.Children.Add(node);
        return node;
    }
 }

The problem is I don't quite understand how to iterate through the collection of items. I tried this:

TreeNode<DBItem> parent = new TreeNode<DBItem>(neededItems[0], "1");
foreach (var doc in neededItems)
{
    string level = doc.GetStringValue("HierarchyLevel");
    if (level.StartsWith("1.")&& level.Length < 5)
    {
        var child1 = parent.AddChild(doc, level);
        foreach (var child in neededItems)
        {
            string level1 = child.GetStringValue("HierarchyLevel");
            if (level1.StartsWith("1."+level))
            {
                child1.AddChild(child, level1);
            }
        }
    }
}

But obviously it is a bad approach. I would like to get some help and advices on how to iterate through the list correctly.

Answer 1

We can achieve this using:

• a Dictionary of all items (to help look-up parent nodes)
• a List of root nodes (in case there is more than 1 root)
• a list of DBItem objects that is ordered by hierarchy depth (1 before 1.01)

Sample implementation:

class so43271922
{
    public so43271922()
    {
    }

    [DebuggerDisplay("HierarchyLevel = {HierarchyLevel}")]
    public class DBItem
    {
        public string Name { get; private set; }
        public string HierarchyLevel { get; private set; }

        public DBItem(string name, string hierarchyLevel)
        {
            this.Name = name;
            this.HierarchyLevel = hierarchyLevel;
        }
    }

    // Dummy list of DB Item objects
    public readonly DBItem[] listItems = new DBItem[] {
        new DBItem("Element 1", "1"),
        new DBItem("Element 1.01", "1.01"),
        new DBItem("Element 1.01.01", "1.01.01"),
        new DBItem("Element 1.01.02", "1.01.02"),
        new DBItem("Element 1.02", "1.02"),
        new DBItem("Element 1.02.01", "1.02.01"),
        new DBItem("Element 1.03", "1.03")
    };

    [DebuggerDisplay("HierarchyLevel = {Value.HierarchyLevel}")]
    public class Node
    {
        public static IReadOnlyDictionary<string,Node> AllNodes { get { return allNodes; } }
        public static IReadOnlyCollection<Node> Roots { get { return roots; } }

        /// <summary>
        /// Stores references to all nodex, using HierarchyLevel as key
        /// </summary>
        private static Dictionary<string, Node> allNodes = new Dictionary<string, Node>();
        /// <summary>
        /// Stores references to root nodes
        /// </summary>
        private static List<Node> roots = new List<Node>();



        public DBItem Value { get; private set; }
        public Node Parent { get; private set; }
        public List<Node> Children { get; private set; }

        public int Level { get; private set; }

        public Node(DBItem li)
        {
            this.Children = new List<Node>();
            this.Value = li;
            allNodes.Add(li.HierarchyLevel, this);

            if (li.HierarchyLevel.Contains("."))
            {
                var parentHier = li.HierarchyLevel.Substring(0, li.HierarchyLevel.LastIndexOf("."));
                this.Parent = allNodes[parentHier];
                this.Parent.Children.Add(this);
                this.Level = this.Parent.Level + 1;
            }
            else
            {
                roots.Add(this);
                this.Parent = null;
                this.Level = 0;
            }
        }
    }

    public void generateHierarchy()
    {
        // Sort all items by: hierarchy depth, then by hierarchy level value
        var sortedItems = listItems
            .OrderBy(i => i.HierarchyLevel.Count(c => c == '.')); // 1 before 1.01

        foreach (var item in sortedItems)
        {
            new Node(item);
        }

        var hier = Node.Roots;
    }

}