Looking for a Set data structure

[mrvn]

As the topic says I'm looking for a set data structure.

I need the following functions:

function insert(set, item) -- add item to set
function remove(set, item) -- remove item from set
function contains(set, item) -- returns true if item in set
function count(set) -- returns number of items in set

A set should not have any duplicates so adding something twice is a NOP. My current code uses an array. But I have to search the whole array for insert, remove and contains which isn't ideal. I'm thinking of switching to a table using set[x] = x for insert. But then I have to keep track of the count of items myself.

Is there a mod out there already that provides a set data structure like I need?

PS: I also need something to iterate over the set.

[Bilka]

But then I have to keep track of the count of items myself.

Why? Can't you just use the size of the table, meaning that you can use table_size(your_set)?

[mrvn]

But then I have to keep track of the count of items myself.

Why? Can't you just use the size of the table, meaning that you can use table_size(your_set)?

Nice. That's one problem taken care of. I only new about # which doesn't give the size for a table.

[danielbrauer]

These guys recommend a table of bools indexed by whatever you want in your set: https://www.lua.org/pil/11.5.html

[eduran]

Code: Select all

local set = {}
-- insert
set[item] = true

-- remove
set[item] = nil

--contains
local contains = set[item] -- if returning nil instead of false is OK for you
local contains = set[item] or false -- if you need false instead of nil

--iterating
for item in pairs(set) do
  --do something with item
end  

Lua tables do pretty much everything you need. If you want a performant count(set) function, increment a counter when inserting and decrement when removing.

[bobingabout]

Bob's Library mod already includes some of those functions.

Add, Remove, Replace (changes 1 item to another but keeps quantity.)

[mrvn]

Code: Select all

local set = {}
-- insert
set[item] = true

-- remove
set[item] = nil

--contains
local contains = set[item] -- if returning nil instead of false is OK for you
local contains = set[item] or false -- if you need false instead of nil

--iterating
for item in pairs(set) do
  --do something with item
end  

Lua tables do pretty much everything you need. If you want a performant count(set) function, increment a counter when inserting and decrement when removing.

That's what I came up with too. When not having to manually count the items in the table (due to table_size) all the methods become rather trivial.

There is one more method I needed:

-- pick an item from the set if any
next(set)

[eduran]

Code: Select all

local next_item = next(set, current_item)

Use current_item = nil (or just next(set)) to get the first item. If current_item == last_item, next will return nil. One caveat: you should not assign new items to your set while traversing it.

[mrvn]

Code: Select all

local next_item = next(set, current_item)

Use current_item = nil (or just next(set)) to get the first item. If current_item == last_item, next will return nil. One caveat: you should not assign new items to your set while traversing it.

Kind of obvious.

I was surprised that pairs and ipairs does not have this problem. I assumed they would be true iterators but they seem to create a copy first so changes in the table don't affect them.

[eduran]

I was surprised that pairs and ipairs does not have this problem. I assumed they would be true iterators but they seem to create a copy first so changes in the table don't affect them.

They are affected. It is OK to assign new values to existing keys. That includes assigning nil, so key removal is also fine. Adding new keys while iterating with pairs/ipairs/next will lead to unpredictable behavior and possible an error.

[mrvn]

I was surprised that pairs and ipairs does not have this problem. I assumed they would be true iterators but they seem to create a copy first so changes in the table don't affect them.

They are affected. It is OK to assign new values to existing keys. That includes assigning nil, so key removal is also fine. Adding new keys while iterating with pairs/ipairs/next will lead to unpredictable behavior and possible an error.

Should I deduce from that that a table will resize (and re-hash the entries) as it grows but will never shrink? I've only deleted keys in loops so far.

[eduran]

Yes, that it pretty much it. Lua rehashes tables only when inserting a key and the hash array is full. Removing keys does not trigger a rehash. There are ways to force Lua to shrink tables, but by default it does not.