Boost logo

Boost :

From: Rene Rivera (grafik.list_at_[hidden])
Date: 2004-03-18 11:28:51

David B. Held wrote:
> "Rene Rivera" <grafik.list_at_[hidden]> wrote in message
>>I look at the implementation and it doesn't do what a rank tree does.
>>It does make it easier to base a rank tree implementation against it.
>>The part that is missing is keeping track of the rank of nodes as the
>>tree changes, the constant time op, that lets one have the logN ops
>>later on. [ Unless I missed something -- So correct me at will ;-) ]
> Hmm...are you sure? Did you look at the rotate_right() and rotate_left()
> functions? The "indexes" wouldn't be correct if you didn't adjust them
> on insert/delete. Essentially, what I call "index" is probably what you
> call "rank".

No I wasn't sure, hence why I said I may have missed something ;-) Yes you are
correct it does have the functionality. It still took me a while to find the
exact place even with your hint above, IndexedNode rotate* and update*, that
has the count.

> does. You might want to take a closer look at that if you haven't
> already. I probably will soon so I can give it a thorough review.

Will do :-)

-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. -
-- rrivera/ - grafik/ - 102708583/icq

Boost list run by bdawes at, gregod at, cpdaniel at, john at