Add `indexBeforeFirst(where:)` and `indexAfterLast(where:)`

[kylemacomber]

In #4 the implementation of trimmed(where:) requires a raw loop because using lastIndex(where:) would require making an extra call to index(after:) to advanced the returned index.

The embracing algorithms talk exhibits the need for the dual—the index before firstIndex(where:)—to avoid a raw loop or an extra call to index(before:):

extension MutableCollection {
    mutating func bringForward(elementsSatisfying predicate: (Element) -> Bool) {
        if let predecessor = indexBeforeFirst(where: predicate) {
            self[predecessor...].stablePartition(isSuffixElement: { !predicate($0) })
        }
    }
}

extension Collection {
    func indexBeforeFirst(where predicate: (Element) -> Bool) -> Index? {
        return indices.first {
            let successor = index(after: $0)
            return successor != endIndex && predicate(self[successor])
        }
    } 
}

These use cases seem like sufficient justification to add these algorithms.

Though I wonder if indexBeforeFirst(where:)/indexAfterLast(where:) or firstIndex(before:)/lastIndex(after:) or some other naming scheme is best?

[natecook1000]

The naming for these is tricky! It would be nice if they sorted next to firstIndex(where:) and lastIndex(where:), but the contortions to make that happen don't seem worth it. When used with a trailing closure, firstIndex(before:) becomes firstIndex { ... }, which loses a vital bit of meaning. firstIndexBefore(where:) is ungainly, and even firstIndexBefore(_:) doesn't seem quite right.

Let's stick with the clear indexBeforeFirst(where:) and indexAfterLast(where:).

[xwu]

In fact, the “firstness” and “lastness” of these APIs are kind of inconsequential, and even potentially misinterpretable. The index before the first x is actually the last index before x.

By contrast, the “beforeness” and “afterness” of these APIs is very clear. It’s also worth reflecting that the index before the first x is also the index before any x. Perhaps, if we wanted to reflect the relationship between these APIs, we might invoke existing naming precedent and say: indexBefore(anySatisfying:) and indexAfter(allSatisfying:).

[kylemacomber]

@natecook1000 it's a good point, since these APIs take a trailing closure we can't rely on the argument label to pull very much weight

[timvermeulen]

I think indexAfterLast(where:) has a lot more going for it than indexBeforeFirst(where:). It's no coincidence that trimmed(where:) needs indexAfterLast(where:), but not indexBeforeFirst(where:) — in a world of half-open ranges, the dual of indexAfterLast(where:) isn't indexBeforeFirst(where:), it's firstIndex(where:).

The same need for indexAfterLast(where:) arises in the startOfChunk(endingAt:) helper of the LazyChunked type. Where firstIndex(where:) gives you the (exclusive) end of the current chunk / the (inclusive) start of the next one, indexAfterLast(where:) gives you the (inclusive) start of the current chunk / the (exclusive) end of the previous one. indexBeforeFirst(where:) would instead give you an exclusive start / inclusive end, which isn't as useful.

It's true that the bringForward method from the Embracing Algorithms talk needed indexBeforeFirst(where:), but in my opinion that was a pretty niche use case driven by the specific needs of the example app. If you were to implement a similar sendBackward method in the same way, wouldn't that "show" a need for an indexAfterIndexAfterLast(where:) method?

[kylemacomber]

@timvermeulen really interesting point about lowerBound and upperBound of a half-open range corresponding to firstIndex(where:) and indexAfterLast(where:)!

That we've already open coded indexAfterLast(where:) for trimmed and chunked, convinces me it's worth adding.

[timvermeulen]

Every use of indexAfterLast(where:) I've seen is followed by ?? startIndex. I'm beginning to wonder if what we're really looking for is a method that returns a non-optional index, defaulting to startIndex when no element satisfies the predicate. It would need a different name than indexAfterLast(where:) though.

Its dual would be an alternative to firstIndex(where:) that returns endIndex when no match is found, which is also how trimming and chunked are already using firstIndex(where:).

[benrimmington]

The API could return a range (or tuple) with both indices (i.e. the last index, and the index after last).

extension BidirectionalCollection {

  public func lastIndexAsRange(
    where predicate: (Element) throws -> Bool
  ) rethrows -> Range<Index>? {
    var upperBound = endIndex
    while upperBound != startIndex {
      let lowerBound = index(before: upperBound)
      if try predicate(self[lowerBound]) {
        return lowerBound..<upperBound
      }
      upperBound = lowerBound
    }
    return nil
  }
}

[benrimmington]

I've created pull request #55.

[natecook1000]

@benrimmington I don't think there's motivation in the use cases given here for returning a range instead of just the specific boundary index — it would only make usage more cumbersome. When you need this method instead of firstIndex or lastIndex, you just want the off-by-one index, not both.

@timvermeulen Viewed from that perspective, there's a kind of relationship with partitioningIndex. In particular, indexAfterLast(where:) returns the index that splits the collection into (1) the slice that includes the last matching element and (2) the remainder of the collection. It differs from partitioningIndex in that there are no guarantees or requirements about the remainder of the elements in slice 1 — all except the last element could fail the predicate. Interestingly, the from-the-front version isn't required for this kind of split/partitioning, since the position of the first matching element is sufficient to split the collection into those two pieces.

If we had suffix(while:), this could be written as myCollection.suffix(while: { !predicate($0) }).startIndex. (Or really, suffix(while:) would be written on top of this.)

[benrimmington]

@natecook1000 Returning both indices makes it easier to name the API, and lastIndexAsRange will be listed next to the existing lastIndex methods.

Not returning both indices will throw away (potentially useful) information. It seems easy to append ?.upperBound to the method call.

But I won't mind if you decide to close the pull request.

[timvermeulen]

Viewed from that perspective, there's a kind of relationship with partitioningIndex.

Absolutely! The way I like to think about these methods is that they return the least upper bound and greatest lower bound of all indices whose elements satisfy the predicate, and with partitioningIndex these two bounds just happen to coincide (with one of the predicates flipped).

Interestingly, the from-the-front version isn't required for this kind of split/partitioning, since the position of the first matching element is sufficient to split the collection into those two pieces.

That's only really true when a matching element exists in the first place. Without a matching element such a "split" would still make sense, in the same way that prefix(while: { _ in true }) makes sense.

If we had suffix(while:), this could be written as myCollection.suffix(while: { !predicate($0) }).startIndex. (Or really, suffix(while:) would be written on top of this.)

I'm inclined to agree that these are the conceptual building blocks of prefix(while:) and suffix(while:), and not the other way around. The ! bothers me, though, and it also appears in chunked and trimming — should we flip the predicate and instead talk about the upper/lower bound of the maximum prefix/suffix of matching (rather than non-matching) elements? This might not make naming them any easier though... 😅