Re: [boost] [proposal] Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2006-10-31 01:07:09

Martin Knoblauch Revuelta wrote:

>   How about a sequence container (like a vector) with the advantage of
> logarithmic time insertion/removal at any point of the sequence? The
> disadvantage is that random access takes logarithmic time too (instead
> of the usual constant time random access of a vector).

Sorry if these where already mentioned, but I just got around to looking 
at the implementation:

* There's no need for the m_next and m_prev fields. You can do inorder, 
preorder, postorder, and others without them.

* I suspect you don't need the m_height either. But I don't know what 
you are using it for yet.

* In my rank tree implementation the only extra field per node is the 
count, what you call width (as separate node and total). If I remember 
correctly in CLRS they describe the possibility of the count not 
directly reflecting the subtree+1 size to allow for sparse trees. I 
suspect that you can remove the need for the different m_node_width and 
m_total_width, using one only, by deducing the m_node_width from "count 
- left_count - right_count".

* Overall you need to make use of STD utilities more. I think someone 
already mentioned something to this effect. Another example is using the 
iterator tags and other meta information. This is important to help out 
type specific algorithms.

* Also putting implementations out-of-line would help in reading what 
the various interfaces do. I also dislike the use of abbreviations and 
single letter symbols, as it makes it harder to read. But this is mostly 
a matter of taste :-)

* I don't see how not having a static allocator prevents moving nodes 
across equally typed containers.

* I get the impression that there's is way more code than needed to 
implement this data structure.

* You should use the allocator types instead of making types out of the 
value type directly.

* Not sure why you would want the various unsigned/int/long vs size_type 
variations of methods. Having those extra methods just confuses the 
interface for users and introduces extra use cases to account for in the 
implementation.

* operator=(o) can't be O(max(N,M)). You have to both construct the new 
elements and destroy the existing elements which makes it O(M+N), and 
keeping exceptions in mind you do a swap in between :-)

* You have a variety of C style casts, and you happen to be casting 
"this". That's frowned upon, and truthfully I can't see why you do it.

* Algorithms rarely have a place in STL containers. You might want to 
move the various binary_search, sort, etc. methods to functions. 
Preferably having them use the same interface as the STD versions.

* I would make the value sorted aspect a separate container, possibly as 
an adaptor to the rank container but possibly also some other form of 
tree. Sorted ordering is orthogonal to rank statistics.

* You seem to be using a sentinel node as a hybrid root and tail node 
but making the avl_array itself that sentinel node. To say the least 
this is a bit strange to me. Why not have just a root pointer to a real 
root node?

Now for naming...

I don't think I'll ever be able to refer to this as anything other than 
a rank tree, even with the addition of a sparse version. Obviously you 
named it avl for the type of balancing you are doing. As for some of the 
other suggested names they fall into two categories: structure 
(log_list, llist, larray, chain, random_list, rlist, ralist, 
ra_sequence) and category (os_tree, order statistics dictionary, and the 
variety of synonyms for sequence).

The category terms fail to account for implementations of other 
exemplars from that category. This is the reason why STL doesn't have a 
"container" class... I know it's an exaggerated example :-)

The STL tends to stick closely to using implementation related terms 
which would fit more closely with using structure terms. Programmers 
find this intuitive because they learn data structures and algorithm, 
and hence they can use the names as an indication of what to expect from 
the implementation of the containers. Unfortunately this rules out all 
the proffered terms as they suggest implementations other than an 
augmented binary tree.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo