Converting table in tree

user_7592111 0
Viewed 117

Is there any scope for improvement in my program which converts flat db entity to a tree data structure. I don't want to loose the Generic flexibility as i should be able to use the same method for any other DBEntity class

Interface for db entity class

public interface IDbEntityNode
    {
         int Id { get; set; }
         int ParentId { get; set; }
    }

Example of db Entity class

 public class ExceptionCategory :IDbEntityNode
    {
        public  int Id { get; set; }
        public  int ParentId { get; set; }
        public string Data { get; set; }      
        public ExceptionCategory(string data, int id, int parentId)
        {
            Id = id;
            ParentId = parentId;
            Data = data;
        }
    }

Generic class which holds the structure of tree node

public class GenericNode<T> 
    {
        public T NodeInformation { get; set; }
        public GenericNode<T> Parent { get; set; }
        public List<GenericNode<T>> Children { get; set; } = new List<GenericNode<T>>();
    }

Method which coverts flat list to tree

public static List<GenericNode<T>> CreateGenericTree<T>(List<T> flatDataObject,Func<T,bool> IsRootNode) where T : IDbEntityNode            
        {
            var lookup = new Dictionary<int, GenericNode<T>>();
            var rootNodes = new List<GenericNode<T>>();
            var noOfElements = flatDataObject.Count;
            for (int element = 0; element < noOfElements; element++)
            {
                GenericNode<T> currentNode;
                if (lookup.TryGetValue(flatDataObject[element].Id, out currentNode))
                {
                    currentNode.NodeInformation = flatDataObject[element];
                }
                else
                {
                    currentNode = new GenericNode<T>() { NodeInformation = flatDataObject[element] };
                    lookup.Add(flatDataObject[element].Id, currentNode);
                }

                if (IsRootNode(flatDataObject[element])) 
                {
                    rootNodes.Add(currentNode);
                }
                else
                {
                    GenericNode<T> parentNode;
                    if (!lookup.TryGetValue(flatDataObject[element].ParentId, out parentNode))
                    {   
                        parentNode = new GenericNode<T>();
                        lookup.Add(flatDataObject[element].ParentId, parentNode);
                    }
                    parentNode.Children.Add(currentNode);
                    currentNode.Parent = parentNode;
                }
            }

            return rootNodes;
        }

Execution:

private static void Main(string[] args)
        {
            List<IDbEntityNode> flatDataStructure = new List<IDbEntityNode>
            {
                new ExceptionCategory("System Exception",1,0),
                new ExceptionCategory("Index out of range",2,1),
                new ExceptionCategory("Null Reference",3,1),
                new ExceptionCategory("Invalid Cast",4,1),
                new ExceptionCategory("OOM",5,1),
                new ExceptionCategory("Argument Exception",6,1),
                new ExceptionCategory("Argument Out Of Range",7,6),
                new ExceptionCategory("Argument Null",8,6),
                new ExceptionCategory("External Exception",9,1),
                new ExceptionCategory("Com",10,9),
                new ExceptionCategory("SEH",11,9),
                new ExceptionCategory("Arithmatic Exception",12,1),
                new ExceptionCategory("DivideBy0",13,12),
                new ExceptionCategory("Overflow",14,12),
            };

            var tree = CreateGenericTree(flatDataStructure, IsRootNode);
        }
 private static bool IsRootNode(IDbEntityNode dbEntity)
        {
            bool isRootNode = false;
            if (dbEntity.ParentId == 0 )
                isRootNode = true;
            return isRootNode;              
        }
tree data-structures c#
2 Answers

Created a generic approach, table objects need to follow the dbSet interface and TreeNode objects need to follow the ITreeNode. I used binarySerach to make this as fast as possible. No recursion needed. The logic ensures that you do not need to have the items in a particular order. I did not throw an error when out of the loop when there are still unassigned objects, this can be easy added.

    using System.Collections.Generic;

public interface ITreeNode
{
    string ParentId { get; set; }
    string Id { get; set; }
    dbItem item { get; set; }
    List<ITreeNode> Nodes { get; set; }
}

public class TreeNode : ITreeNode
{
    public TreeNode()
    { }

    public string ParentId { get; set; }
    public string Id { get; set; }
    public dbItem item { get; set; }
    public List<ITreeNode> Nodes { get; set; }
}

public class dbItem
{
    public string ParentId { get; set; }
    public string Id { get; set; }
    public string Name { get; set; }
}
class app
{


    static void Main()
    {
        List<dbItem> dbSet = new List<dbItem>();

        dbSet.Add(new dbItem() { Id = "5", ParentId = "1", Name = "Jan" });
        dbSet.Add(new dbItem() { Id = "25", ParentId = "1", Name = "Maria" });
        dbSet.Add(new dbItem() { Id = "1", Name = "John" });
        dbSet.Add(new dbItem() { Id = "8", ParentId = "2", Name = "Cornelis" });
        dbSet.Add(new dbItem() { Id = "2", Name = "Ilse" });
        dbSet.Add(new dbItem() { Id = "3", Name = "Nick" });
        dbSet.Add(new dbItem() { Id = "87", ParentId = "5", Name = "Rianne" });
        dbSet.Add(new dbItem() { Id = "67", ParentId = "3000", Name = "Rianne" });
        dbSet.Add(new dbItem() { Id = "3000", Name = "Max" });

        List<TreeNode> result = BuildTree<TreeNode>(dbSet);

    }

