"辞書"を作る
1.WPFにバインドできる辞書
前置きが長くなりました...さて、僕が開発屋さんに頼まれてツールを作るとき、決まって必要になるのが辞書:Dictionaryです。検索キー（key）とそれに紐づいた値（value）との対応表ですね。前置きでお見せした「名前と連絡先の表」は辞書の典型例です。
ListBox/ListViewにバインドさせたObservableCollection<T>は単純な可変長配列であり、こいつを辞書として機能させるには挿入/検索などを自前で実装しなければなりません。辞書として使えるコレクションはないかとライブラリをうろついて、KeyedCollection<TKey,TItem>を見つけました。
ただし、KeyedCollection<TKey,TItem>をそのまま使うことはできません。WPF上のListBox/ListViewにバインドできるコレクションはinterface INotifyCollectionChangedを実装、要はコレクションに対する要素の追加/削除/変更に応じて適切なイベントを発行しなければなりません。ListBox/ListViewはそのイベントに反応して画面の更新を行いますから。
幸いなことにKeyedCollection<TKey,TItem>はイベント発行を埋め込むのにうってつけのprotected virtualメソッドがいくつか定義されているので、これらを再定義することで「WPFにバインドできる辞書:ObservableKeyedCollection<TKey,TItem>」を実装しました。
やっていることはいたって単純、class KeyedCollection<TKey,TItem>とinterface INotifyCollectionChangedから導出し、要素の追加/変更/削除/クリア時に呼び出されるメソッド:InserItem/RemoveItem/SetItem/ClearItems内でそれぞれに応じたイベントを発行するだけ。
using System.Collections.ObjectModel;
using System.Collections.Generic;
using System.Collections.Specialized;
using STeaL.Collections.Specialized;
namespace STeaL.Collections.ObjectModel {
public abstract class ObservableKeyedCollection<TKey, TItem> : KeyedCollection<TKey, TItem>, INotifyCollectionChanged {
public ObservableKeyedCollection() : base() { }
public ObservableKeyedCollection(IEqualityComparer<TKey> comparer) : base(comparer) { }
public ObservableKeyedCollection(IEqualityComparer<TKey> comparer, int dictionaryCreationThreshold) : base(comparer, dictionaryCreationThreshold) { }
protected override void InsertItem(int index, TItem item) {
base.InsertItem(index, item);
CollectionChanged.NotifyAdd(this, item, index);
}
protected override void SetItem(int index, TItem item) {
base.SetItem(index, item);
CollectionChanged.NotifyReplace(this, item, index);
}
protected override void RemoveItem(int index) {
TItem item = this[index];
base.RemoveItem(index);
CollectionChanged.NotifyRemove(this, item);
}
protected override void ClearItems() {
base.ClearItems();
CollectionChanged.NotifyReset(this);
}
public event NotifyCollectionChangedEventHandler CollectionChanged;
}
}
2.要素の重複を許す集合
と、ここでちょっと問題がありまして...こうやって作ったObservableKeyedCollection<TKey,TItem>およびそのベースとなったKeyedCollection<TKey,TItem>は検索キーが同じ複数の要素を格納できないんです。なのでメール,電話,twitterIDなど複数の連絡先を持った人を"名前-連絡先の表"に載せるとなると連絡先がどれか1つに限られてしまいます。いくつものメール・アドレスや電話番号を持っている人なんて、いまどき珍しくもなんともありませんよねぇ。
...というわけで、要素の重複を許す辞書を作ることにしました。挿入/削除に多少の時間はかかるものの、実装の楽な「ソート済み配列」を使うことにします。ソート済み配列ならキーを指定して検索をかけたとき、得られる複数（0コ以上）の検索結果が"配列のココからココまで"つまり配列インデクスのペア（2つ組）で得られます。
二分検索
ソートされた配列から特定の要素を検索するとなれば、使うアルゴリズムはド定番の二分検索でしょうね。IList<T>に対する拡張メソッドで定義してみましょう。2つの要素を比較する関数オブジェクト:Func<T,T,bool>predに基づいてソートされた要素列:list[first]～list[last-1]の中に、ソート状態を維持したまま新たな要素:T valを挿入するときの挿入位置の最小値/最大値を返す関数:lower_bound/upper_boundを実装します。ついでにこの2関数が返す値をペアにして返すequal_rangeや要素が配列内に存在するか否かを調べるbinary_searchも。
using System;
using System.Collections.Generic;
using STeaL.Functional;
namespace STeaL.Algorithm {
public static partial class IListExtensions {
#region lower_bound
public static int lower_bound<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred) {
int count = last - first;
while ( 0 < count ) {
int count2 = count / 2;
int mid = first + count2;
if ( pred(list[mid], val) ) {
first = ++mid;
count -= count2 + 1;
} else {
count = count2;
}
}
return first;
}
#endregion
#region upper_bound
public static int upper_bound<T>(this IList<T> list, int first, int last, T val, Func<T, T, bool> pred) {
int count = last - first;
while (0 < count) {
int count2 = count / 2;
int mid = first + count2;
if (!pred(val,list[mid])) {
first = ++mid;
count -= count2 + 1;
} else {
count = count2;
}
}
return first;
}
#endregion
#region equal_range
public static Tuple<int,int> equal_range<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred) {
int count = last - first;
while ( 0 < count ) {
int count2 = count / 2;
int mid = first + count2;
if ( pred(list[mid], val) ) {
first = ++mid;
count -= count2 + 1;
} else if ( pred(val, list[mid]) ) {
count = count2;
} else {
return Tuple.Create(lower_bound(list,first,mid,val,pred), upper_bound(list,mid+1,first+count,val,pred));
}
}
return Tuple.Create(first, first);
}
#endregion
#region binary_search
public static bool binary_search<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred, out int index) {
index = lower_bound(list, first, last, val, pred);
return ( index != last && !pred(val, list[index]));
}
public static bool binary_search<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred) {
first = lower_bound(list, first, last, val, pred);
return ( first != last && !pred(val, list[first]));
}
#endregion
}
}
