Модуль:Sort

Для документации этого модуля может быть создана страница Модуль:Sort/doc

-- Некоторые алгоритмы сортировки:

local Set = require "Set"

-- Данные:
local data = {

	-- Экспортируемые имена функций:
	API			= {['топологическая'] = topo, ['топо'] = topo, ['topological'] = topo, ['topo'] = topo},

	-- Ошибки:
    notDAG		= "Передан не направленный ациклический граф",
    notGraph	= "Передана не таблица, представляющая направленный граф",

    -- Аргументы:
    
    

}	-- local data = {...}

local function formatNumeralError (message, ...)
    if select('#', ... ) > 0 then
        message = string.format(message, ...)
    end
    return "<span class=\"error\">" .. message .. "</span>"
end

--[[
НАЗНАЧЕНИЕ:  Эта функция сортирует направленный ациклический граф топологически.
 
ПАРАМЕТРЫ:	edges	-- массив рёбер — массивов пар {из, в}.
					   Для изолированных вершин передавать второй параметр false.

ВЫВОД:		нет.
 
ВОЗВРАТ:	0, сообщение об ошибке - Ошибка из-за неверного аргумента
            топологически отсортированный массив вершин.
 
ПРИМЕЧАНИЕ:  Все проверки аргумента уже проведены.
--]]
local function implementTopo (edges)
	-- Алгоритм Роберта Э. Тарджана (поиск в глубину):
	local sorted				= {}		-- empty list that will contain the sorted nodes.
	
	-- Получение множества вершин графа:
	local unmarked = Set ()
	for _, edge in ipairs (edges) do
		unmarked.append (edge [1])
		if edge [2] then
			unmarked.append (edge [2])
		end
	end

	local marked_temporarily	= Set ()
	local marked_permanently	= Set ()
	
	local function visit (node, sorted)
	    if marked_temporarily:contains (node) then
	    	-- Уже были в этой вершине, значит передан циклический граф:
	    	return false
	    end
	    --if n is not marked (i.e. has not been visited yet) then
	    marked_temporarily:append (node)	-- mark node temporarily.
	    --for each node m with an edge from n to m do
	    	visit (m, sorted)
	    marked_permanently:append (node)	-- mark node permanently.
		marked_temporarily:remove (node)	-- unmark node temporarily.
		
	    -- prepend node to sorted.
	    return true
	end

	while unmarked.count () > 0 do
    	local n = unmarked.any ()
    	local ok = visit (n, sorted, marked_temporarily, marked_permanently, unmarked)
    	if not ok then
    		return data.notDAG, nil
    	end
	end
    
	return ok, sorted
end		-- local function implementTopo (edges)

-- Загрузка и первоначальная аргументов и вызов реализации:
local function topo (args)
	local edges = {}
	-- Загрузка и проверка аргументов:
	for _, arg in ipairs (args) do
		if 		type (arg) == 'table'
			and type (arg [1]) == 'string'
			and (type (arg [2]) == 'string' or arg [2] == false) then
			-- Normal edge:
			table.insert (edges, arg)
		else
			return null, data.notGraph
		end
	end

	local ok, sorted = implementTopo (edges)
	return ok, sorted	
end		-- local function declareCurrency (args)

-- Export function:
local m = {}

for alias, func in pairs (data.API) do
	m [alias] = function (frame)
		return func (frame.args)
    end
end

return m