> < ^ From:

> ^ Subject:

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

> < [top]