1896166 - Consider adding set-style sorted insertion methods to nsTArray

Status: NEW

(Core :: XPCOM, enhancement)

Description

[Nika Layzell [:nika] (ni? for response)]

Occasionally it is useful to use a sorted nsTArray as a set type, inserting new items and removing them using a binary search over the collection. This is fairly easy to do with the existing RemoveElementSorted and ContainsSorted methods, however the InsertElementSorted method will insert a second copy of the element if the entry already exists in the array.

It may be worthwhile to add a new EnsureInsertedSorted method (name tbd) which inserts a new entry into a sorted nsTArray iff the element is not already present in the array. It would probably have an "internal" variant which looks something like this (based on InsertElementSortedInternal, and untested):

  template <typename ActualAlloc, class Item, class Comparator>
  value_type* EnsureInsertedSorted(Item&& aItem, const Comparator& aComp, bool* aExisting = nullptr) {
    using mozilla::BinarySearchIf;
    ::detail::CompareWrapper<Comparator, Item> comp(aComp);

    size_t index;
    bool found = BinarySearchIf(
        Elements(), 0, Length(),
        // See `BinaryIndexOf` for why we pass Compare() args in reverse and
        // negate the results.
        [&](const value_type& aElement) {
          return -comp.Compare(aElement, aItem);
        },
        &index);

    if (aExisting) {
      *aExisting = found;
    }

    return found
        ? &ElementAt(index)
        : InsertElementAtInternal<ActualAlloc>(index, std::forward<Item>(aItem));
  }

This can be implemented externally using IndexOfFirstElementGt, and checking the index before the located index for equality, such as how it was handled in ManagedContainer (https://searchfox.org/mozilla-central/rev/8e885f04a0a4ff6d64ea59741c10d9b8e45d9ff8/ipc/glue/ProtocolUtils.h#767-772).