B-tree が書けたらまた自慢しに来ます。
書けました。一旦は append*1/split と添字でのアクセスと bisect*2 ができる列としての B-tree です。セグ木のような区間 fold 演算ができた方がいいのかもという気持ちもあります。
一応実装を貼っておきますが、初めてなので改善の余地はよちよちという感じです。
alloc::collections::btree::node をある程度参考にしつつ書いていて、ある程度は std::collections::BTreeMap の内部についてもわかってきつつ、だいぶ設計が異なるのでまだまだお勉強の余地があるかなという感じです。
LeafNode や InternalNode では B-tree のノード数の下限の制約を無視していて、それは BTreeMap 側で担保しているみたいなのですが、そうした方がいいのかな〜という気持ちがあったりなどします。
列としての B-tree であれば、(BTree|Hash)Map にあるところの .entry() の API は提供する必要がないんですよね。
と思いつつ、「bisect で見つけたあたりの場所が何らかの条件を満たすなら、その箇所に挿入する」のような操作はしたいことがしばしばあって、.entry() めいた I/F を使えたらいいのかもという気もします。
どうせそのうち $\circ\colon S\times S\to S$ とかを渡せるようにして書き直すだろうので、そのときにまた考えます。
参考文献
いつもの (CS166.1146/03) を見ました。
実装し終わった後、下記の記事を見つけました。これもよいと思います。
おわり
思ったより疲れているみたいで、あんまりまともに文章が書けませんでした。
また勉強したり休憩したりしたら、BTreeMap の設計や unsafe なコードのことや Stacked/Tree Borrows のことに関してまとめたい気持ちがあります。
一方、なんか、なんでこんなことやってんだろうなみたいな気持ちも湧いてくることがしばしばあり、危ないな〜というところですね。
簡潔データ構造についても何もまとめていなくてやば〜というところです。
