Introduction
 | We are investigating advanced WPF tree view implementations building on [1] and [2]. This article is about visiting nodes in a tree view, which is required to perform operations, such as: load, save, and filtering of tree view nodes. We explore this with a practical application on searching and filtering the content of a large WPF tree view. |
Background
The first two parts of the Advanced WPF tree view series [1] [2] have triggered questions about performing operations, such as, loading, saving [7], or filtering nodes on WPF tree views. These operations are indeed not trivial, because they require us to navigate a complex structure without getting lost in it. So, this article attempts to answer the question:
- "How do I perform (load, save, search etc.) operations on a WPF Tree View?"
We do this by reviewing generic algorithms to navigate a tree structure (tree traversals) and apply their offerings in practical implementations.
The study of Algorithms & Structures gives us a chance to build on mathematical facts that have been known for more than 100 years (instead of re-inventing the wheel again). This study has also the advantage that we can apply the lessons learned in more programming languages than just .Net. The article contains a Java demo version of the algorithms discussed below Download Java_TreeTraversal.zip to hint the power of that argument.
The practical .Net/WPF application at the end of this article is a way of loading about 100.000 records into a tree view and being able to search and filter that tree view quickly.
 | Index
|
The art of navigating tree structures is known as tree traversal [4]. We are concerned about ViewModels of WPF tree views that can have any shape or form. That is, we are interested in tree structures where every node can have k children with k = 0,1,2,3.... Such tree structures are known as k-ary trees. A special case of a k-ary tree is a binary tree with k=2. A special case of a binary tree (or k-ary trees) is a linked list with k=1. Algorithms on tree traversals with binary trees are well known and long established [4].
A binary tree traversal is usually classified into either a Breadth First or a Depth First ,algorithm. A Breadth First, algorithm visits direct neighbors of a node, before visiting its children, while Depth First algorithm visits the children of a node, before visiting neighboring nodes.
Next, we evaluate binary tree traversal algorithms and determine whether they can also be used to navigate k-ary trees with k>2.
The Level-Order algorithm [4] is a Breadth First search algorithms since it visits every neighboring node before navigating to a child node. The graphic animation below gives an example of this approach by navigating a tree with one root element and a total of 12 nodes.
The node with the red border indicates the node that is currently visited. All other nodes have been visited previously. The animation indicates how we can attain complete knowledge of the tree, or the relations between each parent and its children, by visiting each node from top to bottom.
The C# code below implements the requirements of the Level-Order traversal algorithm depicted in the abov animation. You can test this algorithm by downloading the Download TreeLib.zip demo and reviewing the TreeLibDemo/Development/LevelOrderV1.cs code.
public static void LevelOrderTraversal(Node root)
{
Queue<Tuple<int, Node>> queue = new Queue<Tuple<int, Node>>();
if (root != null)
queue.Enqueue(new Tuple<int, Node>(0, root));
while (queue.Count() > 0)
{
var queueItem = queue.Dequeue();
int iLevel = queueItem.Item1;
Node current = queueItem.Item2;
Console.WriteLine(string.Format("{0,4} - {1}"
, iLevel, current.GetPath()));
foreach (var item in current.Children)
queue.Enqueue(new Tuple<int, Node>(iLevel + 1, item));
}
}
Public Shared Sub LevelOrderTraversal(root As Node)
Dim queue As New Queue(Of Tuple(Of Integer, Node))()
If root IsNot Nothing Then
queue.Enqueue(New Tuple(Of Integer, Node)(0, root))
End If
While queue.Count() > 0
Dim queueItem = queue.Dequeue()
Dim iLevel As Integer = queueItem.Item1
Dim current As Node = queueItem.Item2
Console.WriteLine(String.Format("{0,4} - {1}", iLevel, current.GetPath()))
For Each item As var In current.Children
queue.Enqueue(New Tuple(Of Integer, Node)(iLevel + 1, item))
Next
End While
End Sub
public static void LevelOrderTraversal(Node root)
{
Queue<Tuple<Integer, Node>> queue = new LinkedList<Tuple<Integer, Node>>();
if (root != null)
queue.add(new Tuple<Integer, Node>(0, root));
while (queue.size() > 0)
{
Tuple<Integer, Node> queueItem = queue.remove();
int iLevel = queueItem.Item1;
Node current = queueItem.Item2;
System.out.print(String.format("%04d - %2$s\n", iLevel, current.GetPath()));
for (Node item : current.Children)
queue.add(new Tuple<Integer, Node>(iLevel + 1, item));
}
}
Being able to apply a Level-Order traversal strategy, to any tree structure, is an extremely useful tool. Because you can use this to:
- build up a structure (since the algorithm navigates from root to bottom) and it can also be used to
- convert one type of tree structure into another type of tree structure (as we show further below).
A Depth First algorithm can be classified further by the actual sequence in which they visit the current node, and their left, or right children (eg. visit right children before left children vs. visit left children before right children).
The well-known algorithms here are Pre-Order, In-Order, and Post-Order.
A Pre-Order algorithm [4] visits it's:
- current node, then
- the left children, and then
- the right children.
An k-ary tree does not have an explicit definition of a left or right child. Nonetheless, we can apply Pre-Order to k-ary trees, if we define that:
- the first child (index: 0) is the left-most child, and
- the last child (index: k-1) is the right most child.
This definition enables us to traverse children from left to right, if we are able to browse through their collection:
for(int i=0: i<Children.Count(); i++)
{
visitNode(Children[i])
}
The above definition on the left-most and right-most child is important to understand the algorithm and animation shown below.
The C# code below implements the requirements of the Pre-Order traversal algorithm. You can test this algorithm by downloading the Download TreeLib.zip demo and reviewing the TreeLibDemo/Development/PreOrderV1.cs code.
public static void PreOrder(Node root)
{
var stack = new Stack<Node>();
stack.Push(root);
while (stack.Count > 0)
{
var current = stack.Pop();
System.Console.WriteLine(current.GetPath());
for (int i = current.Children.Count - 1; i >= 0; i--)
{
stack.Push(current.Children[i]);
}
}
}
Public Shared Sub Traverse(root As Node)
Dim stack = New Stack(Of Node)()
stack.Push(root)
While stack.Count > 0
Dim current = stack.Pop()
System.Console.WriteLine(current.GetPath())
For i As Integer = current.Children.Count - 1 To 0 Step -1
stack.Push(current.Children(i))
Next
End While
End Sub
public static void PreOrder(Node root)
{
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (stack.empty() == false)
{
Node current = stack.pop();
System.out.print(current.GetPath() + "\n");
for (int i = current.Children.size() - 1; i >= 0; i--)
{
stack.push(current.Children.get(i));
}
}
}
A Pre-Order algorithm can have similar applications like the Level-Order approach since it also visits a tree from root to bottom, but with a different preference for children. So, this algorithm can be seen as an alternative to the Level-Order algorithm if it is advantageous to visit children before visiting neighboring nodes.
An In-Order algorithm [4] visits it's:
- left children, then
- the current node, and then
- the right children.
It is difficult to apply the In-Order algorithm to k-ary trees, if we assume the definition for left and right children as stated in the Level-Order section. An In-Order traversal can be implemented for k-ary trees, but it is quit involved and we just do not see a motivating need for it. Therefore, we refer to this definition and ask for feedback, if anyone knows a use case and implementation for In-Order traversal for k-ary trees.
A Post-Order algorithm [4] visits it's:
- left children, then
- the right children, and then
- the current node.
We can establish left children and right children with a similar definition as we used on the Pre-Order traversal algorithm. This time however, we have to invert the for loop to traverse the tree structure in the right order:
for(int i=Children.Count(); i>=0 0; i--)
{
visitNode(Children[i])
}
The inverted definition of left and right children is important to understand the algorithmic details shown below:
The C# code below implements the requirements of the Post-Order traversal algorithm. You can test this algorithm by downloading the Download TreeLib.zip demo and reviewing the TreeLibDemo/Development/PostOrderV1.cs code.
public static void nonRecursivePostOrder(Node root)
{
var toVisit = new Stack<Node>();
var visitedAncestors = new Stack<Node>();
toVisit.Push(root);
while (toVisit.Count > 0)
{
var node = toVisit.Peek();
if (node.Children.Count > 0)
{
if (PeekOrDefault(visitedAncestors) != node)
{
visitedAncestors.Push(node);
PushReverse(toVisit, node.Children);
continue;
}
visitedAncestors.Pop();
}
Console.WriteLine(node.GetPath());
toVisit.Pop();
}
}
private static Node PeekOrDefault(Stack<Node> s)
{
return s.Count == 0 ? null : s.Peek();
}
private static void PushReverse(Stack<Node> s, List<Node> list)
{
foreach (var l in list.ToArray().Reverse())
{
s.Push(l);
}
}
Public Shared Sub nonRecursivePostOrder(root As Node)
Dim toVisit = New Stack(Of Node)()
Dim visitedAncestors = New Stack(Of Node)()
toVisit.Push(root)
While toVisit.Count > 0
Dim node = toVisit.Peek()
If node.Children.Count > 0 Then
If PeekOrDefault(visitedAncestors) <> node Then
visitedAncestors.Push(node)
PushReverse(toVisit, node.Children)
Continue While
End If
visitedAncestors.Pop()
End If
System.Console.WriteLine(node.GetPath())
toVisit.Pop()
End While
End Sub
Private Shared Function PeekOrDefault(s As Stack(Of Node)) As Node
Return If(s.Count = 0, Nothing, s.Peek())
End Function
Private Shared Sub PushReverse(s As Stack(Of Node), list As List(Of Node))
For Each l As var In list.ToArray().Reverse()
s.Push(l)
Next
End Sub
public static void nonRecursivePostOrder(Node root)
{
Stack<Node> toVisit = new Stack<Node>();
Stack<Node> visitedAncestors = new Stack<Node>();
toVisit.push(root);
while (toVisit.empty() == false)
{
Node node = toVisit.peek();
if (node.Children.size() > 0)
{
if (PeekOrDefault(visitedAncestors) != node)
{
visitedAncestors.push(node);
PushReverse(toVisit, node.Children);
continue;
}
visitedAncestors.pop();
}
System.out.print(node.GetPath() + "\n");
toVisit.pop();
}
}
private static Node PeekOrDefault(Stack<Node> s)
{
if (s.empty() == true)
return null;
return s.peek();
}
private static void PushReverse(Stack<Node> s, List<Node> list)
{
Collections.reverse(list);
for (Node l : list)
{
s.push(l);
}
}
The Post-Order algorithm visits its deepest nodes first and travels up the tree structure until it visits the root. This seems to be of such an abstract and strange nature that is difficult to say whether it is useful or not. But it turns out that Post-Order is particularly useful for WPF, if we need an algorithm that can perform operations in an offline mode with a minimal number of changes that are visible for the UI thread.
The Post-Order traversal is important for WPF tree views, because it enables us to implement an algorithm that:
- Remove all root nodes (make them invisible),
- Evaluates the tree from it's bottom to the root, and
- Decides at each root item whether the evaluated sub-tree should be added (be visible) or not.
The above algorithm can be advantageous for WPF, because only the first and the last step require UI updates. All other operations, which might need editing of tree view items, can be performed in an off-line mode, meaning that they require no UI updates. We will review this idea in more detail in the Search for Performance section further below.
It is important to note that the Console.WriteLine statements, in the code snippets of the traversal algorithm in the previous sections, can represent any operation to be performed on the items of a tree structure (in this case "operation" means to display the tree node's content), while all the other code is required to navigate the tree.
So, one "obvious way" of re-using the above traversal algorithms would be to pass in a Generic function and replace the Console.WriteLine statement in each algorithm with a call to that Generic function (with the current node being a parameter). The TreeLibNuget application in the Download TreeLib.zip demonstrates that idea (see options 4 and 5), with a traversal method on file system directories, to compute the storage space of a folder. The generic code for the Level-Order Traversal looks like this:
public TRESULT Traverse(T root
, Func<T, IEnumerable<T>> children
, TRESULT ret
, Func<TRESULT, T, TRESULT> process
, Action<T> progress = null
, Func<TRESULT, Exception, T, TRESULT> exception = null
)
{
Queue<Tuple<int, T>> queue = new Queue<Tuple<int, T>>();
if (root != null)
queue.Enqueue(new Tuple<int, T>(0, root));
while (queue.Count() > 0)
{
var queueItem = queue.Dequeue();
int iLevel = queueItem.Item1;
T current = queueItem.Item2;
if (progress != null)
progress(current);
ret = process(ret, current);
try
{
foreach (var item in children(current))
queue.Enqueue(new Tuple<int, T>(iLevel + 1, item));
}
catch (Exception e)
{
if (exception != null)
ret = exception(ret, e, current);
}
}
return ret;
}
...and whats really cool, you can adjust the code around line 75 in DirectorySize.cs to implement any of the other traversal algorithms, and still end up with the same results, eg.:
var res = new DirSizeResult();
var Order = new PostOrder<DirSizeResult, DirectoryInfo>();
res = Order.Traverse(new DirectoryInfo(path)
, i => i.GetDirectories()
, res
, ComputeDirSize
, i => Console.Write(".")
, (i, exc, j) =>
{ Console.Write("D"); return i; }
);
The result from every traversal method is always the same, because the visited nodes are the same. What is different between each algorithm, is only the order of nodes being visited. Traversing the local file system might be efficient in any order. But the order can make a live or die difference, between useful or not, when dealing with special retreival systems (e.g. database servers) and their large data sets.
The Generic approach in the last section was just one way of re-using a tree navigation algorithm. Another way of achieving the same result, is possible through the implementation of IEnumerable/yield as we will discuss in this section.
Let us consider the code snippet below to understand why IEnumerable/yield could be advantageous in the context of tree traversals:
items = TreeLib.Depthfirst.Traverse.PostOrder(root, i => i.Children);
foreach (var item in items)
{
Console.WriteLine(item.GetPath());
}
items = TreeLib.Depthfirst.Traverse.PostOrder(root, Function(i) i.Children)
For Each item In items
Console.WriteLine(item.GetPath())
Next
The above snippet initializes a Generic traversal algorithm:
- with a given
root tree node and - a method for finding the children (
i => i.Children) of each node.
This information can then be applied in the foreach loop to traverse the tree nodes in the requested order. And changing from Post-Order to Pre-Order, -or to Level-Order traversal requires nothing else but to change the first line in the above code snippet.
An implantation of that idea is available in the TreeLib .Net Standard library (attached here but also available on GitHub and Nuget) that can be applied to many different .Net environments. This contribution optimizes the traversal further, because each node traversal is only evaluated when the foreach-client-loop asks for the next element, which is also known as lazy or laziness.
A detailed explanation of the IEnumerable/yield development is beyond the scope of this article. Please review the blog [5] by Mike Adelson to better understand how you could develop a lazy IEnumerable/yield method out of an iterative tree traversal method.
We can use lazy IEnumerable/yield algorithms to traverse in-memory structures efficiently. However, this application has its own limitations when it come to handling exceptions, as we can see when we try:
- option 4) Compute Directory Size (without exception handling in enumeration)
in the TreeLibNugetDemo application.
on a folder that contains a sub-folder where we have no access to.
It is important to note that the IEnumerable/yield algorithm in DirSizeWoException.cs will stop when it encounters an exception, such as, a folder that cannot be accessd. And the exception thrown is not being thrown in the foreach loop but in the:
var levorderItems = TreeLib.BreadthFirst.Traverse.LevelOrder(dirRoot, i => i.GetDirectories());
statement. This means we have to make sure that the i.GetDirectories() statement yields (emits) only items that can be processed without an exception (e.g.: check for access permission before yielding) or we could also use the Generic version described above to have a much more robust implementation. Either way, both implementations seem to have their own rights but their application is certainly not limited by what we can display in a WPF tree view.
The previous sections have given us insights into working with nodes (or tree view items) by visiting (traversing) each node in a defined order. We have seen demo codes and a way of traversing the folder structure in the files system. The remaining part of the article applies this know-how in the light of WPF tree views to sharpen our tools for working with tree structured data sets. To do this, we'll be reviewing the FilterTreeView project attached to this article:
This application searches a world wide database from 2012 [6] for similar strings in a structure of 3 levels (countries, regions, cities). But the implemented algorithms are generic enough that they should be applicable on any other tree structure, as well. This solution contains the following items:
- Components (Solution Folder)
- BusinessLib
- FilterTreeViewLib
- FilterTreeView
- FilterTreeViewVis
The BusinessLib contains the data model layer similar to Josh Smith's article [3], only this time, dealing with 101.908 cities, 4148 regions, and 246 countries [6]. The FilterTreeViewLib contains base class implementations that are used in the 2 demo applications. We review the 2 demo applications FilterTreeView and FilterTreeViewVis to better understand efficient ways of searching WPF tree views.
A WPF application often follows the MVVM pattern, which in turn consists of a view, viewmodel, and model data layer. A typical WPF tree view application in this context is:
- The conversion of items from Model to ViewModel (when loading data), or vice versa,
- The conversion of items from ViewModel to Model(when saving data).
This section is focused on the conversion that takes place when loading data into the ViewModel of the tree view. The animation below shows this conversion with a Model collection on the left side and a ViewModel collection on the right side. The application traverses each item in the Model collection, and adds each converted ViewModel item into the ViewModel colleciton.
The result of this conversion should be a collection of ViewModel items that can be bound to a WPF Tree View.
Let's consider the GetViewModelFromModel method of the MetaLocationViewModel class in the FilterTreeViewLib project. This method is available in 2 implementantions, where each can be activated or deactivated via a TREELIB constant that can be set or unset under:
- FilterTreeViewLib (Project) > Properties > Build > Conditional compilation symbols
The algorithm below is implemented when the TREELIB parameter is set. It converts MetaLocationModel items from the BusinessLib into MetaLocationViewModel items. This conversion takes place because the code is invoked via a call in AppViewModel.LoadSampleDataAsync() and MetaLocationRootViewModel.LoadData(...):
internal static MetaLocationViewModel GetViewModelFromModel(MetaLocationModel srcRoot)
{
if (srcRoot == null)
return null;
var srcItems = TreeLib.BreadthFirst.Traverse.LevelOrder(srcRoot, i => i.Children);
var dstIdItems = new Dictionary<int, MetaLocationViewModel>();
MetaLocationViewModel dstRoot = null;
foreach (var node in srcItems.Select(i => i.Node))
{
if (node.Parent == null)
{
dstRoot = new MetaLocationViewModel(node, null);
dstIdItems.Add(dstRoot.ID, dstRoot);
}
else
{
MetaLocationViewModel vmParentItem;
dstIdItems.TryGetValue(node.Parent.ID, out vmParentItem);
var dstNode = new MetaLocationViewModel(node, vmParentItem);
vmParentItem.ChildrenAdd(dstNode);
dstIdItems.Add(dstNode.ID, dstNode);
}
}
dstIdItems.Clear();
return dstRoot;
}
Friend Shared Function GetViewModelFromModel(ByRef srcRoot As MetaLocationModel) As MetaLocationViewModel
If srcRoot Is Nothing Then Return Nothing
Dim srcItems = TreeLib.BreadthFirst.Traverse.LevelOrder(srcRoot, Function(i) i.Children)
Dim dstIdItems = New Dictionary(Of Integer, MetaLocationViewModel)()
Dim dstRoot As MetaLocationViewModel = Nothing
For Each itemNode In srcItems
Dim node = itemNode.Node
If node.Parent Is Nothing Then
dstRoot = New MetaLocationViewModel(node, Nothing)
dstIdItems.Add(dstRoot.ID, dstRoot)
Else
Dim vmParentItem As MetaLocationViewModel = Nothing
dstIdItems.TryGetValue(node.Parent.ID, vmParentItem)
Dim dstNode = New MetaLocationViewModel(node, vmParentItem)
vmParentItem.ChildrenAdd(dstNode)
dstIdItems.Add(dstNode.ID, dstNode)
End If
Next
dstIdItems.Clear()
Return dstRoot
End Function
We can see here that the source items collections (the model items) is traversed in Level-Order (from root to bottom).
It is important to know that every item has an ID property that holds a collection wide unique identifier. This identifier is present in the ID property to unquily identify each item and it is also shown in the Parent property to hint the unique ID of the parent item.
The above observation on ID and Parent property is important because we can establish for every item:
Parent == null
- The item belongs into the root collection of items
Parent != null
- We have seen the parent item beforesince we traverse from root to bottom. So, we can look up the parent though its ID stored in the dstIdItems dictionary:
dstIdItems.TryGetValue(node.Parent.ID, out vmParentItem);
This approach determines for any item, that it is either a root item, or a child item somewhere in the collection; -searching and finding the parent item gives us a way of inserting the converted item in the correct place.
The code shown above simplifies the traversal task, because it takes advantage of the IEnumerable/Yield implementation in the TreeLib library. We can always implement this Level-Order traversal (just unset the TREELIB constant) method without using the TreeLib library (which is not that bad either):
internal static MetaLocationViewModel GetViewModelFromModel(MetaLocationModel srcRoot)
{
if (srcRoot == null)
return null;
MetaLocationViewModel dstRoot = new MetaLocationViewModel(srcRoot, null);
Queue<MetaLocationModel> srcQueue = new Queue<MetaLocationModel>();
Queue<MetaLocationViewModel> dstQueue = new Queue<MetaLocationViewModel>();
srcQueue.Enqueue(srcRoot);
dstQueue.Enqueue(dstRoot);
while (srcQueue.Count() > 0)
{
MetaLocationModel srcCurrent = srcQueue.Dequeue();
MetaLocationViewModel dstCurrent = dstQueue.Dequeue();
foreach (var item in srcCurrent.Children)
{
var dstVM = new MetaLocationViewModel(item, dstCurrent);
dstCurrent.ChildrenAddBackupNodes(dstVM);
srcQueue.Enqueue(item);
dstQueue.Enqueue(dstVM);
}
}
return dstRoot;
}
Friend Shared Function GetViewModelFromModel(ByVal srcRoot As MetaLocationModel) As MetaLocationViewModel
If srcRoot Is Nothing Then Return Nothing
Dim dstRoot As MetaLocationViewModel = New MetaLocationViewModel(srcRoot, Nothing)
Dim srcQueue As Queue(Of MetaLocationModel) = New Queue(Of MetaLocationModel)()
Dim dstQueue As Queue(Of MetaLocationViewModel) = New Queue(Of MetaLocationViewModel)()
srcQueue.Enqueue(srcRoot)
dstQueue.Enqueue(dstRoot)
While srcQueue.Count() > 0
Dim srcCurrent As MetaLocationModel = srcQueue.Dequeue()
Dim dstCurrent As MetaLocationViewModel = dstQueue.Dequeue()
For Each item In srcCurrent.Children
Dim dstVM = New MetaLocationViewModel(item, dstCurrent)
dstCurrent.ChildrenAddBackupNodes(dstVM)
srcQueue.Enqueue(item)
dstQueue.Enqueue(dstVM)
Next
End While
Return dstRoot
End Function
...but would you not agree that hiding the details of the traversal via IEnumerable/Yield gives us a better and more simplified code as we have seen in the first version of the traversal methods shown above?
Whatever version you choose, you should now be able to transfer your data collection from an in-memory collection (ViewModel items) into a collection of Model items. And your Model collection is ideally designed such that it supports persistent storage.
The above Level-Order algorithm for loading data is also applicable for saving data, since we can exchange source and destination types to convert from:
- ViewModel to Model, and store, instead of:.
- load and convert from Model to ViewModel.
The traversal algorithms that we have evaluated, so far, were applicable, because we were able to solve a problem by visiting nodes from root to bottom. The traversal problem can be a little bit more difficult, if we were required to traverse the tree, evaluate each node with some function, and do the same evaluation for the sub-tree, in order to decide whether a node, or the sub-tree in which a node lives, should be shown or not.
The above requirement can be solved efficiently by traversing a tree from bottom to root. The animation below shows how an algorithm evaluates each item in the tree and determines whether it is a match (green nodes) or a miss-match (red nodes).
- A miss-matched node or a sub-tree with only miss-matched nodes must not be visible
- A matched node or a sub-tree with a matched mode (yellow nodes) must be visible
This idea is visualized in the animation below where frame number 12 contains the result of an assumed Post-Order matching algorithm:
An implementation of the visualized algorithm is available in both sample applications:
Both search methods are non-Generic as it seemed easier at the time of development, but it should be clear by now that we could also implement these with a Generic or IEnumerable/Yield approach via the TreeLib library as discussed earlier.
Both algorithms are detailed below to explain how the work and why one of them is better than the other.
This section discusses performance details for searching WPF Tree Views with the Post-Order match algorithm discussed in the last section. Filtering the nodes of a TreeView may prove beneficial when it comes to delivering a high-quality piece of software that supports a comprehensive UX architecture. However, to perform such a feat - an individual must reevaluate the methodologies he has based on multiple standards - and performance plays a relevant role in this game.
Within this section, we will go through the properties of different approaches and discuss why one approach seems to be more efficient over another approach.
The FilterTreeViewVis application implements its search function via the DoSearch() method in the TestLocationRootViewModel class. The first föreach loop in this method makes all items visible if the search string appears to be empty or contains only 1 letter:
if (searchParams.IsSearchStringEmpty == true ||
searchParams.MinimalSearchStringLength >= searchParams.SearchString.Length)
{
foreach (var rootItem in CountryRootItems)
{
if (token.IsCancellationRequested == true)
return 0;
rootItem.IsItemVisible = true;
rootItem.SetExpand(false);
}
return 0;
}
The real search algorithm is implemented below the above code block:
int imatchCount = 0;
foreach (var rootItem in CountryRootItems)
{
if (token.IsCancellationRequested == true)
return 0;
rootItem.Match = MatchType.NoMatch;
var nodeMatchCount = MatchNodes(rootItem, searchParams);
imatchCount += nodeMatchCount;
if (searchParams.MatchSearchString(rootItem.LocalName) == true)
{
rootItem.Match = MatchType.NodeMatch;
imatchCount++;
}
if (nodeMatchCount > 0)
{
if (rootItem.Match == MatchType.NodeMatch)
rootItem.Match = MatchType.Node_AND_SubNodeMatch;
else
rootItem.Match = MatchType.SubNodeMatch;
}
if (rootItem.Match != MatchType.NoMatch)
{
if ((rootItem.Match & MatchType.SubNodeMatch) != 0)
rootItem.SetExpand(true);
else
rootItem.SetExpand(false);
rootItem.IsItemVisible = true;
}
else
rootItem.IsItemVisible = false;
}
return imatchCount;
This code looks a bit involved, but the really important item here is the MatchNode method which does the actual Post-Order match traversal on each root node and returns with a value of the MatchType enumeration to indicate whether the root node should be visible or not.
public enum MatchType
{
NoMatch = 0,
NodeMatch = 1,
SubNodeMatch = 2,
Node_AND_SubNodeMatch = 4
}
This approach implements the widely used search and filter [3] via switching the Visibility property in each ViewModel item, which in turn, adjusts the visibility in the bound view items.
Please select the FilterTreeViewVis project as start-up project and test its search function with virtualization and without virtualization (see part 2) by stating/commenting these lines in the MainWindow.xaml file to follow the discussion below:
VirtualizingStackPanel.IsVirtualizing="True"
VirtualizingStackPanel.VirtualizationMode="Recycling"
Style="{StaticResource TreeViewStyle}"
FilterTreeView Visibility Property without Virtualization
The task of hiding or showing an item in WPF is often solved via the Visibility property switch in the ViewModel and the bound View. It is, therefore, by far the most common manner of filtering a set of data that is being hosted on a WPF TreeView control [3]. As a matter of fact, we ourselves decided to go for the Visibility approach thinking that it will bestow a relevant manner of filtering the nodes of a TreeView.
But this approach was quick enough only in few typical cases where the tree view did not contain more than 500 items below any node; However, when we decided to do a stress test, we have noticed that the performance has dropped hard at around 1000 child nodes (or more) below a node.
The effect of that in-efficency is visible in a frozen UI and extremly slow interactions despite the fact that we use optimized traversal algorithms(?). Lets consider other options to see why this approach does not seem to scale out very well.
FilterTreeView Visibility Property with Virtualization
The application of virtualization [2] appears to be a fair a solution - loading and filtering seemes to be more performant than before. But this approach also fails once we triy to augment the number of items that we wanted to filter. We have remarkably noticed a slow behaviour that was accompanied with a confusion when you scroll UP/DOWN the TreeView.
The thumb of the scrollbar keeps resizing in an unstable manner, for it not being able to count the genuine number of elements within the TreeView. Such a confusion has occurred, because of the presence of several invisible items, which were being treated as rendered elements, when they were below the visible part of the scroll viewer.
Implementing the Visibility approach has proven to be inapplicable, if the number of child items, below a given node, is well beyond 500 items. We are, thus, looking into other alternatives in the next section below.
FilterTreeView BackNodes Filter without Virtualization
The DoSearch() method in MetaLocationRootViewModel class of FilterTreeView project contains an alternative solution to the previously discussed Visibility approach. The traversal algorithm used is the same and the matching function in the MetaLocationRootViewModel.MatchNodesAsync() method also implements the MatchType evumeration to model the type of match as visualized in the Post-Order Match animation. The only thing thats really different here is that we do not implement the Visibility property to hide or show an item. We are instead storing all items in a redumdant BackUpNodes collection; and add or remove an item in the Observable collection when a filter argument requires this.
In order to do that, we have decided to make an additional collection that behaves as a read-only reserved set of nodes:
These collections are not bound to the TreeView; we only use them to extract the items, which match the criteria we are looking for during our filtering process. The BackUpNodes collections can therefore, be seen as an equivalent way of retirevieng items from a backend system (e.g: database server) rather than assuming that we always have all items in-memory.
We can see an acceptable performance and a fluid UI, if we test the FiltertreeView application without virtualization. But what happens if we test this with virtualization, as well?
FilterTreeView BackNodes Filter with Virtualization
The virtualized FilterTreeView implementation also behaves smoothly even when we try to filter for many items (try to filter for 'los' with String is contained checked). The scroll bar does not miss-behave anymore, as we have seen in the virtualized variation of the Visibility property approach. All in all, using the BackUpNodes approach with the virtualization turned on seems to be the best method for scaling the number of items towards large collections (beyond 500 child items per node).
A remaining riddle to solve is this:
Why is Visibility property setting of a tree view item so slow in comparison to adding/removing nodes?
The answer to that question is that it is not very efficient to add a few thousand items in the collection just to make them invisible to the user. And whats worse still, let these items use memory and CPU usage just to find out, via binding and converter, that these should not be visible is just not the best option when dealing with large data sets.
The iterative tree traversal algorithms shown above cannot only be used confidently in a Copy & Paste manner (just replacing the Console.WriteLine with a call to a method that does the required operation on each tree node). It is also possible, to use a Generic (delegate) method parameter that we can pass into the algorithm, to re-use the traversal algorithm without having to maintain multiple redundant code bases.
The above approach with the Generic method parameter inserts pretty much any requested node operation into the tree traversal algorithm in a very flexible manner. But we can also pull the traversed items out of the algorithm by using the foreach loop discussed in the IEnumerable/yield section above. This method seems to be more advantageous, because it clearly separates the traversal algorithm from the operations performed on the tree structure. And the available implementation in the TreeLib library can be re-used in a wide range of .Net environments.
The second part of the article has shown that efficiently loading, saving, and searching data in a tree view is far from trivial, but can be achieved, if we are able to combine well-known and established algorithms with modern technology. We have realized that not using the standard Visibility property, for binding ViewModel and View items, seems to be the most efficient option when dealing with large collections in WPF.
We have shown that adding and removing items using BackupNodes is faster and scales better. This option is the fastest and most scalable way of filtering WPF Tree Views -until someone else finds a faster solution.
A way for searching for items quickly seems to be useful, but what about highlighting the items found? The problem (and some minor bugfixes) are also solved in the solution attached to this section. An explaination of how this works is given in a seperate article: A Highlightable WPF/MVVM TextBlock.
- 2017-11-27 Added Bonus Track section
- 2017-12-08 Added more VB.Net sample code
