Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / tests_sort.lucb

#==============================================================================================
#
#   tests_sort - quick_sort, insertion_sort and binary_search
#
#   DESCRIPTION:
#       Ports of Tests/AK/TestQuickSort.cpp, TestInsertionSort.cpp and TestBinarySearch.cpp
#       (the randomized cases run over the test's deterministic seed), and the order
#       quick_sort leaves equal keys in, pinned against the donor's AK (it is not stable).
#
#==============================================================================================

struct TestSortPair:
    var key: i32
    var id: i32

func test_sort_pair_less(context: void*?, a: const TestSortPair*, b: const TestSortPair*) -> bool:
    _ = context
    return a.key < b.key

func test_sort_int_greater(context: void*?, a: const i32*, b: const i32*) -> bool:
    _ = context
    return *a > *b

func test_sort_int_less(context: void*?, a: const i32*, b: const i32*) -> bool:
    _ = context
    return *a < *b

test "quick_sort: sorts_without_copy":
    var array: TestSortPair[64]
    for i in 0..<64usize:
        array[i].key = (i32)((64 - i) % 32 + 32)
    let less = Function2[const TestSortPair*, const TestSortPair*, bool](call = test_sort_pair_less, context = none)
    dual_pivot_quick_sort(array, 0, 63, less)
    for i in 0..<63usize:
        assert(array[i].key <= array[i + 1].key)
    for i in 0..<64usize:
        array[i].key = (i32)((64 - i) % 32 + 32)
    single_pivot_quick_sort(array, less)
    for i in 0..<63usize:
        assert(array[i].key <= array[i + 1].key)

test "quick_sort: maximum_stack_depth":
    var data: i32[256]
    for i in 0..<256usize:
        data[i] = (i32)i
    # Construct the data in such a way that the assumed pivot choice
    # of (size / 2) causes the partitions to be of worst case size.
    for i in 0..<128usize:
        swap_5(&data[i], &data[i + (256 - i) // 2])
    quick_sort_t_iterator_t_iterator(data)
    for i in 0..<256usize:
        assert(data[i] == (i32)i)

test "quick_sort: the order of equal keys matches the donor":
    var v: Vector[TestSortPair]
    var w: Vector[TestSortPair]
    for i: i32 in 0..<40:
        vector_append_t(&v, TestSortPair(key = (i * 7) % 5, id = i))
        vector_append_t(&w, TestSortPair(key = (i * 7) % 5, id = i))
    let less = Function2[const TestSortPair*, const TestSortPair*, bool](call = test_sort_pair_less, context = none)
    quick_sort_t_collection_t_less_than(vector_span(&v), less)
    let dual: i32[40] = [10, 5, 15, 25, 20, 0, 30, 35, 13, 33, 38, 23, 3, 28, 18, 8, 26, 11, 21, 16, 36, 1, 31, 6, 24, 9, 39, 4, 14, 29, 19, 34, 32, 27, 17, 2, 22, 37, 12, 7]
    for i in 0..<40usize:
        assert(vector_at(&v, i).id == dual[i])
    quick_sort_t_iterator_t_iterator_t_less_than(vector_span(&w), less)
    let single: i32[40] = [20, 0, 15, 35, 25, 10, 30, 5, 18, 28, 13, 23, 33, 38, 8, 3, 21, 26, 11, 16, 31, 6, 36, 1, 29, 34, 4, 24, 19, 9, 39, 14, 12, 7, 37, 17, 22, 27, 32, 2]
    for i in 0..<40usize:
        assert(vector_at(&w, i).id == single[i])

test "quick_sort: default comparison":
    var values: i64[7] = [5, -3, 9, 0, 9, 2, -8]
    quick_sort_t_collection(values)
    for i in 0..<6usize:
        assert(values[i] <= values[i + 1])

test "insertion_sort: sorts_ascending and sorts_descending":
    for iteration in 0..<10:
        _ = iteration
        var ints: i32[10]
        for j in 0..<10usize:
            ints[j] = (i32)(testing.random() % 2000) - 1000
        var ints_copy = ints
        insertion_sort(ints)
        insertion_sort(ints_copy)
        for j in 0..<9usize:
            assert(ints[j] <= ints[j + 1])
            assert(ints[j] == ints_copy[j])
        let greater = Function2[const i32*, const i32*, bool](call = test_sort_int_greater, context = none)
        insertion_sort_t_comparator(ints, greater)
        for j in 0..<9usize:
            assert(ints[j] >= ints[j + 1])

test "insertion_sort: sorts_subrange_without_affecting_outside_elements":
    var ints: i32[10] = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    let original_ints = ints
    let start: isize = 3
    let end: isize = 6
    insertion_sort_isize(ints, start, end, Function2[const i32*, const i32*, bool](call = test_sort_int_less, context = none))
    for i in 3..<6usize:
        assert(ints[i] <= ints[i + 1])
    for i in 0..<3usize:
        assert(ints[i] == original_ints[i])
    for i in 7..<10usize:
        assert(ints[i] == original_ints[i])

test "binary_search: vector_ints, single_element, not_found, no_elements":
    var ints: Vector[i32]
    vector_append_t(&ints, 1)
    vector_append_t(&ints, 2)
    vector_append_t(&ints, 3)
    let compare = default_comparator[i32]()
    assert(*(binary_search(vector_span_const(&ints), 1i32, none, compare) else trap("missing")) == 1)
    assert(*(binary_search(vector_span_const(&ints), 2i32, none, compare) else trap("missing")) == 2)
    assert(*(binary_search(vector_span_const(&ints), 3i32, none, compare) else trap("missing")) == 3)
    assert(binary_search(vector_span_const(&ints), -1i32, none, compare) == none)
    assert(binary_search(vector_span_const(&ints), 0i32, none, compare) == none)
    assert(binary_search(vector_span_const(&ints), 4i32, none, compare) == none)
    var empty: Vector[i32]
    assert(binary_search(vector_span_const(&empty), 1i32, none, compare) == none)

test "binary_search: span_rvalue_reference, array_doubles and unsigned_to_signed_regression":
    let array: i64[3] = [1, 2, 3]
    var nearby_index: usize = 0
    let pointer = binary_search(array, 2i64, &nearby_index, default_comparator[i64]()) else trap("missing")
    assert(nearby_index == 1)
    assert(*pointer == 2)
    let doubles: f64[3] = [1.1, 9.9, 33.33]
    let compare = default_comparator[f64]()
    assert(*(binary_search(doubles, 1.1, none, compare) else trap("missing")) == 1.1)
    assert(*(binary_search(doubles, 33.33, none, compare) else trap("missing")) == 33.33)
    assert(*(binary_search(doubles, 9.9, none, compare) else trap("missing")) == 9.9)
    let input: u32[5] = [0, 1, 2, 3, 4]
    # The algorithm computes 1 - input[2] = -1, and if this is (incorrectly) cast
    # to an unsigned then it will look in the wrong direction and miss the 1.
    nearby_index = 1
    assert(*(binary_search(input, 1u32, &nearby_index, default_comparator[u32]()) else trap("missing")) == 1)
    assert(nearby_index == 1)

test "binary_search: finds present numbers and not absent ones":
    for round in 0..<20:
        _ = round
        var values: u64[16]
        for i in 0..<16usize:
            values[i] = testing.random() % 1000
        quick_sort_t_collection(values)
        let compare = default_comparator[u64]()
        let n = values[(usize)(testing.random() % 16)]
        assert(*(binary_search(values, n, none, compare) else trap("missing")) == n)
        var not_present: u64 = 0
        var found = true
        while found:
            found = false
            for value in values:
                if value == not_present:
                    found = true
            if found:
                not_present += 1
        assert(binary_search(values, not_present, none, compare) == none)