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

A KeyedList implementation

, 24 Dec 2003
Rate this:
Please Sign up or sign in to vote.
A KeyedList implements an ordered key-value list.
<!-- 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

 
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 
Working version here (sorry for the large post and mistakes).
 
Imports System.Collections
 
Namespace {Your NameSpace}
 
' HashtableList - derives from Hashtable and adds fixed ArrayList enumeration of objects
' based on the order that they were added, unlike Hashtable, SortedList, etc.
' Until Generics/Templates, this will serve its purpose. Acts more like hashtable than arraylist.
' 01 Feb 2005 Marty Spallone / Blue Object Software, LLC., martyone(nospam)@snet.net
' Much code and ideas borrowed from Marc Clifton, Code Project 01 Feb 2005
'
' 01 Feb 2005 - Added CopyTo()
'
Public Class HashtableList
Inherits System.Collections.Hashtable
 
Private keyList As ArrayList = New ArrayList
 
Public Overrides Sub Add(ByVal key As Object, ByVal value As Object)
MyBase.Add(key, value)
keyList.Add(key)
End Sub
 
Default Public Overloads Property Item(ByVal key As Object) As Object
Get
Return MyBase.Item(key)
End Get
Set(ByVal Value As Object)
If keyList.Contains(key) Then
MyBase.Item(key) = Value
Else
Me.Add(key, Value)
End If
End Set
End Property
 
Public Overrides Sub Remove(ByVal key As Object)
keyList.RemoveAt(IndexOf(key)) ' Remove me first!
MyBase.Remove(key)
End Sub
 
Public Overrides Sub CopyTo(ByVal array As System.Array, ByVal index As Integer)
Dim o As ArrayList = New ArrayList(keyList.Count)
For Each key As Object In keyList
o.Add(MyBase.Item(key))
Next
o.CopyTo(array, index)
End Sub
 
Public Overrides Function Clone() As Object
Dim htl As HashtableList = New HashtableList
For Each key As Object In Me.keyList
htl.Add(key, MyBase.Item(key))
Next
Return htl
End Function
 
Public Overrides Function GetEnumerator() As System.Collections.IDictionaryEnumerator
Return New KeyedListEnumerator(keyList, Me)
End Function
 
Public Overloads ReadOnly Property Keys() As ICollection
Get
Dim retkeyList As New ArrayList
Dim i As Integer
For i = 0 To keyList.Count - 1
retkeyList.Add(keyList(i))
Next i
Return retkeyList
End Get
End Property
 

Public Overloads ReadOnly Property Values() As ICollection
Get
Dim retkeyList As New ArrayList
Dim i As Integer
For i = 0 To keyList.Count - 1
retkeyList.Add(MyBase.Item(keyList(i)))
Next i
Return retkeyList
End Get
End Property
 
Private Function IndexOf(ByVal key As Object) As Integer
Dim i As Integer
For i = 0 To keyList.Count - 1
If (keyList(i).Equals(key)) Then
Return i
End If
Next i
Return -1
End Function
 
Public Overloads ReadOnly Property IsSynchronized() As Boolean
Get
Return False
End Get
End Property
End Class
 
Friend Class KeyedListEnumerator
Implements IDictionaryEnumerator
Private index As Integer = -1
Private objs As ArrayList ' access to the consumer's arraylist
Private ref As IDictionary ' access to the consumer's hashtable
 

Public Sub New(ByVal list As ArrayList, ByVal refHT As IDictionary)
objs = list
ref = refHT
End Sub
 
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 New DictionaryEntry(Current, ref(Current))
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

GeneralFixed a bug PinsussJakob Røjel30-Jan-05 20:28 
GeneralAttempted to convert to vb.net PinmemberKenJohnson30-Jul-04 17:21 
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 
QuestionStrongly-Typed Collection? Pinmembermikasa30-Dec-03 4:31 
AnswerRe: Strongly-Typed Collection? PineditorMarc Clifton30-Dec-03 4:49 

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
Web03 | 2.8.140721.1 | Last Updated 25 Dec 2003
Article Copyright 2003 by Marc Clifton
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid