Design Principles
For starters, we studied existing Java and Smalltalk collection libraries and drew up a list of design objectives:
- The library should provide well-known collection abstractions such as lists, sets, bags (multisets), priority queues, double-ended queues, stacks, and dictionaries (finite maps).
- The library should provide standard implementations of these, using data structures such as array lists, doubly linked lists, hash-based and comparer-based collections, and interval heaps.
- Functionality should be orthogonal so that it can be freely combined.
- The library should provide convenient but hard-to-implement functionality, such as persistent sorted collections and sublist views on hash-indexed linked lists.
- The library should fit with existing C# concepts such as enumerables, the foreach statement, and events, and make good use of C# 2.0 features such as generic types and methods, the yield statement (iterator methods), nullable value types, and anonymous methods.
- The functionality of a collection class should be completely characterized by the interfaces it implements. This permits "programming to interface, not to implementation." For instance, the classes ArrayList<T> and LinkedList<T> have the same functionality and implement the same interfaces.
- Good asymptotic complexity is more important than nanosecond efficiency. Thus, existing operations on .NET's standard array list List<T> may be faster by a constant factor than operations on C5 ArrayList<T>, but other operations may simply be nonexistent, and therefore not efficiently implementable on List<T>.
- The library should be tested and documented well enough to be widely usable. This includes documentation of the asymptotic running time of each operation on each collection implementation.
Figures 1 and 2 show the inheritance hierarchies of the collection types and dictionary types.
[Click image to view at full size]
Figure 1: The collection type hierarchy.
Figure 2: The dictionary type hierarchy.
