Re: Newbie question on pairs and ipairs

[Rici Lake <lua@...>]

On 16-Dec-04, at 12:59 AM, Glenn Edgar wrote:

> Hi
>
> The source code indicates that a lua table consists of two parts, an 
> array
> part and a hash table part.  It also appears that ipairs iterates over 
> the
> array part and pairs iterates over both the array and hash table part.

Not quite. ipairs iterates over integer keys, starting from 1, until it 
finds one which is not in the table. It is quite possible for an 
integer key to be in the hash part of the table; you should regard the 
internal implementation of the table as two parts to be an 
implementation detail.

> If my understanding is correct, I would like to ask the following 
> question.
>
> What is the best way to iterate over the keys that are only in that 
> hash table
> part of the table?

The semantic definition of Lua avoids making reference to 
implementation details (which is correct, imho), so there is no way to 
do that, either with Lua or even with the C API.

The solution proposed by Asko is one possibility, but it suffers from 
two flaws: first, if there are a lot of integer keys, it does a lot of 
unnecessary work; and second, if the integer keys are not contiguous, 
then it will miss some keys which would also be missed by ipairs. This 
might not be a concern.

If you want a table which can be iterated separately by numeric or 
non-numeric keys, I recommend that you use two tables. Something like 
the following might work for you:

do
  -- metatable sorts gets and sets by type of key
  local meta = {}
  function meta:__index(k)
    return self.numeric[k] or self.nonnumeric[k]
  end
  function meta:__newindex(k, v)
    if type(k) == "number" then
      self.numeric[k] = v
      if k > self.n then self.n = k end
     else
      self.nonnumeric[k] = v
    end
  end

  -- constructor creates the subtables, sets 'n', and
  -- assigns the metatable
  function SplitTable()
    return setmetatable({numeric = {},
                         nonnumeric = {},
                         n = 0},
                        meta)
  end

  -- two iterators, one for each part
  -- The numeric iterator uses our own stored n,
  -- but it could have been written more simply
  -- with ipairs. The advantage of this one is
  -- that it allows vectors with nil's in them.
  -- (but doesn't return the keys with nil values)

  local function numeric_iter(st, i)
    for testkey = i + 1, st.n do
      local testval = st.numeric[testkey]
      if testval ~= nil then
        return testkey, testval
      end
    end
  end

  -- we don't attempt to deal with non-positive or
  -- non-integer keys. That's left as an exercise
  -- for the reader
  function numerics(st)
    return numeric_iter, st, 0
  end

  -- The nonnumeric iterator just punts to next
  function nonnumerics(st)
    return next, st.nonnumeric, nil
  end
end

-- test code
-- Simple Sieve of Erastothenes, which builds a factorisation
-- table up to its argument.
function sieve(n)
  local factored = {}
  for prime = 2, math.sqrt(n) do
    if not factored[prime] then
      for factor = 2, n / prime do
        factored[prime * factor] =
          string.format("%d x %d", prime, factor)
      end
    end
  end
  return factored
end

-- Test the sieve
do
  local f = sieve(52)
  for i = 2, 52 do
    if f[i] then print(string.format("%d = %s", i, f[i]))
            else print(string.format("%d is prime", i))
    end
  end
end

-- Now create a SplitTable whose keys are the primes up to 52
-- and the English vowels

primesAndVowels = SplitTable()
do
  local factored = sieve(52)
  -- note: ipairs won't work here
  for i = 2, 52 do
    if not factored[i] then
      primesAndVowels[i] = "prime"
    end
  end
end

for char in string.gfind("aeiouyAEIOUY", "(.)") do
  primesAndVowels[char] = "vowel"
end

-- And what do we have?
for k, v in numerics(primesAndVowels) do
  print(k, v)
end

for k, v in nonnumerics(primesAndVowels) do
  print(k, v)
end