(Draft) Add last(where:) and lastIndex(where:) methods

(Nate Cook) #1

I've needed these in the past and used them in other languages—any feedback on this idea?

Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections
The standard library should include methods for finding the last element of a bidirectional collection that matches a predicate, along with the index of that element.

Motivation
The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a collection to find an element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1
Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of particular kind of element has multiple applications, particularly with text, such as wrapping a long string into lines of a maximum length or trimming whitespace from the beginning and end of a string.

This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })
Wat.

Proposed solution
Bidirectional collections should include three new methods for symmetry with the existing forward-searching APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7
Much better!

(Hooman Mehr) #2

I agree with adding more such API’s.

Look at this gist <https://gist.github.com/hooman/e77cc0e955a1db672ae49e45b0038d04> for an implementation of a few more of what I find useful. You can add them to your proposal if you like them and I will be able to help better shape it up. Here is a summary:

public func offset(of index: Index) -> IndexDistance
public func index(atOffset offset: IndexDistance) -> Index

public func index(of element: Iterator.Element, from firstIndex: Index) -> Index?
public func index(from firstIndex: Index, where predicate: @noescape (Iterator.Element) throws -> Bool) rethrows -> Index?
public func index<C: Collection where ...>(of elementSequence: C) -> Index?
public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index) -> Index?

Look at the comments for the example usage. For `offset` function, see the source code for usage.

Hooman

···

On May 10, 2016, at 11:54 AM, Nate Cook via swift-evolution <swift-evolution@swift.org> wrote:

I've needed these in the past and used them in other languages—any feedback on this idea?

Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections
The standard library should include methods for finding the last element of a bidirectional collection that matches a predicate, along with the index of that element.

Motivation
The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a collection to find an element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1
Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of particular kind of element has multiple applications, particularly with text, such as wrapping a long string into lines of a maximum length or trimming whitespace from the beginning and end of a string.

This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })
Wat.

Proposed solution
Bidirectional collections should include three new methods for symmetry with the existing forward-searching APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7
Much better!

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(plx) #3

Do these return endIndex or nil on a not-found?

Either can work with different tradeoffs; depends on what you care about...but the choice should be justified and the alternative explained.

···

On May 10, 2016, at 13:54, Nate Cook via swift-evolution <swift-evolution@swift.org> wrote:

I've needed these in the past and used them in other languages—any feedback on this idea?

Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections
The standard library should include methods for finding the last element of a bidirectional collection that matches a predicate, along with the index of that element.

Motivation
The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a collection to find an element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1
Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of particular kind of element has multiple applications, particularly with text, such as wrapping a long string into lines of a maximum length or trimming whitespace from the beginning and end of a string.

This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })
Wat.

Proposed solution
Bidirectional collections should include three new methods for symmetry with the existing forward-searching APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7
Much better!

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Xiaodi Wu) #4

If these are to be added, I'd advocate for renaming `index(of:)` and
`index(where:)` to `firstIndex(of:)` and `firstIndex(where:)`, respectively.

···

On Tue, May 10, 2016 at 13:54 Nate Cook via swift-evolution < swift-evolution@swift.org> wrote:

I've needed these in the past and used them in other languages—any
feedback on this idea?
------------------------------
Add last(where:) and lastIndex(where:) Methods to Bidirectional
Collections

The standard library should include methods for finding the last element
of a bidirectional collection that matches a predicate, along with the
index of that element.
Motivation

The standard library currently has (or will soon have) methods that
perform a linear search from the beginning of a collection to find an
element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1

Unfortunately, there is no such method that searches from the end of a
bidirectional collection. Finding the last of particular kind of element
has multiple applications, particularly with text, such as wrapping a long
string into lines of a maximum length or trimming whitespace from the
beginning and end of a string.

This limitation can be worked around by using the methods above on the
reversed collection, but the resulting code is truly dreadful. For example,
to find the corresponding last index to a.index(where: { $0 > 25 }), this
unholy incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })

Wat.
Proposed solution

