Extending ipairs for use in sparse arrays

The ipairs function in the Lua language is used to iterate over entries in a sequence. This means every entry must be defined by the pair of key and value, where the key is the integer value. The main limitation of the ipairs function is that the keys must be consecutive numbers.

You can modify the ipairs function so that you can successfully iterate over entries with integer keys that are not consecutive. This is commonly seen in sparse arrays.

Getting ready

In this recipe, you'll need to define our own iterator function, which will return every entry of a sparse array in deterministic order. In this case, the iterator function can be included in your code as a global function to accompany pairs and ipairs functions; or you can put it in a Lua module file not to pollute the global environment space.

How to do it…

This code shows a very simple sparse array iterator without any caching:

function ipairs_sparse(t)
  -- tmpIndex will hold sorted indices, otherwise
  -- this iterator would be no different from pairs iterator
  local tmpIndex = {}
  local index, _ = next(t)
  while index do
    tmpIndex[#tmpIndex+1] = index
    index, _ = next(t, index)
  end
  -- sort table indices
  table.sort(tmpIndex)
  local j = 1

  return function()
    -- get index value
    local i = tmpIndex[j]
    j = j + 1
    if i then
      return i, t[i]
    end
  end
end

The following lines of code show the usage example for iteration over a sparse array;

-- table below contains unsorted sparse array
local t = {
  [10] = 'a', [2] = 'b', [5] = 'c', [100] = 'd', [99] = 'e',
}
-- iterate over entries
for i, v in ipairs_sparse(t) do
  print(i,v)
end

How it works…

The Lua language uses iterator functions in the control structure called the generic for. The generic for calls the iterator function for each new iteration and stops when the iterator function returns nil. The ipairs_sparse function works in the following steps:

1. It builds a new index of keys from the table.
2. It sorts the index table.
3. It returns a closure where each call of the closure returns a consecutive index and a value from the sparse array.

Each call to ipairs_sparse prepares a new index table called index. The index consists of (integer, entry) pairs.