Yield to the power of yield

I must admit, I had never really become too comfortable with the C# ‘yield’ keyword until recently. I knew that it was introduced in C# 2.0 as a means of simplifying the creation of an enumerator. I also knew that the C# compiler interprets the code in a method that uses the yield keyword. A compiler-generated implementation of IEnumerator exists behind the scenes, which implements the logic to produce the enumerator you declared in C#. Beyond that vague understanding, I was not too familiar with it. It felt “odd” so I rarely used it.

In my ‘Simplifying the WPF TreeView by Using the ViewModel Pattern‘ article I have a demo program that lets the user search through the items in a TreeView. The search logic uses the yield keyword, as seen below:

(Click on the image to view the source code at full-size)

The article also has a demo program that lazy-loads each item’s children. That demo does not provide the ability to search. Shortly after publishing the article, two people asked how to have a lazy-loaded tree with search capabilities. Aside from the fact that performing a search that produces no matching items will force all of the items to be loaded; it is a reasonable question. I decided to implement a solution.

At the time, I misunderstood exactly how my search method used the ‘yield’ keyword. I was under the false assumption that it was executing the search logic to completion when the FindMatches method is called, and storing the results in a collection of some type. As we will see later, this is entirely untrue, but I, too, can be an idiot sometimes. 🙂

I took the load-on-demand sample and added in the ability to search the items. The UI looks like this:

Based on my misunderstanding of how a yield-based enumerator works, I thought it would have been bad to use it in this situation. Since I (incorrectly) thought that it walked down the entire data tree upon creation, performing a search with it would have forced the entire tree to be loaded into memory at once. So I thought that I had to create a custom search algorithm that would perform the search and only load as many items into memory as necessary to find the first matching item. After finding the first match, the next time I perform the search, it should only load as many items as necessary to find the next matching item. And so on, and so on…

I have plenty of experience building recursive algorithms that walk over trees, but I had never built one like this. Most recursive algorithms store their state on the callstack. Each time the recursive method is called, a new frame is pushed onto the callstack, and it keeps track of the local variable values for you. By ‘local variables’ I mean things like, the current item, the index of a for loop, the parent item to which we return after processing a sub-tree, etc.

That’s all well and good, until you need to create a recursive method that returns a value and, later on, needs to resume processing from where it left off last time it was invoked. This is exactly what I needed to build. I needed to create a recursive algorithm that stores its state in an external data structure, so that I can effectively save and load that state between executions. It was an exciting Sunday morning programming exercise, for sure!

The source code of the demo app is available at the bottom of this post. In it, you’ll find a TreeViewItemViewModelSearch.cs file. It contains all of the code involved with this implementation. That file contains a static class, TreeViewItemViewModelSearch, which contains just one public method:

The SearchResult class implements IEnumerable<TreeViewItemViewModel> and its GetEnumerator returns an instance of SearchEnumerator, which implements IEnumerator<TreeViewItemViewModel>. This search logic is invoked by the enumerator’s MoveNext method:

(Click on the image to view the source code at full size.)

The helper classes seen in that algorithm are listed below:

As it turns out, none of this is necessary at all! If you look in the TreeViewItemViewModel class, you will see how there are two implementations of the search functionality. One of them uses the very elaborate code we just saw, and the other, which works JUST AS WELL as my code, is a simple method with the ‘yield’ keyword. Click on the following image to see how both techniques are used:

As seen in the FindMatches_Yield method, all that I had to do was add in code that lazy-loads the child items before it searches them! The compiler-generated implementation of my search logic will be invoked every time the enumerator’s MoveNext is called, and it only searches for one item at a time. This is perfect for a load-on-demand scenario. If I had known about this earlier, I never would have bothered to write that custom search enumerator. But then again, it was a lot of fun and quite interesting to implement, so it’s all good!

Download the source code here: treeview_with_viewmodel_lazyload_and_search_demo Be sure to change the file extension from .DOC to .ZIP and then decompress the file.