Bidirectional collections should include three new methods for symmetry
with the existing forward-searching APIs: last(where:), lastIndex(where:),
and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed
collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7

Much better!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Dave Abrahams) #5

I've needed these in the past and used them in other languages—any feedback on this idea?

---------------------------------------------------------------------------------------------------------------------

Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections

The standard library should include methods for finding the last element of a bidirectional collection that matches a
predicate, along with the index of that element.

Why shouldn't this work with all Collections, with an optimized version
for BidirectionalCollections?

Motivation

The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a
collection to find an element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1

Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of
particular kind of element has multiple applications, particularly with text, such as wrapping a long string into
lines of a maximum length or trimming whitespace from the beginning and end of a string.

This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is
truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy
incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })

Wat.

Proposed solution

Bidirectional collections should include three new methods for symmetry with the existing forward-searching
APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7

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)

···

on Tue May 10 2016, Nate Cook <swift-evolution@swift.org> wrote:

--
-Dave

(Nate Cook) #6

Thanks Hooman! Those do look like useful extensions. I think the proposal should stay focused on the APIs it includes already.

I agree with adding more such API’s.

Look at this gist <https://gist.github.com/hooman/e77cc0e955a1db672ae49e45b0038d04> for an implementation of a few more of what I find useful. You can add them to your proposal if you like them and I will be able to help better shape it up. Here is a summary:

public func offset(of index: Index) -> IndexDistance
public func index(atOffset offset: IndexDistance) -> Index

I like these, but I doubt they would get much traction, since they're essentially substituting startIndex into existing methods. I have thought it would be nice to have startIndex as the default parameter to those methods, though, so you could write either of these:

  let i = c.index(c.startIndex, offsetBy: 5) // current
  let i = c.index(offsetBy: 5) // nice addition

public func index(of element: Iterator.Element, from firstIndex: Index) -> Index?
public func index(from firstIndex: Index, where predicate: @noescape (Iterator.Element) throws -> Bool) rethrows -> Index?

I have the same reaction to these. Because indices are shared between collections and slices, instead of using a starting index, Swift's collection operations can just work on a slice. So instead of calling

  let i = c.index(of: "A", from: firstIndex)

you can call

  let i = c.suffix(from: firstIndex).index(of: "A")

public func index<C: Collection where ...>(of elementSequence: C) -> Index?
public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index) -> Index?

These methods we don't have at all currently, and could really use! I would definitely support a proposal for finding a subsequence of a collection. There are several algorithms beyond the naive approach, so it would be interesting to see if / how a proposal could use those in a generic context.

Thanks again!
Nate

···

On May 10, 2016, at 4:18 PM, Hooman Mehr <hooman@mac.com> wrote:

Look at the comments for the example usage. For `offset` function, see the source code for usage.

Hooman

On May 10, 2016, at 11:54 AM, Nate Cook via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I've needed these in the past and used them in other languages—any feedback on this idea?

Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections
The standard library should include methods for finding the last element of a bidirectional collection that matches a predicate, along with the index of that element.

Motivation
The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a collection to find an element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1
Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of particular kind of element has multiple applications, particularly with text, such as wrapping a long string into lines of a maximum length or trimming whitespace from the beginning and end of a string.

This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })
Wat.

Proposed solution
Bidirectional collections should include three new methods for symmetry with the existing forward-searching APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7
Much better!

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

(Nate Cook) #7

Do these return endIndex or nil on a not-found?

Either can work with different tradeoffs; depends on what you care about...but the choice should be justified and the alternative explained.

These return nil when no matching element is found, just like their from-the-beginning counterparts. endIndex would not be appropriate as a return value.

···

On May 10, 2016, at 7:27 PM, plx via swift-evolution <swift-evolution@swift.org> wrote:

On May 10, 2016, at 13:54, Nate Cook via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I've needed these in the past and used them in other languages—any feedback on this idea?

Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections
The standard library should include methods for finding the last element of a bidirectional collection that matches a predicate, along with the index of that element.

Motivation
The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a collection to find an element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1
Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of particular kind of element has multiple applications, particularly with text, such as wrapping a long string into lines of a maximum length or trimming whitespace from the beginning and end of a string.

This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })
Wat.

Proposed solution
Bidirectional collections should include three new methods for symmetry with the existing forward-searching APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7
Much better!

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Brent Royal-Gordon) #8

Why shouldn't this work with all Collections, with an optimized version
for 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. 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 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.

···

--
Brent Royal-Gordon
Architechies

(Hooman Mehr) #9

Thank you for your comments.

I think additional index manipulation and collection scanning API is needed, and your proposal cover an important part of it.

I also have some clarifications and comments inline:

Thanks Hooman! Those do look like useful extensions. I think the proposal should stay focused on the APIs it includes already.

public func offset(of index: Index) -> IndexDistance
public func index(atOffset offset: IndexDistance) -> Index

I like these, but I doubt they would get much traction, since they're essentially substituting startIndex into existing methods. I have thought it would be nice to have startIndex as the default parameter to those methods, though, so you could write either of these:

  let i = c.index(c.startIndex, offsetBy: 5) // current
  let i = c.index(offsetBy: 5) // nice addition

That is right. The main function is `offset` that I use a lot and for the reverse, your suggestion seems better. I am using `offset` quite a bit but I don’t know if it is generally as useful for other people as it is for me.

public func index(of element: Iterator.Element, from firstIndex: Index) -> Index?
public func index(from firstIndex: Index, where predicate: @noescape (Iterator.Element) throws -> Bool) rethrows -> Index?

I have the same reaction to these. Because indices are shared between collections and slices, instead of using a starting index, Swift's collection operations can just work on a slice. So instead of calling

  let i = c.index(of: "A", from: firstIndex)

you can call

  let i = c.suffix(from: firstIndex).index(of: "A”)

The point is: The `i` above is an index into the (discarded) slice returned by `suffix()`, not the collection `c`. In general, it does not work correctly on the original collection. The behavior of slice indexes have changed a couple of times and is not totally consistent or guaranteed for different concrete collections. That is the reason I am proposing the above function to provide a sure way to have this functionality working properly and I find it extremely useful. Again I don’t know about others.

It seems that the subject of the interaction between slice indexes and the parent collections need further clarifications and specification from the core Swift team.

public func index<C: Collection where ...>(of elementSequence: C) -> Index?
public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index) -> Index?

These methods we don't have at all currently, and could really use! I would definitely support a proposal for finding a subsequence of a collection. There are several algorithms beyond the naive approach, so it would be interesting to see if / how a proposal could use those in a generic context.

I updated the gist <https://gist.github.com/hooman/e77cc0e955a1db672ae49e45b0038d04>. Besides some corrections and removing a couple of extension constraints, I merged the two functions above into:

public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index? = nil) -> Index?

I think the basic implementation in the gist is good enough for many cases and we can specialize for array. As long as the collection and the sub-collection are not huge, performance should be fine.

On the other hand, I am too busy to seriously propose and pursue its addition. If enough people find it worthy of general inclusion into the standard library, somebody will pick it up, but not me.

I didn’t intend to hijack your proposal, but I thought some comments would help clarify things.

Thank you again,
Hooman

···

On May 10, 2016, at 4:52 PM, Nate Cook <natecook@gmail.com> wrote:

On May 10, 2016, at 4:18 PM, Hooman Mehr <hooman@mac.com <mailto:hooman@mac.com>> wrote:

Thanks again!
Nate

Look at the comments for the example usage. For `offset` function, see the source code for usage.

Hooman

On May 10, 2016, at 11:54 AM, Nate Cook via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I've needed these in the past and used them in other languages—any feedback on this idea?

Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections
The standard library should include methods for finding the last element of a bidirectional collection that matches a predicate, along with the index of that element.

Motivation
The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a collection to find an element that matches a predicate:

let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
a.first(where: { $0 > 25 }) // 30
a.index(of: 10) // 2
a.index(where: { $0 > 25 }) // 1
Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of particular kind of element has multiple applications, particularly with text, such as wrapping a long string into lines of a maximum length or trimming whitespace from the beginning and end of a string.

This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy incantation is required:

(a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })
Wat.

Proposed solution
Bidirectional collections should include three new methods for symmetry with the existing forward-searching APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.

These additions would remove the need for searching in a reversed collection and allow code like the following:

a.last(where: { $0 > 25 }) // 40
a.lastIndex(of: 10) // 6
a.lastIndex(where: { $0 > 25 }) // 7
Much better!

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

(Dave Abrahams) #10

Why shouldn't this work with all Collections, with an optimized version
for 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.

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.

···

on Thu May 19 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

--
-Dave

(Nate Cook) #11

Thank you for your comments.

I think additional index manipulation and collection scanning API is needed, and your proposal cover an important part of it.

I also have some clarifications and comments inline:

Thanks Hooman! Those do look like useful extensions. I think the proposal should stay focused on the APIs it includes already.
public func offset(of index: Index) -> IndexDistance
public func index(atOffset offset: IndexDistance) -> Index

I like these, but I doubt they would get much traction, since they're essentially substituting startIndex into existing methods. I have thought it would be nice to have startIndex as the default parameter to those methods, though, so you could write either of these:

  let i = c.index(c.startIndex, offsetBy: 5) // current
  let i = c.index(offsetBy: 5) // nice addition

That is right. The main function is `offset` that I use a lot and for the reverse, your suggestion seems better. I am using `offset` quite a bit but I don’t know if it is generally as useful for other people as it is for me.

'distance(from:to:)' is the corresponding method to your 'offset(of:)', although it might need a different name if the first parameter were optional. I don't find it onerous to provide c.startIndex when using that one.

public func index(of element: Iterator.Element, from firstIndex: Index) -> Index?
public func index(from firstIndex: Index, where predicate: @noescape (Iterator.Element) throws -> Bool) rethrows -> Index?

I have the same reaction to these. Because indices are shared between collections and slices, instead of using a starting index, Swift's collection operations can just work on a slice. So instead of calling

  let i = c.index(of: "A", from: firstIndex)

you can call

  let i = c.suffix(from: firstIndex).index(of: "A”)

The point is: The `i` above is an index into the (discarded) slice returned by `suffix()`, not the collection `c`. In general, it does not work correctly on the original collection. The behavior of slice indexes have changed a couple of times and is not totally consistent or guaranteed for different concrete collections. That is the reason I am proposing the above function to provide a sure way to have this functionality working properly and I find it extremely useful. Again I don’t know about others.

It seems that the subject of the interaction between slice indexes and the parent collections need further clarifications and specification from the core Swift team.

Indices from slices absolutely should reference the same element(s) in the original collection―the collections system is based in part on that interoperability. If you see any behavior that deviates from this, please file a bug!

public func index<C: Collection where ...>(of elementSequence: C) -> Index?
public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index) -> Index?

These methods we don't have at all currently, and could really use! I would definitely support a proposal for finding a subsequence of a collection. There are several algorithms beyond the naive approach, so it would be interesting to see if / how a proposal could use those in a generic context.

I updated the gist. Besides some corrections and removing a couple of extension constraints, I merged the two functions above into:

public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index? = nil) -> Index?

I think the basic implementation in the gist is good enough for many cases and we can specialize for array. As long as the collection and the sub-collection are not huge, performance should be fine.

On the other hand, I am too busy to seriously propose and pursue its addition. If enough people find it worthy of general inclusion into the standard library, somebody will pick it up, but not me.

I didn’t intend to hijack your proposal, but I thought some comments would help clarify things.

Thank you again,
Hooman

Nate

···

On May 11, 2016, at 12:32 PM, Hooman Mehr via swift-evolution <swift-evolution@swift.org> wrote:

On May 10, 2016, at 4:52 PM, Nate Cook <natecook@gmail.com> wrote:
On May 10, 2016, at 4:18 PM, Hooman Mehr <hooman@mac.com> wrote:

(Nate Cook) #12

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:

Nate

···

On May 20, 2016, at 10:34 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Thu May 19 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

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

(Brent Royal-Gordon) #13

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'm imagining an implementation something like this:

  func lastIndex(of value: Element) -> Index? {
    let count = self.count
    
    for endOffset in 0..<count {
      let offset = count - endOffset - 1
      let i = index(startIndex, offsetBy: offset)
      
      if self[i] == value {
        return i
      }
    }
    
    return nil
  }

`index(_:offsetBy:)` is O(N) for a ForwardCollection, and `offset` gets smaller as you execute the loop, so I *believe* this ends up being O(N log N). I was never that good at big-O notation, though, so I could be wrong about that. What I can say is that it would be O(N^2) if not for the decreasing size of `offset`, so it's smaller than that.

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.

If you guys think it's okay, I'm not going to argue.

···

--
Brent Royal-Gordon
Architechies

(Dave Abrahams) #14

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'm imagining an implementation something like this:

  func lastIndex(of value: Element) -> Index? {
    let count = self.count

    for endOffset in 0..<count {
      let offset = count - endOffset - 1
      let i = index(startIndex, offsetBy: offset)

      if self[i] == value {
        return i
      }
    }

    return nil
  }

Oh, no!

    extension Collection {
      func lastIndex(where predicate: (Element)->Bool) -> Index? {
        var result: Index? = nil
        for i in indices {
          if predicate(self[i]) { result = i }
        }
        return result
      }
    }

    extension Collection where Element : Equatable {
      func lastIndex(of value: Element) -> Index? {
        return lastIndex(where: { $0 == value })
      }
    }

`index(_:offsetBy:)` is O(N) for a ForwardCollection, and `offset`
gets smaller as you execute the loop, so I *believe* this ends up
being O(N log N). I was never that good at big-O notation, though, so
I could be wrong about that. What I can say is that it would be O(N^2)
if not for the decreasing size of `offset`, so it's smaller than that.

What you wrote is still (N*(N - 1))/2 steps, i.e. O(N^2), in the worst
case, unless I'm missing something.

···

on Sat May 21 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

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.

If you guys think it's okay, I'm not going to argue.

--
-Dave

(Brent Royal-Gordon) #15

       var result: Index? = nil
       for i in indices {
         if predicate(self[i]) { result = i }
       }
       return result

That is better! I didn't think to just give up on testing the minimum number of elements.

···

--
Brent Royal-Gordon
Architechies

(Patrick Smith) #16

Ha what a simple but great implementation! Seems obvious in retrospect.

···

On 22 May 2016, at 7:53 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Sat May 21 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

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'm imagining an implementation something like this:

  func lastIndex(of value: Element) -> Index? {
    let count = self.count

    for endOffset in 0..<count {
      let offset = count - endOffset - 1
      let i = index(startIndex, offsetBy: offset)

      if self[i] == value {
        return i
      }
    }

    return nil
  }

Oh, no!

   extension Collection {
     func lastIndex(where predicate: (Element)->Bool) -> Index? {
       var result: Index? = nil
       for i in indices {
         if predicate(self[i]) { result = i }
       }
       return result
     }
   }

   extension Collection where Element : Equatable {
     func lastIndex(of value: Element) -> Index? {
       return lastIndex(where: { $0 == value })
     }
   }

`index(_:offsetBy:)` is O(N) for a ForwardCollection, and `offset`
gets smaller as you execute the loop, so I *believe* this ends up
being O(N log N). I was never that good at big-O notation, though, so
I could be wrong about that. What I can say is that it would be O(N^2)
if not for the decreasing size of `offset`, so it's smaller than that.

What you wrote is still (N*(N - 1))/2 steps, i.e. O(N^2), in the worst
case, unless I'm missing something.

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.

If you guys think it's okay, I'm not going to argue.

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