sketch_segment_tree_test.nx source
↩ module page · 133 lines · 3986 B
1// sketch_segment_tree_test.nx -- range sum / min / max verification.
2
3import "syscalls.nx"
4import "sketch_segment_tree.nx"
5import "sketch_types.nx"
6
7func main() -> i64 {
8 // ---- alloc ----
9 let t: *SegmentTree = nx_st_alloc(8)
10 if t == (0 as *SegmentTree) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
11 // Reject n<2.
12 if nx_st_alloc(1) != (0 as *SegmentTree) {
13 return __syscall(93, 6, 0, 0, 0, 0, 0)
14 }
15
16 // ---- single update + point read ----
17 nx_st_update(t, 0, 5)
18 if nx_st_get(t, 0) != 5 {
19 return __syscall(93, 10, 0, 0, 0, 0, 0)
20 }
21 // Initial unwritten slots: sum=0.
22 if nx_st_get(t, 3) != 0 {
23 return __syscall(93, 11, 0, 0, 0, 0, 0)
24 }
25
26 // ---- populate 8 elements: [1, 2, 3, 4, 5, 6, 7, 8] ----
27 var i: i64 = 0
28 while i < 8 {
29 nx_st_update(t, i, i + 1)
30 i = i + 1
31 }
32
33 // ---- range_sum ----
34 // Full range: 1+2+..+8 = 36
35 if nx_st_range_sum(t, 0, 8) != 36 {
36 return __syscall(93, 20, 0, 0, 0, 0, 0)
37 }
38 // [2, 5): 3+4+5 = 12
39 if nx_st_range_sum(t, 2, 5) != 12 {
40 return __syscall(93, 21, 0, 0, 0, 0, 0)
41 }
42 // [0, 1): just element 1
43 if nx_st_range_sum(t, 0, 1) != 1 {
44 return __syscall(93, 22, 0, 0, 0, 0, 0)
45 }
46 // Empty range
47 if nx_st_range_sum(t, 5, 5) != 0 {
48 return __syscall(93, 23, 0, 0, 0, 0, 0)
49 }
50 // Out-of-range: returns 0.
51 if nx_st_range_sum(t, -1, 8) != 0 {
52 return __syscall(93, 24, 0, 0, 0, 0, 0)
53 }
54
55 // ---- range_min ----
56 // [3, 7): min of {4, 5, 6, 7} = 4
57 if nx_st_range_min(t, 3, 7) != 4 {
58 return __syscall(93, 30, 0, 0, 0, 0, 0)
59 }
60 // [0, 8): min = 1
61 if nx_st_range_min(t, 0, 8) != 1 {
62 return __syscall(93, 31, 0, 0, 0, 0, 0)
63 }
64 // Single element: min = that element
65 if nx_st_range_min(t, 3, 4) != 4 {
66 return __syscall(93, 32, 0, 0, 0, 0, 0)
67 }
68
69 // ---- range_max ----
70 // [0, 4): max of {1, 2, 3, 4} = 4
71 if nx_st_range_max(t, 0, 4) != 4 {
72 return __syscall(93, 40, 0, 0, 0, 0, 0)
73 }
74 // [0, 8): max = 8
75 if nx_st_range_max(t, 0, 8) != 8 {
76 return __syscall(93, 41, 0, 0, 0, 0, 0)
77 }
78 if nx_st_range_max(t, 5, 8) != 8 {
79 return __syscall(93, 42, 0, 0, 0, 0, 0)
80 }
81
82 // ---- update + re-query (mutation correctness) ----
83 nx_st_update(t, 3, 100) // change element 3 from 4 to 100
84 if nx_st_get(t, 3) != 100 {
85 return __syscall(93, 50, 0, 0, 0, 0, 0)
86 }
87 // Sum updated: 36 - 4 + 100 = 132
88 if nx_st_range_sum(t, 0, 8) != 132 {
89 return __syscall(93, 51, 0, 0, 0, 0, 0)
90 }
91 // Max in [0, 8) becomes 100.
92 if nx_st_range_max(t, 0, 8) != 100 {
93 return __syscall(93, 52, 0, 0, 0, 0, 0)
94 }
95 // Set element 3 to a smaller value -> min over [3,4)
96 nx_st_update(t, 3, -5)
97 if nx_st_range_min(t, 0, 8) != -5 {
98 return __syscall(93, 53, 0, 0, 0, 0, 0)
99 }
100
101 // ---- larger tree ----
102 let t2: *SegmentTree = nx_st_alloc(100)
103 var j: i64 = 0
104 while j < 100 {
105 nx_st_update(t2, j, j + 1)
106 j = j + 1
107 }
108 // Sum 1..100 = 5050
109 if nx_st_range_sum(t2, 0, 100) != 5050 {
110 return __syscall(93, 60, 0, 0, 0, 0, 0)
111 }
112 // Sum 25..75 = sum(26..75) = (26+75)*50/2 = 2525
113 if nx_st_range_sum(t2, 25, 75) != 2525 {
114 return __syscall(93, 61, 0, 0, 0, 0, 0)
115 }
116
117 // ---- typed envelope ----
118 let q: *ApproxI64 = nx_st_query_sum(t2, 0, 100)
119 if q.envelope_kind != NX_ENV_ABS {
120 return __syscall(93, 70, 0, 0, 0, 0, 0)
121 }
122 if q.param_a != 0 { // EXACT
123 return __syscall(93, 71, 0, 0, 0, 0, 0)
124 }
125 if q.value != 5050 {
126 return __syscall(93, 72, 0, 0, 0, 0, 0)
127 }
128 if q.maturity != NX_MATURITY_PRODUCTION {
129 return __syscall(93, 73, 0, 0, 0, 0, 0)
130 }
131
132 return 0
133}