A KeyedList implementation

• Download source files - 2 Kb

Introduction

A KeyedList is an ordered key-value list.  In comparison:

• Hashtable is a key-value list that is not ordered;
• SortedList is a key-value list that is sorted;
• ArrayList is an ordered list.

but in the System.Collections namespace, there is nothing that implements an ordered key-value list.

Hasn't Someone Done This Before?

For some reason, Microsoft has decided to implement a KeyedList as part System.Web.UI namespace.  Refer to this preliminary MSDN documentation which is part of Longhorn.  What's up with implementing this in System.Web.UI?  What I need is a KeyedList that is platform independent!  Googling a bit more, I came across a code implementation from the Mono project, here and here. 

The Implementation

The following code takes that implementation, written by Todd Berman, removes the IStateManager interface and places the implementation into the System.Collections namespace, rather than System.Web.UI. Rocket science this isn't, but since I didn't find any KeyedList articles on CP, I figured here would be a good place to put this valuable class.  The KeyedList is also derived from the interfaces specified in the Longhorn MSDN rather than the interfaces used in the Mono implementation.  All told, I think I spent more time Googling for an ordered Hashtable than I did extracting the code from the Mono links previously mentioned and slightly modifying them!

using System;
using System.Collections;

namespace System.Collections
{
 public interface IOrderedDictionary
 {
  void Insert(Int32 index, Object key, Object value);
  void RemoveAt(Int32 index);
 }

 [Serializable]
 public class KeyedList : 
    ICollection, IDictionary, IEnumerable, IOrderedDictionary
 {
  private Hashtable objectTable = new Hashtable ();
  private ArrayList objectList = new ArrayList ();

  public void Add (object key, object value)
  {
   objectTable.Add (key, value);
   objectList.Add (new DictionaryEntry (key, value));
  }

  public void Clear ()
  {
   objectTable.Clear ();
   objectList.Clear ();
  }

  public bool Contains (object key)
  {
   return objectTable.Contains (key);
  }

  public void CopyTo (Array array, int idx)
  {
   objectTable.CopyTo (array, idx);
  }

  public void Insert (int idx, object key, object value)
  {
   if (idx > Count)
    throw new ArgumentOutOfRangeException ("index");

   objectTable.Add (key, value);
   objectList.Insert (idx, new DictionaryEntry (key, value));
  }

  public void Remove (object key)
  {
   objectTable.Remove (key);
   objectList.RemoveAt (IndexOf (key));
  }

  public void RemoveAt (int idx)
  {
   if (idx >= Count)
    throw new ArgumentOutOfRangeException ("index");

   objectTable.Remove ( ((DictionaryEntry)objectList[idx]).Key );
   objectList.RemoveAt (idx);
  }

  IDictionaryEnumerator IDictionary.GetEnumerator ()
  {
   return new KeyedListEnumerator (objectList);
  }

  IEnumerator IEnumerable.GetEnumerator ()
  {
   return new KeyedListEnumerator (objectList);
  }

  public int Count 
  {
   get { return objectList.Count; }
  }

  public bool IsFixedSize 
  {
   get { return false; }
  }

  public bool IsReadOnly 
  {
   get { return false; }
  }

  public bool IsSynchronized 
  {
   get { return false; }
  }

  public object this[int idx] 
  {
   get { return ((DictionaryEntry) objectList[idx]).Value; }
   set 
   {
    if (idx < 0 || idx >= Count)
     throw new ArgumentOutOfRangeException ("index");

    object key = ((DictionaryEntry) objectList[idx]).Key;
    objectList[idx] = new DictionaryEntry (key, value);
    objectTable[key] = value;
   }
  }

  public object this[object key] 
  {
   get { return objectTable[key]; }
   set 
   {
    if (objectTable.Contains (key))
    {
     objectTable[key] = value;
     objectTable[IndexOf (key)] = new DictionaryEntry (key, value);
     return;
    }
    Add (key, value);
   }
  }

  public ICollection Keys 
  {
   get 
   { 
    ArrayList retList = new ArrayList ();
    for (int i = 0; i < objectList.Count; i++)
    {
     retList.Add ( ((DictionaryEntry)objectList[i]).Key );
    }
    return retList;
   }
  }

  public ICollection Values 
  {
   get 
   {
    ArrayList retList = new ArrayList ();
    for (int i = 0; i < objectList.Count; i++)
    {
     retList.Add ( ((DictionaryEntry)objectList[i]).Value );
    }
    return retList;
   }
  }
 
  public object SyncRoot 
  {
   get { return this; }
  } 

  private int IndexOf (object key)
  {
   for (int i = 0; i < objectList.Count; i++)
   {
    if (((DictionaryEntry) objectList[i]).Key.Equals (key))
    {
     return i;
    }
   }
   return -1;
  }
 }

 public class KeyedListEnumerator : IDictionaryEnumerator
 {
  private int index = -1;
  private ArrayList objs;

  internal KeyedListEnumerator (ArrayList list)
  {
   objs = list;
  }

  public bool MoveNext ()
  {
   index++;
   if (index >= objs.Count)
    return false;

   return true;
  }

  public void Reset ()
  {
   index = -1;
  }

  public object Current 
  {
   get 
   {
    if (index < 0 || index >= objs.Count)
     throw new InvalidOperationException ();

    return objs[index];
   }
  }

  public DictionaryEntry Entry 
  {
   get 
   {
    return (DictionaryEntry) Current;
   }
  }

  public object Key 
  {
   get 
   {
    return Entry.Key;
   }
  }

  public object Value 
  {
   get 
   {
    return Entry.Value;
   }
  }
 }
}

Using The KeyedList

Using the KeyedList is just like using a Hashtable, except that when you enumerate through the list, the entries are in the same order as when they were added to the list.  Believe me, I needed this capability!

using System;
using System.Collections;

namespace KeyedListTest
{
 class ConsoleApp
 {
  [STAThread]
  static void Main(string[] args)
  {
   KeyedList k=new KeyedList();
   k.Add("One", 1);
   k.Add("Two", 2);
   k.Add("Three", 3);
   k.Add("Four", 4);
   k.Add("Five", 5);
   k.Add("Six", 6);
   k.Add("Seven", 7);
   k.Add("Eight", 8);
   k.Add("Nine", 9);
   k.Add("Ten", 10);

   foreach(DictionaryEntry entry in k)
   {
    Console.WriteLine(entry.Key+": "+entry.Value.ToString());
   }
  }
 }
}

Conclusion

That's it!  A bit of googling, a bit of massaging of some existing source code, and voila!, a solution to my particular problem, and maybe one day a solution to your problem as well.