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