[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Virgin tables
- From: Dirk Laurie <dpl@...>
- Date: Thu, 30 Dec 2010 07:56:56 +0200
All the trouble people have with the table length function and
the table library, well over 100 posts by now, come down to one
thing, and one thing only:
The functions designed for use on tables without holes
don't actually give an error message when applied to
tables with holes.
Now it is very Lua-like to treat a programmer as a responsible
adult, but perhaps just a tiny bit of supervision may be useful.
I suggest this:
a function called table.virgin(t), returning 'true' if the
table t has never had a hole and 'false' otherwise.
* In a virgin table, #t is virtuous: it equals both the largest
numeric index and the number of entries with numeric keys.
* If you are very strict, you can replace table.insert etc by
versions that will warn you when you try to use the function
on a non-virgin table.
* It's an O(1) function. Virginity is lost by t[k]=nil for
k<#t and by t[k]=non_nil for k>#t+1, both easy to test.
* #t would be O(1) for all virgin tables. (At present, many
numeric entries may actually reside in the hash part of the
table, and then #t takes O(log n) time.)
* It would be inefficient if not in the standard library.
Now of course it would be possible for a non-virgin table, after
undergoing certain operations, to be free of holes again. To cover
the case where there is reason to believe that might be true, there
could also be a function table.absolve(t), that would test whether t
is hole-free and in that case restore the property of virginity.