Модуль:Array

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

--[[
	Модуль для добавления к таблицам Lua некоторых функций для работы с массивами.
	Экспортируется: класс Array,
                	функции table_merge, table_append, cartesian, cartesian2, cartesian_iterator.
	Зависимость: Модуль:Class.
--]]
local Class = (require 'Модуль:Class' or require 'Class.lua').create

-- Dependency:
local clone 	= (mw or require 'mw.lua').clone
local ustring	= (mw or require 'mw.ustring.lua').ustring

-- Класс продвинутых таблиц:
local Array = Class ()
-- Конструктор:
function Array:_init (...)
	local args = {...}
	local source
	if #args == 1 and type (args [1]) == 'table' then 
		source = args [1]
	else
		source = args
	end
	for key, val in pairs (source) do
		self [key] = val
	end
end

-- Клонирование:
function Array:clone ()
	return clone (self)
end

-- Итератор:
local coroutine = coroutine
function Array:_call ()
	return pairs (self)	-- or just ipairs?
end		-- function Array:_call ()

-- индексы:
function Array:keys ()
	return table_keys (self)
end	-- function Array:keys ()

-- merge с возвратом клона:
function Array:merge (...)
	local args = {...}
	local merged = self:clone ()
	for i, tbl in ipairs (args) do
		for key, value in pairs (tbl) do
			merged [key] = value
		end
	end
	return merged
end		

-- absorb (merge к себе):
function Array:absorb (...)
	local args = {...}
	for i, tbl in ipairs (args) do
		for key, value in pairs (tbl) do
			self [key] = value
		end
	end
	return true
end	

-- absorb (merge к себе) со слиянием полей.
--    callback -- функция слияния полей, принимающая три аргумента:
--        1) имя поля,
--        2) накопленное значение поля
--           (nil допустимо и должно правильно обрабатываться),
--        3) прибавляемое значение поля:
function Array:absorb_callback (callback, ...)
	local args = {...}
	for i, tbl in ipairs (args) do
		for key, value in pairs (tbl) do
			self [key] = callback (key, self [key], value)
		end
	end
	return true
end	

-- append с возвратом клона:
function Array:append (...)
	local args = {...}
	local res = self:clone ()
	for _, tbl in ipairs (args) do
		-- Оптимизированное for __, value in ipairs (tbl) do:
		-- Оптимизация многократного вызова #res:
		local tail = #res
		for i = 1, #tbl do
			res [tail + i] = tbl [i]
		end
	end
	return res
end

-- append к себе:
function Array:append2self (...)
	local args = {...}
	for _, tbl in ipairs (args) do
		-- Оптимизированное for __, value in ipairs (tbl) do:
		-- Оптимизация многократного вызова #self:
		local tail = #self
		for i = 1, #tbl do
			self [tail + i] = tbl [i]
		end
	end
end

-- append к другому Array или таблице:
function Array:append2 (tbl)
	tail = #tbl
	-- Оптимизированное for key, value in ipairs (self) do:
	for i = 1, #self do
		tail = tail + 1
		tbl [tail] = self [i]
	end
end

-- Создание полей из имеющихся полей подстановкой их в шаблон.
--     Параметр: ассоциативный массив {['полеi'] = 'шаблонi'}:
function Array:newfields (new)
	-- Служебная строковая функция:
	-- Подставить в шаблон значения параметров.
	-- Параметры: 1) шаблон, 2) массив {['образец1'] = 'замена1',... , ['образецn'] = 'заменаn'}:
	local function fill_in (str, params)
		local ret = str or ''
		for param, value in pairs (params) do
			ret =  ustring.gsub (ret, tostring (param), value)
		end
		return ret
	end
	
	for new_field, template in pairs (new) do
		if template and template ~= '' then
			-- нормальная подстановка:
			self [new_field] = fill_in (template, self)
		else
			-- пустой шаблон — инструкция удалить поле:
			self [new_field] = nil
		end
	end
	return self
end

-- Возвращает массив, в котором ключи поменялись местами со значениями:
function Array:flip ()
	local flipped = Array ()
	for key, val in pairs (self) do
		flipped [val] = key
	end
	return flipped
end
	
-- Возвращает массив с ключами из self и значениями из аргумента:
function Array:combine_with (values)
	local combined = Array ()
	-- Оптимизированное for key, value in ipairs (self) do:
	for i = 1, math.min (#self, #values) do
		combined [self [i]] = values [i]
	end
	return combined
end

-- Возвращает итератор по всем перестановкам:
-- Источник: https://www.lua.org/pil/9.3.html
local coroutine = coroutine
function Array:permutations ()
	local length = #self
	return coroutine.wrap (function ()
		permgen (self, length)
	end)
end	--	function Array:permutations ()

local function permgen (arr, number)
	if number == 0 then
		coroutine.yield (arr)
	else
		for i = 1, number do
			-- i-ый элемент в конец:
			arr [number], a [i] = a [i], a [number]
			-- рекурсивно создать перестановки всех остальных элементов:
			permgen (arr, number - 1)
			-- восстановить i-ый элемент:
			arr [number], arr [i] = arr [i], arr [number]
		end
	end	-- if number == 0
end		-- local function permgen (arr, number)

-- map:
function Array:map (func)
	local mapped = Array ()
	for key, value in ipairs (self) do
		mapped [key] = func (value)
	end
	return mapped
end		-- function Array:map (func)

-- reduce:
function Array:reduce (func, initial)
	local reduced = initial
	for key, value in ipairs (self) do
		reduced = func (reduced, value, key)
	end
	return reduced
end		-- function Array:reduce (func, initial)

-- filter:
function Array:filter (func)
	local filtered = Array ()
	for key, value in ipairs (self) do
		if func (value, key) then
			filtered [#filtered + 1] = value
		end
	end
	return filtered
end		-- function Array:filter (func)

-- find:
function Array:find (func)
	for key, value in ipairs (self) do
		if func (value, key) then
			return value
		end
	end
end		-- function Array:find (func)

local m = {}
m.Array = Array

-- Функции для работы с таблицами:

-- Ключи:
local function table_keys (tbl)
	local keys = {}
	for key, _ in pairs (tbl) do
		keys [#keys + 1] = key
	end
	return keys
end	-- local function table_keys (tbl)

m.keys = function (tbl)
	return table_keys (tbl)
end	-- m.keys = function (tbl)

-- Слияние нескольких таблиц (при совпадении ключей, переданные позже затирают переданне раньше):
-- Попробовать ещё table:merge, чтобы уменьшить число копирований?
m.table_merge = function (...)
	local merged = {}
	for i, tbl in ipairs {...} do
		for key, value in pairs (type (tbl) == 'table' and tbl or {tbl}) do
			merged [key] = value
		end
	end
	return merged
end	-- m.table_merge = function (...)

m.table_merge_to_first = function (first, ...)
	for i, tbl in ipairs {...} do
		for key, value in pairs (type (tbl) == 'table' and tbl or {tbl}) do
			first [key] = value
		end
	end
	return first
end	-- m.table_merge_to_first = function (first, ...)

function Array:cartesian_append (array_of_vectors)
	local ret = Array ()
	if #self == 0 then
		return Array_of_vectors
	end
	for _, vector1 in ipairs (self) do
		for __, vector2 in ipairs (array_of_vectors) do
			ret [#ret + 1] = m.table_merge (vector1, vector2)
		end
	end
	return ret
end		-- function Array:cartesian_append (array_of_vectors)
 
-- Слияние нескольких нумерованных таблиц (переданные позже дописываются в конец):
-- Попробовать ещё table:append, чтобы уменьшить число копирований?
m.table_append = function (...)
	local res = {}
	for _, tbl in ipairs {...} do
		if tbl then
			local wrapped = type (tbl) == 'table' and tbl or {tbl}
			for key, val in pairs (wrapped) do
				res [tonumber (key) and #res + 1 or key] = val
			end
		end	-- if tbl
	end
	return res
end		

-- Декартово произведение элементов таблицы.
-- Пустые множества не обнуляют произведение:
m.cartesian  = function (vector_of_sets)
	local combinations = {}
	local new_combinations
	for name, values in pairs (vector_of_sets) do
		new_combinations = {}		
		if #combinations == 0 then
			for j, value in ipairs (values) do
				new_combinations [j] = {[name] = value}
			end
		else
			for i, combination in ipairs (combinations) do
				for j, value in ipairs (values) do
					local new_index = #new_combinations + 1
					new_combinations [new_index] = clone (combination)
					new_combinations [new_index] [name] = value
				end
			end
		end	-- if #combinations == 0
		combinations = new_combinations
	end	-- for name, values in pairs (vector_of_tables)
	return combinations
end		-- m.cartesian  = function (vector_of_sets)

local function wrap (item)
	return type (item) == 'table' and item or {item}
end		-- local function wrap (item)

local function implement_cartesian_iterator (table_of_tables)
	return coroutine.wrap (function ()		
		local last = wrap (table.remove (table_of_tables))
		if #table_of_tables == 0 then
			-- The recursion is over:
			for _, item in ipairs (last) do
				coroutine.yield (item)
			end
		else
			-- We need to go deeper:
			for item_head in implement_cartesian_iterator (table_of_tables) do
				for _, item_tail in ipairs (last) do
					local item = wrap (clone (item_head))
					table.insert (item, item_tail)
					coroutine.yield (item)
				end
			end
		end	-- if #table_of_tables == 0
	end)	-- return coroutine.wrap (function () ... end
end		-- local function implement_cartesian_iterator (table_of_tables)
function m.cartesian_iterator (...)
	return implement_cartesian_iterator {...}
end		-- local function cartesian_iterator (...)

function m.cartesian2 (...)
	local product = {}
	for item in m.cartesian_iterator (...) do
		product [#product + 1] = item
	end
	return product
end		-- function m.cartesian2 (...)

-- Экспорт:
return m