possible implementation of lastIndexOf ??

Question

adysart OP

Created Aug ’15

Replies 4

Boosts 0

Participants 3

So I'm a big fan of the method indexOf() on CollectionType:

extension CollectionType {
    func indexOf(@noescape predicate: (Self.Generator.Element) -> Bool) -> Self.Index?
}

It's really useful for finding the first item in a collection that satisfies the closure:

let foo = 0...10
let firstItem = foo.indexOf { $0 > 5 }

Sure it's O(n), but sometimes you don't care or that's acceptable behavior. Now I'd also really like to have a corresponding lastIndexOf method, which would return the last item in the collection that satisfies the closure. But this doesn't seem to fit well with CollectionType as it is, as I think SequenceType.Generator only goes forward. And I think maybe _Incrementable might be a part of this too? It appears to only index forward as well.

Sure, I could always just do something this:

let lastItem = (foo.count - 1) - foo.reverse.indexOf { $0 < 5 }

But that seems like it would incur a performance penalty by reversing the array. What I really want is to actually iterate through the array in reverse, so that the performance is still just O(n). But I guess that means I can only ever do this where CollectionType.Index is RandomAccessIndexType? I mean, the reverse() method is only available in that case:

extension CollectionType where Index : RandomAccessIndexType {
    func reverse() -> ReverseRandomAccessCollection<Self>
}

Or maybe I want BidirectionalIndexType?

Anyways I've got the simple implementation for Array:

extension Array {
  func lastIndexOf(@noescape predicate: (Array.Generator.Element) -> Bool) -> Array.Index? {
    for var i = self.endIndex-1; i >= self.startIndex; i-- {
      if predicate(self[i]) { 
        return i
      }
    }
    return nil
  }
}

Right? But it seems like this should be accomplishable using just a protocol extension of CollectionType, without generating a reverse array. Presumably with some limitations on types. Anyone have a solution?

Boost

Answer 1

adysart OP

Aug ’15

Hmmm, ok. Does this work??

extension CollectionType where Index : BidirectionalIndexType {
  func lastIndexOf(@noescape predicate: (Self.Generator.Element) -> Bool) -> Self.Index? {
    for var i = self.endIndex.predecessor(); i != self.startIndex; i = i.predecessor() {
      if predicate(self[i]) {
        return i
      }
    }
    return nil
  }
}

0

Answer 2

Systems Engineer OP

Apple

Aug ’15

Actually reverse() is lazy, so should be just about as efficient as doing it manually (it's not going to copy the underlying collection). I think your simplest approach here is probably just fine.

1

Answer 3

adysart OP

Aug ’15

Yeah, I figured reverse was lazy, but is it lazily generating each element? Or does it just lazily generate the entire reverse array the first time it's accessed?

Regardless, this was a good way to get a little more familiar with the organization of the standard library.

0

Answer 4

OOPer OP

Aug ’15

In a usual context speaking about collection types, `lazy` something does not generate the entire array.

As far as I tested, this version of lastIndexOf method runs as fast as the indexOf method in the standard library.

extension CollectionType where Index: BidirectionalIndexType {
    func lastIndexOf(@noescape predicate: (Self.Generator.Element) -> Bool) -> Self.Index? {
        var idx = self.endIndex
        for elt in self.reverse() {
            idx = idx.predecessor()
            if predicate(elt) {
                return idx
            }
        }
        return nil
    }
}

1