commit e6cab9bc88bdc902fc43a3526bd8bc8d2e39e442
parent f65b9680cd17e14119bf7cb7d2e11c694a6bfb69
Author: Sebastian <sebastian@sebsite.pw>
Date: Sat, 2 Apr 2022 00:05:25 -0400
sort: add bisect functions
Signed-off-by: Sebastian <sebastian@sebsite.pw>
Diffstat:
4 files changed, 102 insertions(+), 0 deletions(-)
diff --git a/scripts/gen-stdlib b/scripts/gen-stdlib
@@ -1066,6 +1066,7 @@ slices() {
gensrcs_sort() {
gen_srcs sort \
+ bisect.ha \
search.ha \
sort.ha \
types.ha \
diff --git a/sort/+test.ha b/sort/+test.ha
@@ -2,6 +2,40 @@
// (c) 2021 Drew DeVault <sir@cmpwn.com>
// (c) 2021 Eyal Sawady <ecs@d2evs.net>
+@test fn lbisect() void = {
+ const nums = [1, 3, 4, 4, 5, 7, 9, 11, 11, 11];
+ for (let i = 0z; i < len(nums); i += 1) {
+ if (i != 0 && nums[i - 1] == nums[i]) continue;
+ const key = nums[i];
+ assert(lbisect(nums, size(int), &key, &icmp) == i);
+ };
+ const n = 0;
+ assert(lbisect(nums, size(int), &n, &icmp) == 0);
+ const n = 6;
+ assert(lbisect(nums, size(int), &n, &icmp) == 5);
+ const n = 8;
+ assert(lbisect(nums, size(int), &n, &icmp) == 6);
+ const n = 12;
+ assert(lbisect(nums, size(int), &n, &icmp) == len(nums));
+};
+
+@test fn rbisect() void = {
+ const nums = [1, 3, 4, 4, 5, 7, 9, 11, 11, 11];
+ for (let i = 0z; i < len(nums); i += 1) {
+ if (i != len(nums) - 1 && nums[i + 1] == nums[i]) continue;
+ const key = nums[i];
+ assert(rbisect(nums, size(int), &key, &icmp) == i + 1);
+ };
+ const n = 0;
+ assert(rbisect(nums, size(int), &n, &icmp) == 0);
+ const n = 6;
+ assert(rbisect(nums, size(int), &n, &icmp) == 5);
+ const n = 8;
+ assert(rbisect(nums, size(int), &n, &icmp) == 6);
+ const n = 12;
+ assert(rbisect(nums, size(int), &n, &icmp) == len(nums));
+};
+
@test fn search() void = {
const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
for (let i = 0z; i < len(nums); i += 1) {
diff --git a/sort/bisect.ha b/sort/bisect.ha
@@ -0,0 +1,65 @@
+// License: MPL-2.0
+// (c) 2022 Sebastian <sebastian@sebsite.pw>
+
+// Determines the index that 'elem' should be inserted into sorted slice 'in'.
+// If 'elem' already appears in the slice, inserting to the returned index will
+// insert immediately before the first occurance.
+export fn lbisect(
+ in: []const void,
+ sz: size,
+ elem: const *void,
+ cmp: *cmpfunc,
+) size = {
+ let min = 0z, max = len(in);
+ const in = in: *[*]u8;
+ for (min < max) {
+ let i = (max - min) / 2 + min;
+ const r = cmp(elem, &in[i * sz]);
+ if (r < 0) {
+ max = i;
+ } else if (r > 0) {
+ min = i + 1;
+ } else {
+ if (i == 0) return 0;
+ for (i > 0; i -= 1) {
+ if (cmp(elem, &in[(i - 1) * sz]) != 0) {
+ break;
+ };
+ };
+ return i;
+ };
+ };
+ return max;
+};
+
+// Determines the index that 'elem' should be inserted into sorted slice 'in'.
+// If 'elem' already appears in the slice, inserting to the returned index will
+// insert immediately after the last occurance.
+export fn rbisect(
+ in: []const void,
+ sz: size,
+ elem: const *void,
+ cmp: *cmpfunc,
+) size = {
+ const nmemb = len(in);
+ let min = 0z, max = nmemb;
+ const in = in: *[*]u8;
+ for (min < max) {
+ let i = (max - min) / 2 + min;
+ const r = cmp(elem, &in[i * sz]);
+ if (r < 0) {
+ max = i;
+ } else if (r > 0) {
+ min = i + 1;
+ } else {
+ i += 1;
+ for (i < nmemb; i += 1) {
+ if (cmp(elem, &in[i * sz]) != 0) {
+ break;
+ };
+ };
+ return i;
+ };
+ };
+ return max;
+};
diff --git a/stdlib.mk b/stdlib.mk
@@ -1636,6 +1636,7 @@ $(HARECACHE)/slices/slices-any.ssa: $(stdlib_slices_any_srcs) $(stdlib_rt) $(std
# sort (+any)
stdlib_sort_any_srcs= \
+ $(STDLIB)/sort/bisect.ha \
$(STDLIB)/sort/search.ha \
$(STDLIB)/sort/sort.ha \
$(STDLIB)/sort/types.ha
@@ -3557,6 +3558,7 @@ $(TESTCACHE)/slices/slices-any.ssa: $(testlib_slices_any_srcs) $(testlib_rt) $(t
# sort (+any)
testlib_sort_any_srcs= \
+ $(STDLIB)/sort/bisect.ha \
$(STDLIB)/sort/search.ha \
$(STDLIB)/sort/sort.ha \
$(STDLIB)/sort/types.ha \
