SortedObservableCollection

The reason I started this blog was two fold.  First I’d like to give back to community that has helped me.  I can’t count the number of times I’ve used google to help solve a problem.  The second reason is for my own benefit.  My thought is that by explaining principles, rules and patterns that I’ve discovered will help me to better understand them and commit to memory.  The majority of posts to date have been opinion based and though I enjoy expressing those opinions haven’t yet made much of a contribution to the community or helped me, besides solidifying my own beliefs.  So without further ado, I’d like to present my SortedObservableCollection as the first installment to my “technical” blog.

I read a post earlier today presenting an implementation of a SortedObservableCollection and I thought to myself, “Hey! I’ve made one of those before.”  My own implementation is a bit different but I feel stronger in that rather than adding an item to the collection and then sorting the entire collection, this implementation inserts the item in the appropriate spot.  I will admit performance may take a hit in larger lists but I think most “collections” of UI elements are not big.  The two uses I’ve made of this list thus far number anywhere from 10 – 20 so performance isn’t much of an issue.

public class SortedObservableCollection<T> : ObservableCollection<T>
{
    private readonly Func<T, int> func;

    public SortedObservableCollection(Func<T, int> func)
    {
        this.func = func;
    }

    public SortedObservableCollection(Func<T, int> func, IEnumerable<T> collection) : base(collection)
    {
        this.func = func;
    }

    public SortedObservableCollection(Func<T, int> func, List<T> list) : base(list)
    {
        this.func = func;
    }

    protected override void InsertItem(int index, T item)
    {
        bool added=false;
        for(int idx=0; idx < Count; idx++)
        {
            if (func(item) < func(Items[idx]))
            {
                base.InsertItem(idx, item);
                added = true;
                break;
            }
        }

        if (!added)
        {
            base.InsertItem(index, item);
        }
    }
}

EDIT: I figured I better add an implementation of this so here goes.  The only requirement here is that you have some int, float double, if you must, field that can be sorted by.

SortedObservableCollection collection = new SortedObservableCollection(i => i.Index)
                                        {
                                            new ObjectWithIntIndexField { Index = 10 },
                                            new ObjectWithIntIndexField { Index = 5 }
                                        };

Bind this collection to some UI list and you’ll find the second object added with an index of 5 is first in the list!

About these ads

7 Responses to SortedObservableCollection

  1. Sebastian says:

    You may also try implementation of the SortedObservableCollection from softcollections.codeplex.com

  2. [...] I googled about this on Bing, and found an implementation of "SortedObservableCollection" which I used – I only changed the int to DateTime, for my needs. What does this mean? This means [...]

  3. Seth says:

    Why on earth would you do a linear search to find the insertion point in a sorted collection…? That’s what binary search is for! (cf. lower_bound in c++)

  4. Anonymous says:

    Nice idea but has a few issues.

    First of all instead of using a Func it might be better to use an IComparer for comparing the order of the items. And if none is supplied then use Comparar.Default.

    Like stated before a binary search would be a better option if the collection is always sorted.

    Then one could argue that this breaks the ObservableCollection’s (or Collection’s) Insert-method, which allows inserting an item in a specific index. Since this class is derived from ObservableCollection, it should be able to be used as such. Now if some functionality receives and instance of this SortedObservableCollection as an ObservableCollection it’s only fair that it should be able to assume that it works like an ObservableCollection (or Collection). Let’s say that functionality wants to insert an item into the 4th index. Now if the instance is in fact this SortedObservableCollection, the item might not go into that 4th index.

  5. Adriaan says:

    Suggestions, change the class to be SortedObservableCollection, then the constructor to

    public SortedObservableCollection(Func func)
    {
    this.func = func;
    }

    using IComparer is also a good idea but the func should work ok, but you do need to consider using index seek instead of scan, especially if the collection will get larger

  6. Adriaan says:

    sorry my previous post dropped the angle brackets, here again:

    Suggestions, change the class to be SortedObservableCollection<T, TKey>, then the constructor to

    public SortedObservableCollection(Func<T, TKey> func)
    {
    this.func = func;
    }

    using IComparer is also a good idea but the func should work ok, but you do need to consider using index seek instead of scan, especially if the collection will get larger

  7. Benlitz says:

    A O(n) insertion isn’t very efficient in a sorted collection… Have you considered using dichotomic search to find the index for insertion? Your implementation is not advisable for large collections (which is my case).
    At least you warn the reader, thanks for that, though most people probably don’t read articles when they look for code snippets :)

Leave a Reply

Fill in your details below or click an icon to log in:

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: