[swift-evolution] (Draft) Add last(where:) and lastIndex(where:) methods

[Nate Cook]

> On May 20, 2016, at 10:34 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> on Thu May 19 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:
> 
>>> Why shouldn't this work with all Collections, with an optimized version
>>> for BidirectionalCollections?

This sounds fine to me. I think I got hung up on 'last' only being available on BidirectionalCollections, but since that's a property it needs to provide O(1) access and is therefore not a good reference point. (I think 'removeLast' might be the only method that starts with BidirectionalCollections.)

>> Why don't we have `index(before:)` on non-BidirectionalCollections? It's not that you can't write it:
>> 
>>    func index(before index: Index) -> Index {
>>        let offset = distance(from: startIndex, to: index)
>>        return index(startIndex, offsetBy: offset - 1)
>>    }
>> 
>> We don't do that because it would be so slow as to form an attractive
>> nuisance.
> 
> It's O(N) worst case no matter what you do.
> 
>> Similarly, we shouldn't provide operations which are going to
>> repeatedly seek elements near the tail of the list unless we're using
>> a type which can access that tail efficiently. `last` is one
>> thing—it's only O(N). `lastIndex(of:)` is, I believe, O(n log n) in
>> the case of an element that doesn't exist.
> 
> I can't imagine where your O(N log N) comes from in this case, but even
> if it is the right complexity that wouldn't be a reason not to provide
> the operation.  I learned last week there's an O(N log N) in-place
> reverse() for ForwardCollections, and I think we ought to have it.  log
> N is effectively a constant for most purposes.

That sounds interesting! The 'rotate' proposal, which includes in-place reversal methods, has technically not completed review. Should we amend that to make in-place reversal available for any MutableCollection?

>>> I think we need to consider consistency of naming more carefully in this
>>> area.  If we go this route, I want:
>>> 
>>> x.firstIndex(of: 10)
>> 
>> I think that's actually great, because it will separate the
>> user-facing `index(of:)` and `index(where:)` from the stdlib-facing
>> `index(after:)`, `index(before:)`, `index(_:offsetBy:)`, etc.
> 
> Yes.

I'm sold on this too. I've updated the proposal for this that's in the PR queue:
https://github.com/natecook1000/swift-evolution/blob/nc-last-methods/proposals/0000-add-last-methods.md

Nate

> 
> -- 
> -Dave
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution