bisect.ha (1455B)
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 };