Sparse multidimensional tables in Lua

sparse.lua

local Sparse = {}

local function new(dimension)
   local sparse = {}
   sparse._dimension = dimension
   return setmetatable(sparse, Sparse)
end

function Sparse.__index(sparse, key)
   if sparse._dimension == 1 then
      -- clean up and return nil
      local back, idx = rawget(sparse, "_back"), rawget(sparse, "_idx")
      rawset(sparse, "_back", nil)
      rawset(sparse, "_idx", nil)
      if back == nil then
         return nil
      end
      repeat
         rawset(back, idx, nil)
         back, idx = rawget(back, "_back"), rawget(back, "_idx")
      until back == nil
      return nil
   else
      -- provisionally create a Sparse table
      local new_sparse = new(sparse._dimension - 1)
      rawset(new_sparse,"_back", sparse)
      rawset(new_sparse, "_idx", key)
      rawset(sparse, key, new_sparse)
      return new_sparse
   end
end

function Sparse.__newindex(sparse, key, value)
   if sparse._dimension > 1 then
      -- as a refinement, this could be allowed for sparse
      -- tables of the correct dimension
      -- an interesting exercise!
      error("attempt to assign value to inner value of "
            .. sparse._dimension .. "-dimensional sparse table")
   end
   -- reify the intermediate tables
   local back, idx = rawget(sparse, "_back"), rawget(sparse, "_idx")
   rawset(sparse, "_back", nil)
   rawset(sparse, "_idx", nil)
   if back == nil then
      rawset(sparse, key, value)
      return
   end
   repeat
      local back_back, back_idx = rawget(back,"_back"), rawget(back, "_idx")
      rawset(back, "_back", nil)
      rawset(back, "_idx", nil)
      back, idx = back_back, back_idx
   until back == nil
   if value == nil then return nil end
   rawset(sparse, key, value)
end

return new