[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