Collection 2題：「WPFにバインドできる辞書」と「重複を許す検索set」

要素の追加

　これら二分検索アルゴリズムの助けを借りて、ソート済み配列に新たな要素を追加することができます。今回実装したのは、IList<T>を"重複を許すソート済み配列"として使うためのアダプタ:multiset_adaptor<T>です。multiset_adaptor<T>はそれ自身がinterfaceIList<T>を実装しており、

list10

  IList<int> body = new List<int>();
  multiset_adaptor<int> adaptor = new multiset_adaptor<int>(body, (x,y)=> x<y);
  adaptor.Add(3);
  adaptor.Add(1);
  adaptor.Add(5);
  ...

のように、adaptorにAddされた要素は、コンストラクト時に与えたIList<int>（ここではbody）内に、ソート状態を維持する位置に挿入されます。コンストラクタの第二引数はソート順を決定する関数オブジェクト:Func<T,T,bool>predで、pred(x,y)がtrueであるとき、xがyより手前（配列の先頭に近い側）に配置されます。

list11 multiset_adaptor.cs

using System;
using System.Collections.Generic;
using STeaL.Algorithm;
using System.Diagnostics;

namespace STeaL.Collections.Generic {

  public class multiset_adaptor<T> : IList<T> {

    public multiset_adaptor(IList<T> list, Func<T,T,bool> pred) { 
      list_ = list; 
      pred_ = pred;
      list_.sort(pred_);
    }

    private IList<T> list_;
    private Func<T,T,bool> pred_;

    public void ReOrder(Func<T,T,bool> pred) {
      pred_ = pred;
      list_.sort(pred_);
    }

    public bool Find(T item, out Tuple<int,int> range) {
      range = list_.equal_range(item, pred_);
      return range.Item1 != range.Item2;
    }

    public int IndexOf(T item) { 
      int first = list_.lower_bound(item,pred_);
      return pred_(item, list_[first]) ? -1 : first;
    }

    public void Insert(int index, T item) {
      if ( (index > 0 && pred_(item, list_[index-1])) ||
           (index < list_.Count && pred_(list_[index],item)) ) {
        throw new ArgumentException("disordered insertion");
      }
      list_.Insert(index, item); 
      Debug.Assert(list_.is_sorted(pred_));
    }

    public void RemoveAt(int index) { list_.RemoveAt(index); }

    public T this[int index] { 
      get { return list_[index]; }
      set { if ( (index > 0 && pred_(value,list_[index-1])) ||
                 (index < list_.Count-1 && pred_(list_[index+1], value)) ) {
              throw new ArgumentException("disordered replacement");
            }
            list_[index] = value;
            Debug.Assert(list_.is_sorted(pred_));
          }
    }

    public void Add(T item) { list_.Insert(list_.upper_bound(item,pred_), item); }
    public void Clear() { list_.Clear(); }
    public bool Contains(T item) { return list_.binary_search(item,pred_); }
    public void CopyTo(T[] array, int arrayIndex) { list_.CopyTo(array, arrayIndex); }
    public int Count { get { return list_.Count;} }
    public bool IsReadOnly { get { return list_.IsReadOnly;} }

    public bool Remove(T item) {
      Tuple<int,int> range = list_.equal_range(item, pred_);
      list_.erase(range.Item1, range.Item2);
      return range.Item1 != range.Item2;
    }

    public IEnumerator<T> GetEnumerator() { return list_.GetEnumerator(); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return list_.GetEnumerator(); }

  }

} 

最後に

　実装にあたり、前述の二分検索（lower_bound/upper_bound...）は標準C++ライブラリ（STL）の<algorithm>にある同名の関数テンプレートをC#にポートしました。それに伴い、<algorithm>が提供するいくつかの関数テンプレートをポートし、ライブラリ:steal.dllにまとめてあります。stealの全ソースコードはCodePlexに置いてありますから、興味のある方はぜひお立ち寄りください。

　今回実装を試みた、ObservableKeyedCollection<TKey,TItem>とmultiset_adaptor<T>を使ったサンプル:TwoDictionariesを用意しました。2つの辞書が示す挙動の違いに注目していただければ幸いです。

cherry,banana,apple,appleの順にAddしたところ