radiance · Radiance self-hosting compiler

test/tests/prog.linkedlist.rad 5.9 KiB raw

//! returns: 0
//! Linked list via array pool.
//! Implement a singly-linked list using an array of node records
//! (pool allocator pattern). Operations: push, pop, find, reverse, length.

/// A node in the linked list.
record Node {
    value: i32,
    next: ?u32,
}

/// A linked list backed by a pool of pre-allocated nodes.
record List {
    pool: [Node; 64],
    free: u32,
    head: ?u32,
}

/// Allocate a node from the pool. Returns its index.
fn alloc(list: &mut List, value: i32) -> u32 {
    let idx = list.free;
    set list.free += 1;
    set list.pool[idx] = Node { value, next: nil };
    return idx;
}

/// Push a value onto the front of the list.
fn push(list: &mut List, value: i32) {
    let idx = alloc(list, value);
    set list.pool[idx].next = list.head;
    set list.head = idx;
}

/// Pop a value from the front of the list. Returns nil if empty.
fn pop(list: &mut List) -> ?i32 {
    let idx = list.head else {
        return nil;
    };
    let value = list.pool[idx].value;
    set list.head = list.pool[idx].next;
    return value;
}

/// Get the length of the list.
fn length(list: &List) -> u32 {
    let mut count: u32 = 0;
    let mut cur = list.head;
    while let idx = cur {
        set count += 1;
        set cur = list.pool[idx].next;
    }
    return count;
}

/// Find a value in the list. Returns the node index if found, or nil.
fn find(list: &List, value: i32) -> ?u32 {
    let mut cur = list.head;
    while let idx = cur {
        if list.pool[idx].value == value {
            return idx;
        }
        set cur = list.pool[idx].next;
    }
    return nil;
}

/// Get the value at a given index (0-based from head).
fn valueAt(list: &List, index: u32) -> ?i32 {
    let mut cur = list.head;
    let mut i: u32 = 0;
    while let idx = cur {
        if i == index {
            return list.pool[idx].value;
        }
        set cur = list.pool[idx].next;
        set i += 1;
    }
    return nil;
}

/// Reverse the linked list in-place.
fn reverse(list: &mut List) {
    let mut prev: ?u32 = nil;
    let mut cur = list.head;
    while let idx = cur {
        let next = list.pool[idx].next;
        set list.pool[idx].next = prev;
        set prev = idx;
        set cur = next;
    }
    set list.head = prev;
}

/// Compute the sum of all values in the list.
fn sum(list: &List) -> i32 {
    let mut total: i32 = 0;
    let mut cur = list.head;
    while let idx = cur {
        set total += list.pool[idx].value;
        set cur = list.pool[idx].next;
    }
    return total;
}

/// Reset the list to empty.
fn reset(list: &mut List) {
    set list.head = nil;
    set list.free = 0;
}

/// Test basic push and length.
fn testPushLength(list: &mut List) -> i32 {
    push(list, 10);
    push(list, 20);
    push(list, 30);

    assert length(list) == 3;
    // Head should be most recently pushed.
    let v0 = valueAt(list, 0) else {
        return 2;
    };
    assert v0 == 30;
    let v1 = valueAt(list, 1) else {
        return 3;
    };
    assert v1 == 20;
    let v2 = valueAt(list, 2) else {
        return 4;
    };
    assert v2 == 10;
    return 0;
}

/// Test pop.
fn testPop(list: &mut List) -> i32 {
    let v = pop(list) else {
        return 1;
    };
    assert v == 30;
    assert length(list) == 2;
    let v0 = valueAt(list, 0) else {
        return 3;
    };
    assert v0 == 20;
    return 0;
}

/// Test find.
fn testFind(list: &mut List) -> i32 {
    // 20 should be found.
    assert find(list, 20) <> nil;
    // 10 should be found.
    assert find(list, 10) <> nil;
    // 30 was popped, should not be found.
    assert find(list, 30) == nil;
    // 99 never inserted.
    assert find(list, 99) == nil;
    return 0;
}

/// Test reverse.
fn testReverse(list: &mut List) -> i32 {
    // Current list: 20 -> 10
    // Add more elements.
    push(list, 40);
    push(list, 50);
    // List: 50 -> 40 -> 20 -> 10

    let sumBefore = sum(list);

    reverse(list);
    // List should be: 10 -> 20 -> 40 -> 50

    assert length(list) == 4;

    let v0 = valueAt(list, 0) else {
        return 2;
    };
    assert v0 == 10;
    let v1 = valueAt(list, 1) else {
        return 3;
    };
    assert v1 == 20;
    let v2 = valueAt(list, 2) else {
        return 4;
    };
    assert v2 == 40;
    let v3 = valueAt(list, 3) else {
        return 5;
    };
    assert v3 == 50;

    assert sum(list) == sumBefore;
    return 0;
}

/// Test building a larger list.
fn testLargerList(list: &mut List) -> i32 {
    reset(list);

    // Push 32 elements.
    let mut i: u32 = 0;
    while i < 32 {
        push(list, i as i32 * 3);
        set i += 1;
    }

    assert length(list) == 32;

    // Sum should be 3 * (0 + 1 + ... + 31) = 3 * 496 = 1488
    assert sum(list) == 1488;

    // Reverse and verify sum is preserved.
    reverse(list);
    assert sum(list) == 1488;

    // After reverse, head should be 0 (first pushed), tail should be 93 (last pushed).
    let head = valueAt(list, 0) else {
        return 4;
    };
    assert head == 0;
    let tail = valueAt(list, 31) else {
        return 5;
    };
    assert tail == 93;

    // Pop all and verify decreasing original order.
    let mut j: u32 = 0;
    while j < 32 {
        let v = pop(list) else {
            return 6;
        };
        let expected = j as i32 * 3;
        assert v == expected;
        set j += 1;
    }

    assert length(list) == 0;

    // Pop from empty list should return nil.
    assert pop(list) == nil;
    return 0;
}

@default fn main() -> i32 {
    let mut list: List = List {
        pool: [Node { value: 0, next: nil }; 64],
        free: 0,
        head: nil,
    };

    let r1 = testPushLength(&mut list);
    if r1 <> 0 {
        return 10 + r1;
    }

    let r2 = testPop(&mut list);
    if r2 <> 0 {
        return 20 + r2;
    }

    let r3 = testFind(&mut list);
    if r3 <> 0 {
        return 30 + r3;
    }

    let r4 = testReverse(&mut list);
    if r4 <> 0 {
        return 40 + r4;
    }

    let r5 = testLargerList(&mut list);
    if r5 <> 0 {
        return 50 + r5;
    }
    return 0;
}

