Sorted Array (Container) Type

[Siarhei Siamashka]

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:
>
> ```D
> 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:

```D
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)]);
}
```