Add MutableCollection.swapRanges(_: Range<Index>, _: Range<Index>)?

Continuing the discussion from Add `extract(where:)` method to `RangeReplaceableCollection`:

Before @Ben_Cohen moved on to a subrange extraction method, I was going to suggest that a tail-only extraction method needed to be balanced with either a head-only extraction method or some way to swap another range to become the tail.

Outside of the source thread, should MutableCollection get a method to swap ranges of elements? The two ranges must not have any overlap; overlap (that isn't 100%) is a precondition failure. I don't know if we should special-case the identical input ranges case to be a no-op instead of failing upon any overlap. Note that the two ranges don't have to be the same length.

I feel like an implementation of this is non-trivial enough to be valuable in the standard library. How do you feel about adding this on MutableCollection vs.RangeReplaceableCollection? It doesn't change the length, so I see the argument for MutableCollection, but semantically it seems to fit better with the spirit of RangeReplaceableCollection.

Here's my first try:

extension MutableCollection {

    /**
     Exchanges the values at the specified ranges of the collection.

     Both parameters must bound valid index ranges of the collection.
     Using identical ranges has no effect.  Non-identical ranges do
     not have to be the same length.

     - Precondition: The subsequences for `r` and `s` must not share
       any elements unless they are identical.

     - Parameter r: The range for the first subsequence to swap.
     - Parameter s: The range for the second susequence to swap.

     - Postcondition: The targeted subsequences exchange positions
       relative to all the maximum-length untargeted subsequences.  If
       the targeted subsequences have different lengths, then the
       indices for any elements between the two subsequences will shift.

     - Returns: The amount each untargeted in-between element moved.
       Offset the old index value by the return value to get the new index.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    @discardableResult
    public mutating func swapRanges(_ r: Range<Index>, _ s: Range<Index>) -> Int {
        guard r != s else { return 0 }

        let (leader, trailer) = r.lowerBound > s.lowerBound ? (s, r) : (r, s)
        let closedBoundsOverlap = (leader.lowerBound ... leader.upperBound).overlaps(trailer.lowerBound ... trailer.upperBound)
        switch (leader.isEmpty, trailer.isEmpty) {
        case (true, true):
            // No elements are moved.
            return 0
        case (false, true) where closedBoundsOverlap,
             (true, false) where closedBoundsOverlap:
            // An empty range within or capping a non-empty range.
            return 0
        case (true, false):
            // The in-between elements move tail-ward when trailer moves.
            swapRanges(leader.upperBound..<trailer.lowerBound, trailer)
            return +distance(from: trailer.lowerBound, to: trailer.upperBound)
        case (false, true):
            // The in-between elements move head-ward when the leader moves.
            swapRanges(leader, leader.upperBound..<trailer.lowerBound)
            return -distance(from: leader.lowerBound, to: leader.upperBound)
        case (false, false):
            precondition(!leader.overlaps(trailer))

            var l = leader.lowerBound, t = trailer.lowerBound
            while l < leader.upperBound, t < trailer.upperBound {
                swapAt(l, t)
                formIndex(after: &l)
                formIndex(after: &t)
            }

            let result = swapRanges(l..<leader.upperBound, t..<trailer.upperBound)
            return leader.upperBound == trailer.lowerBound ? 0 : result
        }
    }

}

But there are a few problems:

  • I return how much the elements between the two targeted ranges move, but having the exact range may be more useful. More importantly, knowing the two targeted ranges' new values (when they are not the same length) is even more useful.
  • After a few hours, I noticed that I could do some of the moving as a rotate, this is additionally important since:
  • I don't think this algorithm is actually linear. In the last case, if the targeted ranges are not equal in length, a recursive call is done with an empty subsequence versus a non-empty one, which triggers a range swap between the targeted non-empty range and the in-between range. This means that some elements get swapped multiple times. I don't know if it's n^2 or n * log n.

Let's try again:

extension MutableCollection {

    /**
     Rotates the elements such that the value at the given index is now at `startIndex`.

     Passing `startIndex` as `i` has no effect.

     The method applies a left-rotation, bringing the target element's value to `startIndex`.

         var letters = ["A", "B", "C", "D", "E", "F"]
         letters.rotate(toFirst: letters.index(after: letters.startIndex))
         print(String(letters))
         // Prints "BCDEFA"

     - Precondition: `i` must be a valid index of this collection and not equal to `endIndex`.

     - Parameter i: The index of the element whose value will move to `startIndex`.

     - Returns: The index of the element where the value originally at `startIndex` went.

     - Postcondition: The new value is a left-rotation of the old; `newValue == oldValue[i...] + oldValue[..<i]`.

     - Complexity: O(*n*), where *n* is the collection's length.
     */
    @discardableResult
    mutating public func rotate(toFirst i: Index) -> Index {
        precondition(i != endIndex)
        guard i != startIndex else { return startIndex }

        // Adapted from <http://www.cplusplus.com/reference/algorithm/rotate/>.
        var pivot = i, next = pivot, start = startIndex
        let startOffset = distance(from: pivot, to: endIndex)
        while start != next {
            swapAt(start, next)
            formIndex(after: &start)
            formIndex(after: &next)
            if next == endIndex {
                next = pivot
            } else if start == pivot {
                pivot = next
            }
        }
        return index(startIndex, offsetBy: startOffset)
    }

    /**
     Exchanges the values of elements within the specified ranges of
     the collection.

     Both parameters must bound valid index ranges of the collection.
     The subsequences for the ranges must have either no elements in
     common or all of (at least) one subsequence's elements in common.
     There is no effect in the latter case.  Non-identical ranges do
     not have to be the same length.

     - Precondition: The intersection for `r` and `s` must be exactly
       ∅, `r`, or `s`.

     - Parameter r: The range for the first subsequence to swap.
     - Parameter s: The range for the second susequence to swap.

     - Postcondition: No effect if the ranges are identical or one of
       them is completely within the other.  Otherwise, the targeted
       subsequences exchange their relative positions against all the
       maximum-length untargeted subsequences, and `r` and `s` are
       updated to their subsequences' new ranges.

     - Returns: The new range for the subsequence between `r` and `s`,
       or `nil` if no effect occured.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    @discardableResult
    public mutating func swapRanges(_ r: inout Range<Index>, _ s: inout Range<Index>) -> Range<Index>? {
        guard r.lowerBound <= s.upperBound else { return swapRanges(&s, &r) }
        guard r.upperBound <= s.lowerBound else {
            // The first guard above misses when reversed-order ranges abut.
            guard r.lowerBound != s.upperBound else { return swapRanges(&s, &r) }

            // A consistent result is still possible if one range is totally within another.
            precondition(r.lowerBound <= s.lowerBound && r.upperBound >= s.upperBound || s.lowerBound <= r.lowerBound && s.upperBound >= r.upperBound)
            return nil
        }

        var intermediateRange = r.upperBound..<s.lowerBound
        switch (r.isEmpty, intermediateRange.isEmpty, s.isEmpty) {
        case (true, _, true):
            // No elements to move.
            swap(&r, &s)
            return intermediateRange
        case (true, true, false):
            // Move empty subsequence from before to after the non-empty one.
            assert(r == intermediateRange)
            r = s.upperBound..<s.upperBound
            return r
        case (true, false, false):
            // Empty range goes after post-swapped intermediate one.
            swapRanges(&intermediateRange, &s)
            r = intermediateRange.upperBound..<intermediateRange.upperBound
            return intermediateRange
        case (false, true, true):
            // Move empty subsequence from after to before the non-empty one.
            assert(s == intermediateRange)
            s = r.lowerBound..<r.lowerBound
            return s
        case (false, false, true):
            // Empty range goes before post-swapped intermedicate one.
            swapRanges(&r, &intermediateRange)
            s = intermediateRange.lowerBound..<intermediateRange.lowerBound
            return intermediateRange
        case (false, true, false):
            // The targeted ranges abut, just rotate to new positions.
            let newRStartIndex = self[r.lowerBound..<s.upperBound].rotate(toFirst: s.lowerBound)
            (r, s) = (newRStartIndex..<s.upperBound, r.lowerBound..<newRStartIndex)
            return newRStartIndex..<newRStartIndex
        case (false, false, false):
            // Swap around adjacent subsequences.
            // (R -- IR -- S -> R -- S -- IR -> S -- R -- IR -> S -- IR -- R)
            swapRanges(&intermediateRange, &s)
            swapRanges(&r, &s)
            swapRanges(&r, &intermediateRange)
            return intermediateRange
        }
    }

}

I copied over an implementation of rotate(toFirst:) I did earlier. I can do a lot of optimization if at least one range is empty. And by ranges, I mean both the two targeted subsequences and the possibly-empty possible subsequence between them. The purpose of this function, when the two targeted subsequences don't overlap, is to change the collection from:

uninvolved-prefix | first-subsequence | in-between | second-subsequence | uninvolved-suffix

to:

uninvolved-prefix | second-subsequence | in-between | first-subsequence | uninvolved-suffix

(where any part may be empty).

Hopefully, it's actually linear. I have some more thoughts on where to go, but I'll save them for the response to @Jumhyn's reply.

The swapping methods I've tried out all use methods within MutableCollection, so it would be weird to switch between which protocol to conform to. Also, MC allows arbitrary changes to the collection (as long as the count doesn't change). We even have examples as precedent, methods that commit wholesale rearrangement of element values, partition(by:) and reverse() for structured changes and shuffle() as an unstructured one. If we allow those, then something like possibly uneven swapping is relatively OK.

Use of RRC operations necessarily invalidate the indices of all elements of the collection, while MC operations keep the integrity of the element positions outside either targeted subsequence (and the range in-between the targets if they are of the same length). There are also collection types that support only one of the two mutating protocols, so there is a cost right off the bat over miscategorization.

I put my code for this in a gist.

Terms of Service

Privacy Policy

Cookie Policy