Tuning Up The TreeView - Part 1

• Download the source code (requires Visual Studio 2008) - 22.43 KB

Introduction

Recently, as part of a larger project, I had occasion to dig into the WPF TreeView control. I followed what I think is the standard development process: read over some sections in my WPF books, and then went online hunting for code. As I got farther into my particular requirements and implementation, I bumped into some gnarly issues that other people were also struggling with. Some of these problems required just an "aha" moment or online tip to solve, while others sent me off into the wilderness for days. Eventually, the code got smaller and simpler, and I decided that it would be useful to give what I learned back to the community. This is the first of two articles describing how I got the TreeView to update and sort and lazy load just the way I wanted. Part 2 of this series is available here.

The Problem

My application is a tool to profile space utilization on a disk drive. I use a HierarchicalDataTemplate with a TreeView to display the directory structure, with two additional requirements:

• Color code the folders so that "hot-spots" jump out: red for the larger "hot" areas of usage; blue to represent "cold" or relatively small areas, etc.
• Provide sorting and filtering tools to make it easy to locate problem areas. In the screenshot below, the top level (Drive1) is sorted alphabetically while the second level (DirEe116) is sorted by size.

Also, although it's really an implicit user requirement, I need the tree to handle updates such as adding a new directory, deleting one, changing the size, etc. Many of the TreeView examples I looked at were display only, and I ended up spending significant time getting update to work. I should also point out that I didn't consider using a third party component or GUI builder - WPF TreeView was it for me.

WPF TreeView Control

As I began searching around for code to steal, I found several useful directory tree examples on Code Project. Sacha Barber's A Simple WPF Explorer Tree is a good, straightforward example of what I needed to do. Then I happened upon Josh Smith's great article Simplifying the WPF TreeView by Using the ViewModel Pattern. Josh's work was incredibly helpful, and much of what I do here is derived from his approach.

One of the things that comes up right away in many WPF articles is the importance of using the Model-View-ViewModel (MVVM) pattern. My experience with various commercial frameworks and libraries taught me that it is best to interface to them only from a specific layer in your application, like this:

"View" is the WPF framework, and is treated like a black box. Model is the application domain data model and logic, and shouldn't depend on (or know about) WPF. The "View/Model" is an adaptor layer that interfaces the other two. This approach keeps the application side cleaner and more focused, and provides at least some flexibility to port to a different framework later on.

TreeNode Class

The remainder of this article describes the TreeNode class, my ViewModel adaptor for the WPF TreeViewItems(TVI). In other words, all objects bound to ItemsSource through a HierarchicalDataTemplate derive from TreeNode. TreeNode has six responsibilities:

1. Serve as the abstract base class for all of the domain objects displayed in the TreeView.
2. Represent the tree hierarchy by maintaining a collection of children nodes, and a reference to the parent node. This collection of children serves two masters: the HierarchicalDataTemplate that binds to it, as well as the various tree traversal algorithms.
3. Provide the "IsExpanded" property that binds to the corresponding TVI property (Selection is sometimes included here, but I moved it out to a separate class).
4. Provide the implementation for INotifyPropertyChanged, both for the IsExpanded property, and for any properties in derived classes.
5. Provide a way to delete individual nodes or entire sub-trees.
6. Enable deferred or "lazy" loading such that a node's children aren't created until the user requests them.

I don't really have a separate application data model (other than TreeNode subclasses), so it's most convenient for me to store the tree hierarchy directly in the ViewModel. If I was getting the hierarchy from existing application data structures, then I would probably need a different ViewModel. The following sections walk through the implementation of the TreeNode class.

Tree Hierarchy: Parent and Children

The first part of TreeNode represents the tree structure:

// Alias for a generic list of TreeNodes
public class TreeNodeCol : ObservableCollection { }

public abstract class TreeNode : INotifyPropertyChanged, IEditableObject
{
   // my parent in the tree, or null if this is a root node
   private readonly TreeNode parent;
   public TreeNode Parent { get { return parent; } }

   // List of my children.
   private TreeNodeCol children;
   public virtual TreeNodeCol Children { get { return children; } }
   public int ChildrenCount { get { return Children.Count; } } //helper

   // Property that the HierarchicalDataTemplate ItemsSource binds to
   private ListCollectionView view;
   public  ListCollectionView ChildrenView { get { return view; } }

This is fairly typical for a ViewModel class. ObservableCollection is the recommended choice for collections that are a binding target, and INotifyPropertyChanged is needed to allow the UI to update.

One thing I did in this design was to move support for lazy loading to a subclass; that's the reason the Children property is virtual. Also, I explicitly create the CollectionView in this class for three reasons:

• so that I can recreate it later if the underlying collection changes
• to set up different sorting and filtering on individual item collections
• to give WPF hints that it needs to update the TreeView; IEditableObject is needed for the same reason.

These issues are explored in detail below.

In most of the TreeView examples that I looked at, and in my earlier implementations, the children collection is allocated in the constructor. It appeared that the binding from ItemSource to Children locked down the collection such that any attempt to reassign the children reference later would either display old results or throw an exception.

The reason for this became clearer once I began creating the ListCollectionView explicitly. The WPF collection view holds a reference to the children collection, so you can't just swap another collection in underneath it. That's most unfortunate because it is extremely inefficient to create a children collection for every TreeNode. If you imagine a tree with 200 nodes, probably no more that 10 or 20 get expanded, and many others are just leafs with no children. So around ninety percent of the children collection objects that get allocated are never needed or used.

But then I realized that what ItemsSource is bound to (ChildrenView in this case) is just another property, and you can change it if you notify WPF. This probably seems obvious to you, but it was a real revelation to me! This means that TreeNode can have a single empty list that all nodes share until and unless they need their own children collection, like this:

   // Empty list and view shared by all nodes that don't have children
   private static readonly TreeNodeCol emptyChildren;
   private static readonly ListCollectionView emptyView;
   static TreeNode()
   {
      emptyChildren = new TreeNodeCol();
      emptyView     = new ListCollectionView(emptyChildren);
   }

Deferring the construction of the children collection until its needed requires a bit of extra logic, which I put in two "Condition" functions. ConditionalSentinalChildren puts us in the initial state with a shared empty list; most tree nodes will remain in this state:

   // Initialize or reinitialize the children list and view
   public virtual void ConditionSentinalChildren(bool notify)
   {
      children = emptyChildren;
      view     = emptyView;
      if (notify)
         RaisePropertyChanged("ChildrenView");
   }

If a node actually has children, we call ConditionActualChildren to create its unique children collection if it hasn't been done yet:

   // Prepare the children collection and view because we now need
   // to add the children
   // expanding = true  - user requested expand - load the children
   //           = false - programmatic expand only
   protected virtual void ConditionActualChildren(bool expanding)
   {
      if (children == emptyChildren)
      {
         children = new TreeNodeCol();
         view     = new ListCollectionView(children);
         OnCreateView();
         RaisePropertyChanged("ChildrenView");
      }
   }

These functions are virtual because the subclass that handles lazy loading will have to do a little fix up. They are called from the constructor like this:

