From: Rene Rivera (grafik.list_at_[hidden])
Date: 2004-03-17 00:24:49
Jeremy Maitin-Shepard wrote:
> This seems like a useful data structure, although I can't think of any
> specific use cases.
I use such a data structure right... keeping track of a GUI list that can have
items inserted/removed in it. A regular number->item map doesn't work as it
has to change the index of items on inserts/deletes.
> I am assuming you are implementing it as a balanced binary tree where
> you keep track of the number of nodes in the subtree rooted at each
> node. (This allows finding a node by its numeric index in time.)
That is how I implemented it. The data structure is called a "rank tree",
describe in the white book. I've mentioned the structure in this list before :-)
-- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk