csammisrun

The third in a series of write-ups on some of the odder parts of shaim.

1. WPF versus IM typing notifications
2. WPF windows, in my Winforms application?

As I described in the last write-up, shaim is organized around a central core. The core provides services such as preference loading/saving, loading plugins and dispatching inter-plugin events, and a factory for proxied sockets. It also holds the most central data structure to any instant messaging application: the contact list. This post is going to talk about creating a data structure that replicates the functionality of a .NET 3.0 INotifyCollectionChanged collection in .NET 2.0-compatible code. Why would you want to do that in the first place? All shall be made clear…

Representing and displaying the contact list

For most IM systems and for the purposes of this discussion, a contact list is hierarchical. Stemming from the root of the list are groups, each of which can contain one or more contacts

Contact List
|
+-- Group
|   |
|   +-- Contact
|   +-- Contact
|
+-- Group
    |
    +-- Contact

Hierarchical data of this nature is naturally represented using a tree view, and shaim’s UI plugin is no exception. It uses the WPF TreeView control, which is capable of binding to a list-of-lists and displaying the data in a pleasing fashion. If you bind to a collection that implements the INotifyCollectionChanged interface, the TreeView will even do such kind things as update the view automatically when the bound list changes.

A challenge!

One of the driving goals of the project is to maintain a core that can be compiled on Mono, which means the core uses absolutely no .NET 3.0 components or data structures. The modularity of the plugin design still lets the framework utilize plugins that are based on .NET 3.0 technology, but as long as the core maintains its purity, it’s all good in our hood. Tra la la, happy days…oh shit, INotifyCollectionChanged is a .NET 3.0 interface. The contact list can’t use it, the TreeView won’t update itself properly, chaos ensues, and I’m lying in a ditch somewhere having been beaten to death by hired goons.

Well that’s alright, that’s okay, no one ever said life was simple. We’ll just implement a collection with similar – and compatible – behavior using .NET 2.0. In fact, since people like to do silly things like organize their data alphabetically (pfffft), let’s add sorting logic to it. And while we’re being all nutty, let’s add a filter so users can remove items that meet certain criteria, then people can do such as not display empty groups or offline contacts. Above all, it has to be painless from the UI’s point of view: we don’t want any of this logic floating up into the UI, where it would have to be replicated by any new UI plugin.

So this collection has to be:

• .NET 2.0 compatible
• Bindable by WPF and Winforms
• Sortable
• Filterable
• Hell, let’s make it generic while we’re at it

We shall call it: BindingListCollection!

The basics of the BindingListCollection

First things first, we have to find .NET 2.0 structures and interfaces that we can start with that’ll let us fake the funk appropriately.

Like all good classes that are bound in some way, the BindingListCollection will implement INotifyPropertyChanged. This interface is similar to the verboten INotifyCollectionChanged, in that it notifiers consumers of a change in the implementing object, but instead of a change on the contents of a collection the INotifyPropertyChanged interface notifies of changes in a single property. Perhaps we can fool the TreeView into refreshing its view of the collection by notifying of a property change on the Items property! In fact we can, this does work, but it’s pretty horrific. Anything binding to a specific property completely refreshes when a property change happens, which gets expensive and slow when you’re talking about a list of any sort of appreciable size. The INotifyCollectionChanged interface gets around this by raising an event that specifies exactly what action was taken (adding or removing an item, for instance) and where in the list it happened, so the entire thing isn’t munged by what should be a quick change.

Is there an interface or a class in .NET 2.0 that is clever like the INotifyCollectionChanged interface? Turns out that there is: BindingList. It fits all of our requirements: it’s .NET 2.0, supports binding, has support for sorting and filtering, and is generic. So begins our new type, BindingListCollection.

public class BindingListCollection<T> : BindingList<T>, INotifyPropertyChanged

Now whenever we manipulate the collection (by adding, removing, filtering, or sorting items), raising the ListChanged event will cause whatever’s binding to it to update correctly and specifically, just like INotifyCollectionChanged.

Filtering and sorting: adding support for all this ballyhoo

The BindingList provides support for filtering and sorting, but leaves it to you to implement the routines to do it. Let’s make this super-extensible, and create methods to filter and sort using generic delegates for the purpose. Consumers of the BindingListCollection can create custom methods to sort and filter, then pass it in and let the BindingListCollection do the rest.

private bool isSorted;
private bool isFiltered;
/// <summary>
/// The sorting comparison currently in use
/// </summary>
private Comparison currentComparison;
/// <summary>
/// The filtering predicate currently in use
/// </summary>
private Predicate currentFilter;

/// <summary>
/// Sorts the list by the specified property in the specified direction
/// </summary>
public void Sort(Comparison sortCriteria)
{
    isSorted = true;
    currentComparison = sortCriteria;
    ApplyListAlterations();
}
/// <summary>
/// Filters the list contents by the specified predicate
/// </summary>
public void Filter(Predicate filterCriteria)
{
    isFiltered = true;
    currentFilter = filterCriteria;
    ApplyListAlterations();
}
/// <summary>
/// Applies the current filter and sort to the list
/// </summary>
private void ApplyListAlterations()
{
    List listref = Items as List;

    Items.Clear();
    listref.AddRange(unsortedList); // An original copy of all items - explained below

    if (isFiltered)
    {
        // Perform filtering on the current item list
        for (int i = 0; i < Count; i++)
        {
            if (!currentFilter(Items[i]))
            {
                Items.RemoveAt(i--);
            }
        }
    }

    if (isSorted)
    {
        // Sort the current item list
        listref.Sort(currentComparison);
    }

    // Tell all bindings to reset completely
    OnListChanged(new ListChangedEventArgs(ListChangedType.Reset, -1));
}

