On Tuesday, 15 November 2022 at 23:27:07 UTC, Siarhei Siamashka wrote:
>For doing a fast insert into an already sorted array (and avoiding duplicated values) it's probably better to do something like this:
bool fast_insert_into_a_sorted_array(alias less = "a < b", T)(ref T[] a, T value)
{
auto pos = a.assumeSorted!(less).lowerBound(value).length;
if (pos < a.length && a[pos] == value)
return false; // indicate no insert
a.insertInPlace(pos, value);
return true; // indicate insert
}
Actually the comparison needs to be done using the provided predicate too:
bool fast_insert_in_a_sorted_array(alias less = "a < b", T)(ref T[] a, T value)
{
auto pos = a.assumeSorted!(less).lowerBound(value).length;
while (pos < a.length && !binaryFun!less(a[pos], value) &&
!binaryFun!less(value, a[pos])) {
if (a[pos++] == value)
return false; // indicate no insert
}
a.insertInPlace(pos, value);
return true; // indicate insert
}
unittest {
auto less = function bool(ref Tuple!(int, int) a,
ref Tuple!(int, int) b) { return a[0] < b[0]; };
auto a = [tuple(0, 1), tuple(0, 2)];
a.sort!less;
assert(a.fast_insert_in_a_sorted_array!less(tuple(0, 2)) == false);
assert(a == [tuple(0, 1), tuple(0, 2)]);
assert(a.fast_insert_in_a_sorted_array!less(tuple(0, 3)) == true);
assert(a == [tuple(0, 1), tuple(0, 2), tuple(0, 3)]);
assert(a.fast_insert_in_a_sorted_array!less(tuple(-1, 0)) == true);
assert(a == [tuple(-1, 0), tuple(0, 1), tuple(0, 2), tuple(0, 3)]);
}