Array as deque: API thoughts

Now that the map object is finished, the array is the only remaining intrinsic data type on the development plan. The point of an array, of course, is to store a series of values in some specific order, and to allow efficient access to those values by index. Radian’s arrays will use a densely-packed zero-based ascending index, which is to say they will not have gaps, and that an array containing N items will store values at indexes 0..(N-1). Perhaps someday it will make sense to allow a variable lower bound, or to allow gaps in the index, but for now I don’t want to worry about those complications.

An array is a container, so it will have empty? and size functions. It is a sequence, so it will have iterate. It is also an indexed container, so it will also have a [lookup] function and the insert and remove methods.

The best way to implement this data structure is, without a doubt, the finger tree. This is an immutable data structure which offers some highly appealing performance characteristics and has enough versatility to serve as the foundation of a deque, a string, an array, a priority queue, and more.

Ah yes, the deque. I grew up on arrays, but these days I more often find myself reaching for queue, stack, or deque classes when I need to keep a list of values in some order. Most of the time, it turns out, all I really need is a way to construct a list and review it in order, or possibly in reverse order. The Radian library definitely needs to include such tools.

So why not, I wonder, fold the deque right into the array? The finger tree offers amortized constant-time read and write access to the first and last item in the array, so the deque operations would practically come along for free if I decided to expose them. Methods push, pop, and head would let you insert, remove, or lookup the item at one end of the list, and add, shift, and tail would let you work with the item at the other end. Push/pop/head gives you a stack; push/shift/tail gives you a queue going in one direction, and add/pop/head gives you a queue going in the other direction.

I’m not completely satisfied with this nomenclature: in particular, I don’t think shift is quite right for an operation which removes the last entry from the array. It feels like it ought to remove the first entry, thus shifting all the other elements back. That would certainly work, but then “pop” has to move to the end of the list, which means “push” has to come with it, and now the head and the tail are backwards. Could the head really be the last element of the array, and the tail represent element zero? No matter which way I try to arrange this, something ends up sounding a little bit wrong.