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

[Nate Cook]

> 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.

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.

-Nate


> Regards,
> Alex Komnin.
> 
> 
> 
> On Mon, Jan 30, 2017 at 3:21 AM, Dave Abrahams via swift-evolution
> <swift-evolution at swift.org> wrote:
>> 
>> Hi Cihat,
>> 
>> Thanks for diving in here!  For reference, here's the last thing I said
>> about this topic (IIRC):
>> 
>> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html
>> 
>> Also
>> https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679
>> 
>> Note: the comment there isn't quite right: <https://github.com/apple/swift/pull/7135>
>> 
>> on Sun Jan 29 2017, Cihat Gündüz <swift-evolution at swift.org> wrote:
>> 
>>> Hi guys, I know this topic is probably out of scope for Swift 4
>>> and a proposal was already rejected for Swift 3, but I’d like to share
>>> my two cents on this as I just wrote a SortedArray class with support
>>> for binary search in my open source library HandySwift.
>>> 
>>> You can see my classes current implementation here:
>>> https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift
>>> 
>>> My goal was to provide only what is commonly needed when working with
>>> big arrays in algorithms. For me this included:
>>> 
>>> - having a type that keeps a sorted array to prevent re-sorting (solution: the SortedArray class)
>> 
>> Sounds consistent with my feedback... but it doesn't conform to
>> RandomAccessCollection.  Why not?
>> 
>>> - have a method that can find an object using binary search (solution: the index method)
>> 
>> Please see the algorithms prototype
>> 
>>> - allow partitioning the array into smaller parts (solution: subscript, prefix & suffix methods)
>> 
>> * The collection returned by the slicing subscript should obey the law
>> 
>>     a[i..<j][i] == a[i]
>> 
>>  Normally that means you want to make it a different type from a.
>> 
>>> - prevent re-implementing the Array class (solution: a getter to the
>>>  stored internal array)
>> 
>> Not sure I understand what this is supposed to mean.
>> 
>>> Also note that the SortedArray in my approach allows all types that
>>> conform to `Sequence` as input with `Comparable` elements and saves
>>> them into a sorted array on initialization. That array is also
>>> publicly read-accessible. Inserting and deleting objects from the
>>> SortedArray are possible, too, but that’s just few of the
>>> MutableCollection methods.
>> 
>> Actually no, those are RangeReplaceableCollection methods.
>> 
>>> 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.
>> 
>> 
>>> Maybe my approach can somehow help forming the final solution to be
>>> included into Swift once this features is tackled again.
>>> 
>>> Best regards,
>>> Cihat
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>> 
>> 
>> --
>> -Dave
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution