Here's my initial thinking on the design of OrderedDictionary. As mentioned earlier, OrderedDictionary maintains a dictionary of key-value pairs, sorted by the key value. It is implemented internally as a balanced binary tree, and adding, removing, and testing for containment are all guaranteed log(N) operations.

I hope that the semantics of most of the methods are pretty clear. I'll be provided more detailed documentation along with the implementation.

public class OrderedDictionary<KeyType, ValueType> : IDictionary<KeyType,ValueType>, IDictionary, ICloneable
{
  // Constructors
  public OrderedDictionary(); // KeyType must implement IComparable or IComparable
  public OrderedDictionary(IComparer comparer); // ordering via IComparer
  public OrderedDictionary(Ordering ordering); // ordering via an Ordering delegate

  // Cloning
  public OrderedDictionary<KeyType,ValueType> Clone(); // shallow clone
  public OrderedDictionary<KeyType,ValueType> CloneContents(); // clones keys and values also

  // Removing keys
  public void Clear();
  public bool Remove(KeyType key);

  // Adding key/values, updating values for existing key
  public void Add(KeyType key, ValueType value); // never updates, but adds only
  public void Update(KeyType key, ValueType value); // nevers adds, but updates existing key only
  public bool AddOrUpdate(KeyType key, ValueType value); // like this[], but returns bool indicate add vs. update
  public bool FindOrAdd(KeyType key, ref ValueType value); // if key already there, returns old value, else adds new value
  public ValueType this[KeyType key] {get; set; } // adds or updates

  // Combining with other collections
  public void MergeDictionary(IDictionary<KeyType.ValueType> dictionary); // add/update everything in the dictionary
  public void RemoveCollection(IEnumerable<KeyType> keys); // removes all these keys

  // Testing for containment.
  public bool ContainsKey(KeyType key);
  public bool TryGetValue(KeyType key, out ValueType value); // test for containment and retrieve in one operation

  // View just keys or values as a collections
  public ICollection<KeyType> Keys { get; }
  public ICollection<ValueType> Values { get; }

  // Miscellaneous collection/enumeration stuff
  public int Count { get; }
  public void CopyTo(KeyValuePair<KeyType,ValueType>[] array, int arrayIndex);
  public IEnumerator<KeyValuePair<KeyType,ValueType>> GetEnumerator();

  // Sub-views. For example: foreach (string key in dict.Range(x,y).Reversed().Keys)
  public View Reversed(); // A reversed view that can be enumerated
  public View Range(KeyType from, KeyType to); // A partial view that can be enumerated
  public View RangeFrom(KeyType from); // A partial view that can be enumerated
  public View RangeTo(KeyType to); // A partial view that can be enumerated

  // This nested class is for views returned by Reversed and Range
  public class View : IEnumerable<KeyValuePair<KeyType,ValueType>>
  {
    public IEnumerator<KeyValuePair<KeyType,ValueType>> GetEnumerator();
    public int Count {get; }
    public void CopyTo(KeyValuePair<KeyType,ValueType>[] array, int arrayIndex);
    public View Reversed();
    public IEnumerable<KeyType> Keys { get;}
    public IEnumerable<ValueType> Values { get; }
  }
}

// A delegate that defines an ordering between elements. Easier to use that IComparable.
public delegate int Ordering<ElementType>(ElementType e1, ElementType e2);

Notable design points:

1. OrderedDictionary implements both the generic and non-generic IDictionary, for better interoperability. Most of the implementation of the non-generic IDictionary is via implicit interface implementation.

2. How elements are compared can be specified by using one of the three constructors. If the parameterless constructor is used, then KeyType must have an implicit ordering by implementing either IComparable or IComparable. To use an different ordering, either an IComparer can be supplied, or a comparision delegate (Ordering). Using a delegate is very convenient with C# 2.0's anonymous delegate feature.

3. Both shallow cloning and “deep” cloning (cloning the elements) is provided. Shallow cloning is the implementation of ICloneable. “Deep” cloning requires that KeyType and ValueType both implement ICloneable or are value types.

4. I tried to provide a lot of permutations of add/update functionality, and avoid double lookups (testing for containment first). But it almost seems like too many methods that will be confusing. Can this be simplified without losing important functionality?

5. There's no constructor that takes an existing IDictionary; I thought this would lead to too many constructors. Instead, MergeDictionary can be used after construction to add the contents of a dictionary?

6. Should MergeDictionary and RemoveCollection also take non-generic collections? I worry that this will lead to ambiguity errors when they are being used.

7. A sub-view functionality allows iterating over parts of the dictionary, in either forward or reverse order. For example, you can iterate just the Key/Values beginning with “N” by doing:

foreach (KeyValuePair pair in dict.Range(”N”, “O”))

and in reverse order via:

foreach (KeyValuePair pair in dict.Range(”N”, “O”).Reversed())

Views do not copy the actual data; they just provide alternate iteration orders.