.NET 3.0 functionality in .NET 2.0: a sorting, filtering, bindable list
The third in a series of write-ups on some of the odder parts of shaim.
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 ComparisoncurrentComparison; /// <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.
[…] The thrilling conclusion to Part One! […]
csammisrun » .NET 3.0 functionality in .NET 2.0: a sorting, filtering, bindable list - Part Two
17 Jul 08 at 9:54 am edit_comment_link(__('Edit', 'sandbox'), ' ', ''); ?>
[…] recorded first by jfosco on 2008-08-08→ .NET 3.0 functionality in .NET 2.0: a sorting, filtering, bindable … […]
Recent URLs tagged Binding - Urlrecorder
23 Aug 08 at 7:15 pm edit_comment_link(__('Edit', 'sandbox'), ' ', ''); ?>
[…] (required) Website. For spam filtering purposes, please copy the number 1356 to the field below: ….NET 3.0 functionality in .NET 2.0: a sorting, filtering …A rare situation … 23 Aug 08 at 7:15 pm. Leave a Reply. Name (required) Mail (will not be […]
insertitem
5 Mar 10 at 12:17 am edit_comment_link(__('Edit', 'sandbox'), ' ', ''); ?>