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.
