add slices utilsHEADmain

2 files changed, 116 insertions, 0 deletions

diff --git a/lettuce/slices/README b/lettuce/slices/README
new file mode 100644
index 0000000..79c7e5a
--- /dev/null
+++ b/lettuce/slices/README
@@ -0,0 +1,5 @@
+slices: extended slice operations
+
+Note that the functions in this module are only tested to work on the official
+Hare implementation, use on other implementations at your own risk. At a minimum
+they need the [[rt::]] module to be available.
diff --git a/lettuce/slices/functional.ha b/lettuce/slices/functional.ha
new file mode 100644
index 0000000..5981961
--- /dev/null
+++ b/lettuce/slices/functional.ha
@@ -0,0 +1,111 @@
+use rt;
+
+// A function used to evaluate whether an item should remain included in a slice
+// or if it should be removed. Given a pointer to the item, it should return
+// `true` to keep it or `false` to remove it.
+export type fltfunc = fn(item: *opaque) bool;
+
+// Delete an item from a slice of unknown secondary type by passing the width of
+// each item instead. (Acts most similar to a "static delete", i.e. does not
+// realloc the slice's memory.)
+export fn delete_opaque(slice: *[]opaque, itemsz: size, index: size) void = {
+	// see hare specification §6.7.30
+	const raw = slice: *rt::slice;
+	assert(!(raw.data is null), "tried to delete from empty slice");
+	const data = raw.data: *[*]u8;
+	assert(index < raw.length && index >= 0,
+		"deletion index out of bounds");
+	const dest = &data[index * itemsz];
+	const src = &data[(index + 1) * itemsz];
+	const n = itemsz * (raw.length - index - 1);
+	if (n > 0) rt::memmove(dest, src, n);
+	raw.length -= 1;
+};
+
+@test fn delete_opaque() void = {
+	const slice: []int = alloc([1, 2, 3, 4, 5])!;
+	defer free(slice);
+	delete_opaque(&slice: *[]opaque, size(int), 2);
+	assert(len(slice) == 4);
+	assert(slice[0] == 1 && slice[1] == 2 &&
+		slice[2] == 4 && slice[3] == 5);
+};
+
+// Append an item to a slice of unknown secondary type by passing the width of
+// each item instead. (Acts most similar to a "static append", i.e. does not
+// allocate more memory as necessary; therefore please ensure that the slice has
+// a big enough capacity to accomodate the new item before calling.)
+export fn append_opaque(slice: *[]opaque, itemsz: size, item: *opaque) void = {
+	const raw = slice: *rt::slice;
+	assert(!(raw.data is null), "can't append to a slice with no storage");
+	assert(raw.capacity >= raw.length + 1, "no space for new item");
+	const data = raw.data: *[*]u8;
+	const dest = &data[raw.length * itemsz];
+	rt::memcpy(dest, item, itemsz);
+	raw.length += 1;
+};
+
+@test fn append_opaque() void = {
+	const slice: []int = alloc([1, 2, 3, 9])!;
+	defer free(slice);
+	static delete(slice[3]);
+	assert(len(slice) == 3);
+	append_opaque(&slice: *[]opaque, size(int), &4);
+	assert(len(slice) == 4);
+	assert(slice[0] == 1 && slice[1] == 2 &&
+		slice[2] == 3 && slice[3] == 4);
+};
+
+// Filter a slice in-place according to the given filter function. Note that
+// this does not free any of the items it removes; if you need that, please use
+// [[afilter]] instead and do it manually afterwards.
+export fn ifilter(slice: *[]opaque, itemsz: size, flt: *fltfunc) void = {
+	const raw = slice: *rt::slice;
+	if (raw.data is null) return;
+	const data = raw.data: *[*]u8;
+	for (let i = 0z; i < raw.length; i += 1) {
+		const item = &data[i * itemsz];
+		if (!flt(item)) {
+			delete_opaque(slice, itemsz, i);
+			i -= 1;
+		};
+	};
+	rt::unensure(raw, itemsz);
+};
+
+fn fltfunc_lessthanten(item: *opaque) bool = {
+	return *(item: *int) < 10;
+};
+
+@test fn ifilter() void = {
+	const slice: []int = alloc([1, 4, 19, 9, 50, 3])!;
+	defer free(slice);
+	ifilter(&slice: *[]opaque, size(int), &fltfunc_lessthanten);
+	assert(len(slice) == 4);
+	assert(slice[0] == 1 && slice[1] == 4 &&
+		slice[2] == 9 && slice[3] == 3);
+};
+
+// Filter a slice into a new, freshly allocated slice and return it. The
+// returned slice must be freed by the caller.
+export fn afilter(slice: *[]opaque, itemsz: size, flt: *fltfunc)
+		([]opaque | nomem) = {
+	const raw = slice: *rt::slice;
+	if (raw.data is null) return []: []u8;
+	const data = raw.data: *[*]u8;
+	const result: []u8 = alloc([], itemsz * raw.length)?;
+	for (let i = 0z; i < raw.length; i += 1) {
+		const item = &data[i * itemsz];
+		if (flt(item)) append_opaque(&result: *[]opaque, itemsz, item);
+	};
+	return result;
+};
+
+@test fn afilter() void = {
+	const in: []int = [1, 2, 100, 7];
+	const out = afilter(&in: *[]opaque, size(int),
+		&fltfunc_lessthanten)!: []int;
+	defer free(out);
+	assert(len(out) == 3);
+	assert(out[0] == 1 && out[1] == 2 && out[2] == 7);
+};