Blasts from the past: algorithms

[Nevin]

@CTMacUser

    let backIndices = indices.reversed()
    for current in backIndices {
        …
        swapAt(previous, switchOut)
        self[current ..< endIndex].reverse()
        …
    }

Just a reminder: mutating a collection while holding a reference to its indices property is a performance trap which may duplicate the entire collection. The documentation specifically calls this out, saying,

A collection’s indices property can hold a strong reference to the collection itself, causing the collection to be nonuniquely referenced. If you mutate the collection while iterating over its indices, a strong reference can result in an unexpected copy of the collection. To avoid the unexpected copy, use the index(after:) method starting with startIndex to produce indices instead.

[xwu (Xiaodi Wu)]

@saagarjha

Yes, because it’s a useful method to provide–nobody wants to type out a.rotated(shiftingToStart: a.index(a.endIndex, offsetBy: -distance)). shiftingToStart shouldn’t be given preferential treatment over shiftingToEnd.

I'm confused. If you're shifting a particular element to end, then unless that element is already at the end (in which case it's a no-op), it's equivalent to shifting the immediately following element to start, is it not?

[saagarjha]

D'oh! You're right; I forgot that the endIndex == startIndex if we're wrapping around. Sorry for bothering everyone here!

[CTMacUser (Daryle Walker)]

Yes, I mentioned this too in a reply. But you need branching code since endIndex isn’t dereferenceable.

[CTMacUser (Daryle Walker)]

It does appear that you've kept O(n²) for isPermutation(of:by:) and O(n) for permuteForward(by:) and permuteBackward(by:); very nice job translating the C++, by the way. If we're looking for further optimizations, here's what I came up with:

For isPermutation, now I see why. Pre-fetching the indices and the loop are O(n). But the calls to partition and distance within the loop are also O(n), multiplying to a total O(n²).

I wonder how often will users compare collections with a common prefix, and how long those prefixes typically are; where the O(n) short-circuit with diverges(with:) (i.e. C++'s std::mismatch) would be worth it?

isPermutation(of:by:):

var myIndices = Array(indices), otherIndices = Array(other.indices)

This allocates O(n) space (and it takes O(n) time? The documentation isn't clear on it). If we're fine doing this, it may be worth providing specialized, faster methods when available. In particular, if Element is comparable we can sort the two Collections and then check if they're equal in O(n log n) time, and if Element is Hashable we can do it in O(n) time by using a Dictionary.

If Element conforms to both Comparable and Hashable, how would we make sure the Hashable specialization is called?

guard myIndices.count == otherIndices.count else { return false }

Is there a reason why you put this inside the loop? Why not pull it out so it's not evaluated every time?

I had a similar thought. The first run through that guard checks both collections' count. But subsequent ones make sure that the number of elements that don't match the target value (of the previous loop) match. But to double-check: since the other guard makes sure the number of elements that match the target value are equal; assuming the collection and target counts pass, then the non-target counts have to match each loop-through due to the laws of subtraction. So it'd be safe to move the per-loop count check.

permuteForward(by:), permuteBackward(by:)

let backIndices = indices.reversed()

It appears you're creating this because you're using it with index(where:); if we had a lastIndex(where:) I don't think you'd need this. Something that we should add to the standard library?

One last thing, unrelated to algorithmic complexity: I'd like to include some more documentation in these methods, covering exactly what you've mentioned here: "short circuits if the collections are equal, have size 0" etc. so that future enhancers know what sort of guarantees to provide.

extension Collection {

    /// Returns each index of this and the other collection where their leading elements stop being equivalent.
    func diverges<C: Collection>(with other: C, by areEquivalent: (Element, Element) throws -> Bool) rethrows -> (Index, C.Index) where C.Element == Element {
        var selfIndex = startIndex, otherIndex = other.startIndex
        while selfIndex != endIndex, otherIndex != other.endIndex {
            guard try areEquivalent(self[selfIndex], other[otherIndex]) else { break }

            formIndex(after: &selfIndex)
            other.formIndex(after: &otherIndex)
        }
        return (selfIndex, otherIndex)
    }

    /// Returns whether this collection's elements are a rearrangment of the other's, using the given predicate for equivalence.
    func isPermutation<C: Collection>(of other: C, by areEquivalent: (Element, Element) throws -> Bool) rethrows -> Bool where C.Element == Element {
        // Strike elements from consideration through their indexes.
        var selfIndices = Array(indices), otherIndices = Array(other.indices)
        guard selfIndices.count == otherIndices.count else { return false }

        // Only consider the elements past a common prefix.
        let commonPrefixEndOnSelf = try diverges(with: other, by: areEquivalent).0
        let commonPrefixCount = distance(from: startIndex, to: commonPrefixEndOnSelf)
        selfIndices.removeFirst(numericCast(commonPrefixCount))
        otherIndices.removeFirst(numericCast(commonPrefixCount))

        // Remove each element value from consideration for both `self` and `other`.
        while let nextIndex = selfIndices.first {
            // Sort out the considered value.
            let nextValue = self[nextIndex]
            let selfPivot = try selfIndices.partition { try areEquivalent(self[$0], nextValue) }
            let otherPivot = try otherIndices.partition { try areEquivalent(other[$0], nextValue) }
            let selfMatchCount = selfIndices.distance(from: selfPivot, to: selfIndices.endIndex)
            let otherMatchCount = otherIndices.distance(from: otherPivot, to: otherIndices.endIndex)
            guard selfMatchCount == otherMatchCount else { return false }

            // Remove the value.
            selfIndices.removeLast(selfMatchCount)
            otherIndices.removeLast(otherMatchCount)
        }

        // Because of the first `guard`, any values in `other` not in `self` would have made the count of a shared value shorter, and triggered the second `guard`.
        assert(otherIndices.isEmpty)
        return true
    }

}

extension Collection where Element: Equatable {

    /// Returns each index of this and the other collection where their common prefix ends.
    func diverges<C: Collection>(with other: C) -> (Index, C.Index) where C.Element == Element {
        return diverges(with: other, by: ==)
    }

    /// Returns whether this collection's elements are a rearrangment of the other's.
    func isPermutation<C: Collection>(of other: C) -> Bool where C.Element == Element {
        return isPermutation(of: other, by: ==)
    }

}

extension BidirectionalCollection {

    /// Returns the last index in which an element of the collection satisfies the given predicate.
    func index(lastlyWhere predicate: (Element) throws -> Bool) rethrows -> Index? {
        return try reversed().index(where: predicate).map { index(before: $0.base) }
    }

    /// Returns each index of this and the other collection where their trailing elements start being equivalent.
    func converges<C: BidirectionalCollection>(with other: C, by areEquivalent: (Element, Element) throws -> Bool) rethrows -> (Index, C.Index) where C.Element == Element {
        let (selfIndex, otherIndex) = try reversed().diverges(with: other.reversed(), by: areEquivalent)
        return (index(before: selfIndex.base), other.index(before: otherIndex.base))
    }

}

extension BidirectionalCollection where Element: Equatable {

    /// Returns the last index where the specified value appears in the collection.
    func index(forLastOf element: Element) -> Index? {
        return index(lastlyWhere: { $0 == element })
    }

    /// Returns each index of this and the other collection where their common suffix starts.
    func converges<C: BidirectionalCollection>(with other: C) -> (Index, C.Index) where C.Element == Element {
        return converges(with: other, by: ==)
    }

}

extension BidirectionalCollection where Self: MutableCollection {

    /// Rearrages this collection's elements to the next permutation lexiographically determined by the given predicate, or a sorted collection if already at the last permutation.
    @discardableResult
    mutating func permuteForward(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
        // An empty collection is already at its only permutation state.
        guard var current = index(endIndex, offsetBy: -1, limitedBy: startIndex) else { return false }

        // So is a single-element collection.
        while let beforeCurrent = index(current, offsetBy: -1, limitedBy: startIndex) {
            // Find the last pair of consecutive elments where forward iteration increases the value.
            guard try areInIncreasingOrder(self[beforeCurrent], self[current]) else {
                current = beforeCurrent
                continue
            }

            // Find the last element not smaller than the earlier element of the previous pair.  (If all else fails, this must hit the latter element of the previous pair.)
            let lastNotLessThanBeforeCurrent = try index(lastlyWhere: { try areInIncreasingOrder(self[beforeCurrent], $0) })!

            // Update to a lexiographically-later permutation.
            swapAt(beforeCurrent, lastNotLessThanBeforeCurrent)
            self[current ..< endIndex].reverse()  // `self[current...].reverse()` doesn't work.
            return true
        }

        // At the last permutation; reset to the first one.  This is a no-op for single-element collections.
        reverse()
        return false
    }

    /// Rearranges this collection's elements to the previous permutation lexiographically determined by the given predicate, or a reversed-sorted collection if already at the first permutation.
    @discardableResult
    mutating func permuteBackward(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
        // An empty collection is already at its only permutation state.
        guard var current = index(endIndex, offsetBy: -1, limitedBy: startIndex) else { return false }

        // So is a single-element collection.
        while let beforeCurrent = index(current, offsetBy: -1, limitedBy: startIndex) {
            // Find the last pair of consecutive elments where backward iteration increases the value.
            guard try areInIncreasingOrder(self[current], self[beforeCurrent]) else {
                current = beforeCurrent
                continue
            }

            // Find the last element smaller than the earlier element of the previous pair.  (If all else fails, this must hit the latter element of the previous pair.)
            let lastLessThanBeforeCurrent = try index(lastlyWhere: { try areInIncreasingOrder($0, self[beforeCurrent]) })!

            // Update to a lexiographically-earlier permutation.
            swapAt(beforeCurrent, lastLessThanBeforeCurrent)
            self[current ..< endIndex].reverse()  // `self[current...].reverse()` doesn't work.
            return true
        }

        // At the first permutation; reset to the last one.  This is a no-op for single-element collections.
        reverse()
        return false
    }

}

extension BidirectionalCollection where Self: MutableCollection, Element: Comparable {

    /// Rearrages this collection's elements to the next lexiographical permutation, or a sorted collection if already at the last permutation.
    @discardableResult
    mutating func permuteForward() -> Bool {
        return permuteForward(by: <)
    }

    /// Rearranges this collection's elements to the previous lexiographical permutation, or a reversed-sorted collection if already at the first permutation.
    @discardableResult
    mutating func permuteBackward() -> Bool {
        return permuteBackward(by: <)
    }

}

extension Collection {

    /// Returns the elements of the collection, permuted one step forward using the given predicate to compare elements, unless already at the last permutation.
    func nextPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element]? {
        var result = Array(self)
        let hasMore = try result.permuteForward(by: areInIncreasingOrder)
        return hasMore ? result : nil
    }

    /// Returns the elements of the collection, permuted one step backward using the given predicate to compare elements, unless already at the first permutation.
    func previousPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element]? {
        var result = Array(self)
        let hasMore = try result.permuteBackward(by: areInIncreasingOrder)
        return hasMore ? result : nil
    }

}

extension Collection where Element: Comparable {

    /// Returns the elements of the collection, permuted one step forward, unless already at the last permutation.
    func nextPermutation() -> [Element]? {
        return nextPermutation(orderedBy: <)
    }

    /// Returns the elements of the collection, permuted one step backward, unless already at the first permutation.
    func previousPermutation() -> [Element]? {
        return previousPermutation(orderedBy: <)
    }

}

extension RangeReplaceableCollection {

    /// Returns a copy of the collection, permuted one step forward using the given predicate to compare elements, unless already at the last permutation.
    func nextPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Self? {
        let result: [Element]? = try self.nextPermutation(orderedBy: areInIncreasingOrder)
        return result.map { Self($0) }
    }

    /// Returns a copy of the collection, permuted one step backward using the given predicate to compare elements, unless already at the first permutation.
    func previousPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Self? {
        let result: [Element]? = try self.previousPermutation(orderedBy: areInIncreasingOrder)
        return result.map { Self($0) }
    }

}

extension RangeReplaceableCollection where Element: Comparable {

    /// Returns a copy of the collection, permuted one step forward, unless already at the last permutation.
    func nextPermutation() -> Self? {
        return nextPermutation(orderedBy: <)
    }

    /// Returns a copy of the collection, permuted one step backward, unless already at the first permutation.
    func previousPermutation() -> Self? {
        return previousPermutation(orderedBy: <)
    }

}