Monday, October 15, 2007

Sorted dictionary class for Silverlight

Yes, Silverlight 1.1 is far from being perfect. It's lack of some very important classes. The good example for it is SortedDictionary and binary search tree. Why it's so important and what top-down (red-black) binary search trees are?

If you want to use generic dictionary not only for storing key-value information, but also for searching and accessing data by other criteria,  you, probably, can implement IComparable interface and for each new data entry or update resort whole list. But, if you are looking not only for such functionality, but, also, for performance, you'd like to use black-red trees to achieve the behavior.  So, what we really have?

  • Our data exists in Key-Value pairs
  • Total order of items is predefined
  • We can sort by such criteria keys and values and not only keys.

All those features are defined by Binary Search Tree (or BST). But SortedDictionary is maintaining not only those trees, but, also, the criteria or, other words, the order. It also uses sequential algorithm to locate keys. SortedList has linear search time, as the last key in the list will require comparisons to every preceding key, so item insertion, removal and retrieval time will be O(log n) contrasts SortedList, that inserts and removes items with O(n) time and lookup O(log n). So, it's obvious, that SortedDictionary works much faster with large amount of frequent changing data. However, it uses much more objects on heap, due to fact, that all of it's items are linked together with tree, wrapped in a Node (that internally implemented reference type)

Each application should choose what type of sorted collections to use, however, it's really important to understand, that even in SL application, we should have SortedDictionary class.

I got shared source CLI for 2.0 (ECMA CLI and C# for XP), which is freely available through MSDN and wrap and fix SortedDictionary class to be used within Silverlight constraints. So, if you need such class in your Silverlight application, download it here.

No comments: