以下方針のメモ。間違っている部分があるかもしれない。
SkipListNodeSummableField<T>のようなクラスをSkipListNode<TItem, TNode>のインナークラスとして次のように作る。その構造はSkipListNodeに酷似していてやはりツリー類似の構造を持っているのでそのコンテナクラスを作ってやればLINQと整合的に高速な総和計算ができるというのがポイント。ただしこのクラスは自分自身では順序を定める方法を持たない点がスキップリストのノードとは異なる。その代わりにそのインスタンスはSkipListNodeの内部フィールドとして保持される。
class SkipListNodeSummableField<T>{
public TNode ThisNode;
public T[] Values;
public SkipListNodeSummableField<T>[]Next;
public SkipListNodeSummableField<T>[]Prev;
//SkipListNodeのコンストラクタから呼び出してください
public SkipListNodeSummableField(TNode ThisNode){
this.ThisNode=ThisNode;
}
//SkipListNodeのOnHeightDecidedメソッドをオーバーライドして
//このメソッドを呼び出してください
public SetHeight(){
if (values == null) {
Values = new T[ThisNode.Height];
} else {
Array.Resize(ref Values, ThisNode.Height);
}
}
//SkipListNodeのOnMaintainanceメソッドをオーバーライドして
//このメソッドを呼び出してください
public Maintainance(int depth){
if (IsHeader || IsFooter) return;
if(depth==0){
Values[0]=DecideValueDepthZero(ThisNode.Item);
}else{
Values[depth]=SkipList<TItem, TNode>.GetEnumerableInOrder
(ThisNode, true, ThisNode.Next[depth].Prev[depth-1]
.Select(summablefield=>summablefield.Values[depth-1])
.Aggregate(Composite);
}
OnMaintainance(depth);
}
//合成規則
public virtual T Composite(T a, T b){
throw new NotImplementedException();
}
//このメソッドをオーバーライドしてNext[depth]やPrev[depth]に
//ThisNode.Next[depth]やThisNode.Prev[depth]の適当なフィールドを
//指定してください
protected virtual OnMaintainance(int depth){
throw new NotImplementedException();
}
//このメソッドをオーバーライドしてThisNode.ItemからValues[0]を決定する
//方法を指定してください。
protected virtual T DecideValueDepthZero(TItem Item){
throw new NotImplementedException();
}
} SkipListNode<TItem, TNode>の継承クラスの実装としては例えば
class MyNode:SkipListNode<MyItem, MyNode>{
class VolumeSummableFiled:SkipListNodeSummableField<int>{
public int Composite(int a, int b){
return a+b
}
protected virtual OnMaintainance(int depth){
Next[depth]=ThisNode.Next[depth].Price;
Prev[depth]=ThisNode.Next[depth].Price;
}
protected virtual T DecideValueDepthZero(TItem Item){
return Item.Price;
}
}
public VolumeSummableField Volume;
public MyNode(){
Volume=new VolumeSummableField(this);
}
protected override void OnHeightDecided(){
Volume.SetHeight();
}
protected override void OnMaintainance(int depth){
Volume.Maintainance(depth);
}
}
という感じにする。
その上でコンテナクラスとして、SkipListRangeとSkipListSummableFieldRangeとを作る。これらはSkipListNode型あるいはSkipListSummableFieldRange型のInitial及びFinalフィールドを持つ。そして、SkipListRange型とSkipListSummableFieldRange型に対してIQueryableの実装を行う。これで、対応するノードの集合が連続である事を暗黙に仮定する事で、SkipListRange型に関してはFirst, Last, TakeWhile,
Whereメソッド等の高速化ができる。それが仮定できない場合にはIQueryableにダウンキャストしてやればQueryableクラスが提供する標準の拡張メソッドが使用されるという約束にすれば良い。つまり、インタフェースの明示的な実装という奴を使って、ダウンキャストされた場合全部Queryableクラスの静的メソッドに転送するようにすれば良い。LINQはインタフェースの実装を問わず、対応するインスタンスメソッドが存在すればそれを使い、次いでインタフェースの実装を試し、最後に拡張メソッドを探すので、(この優先順位はどこまでC#と拡張メソッドの仕様でどこまでLINQの仕様なのか良く把握できないないが)これでツリー類似の構造を利用した対応するノードの集合が連続である場合の高速なクエリと、対応するノードの集合が連続でない場合の標準的なクエリとを両立できる。SkipListSummableFieldRangeに関してはSumメソッド(Compositeメソッドによる合成だがLINQの他の実装との整合性からメソッド名はSumにすべきだろう)高速化する事が可能だ。
ここまでやれば、後一踏ん張りするとLINQ句への対応までできてしまうのだが、やっぱり何だか面倒そうだなあ。でも、ノードの集合が連続であると仮定した場合の高速なWhereができると、区間の削除が綺麗に実装できるんだよな。そのうち体調的に余裕がある時にまずLINQの独自実装のサンプルを作る事から初めてみよう。
