8
\$\begingroup\$

The following function accepts a list of Topic entities, retrieved from a database using LINQ-to-Entities. Each Topic has an Id, Title and ParentId.

I want to populate an ASP.NET TreeView control, and so the function is creating a hierarchy of the Topics based on their ParentId. If a Topic has no parent, its ParentId is null and I put it under the 'root'.

public TreeNode GenerateTopicsTree(List<Topic> topics) {
  var s = new Stack<TreeNodeAndId>();
  var root = new TreeNode("Topics", "0");
  s.Push(new TreeNodeAndId { Id = null, TreeNode = root });
  while (s.Count > 0) {
    var node = s.Peek();
    var current = topics.FirstOrDefault(o => o.ParentId == node.Id);
    if (current == null) {
      s.Pop();
      continue;
    }
    var child = new TreeNode(current.Title, current.Id.ToString());
    node.TreeNode.ChildNodes.Add(child);
    s.Push(new TreeNodeAndId { Id = current.Id, TreeNode = child });
    topics.Remove(current);
  }
  return root;
}

struct TreeNodeAndId
{
  public TreeNode TreeNode;
  public int? Id;
}

Any improvements?

\$\endgroup\$
  • \$\begingroup\$ Any final solution with full source code sample application ? IMHO, better samples for minimize learning curve are real applications with full source code and good patterns \$\endgroup\$ – Kiquenet Oct 8 '14 at 13:25
5
\$\begingroup\$

Just a word of advice, creating a mutable struct which is always a bad idea. It must be a class otherwise you're just leaving yourself open to problems and confusion.

You could improve it much more if you don't restrict your methods to use lists of topics. You could then easily apply recursion here and write it in a more functional style with simpler logic.

static TreeNode GenerateTopicsTree(IEnumerable<Topic> topics)
{
    // shouldn't the root value be null?
    var root = new TreeNode("Topics", null);
    return GenerateTopicSubTree(root, topics);
}

static TreeNode GenerateTopicSubTree(TreeNode root, IEnumerable<Topic> topics)
{
    // partition the topics to child and non-child topics
    var rootId = GetId(root);
    var childTopics = topics.ToLookup(topic => topic.ParentId == rootId);

    // create and add subtrees to the current node
    var childNodes = childTopics[true].Select(GenerateNode);
    foreach (var childNode in childNodes)
    {
        root.ChildNodes.Add(GenerateTopicSubTree(childNode, childTopics[false]));
    }
    return root;
}

static int? GetId(TreeNode node)
{
    int id;
    if (Int32.TryParse(node.Value, out id))
        return id;
    return null;
}

static TreeNode GenerateNode(Topic topic)
{
    return new TreeNode(topic.Title, Convert.ToString(topic.Id));
}

Consider using data binding to create your tree instead. I don't know how it works with ASP.NET so I can't really give you tips on how to do it. But doing so should make this step unnecessary as the framework will generate the tree for you. You'll probably have to create a class to represent the topics organized in a hierarchy but you could use the above code to create that hierarchy.


After thinking about this again, I think it would be better to just group them all at once in the beginning instead of partitioning at every step. Here's an alternate implementation:

static TreeNode GenerateTopicsTreeAlt(IEnumerable<Topic> topics)
{
    var root = new TreeNode("Topics", null);

    // group all children together now so we don't need to regroup them again later
    var childTopics = topics.ToLookup(topic => topic.ParentId);
    return GenerateTopicSubTreeAlt(root, childTopics);
}

static TreeNode GenerateTopicSubTreeAlt(TreeNode root, ILookup<int?, Topic> childTopics)
{
    // create and add subtrees to the current node
    var rootId = GetId(root);
    var childNodes = childTopics[rootId].Select(GenerateNode);
    foreach (var childNode in childNodes)
    {
        root.ChildNodes.Add(GenerateTopicSubTreeAlt(childNode, childTopics));
    }
    return root;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for this. I don't know what a mutable struct is but I'll take your word for it! Out of interest, what was the problem with using a List? \$\endgroup\$ – James Oct 10 '11 at 21:45
  • \$\begingroup\$ In your example, your mutable struct was the TreeNodeAndId type. It's mutable because you could change the values of the fields. It's bad because when you read a value type, you receive a copy of the value so changes to the copy will not be applied to the actual field. As for the list, it's better to program to an interface. That way you're not restricting yourself to use a list here, but you could instead use an array for example. IList<> could be appropriate too but in this case, it really isn't necessary to access items by index. \$\endgroup\$ – Jeff Mercado Oct 10 '11 at 21:53
  • \$\begingroup\$ You're an absolute legend. I've never seen code like childTopics[true].Select(GenerateNode) before so I have learned a lot from your answer. Cheers! (By the way, I've just changed my code to yours and it compiles great.) \$\endgroup\$ – James Oct 10 '11 at 21:58
  • \$\begingroup\$ Actually, there might be a smarter way to write this. It might be easier and more efficient to just group the topics up front and create the appropriate nodes. I'll update my answer. \$\endgroup\$ – Jeff Mercado Oct 10 '11 at 22:17
  • \$\begingroup\$ Okay, thanks. In my project I have some structs that just contain value types, is that okay? Or do I need to make all the fields readonly? Or convert to a class? \$\endgroup\$ – James Oct 10 '11 at 22:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.