Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Collection Libraries Design Principles Unusual Functionality A Convex Hull Example A Multidictionary Example Implementation Challenges

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.

Previous Page | 1 Collection Libraries | 2 Design Principles | 3 Unusual Functionality | 4 A Convex Hull Example | 5 A Multidictionary Example | 6 Implementation Challenges Next Page

RELATED ARTICLES recls 100% .NET		TOP 5 ARTICLES No Top Articles.