I woud like a name focused on what it provides: a sequence, random access, insertion/deletion, logarithmic complexity, alternative index derived from the sum of 'widths'...
The technical term which you'll find in accepted text books for the ADT is OS-dictionary, or Order-Statistics Dictionary. Random-access dictionary might be just as adequate. Binary Tree with Rank does not speak about the ADT but about its implementation. As for the compaction of elements in width, it seems to fit with the framework of weighted data structures. There is quite a body of work focussing on the entropy function (where the weights describe some probability of access), but that's not what you have here, where the weights describe the number of elements/representatives. But that seems to fit with weight-balanced trees and the like. On Oct 28, 2006, at 10:37 AM, Jason Hise wrote:
I think random access list, or ralist, would be the most technically descriptive.
However, perhaps it would be preferable to create an association between an existing word that is currently unused for sequences and this new type of sequence container. How about chain?
vector, deque, chain, list... I think it fits right in.
I've never heard of RALists, which can be implemented in a number of ways (Skip lists, Jump lists, binary trees), so I don't think it's a very good term. Chain is plain bad, due to its ambiguity with chaining (hashing) and its quasi-synonymity with list in a number of contexts (buffer chain, hashing, etc.) -- Hervé Brönnimann CIS Polytechnic University