[swift-evolution] [Proposal] Add Array binary search to the standard library

[Dave Abrahams]

on Mon Jan 30 2017, Nate Cook <natecook-AT-gmail.com> wrote:

>> On Jan 30, 2017, at 2:47 AM, Alexey Komnin via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> Hello to everyone.
>> 
>> Let me put my two cents.
>
>> 
>>>> I didn’t want the SortedArray to conform to MutableCollection or
>>>> even RandomAccessCollection as I felt it was not needed just to
>>>> support binary search and prevent re-sorting.
>>> 
>>> You are right not to support MutableCollection or
>>> RangeReplaceableCollection, as those would allow you to violate the
>>> “sorted” invariant.  However, it should conform to
>>> RandomAccessCollection; that's really easy to implement and would
>>> improve ease-of-use a lot.
>> 
>> Are we able to add some kind of type constraint which allows
>> append/prepend operations on a particular collection? Seems like a
>> good replacement for MutableCollection in this case. It should be
>> available to append elements greater or equal to the last element in
>> SortedArray, isn't it?
>
> I've been playing around with a protocol-based approach to these
> questions. A mutable sorted collection can easily allow operations
> that maintain the collection's order (basically just insertion with
> the collection deciding where to put the element or elements and
> removal of one or more elements). I suppose it's possible to allow
> appending / prepending if we require that the elements be (a) sorted
> and (b) wouldn't change the sort of the collection.

This would require (well, should use) a protocol that would be refined
by RangeReplaceableCollection, which means it needs to happen in before ABI
stability sets in.

> You can see my current version here:
> https://gist.github.com/natecook1000/9400edd75947fcf41dd4c82d1519dea8
> — it defines two protocols along with a mutable SortedArray and an
> immutable SortedView.

Cool; looking forward to the full proposal! ;-)


-- 
-Dave