Click here to Skip to main content
15,868,049 members
Articles / Programming Languages / C#
Article

A KeyedList implementation

Rate me:
Please Sign up or sign in to vote.
4.83/5 (26 votes)
24 Dec 20032 min read 159.9K   868   38   35
A KeyedList implements an ordered key-value list.

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());
   }
  }
 }
}

Sample screenshot

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Architect Interacx
United States United States
Blog: https://marcclifton.wordpress.com/
Home Page: http://www.marcclifton.com
Research: http://www.higherorderprogramming.com/
GitHub: https://github.com/cliftonm

All my life I have been passionate about architecture / software design, as this is the cornerstone to a maintainable and extensible application. As such, I have enjoyed exploring some crazy ideas and discovering that they are not so crazy after all. I also love writing about my ideas and seeing the community response. As a consultant, I've enjoyed working in a wide range of industries such as aerospace, boatyard management, remote sensing, emergency services / data management, and casino operations. I've done a variety of pro-bono work non-profit organizations related to nature conservancy, drug recovery and women's health.

Comments and Discussions

 
QuestionThe CopyTo method should maybe return an ordered list as well? Pin
TrondR4-Jul-04 16:03
TrondR4-Jul-04 16:03 
Generali think SortedList is good enough for use Pin
Eric.Wang27-Jun-04 22:32
Eric.Wang27-Jun-04 22:32 
GeneralRe: i think SortedList is good enough for use Pin
Eric.Wang27-Jun-04 23:01
Eric.Wang27-Jun-04 23:01 
Generalenven easier Pin
Eric.Wang11-Jul-04 19:23
Eric.Wang11-Jul-04 19:23 
SortedList list = new SortedList(13);
list.Add("one", 1);
list.Add("two", 2);
list.Add("three", 3);
int val = (int)list["two"];
GeneralBug in this[object key] set property Pin
dwhearn8-Jan-04 6:18
dwhearn8-Jan-04 6:18 
GeneralRe: Bug in this[object key] set property Pin
DrunkenWagoner30-Nov-04 14:14
DrunkenWagoner30-Nov-04 14:14 
GeneralOne Suggestion Pin
scadaguy30-Dec-03 5:33
scadaguy30-Dec-03 5:33 
QuestionStrongly-Typed Collection? Pin
mikasa30-Dec-03 4:31
mikasa30-Dec-03 4:31 
AnswerRe: Strongly-Typed Collection? Pin
Marc Clifton30-Dec-03 4:49
mvaMarc Clifton30-Dec-03 4:49 
GeneralRe: Strongly-Typed Collection? Pin
mikasa30-Dec-03 5:05
mikasa30-Dec-03 5:05 
GeneralRe: Strongly-Typed Collection? Pin
Iftekhar Ivaan18-Feb-04 9:47
Iftekhar Ivaan18-Feb-04 9:47 
GeneralRe: Strongly-Typed Collection? Pin
mikasa18-Feb-04 9:54
mikasa18-Feb-04 9:54 
GeneralCouple of comments Pin
Frank Olorin Rizzi27-Dec-03 4:14
Frank Olorin Rizzi27-Dec-03 4:14 
GeneralRe: Couple of comments Pin
Marc Clifton27-Dec-03 10:18
mvaMarc Clifton27-Dec-03 10:18 
GeneralRe: Couple of comments Pin
Frank Olorin Rizzi27-Dec-03 11:49
Frank Olorin Rizzi27-Dec-03 11:49 
GeneralBookmarked Pin
Jonathan de Halleux26-Dec-03 5:39
Jonathan de Halleux26-Dec-03 5:39 
Generalno duplicate keys Pin
Ashley van Gerven25-Dec-03 15:51
Ashley van Gerven25-Dec-03 15:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.