In my e-mail of 20-Aug-92 I write (among other things):

What I would really like to have in GAP are *tables*, which are
basically mappings from arbitrary keys to values. A table where all
keys are positive integers is a list, a table where all keys are
strings is a record. Very elegant, very powerfull.

In his e-mail of 20-Aug-92 Steve Linton answers:

This isn't quite all-powerful. It would also be desirable to be able
to get at the keys in some order (think of heap-sort).

This comment does not make any sense to me. Could you please explain it?
There probably would be some function 'Keys( <table> )', which would
return the *set* of key values. For an arbitrary *list* <l> this would
be a (sorted) list of positive integers, for a dense list it would in
fact be a range. Then for an arbitrary table <table> writing
'Sublist(<table>,Keys(<table>))' (or '<tab>{ Keys( <tab> ) }') would give
you the *values* in the table in the order implied by the keys. Is this
what you mean?

Steve continues:

[...] However, possibly hashing is not the right way to go.

Have you considered something like a B-tree or a 2,3-tree (in Knuth
and AHU respectively)? This will cost you log n on a lookup, but
simply dpends on having fast 3-way comparison. This also allows
recovery in order.

The cost of doing a lookup in those trees is about the same as doing
a lookup in a sorted list. The advantage of those trees is of course
that insertion and deletion have cost $O(log(n))$, while insertion
and deletion from a sorted list is a $O(n)$ operation. On the other
hand, finding the <i>-th element in such a tree is also an
$O(log(n))$ operation, while it is an $O(1)$ operation in a sorted
list.

Martin.

--
Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany