Re: [boost] Review managers wanted for augmented data structures

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2013-03-02 09:21:35

On Wed, Feb 27, 2013 at 1:08 AM, Vadim Stadnik <vadimstdk_at_[hidden]> wrote:
> Hi all,
>
>
> At present, neither Boost library nor STL provides containers using
> augmented data structures. I suggest that the Boost community consider
> solving the challenging problem – how to extend STL by integrating advanced
> data structures.

> [...]
> Augmented red-black trees could have been included in the very first
> version of STL.
>
> Why is it difficult and has not been done yet?
>
> The major obstacle for the integration is the C++ standard specification of
> computational complexities of single operations for containers and
> iterators.

I totally agree.

> [...]
> There are two libraries in the Boost review schedule:
>
>
> http://www.boost.org/community/review_schedule.html
>
>
> "STL Extensions" and "Countertree". None of them has as yet a review
> manager. The order of the reviews may not be significant. It is more
> important that at least one library pass the review. This would help
> integrating other advanced data structures.
>
> Are there Boost experts who could volunteer to take responsibility of
> review manager for any of these two libraries?

I really hope that some expert jumps in.

In the meantime, I would like to point out some previous proposals of
similar containers (including mine):

2004 (The oldest mention I could find. I don't know if it got
implemented): http://lists.boost.org/Archives/boost/2004/03/62823.php
2006: "Hierarchical Data Structures"
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierarchy.augment
2006: "AVL Array" (terrible name, I know)
http://sourceforge.net/projects/avl-array
    Renamed as "Rank List" after some debate when proposed for Boost:
http://boost.cvs.sourceforge.net/viewvc/boost-sandbox/boost-sandbox/libs/rank_list/
    This last version is probably outdated with respect to "AVL Array".
And finally...
2012: Countertree
http://dl.dropbox.com/u/8437476/works/countertree/doc/index.html

I think that there are very interesting ideas in some of them.

The "Hierarchical Data Structures" proposed "cursors" in addition to
the ordinary iterators, to let the user traverse the tree at will
---not necessarily in-order---. In my proposal (AVL Array / Rank
List), I decided to hide the internal structure of the tree, offering
only iterators. As a result, I had to offer some additional methods,
like a binary search (provided that the sequence is sorted). Later I
found myself hacking into the tree structure to make some other
experiments!

I proposed augmenting the tree with an integer counting nodes in each
subtree ---like all others--- but I also proposed augmenting the tree
with a user-defined type. In the normal view of a sequence, every
element occupies a unit of space. In what I called "Non-Proportional
Sequence View" the user can decide the "virtual space" occupied by
every element, and then jump to any position in that "virtual scale"
in O(log N) time.

I made some design decisions favouring functionality and low
computational complexity over space. Every node contained pointers to
the next and previous nodes in-order. Between this and the NPSV, they
used a lot of space. At some point I increased their size even
further, and the shocking result was that my experiments run faster.
This leads me to think that a specific allocator ---like the one
proposed in Countertree--- might help a lot.

I also played with this concept of sequence ---with O(log N) random
access and O(log N) insertion/removal--- in permanent storage. See
"Shiftable Files" in the project "AVL Array". It is a toy
implementation, but it works.

I will love to discuss these ideas if anybody is interested. I would
have said all this before, but I was disconnected from the Boost list
for a long while and I didn't know that augmented trees had been
proposed again. Sorry.

Best regards,
Martín Knoblauch Revuelta