   // Create a node and hook it up to its parent
   protected TreeNode(TreeNode parent)
   {
      ConditionSentinalChildren(false);

      // hook up tree structure such that I know my parent, and
      // I'm a child of my parent.
      this.parent = parent;
      if (parent != null)
      {
         parent.ConditionActualChildren(false);
         parent.children.Add(this);
      }
   }

This is just connecting up the tree structure. ConditionActualChildren is also called during lazy loading to ensure that a particular node has a unique collection to add its children to. But I'm not handling lazy loading here: all this logic does is to avoid allocating unnecessary collections, which is a good thing.

Also, I want to point out that I'm calling a virtual function inside the constructor. This is considered bad form because we're selecting a method at run time before the object is fully baked. For example, the Visual Studio Code Analyzer (the nagger) reports a 2214 warning and says "fix it." It's safe in this case because the overridden functions are closely coordinated with TreeNode, so I left it this way.

Sorting and UI Update: IEditableObject and ListCollectionView

Data Binding is a really nice idea. You define a relationship between your data and the UI system, and the binding engine propagates changes back and fourth. But sometimes it doesn't work as expected, and either throws an exception or doesn't update, which was the problem I had.

Once I had a working TreeNode implemented, I populated the TreeView using System.IO calls to query the hard drive directory structure. DirectoryInfo.GetDirectories() politely returns the directories in alphabetical order, so I didn't realize that my tree wasn't really sorted. As soon as I implemented test functionality to rename or delete or add a directory (to simulate an update notification from a FileWatcher, for example), this problem became clear.

After searching online and rereading my WPF books, I realized that I needed to tell the ListCollectionView what to sort. The first approach that I tried was to create the SortDescriptons in XAML, and hook them up to the view using CollectionViewSource. To do this, ItemsSource first binds to the view, and then the view binds to the children collection. But there is a different collection under every tree node, so this method breaks down (see Bea Stollnitz's article here and the discussion under response number five for a detailed explanation of this).

For a while, I used CollectionView.GetDefaultView to get the view that WPF creates to attach a sort description. Once I took over creating and recreating the CollectionView, I had to change how I did sorting and filtering. These operations are all done on the CollectionView, and they have to be re-done any time it changes. So I defined a virtual notification function called OnCreateView:

   // Signal that we are creating the children list and view for this node
   //   - override to set up any needed sorting, grouping, or filtering
   protected virtual void OnCreateView() { }

TreeNode calls OnCreateView to notify its derived classes whenever it recreates the CollectionView. The derived classes override OnCreateView to hook up the appropriate sorting and filtering like this:

   protected override void OnCreateView()
   {
      ChildrenView.SortDescriptions.Add( new SortDescription( ... ) );
   }

Well, this turned out to be necessary but not sufficient: there were still times when the tree wasn't sorted. As I searched through the blogs, I read several complaints about the TreeView not updating in response to model changes. This was discouraging, since I thought the whole point of data binding was to take this update problem out of our hands. It turned out that what the TreeView needed was a little more notification.

I found the explanation in a post by Dr. WPF called ItemsControl: 'E' is for Editable Collection (is he a real doctor?). In addition to implementing INotifyPropertyChanged, which is mentioned in all the books, you have to implement IEditableObject, which isn't. If your objects aren't really transactional, you just have to mark your class with IEditableObject and provide empty implementations like I did in TreeNode:

public abstract class TreeNode : INotifyPropertyChanged, IEditableObject
   . . .
   public void BeginEdit() { }
   public void CancelEdit() { }
   public void EndEdit() { }

Then, when a TreeNode object reports a property change, it also notifies the view of the parent that contains it:

     PropertyChanged(this, new PropertyChangedEventArgs(prop));
     if (parent != null)
     {
        parent.view.EditItem(this);
        parent.view.CommitEdit();
     }

Even with these changes, I have to call view.Refresh() whenever a TreeNode expands, in order to trigger the sort, but this is the only refresh call I needed.

The good news is that the tree now updates, but the bad news is that I now have a binding error! WPF reported a Data Error 4 about the binding source for Horizontal and Vertical Content Alignment, which dazzled me since I never reference these attributes. But I was too close to give up now, so I threw this into the XAML (in two places) to fix it:

    <!-- Following style needed to avoid binding error during sort -->
    <Style TargetType="{x:Type TreeViewItem}">
        <Setter Property="HorizontalContentAlignment" Value="Left" />
        <Setter Property="VerticalContentAlignment" Value="Center" />
    </Style>

Really, sometimes I feel like WPF is just toying with me - is it supposed to be this hard? But with these changes, the TreeView stays gloriously up to date at all times. It sorts, it deletes, it slices and dices. I gather that this is somewhat of an abuse of IEditableObject, and that a future release of WPF may provide a better solution. But in the mean time, this was just the hack I was looking for.

IsExpanded, INotifyPropertyChanged, and Delete

So far, I've described how TreeNode implements requirements one and two (abstract base class and hierarchy structure), along with a side trip into view management and updating. The code for the next two requirements, the IsExpanded property and INotifyPropertyChanged implementation, was lifted pretty directly from Josh Smith's code, except for changes to deferred loading; refer to the source and the next section.

I found that requirement five (delete) was best handled with two functions, one to delete a node (self delete), and one to delete a node's children. Both functions call this recursive helper:

   private void DeleteSubtree(bool destruct)
   {
      if (destruct)
         OnDestruct();     // derived class cleanup, if any

      foreach (TreeNode kid in Children)
         kid.DeleteSubtree(true);

      view = null;
      children = null;
   }

OnDestruct is another virtual notification function that gives derived classes a chance to free up resources. And, the foreach loop is an example of using the Children collection to perform a tree traversal.

Deferred Loading

In many cases, it isn't practical to populate a tree (or list) control with all possible data, so a demand based approach is used. This becomes a ViewModel (or WPF adaptor) issue because if a TreeViewItem doesn't find any children, WPF won't display its '+' expander, and thus the user can't get to the next level.

This is such a common requirement that it's rather surprising that the TreeView doesn't support it. I suspect that Microsoft may add this in the future, but in the mean time there are two approaches that are commonly used to implement deferred loading:

• Put the lazy loading logic and properties in a new class derived from TreeView
• Add a dummy placeholder object to the children collection to trick the TreeView into always displaying the expander, and then remove the placeholder later

Subclassing the TreeView seemed like overkill to me, so I took the second approach. At the same time, I was reluctant to add more code to the TreeNode class, which is already complicated enough. So I ended up putting the lazy loading functionality in a subclass of TreeNode called TreeNodeLL.

There are several interesting aspects to this solution (see the listing below). First, I declared TreeNodeLL internal to TreeNode because it needs direct access to the hierarchy state variables. And, TreePlaceholderChild, the class for the placeholder object, is internal to TreeNodeLL. This is just to restrict its visibility, but since the children collection in TreeNode is strongly typed, the placeholder class must derive from it.

// Deferred Loading support
// - Adds a a dummy or placeholder object during construction
//   ChildrenView will include the placeholder
//
public abstract class TreeNodeLL : TreeNode
{
   // Dummy child added to the sentinel children list
   private class TreePlaceholderChild : TreeNodeLL { }
   private TreeNodeLL() { }

   private static readonly TreeNodeCol placeholderList;
   private static readonly ListCollectionView placeholderView;
   static TreeNodeLL()
   {
      placeholderList = new TreeNodeCol();
      placeholderList.Add(new TreePlaceholderChild());
      placeholderView = new ListCollectionView(placeholderList);
   }

   public override TreeNodeCol Children
   { get { return children == placeholderList ? emptyChildren : children; } }

The ability to swap out the children collection after binding is very important here as well. Rather than adding and removing placeholder objects all the time, the static constructor sets up a single placeholder list and view that are then shared by all of the childless tree nodes.

You can also see that TreeNodeLL overrides the Children property to return an empty list rather than the placeholder list. This ensures that a tree traversal of a node with no children gets an empty list.

The logic to reference the placeholder collection, and to create a new collection when needed, is in the two function overrides ConditionSentinalChildren and ConditionActualChildren. These functions are quite similar to the corresponding functions in TreeNode.

This implementation of TreeNode.TreeNodeLL satisfies our sixth and final requirement, but deriving from an internal class like this is a bit ugly, so I added this bit of syntactic sugar to make it more natural:

public abstract class TreeNodeLazy : TreeNode.TreeNodeLL
{
   protected TreeNodeLazy(TreeNode parent)
      : base(parent) { }
}

TreeNode and TreeNodeLL are tightly coupled classes by design. I would prefer that TreeNodeLL be a separate class granted 'friend' access to TreeNode, but C# doesn't support friend access. Also, you can always merge the lazy loading logic back into TreeNode to reduce this back to a single class.

But by having two classes, you can choose whether to enable deferred loading by which class, TreeNode or TreeNodeLazy, that you inherit from. And, it allows the interesting possibility of mixing both policies in the same tree, which I leave as an (ahem) exercise for the reader.

A Blind Alley

As I briefly mentioned above, when I first got the directory hierarchy to display in the TreeView, I thought I was done with it. Later, when I started working on getting it to update in response to changes to the underlying file system, I hit a wall. This was before I discovered IEditableObject or how to manipulate the view. At that point, additions to the TreeView always displayed at the end of the list rather than in sorted position, and some other updates didn't work at all.

I don't remember my exact reasoning, but in desperation I finally decided that hierarchical data binding was the problem (it was late). By gum, if that tree won't update, I'll just get down and dirty with it. So I switched over to simple data binding, and introduced a new class derived from TreeNode to manage the Items collections within TreeViewItems.

At first it seemed easy: maintain a link between my TreeNodes and WPF's TreeViewItems, and just copy my children into Items, which unlike ItemsSource, you can manipulate from code. This involves using the ItemContainerGenerator to look up TreeViewItems, and because WPF creates them at odd times, you have to listen for status changed events. One good thing about this, besides a deeper understanding of the TreeView, was that the placeholder could be a simple object added in to Items; I didn't have to pollute the children collection with it.

But that was small consolation. Even with lots of calls to Refresh, the sorting still wasn't right and my head was hurting, so I returned to this sage advice from Josh's article:

If you find yourself hooking the ItemContainerGenerator's StatusChanged event so that you can access a TreeViewItem's child items when they are eventually created, you are way off track! Trust me; it does not have to be so ugly and difficult. There is a better way!

Amen, brother, I learned my lesson. Actually I didn't even understand what Josh was talking about the first time I read that. Now, unfortunately, I do. But this failed experiment motivated me to go back to basics and get a stripped down sample working, and to write an article about it. The heavily evolved TreeNode class that I ended up with is a bit ugly and non-intuitive, but after all, the whole purpose of an adaptor class is to isolate this sort of plumbing. These two TreeNode classes end up at about 250 lines to satisfy all six of our requirements.

Next Time

In Tuning up the TreeView - Part 2, I'm going to show how we can build on TreeNode to put together a small sample application. I've included this sample project here so you can see TreeNode in context. The sample implements the sorting I described above in the problem section, as well as deferred loading and the CRUD operations.

One of my biggest mistakes was not implementing the four CRUD operations - Create, Read, Update, and Delete - early on. These basic operations, along with sorting, will immediately expose any problems you have in an implementation. Getting them to work was not so easy in my case, but having them done provides a solid foundation to build on.

I really hope that this stuff is useful to other WPF programmers. I couldn't even get to first base with WPF without great online code repositories like CodeProject. I worked out some of this implementation during the process of preparing this article, so writing for CodeProject actually improved my design. Please tell me what you think, especially if there are better solutions to these issues.

History

• February 24, 2010 - Initial version