1	//! returns: 0
2	//! Linked list via array pool.
3	//! Implement a singly-linked list using an array of node records
4	//! (pool allocator pattern). Operations: push, pop, find, reverse, length.
5
6	/// A node in the linked list.
7	record Node {
8	value: i32,
9	next: ?u32,
10	}
11
12	/// A linked list backed by a pool of pre-allocated nodes.
13	record List {
14	pool: [Node; 64],
15	free: u32,
16	head: ?u32,
17	}
18
19	/// Allocate a node from the pool. Returns its index.
20	fn alloc(list: &mut List, value: i32) -> u32 {
21	let idx = list.free;
22	set list.free += 1;
23	set list.pool[idx] = Node { value, next: nil };
24	return idx;
25	}
26
27	/// Push a value onto the front of the list.
28	fn push(list: &mut List, value: i32) {
29	let idx = alloc(list, value);
30	set list.pool[idx].next = list.head;
31	set list.head = idx;
32	}
33
34	/// Pop a value from the front of the list. Returns nil if empty.
35	fn pop(list: &mut List) -> ?i32 {
36	let idx = list.head else {
37	return nil;
38	};
39	let value = list.pool[idx].value;
40	set list.head = list.pool[idx].next;
41	return value;
42	}
43
44	/// Get the length of the list.
45	fn length(list: &List) -> u32 {
46	let mut count: u32 = 0;
47	let mut cur = list.head;
48	while let idx = cur {
49	set count += 1;
50	set cur = list.pool[idx].next;
51	}
52	return count;
53	}
54
55	/// Find a value in the list. Returns the node index if found, or nil.
56	fn find(list: &List, value: i32) -> ?u32 {
57	let mut cur = list.head;
58	while let idx = cur {
59	if list.pool[idx].value == value {
60	return idx;
61	}
62	set cur = list.pool[idx].next;
63	}
64	return nil;
65	}
66
67	/// Get the value at a given index (0-based from head).
68	fn valueAt(list: &List, index: u32) -> ?i32 {
69	let mut cur = list.head;
70	let mut i: u32 = 0;
71	while let idx = cur {
72	if i == index {
73	return list.pool[idx].value;
74	}
75	set cur = list.pool[idx].next;
76	set i += 1;
77	}
78	return nil;
79	}
80
81	/// Reverse the linked list in-place.
82	fn reverse(list: &mut List) {
83	let mut prev: ?u32 = nil;
84	let mut cur = list.head;
85	while let idx = cur {
86	let next = list.pool[idx].next;
87	set list.pool[idx].next = prev;
88	set prev = idx;
89	set cur = next;
90	}
91	set list.head = prev;
92	}
93
94	/// Compute the sum of all values in the list.
95	fn sum(list: &List) -> i32 {
96	let mut total: i32 = 0;
97	let mut cur = list.head;
98	while let idx = cur {
99	set total += list.pool[idx].value;
100	set cur = list.pool[idx].next;
101	}
102	return total;
103	}
104
105	/// Reset the list to empty.
106	fn reset(list: &mut List) {
107	set list.head = nil;
108	set list.free = 0;
109	}
110
111	/// Test basic push and length.
112	fn testPushLength(list: &mut List) -> i32 {
113	push(list, 10);
114	push(list, 20);
115	push(list, 30);
116
117	assert length(list) == 3;
118	// Head should be most recently pushed.
119	let v0 = valueAt(list, 0) else {
120	return 2;
121	};
122	assert v0 == 30;
123	let v1 = valueAt(list, 1) else {
124	return 3;
125	};
126	assert v1 == 20;
127	let v2 = valueAt(list, 2) else {
128	return 4;
129	};
130	assert v2 == 10;
131	return 0;
132	}
133
134	/// Test pop.
135	fn testPop(list: &mut List) -> i32 {
136	let v = pop(list) else {
137	return 1;
138	};
139	assert v == 30;
140	assert length(list) == 2;
141	let v0 = valueAt(list, 0) else {
142	return 3;
143	};
144	assert v0 == 20;
145	return 0;
146	}
147
148	/// Test find.
149	fn testFind(list: &mut List) -> i32 {
150	// 20 should be found.
151	assert find(list, 20) <> nil;
152	// 10 should be found.
153	assert find(list, 10) <> nil;
154	// 30 was popped, should not be found.
155	assert find(list, 30) == nil;
156	// 99 never inserted.
157	assert find(list, 99) == nil;
158	return 0;
159	}
160
161	/// Test reverse.
162	fn testReverse(list: &mut List) -> i32 {
163	// Current list: 20 -> 10
164	// Add more elements.
165	push(list, 40);
166	push(list, 50);
167	// List: 50 -> 40 -> 20 -> 10
168
169	let sumBefore = sum(list);
170
171	reverse(list);
172	// List should be: 10 -> 20 -> 40 -> 50
173
174	assert length(list) == 4;
175
176	let v0 = valueAt(list, 0) else {
177	return 2;
178	};
179	assert v0 == 10;
180	let v1 = valueAt(list, 1) else {
181	return 3;
182	};
183	assert v1 == 20;
184	let v2 = valueAt(list, 2) else {
185	return 4;
186	};
187	assert v2 == 40;
188	let v3 = valueAt(list, 3) else {
189	return 5;
190	};
191	assert v3 == 50;
192
193	assert sum(list) == sumBefore;
194	return 0;
195	}
196
197	/// Test building a larger list.
198	fn testLargerList(list: &mut List) -> i32 {
199	reset(list);
200
201	// Push 32 elements.
202	let mut i: u32 = 0;
203	while i < 32 {
204	push(list, i as i32 * 3);
205	set i += 1;
206	}
207
208	assert length(list) == 32;
209
210	// Sum should be 3 * (0 + 1 + ... + 31) = 3 * 496 = 1488
211	assert sum(list) == 1488;
212
213	// Reverse and verify sum is preserved.
214	reverse(list);
215	assert sum(list) == 1488;
216
217	// After reverse, head should be 0 (first pushed), tail should be 93 (last pushed).
218	let head = valueAt(list, 0) else {
219	return 4;
220	};
221	assert head == 0;
222	let tail = valueAt(list, 31) else {
223	return 5;
224	};
225	assert tail == 93;
226
227	// Pop all and verify decreasing original order.
228	let mut j: u32 = 0;
229	while j < 32 {
230	let v = pop(list) else {
231	return 6;
232	};
233	let expected = j as i32 * 3;
234	assert v == expected;
235	set j += 1;
236	}
237
238	assert length(list) == 0;
239
240	// Pop from empty list should return nil.
241	assert pop(list) == nil;
242	return 0;
243	}
244
245	@default fn main() -> i32 {
246	let mut list: List = List {
247	pool: [Node { value: 0, next: nil }; 64],
248	free: 0,
249	head: nil,
250	};
251
252	let r1 = testPushLength(&mut list);
253	if r1 <> 0 {
254	return 10 + r1;
255	}
256
257	let r2 = testPop(&mut list);
258	if r2 <> 0 {
259	return 20 + r2;
260	}
261
262	let r3 = testFind(&mut list);
263	if r3 <> 0 {
264	return 30 + r3;
265	}
266
267	let r4 = testReverse(&mut list);
268	if r4 <> 0 {
269	return 40 + r4;
270	}
271
272	let r5 = testLargerList(&mut list);
273	if r5 <> 0 {
274	return 50 + r5;
275	}
276	return 0;
277	}