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

[Dave Abrahams]

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