I have a recursive data structure, such as linked list:
class Node
{
private Node next;
private int data;
// (...)
public Node Next
{
get
{
return next;
}
}
public int Data
{
get
{
return data;
}
}
}
I'd like to make a LINQ query, which starts from the head of the list and then goes through the elements, collecting data on the fly. How to do that?
Here are two helper classes I us to parse all the nodes in a TreeView control.
You might be inspired by how the yield keyword is used to adapt it for your needs.
internal static IEnumerable<TreeNode> Descendants(this TreeNodeCollection c)
{
foreach (var node in c.OfType<TreeNode>())
{
yield return node;
foreach (var child in node.Nodes.Descendants())
{
yield return child;
}
}
}
For example:
var allCheckedNodes = myTreeView.Nodes.Descendants().Where(c => c.Checked);
yield though - it simplified my code a lot!It's difficult to traverse arbitrary complex data-structures with just simple LINQ queries. At some point, you'll have to 'cut your losses' and write iterator blocks yourself - possibly only for the parts that are hard to express with standard LINQ.
That said, for your linked list example, with moreLinq, you can do:
MoreEnumerable.Generate(head, node => node.Next)
.TakeWhile(node => node != null)
If you want recursive LINQ tree traversal (or similar), it would be quite different, but here's a sample (depth-first):
private static IEnumerable<Node> GetNodeAndDescendants(Node node)
{
return new[] { node }.Concat(node.Children.SelectMany(GetNodeAndDescendants));
}
Mostly probably it is not possible using regular LINQ extensions, but one can use the following extension method:
public static IEnumerable<U> For<T, U>(this T obj, Func<T, U> extract, Func<T, bool> continueCondition, Func<T, T> step)
{
while (!continueCondition(obj))
{
yield return extract(obj);
obj = step(obj);
}
}
And from now on, you can write cool queries, like:
head.For(n => n.SomeData, n => n != null, n => n.Next)
.Select(n => n.Data)
// More LINQ here
For instance, let's sum up all even numbers from 1 to 20 (in the fancy linq-maniac way)
int sum = 1.For(n => n, n => n <= 20, n => n + 1)
.Where(n => n % 2 == 0)
.Aggregate((a, b) => a + b);
Generate. There's really no need for continueCondition since LINQ has TakeWhile, or for extract since LINQ has SelectTakeWhile every time you use it (I agree though with no need for extract). And since generally that's the most common scenario, I'd vote on keeping this one :)
List<Node>on which you want to applyLINQ, or you just have aNodeinstance which hierarchically have more instances ofNodeclass and you want to get data from all objects sequentially from head to tail?Nodeonly. If I hadList<Node>, I could simply use existingLINQextensions :)