sketch_min_heap_test.nx source
↩ module page · 123 lines · 4126 B
1// sketch_min_heap_test.nx -- binary min-heap verification.
2
3import "syscalls.nx"
4import "sketch_min_heap.nx"
5
6func main() -> i64 {
7 // ---- alloc ----
8 let h: *MinHeap = nx_heap_alloc(16)
9 if h == (0 as *MinHeap) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
10 if h.size != 0 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
11 // Reject capacity < 4.
12 if nx_heap_alloc(2) != (0 as *MinHeap) {
13 return __syscall(93, 7, 0, 0, 0, 0, 0)
14 }
15
16 // ---- push + peek ----
17 nx_heap_push(h, 50, 500)
18 nx_heap_push(h, 10, 100) // smaller key; bubbles to root
19 nx_heap_push(h, 30, 300)
20 nx_heap_push(h, 20, 200)
21 nx_heap_push(h, 40, 400)
22 if nx_heap_size(h) != 5 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
23 // Min is 10 (key) / 100 (value).
24 if nx_heap_peek_key(h) != 10 {
25 return __syscall(93, 11, 0, 0, 0, 0, 0)
26 }
27 if nx_heap_peek_value(h) != 100 {
28 return __syscall(93, 12, 0, 0, 0, 0, 0)
29 }
30
31 // ---- pop in ascending order ----
32 var prev_key: i64 = -1
33 var n_popped: i64 = 0
34 while nx_heap_size(h) > 0 {
35 let k: i64 = nx_heap_peek_key(h)
36 if k < prev_key {
37 return __syscall(93, 20, 0, 0, 0, 0, 0) // out of order
38 }
39 prev_key = k
40 nx_heap_pop(h)
41 n_popped = n_popped + 1
42 }
43 if n_popped != 5 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
44 if nx_heap_size(h) != 0 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
45 // Pop on empty returns -1.
46 if nx_heap_pop(h) != -1 {
47 return __syscall(93, 23, 0, 0, 0, 0, 0)
48 }
49
50 // ---- streaming inserts produce sorted output ----
51 let h2: *MinHeap = nx_heap_alloc(100)
52 // Insert in shuffled order.
53 let order: *i64 = sys_mmap(20 * 8) as *i64
54 order[0] = 73; order[1] = 12; order[2] = 5; order[3] = 89; order[4] = 41
55 order[5] = 67; order[6] = 23; order[7] = 1; order[8] = 99; order[9] = 50
56 order[10] = 38; order[11] = 7; order[12] = 84; order[13] = 19; order[14] = 56
57 order[15] = 92; order[16] = 30; order[17] = 75; order[18] = 11; order[19] = 64
58 var i: i64 = 0
59 while i < 20 {
60 nx_heap_push(h2, order[i], i)
61 i = i + 1
62 }
63 if nx_heap_size(h2) != 20 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
64 // Pop all -> must come out sorted ascending.
65 prev_key = -1
66 while nx_heap_size(h2) > 0 {
67 let k: i64 = nx_heap_peek_key(h2)
68 if k < prev_key {
69 return __syscall(93, 31, 0, 0, 0, 0, 0)
70 }
71 prev_key = k
72 nx_heap_pop(h2)
73 }
74 // Min should have been 1.
75 // Already verified by ascending order.
76
77 // ---- top-K offer pattern ----
78 // Keep top-5 LARGEST from a stream 1..100.
79 let topk: *MinHeap = nx_heap_alloc(5)
80 i = 1
81 while i <= 100 {
82 nx_heap_top_k_offer(topk, i, 0)
83 i = i + 1
84 }
85 if nx_heap_size(topk) != 5 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
86 // Pop the 5 -- should come out 96, 97, 98, 99, 100 (ascending pop order
87 // for min-heap = the 5 largest in ascending order).
88 let expected: *i64 = sys_mmap(5 * 8) as *i64
89 expected[0] = 96; expected[1] = 97; expected[2] = 98
90 expected[3] = 99; expected[4] = 100
91 i = 0
92 while i < 5 {
93 let k: i64 = nx_heap_peek_key(topk)
94 if k != expected[i] {
95 return __syscall(93, 41, 0, 0, 0, 0, 0)
96 }
97 nx_heap_pop(topk)
98 i = i + 1
99 }
100
101 // ---- capacity overflow ----
102 let small: *MinHeap = nx_heap_alloc(4)
103 nx_heap_push(small, 1, 0)
104 nx_heap_push(small, 2, 0)
105 nx_heap_push(small, 3, 0)
106 nx_heap_push(small, 4, 0)
107 if nx_heap_push(small, 5, 0) != -1 {
108 return __syscall(93, 50, 0, 0, 0, 0, 0)
109 }
110
111 // ---- clear ----
112 nx_heap_clear(small)
113 if nx_heap_size(small) != 0 {
114 return __syscall(93, 60, 0, 0, 0, 0, 0)
115 }
116 // After clear, push works again.
117 nx_heap_push(small, 42, 0)
118 if nx_heap_peek_key(small) != 42 {
119 return __syscall(93, 61, 0, 0, 0, 0, 0)
120 }
121
122 return 0
123}