capitalex / sparse_set.lua

local function push(self, thing) -- Attempt to recycle a previously freed ID local id = self.free_ids[#self.free_ids] table.remove(self.free_ids) if not id then -- Othewise generate a new ID id = self.next_id self.next_id = self.next_id + 1 end -- Assign the ID, the push the object into items -- and add its position to indices. thing.id = id table.insert(self.items, thing) self.indices[thing.id] = #self.items end local function pop(self, thing) assert(self.indices[thing.id], "ID is not bound in this set") assert(self.items[self.indices[thing.id]] == thing, "ID does not belong to this object") -- Add the ID of this object to the free stack table.insert(self.free_ids, thing.id) -- Consume the current index local index = self.indices[thing.id] self.indices[thing.id] = nil -- Swap and pop the last item in the set. self.items[index] = self.items[#self.items] table.remove(self.items) end local function each(self) return ipairs(self.items) end local function sparse_set() return { push = push, pop = pop, each = each, items = {}, indices = {}, free_ids = {}, next_id = 1 } end return sparse_set