Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / tests_binary_heap.lucb

#==============================================================================================
#
#   tests_binary_heap - BinaryHeap<K, V>, Queue<T>, Stack<T>, CircularQueue<T>, IDAllocator
#
#   DESCRIPTION:
#       Ports of Tests/AK/TestBinaryHeap.cpp, TestQueue.cpp, TestStack.cpp and
#       TestCircularQueue.cpp (ByteString values are `str`; the randomized heap cases run over
#       a fixed pseudo-random sequence), and focused IDAllocator cases.
#
#==============================================================================================

# mark: TestBinaryHeap ==========================================================================

test "binary_heap: construct":
    var empty: BinaryHeap[i32, i32]
    assert(binary_heap_is_empty(&empty))
    assert(binary_heap_size(&empty) == 0)

test "binary_heap: construct_from_existing":
    let keys: i32[3] = [3, 2, 1]
    let values: u8[3] = ['c', 'b', 'a']
    var from_existing: BinaryHeap[i32, u8]
    binary_heap_construct(&from_existing, &keys[0], &values[0], 3)
    assert(binary_heap_size(&from_existing) == 3)
    assert(binary_heap_pop_min(&from_existing) == 'a')
    assert(binary_heap_pop_min(&from_existing) == 'b')
    assert(binary_heap_pop_min(&from_existing) == 'c')

test "binary_heap: populate_int":
    var ints: BinaryHeap[i32, i32]
    binary_heap_insert(&ints, 1, 10)
    binary_heap_insert(&ints, 3, 20)
    binary_heap_insert(&ints, 2, 30)
    assert(binary_heap_size(&ints) == 3)
    assert(binary_heap_pop_min(&ints) == 10)
    assert(binary_heap_size(&ints) == 2)
    assert(binary_heap_pop_min(&ints) == 30)
    assert(binary_heap_size(&ints) == 1)
    assert(binary_heap_pop_min(&ints) == 20)
    assert(binary_heap_size(&ints) == 0)

test "binary_heap: populate_string":
    var strings: BinaryHeap[i32, str]
    binary_heap_insert(&strings, 1, "ABC")
    binary_heap_insert(&strings, 2, "DEF")
    assert(binary_heap_size(&strings) == 2)
    assert(binary_heap_pop_min(&strings) == "ABC")
    assert(binary_heap_pop_min(&strings) == "DEF")
    assert(binary_heap_is_empty(&strings))

test "binary_heap: large_populate_reverse":
    var ints: BinaryHeap[i32, i32]
    var i: i32 = 1023
    while i >= 0:
        binary_heap_insert(&ints, i, i)
        i -= 1
    assert(binary_heap_size(&ints) == 1024)
    for j: i32 in 0..<1024:
        assert(binary_heap_peek_min(&ints) == j)
        assert(binary_heap_peek_min_key(&ints) == j)
        assert(binary_heap_pop_min(&ints) == j)

test "binary_heap: pop_min_is_min over pseudo-random keys":
    var state: u64 = 12345
    for round in 0..<50:
        _ = round
        var heap: BinaryHeap[u64, u64]
        var values: Vector[u64]
        state = state *% 6364136223846793005 +% 1442695040888963407
        let count = 1 + (state >> 60) % 10
        for k in 0..<count:
            _ = k
            state = state *% 6364136223846793005 +% 1442695040888963407
            binary_heap_insert(&heap, state, state)
            vector_append_t(&values, state)
        var previous: u64 = 0
        while not binary_heap_is_empty(&heap):
            let peeked = binary_heap_peek_min(&heap)
            let popped = binary_heap_pop_min(&heap)
            assert(peeked == popped)
            assert(popped >= previous)
            previous = popped
        binary_heap_clear(&heap)

# mark: TestQueue ===============================================================================

test "queue: construct and populate_int":
    var ints: Queue[i32]
    assert(queue_is_empty(&ints))
    assert(queue_size(&ints) == 0)
    queue_enqueue(&ints, 1)
    queue_enqueue(&ints, 2)
    queue_enqueue(&ints, 3)
    assert(queue_size(&ints) == 3)
    assert(*queue_head(&ints) == 1)
    assert(*queue_tail(&ints) == 3)
    assert(queue_dequeue(&ints) == 1)
    assert(queue_size(&ints) == 2)
    assert(queue_dequeue(&ints) == 2)
    assert(queue_dequeue(&ints) == 3)
    assert(queue_size(&ints) == 0)
    queue_try_dequeue(&ints) catch failure:
        assert(failure.code == ak_errno_error)
        assert(ak_pending_error.m_code == enoent)
        recover 0

