Note: You can download the complete implementation here.

In my last post I described the implementation of the ICollection interface in ObjectListView, my implementation of a view for collections of arbitrary objects.  The goal is to provide the same view capabilities for collections that DataView supports for DataTables.

In this post, we’ll move on to the next interface required for data binding, IList.

Positional list access

The IList interface defines the methods and properties that make a list-style collection fully functional.  We can add and remove items, and importantly for our view, add, remove, and access items by position.  When we implement these positional methods, the position will always be interpreted as the position within the view, rather than the position in the underlying list.  In our view implementation, we’ll keep a reference to the original underlying list:

private IList list;

The original list

As an example of this positional access, lets say that list contains these items:

If we were to access list[3], we would see G.

Now let’s say we have our view of the list, sorted and filtered to exclude C.  The view presents itself as a list that looks like this:

Sorted and filtered list

If we access view[3], we expect to obtain E.

With that in mind, we know that we will need a sorted, filtered store of list items, and we know that we will need to access it by view position.

For my sorted, filtered store, I chose to maintain a list of integers, such that this list is in sorted order, and the values in the list represent indexes of values in the underlying collection.

private List sortIndexes = new List();

For the previous example, sortIndexes looks like this:

Sort indexes

You can see that these indexes map to the values in the underlying list.  To obtain the value at view[3], we look up the value stored in sortIndexes[3].  That value is 6, so we go to list[6] for the value to return.

View mapping

To keep track of the sorted and filtered positions, we implement a few private methods.  RebuildSortIndexes() re-creates the list of sorted indexes for the current list contents.  GetListPositionOfViewIndex() retrieves the position in the list that corresponds to the given view index (i.e. the method that returns 6 for the index 3 in the above picture).  GetSortedPositionOfListIndex() does the converse – given an index into the underlying list, it finds the corresponding index in the view.  GetSortIndexes() provides access to the list of sorted indexes, rebuilding them if needed.

private int GetSortedPositionOfListIndex(int listIndex)
{
  if (this.IsSorted || this.IsFiltered)
    return this.GetSortIndexes().IndexOf(listIndex);
  else
    return listIndex;
}

private int GetListPositionOfViewIndex(int viewIndex)
{
  if (this.IsSorted || this.IsFiltered)
    return this.GetSortIndexes()[viewIndex];
  else
    return viewIndex;
}

private List GetSortIndexes()
{
  // Items have been added or removed through the list directly, instead of through the ObjectListView.
  if (this.SortIndexesDirty)
    RebuildSortIndexes();

  return this.sortIndexes;
}

private void RebuildSortIndexes()
{
  this.sortIndexes = new List(this.list.Count);
  if (this.IsFiltered)
  {
    for (int i = 0; i < this.list.Count; i++)
    {
      if (this.filterPredicate(this.list[i]))
        this.sortIndexes.Add(i);
    }
  }
  else
  {
    for (int i = 0; i < this.list.Count; i++)
      this.sortIndexes.Add(i);
  }

  if (this.IsSorted)
    ApplySortCore();
}

We'll discuss the filtering and sorting implementations later, so for now, just know that IsFiltered and IsSorted indicate whether or not filtering and sorting have been specified.  If the view is filtered, the filterPredicate is used to test each list item for inclusion in the list of indexes.  After adding all of the indexes to the sortIndexes list, the sortIndexes list is sorted.

The GetSortIndexes() wrapper around sortIndexes is used instead of directly referring to sortIndexes, so that we have a point to determine if the indexes are invalid, and regenerate them if needed.  Normally, the list will notify the view of list item additions and removals.  Lists that do not implement IBindingList do not provide this notification however.  To better support these lists, the view compares the size of the sortIndexes list with the size of the list.  If different, the indexes need to be rebuilt.  This check is implemented in the view's SortIndexesDirty property:

private bool SortIndexesDirty
{
  get
  {
    // The capacity of the indexes list is the size of the list as the view knows it.
    // If the size of the list has changed (items added or removed), we know that the indexes are now invalid.
    // This can happen if the list is manipulated directly (not through methods of the view) and the list does not
    // notify the view of the changes.
    Lock();
    bool dirty = (sortIndexes.Capacity != this.list.Count);
    Unlock();

    return dirty;
  }
}

Adding items

The methods of IList provide a few different ways to add and remove items.  Rather than cover every line of the implementation, I'll just discuss the Add() method in detail and touch on the interesting points of the others.  Here's Add():

public int Add(object value)
{
  Lock();

  int sortedIndex = -1;

  try
  {
    if (!this.allowNew)
      throw new DataException("AllowNew is set to false.");

    // The && should be two ampersands - the code prettifier can't format that correctly.
    if (this.list.Count == 0 && value != null)
      this.ItemType = value.GetType();

    int index = this.list.Add(value);

    // If the list supports ListChanged, OnItemAdded will have already been called.
    if (!this.supportsListChanged)
      sortedIndex = this.OnItemAdded(index);
    else
      sortedIndex = this.GetSortedPositionOfListIndex(index);
  }
  finally
  {
    Unlock();
  }

  RaiseListChangedEvents();
  return sortedIndex;
}

