ordered numeric set vs. tinsert()

["Fabio Reis Cecin" <frcecin@...>]

(this is more of a suggestion than a real question... :-)

I'm using a table as an ordered, sparse set of numeric
keys:

-- example numeric set "set", created in ordered fashion
set = { }
set[0] = 1
set[4] = 1
set[65535] = 1

-- removing an element (maintains order.. right?)
set[4] = nil

Now, how could I insert element 6 in "set" and still
maintain the ordering, so I can use next() (=fast)
instead of foreachi() or a "numeric for" (=slow for
sparse sets) to traverse the table in crescent order?
(0 --> 6 --> 65535)

"tinsert()" asks for the position where I want the
element inserted. so I guess that what I need is
a function that does a binary search. (?)

I can do this in Lua, or do this in C and expose it
to Lua, but it would be nice to achieve this using
the standard lualib.

ANSI C has a binary search function, maybe this
could be used to implement a Lua "bsearch()"
function? :

<stdlib.h>

   void* bsearch(const void* key, const void* base,
     size_t n, size_t size, int (*cmp)(const void*
     keyval, const void* datum)); 

  Searches ordered array base (of n objects each of size size) for item
matching key according to comparison function cmp. cmp must return
negative value if first argument is less than second, zero if equal and
positive if greater. Items of base are assumed to be in ascending order
(according to cmp). Returns a pointer to an item matching key, or
NULL if none found. 


--
[]'s
Fábio R. Cecin
frcecin@terra.com.br