Re: pairs(t, skey) and ipairs(t, skey)

[Sean Conner <sean@...>]

It was thus said that the Great Dirk Laurie once stated:
> 2013/10/6 Tim Hill <drtimhill@gmail.com>:
> 
> > And in either case, you would still have O(n) performance
> 
> I can think of three possible faster-than-O(n) things you could
> reasonably accept:
> 
> 1. Making # mean the number of active keys of whatever class is O(1) worst-case.
> 2. Making # mean the largest positive integer key you have ever used for this
> table is O(1) worst-case.
> 3. Making # mean the largest positive integer key is O(log(n)) worst-case
> if you are willing to accept an O(n) storage penalty.

  I could see this working:

	For a table, set the internal N field (stored in the C structure for
	a table) to 0.
	
	When adding a value (__newindex)
	if N == 0 then
		if the index is 1, 
			scan linearly starting at 1 to find first nil at an
			integer index---store that index - 1 in N (this is
			to cover the case where a sequence is built
			backwards).
		else 
			add the index.  N isn't touched.
	
	else -- N > 0 and the index is an integer value
		if the index is one larger than N, and the value is not
		nil, then set N to the index, and set the index.

		if the index is <= 0, or larger than N+1, don't touch N, but
		add the value at the index.

	When updating a value:

	if the index is an integer
		if index >=1 and <= N, and the value is nil, then
			N = index - 1

  I think that should make # be O(1) for most use cases.

  -spc