Here we're just adding an item to the underlying list.  We get the index of the added item from the list, and translate that to the sorted index in the view.  The view's index is the one we want to return, as all positional interaction with the view is done in terms of the sorted and filtered position.

If this is the first item added to the list, we need to look at the list item type and it's capabilities.  The ItemType property setter does this.

public Type ItemType
{
  get
  {
    Lock();
    Type t = this.itemType;
    Unlock();
    return t;
  }
  set
  {
    if (value == null)
      throw new ArgumentNullException("ItemType");

    Lock();
    try
    {
      // The && should be two ampersands - the code prettifier can't format that correctly.
      if (itemType != null && itemType != value)
        throw new InvalidOperationException("The list already contains items");

      this.isEditableObject = typeof(IEditableObject).IsAssignableFrom(value);
      this.supportsNotifyPropertyChanged = typeof(INotifyPropertyChanged).IsAssignableFrom(value);
      this.itemType = value;
      this.itemProperties = TypeDescriptor.GetProperties(value);
      this.itemPropertyChangedEvents = this.GetPropertyChangedEvents(value);
      this.supportsPropertyChangedEvents = this.itemPropertyChangedEvents.Count > 0;
    }
    finally
    {
      Unlock();
    }
  }
}

With respect to the list item type, we need to find out if the item will raise events when it's property values change, and whether it provides the "undo-able" editing mechanism of IEditableObject.  If the item type implements INotifyPropertyChanged, we know that it will raise PropertyChanged when the value of any public property changes.  This interface is new to .NET 2.0.  In previous versions, the convention for property change notification was the existence of an event of the same name as the property, plus "Changed".  For example, if the property name was "AccountId", the expected change event would be called "AccountIdChanged".  If the event did not exist, there was no notification.  In the ItemType property setter, we check for both INotifyPropertyChanged and .NET 1.x style property change events.

Back in the Add() method, we call OnItemAdded() if the underlying list doesn't support ListChanged.  I mentioned earlier that lists implementing IBindingList raise an event when items are added or removed.  When our IBindingList list raises ListChanged for a newly added item, we call OnItemAdded() in an event handler elsewhere.  Here we're handling the case where list is not an IBindingList.

private int OnItemAdded(int listIndex)
{
  // Invalidate enumerators.
  this.version++;

  // Subscribe to the item change events (either INotifyPropertyChanged or xxxChanged).
  this.WirePropertyChangedEvents(list[listIndex]);

  // Sort and filter.
  this.RebuildSortIndexes();
  int sortedIndex = this.GetSortedPositionOfListIndex(listIndex);
  this.QueueListChanged(new ListChangedEventArgs(ListChangedType.ItemAdded, sortedIndex));
  return sortedIndex;
}

Since the contents of the list are changing, we update our version number to inform any enumerators that they are no longer valid (recall that IEnumerable.GetEnumerator() returns an IEnumerator object that knows what version of our view it was created for).  If our ItemType property setter determined that the list item type supports property change events, we need to add event handlers to those events.  We need to update the sort indexes, as the new item might appear anywhere in the sort, and may or may not meet the filter criteria.

The returned index is the view index, which might be -1 if the added item is not visible.  For example, if our filter limits the view to items with a LastName property equal to "Jones", and the added item's LastName is "Smith", then the item will be added to the underlying list, but will not be accessible through the view.  The Insert() method presents a related dilemma, as it specifies a position in the view to insert the added item.  If the view is sorted, the position of the added item is determined by the sort, so the specified position must be disregarded.

Finally, notice the call to QueueListChanged().  Because our view is implementing IBindingList, it is expected to raise the ListChanged event just like any collection that implements IBindingList would.  If our underlying list is an IBindingList, then the list will raise the event, and the view will also raise the event.  Why are we "queuing" the ListChanged notification instead of just raising the event?  Looking back at the Add() method, we see that OnItemAdded() is called while a lock is held.  The lock is held if the underlying list is synchronized; if not, Lock() and Unlock() are no-ops.  Consider what would happen if a lock is held while ListChanged is raised.  If the user's event handler is on another thread and calls a method or property of the view (e.g. view.Count), it will deadlock.  To prevent this, we queue up any events that would normally be raised while the lock is held, and then raise them after releasing the lock.

Where are we?

We've added support for the IEnumerable, ICollection, and IList interfaces, which expose the basic features of a list-style collection.  In our IList implementation, we're providing the necessary translation from index positions in the view to index positions in the list, and vice versa.  To satisfy the requirements of IBindingList, we're raising the ListChanged event when items are added to or removed from the view.

In my next post, I'll describe the IBindingList interface, where sorting and searching behaviors are exposed.  I'll also discuss more issues surrounding the ListChanged event.