// sort — operations on sorted slices: binary search + insertion-point
// bisection. Faithful port of Hare's sort::{search,lbisect,rbisect} and
// the cmpfunc type (ref/hare/sort/{search,bisect,types}.ha). The
// powersort sort()/insort()/shuffle() surface is out of scope here.
//
// Hare splits this across types.ha/search.ha/bisect.ha; ww merges a
// module into one file (same convention as lib/types/types.ww merging
// Hare's limits.ha + arch+x86_64.ha). test/wcc/963_sort_run.c compiles
// and executes this sole-source package directly.
//
// Divergences from the Hare source, all forced by ww's surface (not
// behavioural — rule-10 align-down):
//   • cmp is a fn-VALUE param (`cmp: cmpfunc`), not Hare's pointer
//     (`cmp: *cmpfunc`). ww renders functions-in-an-interface by value
//     exactly as lib/io.ww's stream vtable does (`read: fn(...)`); the
//     `*cmpfunc` pointer form is not callable (no fn-ptr auto-deref) and
//     `&fn` is `*fn(...)`, not assignable to the named alias `*cmpfunc`.
//   • no `const` qualifier (ww has none; lib/io.ww drops it likewise).
//   • Hare walks bytes through `in: *[*]u8` + `&ba[i*sz]`; ww has no
//     unbounded-array `[*]`, so the base is `*u8` reinterpreted to
//     `uintptr` and elements are `base + i*sz` (the stride idiom proven
//     by test/lang/opaque_assign_cast_test.ww).
//   • `len()` yields i32 in ww (slice length is i32 today), so the
//     count is cast `: size`; Hare's len() is already size.
//   • ww `for` is single-condition only (no `for (init; cond; post)`),
//     so Hare's `for (cond; afterthought)` becomes a body-tail step.

package sort;

// ref/hare/sort/types.ha:11 — comparator: <0 / 0 / >0 for a < / == / > b.
export type cmpfunc = fn(a: *opaque, b: *opaque) int;

// ref/hare/sort/search.ha:6-27 — binary search; element index, or void.
export fn search(in: []opaque, sz: size, key: *opaque, cmp: cmpfunc) (size | void) = {
	let base: uintptr = (in: *u8): uintptr;
	let nmemb: size = len(in): size;
	for (nmemb > 0) {
		let v: *opaque = (base + (nmemb / 2 * sz): uintptr): *opaque;
		let r: int = cmp(key, v);
		if (r < 0) {
			nmemb = nmemb / 2;
		} else if (r > 0) {
			base = (v: uintptr) + (sz: uintptr);
			nmemb = nmemb - (nmemb / 2 + 1);
		} else {
			let offs: uintptr = (v: uintptr) - ((in: *u8): uintptr);
			return (offs / (sz: uintptr)): size;
		};
	};
	return void;
};

// ref/hare/sort/bisect.ha:7-33 — insertion index before the first
// occurrence of an equal element.
export fn lbisect(in: []opaque, sz: size, elem: *opaque, cmp: cmpfunc) size = {
	let min: size = 0;
	let max: size = len(in): size;
	let base: uintptr = (in: *u8): uintptr;
	for (min < max) {
		let i: size = (max - min) / 2 + min;
		let v: *opaque = (base + (i * sz): uintptr): *opaque;
		let r: int = cmp(elem, v);
		if (r < 0) {
			max = i;
		} else if (r > 0) {
			min = i + 1;
		} else {
			if (i == 0) { return 0; };
			for (i > 0) {
				let vp: *opaque = (base + ((i - 1) * sz): uintptr): *opaque;
				let rr: int = cmp(elem, vp);
				if (rr != 0) { break; };
				i = i - 1;
			};
			return i;
		};
	};
	return max;
};

// ref/hare/sort/bisect.ha:38-65 — insertion index after the last
// occurrence of an equal element.
export fn rbisect(in: []opaque, sz: size, elem: *opaque, cmp: cmpfunc) size = {
	let nmemb: size = len(in): size;
	let min: size = 0;
	let max: size = nmemb;
	let base: uintptr = (in: *u8): uintptr;
	for (min < max) {
		let i: size = (max - min) / 2 + min;
		let v: *opaque = (base + (i * sz): uintptr): *opaque;
		let r: int = cmp(elem, v);
		if (r < 0) {
			max = i;
		} else if (r > 0) {
			min = i + 1;
		} else {
			i = i + 1;
			for (i < nmemb) {
				let vp: *opaque = (base + (i * sz): uintptr): *opaque;
				let rr: int = cmp(elem, vp);
				if (rr != 0) { break; };
				i = i + 1;
			};
			return i;
		};
	};
	return max;
};