test "queue: populate_string":
    var strings: Queue[str]
    queue_enqueue(&strings, "ABC")
    queue_enqueue(&strings, "DEF")
    assert(queue_size(&strings) == 2)
    assert(queue_dequeue(&strings) == "ABC")
    assert(queue_dequeue(&strings) == "DEF")
    assert(queue_is_empty(&strings))

struct TestQueueSum:
    var sum: i64

func test_queue_add(context: void*?, value: const i64*):
    let captures = (TestQueueSum*)(context else trap("no captures"))
    captures.sum += *value

test "queue: order across segments":
    with memory.heap:
        var numbers: Queue[i64]
        for i: i64 in 0..<10000:
            queue_enqueue(&numbers, i)
            assert(queue_size(&numbers) == (usize)(i + 1))
        for i: i64 in 0..<1500:
            assert(queue_dequeue(&numbers) == i)
        var captures = TestQueueSum(sum = 0)
        queue_for_each(&numbers, Function1[const i64*, unit](call = test_queue_add, context = &captures))
        assert(captures.sum == 49995000 - 1124250)
        for i: i64 in 1500..<10000:
            assert(queue_dequeue(&numbers) == i)
        assert(queue_is_empty(&numbers))
        queue_enqueue(&numbers, 7)
        queue_clear(&numbers)
        assert(queue_is_empty(&numbers))

# mark: TestStack ===============================================================================

test "stack: basic":
    var stack: Stack[i32]
    stack_construct(&stack, 3)
    assert(stack_is_empty(&stack))
    assert(stack_push(&stack, 2))
    assert(stack_push(&stack, 4))
    assert(stack_push(&stack, 17))
    assert(not stack_push(&stack, 18))
    assert(stack_size(&stack) == 3)
    assert(*stack_top(&stack) == 17)
    assert(stack_contains_slow[i32, I32Traits](&stack, 4))
    assert(stack_pop(&stack))
    assert(stack_pop(&stack))
    assert(stack_pop(&stack))
    assert(not stack_pop(&stack))
    assert(stack_is_empty(&stack))

test "stack: complex_type":
    var stack: Stack[str]
    stack_construct(&stack, 4)
    assert(stack_is_empty(&stack))
    assert(stack_push(&stack, "Well"))
    assert(stack_push(&stack, "Hello"))
    assert(stack_push(&stack, "Friends"))
    assert(stack_push_2(&stack, ":^)"))
    assert(stack_top_const(&stack) == ":^)")
    assert(stack_pop(&stack))
    assert(stack_top_const(&stack) == "Friends")
    assert(stack_pop(&stack))
    assert(stack_top_const(&stack) == "Hello")
    assert(stack_pop(&stack))
    assert(stack_top_const(&stack) == "Well")
    assert(stack_pop(&stack))
    assert(stack_is_empty(&stack))

# mark: TestCircularQueue =======================================================================

test "circular_queue: basic":
    var ints: CircularQueue[i32]
    circular_queue_construct(&ints, 3)
    assert(circular_queue_is_empty(&ints))
    circular_queue_enqueue(&ints, 1)
    circular_queue_enqueue(&ints, 2)
    circular_queue_enqueue(&ints, 3)
    assert(circular_queue_size(&ints) == 3)
    circular_queue_enqueue(&ints, 4)
    assert(circular_queue_size(&ints) == 3)
    assert(circular_queue_first(&ints) == 2)
    assert(circular_queue_last(&ints) == 4)
    assert(circular_queue_head_index(&ints) == 1)
    var expected: i32 = 2
    for value in circular_queue_begin(&ints):
        assert(*value == expected)
        expected += 1
    assert(expected == 5)
    assert(circular_queue_dequeue(&ints) == 2)
    assert(circular_queue_dequeue(&ints) == 3)
    assert(circular_queue_dequeue(&ints) == 4)
    assert(circular_queue_size(&ints) == 0)

test "circular_queue: complex_type and clear":
    var strings: CircularQueue[str]
    circular_queue_construct(&strings, 2)
    circular_queue_enqueue(&strings, "ABC")
    circular_queue_enqueue(&strings, "DEF")
    assert(circular_queue_size(&strings) == 2)
    circular_queue_enqueue(&strings, "abc")
    circular_queue_enqueue(&strings, "def")
    assert(circular_queue_dequeue(&strings) == "abc")
    assert(circular_queue_dequeue(&strings) == "def")
    var more: CircularQueue[str]
    circular_queue_construct(&more, 5)
    for i in 0..<5:
        _ = i
        circular_queue_enqueue(&more, "xxx")
    assert(circular_queue_size(&more) == 5)
    assert(circular_queue_capacity(&more) == 5)
    circular_queue_clear(&more)
    assert(circular_queue_size(&more) == 0)