Is it "smarter" from a design standpoint to abstract priorities or should I just go with a simple table.sort?

I created my own version of the SortedFunctionContainer class from the Lua Chat System (probably written better too) but it feels silly to use when there’s already table.sort. Ultimately I would know better what I need to use but here I’m at somewhat of a crossroads and need second opinions.

My main concern really is RebuildPriorities being called with every addition/removal of a function; that in itself already uses table.sort to organise non-empty priority maps for the iterator but I could skip finding existing priorities to sort if I just sort a raw table? I personally don’t even understand why it’s here in the Lua Chat System, but if a whole class was written then it must have some value.

tl;dr Would a simple table.sort be preferable over a whole abstract class for assigning priorities for function execution? I might just be overthinking this, as usual.

My rewritten SortedFunctionContainer class for reference’s sake:

--- Sort functions by priority
-- @author colbert2677, TheGamer101

local DEFAULT_PRIORITY = 10

local SortedFunctionContainer = {}

local Prototype = {}
Prototype.__index = Prototype

-- Most tables here use the hash portion so the length operator doesn't work here
local function isEmpty(tbl)
	return next(tbl) == nil
end

function Prototype:RebuildPriorities()
	table.clear(self.RegisteredPriorities)
	
	for priority, functions in pairs(self.FunctionMap) do
		if not isEmpty(functions) then
			table.insert(self.RegisteredPriorities, priority)
		end
	end
	
	table.sort(self.RegisteredPriorities, function(a, b)
		return a > b
	end)
end

function Prototype:HasFunction(funcId)
	return self.RegisteredFunctions[funcId] ~= nil
end

function Prototype:AddFunction(funcId, func, priority)
	priority = if typeof(priority) == "number" then priority else DEFAULT_PRIORITY
	
	if self.RegisteredFunctions[funcId] then
		error(funcId .. " belongs to a different function already")
	end
	
	self.RegisteredFunctions[funcId] = priority
	
	if self.FunctionMap[priority] == nil then
		self.FunctionMap[priority] = {}
	end
	
	self.FunctionMap[priority][funcId] = func
	self:RebuildPriorities()
end

function Prototype:RemoveFunction(funcId)
	local functionPriority = self.RegisteredFunctions[funcId]
	
	self.RegisteredFunctions[funcId] = nil
	self.FunctionMap[functionPriority][funcId] = nil
	
	self:RebuildPriorities()
end

--[=[
	local sortedFuncs = SortedFunctionContainer:GetIterator()
	
	for funcId, func, priority in sortedFuncs do
]=]
function Prototype:GetIterator()
	local priorityIndex = 1
	local funcId
	local func
	
	return function()
		while true do
			if priorityIndex > #self.RegisteredPriorities then
				return
			end
			
			local priority = self.RegisteredPriorities[priorityIndex]
			
			funcId, func = next(self.FunctionMap[priority], funcId)
			
			if funcId == nil then
				priorityIndex += 1
			else
				return funcId, func, priority
			end
		end
	end
end

function SortedFunctionContainer.new()
	return setmetatable({
		RegisteredFunctions = {},
		RegisteredPriorities = {},
		FunctionMap = {},
	}, Prototype)
end

-- Compatibility
function SortedFunctionContainer:NewSortedFunctionContainer()
	return SortedFunctionContainer.new()
end

return SortedFunctionContainer

EDIT: cc @TheGamer101

I believe the existence of this class was to actually create an iterator that worked through priorities until it passed the highest one, even with gaps.

Then again. I dont really see the point here if all you’re doing is sorting functions and dont need the iterator.

This is from what I can gather looking at the code, I’m on a phone after all so cant really give it a deeper look

Where exactly would said gap occur, in the collected priorities table?

I’ve been thinking of a simpler pattern like:

local foobar = {
	item_a = {priority = 5, func = something},
	item_b = {priority = 5, func = somethingElse}
}

table.sort(foobar, function(a, b)
    return a.priority > b.priority
end)

I guess after reading it over again it might be easier to add and remove functions from a list given an id because they’re just keys but it’s not like I’m creating a resource here so it’s not particularly important to have any methods to unregister added components.

Coming to revisit this thread since I’ve crossed paths with my SortedFunctionContainer module while working on a new framework for a project. After some thinking and delving into the code, I think I can more sufficiently grasp why this exists and why it’s better than just a raw table.sort.

A raw table.sort is self explanatory: when given an array, sort the items of the array according to the given comparative method. No matter how many elements you have it will go through your entire array, compare and rearrange elements to their more appropriate position.

SortedFunctionContainer is useful in cases where you need to make function priorities because it doesn’t do a complete traversal of all elements and instead “picks and chooses battles wisely”. The key is held within the three tables created in the constructor:

  • RegisteredFunctions is a dictionary where the key is the name of a registered function given as the first parameter of AddFunction and the value is the priority of that function given as either the third parameter of AddFunction or a specified default. The intent of RegisteredFunctions is two-fold: preventing any other functions from being registered with the same id/name and providing RemoveFunction a way to find out a function’s priority to be cleaned from the FunctionMap.

  • RegisteredPriorities is a simple array of numbers representing all “existing” priorities being tracked. An “existing” priority refers to a priority number that is associated with a non-zero number of functions in FunctionMap. RegisteredPriorities is rebuilt every time a new function is added or removed to fit the aforementioned criteria. This is where the sort power comes from - as each priority number is guaranteed to only exist once due to FunctionMap’s dictionary nature, the sorting is mainly against simple collected numbers.

  • FunctionMap is the meat of SortedFunctionContainer. The first layer contains a key-value pair where the key is a number representing a priority value and the value is a table. The value table introduces us to our second layer, another dictionary where the key is the function id submitted to AddFunction and the value is the actual function to be called as designated by the second parameter of AddFunction. This never gets sorted nor does it need to. The intent of FunctionMap is essentially to store our functions with names and then associate them as a collection with a number that represents the priority at which the function should be ran at.

Due to the non-standard structuring of the container and its member tables we also need to create a custom iterator to go through them. While it would be acceptable to just go through the RegisteredPriorities and use the index of the current loop to perform an iteration through the respective FunctionMap key, it’s simply not clean. That’s where GetIterator plays its part.

We create three values when GetIterator is called to be used with the for keyword: a priority index, a function id and a function. The priority index is used, as implied by the name, as a numerically contiguous index for RegisteredPriorities which the value at that index can be used as a key to index FunctionMap. The function id is used to help the next keyword traverse through the table in FunctionMap assigned to the current priority number gotten from the previous index. The while loop is there to repeat the search process if the table of functions for the current priority returns a nil (assumed finished traversal) but not before the priority index is incremented.

For anyone that’s using this module or is interested in the technicals behind this, I hope my explanation will help in that. I’m not a great articulator so the explanation could be confusing in itself but I’ve explained it the best way I know how.

tl;dr Essentially, SortedFunctionContainer makes assigning and sorting easier when you want to grant functions an ordering based on priority values.

2 Likes