RSS

SortableObservableCollection

07 Jul

During the developement of a WPF application ObservableCollections are very useful. But if you want to bind a ObservableCollections to a control and add during program lifetime a new object to that list this item is added on the end of the list.
I wanted to add a object to the corresponding position of my SortableObservableCollection and ensure that the whole collection remains sorted.
For doing that I inherited from ObservableCollection<T> and hided the Add(T item) of the base class. By calling the Add(T item) method, the item is added to the collection and then moved to the corresponding position.
For moving the item I implemented the binary search algorithm in such way that the position of the higher neigbour object is returned and used as index for the new element.

The costs for inserting into the list is in the worst case log(n). That means that if I have a list with 20.000.000 entries and I add a new one, the position where to move that object is found after at most eight tries.

The type of objects that are used into that collection have to implement the IComparable<T> interface.


public class SortableObservableCollection<T> : ObservableCollection<T> where T: IComparable<T>
{
    public SortableObservableCollection()
    {
    }

    public SortableObservableCollection(IEnumerable<T> list)
    {
        if(list == null)
            throw new ArgumentNullException("list");
        foreach(T item in list)
            Add(item);
    }

    public new void Add(T item)
    {
        base.Add(item);
        MoveItemIntoSortedList(item);
    }

    private void MoveItemIntoSortedList(T item)
    {
        MoveItem(Count - 1, GetBinarySearchIndex(item, 0, Count - 1));
    }

    private int GetBinarySearchIndex(T item, int low, int high)
    {
        if (high < low)
            return low;
        int mid = low + ((high - low) / 2);
        if (base[mid].CompareTo(item) > 0)
            return GetBinarySearchIndex(item, low, mid - 1);
        if (base[mid].CompareTo(item) < 0)
            return GetBinarySearchIndex(item, mid + 1, high);
        return mid;
    }
}
Advertisements
 
3 Comments

Posted by on July 7, 2010 in C-Sharp, WPF

 

Tags:

3 responses to “SortableObservableCollection

  1. dtmackenzie

    March 21, 2012 at 14:08

    Very nice, thank you!
    I would add the following constructors:

    public SortableObservableCollection()
    : base()
    {
    }

    public SortableObservableCollection(IEnumerable items)
    : this()
    {
    foreach (T item in items)
    {
    this.Add(item);
    }
    }

     
    • michaelmairegger

      March 21, 2012 at 18:49

      Thanks for the reply. I will consider your suggestion and edit the post.

       
  2. michaelmairegger

    March 21, 2012 at 21:23

    I’ve updated the posts. Thanks.
    As I have seen I’ve implemented this constructor in my library collection already.

     

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: