[swift-evolution] [Discussion] Binary search, lower bound, upper bound, equal range

Jeff Hajewski jeff.hajewski at gmail.com
Mon Feb 15 19:52:00 CST 2016


Thanks Daniel - comments regarding Array vs CollectionType are duly noted. Stable sort is next on my list unless someone else tackles it before I finish this work. I suppose I’ll be adding isPartitioned as well at some point.

Thanks again for the comments
Jeff

> On Feb 15, 2016, at 5:45 PM, Daniel Vollmer via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
>> On 15 Feb 2016, at 21:35, Jeff Hajewski via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> Hello,
>> 
>> Description
>> Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.
>> 
>> Initial Proposal
>> I propose adding four methods for generic Array and adding four methods for Arrays that conform to Comparable:
> 
> Over the weekend, I looked at what I would require for porting a simple kd-tree from C++ to Swift, and other than stable sort I was also lacking equal_range. But I think that defining the interface for these methods on Array would be a mistake: One thing the STL got very right is that the caller gets to pick the iterators (ranges) for the algorithm. For the kd-tree, I would want to stable_sort and apply equal_range to recursively smaller segments (slices?) of an Array, and not always the complete one.
> 
> 	Daniel.
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160215/6e498e2f/attachment.html>


More information about the swift-evolution mailing list