Introduction
We are investigating aspects of advanced WPF tree view implementations in this article. We will use the lessons learned here to enable efficient tree view applications with large data sets [10]. This investigation requires an understanding of the foundation as explained in the first part [1] of this series.
Background
The background of this article is similar to the background in [1] except that we concentrate on handling large data structures efficiently in a WPF treeview. So, here is the article to complete the picture that we started to sketch out before.
Index
The term Virtualization refers in WPF to a control design pattern that ensures efficient display and handling of a large number of data items. This pattern is available for different types of controls, such as, list views, tree views, or even a canvas control. These controls are usually based on an ItemsControl and can be used to display and manipulate a large number of items, while it is possible to virtualize an ItemsControl [2] by itself, we will concentrate here on the aspects of virtualizing a tree view [9].
Any virtualized UI solution is usually build for the use case where users would like to view and interact with a large number of items. The exact number of items considered to be large varies with the type of application (desktop, mobile, or web) and the available hardware (to mention only to important factors). The challenge is that we have much more items to display than we could ever fit on one display, let alone store at any one time in memory or even on disc. So, how do we set about working with this kind of large data sets anyway?
The classic (web) approach to virtualization is to tell the user the number of pages that is required to view all results of a search and give them a way for navigating through pages 1 through n. This approach is more implicit and less obvious for the user in WPF, because the system does not create objects for all items in the collection, but only for those that are actually visible. And this can be done for controls (view items) as well as items in the viewmodel.
The system "simply" creates only those view items that are actually visible on a user's screen (this is known as UI Virtualiszation). So, when the user adjusts the view (e.g: Scrolls) new view items that are now visible are created and old view items that are now invisible are thrown away.
All other (invisible) view items are only interesting in terms of their total count and place in the overall collection. An even more advanced solution (data virtualization - that is out of scope here) will only create a viewmodel when the corresponding view item is visible. Keeping track of that information is not easy, but a much better scalable solution than generating all items just to find out that you need a computer with infinite large memory space and processing requirements.
The UI Virtualization of a tree view is important, because it gives us one more option to look at should we actually run into performance or space problems [6][9]. But it is also important to know and understand that virtualization will change the behavior of the tree view in some ways. So, lets look at 2 attached samples to understand this in practice:
The solution in SortableObservableDictionary_VirtualizationProblems.zip is basically the same solution as in the previous article [1], except, we are now virtualizing the tree view with this XAML in MainWindow.xaml:
<Style x:Key="TreeViewStyle" TargetType={x:Type TreeView}>
<Setter Property="TreeView.Background" Value="Transparent"/>
<Setter Property="VirtualizingStackPanel.IsVirtualizing" Value="True"/>
<Setter Property="VirtualizingStackPanel.VirtualizationMode" Value="Recycling"/>
<Setter Property="TreeView.SnapsToDevicePixels" Value="True" />
<Setter Property="TreeView.OverridesDefaultStyle" Value="True" />
<Setter Property="ItemsControl.ItemsPanel">
<Setter.Value>
<ItemsPanelTemplate>
<VirtualizingStackPanel IsItemsHost="True"/>
</ItemsPanelTemplate>
</Setter.Value>
</Setter>
<Setter Property="TreeView.Template">
<Setter.Value>
<ControlTemplate TargetType="TreeView">
<ScrollViewer Focusable="False" CanContentScroll="True" Padding="3">
<ItemsPresenter HorizontalAlignment="Stretch"/>
</ScrollViewer>
</ControlTemplate>
</Setter.Value>
</Setter>
</Style>
<TreeView Grid.Row="1" DataContext="{Binding GitHub}"
ItemsSource="{Binding Root}"
behav:TreeViewSelectionChangedBehavior.ChangedCommand="{Binding SelectedItemChangedCommand}"
VirtualizingStackPanel.IsVirtualizing="True"
VirtualizingStackPanel.VirtualizationMode="Recycling"
Style="{StaticResource TreeViewStyle}"
>...
Now, when we download and try the SortableObservableDictionary_VirtualizationProblems.zip solution, we find that the rename/sort behavior is kaput, because the currently selected (renamed) item is no longer kept in the view port of the tree view.
| 1) Select one of the top items, rename it with the textbox and click Rename (button) |  |
| 2) The renamed item is updated and repositioned outside the current scroll area. |  |
| 3) Only manually scrolling down to the renamed item reveals its current position to the user. |  |
The behavior is now that the changed item still moves to the correct spot (because the observable collections still knows where it belongs), but the UI does no longer follow to its new location. This is because the bring-into-view behavior (TreeViewItemBehaviour) works only for view items (controls) that are actually in existence. But a virtualized view item is only in existence, if it is displayed or near the area of the current display.
The WPF framework is able to resolve this scenario by providing functions that can be used to force the creation of a view item based on its viewmodel [4]. The method that we need to instantiate a missing view item is:
TreeViewItem item.ItemContainerGenerator.ContainerFromIndex(index)
Then, when the above method brings the item to life we are able to bring it into view. But that function is burried deep in the depths of the UI. So, how on earth are we going to get that working while maintaining MVVM? Lets revisit the Rename process in the SortableObservableDictionary_Virtualized.zip solution to understand how this could be orchestrated.
The rename process still starts in the ICommand RenameSelectedItemCommand property of the GitHubViewModel class:
if (p is string == false)
return;
var param = p as string;
if (SelectedItem != null)
SelectedItem.Name = param;
if (CurrentlySelectedItem.Equals(default(KeyValuePair<string, GitHubItemViewModel>)) == false)
{
CurrentlySelectedItem.Value.IsItemSelected = false;
_rootItem.Children.Remove(CurrentlySelectedItem.Key);
var newItem = (GitHubItemViewModel)CurrentlySelectedItem.Value.Clone();
newItem.Name = param;
_rootItem.Children.Add(param, newItem);
object[] path = new object[2];
path[0] = _Root.First();
path[1] = _rootItem.Children.Where(kv => kv.Key == param).First();
this.SelectPathItem = path;
newItem.IsItemSelected = true;
}
The interesting thing to note here is the latest addition starting with the: object[] path = new object[2]; line. This addition creates an array of 2 items containing all path items of the path that we would like to browse. The path always has a depth of 2 here because our sample tree has only 2 levels. The statement after path[1] looks so strange, because we really need to get the KeyValuePair (not the Key or the Value) that is bound to the TreeViewItem here - a small complexity price that must be payed should you go with Dr. WPF's solution from part one [1].
So, the SelectPathItem property of the GitHubViewModel class contains eventually the (somewhat silly) complete path of 2 items to the item that we wish to bring into view:
public object[] SelectPathItem
{
get
{
return _SelectPathItem;
}
set
{
if (value != _SelectPathItem)
{
_SelectPathItem = value;
this.NotifyPropertyChanged(() => SelectPathItem);
}
}
}
The MainWindow.xaml file contains a property binding to the BringVirtualTreeViewItemIntoViewBehavior:
<i:Interaction.Behaviors>
<behav:BringVirtualTreeViewItemIntoViewBehavior SelectedItem="{Binding SelectPathItem}" />
</i:Interaction.Behaviors>
So, looking at the BringVirtualTreeViewItemIntoViewBehavior behavior's code we see now how a change in the SelectPathItem property will trigger the execution of the OnSelectedItemChanged method, which in turn contains a way of generating the required UI items if they are happen to be unavailable when we want to show them:
for (int i = 0; i < newNode.Length; i++)
{
var node = newNode[i];
var newParent = currentParent.ItemContainerGenerator.ContainerFromItem(node) as TreeViewItem;
if (newParent == null)
{
currentParent.ApplyTemplate();
var itemsPresenter = (ItemsPresenter)currentParent.Template.FindName("ItemsHost", currentParent);
if (itemsPresenter != null)
itemsPresenter.ApplyTemplate();
else
currentParent.UpdateLayout();
var virtualizingPanel = GetItemsHost(currentParent) as VirtualizingPanel;
CallEnsureGenerator(virtualizingPanel);
var index = currentParent.Items.IndexOf(node);
if (index < 0)
throw new InvalidOperationException("Node '" + node + "' cannot be fount in container");
virtualizingPanel.BringIndexIntoViewPublic(index);
newParent = currentParent.ItemContainerGenerator.ContainerFromIndex(index) as TreeViewItem;
}
if (newParent == null)
throw new InvalidOperationException("Tree view item cannot be found.");
if (node == newNode[newNode.Length-1])
{
newParent.IsSelected = true;
newParent.BringIntoView();
break;
}
if (i < newNode.Length-1)
newParent.IsExpanded = true;
currentParent = newParent;
}
The above sample is somewhat silly because we have a tree with a depth of 2 levels and use a virtual tree view :-) - nevertheless, its worthwhile the exercise since its teaching us a concept that we can use with confidence on deeper trees as we will see in our next sample LazyLoading_VirtualizedTreeViewDemo solution.
It is also worthwhile to note that an array of path items is not the only structure that could be used to bring the requested item into the view of a virtualized tree view. An alternative solution could, for instance, be a selected item that supports the Parent property discussed in the first part of this article series [1].
A bound behavior could build its own array of path items, since a browse into the root is possible though the Parent property (as shown in frames 2-6). It could then generator all path items (right side of frames 6-12) and function as it does right now.
Review [9] for more background information on virtualized tree views and optimization of tree view performance.
It is important to understand that virtualization comes at a price of more complex or sometimes even missing functionalities. We therefore, have to consciously decide whether our performance problems are so bad that we really have to virtualize or whether we rather use a normal tree with an advanced functionality and UI experience.
We know that we can improve a computer's resource usage with a virtualized tree view. A frequently used strategy in this context is to lazy load items [8], which means basically that items are loaded only when the user requests this explicitly. To do this, each item is initially displayed with an expander. A user can then discover whether an item does in fact have children, or not, by clicking on its expander:
The behavior is then to remove the expander if the item happens to have no children (see above sequence) or toggle the expander to show the previously invisible children.
The expander is displayed even if the given item does not have any children to look at. This is because finding out whether there are children or not can be a very expensive task, because of:
- the high number of children to evaluate or
- the slow data source to answer this query for each item (the file system may be slow or the connection to the database server not too fast etc).
The above behavior is referred to as lazy loading, because the computer needs that extra invitation to actually determine whether there is a child, -and then actually display it or not. The biggest benefit to be gained here is that viewmodel and view items that are not visible are not wasting local memory space and display performance.
So, lets have a look at the details of an actual implementation in the LazyLoading_VirtualizedTreeViewDemo solution. The virtualized sample tree view of that solution is defined within the FolderBrowserLib project. Its viewmodel looks like this:
Each item in the tree view is based on the TreeViewItemViewModel and every time when a tree view item is constructed this will also construct its base class which in turn constructs a so-called Dummy Child:
That is, the constructor in the ComputerViewModel class (as an example) calls its base constructor in the TreeViewItemViewModel, which in turn calls its ResetChildren method that references an instance of a dummy child item by default:
protected virtual void ResetChildren(bool lazyLoadChildren)
{
_children.Clear();
if (lazyLoadChildren == true)
_children.Add(DummyChild);
}
We can see in the TreeViewItemViewModel section that a dummy child is just one static object instance that everyone refers to by default:
static readonly IFolderBrowserViewModel DummyChild = new TreeViewItemViewModel();
This makes the process really simple and efficient. And determining whether there are real children, or only one dummy child, below a given parent, is just one comparison away as we can see in the HasDummyChild method:
public virtual bool HasDummyChild
{
get
{
if (this.Children != null)
{
if (this.Children.Count == 1)
{
if (this.Children[0] == DummyChild)
return true;
}
}
return false;
}
}
OK - now that we know how the expander appears by default, it is time to understand what happens if a user clicks on it. To implement a reaction on this, we have an attached behavior TreeViewItemExpanded in the XAML of the FolderBrowserTreeView:
<Style TargetType="{x:Type TreeViewItem}" BasedOn="{StaticResource {x:Type TreeViewItem}}">
<Setter Property="behav:TreeViewItemExpanded.Command" Value="{Binding Path=Data.ExpandCommand, Source={StaticResource DataContextProxy}}" />
<Setter Property="IsExpanded" Value="{Binding IsExpanded, Mode=TwoWay}" />
<Setter Property="IsSelected" Value="{Binding IsSelected, Mode=TwoWay, UpdateSourceTrigger=PropertyChanged}" />
<Setter Property="VerticalAlignment" Value="Center" />
<Setter Property="VerticalContentAlignment" Value="Center" />
</Style>
The TreeViewItemExpanded behavior translates the fact when an items child is expanded via the well-known BindingProxy [1] into a bound ExpandCommand of the DemoViewModel class, which happens to be the class that hosts the root of the tree and all items below it.
_ExpandCommand = new RelayCommand<object>(async (p) =>
{
var folder = p as IFolderBrowserViewModel;
if (folder == null)
return;
await folder.LoadChildrenAsync();
});
The expand command ensures that we have the correct parameter and calls the LoadChildrenAsync method of the IFolderBrowserViewModel interface, which is applicable to all item viewmodels: ComputerViewModel, DriveViewModel, and the FolderViewModel.
public async new Task<int> LoadChildrenAsync()
{
this.Children.Clear();
var folderVMItems = await FolderViewModel.LoadSubFolderAsync(_Model.Path, this);
foreach (var item in folderVMItems)
base.Children.Add(item);
return Children.Count;
}
So, lazy loading tree view items, in a nutshell, is really just referencing a default child item any time we are asked to show a real parent item. Only when the user clicks on the expander of that parent item we are evaluating for real if there is a child item below that parent or not.
Now that we can save processing costs via lazy loading we will look next at browsing tree structure, which in turn is a use case that requires us to load tree view items as fast and efficiently as we possibly can, preferably, without freezing the user interface.
The previous sections investigated some issues with virtualization and lazy loading (to keep us on the sane site of things when working with large structured data sets). In this section we are investigating an optimal approach for the use case where users want to browse to a certain path in the displayed structure of items. This task can have particularly large UI overheads, if we look at browsing to a location that is deep in the structure and has to load many children along the way. Let's consider the following data structure where we want to browse with our tree from the root to item Child 5:
+-> Root
+- Child 1
|
+- Child 2
|
+- Child 3
|
+-> Child 4
|
+-> Child 5
| | The simple way of browsing to item child 5 is to: |
 |
- Determine a current parent item (e.g. the Root) that is either already loaded or is loaded now
- Make sure the current parent has
IsExpanded=true - Load all children of the current parent item
- Set
IsSelected=true on current child (e.g. Child 1) to bring it into view - Set the current parent item to be the current child (e.g. Child 1) and
- Load and expand children in turn until the path is complete
|
The above approach is widely used and does not have too many disadvantages as long as the view is faster than the information of the child items coming in. But this game changes, if you are, for example, browsing your file system and it happens to be on a fast computer and SSD with a slower graphic sub-system. In this case you may see the UI freezing for a noticeable period of time (say a second or two). And you might wonder why, since you did all this nice async task library programming to ensure that the UI is independent of your browsing algorithm, right?
The problem here is that the UI thread is not independent of the algorithm used if you attach every new item right away and manipulate bound properties while browsing the path to its deep destination. This kind of implementation can cause a lot of UI overhead since the UI thread is constantly re-rendering areas with new information that is not even visible, because updates may come in with a faster rate than 100 ms.
Using a progress bar will not help here because the progress view will just be frozen along with the rest of the UI.
An interesting read in the context of too many updates happening too fast is the blog post by Ian Griffiths [7]. Ian suggests that we could use the Rx (Reactive Extensions) to throttle the updates that are visible for the WPF UI. While our case is related to Ian's post we can also optimize this without having to use Rx.
The first optimization can be seen if we select only the last child item instead of selecting every new child item that is created as we browse along the path. This would improve performance because the Bring-Into-View behavior would be triggered only once.
The next optimization would be to not expand every item as we go, but to expand items beginning at the last child going back to the root. This would save unnecessary UI updates because the scroller area would change only once instead of every time an item is expanded.
The above changes in the browsing algorithm will not necessarily resolve the UI freeze but make it only shorter. So, what about browsing the path and attaching the expanded items under the root when the complete (detached) sub-structure is available? It turns out that browsing offline (in the hidden) is the best way to show an animated progress without freezing. There are situations to consider here:
- Browsing to a path at load (construction) time of the tree view (eg.: a dialog opens and displays a tree view with a path already open):
- Solution: Attach a viewmodel to its view at load time only after the intial browsing has finished or
- Browsing to a path when a tree view is already loaded (constructed and visible):
- Solution: Attach only complete (detached) sub-structure when it is completely available
The first option will even work if we used the naive browsing algorithm above. But it can cause UI freezes if the tree view is already visible and we want to browse to another deep location without having to detach the complete tree (and save and restore states).
The second option will also fix the freeze at load time of the tree view. So, lets see the LazyLoading_VirtualizedTreeViewDemo.zip sample solution to understand how this can work.
The above screenshots shows the LazyLoading_VirtualizedTreeViewDemo.zip sample solution. The left screenshot shows the default and the right screenshot shows the result after clicking the Browse button. I use a SQL Server path here because it is deep enough to cause some overheads as the system has to browse into it - but you could use any other path that exists on your system to browse into it with the click of a mouse button. I use the endless progress bar below, because I found this to be a good test indicator, since it will freeze its animation, when the UI thread is blocked for the slightest notable part in time.
Clicking the Browse button invokes the BrowseCommand in the DemoViewModel class:
var path = p as string;
this.BrowserStatus = "Browsing...";
var selItem = await _ComputerInstance.BrowsePath(path);
this.SelectPathItem = selItem;
if (selItem == null)
{
this.BrowserStatus = "Target does not exist or cannot be located (make sure access is granted).";
SelectedItem = null;
}
else
{
this.BrowserStatus = "Ready.";
SelectedItem = selItem[selItem.Length - 1];
}
This command does 2 things - it completes the requested path of the children structure below the ComputerViewModel object and sets the SelectPathItem property to bring the new item into view as explained earlier in the Virtualization section.
var exists = await PathModel.DirectoryPathExistsAsync(inputPath);
if (exists == false)
return null;
var folders = PathModel.GetDirectories(inputPath);
var drive = this.FindChildByName(folders[0]);
return await NavigatePathAsync(drive, folders);
The BrowsePath method does some basic sanity checks, such as:
- Check if the target we are browsing towards, does actually appear to exist in the file system.
- Generate an array of path item strings via the
PathModel class - Start the navigation process with the Drive being the first item to confirm in the sub-structure
Then, when these basic issues are addressed and resolved the NavigatePathAsync method is executed to perform the actual browsing into the viewmodel items:
private async Task<IFolderBrowserViewModel[]> NavigatePathAsync(
IFolderBrowserViewModel parent
,string[] folders
,int iMatchIdx = 0)
{
IFolderBrowserViewModel[] pathFolders = new IFolderBrowserViewModel[folders.Count() + 1];
pathFolders[0] = this;
pathFolders[1] = parent;
IFolderBrowserViewModel dummyParent = null;
List<IFolderBrowserViewModel> dummyChildren = null;
int iNext = iMatchIdx + 1;
for (; iNext < folders.Count(); iNext++)
{
if (dummyChildren == null && dummyParent == null)
{
if (parent.HasDummyChild == true)
{
dummyParent = parent;
dummyChildren = await parent.LoadChildrenListAsync();
var nextChild = dummyChildren.SingleOrDefault(item => folders[iNext] == item.Name);
if (nextChild != null)
{
pathFolders[iNext + 1] = nextChild;
parent = nextChild;
}
}
else
{
var nextChild = parent.FindChildByName(folders[iNext]);
if (nextChild != null)
{
pathFolders[iNext + 1] = nextChild;
parent = nextChild;
}
}
}
else
{
var children = await parent.LoadChildrenAsync();
var nextChild = parent.FindChildByName(folders[iNext]);
if (nextChild != null)
{
pathFolders[iNext + 1] = nextChild;
parent = nextChild;
}
}
}
if (dummyParent != null && dummyChildren != null)
dummyParent.AddChildren(dummyChildren);
return pathFolders;
}
This code works like a zipper in the sense that it browses along the available viewmodel items structure and puts items into the pathFolders array as long as they are already there. The code executes the marked parent.HasDummyChild == true statement when the structure appears to be incomplete. This is where we continue to complete the structure with:
| |
dummyParent being the node where the track ends anddummyChildren being the nodes where we continue to browse offline.
The animation on the left side of the page tries to visualize this algorithm. The red item is the dummyParent - and the items below that item are the dummyChildren, which are not visible, until after the construction of all items below it, has taken place.
|
The code completes the missing structure below the dummyChildren node in offline mode - that is, the tree view sees nothing of it since it still sees only the dummy child below the dummyParent. This does not change until both items, dummyParent and dummyChildren, are joined with the last if statement in the listing shown above.
This article provides a foundation that should be useful when working with large structured data sets and tree views in MVVM/WPF. Typically, such data sets are already stored in some available retrieval system (eg.: the file system or a database, or a Rest API service or...). So, a data model is almost certainly granted, but a viewmodel to browse these structures efficiently in WPF, is a challenge since it is not efficient to load all items in one huge swoop.
We have reviewed Lazy Loading, Virtualization, and Efficient Browsing to provide us with a basic collection of resolutions for this type of challenge. And it should be more than obvious now that developing a virtualized treeview is a completely different story in comparison to a non-virtualized treeview.
A virtualized treeview seems to be the way to go whenever the number of items is pretty much unbounded. There is, typically no defined upper limit on the number of items and browsing still needs to be quick. The non-virtualized tree view, on the other hand, is the way to go if we look at a classical application, such as, the Project Explorer in Visual Studio.
The decision to virtualize or not has a huge impact on how the UI can be organized. But it almost always also impacts other tasks, like interacting with items, persisting data, or searching items, because these tasks may require methods that scale with the number of items, which means usually more work. But this overhead is not required for a non-virtualized tree view or a small number of items.
