Potential order statistic tree?

From: Soronel Haetir (soronel.haetir_at_[hidden])
Date: 2020-12-27 23:50:14

Boost developers,

Would there be interest in adding an order statistic tree to the boost
library? That is, a tree that instead of being sorted simply keeps
nodes in whatever order is specified, along with a (potentially
multi-index) per-node value and a total of per-node values of each
node and its left-descent tree.

I currently have two such types, a very capable intrusive version (not
based on boost::intrusive though using some of the same ideas) and a
less capable non-intrusive form that uses the mechanics of the
intrusive form as an implementation detail. The reason for not being
based on Boost.Intrusive is that the tree algorithms that
Boost.Intrusive provides are all for search trees and this very
definitely is not, plus the need to alter node weights during insert,
delete and rotations and the Boost.Intrusive algorithm providers not
having a good place to add that behavior.

I have personally found this type very useful while implementing a
rope container and also while implementing tracking for various parts
of a text editor (that is, paragraph, line and run positions) (in
terms of characters, graphemes and screen height).

Perhaps the major drawback to what I have is that I have not been
careful to isolate c++-version dependent code. Although I know it does
compile with the latest msvc 2019 as well as the clang 10.0 that MS
ships.

I am simply not sure whether such a type has a broad enough appeal to
make the work of adding it to boost worthwhile.

-- 
Soronel Haetir
soronel.haetir_at_[hidden]