Metainformationen zur Seite
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
|
start:visualstudio2017:programmieren:dotnetgrundlagen:tipps_tricks:searchingtreeofobjectswithlinq [2022/06/22 10:08] wikiadmin [Tree to IEnumerable<T> Extension methods] |
start:visualstudio2017:programmieren:dotnetgrundlagen:tipps_tricks:searchingtreeofobjectswithlinq [2022/06/22 10:31] (aktuell) wikiadmin [Tree to IEnumerable<T> Extension methods] |
||
|---|---|---|---|
| Zeile 22: | Zeile 22: | ||
| In breadth-first traversal, the algorithm will return all nodes at a particular depth first before considering the children at the next level. I.e. First return all the nodes from level 1, then all nodes from level 2, etc. | In breadth-first traversal, the algorithm will return all nodes at a particular depth first before considering the children at the next level. I.e. First return all the nodes from level 1, then all nodes from level 2, etc. | ||
| - | =====Tree to IEnumerable< | + | ====Tree to IEnumerable< |
| <code C# [enable_line_numbers=" | <code C# [enable_line_numbers=" | ||
| Zeile 56: | Zeile 56: | ||
| } | } | ||
| </ | </ | ||
| + | This static class provides two extension methods that can be used on any object, as long as it’s possible to express a function that returns all children of that object, i.e. the object is a node in some type of tree and has a method or property for accessing a list of its children. | ||
| - | <code C# [enable_line_numbers=" | + | ===An Example=== |
| + | |||
| + | Let’s use a hypothetical Tree model defined by this Node class: | ||
| + | <code C# [enable_line_numbers=" | ||
| public class Node | public class Node | ||
| { | { | ||
| Zeile 79: | Zeile 83: | ||
| } | } | ||
| </ | </ | ||
| + | Each node simply contains a list of children and has an Id, so that we know what node we’re looking at. The AddChild() method is a convenience method so we don’t expose the child collection and no node can ever be added as a child twice. | ||
| + | |||
| + | The calling convention for a depth-first collection is: | ||
| + | <code C# [enable_line_numbers=" | ||
| - | <code C# [enable_line_numbers=" | ||
| IEnumerable< | IEnumerable< | ||
| </ | </ | ||
| - | + | The lambda expression **n => n.Children** is the function that will return the children of a node. It simply states given n, return the value of the Children property of n. A simple test to verify that our extension works and to show us using the extension in linq looks like this: | |
| - | <code C# [enable_line_numbers=" | + | <code C# [enable_line_numbers=" |
| [Test] | [Test] | ||
| public void DepthFirst() | public void DepthFirst() | ||
| Zeile 106: | Zeile 113: | ||
| } | } | ||
| </ | </ | ||
| + | For breadth-first collections, | ||
| + | <code C# [enable_line_numbers=" | ||
| - | <code C# [enable_line_numbers=" | ||
| IEnumerable< | IEnumerable< | ||
| </ | </ | ||
| - | + | Again, we can test that the extension works like this: | |
| - | <code C# [enable_line_numbers=" | + | <code C# [enable_line_numbers=" |
| [Test] | [Test] | ||
| public void BreadthFirst() | public void BreadthFirst() | ||
| Zeile 134: | Zeile 142: | ||
| </ | </ | ||
| - | <code C# [enable_line_numbers=" | + | ===Searching Trees=== |
| - | </ | + | |
| - | <code C# [enable_line_numbers=" | + | The tree used in the example is of course extremely simple, i.e. it doesn’t even have any worthwhile data to query attached to a node. But these extension methods could be used on a node of any kind of tree, **allowing the full power of Linq, grouping, aggregation, |
| - | </code> | + | |
| + | As a final note, you may wonder, **why bother with depth-first vs. breadth first?** After all, in the end we do examine every node! There is however one particular case where the choice of algorithm can be very important: **You are looking for one match or a particular number of matches**. Since we are using yield, we can terminate the traversal at any time. Using the **FirstOrDefault()** extension on our Linq expression, the traversal would stop as soon as one match is found. And if have any knowledge where that node might be in the tree, the choice of search algorithm can be a significant performance factor. | ||
| + | |||
| + | [[http:// | ||