That was it! We now have a filterable sortable bindable generic collection...but it sucks! If you add a new item to the BindingListCollection, it doesn't get sorted or filtered. Right now a consumer has to call Sort and Filter again every time an item is added, which causes a complete reprocessing and binding reset, and that is e-x-p-e-n-s-i-v-e. We have to be clever to achieve awesomeness.

The essence of filtering is removing items from the list, but we have to save those items somehow; if we didn't, every time the filter was changed, or removed, or the item changed so that the filter no longer applies, the item would have to be re-added. The essence of sorting is changing the order in which items are displayed, but we want to preserve the original order. Both of these can be accomplished by maintaining a backing list - a list of all the items, exactly as they're added, that can be used to restore order when the sort or filter changes. We've already seen this in the BindingListCollection: the 'unsortedList' mentioned in ApplyListAlterations().

/// <summary>
/// The underlying list of manually inserted items
/// </summary>
private List<T> unsortedList = new List<T>();
/// <summary>
/// The index at which the item was originally inserted by the list controller
/// </summary>
private readonly Dictionary<T, int> insertIndicies;

The backing list must be maintained whenever items are added or removed from the BindingListCollection, so the InsertItem and RemoveItem methods are overriden to add to both the backing list and the main list. InsertItem is not terribly complicated:

/// 
<summary>
/// Inserts the specified item in the list at the specified index.
/// </summary>
protected override void InsertItem(int index, T item)
{
    // Maintain the backing list
    if (index > unsortedList.Count)
    {
        unsortedList.Add(item);
    }
    else
    {
        unsortedList.Insert(index, item);
    }

    // Add the requested index to the item-index map
    insertIndicies[item] = index;

    // Insert the item into the list
    if (index != -1)
    {
        if (index > base.Count)
        {
            index = base.Count;
        }
        base.InsertItem(index, item);
    }

    if (PropertyChanged != null)
    {
        PropertyChanged(this, new PropertyChangedEventArgs("Items"));
    }

    // Fire the AddingNew event
    OnAddingNew(new AddingNewEventArgs(item));
}

I'm not going to specifically list out RemoveItem here, but it's pretty simple: Remove the requested item from the backing list and insertIndicies, remove it from the base list, and that's that.

Filtering and sorting: what goes where?

Even though every item added to the BindingListCollection ends up in the backing list, it may not end up in the requested insert position if a sort is applied, and it may not end up in the main list at all if a filter is applied. The BindingListCollection has to compute an insertion index that makes sense according to the current sort and filter, and that's done using a new-fangled method, PlaceByCurrentComparison:

/// <summary>
/// Returns the index at which an item would be inserted by the current sort comparison
/// and current filter
/// </summary>
/// <returns>The index at which to insert the item, or -1 if it would not be in the currently filtered list</returns>
private int PlaceByCurrentComparison(T item)
{
    // If the item doesn't match the current filter, don't add it
    if (isFiltered && !currentFilter(item))
    {
        return -1;
    }

    int insertindex = 0;
    if (currentComparison != null)
    {
        // Get the index in the sorted list
        while (insertindex < Count && currentComparison(item, Items[insertindex]) >= 0)
        {
            insertindex++;
        }
    }
    else
    {
        // Check the originally requested insertion index, put it as close as possible
        if (insertIndicies.ContainsKey(item))
        {
            while (insertindex < Count &&
                (insertIndicies.ContainsKey(Items[insertindex]) && insertIndicies[item] >= insertIndicies[Items[insertindex]]))
            {
                insertindex++;
            }
        }
    }

    return insertindex;
}

...and the InsertItem method gets updated:

...
    // Add the requested index to the item-index map
    insertIndicies[item] = index;

    // If the list is sorted, find the correct insertion point for the sorted order
    if (isSorted || isFiltered)
    {
        index = PlaceByCurrentComparison(item);
    }

    // Insert the item into the list
    if (index != -1)
    {
        if (index > base.Count)
        {
            index = base.Count;
        }
        base.InsertItem(index, item);
    }
...

This seems pretty nice now: items are inserted into the list, their requested insert indexes are saved, but they may or may not be displayed sorted or at all, and the BindingListCollection takes care of all of it. The caller sees only this:

BindingListCollection<ContactGroup> groupList = ...;
groupList.Sort(someAlphabeticComparison);
groupList.Add(new ContactGroup("Buddies"));
groupList.Add(new ContactGroup("Amigos"));
groupList.Add(new ContactGroup("Wise-ass jerks"));

I am so done with typing right now

This is getting pretty ridiculously long for a blog post, so I'll finish off the discussion later this week. Still to come: Live updating of the filter and sort as items change, overriding properties to make sure the bound UI object knows what can be expected, and a failed recipe for basil-lime sorbet.