Lua is memory efficient for huge but sparse multi-dimensional arrays,
since nil values aren't stored in the tables.
However, reading and writing to such sparse multi-dimensional arrays can
be quite a hassle. If I want to access the value of
t[a][b][c][d][e], I first have to check whether t[a] is a table, t[a][b]
is a table, t[a][b][c] is a table etc, otherwise Lua throws an error
"Attempt to index a nil value".
For example, to read the value at t[a][b][c][d][e], I cannot simply use:
v = t[a][b][c][d][e]
Instead, the code must look something like:
v = t and t[a] and t[a][b] and t[a][b][c] and t[a][b][c][d] and
t[a][b][c][d][e]
Or, to write a value to t[a][b][c][d][e], I cannot simply use:
t[a][b][c][d][e] = v
Instead, the code must look something like:
if not t then t = {[a] = {[b] = {[c] = {[d] = {[e] = v}}}}}
elseif not t[a] then t[a] = {[b] = {[c] = {[d] = {[e] = v}}}}
elseif not t[a][b] then t[a][b] = {[c] = {[d] = {[e] = v}}}
elseif not t[a][b][c] then t[a][b][c] = {[d] = {[e] = v}}
elseif not t[a][b][c][d] then t[a][b][c][d] = {[e] = v}
else t[a][b][c][d][e] = v
end
I like these sorts of brain-teasers, so I went ahead and implemented something which does most of what you want.
...followed by code that was less than ready for prime time. You can never proofread enough it seems.
Pride compels me to post one more time, though experience tells me there must be at least one glaring error remaining. Further updates I will make to the gist alone.
local Sparse = {}
local function new(dimension)
local sparse = {}
sparse._dimension = dimension
sparse._count = 1
return setmetatable(sparse, Sparse)
end
function Sparse.__index(sparse, key)
if sparse._count == sparse._dimension 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 - sparse._count)
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._count < sparse._dimension then
-- as a refinement, this could be allowed for sparse
-- tables of the correct dimension
-- an interesting exercise!
error("attempt to assign value to dimension " .. sparse._count
.. " 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
