Hibernating Rhinos

Zero friction databases

Implementing a VirtualizingWrapPanel

This is a guest post by Samuel Jack, a freelancer who has worked with us on the new RavenDb Studio features.

If you’ve used Silverlight or WPF for any length of time, you will know all about Panels – StackPanel, DockPanel, Grid and the like - which handle the positioning of UI elements on screen. You’ll also know about VirtualizingStackPanel, which can work wonders for UI performance when displaying substantial lists of data. It does this by deferring the creation of UI elements for off-screen list items until they are scrolled into view. (If you don’t know about Panels, and want to learn, a good place to start is on Dr WPF’s blog)

What if you have a huge stash of data but don’t want to display it in a boring old list? What if you want items laid out like cards on a table? Silverlight and WPF both include a WrapPanel class which can achieve the desired layout. But as its name suggests, it doesn’t virtualize. Use a WrapPanel in your 10,000-item ListBox, and you’ll be twiddling your thumbs whilst it goes off to create elements you might never see.

This was a problem we faced when we were implementing the new data virtualization features in RavenDb Studio 1.2, which lets you scroll through your entire collection of documents. We wanted the card layout, but WrapPanel wasn’t up to the job of working with huge numbers of items.

So I set about implementing a VirtualizingWrapPanel, which I’ll share with you today. You can see it in action in our sample Netflix browser (switch the Display Style to Card). The code is all available on GitHub.

First I’ll give you a quick refresher on how you make ListBox use a custom Panel, then I’ll run through how one goes about implementing a virtualizing panel in Silverlight.

A Quick Refresher on Using Panels

Here’s a snippet of XAML showing a ListBox using a VirtualizingWrapPanel:

<ListBox x:Name="DocumentsList"
                        ItemsSource="{Binding Items}" DisplayMember="Item.Name">
      <ListBox.Template>
          <ControlTemplate>
              <Border CornerRadius="2" 
                    BorderBrush="{TemplateBinding BorderBrush}"
                    BorderThickness="{TemplateBinding BorderThickness}">
                  <!-- We set the TabNavigation to Cycle on this ScrollViewer to work around a bug which causes the ListBox to loose focus when navigating down (with Down Arrow or Page Down) from the last visible item
              (or even when navigating Up/Down on an item that is only partially visible at the bottom of the screen) -->
                  <ScrollViewer x:Name="ScrollViewer" Padding="{TemplateBinding Padding}" Background="{TemplateBinding Background}" BorderBrush="Transparent" BorderThickness="0" 
                                  TabNavigation="Cycle" IsTabStop="False">
                      <ItemsPresenter />
                  </ScrollViewer>
              </Border>
          </ControlTemplate>
      </ListBox.Template>
    <ListBox.ItemsPanel>
        <ItemsPanelTemplate>
            <VirtualCollection1:VirtualizingWrapPanel ItemWidth="200"
                                            ItemHeight="230"/>
        </ItemsPanelTemplate>
    </ListBox.ItemsPanel>
</ListBox>
The key part is right down at the bottom of the snippet, where we set the ItemsPanel property of the ListBox. There we specify an ItemsPanelTemplate which instantiates the VirtualizingWrapPanel. Notice that you need to tell the panel how big each item is going to be up front, so that it knows how much room to allow for items which are off screen.

There’s one other important point. Notice that I’ve overridden the Template property for the ListBox. This is so that I can tweak the ScrollViewer which is going to contain the VirtualizingWrapPanel. The tweak is a small one: I set its TabNavigation property to Cycle. Without this, keyboard navigation doesn’t work properly within the VirtualizingWrapPanel: under certain circumstances, navigating with the Up/Down or Page Up/Page Down keys would move the keyboard focus out of the ListBox, rather than to the next item in the ListBox.

Birds-Eye View of a Virtualizing Panel

So how do you implement a Virtualizing Panel in Silverlight?

There’s a post on my own blog which explains how to create Panels of the standard variety, and I suggest you go there first for a bit of background. Suffice to say here that normal Panels have one job in life: they must layout the elements given to them by their parent control.

Virtualizing Panels have two additional responsibilities. First, they must keep track of their own scroll state. And second, they must manage the creation of UI elements - item containers -for each data item as and when they are needed. They don’t actually create the elements – that is done by an ItemContainerGenerator. They just decide when each item container should be generated.

Implementing a virtualizing panel that can handle UI items of any size you throw at it is a very tricky job. That’s because, in order to accurately position any given element, you need to know the sizes of all the elements that come before it in the list. To know their sizes, you have to measure them, and to be measured, they need to exist. But the very reason for using a virtualizing panel is to avoid creating item unnecessarily. That is why virtualizing panels tend to take one of two easy routes out of the conundrum.

VirtualizingStackPanel’s favoured approach is to use index based scrolling, where it only ever shows whole items, and the scroll bar reflects the current items’ indexes in the list and has nothing to do with their sizes. This has the downside of jerky scrolling if you have large items, since each movement of the scrollbar will move previous items entirely out of view.

Jerky scrolling is avoided by the approach I’ve taken, which is to require that each item displayed by the panel is the same size. This enables us to easily calculate the position of any given item based on its index in the list.

Scrolling Responsibilities

How does a virtualizing panel discharge its scrolling responsibilities?

The panel needs to implement IScrollInfo so its containing ScrollViewer knows that it is going to manage its own scrolling. IScrollInfo’s job splits into two parts: one is to report on the current scroll state through properties like ExtentHeight and ViewportWidth. The Extent represents the logical size of the panel – what it would be if no scrolling was taking place and everything was visible at once. The Viewport is the rectangle of the panel that is actually visible at this moment.

IScrollInfo’s other job is to enable that scroll state to be manipulated, through methods like LineUp and MouseWheelDown. In many implementations, these manipulation methods all end up by calling one of two other methods on IScrollInfo, SetVerticalOffset and SetHorizontalOffset.

Both SetVerticalOffset and SetHorizontalOffset do much the same thing, so I’ll just show the SetVerticalOffset method:

public void SetVerticalOffset(double offset)
{
  if (_isInMeasure)
  {
      return;
  }

  offset = Clamp(offset, 0, ExtentHeight - ViewportHeight);
  _offset = new Point(_offset.X, offset);

  InvalidateScrollInfo();
  InvalidateMeasure();
}

After checking that the given offset is within the scrollable range, the method simply updates a field to show where the panel is scrolled to. Then it notifies its parent ScrollViewer that its state has changed, and, by calling InvalidateMeasure, tells the framework that its layout (i.e. the arrangement of its children) needs updating. The method does one other check: if it discovers that the panel is already in the middle of updating its layout (i.e. _isInMeasure is true) it doesn’t bother changing the scroll offset. This circumvents a problem I’ve encountered where Silverlight tries to scroll to elements newly created during the layout process.

Handling Layout

Layout happens in two parts. First we measure, calculating how much space the panel will occupy taking into account its children; then we arrange, allocating each child its place within the parent. Measuring happens in MeasureOverride, and arranging in ArrangeOverride. Most of the work in the VirtualizingWrapPanel actually happens in MeasureOverride because the panel needs to generate items containers before it can measure them. You might wonder why we need to measure the item containers when we’ve already decided that they have a fixed size? That is so that the item containers can handle their own layout, which happens using the same Measure and Arrange process.

Before I show you the code for MeasureOverride, here’s an outline of what it does:

  1. GetExtentInfo is called to calculate the full height of the list – i.e. how tall it would be if we displayed it all instead of scrolling.
  2. GetLayoutInfo then works out, based on the scroll offset, which item indexes fall inside the visible range. We always make sure to include realize one item before the first visible item, and one item after the last visible item. This enables keyboard scrolling to work properly, because Silverlight can then scroll that item into view, thus triggering the panel to realize the rest of the row.
  3. Any of the current item containers that now fall outside of the visible range are recycled – handed back to the ItemContainerGenerator so that it can reuse them for other items.
  4. MeasureOverride then loops through the visible item indexes and:
    1. Asks the ItemContainerGenerator to create the UI container for the item. If the visibility of the item hasn’t changed, ItemContainerGenerator will give us back the same item container we had before
    2. Calls SetVirtualItemIndex to tag the container with the index in the list that it is now representing. This is used in step 3 the next time round when we check for items that fall outside of the visible range.
    3. Makes sure the container is in the correct place in the Panel’s list of visual children, and thus part of the visual tree. If an item is not in the correct order, keyboard navigation won’t work correctly
    4. Asks the ItemContainerGenerator to Prepare the container – apply its styles, etc.
    5. Measures the item container – this must come after step 4, because until that point the item container isn’t fully initialized, and might not even know what its content is.
    6. Decide where exactly the item container is going to be displayed: its layout rectangle is recorded in the _childLayouts dictionary. This is used by the ArrangeOverride method to arrange each child
  5. Now we can go through the panel’s list of item containers and remove any which were never actually reused. Back in step 3 every existing item container’s VirtualItemIndex tag was set to –1; and in step 4.2, containers which are in use have their tag set to the item of the index they are now representing. So item containers which were never reused will still have a VirtualItemIndex of –1.
  6. Update the scroll state with the new extent height and viewport size so that scroll bars can be drawn in the correct proportions.
  7. Decide what size to report as the desired size for the Panel. The Panel wants to take up all the available space (within the confines of its parent), so in most cases, that’s what it reports. But if it is told that the available size is Infinite, then it returns a size of 0, and by convention, Silverlight takes that to mean “use all the available space”.

Here’s the code:

protected override Size MeasureOverride(Size availableSize)
{
  if (_itemsControl == null)
  {
      return availableSize;
  }
  
  _isInMeasure = true;
  _childLayouts.Clear();

  var extentInfo = GetExtentInfo(availableSize, ItemHeight);

  EnsureScrollOffsetIsWithinConstrains(extentInfo);

  var layoutInfo = GetLayoutInfo(availableSize, ItemHeight, extentInfo);

  RecycleItems(layoutInfo);

  // Determine where the first item is in relation to previously realized items
  var generatorStartPosition = _itemsGenerator.GeneratorPositionFromIndex(layoutInfo.FirstRealizedItemIndex);

  var visualIndex = 0;

  var currentX = layoutInfo.FirstRealizedItemLeft;
  var currentY = layoutInfo.FirstRealizedLineTop;

  using (_itemsGenerator.StartAt(generatorStartPosition, GeneratorDirection.Forward, true))
  {
      for (var itemIndex = layoutInfo.FirstRealizedItemIndex; itemIndex <= layoutInfo.LastRealizedItemIndex; itemIndex++, visualIndex++)
      {
          bool newlyRealized;

          var child = (UIElement)_itemsGenerator.GenerateNext(out newlyRealized);
          SetVirtualItemIndex(child, itemIndex);

          if (newlyRealized)
          {
              InsertInternalChild(visualIndex, child);
          }
          else
          {
              // check if item needs to be moved into a new position in the Children collection
              if (visualIndex < Children.Count)
              {
                  if (Children[visualIndex] != child)
                  {
                      var childCurrentIndex = Children.IndexOf(child);

                      if (childCurrentIndex >= 0)
                      {
                          RemoveInternalChildRange(childCurrentIndex, 1);
                      }

                      InsertInternalChild(visualIndex, child);
                  }
              }
              else
              {
                  // we know that the child can't already be in the children collection
                  // because we've been inserting children in correct visualIndex order,
                  // and this child has a visualIndex greater than the Children.Count
                  AddInternalChild(child);
              }
          }

          // only prepare the item once it has been added to the visual tree
          _itemsGenerator.PrepareItemContainer(child);

          child.Measure(new Size(ItemWidth, ItemHeight));

          _childLayouts.Add(child, new Rect(currentX, currentY, ItemWidth, ItemHeight));

          if (currentX + ItemWidth * 2 >= availableSize.Width)
          {
              // wrap to a new line
              currentY += ItemHeight;
              currentX = 0;
          }
          else
          {
              currentX += ItemWidth;
          }
      }
  }

  RemoveRedundantChildren();
  UpdateScrollInfo(availableSize, extentInfo);

  var desiredSize = new Size(double.IsInfinity(availableSize.Width) ? 0 : availableSize.Width,
                             double.IsInfinity(availableSize.Height) ? 0 : availableSize.Height);

  _isInMeasure = false;

  return desiredSize;
}

It’s a Wrap

That concludes our look at the VirtualizingWrapPanel. Go and check out the whole sample on GitHub, and let us know what you make of it.

Comments

HamGuy
09/19/2012 09:18 AM by
HamGuy

Hi, jack I tried to use this panel you created i windows phone, but unfortunately, it was incompatible. I can't scroll any more. I have no idea why the IScroll methods not called, could you give me some tips or create a windows phone version demo, thanks in advance!

Samuel Jack
09/24/2012 11:09 AM by
Samuel Jack

I've not tried this code on Windows Phone 7, so I can't say why it isn't working. I did find this though (http://stackoverflow.com/questions/2793167/scroll-gestures-not-passed-to-iscrollinfo-implementing-panel-in-windows-phone-7) which suggests that custom panels like VirtualizingWrapPanel won't work correctly on WP7.

Comments have been closed on this topic.