Click here to Skip to main content
Click here to Skip to main content

A KeyedList implementation

By , 24 Dec 2003
Rate this:
Please Sign up or sign in to vote.
<!-- Add the rest of your HTML here -->

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

About the Author

Marc Clifton

United States United States
Marc is the creator of two open source projets, MyXaml, a declarative (XML) instantiation engine and the Advanced Unit Testing framework, and Interacx, a commercial n-tier RAD application suite.  Visit his website, www.marcclifton.com, where you will find many of his articles and his blog.
 
Marc lives in Philmont, NY.

Comments and Discussions

 
GeneralSmall bug PinmemberDThrasher28-Dec-07 8:01 
GeneralGenerics version PinprotectorMarc Clifton28-Dec-07 9:36 
Generalgreatly simplified C# version PinmemberBrian Perrin1-Mar-07 0:20 
GeneralRe: greatly simplified C# version PinprotectorMarc Clifton28-Dec-07 9:28 
GeneralCode update, tiny but could be usefull Pinmemberraymond7725-Jan-07 22:07 
GeneralThanks! PinmemberMicah Wedemeyer10-Oct-06 4:37 
GeneralContainsKey Pinmemberericksoa0427-Mar-06 4:19 
General.NET 2.0 KeyedList PinprotectorMarc Clifton27-Mar-06 5:22 
QuestionGetEnumerator? PinmemberDoncp1-Jan-06 16:45 
GeneralCode Update Pinmemberdavid.minor25-Jul-05 9:21 
GeneralCode Update Pinmemberdavid.minor25-Jul-05 9:19 
GeneralSimilar Implementation in C Pinmemberdavid.minor25-Jul-05 9:18 
GeneralHashtableList - derives from hashtable PinmemberMartyOne1-Feb-05 10:47 
GeneralRe: HashtableList - derives from hashtable PinmemberMartyOne1-Feb-05 11:01 
GeneralRe: HashtableList - derives from hashtable PinmemberMartyOne1-Feb-05 12:03 
GeneralFixed a bug PinsussJakob Røjel30-Jan-05 20:28 
GeneralAttempted to convert to vb.net PinmemberKenJohnson30-Jul-04 17:21 
Thanks for the code. I tried to convert it to vb.net but encounterd two problems. If I kept the Namespace System.Collections then it would not let me add the implements information to the members. This is a bit odd and I would love to be edified. The Secon and harder for me to understand is that is the two GetEnumerator members. They are conflicting with one another. I would greatly appreciate it if someone could explain this to me.
 
I am putting the code in this message. Hopefully it will fit.
 

Imports System
Imports System.Collections
 

'Namespace System.Collections
 
Public Interface IOrderedDictionary
      Sub Insert(ByVal index As Int32, ByVal key As [Object], ByVal value As [Object])
      Sub RemoveAt(ByVal index As Int32)
End Interface
 

