if not modules then modules = { } end modules ['sort-ini'] = {
    version   = 1.001,
    comment   = "companion to sort-ini.mkiv",
    author    = "Hans Hagen, PRAGMA-ADE, Hasselt NL",
    copyright = "PRAGMA ADE / ConTeXt Development Team",
    license   = "see context related readme files"
}

-- It took a while to get there, but with Fleetwood Mac's "Don't Stop" playing in
-- the background we sort of got it done.
--
-- The code here evolved from the rather old mkii approach. There we concatinate the
-- key and (raw) entry into a new string. Numbers and special characters get some
-- treatment so that they sort ok. In addition some normalization (lowercasing,
-- accent stripping) takes place and again data is appended ror prepended.
-- Eventually these strings are sorted using a regular string sorter. The relative
-- order of character is dealt with by weighting them. It took a while to figure
-- this all out but eventually it worked ok for most languages, given that the right
-- datatables were provided.
--
-- Here we do follow a similar approach but this time we don't append the
-- manipulated keys and entries but create tables for each of them with entries
-- being tables themselves having different properties. In these tables characters
-- are represented by numbers and sorting takes place using these numbers. Strings
-- are simplified using lowercasing as well as shape codes. Numbers are filtered and
-- after getting an offset they end up at the right end of the spectrum (more clever
-- parser will be added some day). There are definitely more solutions to the
-- problem and it is a nice puzzle to solve.
--
-- In the future more methods can be added, as there is practically no limit to what
-- goes into the tables. For that we will provide hooks.
--
-- Todo: decomposition with specific order of accents, this is relatively easy to
-- do.
--
-- Todo: investigate what standards and conventions there are and see how they map
-- onto this mechanism. I've learned that users can come up with any demand so
-- nothing here is frozen.
--
-- Todo: I ran into the Unicode Collation document and noticed that there are some
-- similarities (like the weights) but using that method would still demand extra
-- code for language specifics. One option is to use the allkeys.txt file for the uc
-- vectors but then we would also use the collapsed key (sq, code is now commented).
-- In fact, we could just hook those into the replacer code that we reun beforehand.
--
-- In the future index entries will become more clever, i.e. they will have language
-- etc properties that then can be used.

local gsub, find, rep, sub, sort, concat, tohash, format = string.gsub, string.find, string.rep, string.sub, table.sort, table.concat, table.tohash, string.format
local utfbyte, utfchar, utfcharacters = utf.byte, utf.char, utf.characters
local next, type, tonumber, rawget, rawset = next, type, tonumber, rawget, rawset
local P, Cs, R, S, lpegmatch, lpegpatterns = lpeg.P, lpeg.Cs, lpeg.R, lpeg.S, lpeg.match, lpeg.patterns

local allocate          = utilities.storage.allocate
local setmetatableindex = table.setmetatableindex

local trace_tests       = false  trackers.register("sorters.tests",        function(v) trace_tests        = v end)
local trace_methods     = false  trackers.register("sorters.methods",      function(v) trace_methods      = v end)
local trace_orders      = false  trackers.register("sorters.orders",       function(v) trace_orders       = v end)
local trace_replacements= false  trackers.register("sorters.replacements", function(v) trace_replacements = v end)

local report_sorters    = logs.reporter("languages","sorters")

local comparers         = { }
local splitters         = { }
local definitions       = allocate()
local tracers           = allocate()
local ignoredoffset     = 0x10000 -- frozen
local replacementoffset = 0x10000 -- frozen
local digitsoffset      = 0x20000 -- frozen
local digitsmaximum     = 0xFFFFF -- frozen

local lccodes           = characters.lccodes
local uccodes           = characters.uccodes
local lcchars           = characters.lcchars
local ucchars           = characters.ucchars
local shchars           = characters.shchars
local fscodes           = characters.fscodes
local fschars           = characters.fschars

local decomposed        = characters.decomposed

local variables         = interfaces.variables

local v_numbers         = variables.numbers
local v_default         = variables.default
local v_before          = variables.before
local v_after           = variables.after
local v_first           = variables.first
local v_last            = variables.last

local validmethods      = tohash {
    "ch", -- raw character (for tracing)
    "mm", -- minus mapping
    "zm", -- zero  mapping
    "pm", -- plus  mapping
    "mc", -- lower case - 1
    "zc", -- lower case
    "pc", -- lower case + 1
    "uc", -- unicode
}

local predefinedmethods = {
    [v_default] = "zc,pc,zm,pm,uc",
    [v_before]  = "mm,mc,uc",
    [v_after]   = "pm,mc,uc",
    [v_first]   = "pc,mm,uc",
    [v_last]    = "mc,mm,uc",
}

sorters = {
    comparers    = comparers,
    splitters    = splitters,
    definitions  = definitions,
    tracers      = tracers,
    constants    = {
        ignoredoffset     = ignoredoffset,
        replacementoffset = replacementoffset,
        digitsoffset      = digitsoffset,
        digitsmaximum     = digitsmaximum,
        defaultlanguage   = v_default,
        defaultmethod     = v_default,
        defaultdigits     = v_numbers,
        validmethods      = validmethods,
    }
}

local sorters   = sorters
local constants = sorters.constants

local data, language, method, digits
local replacements, m_mappings, z_mappings, p_mappings, entries, orders, lower, upper, method, sequence, usedinsequence
local thefirstofsplit

local mte = { -- todo: assign to t
    __index = function(t,k)
        if k and k ~= "" and utfbyte(k) < digitsoffset then -- k check really needed (see s-lan-02)
            local el
            if k then
                local l = lower[k] or lcchars[k]
                el = rawget(t,l)
            end
            if not el then
                local l = shchars[k]
                if l and l ~= k then
                    if #l > 1 then
                        l = sub(l,1,1) -- todo
                    end
                    el = rawget(t,l)
                    if not el then
                        l = lower[k] or lcchars[l]
                        if l then
                            el = rawget(t,l)
                        end
                    end
                end
                el = el or k
            end
        --  rawset(t,k,el)
            return el
        else
        --  rawset(t,k,k)
        end
    end
}

local noorder = false
local nothing = { 0 }

local function preparetables(data)
    local orders, lower, m_mappings, z_mappings, p_mappings = data.orders, data.lower, { }, { }, { }
    for i=1,#orders do
        local oi = orders[i]
        local n = { 2 * i }
        m_mappings[oi], z_mappings[oi], p_mappings[oi] = n, n, n
    end
    local mtm = {
        __index = function(t,k)
            local n, nn
            if k then
                if trace_orders then
                    report_sorters("simplifing character %C",k)
                end
                local l = lower[k] or lcchars[k]
                if l then
                    if trace_orders then
                        report_sorters(" 1 lower: %C",l)
                    end
                    local ml = rawget(t,l)
                    if ml then
                        n = { }
                        nn = 0
                        for i=1,#ml do
                            nn = nn + 1
                            n[nn] = ml[i] + (t.__delta or 0)
                        end
                        if trace_orders then
                            report_sorters(" 2 order: % t",n)
                        end
                    end
                end
                if not n then
                    local s = shchars[k] -- maybe all components?
                    if s and s ~= k then
                        if trace_orders then
                            report_sorters(" 3 shape: %C",s)
                        end
                        n = { }
                        nn = 0
                        for l in utfcharacters(s) do
                            local ml = rawget(t,l)
                            if ml then
                                if trace_orders then
                                    report_sorters(" 4 keep: %C",l)
                                end
                                if ml then
                                    for i=1,#ml do
                                        nn = nn + 1
                                        n[nn] = ml[i]
                                    end
                                end
                            else
                                l = lower[l] or lcchars[l]
                                if l then
                                    if trace_orders then
                                        report_sorters(" 5 lower: %C",l)
                                    end
                                    local ml = rawget(t,l)
                                    if ml then
                                        for i=1,#ml do
                                            nn = nn + 1
                                            n[nn] = ml[i] + (t.__delta or 0)
                                        end
                                    end
                                end
                            end
                        end
                    else
                        -- this is a kind of last resort branch that we might want to revise
                        -- one day
                        --
                        -- local b = utfbyte(k)
                        -- n = decomposed[b] or { b }
                        -- if trace_tests then
                        --     report_sorters(" 6 split: %s",utf.tostring(b)) -- todo
                        -- end
                        --
                        -- we need to move way above valid order (new per 2014-10-16) .. maybe we
                        -- need to move it even more up to get numbers right (not all have orders)
                        --
                        if k == "\000" then
                            n = nothing -- shared
                            if trace_orders then
                                report_sorters(" 6 split: space") -- todo
                            end
                        else
                            local b = 2 * #orders + utfbyte(k)
                            n = decomposed[b] or { b } -- could be shared tables
                            if trace_orders then
                                report_sorters(" 6 split: %s",utf.tostring(b)) -- todo
                            end
                        end
                    end
                    if n then
                        if trace_orders then
                            report_sorters(" 7 order: % t",n)
                        end
                    else
                        n = noorder
                        if trace_orders then
                            report_sorters(" 8 order: 0")
                        end
                    end
                end
            else
                n = noorder
                if trace_orders then
                    report_sorters(" 9 order: 0")
                end
            end
            rawset(t,k,n)
            return n
        end
    }
    data.m_mappings = m_mappings
    data.z_mappings = z_mappings
    data.p_mappings = p_mappings
    m_mappings.__delta = -1
    z_mappings.__delta =  0
    p_mappings.__delta =  1
    setmetatable(data.entries,mte)
    setmetatable(data.m_mappings,mtm)
    setmetatable(data.z_mappings,mtm)
    setmetatable(data.p_mappings,mtm)
    thefirstofsplit = data.firstofsplit
