Looking for a Set data structure

Place to get help with not working mods / modding interface.
Post Reply
mrvn
Smart Inserter
Smart Inserter
Posts: 4050
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Looking for a Set data structure

Post by 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
Factorio Staff
Factorio Staff
Posts: 2503
Joined: Sat Aug 13, 2016 9:20 am
Contact:

Re: Looking for a Set data structure

Post by 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)?
I'm an admin over at https://wiki.factorio.com. Feel free to contact me if there's anything wrong (or right) with it.

mrvn
Smart Inserter
Smart Inserter
Posts: 4050
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Looking for a Set data structure

Post by mrvn »

Bilka wrote:
Thu Apr 04, 2019 11:04 am
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
Long Handed Inserter
Long Handed Inserter
Posts: 91
Joined: Thu May 18, 2017 2:22 pm
Contact:

Re: Looking for a Set data structure

Post by 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
Filter Inserter
Filter Inserter
Posts: 344
Joined: Fri May 09, 2014 2:52 pm
Contact:

Re: Looking for a Set data structure

Post by 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.

User avatar
bobingabout
Smart Inserter
Smart Inserter
Posts: 7198
Joined: Fri May 09, 2014 1:01 pm
Contact:

Re: Looking for a Set data structure

Post by bobingabout »

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

Add, Remove, Replace (changes 1 item to another but keeps quantity.)
Creator of Bob's mods. Expanding your gameplay since version 0.9.8.
I also have a Patreon.

mrvn
Smart Inserter
Smart Inserter
Posts: 4050
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Looking for a Set data structure

Post by mrvn »

eduran wrote:
Thu Apr 04, 2019 6:36 pm

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
Filter Inserter
Filter Inserter
Posts: 344
Joined: Fri May 09, 2014 2:52 pm
Contact:

Re: Looking for a Set data structure

Post by 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
Smart Inserter
Smart Inserter
Posts: 4050
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Looking for a Set data structure

Post by mrvn »

eduran wrote:
Sat Apr 06, 2019 11:52 am

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
Filter Inserter
Filter Inserter
Posts: 344
Joined: Fri May 09, 2014 2:52 pm
Contact:

Re: Looking for a Set data structure

Post by eduran »

mrvn wrote:
Mon Apr 08, 2019 10:06 am
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
Smart Inserter
Smart Inserter
Posts: 4050
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Looking for a Set data structure

Post by mrvn »

eduran wrote:
Mon Apr 08, 2019 10:17 am
mrvn wrote:
Mon Apr 08, 2019 10:06 am
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
Filter Inserter
Filter Inserter
Posts: 344
Joined: Fri May 09, 2014 2:52 pm
Contact:

Re: Looking for a Set data structure

Post by 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.

Post Reply

Return to “Modding help”

Who is online

Users browsing this forum: No registered users