The problem

As billg mentioned a while back we are in an era where we evolved “from browse to search to subscribe”. For a while, we have been used to get a few thousands matches in a blink of an eye for any query in your favorite search engine and yet it is not that obvious to filter a hierarchy based on a search input. Imagine Windows Explorer, what if you want to see only the folders that contains a particular string and their parents? How would you implement this in WPF?

The idea

I have a few rules of thumbs when it comes to developing, if my app needs to be relational I get a relational database, if it needs to communicate I use WCF, if it needs a great UI experience on a desktop application I use WPF. Well, I want to filter user input? Get myself a CollectionViewSource .

In order to be able to filter a hierarchy you need a few pre requisites:

You got to be able to walk the hierarchy both children and parent,

You got to be able to define how you want the filtering to be applied,

You got to be able to filter the visible children of any node in the hierarchy,

You got to be able to react if new children have been added

The implementation

We’ll need an interface that describes the hierarchy (parent and children), how to filter a node (with a Predicate ), if a node is filtered (to hook up to the CollectionViewSource filter delegate) as well as the VisibleChildren (children matching the filtering criteria). The later will be bound to the treeview with a HierarchicalDataTemplate.

Here is the resulting interface:

public interface IFilterableHierarchicalData bool HasChildren { get; } ObservableCollection InternalChildren { get; } ICollectionView VisibleChildren { get; } IFilterableHierarchicalData Parent { get; set; } IEnumerable GetAllChildren(); IEnumerable GetVisibleChildren(); IEnumerable GetAncestors(); Predicate FilterPredicate { get; } bool IsFilteredOut { get; set; }

Obviously, interface won’t do much as is, you need an implementation. Luckily enough, we can provide a default one that will cover the scenario. We’ll make it abstract so we can provide concrete implementation based on data objects later on.

One trick here is to also leverage ICollectionView grouping in order to introduce containers in a hierarchy that has been flatten by InternalChildren. For instance, take a directory it can contain both Directories and Files. They’re flatten under the collection InternalChildren, you can introduce containers: Directories and Files in your hierarchy simply by leveraging ICollectionView grouping. The class implementing IFilterableHierarchicalData has to expose a property that will be used as a grouping criteria. One trick in order to not impact performance while applying grouping is the initiate a DeferFresh on the ICollectionViews prior grouping.

Here are the specifics of the abstract class:

FilterableHierarchicalData

Expose the visible children as an ICollectionView based on a filtering criteria

private ICollectionView m_visibleChildren; public ICollectionView VisibleChildren if (m_visibleChildren == null) m_visibleChildren = CollectionViewSource.GetDefaultView(this.InternalChildren); if (m_visibleChildren.CanFilter) m_visibleChildren.Filter = i => !((IFilterableHierarchicalData)i).IsFilteredOut; return m_visibleChildren;

Set the IsFilteredOut flag accordingly and force its ICollectionView to refresh if the filter flag changes

private bool m_isFilteredOut; public bool IsFilteredOut get { return m_isFilteredOut; } if (m_isFilteredOut != value) m_isFilteredOut = value; this.OnPropertyChanged("IsFilteredOut"); //Force refresh CollectionView with filter if (this.Parent != null) this.Parent.VisibleChildren.Refresh();

Let’s delegate the responsibility of filtering to the concrete class:

public abstract Predicate FilterPredicate { get; }

We want to display folder structures so we are going to need a couple of properties: DirectoryName and DirectoryPath. The interesting part here is how we want to identify a directory that matches a particular filter. Here is the implementation proposed:

public override Predicate FilterPredicate get { return Filter; } private bool Filter(string filterValue) //Eq to contains w/ StringComparison return this.DirectoryName.IndexOf(filterValue, StringComparison.OrdinalIgnoreCase)!= -1;

Interface methods such as GetChildren, GetVisibleChildren are helpers to walk down the hierarchy tree and get in return, in flat form, the current item’s  children and all their respective children, recursively, visible only or not. Those are later used in the filtering mechanism in order to turn on or off the filtering flag. Those are implemented in the default implementation of the filtering interface and should not require any further modifications.
Now that we have the underlying structure, we need all the plumbing around it:

Get the directory structure
We’ll use Rx for this in order to explore all the folder from a particular starting point

Provide a “great” UI
We’ll need a textbox, a treeview and a couple of text decorators. In order to add some visual feedback while the user searches for a particular string we’ll also leverage a great control in our case “ Search and Highlight in TextBlock ” from MSDN

var l_textChangedEvent = Observable.FromEventPattern<TextChangedEventHandler, TextChangedEventArgs>(h => m_filterBox.TextChanged += h, h => m_filterBox.TextChanged -= h); var l_filterEvent = from filterEvent in l_textChangedEvent select ((TextBox)filterEvent.Sender).Text; l_filterEvent.Subscribe(OnFilterHandler);

Bellow is a custom DataTemplateSelector applied to the treeview that either walks through data via InternalChildren or via the Grouping descriptions.

See how depending in which template we are in, ItemSource binding changes in order to reflect  the underlying data: {Binding VisibleChildren} (=> default no grouping), {Binding Items} (=> items members of current group) or {Binding VisibleChildren.Groups} (=> list of available groups on item) The goal of this DataTemplateSelector is to select the appropriate DataTemplate used to display the children of the current node which would be either no grouping at all, a grouping definition or an item. The interesting part is the SelectTemplate method override: public override DataTemplate SelectTemplate(object item, DependencyObject container) if (item is IFilterableHierarchicalData) var l_item = (IFilterableHierarchicalData)item; if (l_item.VisibleChildren.GroupDescriptions.Count() == 0) return this.NoGroupingTemplate ?? base.SelectTemplate(item, container); return this.ItemTemplate ?? base.SelectTemplate(item, container); else if (item is CollectionViewGroup) return this.GroupTemplate ?? base.SelectTemplate(item, container); return base.SelectTemplate(item, container);

Here is a screenshot of the final result:

Going further

We can extend filtering in order to filter not only based on text input but by type of node or any other criteria.

Keep in mind that dealing with large numbers of items in the treeview can have a drastic impact on the overall performance. Even though the suggested implementation leverages UI virtualization , huge performance improvement can be found when displaying content in a treeview that supports both UI and data virtualization.

It’s not optimal to deal with ObservableCollection<T> for InternalChildren property of IFilterableHierarchicalData. It would be better to expose a CompositeCollection , however I stopped my investigation when I found out that the property CanFilter  of CompositeCollectionView class (returned when CollectionViewSource.GetDefaultView with a CompositeCollection) returns FALSE thus preventing filtering. This is certainly an area of investigation in order to provide a better experience for the developer.

While it can be tedious to manually implement this interface for a large number of different types of "nodes". Code generation is a good companion in order to take that load out of your hands. We will see in a future post how we can leverage it in order to give a nice refresh to the plain old Model Explorer provided by DSL Tools.

The source code associated is available here minus group implementation. Drop a comment or ping us if you're interested in the implementation.