A complex selection LINQ query

Question

I am stuck on recursive selection of the objects for TreeView.

I have some class IMenuDataSet, that stores objects, named 'I' in the List property:

public partial class IMenuDataSet
{
 private List<I> itemsField = new List<I>(); 

Each 'I' object has XDocument doc and public IT[] T properties:

public partial class I
{
 [System.Xml.Serialization.XmlIgnoreAttribute()]
 public XDocument doc;
 public IT[] T

And IT object is

public partial class IT
{
 private string nField;
 private string valueField;

IT object is a part of serialized XML, that could looks like

<?xml version="1.0" encoding="UTF-8"?>
<I c="PieMenuCategory" i="pie_menu_category" m="abc" n="someM" s="16312547127249792256">
 <T n="_collapsible">False</T>
 <T n="_display_name">0x3F70BCAA</T> 
 <T n="_parent">12342647638224932948</T>
</I>

An important note: each XML file (each IT object) has s attribute, the value of this attribute is ID of the I tag (IT object). ID of the parent element stored in T tag, that has attribute n="_parent" . Each main (top/root) hasn't such <T n="_parent"> tag.

I need to build TreeView with LINQ query, something like an example in the How to use Linq to Xml to get tree data with recursive querying?

var dataSource = (from results in ids.Items.Descendants("nodeObject")
 select new nodeObject
 {
 nodeName = results.Element("nodeName").Value.ToString(),
 nodeChildren = this.GetChilden(results)
 });

Currently, my solution is

 List<I> xi = (from c in ids.Items
 where !(
 from b in c.T.ToList()
 select b.n
 ).Contains("_parent")
 select c
 ).ToList<I>();
 foreach (I iobj in xi)
 {
 String nameId = iobj.T.ToList()
 .Where(zxc => zxc.n.Equals("_display_name"))
 .First().Value;
 uint elNameUint = Convert.ToUInt32(nameId, 16);
 String elName = translations[elNameUint];
 TreeNode treeNode = new TreeNode(elName);
 treeNode.Tag = iobj.rie.Instance;
 treeView1.Nodes.Add(treeNode);
 }
 xi = (from c in ids.Items
 where (
 from b in c.T.ToList()
 select b.n
 ).Contains("_parent")
 select c
 ).ToList<I>();
 while (xi.Count > 0)
 {
 foreach (I iobj in xi)
 {
 String nameId = iobj.T.ToList()
 .Where(zxc => zxc.n.Equals("_display_name"))
 .First().Value;
 String parentId = iobj.T.ToList()
 .Where(zxc => zxc.n.Equals("_parent"))
 .First().Value;
 uint elNameUint = Convert.ToUInt32(nameId, 16);
 String elName = translations[elNameUint];
 TreeNode treeNode = new TreeNode(elName);
 treeNode.Tag = iobj.rie.Instance;
 TreeNode ttmp = FindNode(treeView1.Nodes, parentId);
 if (ttmp != null)
 {
 ttmp.Nodes.Add(treeNode);
 xi.Remove(iobj);
 break;
 }
 }
 }
 treeView1.ExpandAll();

But I think, that my solution with breaks isn't a very clean solution and I was hoping to figure out a more elegant solution using LINQ

• jdweng: If you are doing recursion then have a recursive call to the same method. I do not like recursive methods that use the push/pop algorithm. It is like using a HP hand calculator that uses reverse polish notation. See webpage : stackoverflow.com/questions/28976601/…
• t3chb0t: This code horrible. Do you have a convention disallowing variable names longer then two characters or any other meaniningful names?

Answer 1

Don't fetishise List<>

 List<I> xi = (from c in ids.Items
 where !(
 from b in c.T.ToList()
 select b.n
 ).Contains("_parent")
 select c
 ).ToList<I>();

c.T is an array: what benefit is there to calling ToList() on it? There are two reasons for using ToList() on an enumerator: it's a lazy enumerator which you want to evaluate fully, or you need some specific method from List. Here neither of these applies.

It's not clear to me that xi needs to be eager either. I think that a first refactor could be to

 var xi = (from c in ids.Items
 where !(
 from b in c.T
 select b.n
 ).Contains("_parent")
 select c
 );

Personally I'm not a fan of the SQL-like LINQ syntax. I'd find this more readable as

 var xi = ids.Items.Where(item => !item.T.Any(t => t.n == "_parent"));

There are various other instances of the same unnecessary or even counterproductive use of ToList().

---

Learn the LINQ overloads

 String nameId = iobj.T.ToList()
 .Where(zxc => zxc.n.Equals("_display_name"))
 .First().Value;

Instead of Where(...).First() you can just use First(...):

 String nameId = iobj.T.First(zxc => zxc.n.Equals("_display_name")).Value;

---

Don't do pointless work

 while (xi.Count > 0)
 {
 foreach (I iobj in xi)
 {
 String nameId = ...;
 String parentId = ...;
 // Do a lot of work with nameId
 ...
 TreeNode ttmp = FindNode(treeView1.Nodes, parentId);
 if (ttmp != null)
 {
 ttmp.Nodes.Add(treeNode);
 xi.Remove(iobj);
 break;
 }
 }
 }

A given I instance might not find its parent until the 100th time round the outer loop, which means that 99 times it will construct a node and then hand it off to the garbage collector without it ever being needed. That's not only bad for performance: it's confusing for the maintenance programmer. Compare this rewrite:

 while (xi.Count > 0)
 {
 foreach (I iobj in xi)
 {
 String parentId = ...;
 TreeNode ttmp = FindNode(treeView1.Nodes, parentId);
 if (ttmp != null)
 {
 String nameId = ...;
 // Do a lot of work with nameId
 ...
 ttmp.Nodes.Add(treeNode);
 xi.Remove(iobj);
 break;
 }
 }
 }

---

Avoid linear time insertions, deletions, and searches where possible

E.g.

 String nameId = iobj.T.ToList()
 .Where(zxc => zxc.n.Equals("_display_name"))
 .First().Value;
 String parentId = iobj.T.ToList()
 .Where(zxc => zxc.n.Equals("_parent"))
 .First().Value;

Even rewriting that to ditch to ToList() and use First(...), it's doing multiple linear searches through the same array. I would want to investigate whether I could refactor to replace IT[] T with IDictionary<string, string> T.

If I can't, I would strongly consider introducing a local struct or class to wrap iobj, nameId, and parentId so that the search can be done once.

Then in this main loop, xi has elements at random positions selected for removal. In that case it should under no means be a List<>. ISet is far more appropriate for random removals.

FindNode isn't supplied, but I suspect that it also does a linear search. There's nothing stopping you from introducing an IDictionary<string, TreeNode> to find the parents quickly.

---

Think in parallel

(Or: a lot of the preceding was because they're important lessons, but I'm now going to recommend throwing most of the code away and rewriting from scratch).

Why is it necessary to first find the roots and then build parents? And why is it necessary to break out of the inner loop in the second half when you've found a node whose parent is already in the tree? [NB That's a rhetorical question: I know that you're doing it to avoid a concurrent modification exception, but there are standard workarounds for that which are less inefficient].

In particular, is there any reason not to structure things like this?

IDictionary<string, Tuple<I, TreeNode>> nodes = ids.Items.ToDictionary(
 item => ...,
 item => ...);
foreach (var pair in nodes.Values)
{
 if (ItemHasParent(pair.Item1))
 {
 TreeNode parentNode = ...;
 parentNode.Nodes.Add(pair.Item2);
 }
 else
 {
 treeView1.Nodes.Add(pair.Item2);
 }
}