<Serializable()> Public Class KeyedList
      Implements IDictionary, IEnumerable, IOrderedDictionary
      Private objectTable As New Hashtable
      Private objectList As New ArrayList
 

      Public Sub Add(ByVal key As Object, ByVal value As Object) Implements IDictionary.Add
            objectTable.Add(key, value)
            objectList.Add(New DictionaryEntry(key, value))
      End Sub
 

      Public Sub Clear() Implements IDictionary.Clear
            objectTable.Clear()
            objectList.Clear()
      End Sub
 

      Public Function Contains(ByVal key As Object) As Boolean Implements IDictionary.contains
            Return objectTable.Contains(key)
      End Function
 

      Public Sub CopyTo(ByVal array As Array, ByVal idx As Integer) Implements ICollection.CopyTo
            objectTable.CopyTo(array, idx)
      End Sub
 

      Public Sub Insert(ByVal idx As Integer, ByVal key As Object, ByVal value As Object) Implements IOrderedDictionary.Insert
            If idx > Count Then
                  Throw New ArgumentOutOfRangeException("index")
            End If
            objectTable.Add(key, value)
            objectList.Insert(idx, New DictionaryEntry(key, value))
      End Sub
 

      Public Sub Remove(ByVal key As Object) Implements IDictionary.Remove
            objectTable.Remove(key)
            objectList.RemoveAt(IndexOf(key))
      End Sub
 

      Public Sub RemoveAt(ByVal idx As Integer) Implements IOrderedDictionary.RemoveAt
            If idx >= Count Then
                  Throw New ArgumentOutOfRangeException("index")
            End If
            objectTable.Remove(CType(objectList(idx), DictionaryEntry).Key)
            objectList.RemoveAt(idx)
      End Sub
 

      Function GetEnumerator() As IDictionaryEnumerator Implements IDictionary.GetEnumerator
            Return New KeyedListEnumerator(objectList)
      End Function
 

      Function GetEnumerator() As IEnumerator Implements IEnumerable.GetEnumerator
            Return New KeyedListEnumerator(objectList)
      End Function
 

      Public ReadOnly Property Count() As Integer Implements ICollection.Count
            Get
                  Return objectList.Count
            End Get
      End Property
 
      Public ReadOnly Property IsFixedSize() As Boolean Implements IDictionary.isFixedSize
            Get
                  Return False
            End Get
      End Property
 
      Public ReadOnly Property IsReadOnly() As Boolean Implements IDictionary.IsReadOnly
            Get
                  Return False
            End Get
      End Property
 
      Public ReadOnly Property IsSynchronized() As Boolean Implements IDictionary.IsSynchronized
            Get
                  Return False
            End Get
      End Property
 
      Default Public Property Item(ByVal idx As Integer) As Object
            Get
                  Return CType(objectList(idx), DictionaryEntry).Value
            End Get
            Set(ByVal Value As Object)
                  If idx < 0 Or idx >= Count Then
                        Throw New ArgumentOutOfRangeException("index")
                  End If
                  Dim key As Object = CType(objectList(idx), DictionaryEntry).Key
                  objectList(idx) = New DictionaryEntry(key, Value)
                  objectTable(key) = Value
            End Set
      End Property
 

      Default Public Property Item(ByVal key As Object) As Object Implements IDictionary.item
            Get
                  Return objectTable(key)
            End Get
            Set(ByVal Value As Object)
                  If objectTable.Contains(key) Then
                        objectTable(key) = Value
                        objectTable(IndexOf(key)) = New DictionaryEntry(key, Value)
                        Return
                  End If
                  Add(key, Value)
            End Set
      End Property
 

      Public ReadOnly Property Keys() As ICollection Implements IDictionary.keys
            Get
                  Dim retList As New ArrayList
                  Dim i As Integer
                  For i = 0 To objectList.Count - 1
                        retList.Add(CType(objectList(i), DictionaryEntry).Key)
                  Next i
                  Return retList
            End Get
      End Property
 

      Public ReadOnly Property Values() As ICollection Implements IDictionary.values
            Get
                  Dim retList As New ArrayList
                  Dim i As Integer
                  For i = 0 To objectList.Count - 1
                        retList.Add(CType(objectList(i), DictionaryEntry).Value)
                  Next i
                  Return retList
            End Get
      End Property
 

      Public ReadOnly Property SyncRoot() As Object Implements System.Collections.ICollection.SyncRoot
            Get
                  Return Me
            End Get
      End Property
 
      Private Function IndexOf(ByVal key As Object) As Integer
            Dim i As Integer
            For i = 0 To objectList.Count - 1
                  If CType(objectList(i), DictionaryEntry).Key.Equals(key) Then
                        Return i
                  End If
            Next i
            Return -1
      End Function
End Class
      _
 
Public Class KeyedListEnumerator
      Implements IDictionaryEnumerator
      Private index As Integer = -1
      Private objs As ArrayList
 

      Friend Sub New(ByVal list As ArrayList)
            objs = list
      End Sub 'New
 

      Public Function MoveNext() As Boolean Implements IDictionaryEnumerator.MoveNext
            index += 1
            If index >= objs.Count Then
                  Return False
            End If
            Return True
      End Function
 

      Public Sub Reset() Implements IDictionaryEnumerator.Reset
            index = -1
      End Sub
 

      Public ReadOnly Property Current() As Object Implements IDictionaryEnumerator.Current
            Get
                  If index < 0 Or index >= objs.Count Then
                        Throw New InvalidOperationException
                  End If
                  Return objs(index)
            End Get
      End Property
 

      Public ReadOnly Property Entry() As DictionaryEntry Implements IDictionaryEnumerator.Entry
            Get
                  Return CType(Current, DictionaryEntry)
            End Get
      End Property
 

      Public ReadOnly Property Key() As Object Implements IDictionaryEnumerator.Key
            Get
                  Return Entry.Key
            End Get
      End Property
 

      Public ReadOnly Property Value() As Object Implements IDictionaryEnumerator.Value
            Get
                  Return Entry.Value
            End Get
      End Property
End Class
'End Namespace 'System.Collections

 
Ken Johnson (kenjohnson777@hotmail.com)
GeneralRe: Attempted to convert to vb.net Pinmemberrwallacej210-Sep-12 5:30 
QuestionThe CopyTo method should maybe return an ordered list as well? PinmemberTrond Reierth4-Jul-04 16:03 
Generali think SortedList is good enough for use Pinmembersuger27-Jun-04 22:32 
GeneralRe: i think SortedList is good enough for use Pinmembersuger27-Jun-04 23:01 
Generalenven easier Pinmembersuger11-Jul-04 19:23 
GeneralBug in this[object key] set property Pinmemberdwhearn8-Jan-04 6:18 
GeneralRe: Bug in this[object key] set property Pinmemberrohan_p30-Nov-04 14:14 
GeneralOne Suggestion PinmemberBrian Gideon30-Dec-03 5:33 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.140421.2 | Last Updated 25 Dec 2003
Article Copyright 2003 by Marc Clifton
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid