Virtualizing WrapPanel

• Download source code - 4.88 KB

The latest code for this article can be found here; if you want to contribute to the code, just post a message here with your CodePlex account.

Introduction

This is a Virtualizing WrapPanel, similar to the default WPF WrapPanel, but it should be used inside ListBoxes/ListViews that bind to large sets of data since it only generates elements that are visible to the user, thereby improving performance.

Description

After searching on the internet for an implementation, I downloaded the trial of a paid solution that didn't work (at least, not for what I needed), so I decided to write my own. It took me an entire day to implement this, so I thought: "Why not share this so others need not go through the same trouble?".

I wrote this panel for implementing a custom open file dialog that arranges files like the Windows XP default open file dialog (fixed height and vertical orientation so it wraps into a new column), but you can use it to display any wrapping content (won't make a difference from the default WrapPanel if the data set is small).

Implementation

Firstly, a Virtualizing Panel must handle scrolling, so I followed the instructions on Ben Constable's tutorial on how to implement the IScrollInfo interface. This interface is how the ScrollViewer inside a ListBox/ListView communicates with your panel; it will ask the panel for the total area (which can be fixed or determined by the size of the children), and will pass the visible area (viewport) as a parameter to the panel's MeasureOverride method. It will also tell the panel when the user uses the scroll bar in any way. Secondly, you must handle the children generation/destruction by using the VirtualizingPanel's ItemContainerGenerator, as shown in Dan Crevier's tutorial.

The big problem is that on those samples, the size of the items is known beforehand, either by a size calculation rule or by getting the value from a property. On a WrapPanel, you only know the children size after they get instantiated by the ItemContainerGenerator, but at the same time, Virtualization of UI requires that only the visible children be instantiated. This poses a problem when you try to calculate the extent of the panel when the size is determined by the children.

To get around this, I first iterate through all the items in the collection, and when I find a new type, I generate the container for that item and map that container to the type. This same rule is adapted to when the user explicitly sets the ItemTemplate, or when using the ItemTemplateSelector, as shown in the following method:

private void RealizePossibleDataTemplates()
{
    var virtualFrame = new Rect(new Size(10000, 10000));

    var template = _itemsControl.ItemTemplate;
    if (template != null)
    {
        Type type = template.DataType as Type;
        var realizedTemplate = (FrameworkElement)template.LoadContent();
        realizedTemplate.HorizontalAlignment = HorizontalAlignment.Left;
        realizedTemplate.VerticalAlignment = VerticalAlignment.Top;
        realizedTemplate.Arrange(virtualFrame);
        _realizedDataTemplates.Add(type, (FrameworkElement)realizedTemplate);
        return;
    }

    var templateSelector = _itemsControl.ItemTemplateSelector;
    if (templateSelector != null)
    {
        foreach (var item in _itemsControl.Items)
        {
            var dt = templateSelector.SelectTemplate(item, _itemsControl);
            if (!_loadedDataTemplates.ContainsKey(dt))
            {
                var realizedTemplate = (FrameworkElement)dt.LoadContent();
                realizedTemplate.HorizontalAlignment = HorizontalAlignment.Left;
                realizedTemplate.VerticalAlignment = VerticalAlignment.Top;
                realizedTemplate.Arrange(virtualFrame);
                _loadedDataTemplates.Add(dt, realizedTemplate);
            }
        }
        _useTemplateSelector = true;
        return;
    }

    int count = _itemsControl.Items.Count;

    for (int i = 0; i < count; i++)
    {
        object currentItem = _itemsControl.Items[i];
        Type currentItemDataType = currentItem.GetType();
        if (!_realizedDataTemplates.ContainsKey(currentItemDataType))
        {
            var currentPos = _generator.GeneratorPositionFromIndex(i);
            using (_generator.StartAt(currentPos, GeneratorDirection.Forward, false))
            {
                var child = _generator.GenerateNext() as ListBoxItem;
                child.HorizontalAlignment = HorizontalAlignment.Left;
                child.VerticalAlignment = VerticalAlignment.Top;
                _generator.PrepareItemContainer(child);
                child.Arrange(virtualFrame);
                _realizedDataTemplates.Add(currentItemDataType, 
                   (FrameworkElement)VisualTreeHelper.GetChild(child, 0));
            }
            _generator.Remove(currentPos, 1);
        }
    }
}

When I need to calculate the size of a specific item, I use this:

private Size GetItemSize(object item)
{
    FrameworkElement realizedTemplate = null;
    if (_useTemplateSelector)
    {
        var templateSelector = _itemsControl.ItemTemplateSelector;
        var template = templateSelector.SelectTemplate(item, _itemsControl);
        realizedTemplate = _loadedDataTemplates[template];
    }
    else
    {
        Type itemDataType = item.GetType();
        if (!_realizedDataTemplates.ContainsKey(itemDataType))
            throw new ArgumentException("invalid item");
        realizedTemplate = _realizedDataTemplates[itemDataType];
    }
    realizedTemplate.DataContext = item;
    realizedTemplate.UpdateLayout();
    return new Size(realizedTemplate.ActualWidth, realizedTemplate.ActualHeight);
}

After that, it is pretty straightforward. All that is needed to be done is to "virtualize" all the items by storing the size and calculating the position (WrapPanel specific logic).

Using the code

To use the control, simply set it as an ItemsPanel on a bound ListBox or ListView:

<ListBox ItemsSource="{StaticResource boundCollection}">
   <ListBox.ItemsPanel>
       <ItemsPanelTemplate>
            <VirtualizingWrapPanel Orientation="Vertical" /> 
       </ItemsPanelTemplate>
    </ListBox.ItemsPanel> 
</ListBox>

Points of interest

The reason why I wanted to use a virtualizing wrappanel was that navigation was slow using the keyboard arrows when I had a large collection in a normal WrapPanel. Later I found that it was because the calculation the panel used to find the nearest child was an O(n) algorithm (n being the number of items in the panel), so writing a virtualizing panel ended not helping on that (even though it helps the loading time on large data sets). So on the Virtualizing WrapPanel, I handle the KeyPress event to use my own navigation logic. If you want to use the default panel keyboard navigation, just erase the 'OnKeyDown' method.

Observations

You can't use this panel as a standalone layout control, it must be used inside a ListBox/ListView with the ItemsSource property set to a collection. I hope someone finds this useful.

Update

After testing the first version of the Virtualizing WrapPanel, I figured that the performance wasn't acceptable since the calculation of the size made use of the 'UIElement.UpdateLayout()' method, and this ended up causing even bigger performance issues than the ordinary WrapPanel when the number of elements is really big. So I decided to check on the inner workings of the Virtualizing StackPanel, so I could see how it managed to calculate the extent of the panel so fast. And guess what? It doesn't know anything about the size of the items.

As shown in the first part of the article, I pre-calculate the size of the items prior to generating the containers, and this was necessary to implement a pixel based virtualizing panel. By pixel based, I mean that the panel viewport and extent are measured in pixels.

The Virtualizing StackPanel uses a different approach: it measures the viewport and extent using an item-based unit of measure. For example: if the panel's orientation is vertical and the number of items is 957, then the extent's height is set to 957. After each measure (scroff vertical offset changed), the viewport's height is dynamically set to the number of visible items. Some of you may have noticed that when you use the scroll down button, the Virtualizing StackPanel translates its viewport by one item. That's because the LineDown() method raises the vertical offset by 1. So, irrespective of the item's height in pixels, it will always move to the next item. This may cause some strange effects on the scroll bar if the height (or width in the case of a horizontal oriented panel) of the items change by large values, since the number of visible items (and consequently the viewport dimensions) will change. Apart from that, this measurement approach makes the panel extremely fast irrespective of the number of items.

After understanding the Virtualizing StackPanel's implementation, I thought: "So, all I have to do is implement the Virtualizing WrapPanel using a non-pixel based measurement". That's when I found some complications that made be think if it's really possible to implement a Virtualizing WrapPanel in this way:

• WrapPanels can grow in two directions, while StackPanels only grow vertically or horizontally. Also, the growth in the direction orthogonal to the panel's orientation depends on the size of the items in the direction of the panel's orientation, so I can't know when to wrap into a new line/column unless I know the size of all the items on the last line/column, but this is impossible if I want to virtualize both directions of the panel.
• The size of the extent is the same as the number of lines/columns (which I will call sections from now on). On the StackPanel, this is not a problem: since only one item per section is allowed, the extent width/height is the number of items. On the WrapPanel, the number of sections depends highly on the size of items, and since the size of the items is not fixed and can change in any direction, it is impossible to calculate the number of sections on a WrapPanel.

With that said, I have found a way to develop a non-pixel based Virtualizing WrapPanel by using the following tricks/limitations:

• The panel's extent is never known for sure. Instead, I estimate the number of sections after each MeasureOverride, using the following expression: (number of items/average items per section). Since I update the average number of items per section after each scrolling, the extent of the panel is dynamic. The extent will be static if the items size in the panels orientation is fixed.
• The items section/section index can only be calculated sequentially, so if you are viewing the first items and you jump to a section that bypasses one or more unrealized sections, the panel will use the estimation to know which item is the first visible. This will be corrected if you go back to a realized section and go back sequentially. For example: if the panel knows that item 12 is in section 1 and the panel estimates 10 items per section (section 0 being the first), if you jump to section 9, the panel will show the 100^th item as the first visible item (that will only be correct if from section 1 to 9, there are exactly 10 items per section). But if you go back to section 1 and access all the sections until you reach section 9, then the panel will store all the item sections correctly, so no further estimations will be made up to section 10.
• Normally, a WrapPanel inside a ScrollViewer would be allowed to scroll vertically and horizontally, but since I can only virtualize one direction, this WrapPanel will only scroll in the direction orthogonal to the panel's orientation. (Meaning, you shouldn't set the VirtualizingPanel height/width explicitly).

