| 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 |
}; |