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

[Dave Abrahams]

on Mon Jan 30 2017, Alexey Komnin <interfere.work-AT-gmail.com> 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 think we should handle that with a method like this

  /// Inserts `x` in the correct position, using `positionHint`
  /// to improve performance if it is accurate.
  func insert(_ x: Element, positionHint: Index) -> Index

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

-- 
-Dave