模块:Sort

此模块的文档可以在模块:Sort/doc创建

-- Mono's sort function
-- This is an unstable sort. It is ported to keep in-game order.

local p = {}

p.sortWithKey = function(array, key)
    local newArr = {}
    local length = 0
    for i, x in ipairs(array) do
        newArr[i - 1] = x
        length = i
    end

    local comparer
    if type(key) == 'string' then
        comparer = function(a, b)
            return a[key] - b[key]
        end
    else
        comparer = function(a, b)
            return key(a) - key(b)
        end
    end

    IntrospectiveSort(newArr, 0, length, comparer)

    for i = 1, length do
        array[i] = newArr[i - 1]
    end
end

function SwapIfGreater(keys, comparer, a, b)
    if a ~= b then
        if comparer(keys[a], keys[b]) > 0 then
            local temp = keys[a]
            keys[a] = keys[b]
            keys[b] = temp
        end
    end
end

function Swap(keys, i, j)
    local t = keys[i]
    keys[i] = keys[j]
    keys[j] = t
end

function IntrospectiveSort(keys, left, length, comparer)
    if length < 2 then
        return
    end
    return IntroSort(keys, left, length + left - 1, 2 * FloorLog2(length), comparer)
end

function IntroSort(keys, lo, hi, depthLimit, comparer)
    while hi > lo do
        local partitionSize = hi - lo + 1
        if partitionSize <= 16 then
            if partitionSize == 1 then
                return
            end
            if partitionSize == 2 then
                SwapIfGreater(keys, comparer, lo, hi)
                return
            end
            if partitionSize == 3 then
                SwapIfGreater(keys, comparer, lo, hi - 1)
                SwapIfGreater(keys, comparer, lo, hi)
                SwapIfGreater(keys, comparer, hi - 1, hi)
                return
            end

            InsertionSort(keys, lo, hi, comparer)
            return
        end

        if depthLimit == 0 then
            error('Reached depth limit')
        end
        depthLimit = depthLimit - 1

        local p = PickPivotAndPartition(keys, lo, hi, comparer)
        if p == nil then
            error('p == nil ; lo == ' .. tostring(lo))
        end
        IntroSort(keys, p + 1, hi, depthLimit, comparer)
        hi = p - 1
    end
end

function PickPivotAndPartition(keys, lo, hi, comparer)
    local mid = lo + math.floor((hi - lo) / 2)
    SwapIfGreater(keys, comparer, lo, mid)
    SwapIfGreater(keys, comparer, lo, hi)
    SwapIfGreater(keys, comparer, mid, hi)

    local pivot = keys[mid]
    Swap(keys, mid, hi - 1)
    local left = lo
    local right = hi - 1

    while left < right do
        while true do
            left = left + 1
            if not (comparer(keys[left], pivot) < 0) then
                break
            end
        end
        while true do
            right = right - 1
            if not (comparer(pivot, keys[right]) < 0) then
                break
            end
        end

        if left >= right then
            break
        end

        Swap(keys, left, right)

    end
    Swap(keys, left, hi - 1)
    return left
end

function InsertionSort(keys, lo, hi, comparer)
    local i = lo
    while i < hi do
        local j = i
        local t = keys[i + 1]
        while j >= lo and comparer(t, keys[j]) < 0 do
            keys[j + 1] = keys[j]
            j = j - 1
        end
        keys[j + 1] = t
        i = i + 1
    end
end

function FloorLog2(n)
    local result = 0
    while n >= 1 do
        result = result + 1
        n = math.floor(n / 2)
    end
    return result
end

p.debug = function()
    local array = {
        { key = 1000099, id = 40000012 },
        { key = 100101, id = 40000186 },
        { key = 4701100, id = 40000202 },
        { key = 600101, id = 40000208 },
        { key = 600011, id = 40000209 },
        { key = 4701100, id = 40000216 },
        { key = 470031, id = 40000218 },
        { key = 4701100, id = 40000228 },
        { key = 6001199, id = 40000232 },
        { key = 4701100, id = 40000235 },
        { key = 4701100, id = 40000236 },
        { key = 4701099, id = 40000239 },
        { key = 4400099, id = 40000240 },
        { key = 4701099, id = 40000241 },
        { key = 440011, id = 40000245 },
        { key = 980301, id = 40000254 },
        { key = 100111, id = 40000255 },
        { key = 200122, id = 40000262 },
        { key = 460011, id = 40000266 },
        { key = 450011, id = 40000275 },
        { key = 6000299, id = 40000276 },
        { key = 4500299, id = 40000280 },
        { key = 100221, id = 40000289 },
        { key = 300912, id = 40000290 },
        { key = 4700099, id = 40000294 },
        { key = 980052, id = 40000297 },
        { key = 4701099, id = 40000302 },
        { key = 4600299, id = 40000308 },
        { key = 4400299, id = 40000310 },
        { key = 470012, id = 40000313 },
        { key = 200131, id = 40000316 },
        { key = 980991, id = 40000317 },
        { key = 100212, id = 40000326 },
        { key = 200133, id = 40000337 },
        { key = 600991, id = 40000357 },
        { key = 4701099, id = 40000451 },
        { key = 100001, id = 40000452 },
        { key = 100001, id = 40000457 },
        { key = 460001, id = 40000458 },
        { key = 100001, id = 40000480 },
        { key = 1000099, id = 40000482 },
        { key = 100001, id = 40000496 },
    }
    p.sortWithKey(array, 'key')
    for i, item in ipairs(array) do
        mw.log(item.key, item.id)
    end
end

return p