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