local export = {}

local m_links = require("Module:links")
local m_languages = require("Module:languages")


-- Custom functions for generating a sortkey that will achieve the desired sort
-- order.
-- name of module and name of exported function
local custom_sort_functions = {
	egy = { "egy-utilities", "make_sortkey" },
}


local function get_col_lengths(n_columns, n_items)
	local r = math.mod(n_items, n_columns)
	local col_lengths = {}
	
	for i = 1, n_columns do
		table.insert(col_lengths, (n_items - r) / n_columns)
		if (i <= r) then
			col_lengths[i] = col_lengths[i] + 1
		end
	end
	
	return col_lengths
end


local function set_columns(n_columns, items, line_start, lang)
	local col_lengths = get_col_lengths(n_columns, #items)
	local result = {}
	local count = 1
	
	for i = 1, n_columns do
		local col = {}
		for j = 1, col_lengths[i] do
			local item = items[count]
			
			if lang and not string.find(item, "<span") then
				item = m_links.full_link({lang = lang, term = item})
			end
			
			col[j] = '\n' .. line_start .. item
			count = count + 1
		end
		result[i] = table.concat(col)
	end
	
	return result
end


local function laborious_comp(item1, item2)
    local l1 = mw.ustring.len(item1)
    local l2 = mw.ustring.len(item2)
    for i=1,math.min(l1,l2) do
        local b1 = mw.ustring.codepoint(item1, i, i)
        local b2 = mw.ustring.codepoint(item2, i, i)
        if b1 ~= b2 then
            return b1 < b2
        end
    end
    return l1 < l2
end


local function do_alphabetize(content, lang)
    if lang then
		local cache = {}
		
		local custom_sort_function = custom_sort_functions[lang:getCode()]
		local makeSortKey =
			custom_sort_function and require("Module:" .. custom_sort_function[1])[custom_sort_function[2]]
			or function(text)
			return lang:makeSortKey(text)
		end
		local function prepare(element)
			local result = cache[element]
			
			if result then
				return result
			end
			
			result = m_links.remove_links(element)
			result = mw.ustring.gsub(result, "[%p ]", "")
			result = makeSortKey(lang:makeEntryName(result))
			cache[element] = result
			
			return result
		end
		
		local SMP = false
		-- Search for UTF-8-encoded characters with codepoints above U+FFFF.
		-- Their byte sequences are four bytes long and begin with the bytes 240
		-- to 244. The C locale used by our copy of Lua does not handle them
		-- correctly.
		for _, element in ipairs(content) do
			if element:find '[\240-\244]' then
				SMP = true
				--[[Special:WhatLinksHere/Template:tracking/columns/SMP]]
				require 'Module:debug'.track('columns/SMP')
				break
			end
		end
		
		local comp = SMP and laborious_comp
			or function (item1, item2)
				return prepare(item1) < prepare(item2)
			end
		
		table.sort(content, comp)
	else
		table.sort(content)
	end
end


local function get_col_header(bg, collapse, class, title, column_width)
	if collapse then
		return table.concat {'<div class="NavFrame">\n<div class="NavHead">',
                        title,
                        '</div>\n<div class="NavContent">\n{| style="width: 100%;" role="presentation" class="',
                        class,
                        '"\n|-\n| style="vertical-align: top; text-align: left; background-color: ',
                        bg,
                        ';  width: ',
                        column_width,
                        '%;" |'}
    else
    	return table.concat {'<div style="width: auto; margin: 0; overflow: auto;">\n{| role="presentation" style="width: 100%"\n|-\n| style="background: ',
                        bg,
                        '; vertical-align: top; width: ',
                        column_width,
                        '%" |'}
    end

end


function export.create_table(n_columns, content, alphabetize, bg, collapse, class, title, column_width, line_start, lang)
	if column_width then
		require("Module:debug").track("columns/column_width")
	end
	
	column_width = column_width or math.floor(80 / n_columns)
	
	if line_start then
		require("Module:debug").track("columns/line_start")
	end
	
	line_start = line_start or "* "
	
	local separator = '\n| style="width: 1%;" |\n| style="background: ' .. bg .. '; vertical-align: top; text-align: left; width: ' .. column_width .. '%;" |'
    local final = ''
	if collapse then
        final = '\n|}</div></div>'
    else
	    final = '\n|}</div>'
	end
	
    if alphabetize then
		do_alphabetize(content, lang)
	end
	
	local header = get_col_header(bg, collapse, class, title, column_width)
	local columns_t = set_columns(n_columns, content, line_start, lang)
	local columns = table.concat(columns_t, separator)
	
	return header .. columns .. final
end


function export.display(frame)
	local params = {
		["class"] = {default = "derivedterms"},
		["collapse"] = {type = "boolean"},
		["columns"] = {type = "number", default = 1},
		["lang"] = {},
		["sort"] = {type = "boolean"},
		["title"] = {default = ""},
	}
	
	local frame_args = require("Module:parameters").process(frame.args, params)
	
	params = {
		[1] = {list = true},
		
		["title"] = {},
		["lang"] = not frame_args["lang"] and {required = true, default = "und"} or nil,
		["collapse"] = {},
	}
	
	local args = require("Module:parameters").process(frame:getParent().args, params)
	
	local lang = frame_args["lang"] or args["lang"]
	lang = m_languages.getByCode(lang) or m_languages.err(lang, "lang")
	
	return export.create_table(frame_args["columns"], args[1], frame_args["sort"], "#F8F8FF", frame_args["collapse"], frame_args["class"], args["title"] or frame_args["title"], nil, nil, lang)
end


return export