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

[Alexey Komnin]

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?

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