Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.45.0

0.45.0 / src / support / order.lucb

#==============================================================================================
#
#   order - A stable sort for the compiler's own arrays
#
#   DESCRIPTION:
#       A bottom-up merge sort: n log n comparisons, equal items kept in the order they
#       came, and one scratch array of the same length from the current allocator. The
#       compiler's sources keep to what the seed's library has, which has no sort.
#
#==============================================================================================

## `items` ordered by `less`, equal items in their order.
pub func stable[T](items: T[], less: func(T, T) -> bool) -> !:
    let n = items.length
    if n < 2:
        return
    var other = try new T[n] ---
    defer free(other)
    var source = items
    var target = other
    var width: usize = 1
    # whether the sorted runs are in `other` after the last pass
    var moved = false
    while width < n:
        var start: usize = 0
        while start < n:
            let middle = start + width if start + width < n else n
            let end = start + 2 * width if start + 2 * width < n else n
            var i = start
            var j = middle
            for k in start..<end:
                # the right run's item goes first only when it is strictly less
                if i < middle and (j >= end or not less(source[j], source[i])):
                    target[k] = source[i]
                    i += 1
                else:
                    target[k] = source[j]
                    j += 1
            start = end
        let swap = source
        source = target
        target = swap
        moved = not moved
        width *= 2
    if moved:
        for k in 0..<n:
            items[k] = source[k]

func before(a: u32, b: u32) -> bool:
    return a < b

func by_key(a: (u32, u32), b: (u32, u32)) -> bool:
    let (x, _) = a
    let (y, _) = b
    return x < y

test "a merge sort orders, past one run's width, and keeps equal items in their order":
    var values: u32[9] = [5, 3, 9, 1, 3, 7, 2, 8, 0]
    try stable(values, before)
    for k in 1..<values.length:
        assert(values[k - 1] <= values[k])
    var pairs: (u32, u32)[5] = [(2, 0), (1, 1), (2, 2), (1, 3), (0, 4)]
    try stable(pairs, by_key)
    let (_, first) = pairs[1]
    let (_, second) = pairs[2]
    let (_, third) = pairs[3]
    assert(first == 1 and second == 3 and third == 0)