    private class ParentComparer<T> : IComparer<ITreeNode> where T: ITreeNode
    {
        public int Compare(ITreeNode x, ITreeNode y)
        {
            if (x.ParentId == null) return -1; //have the parents first
            return x.ParentId.CompareTo(y.ParentId);
        }
    }
    private class IdComparer<T> : IComparer<ITreeNode> where T : ITreeNode
    {
        public int Compare(ITreeNode x, ITreeNode y)
        {
           return x.Id.CompareTo(y.Id);
        }
    }

    static private List<T> BuildTree<T> (List<dbItem> table) where T: ITreeNode, new()
    {
        //temporary list of tree nodes to build the tree
        List<T> tmpNotAssignedNodes = new List<T>();
        List<T> tmpIdNodes = new List<T>();
        List<T> roots = new List<T>();

        IComparer<T> pc = (IComparer<T>) new ParentComparer<T>();
        IComparer<T> ic = (IComparer<T>) new IdComparer<T>();

        foreach (dbItem item in table)
        {
            T newNode = new T() { Id = item.Id, ParentId = item.ParentId, item = item };
            newNode.Nodes = new List<ITreeNode>();
            T dummySearchNode = new T() { Id = item.ParentId, ParentId = item.ParentId };

            if (string.IsNullOrEmpty(item.ParentId))
                roots.Add(newNode);
            else
            {
                int parentIndex = tmpIdNodes.BinarySearch(dummySearchNode, ic);//Get the parent
                if (parentIndex >=0)
                {
                    T parent = tmpIdNodes[parentIndex];
                    parent.Nodes.Add(newNode);
                }
                else
                {
                    parentIndex = tmpNotAssignedNodes.BinarySearch(dummySearchNode, pc);
                    if (parentIndex < 0) parentIndex = ~parentIndex;
                    tmpNotAssignedNodes.Insert(parentIndex, newNode);
                }
            }

            dummySearchNode.ParentId = newNode.Id;

            //Cleanup Unassigned
            int unAssignedChildIndex = tmpNotAssignedNodes.BinarySearch(dummySearchNode, pc);

            while (unAssignedChildIndex >= 0 && unAssignedChildIndex < tmpNotAssignedNodes.Count)
            {
                if (dummySearchNode.ParentId == tmpNotAssignedNodes[unAssignedChildIndex].ParentId)
                {
                    T child = tmpNotAssignedNodes[unAssignedChildIndex];
                    newNode.Nodes.Add(child);
                    tmpNotAssignedNodes.RemoveAt(unAssignedChildIndex);
                }
                else unAssignedChildIndex--;
            }
            int index = tmpIdNodes.BinarySearch(newNode, ic);
            tmpIdNodes.Insert(~index, newNode);

        }


        return roots;
    }
}
user_98509700

Try following solution using recursive code :

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

namespace ConsoleApplication1
{
    class Program
    {
        public static List<IDbEntityNode> flatDataStructure = null;
        public static Dictionary<int?, List<IDbEntityNode>> dict = null;
        static void Main(string[] args)
        {
            flatDataStructure = new List<IDbEntityNode>
            {
                new ExceptionCategory("System Exception",1,0),
                new ExceptionCategory("Index out of range",2,1),
                new ExceptionCategory("Null Reference",3,1),
                new ExceptionCategory("Invalid Cast",4,1),
                new ExceptionCategory("OOM",5,1),
                new ExceptionCategory("Argument Exception",6,1),
                new ExceptionCategory("Argument Out Of Range",7,6),
                new ExceptionCategory("Argument Null",8,6),
                new ExceptionCategory("External Exception",9,1),
                new ExceptionCategory("Com",10,9),
                new ExceptionCategory("SEH",11,9),
                new ExceptionCategory("Arithmatic Exception",12,1),
                new ExceptionCategory("DivideBy0",13,12),
                new ExceptionCategory("Overflow",14,12),
            };

            dict = flatDataStructure.GroupBy(x => x.ParentId, y => y)
                .ToDictionary(x => x.Key, y => y.ToList());

            GenericNode<IDbEntityNode> root = new GenericNode<IDbEntityNode>();
            root.Parent = null;
            int rootId = 0;
            root.NodeInformation.Id = rootId;
            root.NodeInformation.name = "root";
            root.NodeInformation.ParentId = null;
            CreateGenericTree(root);
        }
        public static void CreateGenericTree<T>(GenericNode<T> parent) where T : IDbEntityNode, new()
        {
            if (dict.ContainsKey(parent.NodeInformation.Id))
            {
                List<IDbEntityNode> children = dict[parent.NodeInformation.Id];
                foreach (IDbEntityNode child in children)
                {
                    GenericNode<T> newChild = new GenericNode<T>();
                    if (parent.Children == null) parent.Children = new List<GenericNode<T>>();
                    parent.Children.Add(newChild);
                    newChild.NodeInformation.Id = child.Id;
                    newChild.NodeInformation.ParentId = parent.NodeInformation.Id;
                    newChild.NodeInformation.name = child.name;
                    newChild.Parent = parent;

                    CreateGenericTree(newChild);
                }
            }
        }

    }
    public class GenericNode<T> where T : new()
    {
        public T NodeInformation = new T();
        public GenericNode<T> Parent { get; set; }
        public List<GenericNode<T>> Children { get; set; }
    }
    public class IDbEntityNode
    {
        public int Id { get; set; }
        public int? ParentId { get; set; }
        public string name { get; set; }
    }
    public class ExceptionCategory : IDbEntityNode
    {
        public string Data { get; set; }
        public ExceptionCategory(string data, int id, int parentId)
        {
            Id = id;
            ParentId = parentId;
            Data = data;
        }
    }
}
user_50152380
Related