Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles
(untagged)

Replacing TreeView with ListBox

0.00/5 (No votes)
6 Oct 2011 1  
TreeView is not good enough to support millions of nodes. Simulating using a ListBox might help.

Introduction

Performance of the TreeView control is not good enough to handle thousands of nodes. It does not do UI virtualization if a single node contains a few thousands of child nodes. So I used a ListBox which supports virtualization to simulate the TreeView.

Background

I was developing an Open Source project named Media Assistant which manages all your media (music and movies) files and provide information information from IMDb and provide recommendation from TasteKid and many other features. But when I added a few thousands of movies in the application, it collected about 24 thousands of artist/genre and other information. I display the Media Library in a TreeView. I found that TreeView cannot handle such huge data. It was talking a long time to load and expand a node. Specially if a single node has a few thousands of children. I searched on the net about the problem and found a custom TreeView control which supports virtualization. But the performance was still not satisfactory. So I needed some kind of data virtualization and UI virtualization to solve my problem. I found a beautiful article about Data Virtualization. But data virtualization explained in the article works only for flat data not with hierarchical data. So, I ended up with a solution to use ListBox where I can do Data Virtualization, and ListBox supports UI virtualization by default. A complete solution to my problem.

Media_Library.png

How to simulate TreeView control with a ListBox

To explain how I implemented a ListBox which looks like TreeView with Data Virtualization, I split the problem in two parts. The first part will explain Templating ListBox in such a way that it looks like a TreeView, and the second part will explain how I converted hierarchical data to a flat list so that I can achieve Data Virtualization.

Templating ListBox so that it looks like a TreeView

<ListBox Name="Tree" DockPanel.Dock="Top" 
       ItemsSource="{Binding DataSource.OrderedLibraryItems}" 
       Width="230" HorizontalAlignment="Left"
       BorderThickness="0"
       Background="Transparent"
       VirtualizingStackPanel.IsVirtualizing="True"
       VirtualizingStackPanel.VirtualizationMode="Standard"
       ScrollViewer.IsDeferredScrollingEnabled="True"               
       ItemTemplate="{StaticResource ListLibraryItemTemplate}"
       SelectionMode="Single"
       MouseDoubleClick="HandleMouseDoubleClick"
/>

By default, ListBox uses VirtualizingStackPanel. I used deferred scrolling so that while scrolling, the ListBox doesn't get updated. In the ItemsSource, I bind the flat lists which is a flat representation of my hierarchical data. ListLibraryItemTemplate represents the list items so that it looks like a node of a TreeView.

<DataTemplate x:Key="ListLibraryItemTemplate" >
    <StackPanel x:Name="listItemPanel" Orientation="Horizontal" 
          Margin="{Binding Converter={StaticResource LibraryItemMarginConverter}}">
        <ToggleButton x:Name="expandCollapseButton"
          IsChecked="{Binding IsExpanded, Mode=TwoWay}" 
          Visibility="{Binding HasChildren, 
                      Converter={StaticResource HasChildreenVisibilityConverter}}"
          Command="{Binding RelativeSource={RelativeSource 
                   Mode=FindAncestor,AncestorType={x:Type UserControl}}, 
                   Path=DataContext.ToggleExpandCollapseCommand}"
          Style="{StaticResource ExpandCollapseToggleStyle}"/>
        <Border Name="iconBorder" Width="20" Height="20">
            <ContentControl x:Name="icon"/>
        </Border>
        <TextBlock TextAlignment="Left" HorizontalAlignment="Center" 
          VerticalAlignment="Center" Text="{Binding Title}" 
          ToolTip="{Binding Title}" Width="150" 
          TextTrimming="CharacterEllipsis"></TextBlock>
    </StackPanel>
    <DataTemplate.Triggers>
        <DataTrigger Binding="{Binding Type}" 
                  Value="{x:Static Constants:LibraryItemType.MovieLibrary}">
            <Setter TargetName="icon" Property="Content" 
                  Value="{StaticResource MovieLibraryImage}"/>
            <Setter TargetName="iconBorder" 
                    Property="Width" Value="25"/>
            <Setter TargetName="iconBorder" 
                    Property="Height" Value="25"/>
        </DataTrigger>
        <DataTrigger Binding="{Binding Type}" 
                  Value="{x:Static Constants:LibraryItemType.UnreadMovieLibrary}">
            <Setter TargetName="icon" Property="Content" 
                   Value="{StaticResource NewImage}"/>
        </DataTrigger>
    //some other triggers
    </DataTemplate.Triggers>
</DataTemplate>

In the data template, I used a toggle button to show the +/- expand/collapse state, an icon to represent the library item, and a TextBlock represents the text of my library item.

To make the toggle button look like the expand/collapse button, I used the following style:

<Style x:Key="ExpandCollapseToggleStyle" TargetType="{x:Type ToggleButton}">
    <Setter Property="Focusable" Value="False"/>
    <Setter Property="Width" Value="19"/>
    <Setter Property="Height" Value="13"/>
    <Setter Property="Template">
        <Setter.Value>
            <ControlTemplate TargetType="{x:Type ToggleButton}">
                <Border Width="19" Height="13" Background="Transparent">
                    <Border SnapsToDevicePixels="true" Width="9" Height="9" 
                           Background="{DynamicResource {x:Static SystemColors.WindowBrushKey}}" 
                           BorderBrush="{DynamicResource {x:Static SystemColors.GrayTextBrushKey}}" 
                           BorderThickness="1">
                        <Path Margin="1,1,1,1" x:Name="ExpandPath" 
                            Fill="{DynamicResource {x:Static SystemColors.WindowTextBrushKey}}" 
                            Data="M 0 2 L 0 3 L 2 3 L 2 5 L 3 5 L 3 3 L 5 3 L 5 2 L 3 2 L 3 0 L 2 0 L 2 2 Z"/>
                    </Border>
                </Border>
                <ControlTemplate.Triggers>
                    <Trigger Property="IsChecked" Value="True">
                        <Setter Property="Data" TargetName="ExpandPath" 
                                 Value="M 0 2 L 0 3 L 5 3 L 5 2 Z"/>
                    </Trigger>
                </ControlTemplate.Triggers>
            </ControlTemplate>
        </Setter.Value>
    </Setter>
</Style> 

I used the IsExpanded property of my library item to change the expand/collapse state of the toggle button. I introduced a property in my data structure to represent if it is expanded or collapsed.

To show the indenting at the ListBoxItem so that it looks like a tree node, I used LibraryItemMarginConverter to convert the Lavel property of the library item to margin for indenting.

public class LibraryItemMarginConverter:IValueConverter
{
    public object Convert(object value, Type targetType, 
           object parameter, CultureInfo culture)
    {
        var libraryItem = (LibraryItem)value;
        return new Thickness(libraryItem.Lavel * 10, 1, 0, 1);
    }
    public object ConvertBack(object value, Type targetType, 
           object parameter, CultureInfo culture)
    {
        throw new NotImplementedException();
    }
}

I introduced a Lavel property in my LibraryItem.

If a node doesn't have a child node then the tree view doesn't display any expand/collapse button. To simulate this, I used the HasChildreenVisibilityConverter converter which converts the HasChildren boolean property to visibility.

public class HasChildreenVisibilityConverter:IValueConverter
{
    public object Convert(object value, Type targetType, 
                  object parameter, CultureInfo culture)
    {
        if (value == null)
            return Visibility.Visible;
        var hasChildren = (bool)value;
        return hasChildren ? Visibility.Visible : Visibility.Hidden;
    }
    public object ConvertBack(object value, Type targetType, 
                  object parameter, CultureInfo culture)
    {
        throw new NotImplementedException();
    }
}

I introduced a HasChildren property in my LibraryItem. I could find if the library item has children while needed. But it is expensive when you are using Entity Framework. Because every time you access a navigation property, it takes enough time to process. I used a data trigger to change the icon of my library item. That's all for templating a ListBox to look like a TreeView.

Converting hierarchical data to a flat list to support data virtualization

To understand data virtualization, please read the article WPF Data Virtualization.

var orderedLibraryItems = 
  new VirtualizingCollection<LibraryItem>(new LibraryItemProvider(rootItems));

VirtualizingCollection takes an implementation of IItemsProvider which has two methods: FetchCount and FetchRange. My implementation for IItemsProvider is LibraryItemProvider which takes the root item as a constructor parameter. VirtualizingCollection first accesses the FetchCount method to identify how many items are available in the collection.

Calculating count

private void CalculateCount()
{
    _count = 0;
    foreach (var rootItem in _rootItems)
    {
        _count++;
        rootItem.Lavel = 0;
        _startIndexDictionary.Add(_count - 1, rootItem);
        GetChildrenCount(rootItem, 0);
    }
}
private void GetChildrenCount(LibraryItem item, int label)
{
    if (!item.IsExpanded)
    {
        return;
    }
    if (LibraryItemType.CanHaveChildren(item.Type) == false)
    {
        return;
    }
    if (LibraryItemType.IsLastParent(item.Type) == false)
    {
        foreach (var child in item.OrderedChildren)
        {
            _count++;
            child.Lavel = label + 1;
            _startIndexDictionary.Add(_count - 1, child);
            GetChildrenCount(child, label + 1);
        }
    }
    else
    {
        _count += item.Children.Count;
    }
}

I used a recursive method to count the number of visible items in the list. If the item is expanded and it has children, then I'm continuing recursion by increment the Lavel which I use to do indenting like TreeView nodes. At the same time, I have a dictionary where the index is the key and the item at that index position is the value. This dictionary will be used in the FetchRange method to find a range of data to serve the virtualizing StackPanel.

FetchRange

public IList<LibraryItem> FetchRange(int startIndex, int count)
{
    lock (DatabaseManager.LockObject)
    {
        var skippedItems = 0;
        var items = new List<LibraryItem>();
        foreach (var kv in _startIndexDictionary.OrderBy(kv => kv.Key))
        {
            var endeIndex = kv.Key;
            if (kv.Value.IsExpanded)
            {
                endeIndex += kv.Value.Children.Count;
            }
            if (endeIndex < startIndex)
            {
                skippedItems = endeIndex + 1;
                continue;
            }
            if (skippedItems < startIndex)
            {
                skippedItems++;
            }
            else
            {
                items.Add(kv.Value);
                if (items.Count == count)
                    return items;
            }
            if (kv.Value.IsExpanded && LibraryItemType.IsLastParent(kv.Value.Type))
            {
                foreach (var item in kv.Value.OrderedChildren)
                {
                    if (skippedItems < startIndex)
                    {
                        skippedItems++;
                    }
                    else
                    {
                        item.Lavel = kv.Value.Lavel + 1;
                        items.Add(item);
                        if (items.Count == count)
                            return items;
                    }
                }
            }
        }
        return items;
    }
}

In the FetchRange method, I skip the number of items to move the position to the startIndex. I use the dictionary I build to do this traveling to make the code run faster. Once I reach the item of startIndex, I try to return the number of items represented in the count parameter. The virtualizingCollection class uses a page size of 100 which can be changed to fetch items.

Points of interest

When developing Media Assistant, I found many areas where performance is a big issue and standard WPF controls needed to be used in a different way to solve problems. I'll try to post all such work I did to improve the performance of the application.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here