RSS

Tag Archives: ObservableCollection

SortableObservableCollection

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: