Last active
January 29, 2023 16:01
-
-
Save RyanPattison/0f7307ee39a5238270a0 to your computer and use it in GitHub Desktop.
Ordered table for Lua. A table that keeps track of the order that keys are added and makes pairs iterate in order of insertion. Also, it maintains/reports the correct number of items in the table with the `#` operator.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
local ordered_table = {} | |
--[[ | |
This implementation of ordered table does not hold performance above functionality. | |
It invokes a metamethod `__newindex` for every access, and | |
while this is not ideal performance wise, the resulting table behaves very closely to | |
a standard Lua table, with the quirk that the keys are ordered by when they are first seen | |
(unless deleted and then reinserted.) | |
--]] | |
-- private unique keys | |
local _values = {} | |
local _keys = {} | |
function ordered_table.insert(t, k, v) | |
if v == nil then | |
ordered_table.remove(t, k) | |
else -- update/store value | |
if t[_values][k] == nil then -- new key | |
t[_keys][#t[_keys] + 1] = k | |
end | |
t[_values][k] = v | |
end | |
end | |
local function find(t, v) | |
for i,val in ipairs(t) do | |
if v == val then | |
return i | |
end | |
end | |
end | |
function ordered_table.remove(t, k) | |
local tv = t[_values] | |
local v = tv[k] | |
if v ~= nil then | |
local tk = t[_keys] | |
table.remove(tk, assert(find(tk, k))) | |
tv[k] = nil | |
end | |
return v | |
end | |
function ordered_table.pairs(t) | |
local i = 0 | |
return function() | |
i = i + 1 | |
local key = t[_keys][i] | |
if key ~= nil then | |
return key, t[_values][key] | |
end | |
end | |
end | |
-- set metamethods for ordered_table "class" | |
ordered_table.__newindex=ordered_table.insert -- called for updates too since we store the value in `_values` instead. | |
ordered_table.__len=function(t) return #t[_keys] end | |
ordered_table.__pairs=ordered_table.pairs | |
ordered_table.__index=function(t, k) return t[_values][k] end -- function so we can share between tables | |
function ordered_table:new(init) | |
init = init or {} | |
local key_table = {} | |
local value_table = {} | |
local t = {[_keys]=key_table, [_values]=value_table} | |
local n = #init | |
if n % 2 ~= 0 then | |
error("key: "..tostring(init[#init]).." is missing value", 2) | |
end | |
for i=1,n/2 do | |
local k = init[i * 2 - 1] | |
local v = init[i * 2] | |
if value_table[k] ~= nil then | |
error("duplicated key:"..tostring(k), 2) | |
end | |
key_table[#key_table + 1] = k | |
value_table[k] = v | |
end | |
return setmetatable(t, self) | |
end | |
return setmetatable(ordered_table, {__call=ordered_table.new}) | |
--[[ Example Usage: | |
ordered_table = require"ordered_table" | |
local t = ordered_table{ | |
"hello", 1, -- key, value pairs | |
2, 2, | |
50, 3, | |
"bye", 4, | |
200, 5, | |
"_values", 20, | |
"_keys", 4, | |
} | |
print(#t, "items") | |
print("hello is", t.hello) | |
print() | |
for k, v in pairs(t) do print(k, v) end | |
print() | |
t.bye = nil -- delete it | |
t.hello = 0 -- updates | |
t.bye = 4 -- bring it back! | |
for k, v in pairs(t) do print(k, v) end | |
print(#t, "items") | |
--]] |
It's been a very long time since I've written in Lua and I don't think this was used anywhere, so use it at your risk and support basically. The MIT one without attrition works for me though: https://opensource.org/licenses/MIT-0
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
What license is this under? Thanks in advance!