Re: Implementing custom data structures

[RLake@...]

> Is it feasible to implement custom data structures for Lua?  For 
example,
> I'd like to be able to have a dictionary data structure (I'm sure that's 
the
> wrong term technically - but I'm not sure what to call it), which would
> allow for easy auto-completion.  Tables are excellent for looking up 
data
> given a string key, but obviously they won't work with only the first 
part
> of that key, so I need something different.

I guess that depends on how big the table is. Autocompletion doesn't have 
to
terminate in microseconds, and linear search of a table of say 100 
elements
is not going to take much time.

> The data structure itself isn't
> too hard - I know I can create a new userdata, and set up a metatable to 
let
> me access the items, the trouble is storing those items.

> Since I want to be able to reuse this in slightly different 
circumstances, I
> don't know what type each data item will be - it could a table, a 
string,
> anything really.  So I need some way of storing a lua object directly in 
my
> own system.

In this case, you don't actually need to store the items. Just store the 
key
which you know to be a character. You can look up the value in the 
original
table, given the key. But I wouldn't bother unless you were anticipating a
table of tens of thousands of entries.

> I've considered using the registry to store the items, and just storing an
> index into the registry within my own data structure, but I don't know 
how
> efficient this will be, and I'd prefer a better way if there is one. The
> only other option I can see is to start hacking the Lua code.  Is there
> another way?

See above :) Storing in the registry is efficient enough, but it leaves 
you
to deal with making sure the references disappear at appropriate moments,
which might be very challenging.

By the way, a trick I often use is to store the key indices in the same
table; you can get away with that if you know that all the keys are
not numbers. (Say, they are all strings.)

(And you don't have to worry about the n field, either):

U:\>lua
Lua 5.0  Copyright (C) 1994-2003 Tecgraf, PUC-Rio
> a = {"m", "l", "k", "n",
>> k = "kuchen", l = "ladyfinger", m = "marzipan", n = "nougat"}
> table.setn(a, table.getn(a))
> table.sort(a)
> table.foreach(a, print)
1       k
2       l
3       m
4       n
k       kuchen
m       marzipan
l       ladyfinger
n       nougat
> table.foreachi(a, print)
1       k
2       l
3       m
4       n
>