While this problem may look complicated, it got much simpler with these data structures:

class ItemAbstraction
{
    public ItemAbstraction(WrapPanelAbstraction panel, int index)
    {
        _panel = panel;
        _index = index;
    }

    WrapPanelAbstraction _panel;

    public readonly int _index;

    int _sectionIndex = -1;
    public int SectionIndex
    {
        get
        {
            if (_sectionIndex == -1)
            {
                return _index % _panel._averageItemsPerSection - 1;
            }
            return _sectionIndex;
        }
        set
        {
            if (_sectionIndex == -1)
                _sectionIndex = value;
        }
    }

    int _section = -1;
    public int Section
    {
        get
        {
            if (_section == -1)
            {
                return _index / _panel._averageItemsPerSection;
            }
            return _section;
        }
        set
        {
            if (_section == -1)
                _section = value;
        }
    }
}

class WrapPanelAbstraction : IEnumerable<ItemAbstraction>
{
    public WrapPanelAbstraction(int itemCount)
    {
        List<ItemAbstraction> items = new List<ItemAbstraction>(itemCount);
        for (int i = 0; i < itemCount; i++)
        {
            ItemAbstraction item = new ItemAbstraction(this, i);
            items.Add(item);
        }

        Items = new ReadOnlyCollection<ItemAbstraction>(items);
        _averageItemsPerSection = itemCount;
        _itemCount = itemCount;
    }

    public readonly int _itemCount;
    public int _averageItemsPerSection;
    private int _currentSetSection = -1;
    private int _currentSetItemIndex = -1;
    private int _itemsInCurrentSecction = 0;
    private object _syncRoot = new object();

    public int SectionCount
    {
        get
        {
            int ret = _currentSetSection + 1;
            if (_currentSetItemIndex + 1 < Items.Count)
            {
                int itemsLeft = Items.Count - _currentSetItemIndex;
                ret += itemsLeft / _averageItemsPerSection + 1;
            }
            return ret;
        }
    }

    private ReadOnlyCollection<ItemAbstraction> Items { get; set; }

    public void SetItemSection(int index, int section)
    {
        lock (_syncRoot)
        {
            if (section <= _currentSetSection + 1 && index == _currentSetItemIndex + 1)
            {
                _currentSetItemIndex++;
                Items[index].Section = section;
                if (section == _currentSetSection + 1)
                {
                    _currentSetSection = section;
                    if (section > 0)
                    {
                        _averageItemsPerSection = (index) / (section);
                    }
                    _itemsInCurrentSecction = 1;
                }
                else
                    _itemsInCurrentSecction++;
                Items[index].SectionIndex = _itemsInCurrentSecction - 1;
            }
        }
    }

    public ItemAbstraction this[int index]
    {
        get { return Items[index]; }
    }
}

As you can imagine, I had to rewrite 90% of the code, and while I will leave the old panel available to download, I definitively recommend the new panel since it's so much faster, and even with the limitations, this panel works perfectly for the file dialog I created, and I hope it serves someone else too.