Potential order statistic tree?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Potential order statistic tree?

Boost - Dev mailing list
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
[hidden email]

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Potential order statistic tree?

Boost - Dev mailing list
On Sun, Dec 27, 2020 at 6:00 PM Soronel Haetir via Boost <
[hidden email]> wrote:

> Would there be interest in adding an order statistic tree to the boost
> library?
>

I had to search my Boost dev email history to recall how many times that
data structure has been suggested... It's at least half a dozen times :-)
It's been suggested enough that Boost Multiindex already supports it <
https://www.boost.org/doc/libs/1_75_0/libs/multi_index/doc/tutorial/indices.html#rnk_indices>.
Hence you'll need to point out a comparison between what you did and what
exists (and possibly what has been suggested in the past) to better inform
why your version of this should be adopted. As, clearly, there's historical
interest.


--
-- René Ferdinand Rivera Morell
-- Don't Assume Anything  -- No Supone Nada
-- Robot Dreams - http://robot-dreams.net

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Potential order statistic tree?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list


> -----Original Message-----
> From: Boost <[hidden email]> On Behalf Of Soronel Haetir via Boost
> Sent: 27 December 2020 23:50
> To: [hidden email]
> Cc: Soronel Haetir <[hidden email]>
> Subject: [boost] Potential order statistic tree?
>
> 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.

You need not be *too* concerned about previous C++ versions.  For a new library, you can simply specify the platform and compiler versions (and minimum C++ standard version) required.  It is highly desirable that it works with recent MS, Clang and GCC versions (and you have ticked two those boxes).

(You may be able to get it working with older tools by requiring certain features whose availability is defined by macros).

Of course, we would hope that you would do the necessary maintenance for future C++ versions - (perhaps you should worry more about that đŸ˜‰ )

(I am entirely unqualified to speak about the usefulness etc of your library).

Paul




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Potential order statistic tree?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 28/12/2020 3:51, René Ferdinand Rivera Morell via Boost wrote:

> On Sun, Dec 27, 2020 at 6:00 PM Soronel Haetir via Boost <
> [hidden email]> wrote:
>
>> Would there be interest in adding an order statistic tree to the boost
>> library?
>>
>
> I had to search my Boost dev email history to recall how many times that
> data structure has been suggested... It's at least half a dozen times :-)
> It's been suggested enough that Boost Multiindex already supports it <
> https://www.boost.org/doc/libs/1_75_0/libs/multi_index/doc/tutorial/indices.html#rnk_indices>.
> Hence you'll need to point out a comparison between what you did and what
> exists (and possibly what has been suggested in the past) to better inform
> why your version of this should be adopted. As, clearly, there's historical
> interest.

There was a pull request to Boost.Intrusive adding Augmented binary
search trees. At that time there was not much interest from other users,
but it seems a good starting point, it does not seem a very big patch:

https://github.com/boostorg/intrusive/pull/3

We'd need to add tests to this feature to make sure it is not broken in
newer versions.

Best,

Ion

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost