November 16, 2022

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)]);
}
1 2
Next ›   Last »