On 10/28/06, Hervé Brönnimann <hervebronnimann@mac.com> wrote:
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
Doesn't 'dictionary' imply a key-value relationship? Granted, one can think of the index as the key, but this key is not bound or related to the object. It changes the moment a new object is inserted before it. This is not an associative container, it is a sequence.
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.
I don't know that this structure with it's complexity guarantees can be implemented in multiple different ways... but how does that imply that the name doesn't fit? The name describes the advantages of the container: it is used as a list that supports random access. I havn't seen this type of sequence container in widespread use elsewhere, so why should we expect that there is an existing term to use as a precident?
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.)
It does not seem to me that this terminology is in conflict. Chaining is a verb, and chain is a noun. So there is no reason that you couldn't implement chaining with a chain, or with a list, or even with a vector. All of these make sense. In fact, I bet that a hash container that implemented chaining with a chain instead of a list might be pretty effective. Is chain really commonly used as a synonym for linked list? I havn't ever encountered that use of the term before. Although there exist naming precidents for the implementation of this structure, I don't believe there is a precident for naming its interface. As such, my opinion is that it is our responsibility to invent the terminology. We should find a name which is short, not already in use, and implies that this is a sequence (not a tree or associative container). Then as more people use it they would come to associate the term with its complexity guarantees. -Jason