end

local function update() -- prepare parent chains, needed when new languages are added
    for language, data in next, definitions do
        local parent = data.parent or "default"
        if language ~= "default" then
            setmetatableindex(data,definitions[parent] or definitions.default)
        end
        data.language   = language
        data.parent     = parent
        data.m_mappings = { } -- free temp data
        data.z_mappings = { } -- free temp data
        data.p_mappings = { } -- free temp data
    end
end

local function setlanguage(l,m,d,u) -- this will become a specification table (also keep this one as it's used in manuals)
    language = (l ~= "" and l) or constants.defaultlanguage
    data     = definitions[language or constants.defaultlanguage] or definitions[constants.defaultlanguage]
    method   = (m ~= "" and m) or (data.method ~= "" and data.method) or constants.defaultmethod
    digits   = (d ~= "" and d) or (data.digits ~= "" and data.digits) or constants.defaultdigits
    if trace_tests then
        report_sorters("setting language %a, method %a, digits %a",language,method,digits)
    end
    replacements = data.replacements
    entries      = data.entries
    orders       = data.orders
    lower        = data.lower
    upper        = data.upper
    preparetables(data)
    m_mappings   = data.m_mappings
    z_mappings   = data.z_mappings
    p_mappings   = data.p_mappings
    --
    method = predefinedmethods[variables[method]] or method
    data.method  = method
    --
    data.digits  = digits
    --
    local seq = utilities.parsers.settings_to_array(method or "") -- check the list
    sequence = { }
    local nofsequence = 0
    for i=1,#seq do
        local s = seq[i]
        if validmethods[s] then
            nofsequence = nofsequence + 1
            sequence[nofsequence] = s
        else
            report_sorters("invalid sorter method %a in %a",s,method)
        end
    end
    usedinsequence = tohash(sequence)
    data.sequence = sequence
    data.usedinsequence = usedinsequence
-- usedinsequence.ch = true -- better just store the string
    if trace_tests then
        report_sorters("using sort sequence: % t",sequence)
    end
    --
    return data
end

function sorters.update()
    update()
    setlanguage(language,method,numberorder) -- resync current language and method
end

function sorters.setlanguage(language,method,numberorder)
    update()
    setlanguage(language,method,numberorder) -- new language and method
end

-- tricky: { 0, 0, 0 } vs { 0, 0, 0, 0 } => longer wins and mm, pm, zm can have them

-- inlining and checking first slot first doesn't speed up (the 400K complex author sort)

local function basicsort(sort_a,sort_b)
    if sort_a and sort_b then
        local na = #sort_a
        local nb = #sort_b
        if na > nb then
            na = nb
        end
        if na > 0 then
            for i=1,na do
                local ai, bi = sort_a[i], sort_b[i]
                if ai > bi then
                    return  1
                elseif ai < bi then
                    return -1
                end
            end
        end
    end
    return 0
end

-- todo: compile compare function

local function basic(a,b) -- trace ea and eb
    if a == b then
        -- hashed (shared) entries
        return 0
    end
    local ea = a.split
    local eb = b.split
    local na = #ea
    local nb = #eb
    if na == 0 and nb == 0 then
        -- simple variant (single word)
        local result = 0
        for j=1,#sequence do
            local m = sequence[j]
            result = basicsort(ea[m],eb[m])
            if result ~= 0 then
                return result
            end
        end
        if result == 0 then
            local la = #ea.uc
            local lb = #eb.uc
            if la > lb then
                return 1
            elseif lb > la then
                return -1
            else
                return 0
            end
        else
            return result
        end
    else
        -- complex variant, used in register (multiple words)
        local result = 0
        for i=1,nb < na and nb or na do
            local eai = ea[i]
            local ebi = eb[i]
            for j=1,#sequence do
                local m = sequence[j]
                result = basicsort(eai[m],ebi[m])
                if result ~= 0 then
                    return result
                end
            end
            if result == 0 then
                local la = #eai.uc
                local lb = #ebi.uc
                if la > lb then
                    return 1
                elseif lb > la then
                    return -1
                end
            else
                return result
            end
        end
        if result ~= 0 then
            return result
        elseif na > nb then
            return 1
        elseif nb > na then
            return -1
        else
            return 0
        end
    end
end

-- if we use sq:
--
-- local function basic(a,b) -- trace ea and eb
--     local ea, eb = a.split, b.split
--     local na, nb = #ea, #eb
--     if na == 0 and nb == 0 then
--         -- simple variant (single word)
--         return basicsort(ea.sq,eb.sq)
--     else
--         -- complex variant, used in register (multiple words)
--         local result = 0
--         for i=1,nb < na and nb or na do
--             local eai, ebi = ea[i], eb[i]
--             result = basicsort(ea.sq,eb.sq)
--             if result ~= 0 then
--                 return result
--             end
--         end
--         if result ~= 0 then
--             return result
--         elseif na > nb then
--             return 1
--         elseif nb > na then
--             return -1
--         else
--             return 0
--         end
--     end
-- end

comparers.basic = basic

function sorters.basicsorter(a,b)
    return basic(a,b) == -1
end

local function numify(old)
    if digits == v_numbers then -- was swapped, fixed 2014-11-10
        local new = digitsoffset + tonumber(old) -- alternatively we can create range
        if new > digitsmaximum then
            new = digitsmaximum
        end
        return utfchar(new)
    else
        return old
    end
end

local pattern = nil

local function prepare() -- todo: test \Ux{hex}
    pattern = Cs( (
        characters.tex.toutfpattern()
      + lpeg.patterns.whitespace / "\000"
      + (P("\\Ux{") / "" * ((1-P("}"))^1/function(s) return utfchar(tonumber(s,16)) end) * (P("}")/""))
      + (P("\\") / "") * R("AZ")^0 * (P(-1) + #(1-R("AZ")))
      + (P("\\") * P(1) * R("az","AZ")^0) / ""
      + S("[](){}$\"'") / ""
      + R("09")^1 / numify
      + P(1)
    )^0 )
    return pattern
end

local function strip(str) -- todo: only letters and such
    if str and str ~= "" then
        return lpegmatch(pattern or prepare(),str)
    else
        return ""
    end
end

sorters.strip = strip

local function firstofsplit(entry)
    -- numbers are left padded by spaces
    local split = entry.split
    if #split > 0 then
        split = split[1].ch
    else
        split = split.ch
    end
    local first = split and split[1] or ""
    if thefirstofsplit then
        return thefirstofsplit(first,data,entry) -- normally the first one is needed
    else
        return first, entries[first] or "\000" -- tag
    end
end

sorters.firstofsplit = firstofsplit

-- for the moment we use an inefficient bunch of tables but once
-- we know what combinations make sense we can optimize this

function splitters.utf(str,checked) -- we could append m and u but this is cleaner, s is for tracing
    local nofreplacements = #replacements
    if nofreplacements > 0 then
        -- todo make an lpeg for this
        local replacer = replacements.replacer
        if not replacer then
            local rep = { }
            for i=1,nofreplacements do
                local r = replacements[i]
                rep[strip(r[1])] = strip(r[2])
            end
            replacer = lpeg.utfchartabletopattern(rep)
            replacer = Cs((replacer/rep + lpegpatterns.utf8character)^0)
            replacements.replacer = replacer
        end
        local rep = lpegmatch(replacer,str)
        if rep and rep ~= str then
            if trace_replacements then
                report_sorters("original   : %s",str)
                report_sorters("replacement: %s",rep)
            end
            str = rep
        end
     -- for k=1,#replacements do
     --     local v = replacements[k]
     --     local s = v[1]
     --     if find(str,s) then
     --         str = gsub(str,s,v[2])
     --     end
     -- end
    end
    local m_case    = { }
    local z_case    = { }
    local p_case    = { }
    local m_mapping = { }
    local z_mapping = { }
    local p_mapping = { }
    local char      = { }
    local byte      = { }
    local n         = 0
    local nm        = 0
    local nz        = 0
    local np        = 0
    for sc in utfcharacters(str) do
        local b = utfbyte(sc)
        if b >= digitsoffset then
            if n == 0 then
                -- we need to force number to the top
                z_case[1] = 0
                m_case[1] = 0
                p_case[1] = 0
                char[1] = sc
                byte[1] = 0
                m_mapping[1] = 0
                z_mapping[1] = 0
                p_mapping[1] = 0
                n = 2
            else
                n = n + 1
            end
            z_case[n] = b
            m_case[n] = b
            p_case[n] = b
            char[n] = sc
            byte[n] = b
            nm = nm + 1
            nz = nz + 1
            np = np + 1
            m_mapping[nm] = b
            z_mapping[nz] = b
            p_mapping[np] = b
        else
            n = n + 1
            local l = lower[sc]
            l = l and utfbyte(l) or lccodes[b] or b
         -- local u = upper[sc]
         -- u = u and utfbyte(u) or uccodes[b] or b
            if type(l) == "table" then
                l = l[1] -- there are currently no tables in lccodes but it can be some, day
            end
         -- if type(u) == "table" then
         --     u = u[1] -- there are currently no tables in lccodes but it can be some, day
         -- end
            z_case[n] = l
            if l ~= b then
                m_case[n] = l - 1
                p_case[n] = l + 1
            else
                m_case[n] = l
                p_case[n] = l
            end
            char[n], byte[n] = sc, b
            local fs = fscodes[b] or b
            local msc = m_mappings[sc]
            if msc ~= noorder then
                if not msc then
                    msc = m_mappings[fs]
                end
                for i=1,#msc do
                    nm = nm + 1
                    m_mapping[nm] = msc[i]
                end
            end
            local zsc = z_mappings[sc]
            if zsc ~= noorder then
                if not zsc then
                    zsc = z_mappings[fs]
                end
                for i=1,#zsc do
                    nz = nz + 1
                    z_mapping[nz] = zsc[i]
                end
            end
            local psc = p_mappings[sc]
            if psc ~= noorder then
                if not psc then
                    psc = p_mappings[fs]
                end
                for i=1,#psc do
                    np = np + 1
                    p_mapping[np] = psc[i]
                end
            end
        end
    end
    -- -- only those needed that are part of a sequence
    --
    -- local b = byte[1]
    -- if b then
    --     -- we set them to the first split code (korean)
    --     local fs = fscodes[b] or b
    --     if #m_mapping == 0 then
    --         m_mapping = { m_mappings[fs][1] }
    --     end
    --     if #z_mapping == 0 then
    --         z_mapping = { z_mappings[fs][1] }
    --     end
    --     if #p_mapping == 0 then
    --         p_mapping = { p_mappings[fs][1] }
    --     end
    -- end
    local result
    if checked then
        result = {
            ch = trace_tests       and char      or nil, -- not in sequence
            uc = usedinsequence.uc and byte      or nil,
            mc = usedinsequence.mc and m_case    or nil,
            zc = usedinsequence.zc and z_case    or nil,
            pc = usedinsequence.pc and p_case    or nil,
            mm = usedinsequence.mm and m_mapping or nil,
            zm = usedinsequence.zm and z_mapping or nil,
            pm = usedinsequence.pm and p_mapping or nil,
        }
    else
        result = {
            ch = char,
            uc = byte,
            mc = m_case,
            zc = z_case,
            pc = p_case,
            mm = m_mapping,
            zm = z_mapping,
            pm = p_mapping,
        }
    end
 -- local sq, n = { }, 0
 -- for i=1,#byte do
 --     for s=1,#sequence do
 --         n = n + 1
 --         sq[n] = result[sequence[s]][i]
 --     end
 -- end
 -- result.sq = sq
    return result
end

local function packch(entry)
    local split = entry.split
    if split and #split > 0 then -- useless test
        local t = { }
        for i=1,#split do
            local tt = { }
            local ch = split[i].ch
            for j=1,#ch do
                local chr = ch[j]
                local byt = utfbyte(chr)
                if byt > ignoredoffset then
                    tt[j] = "[]"
                elseif byt == 0 then
                    tt[j] = " "
                else
                    tt[j] = chr
                end
            end
            t[i] = concat(tt)
        end
        return concat(t," + ")
    else
        local t  = { }
        local ch = (split and split.ch) or entry.ch or entry
        if ch then
            for i=1,#ch do
                local chr = ch[i]
                local byt = utfbyte(chr)
                if byt > ignoredoffset then
                    t[i] = "[]"
                elseif byt == 0 then
                    t[i] = " "
                else
                    t[i] = chr
                end
            end
            return concat(t)
        else
            return ""
        end
    end
end

local function packuc(entry)
    local split = entry.split
    if split and #split > 0 then -- useless test
        local t = { }
        for i=1,#split do
            t[i] = concat(split[i].uc, " ") -- sq
        end
        return concat(t," + ")
    else
        local uc = (split and split.uc) or entry.uc or entry
        if uc then
            return concat(uc," ") -- sq
        else
            return ""
        end
    end
end

sorters.packch = packch
sorters.packuc = packuc

function sorters.sort(entries,cmp)
    if trace_methods then
        local nofentries = #entries
        report_sorters("entries: %s, language: %s, method: %s, digits: %s",nofentries,language,method,tostring(digits))
        for i=1,nofentries do
            report_sorters("entry %s",table.serialize(entries[i].split,i,true,true,true))
        end
    end
    if trace_tests then
        sort(entries,function(a,b)
            local r = cmp(a,b)
            local e = (not r and "?") or (r<0 and "<") or (r>0 and ">") or "="
            report_sorters("%s %s %s | %s %s %s",packch(a),e,packch(b),packuc(a),e,packuc(b))
            return r == -1
        end)
        local s
        for i=1,#entries do
            local entry = entries[i]
            local letter, first = firstofsplit(entry)
            if first == s then
                first = "  "
            else
                s = first
                if first and letter then
                    report_sorters(">> %C (%C)",first,letter)
                end
            end
            report_sorters("   %s | %s",packch(entry),packuc(entry))
        end
    else
        sort(entries,function(a,b)
            return cmp(a,b) == -1
        end)
    end
end

-- helper

function sorters.replacementlist(list)
    local replacements = { }
    for i=1,#list do
        replacements[i] = {
            list[i],
            utfchar(replacementoffset+i),
        }
    end
    return replacements
end