[Mono-list] generic KeyedCollection implementation

Carlo Kok ck at carlo-kok.com
Wed Oct 19 05:59:53 EDT 2005


Attached to this email an incremental patch for the KeyedCollection ( to 
be applied in the \mcs\class\corlib\System.Collections.ObjectModel 
directory. Also included is a testcase, tested with both Beta2 and my 
own implementation.

I followed the existing testcases I could find in SVN. The two almost 
idental guides on the wiki seem to be out of date:

http://www.mono-project.com/Test_Suite
http://www.mono-project.com/Mono_Contribution_HOWTO

comments?

I used the SVN Patch ability of tortoisesvn, if I did that wrong, please 
tell me what I should use instead.

--
Carlo Kok
-------------- next part --------------
Index: Collection.cs
===================================================================
--- Collection.cs	(revision 51865)
+++ Collection.cs	(working copy)
@@ -68,11 +68,17 @@
 
 		public void Add (T item)
 		{
-			list.Add (item);			
+			int idx = list.Count;
+			InsertItem (idx, item);
 		}
 
 		public void Clear ()
 		{
+			ClearItems ();
+		}
+
+		protected virtual void ClearItems ()
+		{
 			list.Clear ();
 		}
 
@@ -98,16 +104,32 @@
 
 		public void Insert (int index, T item)
 		{
+			InsertItem (index, item);
+		}
+
+		protected virtual void InsertItem (int index, T item)
+		{
 			list.Insert (index, item);
 		}
 
 		public bool Remove (T item)
 		{
-			return list.Remove (item);
+			int idx = IndexOf (item);
+			if (idx == -1) 
+				return false;
+			
+			RemoveItem (idx);
+			
+			return true;
 		}
 
 		public void RemoveAt (int index)
 		{
+			RemoveItem (index);
+		}
+
+		protected virtual void RemoveItem (int index)
+		{
 			list.RemoveAt (index);
 		}
 
@@ -117,12 +139,18 @@
 
 		public virtual T this [int index] {
 			get { return list [index]; }
-			set { list [index] = value; }
+			set { SetItem (index, value); }
 		}
 
 		public bool IsReadOnly {
 			get { return list.IsReadOnly; }
 		}
+
+		protected virtual void SetItem (int index, T item)
+		{
+			list[index] = item;
+		}
+
 		
 #region Helper methods for non-generic interfaces
 		
@@ -173,8 +201,9 @@
 				
 		int IList.Add (object item)
 		{
-			list.Add (ConvertItem (item));
-			return list.Count - 1;
+			int idx = list.Count;
+			InsertItem (idx, ConvertItem (item));
+			return idx;
 		}
 		
 		bool IList.Contains (object item)
@@ -193,13 +222,16 @@
 		
 		void IList.Insert (int index, object item)
 		{
-			list.Insert (index, ConvertItem (item));
+			InsertItem (index, ConvertItem (item));
 		}
 		
 		void IList.Remove (object item)
 		{
 			CheckWritable (list);
-			list.Remove (ConvertItem (item));
+
+			int idx = IndexOf (ConvertItem (item));
+
+			RemoveItem (idx);
 		}
 		
 		bool ICollection.IsSynchronized {
@@ -219,7 +251,7 @@
 		
 		object IList.this [int index] {
 			get { return list [index]; }
-			set { list [index] = ConvertItem (value); }
+			set { SetItem (index, ConvertItem (value)); }
 		}
 #endregion
 	}
Index: KeyedCollection.cs
===================================================================
--- KeyedCollection.cs	(revision 51865)
+++ KeyedCollection.cs	(working copy)
@@ -42,58 +42,167 @@
 	[Serializable]
 	public abstract class KeyedCollection<TKey, TItem> : Collection<TItem>
 	{
+		private Dictionary<TKey, TItem> dictionary;
+		private IEqualityComparer<TKey> comparer;
+		private int dictionaryCreationThreshold;
+
+		protected KeyedCollection ()
+			: this (null, 0)
+		{ 
+		}
+
+		protected KeyedCollection (IEqualityComparer<TKey> comparer)
+			: this(comparer, 0)
+		{
+		}
+
+		protected KeyedCollection (IEqualityComparer<TKey> comparer, int dictionaryCreationThreshold)
+		{
+			if (comparer != null)
+				this.comparer = comparer;
+			else
+				this.comparer = EqualityComparer<TKey>.Default;
+
+			this.dictionaryCreationThreshold = dictionaryCreationThreshold;
+
+			if (dictionaryCreationThreshold == 0)
+				dictionary = new Dictionary<TKey, TItem> (this.comparer);
+		}
+
 		public bool Contains (TKey key)
 		{
-			throw new NotImplementedException ();
+			if (dictionary != null)
+				return dictionary.ContainsKey (key);
+			return IndexOfKey (key) >= 0;
 		}
 
+		private int IndexOfKey (TKey key)
+		{
+			for (int i = Count - 1; i >= 0; i--)
+			{
+				TKey lkey = GetKeyForItem (this [i]);
+				if (comparer.Equals (key, lkey))
+					return i;
+			}
+			return -1;
+		}
+
 		public bool Remove (TKey key)
 		{
-			throw new NotImplementedException ();
+			TItem item;
+			if (dictionary != null)
+			{
+				if (dictionary.TryGetValue (key, out item))
+					return base.Remove(item);
+				else
+					return false;
+			}
+
+			int idx = IndexOfKey (key);
+
+			if (idx == -1)
+				return false;
+			
+			RemoveAt(idx);
+			return true;
 		}
 
 		public IEqualityComparer<TKey> Comparer {
 			get {
-				throw new NotImplementedException ();
+				return comparer;
 			}
 		}
 
-		public TItem this[TKey key] {
+		public TItem this [TKey key] {
 			get {
-				throw new NotImplementedException ();
+				if (dictionary != null)
+					return dictionary [key];
+
+				int idx = IndexOfKey (key);
+				if (idx >= 0)
+					return base [idx];
+				else
+					throw new KeyNotFoundException();
 			}
 		}
 
 		protected void ChangeItemKey (TItem item, TKey newKey)
 		{
-			throw new NotImplementedException ();
+			if (!Contains(item)) throw new ArgumentException();
+
+			TKey oldKey = GetKeyForItem (item);
+			if (comparer.Equals (oldKey, newKey)) return;
+
+			if (Contains (newKey)) throw new ArgumentException();
+			if (dictionary != null)
+			{
+
+				if (!dictionary.Remove (oldKey))
+					throw new ArgumentException();
+
+				dictionary.Add (newKey, item);
+			}
 		}
 
-		protected void ClearItems ()
+		protected override void ClearItems ()
 		{
-			throw new NotImplementedException ();
+			if (dictionary != null)
+			{
+				dictionary.Clear();
+			}
+
+			base.ClearItems ();
 		}
 
 		protected abstract TKey GetKeyForItem (TItem item);
 
-		protected virtual void InsertItem (int index, TItem item)
+		protected override void InsertItem (int index, TItem item)
 		{
-			throw new NotImplementedException ();
+			if (dictionary != null)
+			{
+				dictionary.Add (GetKeyForItem (item), item);
+			}
+			else
+			{
+				if (dictionaryCreationThreshold != -1 && Count + 1 > dictionaryCreationThreshold)
+				{
+					dictionary = new Dictionary<TKey, TItem> (comparer);
+
+					for (int i = Count - 1; i >= 0; i--)
+					{
+						TItem dictitem = this[i];
+						dictionary.Add(GetKeyForItem(dictitem), dictitem);
+					}
+
+					dictionary.Add (GetKeyForItem (item), item);
+				}
+			}
+			base.InsertItem (index, item);
 		}
 
-		protected virtual void RemoveItem (int index)
+		protected override void RemoveItem (int index)
 		{
-			throw new NotImplementedException ();
+			if (dictionary != null)
+			{
+				TKey key = GetKeyForItem (this [index]);
+				dictionary.Remove (key);
+			}
+			base.RemoveItem (index);
 		}
 
-		protected virtual void SetItem (int index, TItem item)
+		protected override void SetItem (int index, TItem item)
 		{
-			throw new NotImplementedException ();
+			if (dictionary != null)
+			{
+				dictionary.Remove (GetKeyForItem (this [index]));
+				dictionary.Add (GetKeyForItem (item), item);
+			}
+			base.SetItem (index, item);
 		}
 
 		protected IDictionary<TKey, TItem> Dictionary {
 			get {
-				throw new NotImplementedException ();
+				return dictionary;
 			}
 		}
 	}
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 51865)
+++ ChangeLog	(working copy)
@@ -1,3 +1,8 @@
+2005-10-19  Carlo Kok  <ck at carlo-kok.com>
+
+        * Added virtual ClearItems, InsertItem, RemoveItem, SetITem
+        * Implemented KeyedCollection
+		
 2005-06-19  David Waite  <mass at akuma.org>
 
         * Collection.cs ReadonlyCollection.cs: Implement all methods
-------------- next part --------------
// KeyedCollectionTest.cs - NUnit Test Cases for System.Collections.ObjectModel.KeyedCollection
//
// Carlo Kok (ck at carlo-kok.com)
//
// (C) Carlo Kok
// 

#if NET_2_0
using NUnit.Framework;
using System;
using System.Globalization;
using System.Collections.Generic;
using System.Collections.ObjectModel;

namespace MonoTests.System.Collections.ObjectModel
{

  [TestFixture]
  public class KeyedCollectionTest 
  {

    private class CaseInsensitiveComparer : IEqualityComparer<string>
    {
      public CaseInsensitiveComparer() { }
      #region IEqualityComparer<string> Members

      public bool Equals(string x, string y)
      {
        return String.Compare(x, y, true, CultureInfo.InvariantCulture) == 0;
      }

      public int GetHashCode(string obj)
      {
        return obj.ToUpper(CultureInfo.InvariantCulture).GetHashCode();
      }

      #endregion
}

    private class StrKeyCollection : KeyedCollection<string, string>
    {
      public StrKeyCollection(IEqualityComparer<string> comparer, int dictionaryCreationThreshold): base(comparer, dictionaryCreationThreshold)
      {
      }

      protected override string GetKeyForItem(string item)
      {
        return "Key:" + item;
      }

      public IDictionary<string, string> GetDictionary()
      {
        return Dictionary;
      }
    }

    public KeyedCollectionTest()
    {
    }

    [Test]
    public void TestDelete()
    {
      StrKeyCollection collection = new StrKeyCollection(EqualityComparer<string>.Default, 2);
      collection.Add("One"); // Key:First
      collection.Add("Two"); // Key:Two
      Assert.IsTrue(collection.Remove("Key:One"));
      collection.Add("Four"); // Key:Four
      collection.Insert(2, "Three"); // Key:Three
      Assert.IsTrue(collection.Remove("Key:Three"));

      Assert.IsFalse(collection.Remove("Unknown"));

      Assert.AreEqual(collection.GetDictionary().Count, 2);


      Assert.AreEqual(collection.Count, 2, "Collection count not equal to 2");
      // check if all items are ordered correctly

      Assert.AreEqual(collection[0], "Two");
      Assert.AreEqual(collection[1], "Four");

      Assert.AreEqual(collection["Key:Two"], "Two");
      Assert.AreEqual(collection["Key:Four"], "Four");

      try
      {
        collection["Key:One"].ToString();
        Assert.Fail("Unknown key should fail");
      }
      catch (KeyNotFoundException e)
      {
        e.ToString(); // avoid warning
        // oke
      }

      try
      {
        collection["Key:One"].ToString();
        Assert.Fail("Unknown key should fail");
      }
      catch (KeyNotFoundException e)
      {
        e.ToString(); // avoid warning
        // oke
      }
    }

    [Test]
    public void TestInsert()
    {
      StrKeyCollection collection = new StrKeyCollection(EqualityComparer<string>.Default, 2);
      
      Assert.IsNull(collection.GetDictionary(), "Dictionary created too early"); // There can't be a dictionary yet
      
      collection.Add("One"); // Key:First

      Assert.IsNull(collection.GetDictionary(), "Dictionary created too early"); // There can't be a dictionary yet

      collection.Add("Two"); // Key:Two

      Assert.IsNull(collection.GetDictionary(), "Dictionary created too early"); // There can't be a dictionary yet

      collection.Add("Four"); // Key:Four

      Assert.IsNotNull(collection.GetDictionary(), "Dictionary created too late"); // There must be a dictionary 
      
      collection.Insert(2, "Three"); // Key:Three

      Assert.AreEqual(collection.Count, 4, "Collection count not equal to 4");
      // check if all items are ordered correctly

      Assert.AreEqual(collection[0], "One");
      Assert.AreEqual(collection[1], "Two");
      Assert.AreEqual(collection[2], "Three");
      Assert.AreEqual(collection[3], "Four");

      Assert.AreEqual(collection["Key:One"], "One");
      Assert.AreEqual(collection["Key:Two"], "Two");
      Assert.AreEqual(collection["Key:Three"], "Three");
      Assert.AreEqual(collection["Key:Four"], "Four");

      Assert.AreEqual(collection.GetDictionary().Count, 4);

      try
      {
        collection["UnkownKey"].ToString();
        Assert.Fail("Unknown key should fail");
      }
      catch(KeyNotFoundException e)
      {
        e.ToString(); // avoid warning
        // oke
      }
    }
  }
}
#endif


More information about the Mono-list mailing list