[swift-evolution] [Proposal] Add Array binary search to the standard library
dabrahams at apple.com
Sun Jan 29 18:21:22 CST 2017
Thanks for diving in here! For reference, here's the last thing I said
about this topic (IIRC):
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:
> 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,
> swift-evolution mailing list
> swift-evolution at swift.org
More information about the swift-evolution