-
-
Save RyanPattison/0f7307ee39a5238270a0 to your computer and use it in GitHub Desktop.
| 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
Hi. It ain't working in LuaJIT 5.1, showing 0 items for the given example.
The output of the example:
0 items
hello is 1
table: 0x405d1000 table: 0x405cf4c0
table: 0x405d0fd8 table: 0x405cf4e8
table: 0x405d1000 table: 0x405cf4c0
table: 0x405d0fd8 table: 0x405cf4e8
0 items
I've got adapted the code a bit, to make it working in 5.1. Let me know if you want me to contribute...
Hi. I just ran it with Lua 5.4, which seems to work. Thanks for the offer to contribute. I haven't used this in the last decade so it's not something I'll be maintaining or putting any more effort into.
What license is this under? Thanks in advance!