Click here to Skip to main content
15,868,016 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

 
GeneralSmall bug Pin
DThrasher28-Dec-07 8:01
DThrasher28-Dec-07 8:01 
GeneralGenerics version Pin
Marc Clifton28-Dec-07 9:36
mvaMarc Clifton28-Dec-07 9:36 
Generalgreatly simplified C# version Pin
Brian Perrin1-Mar-07 0:20
Brian Perrin1-Mar-07 0:20 
GeneralRe: greatly simplified C# version Pin
Marc Clifton28-Dec-07 9:28
mvaMarc Clifton28-Dec-07 9:28 
GeneralCode update, tiny but could be usefull Pin
raymond7725-Jan-07 22:07
raymond7725-Jan-07 22:07 
GeneralThanks! Pin
Micah Wedemeyer10-Oct-06 4:37
Micah Wedemeyer10-Oct-06 4:37 
GeneralContainsKey Pin
ericksoa0427-Mar-06 4:19
ericksoa0427-Mar-06 4:19 
General.NET 2.0 KeyedList Pin
Marc Clifton27-Mar-06 5:22
mvaMarc Clifton27-Mar-06 5:22 
QuestionGetEnumerator? Pin
Doncp1-Jan-06 16:45
Doncp1-Jan-06 16:45 
GeneralCode Update Pin
david.minor25-Jul-05 9:21
david.minor25-Jul-05 9:21 
GeneralCode Update Pin
david.minor25-Jul-05 9:19
david.minor25-Jul-05 9:19 
GeneralSimilar Implementation in C Pin
david.minor25-Jul-05 9:18
david.minor25-Jul-05 9:18 
GeneralHashtableList - derives from hashtable Pin
Marty Spallone1-Feb-05 10:47
Marty Spallone1-Feb-05 10:47 
GeneralRe: HashtableList - derives from hashtable Pin
Marty Spallone1-Feb-05 11:01
Marty Spallone1-Feb-05 11:01 
GeneralRe: HashtableList - derives from hashtable Pin
Marty Spallone1-Feb-05 12:03
Marty Spallone1-Feb-05 12:03 
GeneralFixed a bug Pin
Jakob Røjel30-Jan-05 20:28
sussJakob Røjel30-Jan-05 20:28 
GeneralAttempted to convert to vb.net Pin
KenJohnson30-Jul-04 17:21
KenJohnson30-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 Pin
rwallacej210-Sep-12 5:30
rwallacej210-Sep-12 5:30 
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 
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 

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.