Re: [boost] [countertree] Formal Review Request

Subject: Re: [boost] [countertree] Formal Review Request
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-10-05 12:37:38

Thanks Mr Stadnik. At end, I forgot the references. The “Introduction to
Algorithms” is one of my favorite books. When I bought the book I had done
my first implementation of the counter trees. I tried to use the balanced
algorithms of the book in this version , but with counters of the nodes,
was impossible, and I began from zero to design the algorithms based on the
definition of Tree234. I will add references to the project. It can be
useful for the people.

 About the double augmented tree for support accumulate function in a log
(N) time, it is possible , but it is a hard work, because you must redesign
all the algorithms for to balance the tree.

 In the countertree the insertion or deletion NOT invalidate the existing
iterators. The iterator have a pointer to the node, and when you want to
know the position, travel from their position to the root examining the
node counters. If you insert an element in a previous position to one
iterator, you can access to the element pointed by the iterator, but when
you check the position you will obtain the next number. You can safely mix
access, insertion and deletion with iterators and positions. You have
arithmetic with the iterators, even with the end() and rend() iterators.

 unsigned D = V.end() - ( V.begin() +5) ;

 The arithmetic operations are log(N), because the iterators obtain the
position as I described before.

 About the dynamically allocated augmented B+ trees, I must read more, in
order to provide you a former opinion, but it looks very interested.

 About the Boost::container the data structures similar to the data
structures of countertree, are implemented ( as I understand) over sorted
vectors, or similar data structures, which have performance problems when
insert or delete in central positions. But I must study more.

 Regards

 Francisco Tapia