C5 User's guide for prerelease version 0.5

Table of contents

• C5 User's guide for prerelease version 0.5
  • Table of contents
• Overview
• Interfaces
  • "Proper" collection interfaces
  • Dictionary interfaces
  • Query result interfaces
• To construct a collection
  • To use an external hasher
  • To use an external comparer
  • To make collections of collections
• Special topics
  • To choose a set or bag collection
  • To work on part of a list: list views
  • To work with persistent red-black trees
  • To implement new collection classes or subclass an existing one
  • To present a read only view of a collection
• Collection classes by data structure/class
• Planned architecture or interface changes for first release
• Performance details for proper collection classes
• Performance details for dictionary classes

Overview

C5 is a comprehensive library of collection classes for the Common Language Infrastructure (CLI). This guide describes prerelease version 0.5 of  C5.

C5 is a refactoring and extension of the generic collection classes developed by Peter Sestoft while visiting Microsoft Research in Cambridge.

Unless stated otherwise types mentioned below will belong to the "C5" namespace; and all code examples assume a "using C5;" clause (and no "using System.Collection.Generics;" clause).. 

The goals in the development of the library has been

• To create a library of collection classes for the CLI that can assist expert and non-expert programmers on the platform to develop correct and efficient applications.

• The library should at least fill the gaps in the standard “System.Collections.Generics” namespace compared to standard collection class libraries for related object oriented languages like Java, and utilize the new facilities for generic programming. Microsoft recently (mid 2004) seems to have changed their minds and ntend to bridge that gap in the beta2 version of VS 2005 due at the end of 2004.

In order to fulfill the efficiency goal, the library utilizes first-class data structures inside its collection classes. The library has been constructed with the modern object oriented programming principle of  "code to interfaces, not to implementations" in mind, while the interface architecture has been carefully crafted to reflect the efficient data structures actually existence.

A collection in the sense of this library is a plain "collection of items of a single type". A collection does not impose any other logical structure on its items than perhaps uniqueness or sequence ordering.

The main division line among the collection classes of this library is the distinction between "proper" collections and dictionaries. A dictionary is a class that defines a partial function (or map) from one item type (the keys) to another one (the values). A dictionary can be viewed as a collection of (key,value) pairs having the property of defining a partial function.

The item type for the collection classes are always given by generic parameters. For a proper collection, there will be a single parameter, customarily called T, as in HashSet<T>. For a dictionary there will be two - the key and value types - as in HashDictionary<K,V>.

A collection class, or rather the data structure inside, can be either equality based or comparison based. An equality based collection will have an associated so-called hasher of type IHasher<T>, where T is the item type of the collection. A comparison based collection has an associated comparer of type IComparer<T>. The section below on creation of collection classes explains how the hashers and comparers are chosen. NB: this design will be modified soon, cf. Planned changes.

Collection classes in the library have either set or bag semantics. A set collection can at most contain one copy of an item, while bag collections may contain several. One can programmatically see at runtime if an editable collection class has set or bag semantics by checking the AllowsDuplicates property. At compile time, refer to the set or bag table below for an overview.

Interfaces

The C5 library is designed to make it easy to program to interfaces instead of implementations. In particular, all public properties and methods of the collection classes belong to their implemented interfaces (except for the odd special diagnostic method and the odd mistake to be weeded out before release). The typical programming style would be

IList<int> lst = new LinkedList<int>();
lst.Add(7);

instead of 

LinkedList<int> lst = new LinkedList<int>();
lst.Add(7);

Note that with this programming style, the Add call will be compiled to an interface call instead of a (virtual) method call, but interface calls on the CLR (at least the Microsoft implementation) are at most very slightly slower than virtual calls, so one should not shun the interface style for performance reasons.

We will discuss the collection classes available in C5 structured according to the main functional interfaces of the proper collections, the dictionaries and the interfaces of query results.

"Proper" collection interfaces

The following diagam shows the type hierarchy of the proper collection classes:

The most important interfaces - those that are directly implemented by collection classes - are listed to the left in this table with a short description in the middle and all implementing classes to the right. 

Please see also the complete complexity table for more comprehensive guidance.

To identify which classes are hasher or comparer based and which classes implement set or bag we use the following symbols:

Dictionary interfaces

There are two dictionary interfaces:

Query result interfaces

Some of the most basic collection interfaces have an important usage as the types of results of queries to collections, although these interfaces also appear at the base of the other collection interfaces and even as the types of synthetic collections. The interfaces in question are the standard System.Collections.Generics.IEnumerable<T>, ICollectionValue<T>, IDirectedEnumerable<T> and IDirectedCollectionValue<T>.

The differences between the "Enumerable" and "Collection" variants are that the "Enumerable" variant only knows how to enumerate through its items, the "Collection" variants also knows how many items it has (without having to walk through an enumeration). The "Directed" variants are used for results of queries to sequenced collections (implementing ISequenced<T>) and therefore have a non-implementation dependent enumeration order. The "Directed" variants supports two operations, Backwards() to enable enumeration in the opposite direction and Direction to tell if the enumeration order is forwards or backwards with respect to the original collection.

Note: operations on an enumerator created by the GetEnumerator() method on System.Collections.Generics.IEnumerable<T> cannot be interleaved with update operations on the underlying collection.

Note: for all enumerators in the library the operations have O(1) amortized complexity.

To construct a collection

All collections classes in C5 have (zero parameter) default constructors. So if we want to make a linked list of items of some type, TheType, and add an item to the list we will do

    IList<TheType> lst = new LinkedList<TheType>();
    TheType t = ...;
    lst.Add(t);

The collection classes have no constructors that will take an array or a collection as parameter for prepopulating the collection, use the AddAll method instead. NB: in the released version, expect constructors with an enumerable as argument and constructors with a variable number of arguments ("params") for the initialization of the collection, see the planned changes section.

Some collection classes are governed by internal parameters that one can give non-default values at creation time (fill in HashSet<T>,  HashBag<T>, HashDictionary<K,V>) or use internal tables that one can expand in advance if one has expectations of how large the collection will grow (HashSet<T>,  HashBag<T>, HashDictionary<K,V>, ArrayList<T>, HashedArrayList<T>, SortedArray<T>, IntervalHeap<T>).

For equality-based collection classes, these constructors will use a default hasher to define equality of items according to the following table:

For comparison-based collection classes, these constructors will use a default comparer:

Sometimes, the default hasher or comparer is not the right one for the problem at hand. In that case one must get hold on a hasher or comparer of the right kind and supply it to one of the constructors of the collection classes that supports such a parameter. The procedure is demonstrated in the sections below on external hashers, external comparers and collections as items.

NB: in the released version, expect the hashers and comparers to be of the System.Collections.Generics.IComparer<T> type, see the planned changes section.

To use an external hasher

In addition to the helper classes referenced above, the library has the helper class KeyValuePairHasher<K,V> to construct a hasher for pairs of the type KeyValuePair<K,V>, the type of entry of a K to V dictionary. The constructed hasher will only take the first component of the pair into account. We can use these classes in the following way to make a linked list (with hash index) of pairs of strings identified by their first components using some custom hasher on strings:

IHasher<string> csh = ...;
IHasher<KeyValuePair<string,string>> cph = 
              new KeyValuePairHasher<string,string>(csh);
IList<KeyValuePair<string,string>> lst =
                           new HashedLinkedList<KeyValuePair<string,string>>(cph);
lst.Add(new KeyValuePair<string,string>("abe","kat"));

One may, of course, program a hasher oneself. This one should always do if the item type is defined as a struct (value type) that does not override the Equals and GetHashCode methods of object, since in that case the default hasher will use the slow default versions of those methods supplied by the runtime via reflection. 

To use an external comparer

There is a helper class for comparer of pairs: KeyValuePairComparer<K,V>. We will show an example of a custom comparer. Imagine wanting to compare double precision floating point numbers with a tolerance. The following code snippet shows how one could make a tree set out of such numbers:

class DC : IComparer<double> {
   const double eps = 1E-10;
   int Compare(double a, double b) 
      {return a > b + eps ? 1 : a < b - eps ? -1 : 0;}
}

void dowork() {
   IComparer<double> dc = new DC();
   ISorted<double> tree = new TreeSet<double>(dc);
   tree.Add(3.45);
   ...
}

In this particular case, one would have to make sure, that two different floating point numbers are only identified by the comparer if they really should represent the same value and not by coincidence.

To make collections of collections

When one wants to use a collection whose items itself are of collection type, one usually wants the interior collections to be identified by contents - either according to or irrespective of sequence order. An example could be transformations of Finite Automatons. The default hashers and the HasherBuilder classes mentioned above may help to construct such collections of collections as in the examples that follow:

To make an array list of sequenced collections identified by contents in sequenced fashion one would simply do:

ArrayList<ISequenced<int>> lst = new ArrayList<ISequenced<int>>();

To make a linked list of linked lists identified by contents unsequenced, explicitly construct the collection hasher:

IHasher<LinkedList<int>> lsth =
     new HasherBuilder.UnsequencedHasher<int,LinkedList<int>>();
LinkedList<LinkedList<int>> lst =
   new LinkedList<LinkedList<int>>(lsth);

If for some strange reason one would like to make a hash set of linked lists with the lists identified by reference equality one would simply do:

HashSet<LinkedList<int>> lst = new HashSet<LinkedList<int>>();

If for even stranger reasons one would make a hash set of ISequenced<int> collections with the collections identified by reference equality one would do like this:

IHasher<ISequenced<int>> lsth =
      new DefaultReferenceTypeHasher<ISequenced<int>>();
HashSet<ISequenced<int>> lst =
   new HashSet<ISequenced<int>>(lsth);

Special topics

To choose a set or bag collection

The following table shows which of the collection classes have set semantics and which have bag semantics. All the implemented classes have fixed, compiled in semantics.

Note: when in a set collection, methods with an Add in the name will ignore attempts to add an item already there or flag the failed attempt by a Boolean return value; methods with an Insert in the name (only in lists) will throw an exception.

To work on part of a list: list views

The IList<T> interface supports via the View method the functionality that one can zoom in on part of a list and use it as an IList<T> in its own right while having updates to the view passed through to the base (original) IList<T>. Using the Slide method calls, one may move the view around the base list. Using Slide repeatedly one can implement safe ways to iterate over a list while updating it. The IList<T> interface also has properties Underlying and Offset showing the base list of a view and the current site of a view.

One can create a view on a view, but the new view will have the original base list as base. A view will be invalidated if an update operation is performed on the base list by any other means than through this particular view.

The following code snippet shows a silly example of iterating over a list, doing an insertion each time certain combination of items are seen (the example iterates right to left and inserts 666 whenever two consecutive items have an odd difference):

IList<int> lst = ...;
IList<int> view = lst.CreateView(lst.Count-2, 2);
while (true) {
    if ((view.Last - view.First) % 2 == 1)
        view.Insert(1, 666);
    if (view.Offset == 0)
        break;
    else
        view.Slide(-1,2);
}

To work with persistent red-black trees

The search tree implementation in the library is based on node copy persistent red-black trees. The persistence is exposed in the Snapshot method that can be considered a very fast and space-saving way of making a read-only clone of the tree. When using persistence, the space use of a red-black tree in this implementation is linear in the number of operations since the creation of the tree.

One use of persistence could be to safely enumerate a tree interleaved with updates:

IPersistentSorted<int> tree = new TreeSet<int>();
tree.Add(5);
...
ISorted<int> snap = tree.Snapshot();
foreach (int i in snap)
    tree.Add(i+7);

The GUITester project of the complete library source code contains an interesting (standard) usage of persistent search trees to the geometric problem of constructing an efficient data structure for point location in a division of the plane given by a list of line segments.

To implement new collection classes or subclass an existing one

All interface methods and properties of the collection classes implemented in the library are virtual and so it should be safe to subclass these classes. Some classes may have protected members if they are subclassed in the library itself. We refer to the detailed reference manuals and the library source for information on the protected members and their role in subclassing.

There is a sequence of helper classes designed to be used as base classes of collection classes: EnumerableBase<T>, CollectionValueBase<T>, CollectionBase<T>, SequencedBase<T> and ArrayBase<T>. Please see the reference manual and the library source code for documentation and examples.

As for dictionaries, the DictionaryBase<K,V> class will construct a class implementing IDictionary<K,V> by simply plugging in a set implementation.

To present a read only view of a collection

The library contains a long list of wrapper classes all with name starting with Guarded having the purpose of creating a read-only view of an existing collection. The wrapping is done by the constructors of the classes. If we want to give some code access to only lookup operations on a, say, list we can do as follows:

IList<int> lst;
...
IList<int> rolst = new GList<int>(lst);
OtherObject.dowork(rolst);

Please see the reference manual for details on available wrapper classes.

Collection classes by data structure/class

The following table shows the underlying data structure of the various collection classes.

<>Planned architecture or interface changes for first release

1. Eliminate the use of our own generic equality/comparator types, C5.IComparer<T> and C5.IHasher<T> and use the new design of VS 2005 beta1 in the form of the combined System.Collections.Generic.IComparer<T>.
2. Vararg (params) constructors? (And IEnum do.)
3. Possibly extended use of "wildcard style" operations like AddAll<U>(IEnumerable<U> items)?
4. Make all collection classes clonable and serializable.

Performance details for proper collection classes

This section overviews the complexities of cc public methods and property accesses.

In the table below, for lack of space we use the following numbers to identify collection classes:

And the following special symbols: 

n size of collection, 
m size of argument if collection-: not supported
*: means: suboptimal complexity (library is in error)
$: special at end: the operation is much faster at the start and/or end (end for array list, both for linked list)

Note: we do not show return type  or parameters for methods, just mark with ()
Note: we ignore time for reclaiming of internal array space (e.g. Clear)
User supplied operations like comparers or hashers are assumed to be O(1)

Performance details for dictionary classes