Implementation

Node クラス

Node<T> は、WBList<T> と WBTreeBase<T> で共通とする。

Set と MultiSet の分離

次の実装方法がある：

• Set と MultiSet、Map と MultiMap を分離する
  • IsDistinct を抽象プロパティとする
• Set と MultiSet、Map と MultiMap を分離しない
  • コンストラクターで IsDistinct を指定する
  • Map と MultiMap を共通化するのが難しい

前者を採用。

GetFirst, GetAt などの戻り値

次の実装方法がある：

• T 型
  • 合致するノードが存在しない場合の処理が複雑
  • GetItemOrDefault, TryGetItem などを個別に実装
• Node<T> 型
  • 合致するノードが存在しない場合、null を返す
  • GetItemOrDefault, TryGetItem などをサポートするため、NodeHelper クラスにより拡張メソッドを提供する

後者を採用。

RemoveNode メソッド

次の実装方法がある：

• 葉のアイテムと入れ替えて、葉を削除する
  • 簡易的な実装
  • 指定されたノードのインスタンスが木から削除されるとは限らない
• 葉のノードと入れ替えて、葉を削除する
  • 少し複雑な実装
  • 指定されたノードのインスタンスが木から削除されるため、副作用が少ない

後者を採用。
また、削除後のリバランスはしない。

WBTreeBase.Initialize メソッド

CreateSubtree メソッドを呼び出す前に、次が保証されなければならない：

• ソート済み
  • Initialize メソッド内で加工が可能
• キーの一意性 (IsDistinct の場合)
  • 重複する値が存在するときにどれを採用するか確定しないため、Initialize メソッド内で加工が不可能

Set, Map

重複する値が存在する場合、例外を発生させる。

• useRawItems が true のとき (一意かつソート済みであることが保証されるとき)、
  • そのまま CreateSubtree メソッドを呼び出す (最速)
• useRawItems が false のとき (一意かつソート済みであることが保証されないとき)、
  • ソート (安定である必要はない)、重複チェックをしてから CreateSubtree メソッドを呼び出す (高速のため採用)
  • または、AddOrGetNode メソッドを呼び出しながら重複チェック (低速)

重複の無視

ignoreDuplicates パラメーターの導入を検討していたが、AddItems メソッドを呼び出すだけになるため実装せず。
重複を無視するには、Initialize メソッドの代わりに AddItems メソッドを呼び出す。 ただし低速のため、なるべく一意かつソート済みに加工してから Initialize メソッドを呼び出すのが望ましい。

MultiSet, MultiMap

重複についての制約がないため、ソート済みかどうかだけで分岐する。

• useRawItems が true のとき (ソート済みであることが保証されるとき)、
  • そのまま CreateSubtree メソッドを呼び出す (最速)
• useRawItems が false のとき (ソート済みであることが保証されないとき)、
  • 安定ソートをしてから CreateSubtree メソッドを呼び出す (高速のため採用)
  • または、AddItems メソッドを呼び出す (低速)

WBTreeBase.AddOrGetNode メソッド

IsDistinct が true かつ指定されたアイテムが既に存在する場合、ノードを追加しない。
IsDistinct が false かつ指定されたアイテムが既に存在する場合、同じ順位のアイテムの末尾に追加する (安定ソート)。

ComparerHelper クラス

ComparerHelper<T> クラスに型引数 T を指定することで、Create メソッドを呼び出すときに型引数 <T, Tkey> の指定を省略できる。