sounio-benchmarks/053_queue_from_stacks.sio at main · Sounio-lang/sounio-benchmarks · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//@ run-pass
// HumanEval 053: Queue from Two Stacks
//
// Implement a FIFO queue using two stacks. Stack1 is for enqueue,
// stack2 is for dequeue. When stack2 is empty, transfer all elements
// from stack1 to stack2 (reversing order to get FIFO).

struct Queue {
    s1_data: [i64; 256],
    s1_top: i64,
    s2_data: [i64; 256],
    s2_top: i64
}

fn q_new() -> Queue {
    Queue { s1_data: [0; 256], s1_top: 0, s2_data: [0; 256], s2_top: 0 }
}

fn q_enqueue(q: &!Queue, val: i64) with Mut, Panic {
    q.s1_data[q.s1_top] = val
    q.s1_top = q.s1_top + 1
}

fn q_transfer(q: &!Queue) with Mut, Panic {
    // Move all from s1 to s2 (reverses order)
    while q.s1_top > 0 {
        q.s1_top = q.s1_top - 1
        q.s2_data[q.s2_top] = q.s1_data[q.s1_top]
        q.s2_top = q.s2_top + 1
    }
}

fn q_dequeue(q: &!Queue) -> i64 with Mut, Panic {
    if q.s2_top == 0 {
        q_transfer(q)
    }
    q.s2_top = q.s2_top - 1
    q.s2_data[q.s2_top]
}

fn q_peek(q: &!Queue) -> i64 with Mut, Panic {
    if q.s2_top == 0 {
        q_transfer(q)
    }
    q.s2_data[q.s2_top - 1]
}

fn q_empty(q: &Queue) -> i64 {
    if q.s1_top == 0 {
        if q.s2_top == 0 {
            return 1
        }
    }
    0
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: basic FIFO order
    var q1 = q_new()
    q_enqueue(&!q1, 1)
    q_enqueue(&!q1, 2)
    q_enqueue(&!q1, 3)
    assert(q_dequeue(&!q1) == 1)
    assert(q_dequeue(&!q1) == 2)
    assert(q_dequeue(&!q1) == 3)

    // Test 2: interleaved enqueue/dequeue
    var q2 = q_new()
    q_enqueue(&!q2, 10)
    q_enqueue(&!q2, 20)
    assert(q_dequeue(&!q2) == 10)
    q_enqueue(&!q2, 30)
    assert(q_dequeue(&!q2) == 20)
    assert(q_dequeue(&!q2) == 30)

    // Test 3: peek does not remove
    var q3 = q_new()
    q_enqueue(&!q3, 42)
    q_enqueue(&!q3, 99)
    assert(q_peek(&!q3) == 42)
    assert(q_peek(&!q3) == 42)
    assert(q_dequeue(&!q3) == 42)
    assert(q_peek(&!q3) == 99)

    // Test 4: empty check
    var q4 = q_new()
    assert(q_empty(&q4) == 1)
    q_enqueue(&!q4, 5)
    assert(q_empty(&q4) == 0)
    let v = q_dequeue(&!q4)
    assert(v == 5)
    assert(q_empty(&q4) == 1)

    // Test 5: many elements
    var q5 = q_new()
    var i: i64 = 0
    while i < 10 {
        q_enqueue(&!q5, i * 100)
        i = i + 1
    }
    var j: i64 = 0
    while j < 10 {
        assert(q_dequeue(&!q5) == j * 100)
        j = j + 1
    }

    println("053_queue_from_stacks: ALL TESTS PASSED")
    0
}