GENERIC COLLECTIONS FOR GENERIC C#
==================================
sestoft@itu.dk * 2001-12-02, 2003-08-11

[NOTE added 26 July 2004: The collection library C5 is a redesigned
and vastly extended and improved descendant of this library; get it
from http://www.itu.dk/research/c5/]

This is an implementation of generic collections for Generic C#.  Only
the most basic operations are provided, but they have the types and
the asymptotic complexity one would expect.  They have not been
systematically tested yet.

The general design is inspired by that of object-based collections in
Java 1.2, which is more complete and has more convenient names than
System.Collections in the .NET Framework.  This may be awkward for
non-technical reasons, but has the virtue that Java programmers can
use the present interfaces and classes with little effort.

Some changes have been made, partly to exploit C#-specific features
such as properties and indexers, and partly because in generic
collections one cannot use the return value null to signify the
absence of a result.  

We first give an overview of the extent of the implementation and then
describe the contracts imposed by interfaces, and the asymptotic
complexity of the implementations, in more detail.


1. OVERVIEW OF THE COLLECTION LIBRARY
=====================================

All these are public members of the namespace GCollections.

Enumeration (iteration)
-----------------------

IEnumerator<T>          produces T values; supports the foreach statement;
IEnumerable<T>          produces an IEnumerator<T>;


Collections
-----------

ICollection<T>          a collection of T elements;
                        extends IEnumerable<T> 

Lists, stacks and queues
------------------------

IList<T>                a collection that preserves insertion order;
                        extends ICollection<T> 
LinkedList<T>           a doubly-linked list implementation; suitable
                        for implementing a queue; implements IList<T>
ArrayList<T>            an array-based list implementation; suitable
                        for implementing a stack; implements IList<T> 

Sets
----
ISet<T>                 a duplicate-free collection of T elements;
                        extends ICollection<T>
ISortedSet<T>           a set whose elements are ordered;
                        extends ISet<T>
HashSet<T>              an unsorted hashtable implementation of sets;
                        implements ISet<T>
TreeSet<T>              a binary tree implementation of sets;
                        implements ISortedSet<T>
OTreeSet<T>             a binary tree using object-based T : IComparable;
                        extends TreeSet<T>
GTreeSet<T>             a binary tree using generic T : IComparable<T>;
                        extends TreeSet<T>


Maps (dictionaries)
-------------------

IMap<K,V>               a map from keys K to data values V;
                        extends ICollection< MapEntry<K,V> >
ISortedMap<K,V>         a map whose keys are ordered;
                        extends IMap<K, V> { }
HashMap<K,V>            an unsorted hashtable implementation of maps;
                        implements IMap<K,V>
TreeMap<K,V>            a sorted binary tree implementation of maps;
                        implements ISortedMap<K,V>                      
OTreeMap<K,V>           a binary tree using object-based K : IComparable;
                        extends TreeMap<K,V>
GTreeMap<K,V>           a binary tree using generic K : IComparable<K>;
                        extends TreeMap<K,V>

MapEntry<K,V>           a struct that is a pair of a key and a value


Comparison
----------

IComparer<T>            three-way comparer of two T values
IComparable<T>          three-way comparison to a T value



2. DETAILED SPECIFICATION OF THE INTERFACES AND CLASSES
=======================================================

The collections are not thread-safe.


The IEnumerator<T> interface (iteration)
----------------------------------------

   public interface IEnumerator<T> : System.Collections.IEnumerator {
     T Current { get; } 
     bool MoveNext();
     void Reset();
   }

   Current returns the current element of the enumerator; throws
   InvalidOperationException before the first call to MoveNext, after
   a call to Reset, and at the end of the enumeration (when MoveNext
   has returned false).

   MoveNext() advances the enumerator; returns true in case there was
   an element to advance to, false if there were no more elements. 

   Reset() resets the enumerator to before the first element.


The IEnumerable<T> interface (iteration)
----------------------------------------

   public interface IEnumerable<T> : System.Collections.IEnumerable { 
     IEnumerator<T> GetEnumerator();
   }

   GetEnumerator() returns an enumerator.  The enumerator adheres to
   the .NET conventions.  Thus an enumerator created from a collection
   fails early (by MoveNext throwing InvalidOperationException) if the
   underlying collection has been (structurally) modified.  Creating
   an enumerator from a collection is a constant time operation.


The ICollections<T> interface
-----------------------------

   public interface ICollection<T> : IEnumerable<T> { 
     int Count { get; }
   }

   Count returns the number of elements in the collection.  This is a
   constant-time operation.

   All collection classes override the methods GetHashCode() and
   Equals(object) inherited from class object, calling the
   GetHashCode() and Equals(object) methods of their elements as
   further specified below.


The IList<T> interface
----------------------

   public interface IList<T> : ICollection<T> {
     bool Add(T item);
     bool Add(int i, T item);
     T Remove();
     T RemoveAt(int i);
     T Remove(T item);
     bool Contains(T item);        // using Equals from object
     T this[int index] { get; set; }
   }

   An IList<T> is a collection of T elements that preserves insertion
   order.  The implementing classes LinkedList<T> and ArrayList<T> are
   well-suited for implementing double-ended queues (fifo buffers) and
   stacks (lifo buffers) respectively.

   Add(t) adds t to the end of the list; this is a constant-time
   operation.  Returns true.

   Add(i, t) inserts t before position i in the list, counting from 0.
   Returns true.  Throws IndexOutOfRangeException unless 0<=i<=Count.

   Remove() removes and returns an element of the list.  Generally
   takes the elements that is cheapest to remove: the first element of
   a LinkedList, the element of an ArrayList.  Take constant time.
   Throws IndexOutOfRangeException if the list is empty.

   RemoveAt(i) removes and returns element number i in the list,
   counting from zero.  Throws IndexOutOfRangeException unless
   0<=i<Count.  

   Remove(t) evaluates x.Equals(t) for each list element x in order,
   until this gives true or there are no more elements.  Returns x and
   removes it from the list is the former case, throws
   ElementNotFoundException in the latter case.

   Contains(t) evaluates x.Equals(t) for each list element x in order,
   until this gives true or there are no more elements.  Returns true
   in the former case, false in the latter.

   lst[i] returns element number i of lst; it may be used as a lvalue
   (assigned).  Throws IndexOutOfRangeException unless 0<=i<Count.

   GetHashCode() returns the hashcode of the list, computed from the
   hashcodes h1, h2, ..., hn of the list elements by 
     (... (h1 * 31 + h2) * 31 + ... ) * 31 + hn

   Equals(lst2) returns false if lst2 is not an IList<T> or if does
   not have Count elements.  Otherwise, evaluates x.Equals(y), drawing
   elements x from this list and y from lst2 in order, until it gives 
   false or there are no more elements.  Returns false in the former case, 
   and true in the latter.

   GetEnumerator() returns an enumerator over the list, which produces
   the elements in their list order.


The LinkedList<T> class
-----------------------

   public class LinkedList<T> : IList<T> { 
     ... 
     public LinkedList();
     public bool AddLast(T item);
     public bool AddFirst(T item);
     public bool RemoveFirst();
     public bool RemoveLast();
   }

   A LinkedList<T> is an implementation of IList<T> as a doubly-linked
   list.  It is well-suited for implementing double-ended queues (fifo
   buffers), because Add inserts elements at the end, and Remove takes
   them off the front of the list.

   new LinkedList() returns an empty list.

   Add(t) adds t to the end of the list.  Takes constant time.

   AddLast(t) is the same.

   Add(i, t) inserts t before position i in the list, counting from 0.
   Throws IndexOutOfRangeException unless 0<=i<=Count.  Takes time
   O(min(i, Count-i)).

   AddFirst(t) is Add(0, t).  Takes constant time.

   Remove() removes and returns the first element of the list; throws
   IndexOutOfRangeException if the list is empty.  Takes constant time.

   RemoveFirst() is the same.

   RemoveAt(i) removes and returns element number i in the list,
   counting from zero.  Throws IndexOutOfRangeException unless
   0<=i<Count.  Takes time O(min(i, Count-i)).

   RemoveLast() is Remove(Count-1).  Takes constant time.

   Remove(t) evaluates x.Equals(t) for each list element x in order,
   until this gives true or there are no more elements.  Returns x and
   removes it from the list is the former case, throws
   ElementNotFoundException in the latter case.

   Contains(t) searches the list from element number 0 and evaluates
   x.Equals(t) until this gives true, or there are no more elements;
   returns true in the former case, false in the latter.  Takes time
   O(Count).

   lst[i] returns element number i of lst, counting from 0.  Throws
   IndexOutOfRangeException unless 0<=i<Count.  
   Takes time O(min(i, Count-i)).   (The indexer is used as rvalue).

   lst[i] = v replaces element number i of lst by v.  Throws
   IndexOutOfRangeException unless 0<=i<Count.  
   Takes time O(min(i, Count-i)).  (The indexer is used as lvalue).


The ArrayList<T> class
----------------------

   public class ArrayList<T> : IList<T> {
      ... 
      public ArrayList();
      public bool AddLast(T item);
   }

   An ArrayList<T> is an implementation of IList<T> using an
   underlying array.  It is well-suited for implementing stacks (lifo
   buffers), because Add inserts elements at the end, and Remove takes
   them off the end also.

   new ArrayList() returns an empty list.

   Add(t) adds t to the end of the list.  Takes constant time.

   AddLast(t) is the same.

   Add(i, t) inserts t before position i in the list, counting from 0.
   Throws IndexOutOfRangeException unless 0<=i<=Count.  Takes time
   O(Count-i).

   Remove() removes and returns the last element of the list; throws
   IndexOutOfRangeException if the list is empty.  Takes constant
   time.

   RemoveAt(i) removes and returns element number i in the list,
   counting from zero.  Throws IndexOutOfRangeException unless
   0<=i<Count.  Takes time O(Count-i).

   RemoveLast(i) is Remove(Count-1).  Takes constant time.

   Remove(t) evaluates x.Equals(t) for each list element x in order,
   until this gives true or there are no more elements.  Returns x and
   removes it from the list is the former case, throws
   ElementNotFoundException in the latter case.

   Contains(t) evaluates x.Equals(t) for each list element x in order,
   until this gives true or there are no more elements.  Returns true
   in the former case, false in the latter.  Takes time O(Count).

   lst[i] returns element number i of lst, counting from 0.  Throws
   IndexOutOfRangeException unless 0<=i<Count.  Takes constant time.
   (The indexer is used as rvalue).

   lst[i] = v replaces element number i of lst by v.  Throws
   IndexOutOfRangeException unless 0<=i<Count.  Takes constant time.
   (The indexer is used as lvalue).


The ISet<T> interface
---------------------

   public interface ISet<T> : ICollection<T> {
     bool Add(T item);             // return true if item was added
     T Remove(T item);             // return removed item
     bool Contains(T item);
   }

   An ISet<T> is a duplicate-free collection of T elements.  The
   concept of element equality (and thus the notion of `duplicate')
   depend on what kind of set is considered.  A HashSet uses the
   element's Equals method inherited from object.  A SortedSet uses
   some form of element ordering (three-way comparison).  
      Iteration over the collection is done in some order determined
   by the representation; for ISortedSets it is in element order.

   Add(t) attempts to add t to the set.  Returns true if t was added,
   false if t was in the set already.  

   Remove(t) attempts to remove t from the set.  If there is some
   element x in the set for which x.Equals(t), returns x; otherwise
   throws ElementNotFoundException.

   Contains(t) returns true if there is some element x in the set for
   which x.Equals(t); otherwise returns false.

   Equals(set2) returns false if set2 is not an ISet<T> or if set2
   does not have Count elements.  Otherwise checks that every element
   of this set is in set2; returns true if so, otherwise false.

   GetHashCode() returns the sum of the hashcodes of the set's
   elements.


The HashSet<T> class
--------------------

   public class HashSet<T> : ISet<T> { ... }

   A HashSet<T> relies on the GetHashCode() and Equals(object) methods
   of the element type T.  These must satisfy x.Equals(y) implies
   x.GetHashCode() = y.GetHashCode() as usual.  Methods Remove and
   Contains take constant time.  Method Add takes amortized constant
   time.

   Note that because these object-based functions are used, HashSet<T>
   will be no more (and no less) efficient for primitive types than
   object-based hashtables.  In fact, currently the implementation
   uses the .NET Framework System.Collections.Hashtable. 


The ISortedSet<T> interface
---------------------------

   public interface ISortedSet<T> : ISet<T> { }

   An ISortedSet<T> is a set whose elements T are ordered, either
   because T implements object-based IComparable (OTreeSet), or
   because T implements IComparable<T>, or because an explicit
   comparer method was provided for T when the set was created.

   Enumeration of an ISortedSet produces its elements according to the
   ordering on T.


The IComparer<T> interface
--------------------------

   public interface IComparer<T> {
     int Compare(T v1, T v2);
   }

   Compare(v1, v2) must return a negative number if v1 is less than
   v2, zero if v1 equals v2, and a positive number if v1 is greater
   than v2.  This is a typed version of System.Collections.IComparer.


The IComparable<T> interface
----------------------------

   public interface IComparable<T> {
     int CompareTo(T that);
   }

   v1.CompareTo(v2) must return a negative number if v1 is less than
   v2, zero if v1 equals v2, and a positive number if v1 is greater
   than v2.  This is a typed version of System.IComparable.


The TreeSet<T> class
--------------------

   public class TreeSet<T> : ISortedSet<T> {
     public TreeSet(System.Collections.IComparer comparer);
     public TreeSet(IComparer<T> comparer) 
     ...
   }

   A TreeSet<T> is an ISortedSet<T> implemented using red-black
   balanced ordered binary trees.  Operations Add, Remove and Contains
   all take time O(log n) where n is the size of the set.  
      The elements T must be ordered.  The element ordering can be
   specified in one of four different ways:
     
   1. Type T implements object-based System.IComparable.
      Use subclass OTreeSet<T : System.IComparable>

   2. Type T implements generic IComparable<T>.
      Use subclass GTreeSet<T : IComparable<T>>

   3. An explicit object-based comparer System.Collections.IComparer
      is given when the set is created.
      Use the TreeSet constructor TreeSet<T>(System.Collections.IComparer)

   4. An explicit generic comparer IComparer<T> is given when the set
      is created.
      Use the TreeSet constructor TreeSet<T>(IComparer<T>)

   
The IMap<K,V> interface
-----------------------

   public interface IMap<K,V> : ICollection< MapEntry<K,V> > {
     bool Add(K key, V val);
     MapEntry<K,V> Remove(K key);
     V this[K key] { get; set; }
     bool Contains(K key);
   }

   An IMap<K,V> is a mapping (dictionary) from keys of type K to
   values of type V.  A pair (k,v) in a mapping is called an entry.  A
   map cannot contain duplicate entries (k, v1) and (k, v2) for the
   same key k.  The concept of key equality (and thus the notion of
   `duplicate') depend on what kind of map is considered.  A HashMap
   uses the key's Equals method inherited from object.  A SortedMap
   uses some form of key ordering (three-way comparison).

   Count returns the number of entries in the map.  This takes
   constant time.

   Add(k, v) adds the entry (k,v) to the map if it is not there
   already, in which case it returns true; otherwise it returns false
   and leave the map unchanged.

   Remove(k) attempts to an entry with key k from the map.  If there
   is some entry (x,y) in the map for which x equals k, returns (x,y);
   otherwise throws ElementNotFoundException.

   Contains(k) returns true if the map contains an entry (x,y) for
   which x equals k, otherwise false.

   map[k] returns the value associated with key k if any, otherwise
   throws ElementNotFoundException.  (The indexer is used as rvalue).

   map[k] = v replaces the value associated with key k with v, if any
   value was associated with k; otherwise adds the entry (k,v) to the
   map.  (The indexer is used as lvalue).

   GetHashCode() returns the sum of the hashcodes of the entries in
   the map.

   Equals(map2) returns false if map2 is not an IMap<K,V> or does not
   have Count entries.  Otherwise checks that every entry in this map
   is in map2; returns true if so, otherwise false.

   GetEnumerator() returns an enumerator that produces all the map's
   entries, as MapEntry<K,V> structs. 


The MapEntry<K,V> struct
------------------------

   public struct MapEntry<K,V> {
     public MapEntry(K key, V val);
     public K Key { get; }
     public V Value { get; }
   }

   A MapEntry<K,V> is a pair of a key and a value.

   new MapEntry<K,V>(k,v) produces the entry (k,v).

   Key is the key k in an entry (k,v).

   Value is the value v in an entry (k,v).


The HashMap<K,V> class
----------------------

   public class HashMap<K,V> : IMap<K,V> { ... }

   A HashMap<K,V> relies on the GetHashCode() and Equals(object)
   methods of the key type K.  These must satisfy x.Equals(y) implies
   x.GetHashCode() = y.GetHashCode() as usual.  Methods Remove and
   Contains take constant time.  Method Add takes amortized constant
   time.

   Note that because these object-based functions are used,
   HashMap<K,V> will be no more (and no less) efficient for primitive
   types than object-based hashtables.  In fact, currently the
   implementation uses the .NET Framework System.Collections.Hashtable.


The ISortedMap<K,V> interface
-----------------------------

   public interface ISortedMap<K, V> : IMap<K, V> { }

   An ISortedMap<K,V> is a map whose entries are ordered, either
   because the keys K implement object-based IComparable (OTreeMap),
   or because K implements IComparable<K>, or because an explicit
   comparer method was provided for K when the map was created.

   Enumeration of an ISortedMap produces its entries according to the
   ordering on T.


The TreeMap<K,V> class
----------------------

   public class TreeMap<K, V> : ISortedMap<K,V> {
     public TreeMap(System.Collections.IComparer comparer);
     public TreeMap(IComparer<K> comparer);
     ...
   }

   A TreeMap<K,V> is an ISortedMap<K,V> implemented using red-black
   balanced ordered binary trees.  Operations Add, Remove, Contains,
   map[k] and map[k] = v all take time O(log n) where n is the number
   of entries in the map.  
      The keys K must be ordered.  The key ordering can be specified
   in one of four different ways:
     
   1. Type K implements object-based System.IComparable.
      Use subclass OTreeMap<K : System.IComparable, V>

   2. Type K implements generic IComparable<K>.
      Use subclass GTreeMap<K : IComparable<K>>

   3. An explicit object-based comparer System.Collections.IComparer
      is given when the map is created.
      Use the TreeMap constructor TreeMap<K,V>(System.Collections.IComparer)

   4. An explicit generic comparer IComparer<K> is given when the map
      is created.
      Use the TreeSet constructor TreeMap<K,V>(IComparer<T>)