Debian Codegraph @

sort/bisect.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // Determines the index that 'elem' should be inserted into sorted slice 'in'.
5 // If 'elem' already appears in the slice, inserting to the returned index will
6 // insert immediately before the first occurance.
7 export fn lbisect(
8 in: []const opaque,
9 sz: size,
10 elem: const *opaque,
11 cmp: *cmpfunc,
12 ) size = {
13 let min = 0z, max = len(in);
14 const in = in: *[*]u8;
15 for (min < max) {
16 let i = (max - min) / 2 + min;
17 const r = cmp(elem, &in[i * sz]);
18 if (r < 0) {
19 max = i;
20 } else if (r > 0) {
21 min = i + 1;
22 } else {
23 if (i == 0) return 0;
24 for (i > 0; i -= 1) {
25 if (cmp(elem, &in[(i - 1) * sz]) != 0) {
26 break;
27 };
28 };
29 return i;
30 };
31 };
32 return max;
33 };
34
35 // Determines the index that 'elem' should be inserted into sorted slice 'in'.
36 // If 'elem' already appears in the slice, inserting to the returned index will
37 // insert immediately after the last occurance.
38 export fn rbisect(
39 in: []const opaque,
40 sz: size,
41 elem: const *opaque,
42 cmp: *cmpfunc,
43 ) size = {
44 const nmemb = len(in);
45 let min = 0z, max = nmemb;
46 const in = in: *[*]u8;
47 for (min < max) {
48 let i = (max - min) / 2 + min;
49 const r = cmp(elem, &in[i * sz]);
50 if (r < 0) {
51 max = i;
52 } else if (r > 0) {
53 min = i + 1;
54 } else {
55 i += 1;
56 for (i < nmemb; i += 1) {
57 if (cmp(elem, &in[i * sz]) != 0) {
58 break;
59 };
60 };
61 return i;
62 };
63 };
64 return max;
65 };