ジェネリック版OrderedDictionary

System.Collections.Specialized.OrderedDictionaryクラスは非ジェネリックで、これに対応するジェネリック版のクラスが存在しない。

以下はSystem.Collections.ObjectModel.Collection<System.Collections.Generic.KeyValuePair<TKey, TValue>>をベースにOrderedDictionary<TKey, TValue>を実装したもの。

使用例・動作例

使用例

行番号を表示する

using System;

class Sample {
  static void Main()
  {
    var dict = new OrderedDictionary<string, int>();

    dict.Add("foo", 16);

    dict["bar"] = 72;

    dict.Add("qux", 7);

    dict.Insert(2, "baz", 42);

    for (var index = 0; index < dict.Count; index++) {
      Console.WriteLine("{0} => {{{1}, {2}}}",
                        index,
                        dict[index].Key,
                        dict[index].Value);
    }
  }
}

実行結果

0 => {foo, 16}
1 => {bar, 72}
2 => {baz, 42}
3 => {qux, 7}

OrderedDictionary<TKey, TValue>

実装となるコード。　System.Collections.Generic.Dictionary<TKey, TValue>と同じ動作となるようにしてあるので、これを置き換える目的であればコードの修正は必要ないが、System.Collections.Specialized.OrderedDictionaryを置き換える目的で使用する場合は、使用側のコードを修正する必要がある。

その他注意事項・制限事項等はソース中のコメントを参照のこと。　ライセンスはMIT Licenseとします(ソース下部のリンク参照)。

OrderedDictionary<TKey, TValue>

行番号を表示する

#define ENABLE_KEYS_VALUES
//#undef ENABLE_KEYS_VALUES

using System;
using System.Linq;
using System.Collections.Generic;

/// <summary>
/// ジェネリック版のOrderedDictionary実装。
/// </summary>
/// <remarks>
///  <para>
///   System.Collections.ObjectModel.Collection&lt;KeyValuePair&lt;TKey, TValue&gt;&gt;をベースとして構築したOrderedDictionary。
///  </para>
///  <para>
///   このクラスにおける制限事項等は次の通り。
///   <list type="bullet">
///    <item>
///     <description>
///      インデクサthis[int index]の型はTValueではなく、KeyValuePair&lt;TKey, TValue&gt;。
///    　つまりインデックスによるアクセスでは値を取得・設定するのではなく、KeyValuePairを取得・設定することになる。
///     </description>
///    </item>
///    <item><description>キーによるアクセスはO(n)、インデックスによるアクセスはO(1)となる。</description></item>
///    <item><description>容量(Capacity)を指定することはできない。</description></item>
///    <item><description>ISerializableを実装していない。　シリアライズの動作が未定義。</description></item>
///    <item>
///     <description>
///      Keysプロパティ・Valuesプロパティは、アクセス時にキャッシュされたコレクションを別途生成する。
///      このプロパティの実装が不要な場合はENABLE_KEYS_VALUESをundefにすることで無効化できる。
///     </description>
///    </item>
///   </list>
///  </para>
/// </remarks>
public class OrderedDictionary<TKey, TValue> :
  System.Collections.ObjectModel.Collection<KeyValuePair<TKey, TValue>>,
  IDictionary<TKey, TValue>
{
  private readonly IEqualityComparer<TKey> keyComparer;

  public OrderedDictionary()
    : this(EqualityComparer<TKey>.Default)
  {
  }

  public OrderedDictionary(IEqualityComparer<TKey> keyComparer)
  {
    this.keyComparer = keyComparer;
  }

  public void Add(TKey key, TValue val)
  {
    Add(new KeyValuePair<TKey, TValue>(key, val));
  }

  public void Insert(int index, TKey key, TValue val)
  {
    Insert(index, new KeyValuePair<TKey, TValue>(key, val));
  }

  public bool Remove(TKey key)
  {
    int index;

    if (TryGetIndex(key, out index)) {
      RemoveAt(index);

      return true;
    }
    else {
      return false;
    }
  }

  public bool ContainsKey(TKey key)
  {
    int index;

    return TryGetIndex(key, out index);
  }

  public bool TryGetValue(TKey key, out TValue val)
  {
    int index;

    if (TryGetIndex(key, out index)) {
      val = this[index].Value;

      return true;
    }
    else {
      val = default(TValue);

      return false;
    }
  }

  /// <summary>
  /// キーに対応するインデックスを取得する。
  /// </summary>
  /// <returns>キーに該当する要素がある場合は<c>true</c>、ない場合は<c>false</c>。</returns>
  /// <param name="key">インデックスを取得したい要素のキー。</param>
  /// <param name="index">キーに該当する要素がある場合、そのインデックス。</param>
  private bool TryGetIndex(TKey key, out int index)
  {
    for (index = 0; index < Count; index++) {
      if (keyComparer.Equals(this[index].Key, key))
        return true;
    }

    return false;
  }

  public TValue this[TKey key] {
    get {
      int index;

      if (TryGetIndex(key, out index))
        return this[index].Value;
      else
        throw new KeyNotFoundException(string.Format("item not found; key = {0}", key));
    }
    set {
      int index;

      if (TryGetIndex(key, out index))
        this[index] = new KeyValuePair<TKey, TValue>(key, value);
      else
        Add(key, value);
    }
  }

#if ENABLE_KEYS_VALUES
  private ICollection<TKey> keys = null;
  private ICollection<TValue> values = null;

  private bool modified = true;

  /// <summary>
  /// キャッシュされたkeys, valuesを最新の状態にする。
  /// </summary>
  /// <remarks>
  /// 前回のキャッシュ生成以降にコレクションが変更されていれば、キャッシュを破棄して生成しなおす。
  /// </remarks>
  private void EnsureKeysAndValuesUpdated()
  {
    if (!modified)
      return;

    keys = this.Select(pair => pair.Key).ToList().AsReadOnly();
    values = this.Select(pair => pair.Value).ToList().AsReadOnly();

    modified = false;
  }
#endif

  public ICollection<TKey> Keys {
    get {
#if ENABLE_KEYS_VALUES
      EnsureKeysAndValuesUpdated();

      return keys;
#else
      throw new NotSupportedException();
#endif
    }
  }

  public ICollection<TValue> Values {
    get {
#if ENABLE_KEYS_VALUES
      EnsureKeysAndValuesUpdated();

      return values;
#else
      throw new NotSupportedException();
#endif
    }
  }

  protected override void InsertItem(int index, KeyValuePair<TKey, TValue> item)
  {
    int existentIndex;

    if (TryGetIndex(item.Key, out existentIndex))
      throw new ArgumentException(string.Format("the item already exists; key = {0}", item.Key));

    base.InsertItem(index, item);

#if ENABLE_KEYS_VALUES
    modified = true;
#endif
  }

  protected override void SetItem(int index, KeyValuePair<TKey, TValue> item)
  {
    int existentIndex;

    if (TryGetIndex(item.Key, out existentIndex) && index != existentIndex)
      throw new ArgumentException(string.Format("the item already exists; key = {0}", item.Key));

    base.SetItem(index, item);

#if ENABLE_KEYS_VALUES
    modified = true;
#endif
  }

#if ENABLE_KEYS_VALUES
  protected override void RemoveItem(int index)
  {
    base.RemoveItem(index);

    modified = true;
  }

  protected override void ClearItems()
  {
    base.ClearItems();

    modified = true;
  }
#endif
}

テストコード

要NUnit。　ライセンスはMIT Licenseとします(ソース下部のリンク参照)。

OrderedDictionary<TKey, TValue>のテストコード

行番号を表示する

#define ORDERED_DICTIONARY
// ORDERED_DICTIONARYをundefするとSystem.Collections.Generic.Dictionaryと同じ動作となることの確認用テストコードとなる
//#undef ORDERED_DICTIONARY

using System;
using System.Collections.Generic;
using NUnit.Framework;

#if ORDERED_DICTIONARY
using Dict = OrderedDictionary<string, int>;
#else
using Dict = System.Collections.Generic.Dictionary<string, int>;
#endif
using Pair = System.Collections.Generic.KeyValuePair<string, int>;

[TestFixture]
public class OrderedDictionaryTests {
#if ORDERED_DICTIONARY
  [Test]
  public void MajorUseCase1()
  {
    var dict = new Dict();

    dict.Add("foo", 16);
    dict.Add("baz", 42);

    dict.Insert(1, "bar", 72);

    CollectionAssert.AreEqual(new[] {"foo", "bar", "baz"}, dict.Keys, "#1");
    CollectionAssert.AreEqual(new[] {16, 72, 42}, dict.Values, "#2");

    dict["bar"] = 36;

    Assert.AreEqual(36, dict["bar"]);

    CollectionAssert.AreEqual(new[] {"foo", "bar", "baz"}, dict.Keys, "#3");
    CollectionAssert.AreEqual(new[] {16, 36, 42}, dict.Values, "#4");

    dict.Clear();

    CollectionAssert.IsEmpty(dict, "#5");
    CollectionAssert.IsEmpty(dict.Keys, "#6");
    CollectionAssert.IsEmpty(dict.Values, "#7");
  }

  [Test]
  public void MajorUseCase2()
  {
    var dict = new Dict();

    dict.Add("foo", 16);
    dict.Add("bar", 72);
    dict.Add("baz", 42);

    var expectedKeys = new[] {"foo", "bar", "baz"};
    var expectedValues = new[] {16, 72, 42};

    for (var index = 0; index < dict.Count; index++) {
      Assert.AreEqual(expectedKeys[index], dict[index].Key, "#1 key of index {0}", index);
      Assert.AreEqual(expectedValues[index], dict[index].Value, "#2 value of index {0}", index);
    }
  }
#endif

  [Test]
  public void TestEqualityComparer()
  {
    var dict = new Dict(StringComparer.OrdinalIgnoreCase);

    dict.Add("a", 1);

    Assert.AreEqual(1, dict["A"], "#1");
#if ORDERED_DICTIONARY
    Assert.AreEqual("a", dict[0].Key, "#2");
#endif

    Assert.Throws<ArgumentException>(() => dict.Add("A", 2), "#3");
  }

  [Test]
  public void TestSetByKey()
  {
    var dict = new Dict();

    Assert.DoesNotThrow(() => dict["a"] = 1, "#1 new entry");
    Assert.AreEqual(1, dict["a"], "#2");

    Assert.DoesNotThrow(() => dict["a"] = 2, "#3 existent entry");
    Assert.AreEqual(2, dict["a"], "#4");
  }

#if ORDERED_DICTIONARY
  [Test]
  public void TestSetByIndex()
  {
    var dict = new Dict();

    Assert.Throws<ArgumentOutOfRangeException>(() => dict[0] = new Pair("a", 1), "#1 new entry");

    dict.Add("a", 1);

    Assert.DoesNotThrow(() => dict[0] = new Pair("b", 2), "#2 existent entry");

    Assert.AreEqual(1, dict.Count, "#3");
    Assert.AreEqual(2, dict["b"], "#4");
  }

  [Test]
  public void TestSetByIndexExistentKey()
  {
    var dict = new Dict();

    dict.Add("a", 1);
    dict.Add("b", 2);

    Assert.Throws<ArgumentException>(() => dict[0] = new Pair("b", 3), "#1 existent key");

    Assert.AreEqual("a", dict[0].Key, "#2");
  }
#endif

  [Test]
  public void TestGetByKey()
  {
    var dict = new Dict();

    dict["a"] = 1;

    Assert.AreEqual(1, dict["a"], "#1 existent entry");
    Assert.Throws<KeyNotFoundException>(() => {int b = dict["b"];}, "#2 non existent entry");
  }

#if ORDERED_DICTIONARY
  [Test]
  public void TestGetByIndex()
  {
    var dict = new Dict();

    dict["a"] = 1;

    Assert.AreEqual("a", dict[0].Key, "#1 existent entry");
    Assert.AreEqual(1, dict[0].Value, "#2 existent entry");
    Assert.Throws<ArgumentOutOfRangeException>(() => {var pair = dict[1];}, "#3 non existent entry");
  }
#endif

  [Test]
  public void TestAddKeyValue()
  {
    var dict = new Dict();

    Assert.DoesNotThrow(() => dict.Add("a", 1), "#1 add new");

    Assert.AreEqual(1, dict.Count, "#2");
    Assert.AreEqual(1, dict["a"], "#3");
#if ORDERED_DICTIONARY
    Assert.AreEqual("a", dict[0].Key, "#4");
    Assert.AreEqual(1, dict[0].Value, "#5");
#endif

    Assert.Throws<ArgumentException>(() => dict.Add("a", 2), "#6 add existent key");
#if ORDERED_DICTIONARY
    Assert.Throws<ArgumentException>(() => dict.Add(new Pair("a", 3)), "#7 add existent key");
#endif
  }

#if ORDERED_DICTIONARY
  [Test]
  public void TestInsertKeyValue()
  {
    var dict = new Dict();

    dict.Add("a", 1);

    Assert.DoesNotThrow(() => dict.Insert(0, "b", 2), "#1 insert new");

    Assert.AreEqual(2, dict.Count, "#2");
    Assert.AreEqual(2, dict["b"], "#3");
    Assert.AreEqual("b", dict[0].Key, "#4");
    Assert.AreEqual(2, dict[0].Value, "#5");

    Assert.Throws<ArgumentException>(() => dict.Insert(0, "a", 2), "#6 insert existent key");
    Assert.Throws<ArgumentException>(() => dict.Insert(1, "a", 2), "#7 insert existent key");
    Assert.Throws<ArgumentException>(() => dict.Insert(0, new Pair("a", 3)), "#8 add existent key");
    Assert.Throws<ArgumentException>(() => dict.Insert(1, new Pair("a", 3)), "#9 add existent key");

    Assert.Throws<ArgumentOutOfRangeException>(() => dict.Insert(3, "c", 3), "#10 insert to out of range");
    Assert.Throws<ArgumentOutOfRangeException>(() => dict.Insert(-1, "c", 3), "#11 insert to out of range");
  }
#endif

  [Test]
  public void TestRemoveByKey()
  {
    var dict = new Dict();

    dict.Add("a", 1);

    Assert.IsFalse(dict.Remove("b"), "#1 remove non existent key");

    Assert.AreEqual(1, dict.Count, "#2");

    Assert.IsTrue(dict.Remove("a"), "#3 remove existent key");

    Assert.AreEqual(0, dict.Count, "#4");
  }

  [Test]
  public void TestContainsKey()
  {
    var dict = new Dict();

    dict.Add("a", 1);

    Assert.IsFalse(dict.ContainsKey("b"), "#1 non existent key");
    Assert.IsTrue(dict.ContainsKey("a"), "#2 existent key");
  }

  [Test]
  public void TestTryGetValue()
  {
    var dict = new Dict();

    dict.Add("a", 1);

    int val;

    Assert.IsFalse(dict.TryGetValue("b", out val), "#1 non existent key");

    Assert.IsTrue(dict.TryGetValue("a", out val), "#2 existent key");
    Assert.AreEqual(1, val, "#3");
  }

#if ORDERED_DICTIONARY
  [Test]
  public void TestKeysReadOnly()
  {
    var dict = new Dict();

    Assert.Throws<NotSupportedException>(() => dict.Keys.Add("x"), "#1");
  }

  [Test]
  public void TestValuesReadOnly()
  {
    var dict = new Dict();

    Assert.Throws<NotSupportedException>(() => dict.Values.Add(-1), "#1");
  }
#endif

  [Test]
  public void TestKeys()
  {
    var dict = new Dict();

    Assert.IsNotNull(dict.Keys, "#1-1 initial state");
    CollectionAssert.IsEmpty(dict.Keys, "#1-2 initial state");

    dict.Add("a", 1);

    CollectionAssert.AreEqual(new[] {"a"}, dict.Keys, "#2-1 after insert item");

    dict.Add("b", 2);

    CollectionAssert.AreEqual(new[] {"a", "b"}, dict.Keys, "#2-2 after insert item");

    dict["a"] = 0;

    CollectionAssert.AreEqual(new[] {"a", "b"}, dict.Keys, "#3 after set item");

    dict.Remove("a");

    CollectionAssert.AreEqual(new[] {"b"}, dict.Keys, "#3 after remove item");

    dict.Clear();

    CollectionAssert.IsEmpty(dict.Keys, "#4 after clear");
  }

  [Test]
  public void TestValues()
  {
    var dict = new Dict();

    Assert.IsNotNull(dict.Values, "#1-1 initial state");
    CollectionAssert.IsEmpty(dict.Values, "#1-2 initial state");

    dict.Add("a", 1);

    CollectionAssert.AreEqual(new[] {1}, dict.Values, "#2-1 after insert item");

    dict.Add("b", 2);

    CollectionAssert.AreEqual(new[] {1, 2}, dict.Values, "#2-2 after insert item");

    dict["a"] = 0;

    CollectionAssert.AreEqual(new[] {0, 2}, dict.Values, "#3 after set item");

    dict.Remove("a");

    CollectionAssert.AreEqual(new[] {2}, dict.Values, "#3 after remove item");

    dict.Clear();

    CollectionAssert.IsEmpty(dict.Values, "#4 after clear");
  }
}