A mutating method that rotates the elements of a collection to new positions.
var numbers = [10, 20, 30, 40, 50, 60]
let p = numbers.rotate(toStartAt: 2)
// numbers == [30, 40, 50, 60, 10, 20]
// p == 4 -- numbers[p] == 10
To work around the CoW / slice mutation problem for divide-and-conquer algorithms, which are the idiomatic use case for rotation, this also includes variants that take a range:
var numbers = [10, 20, 30, 40, 50, 60]
numbers.rotate(subrange: 0..<3, toStartAt: 1)
// numbers = [20, 30, 10, 40, 50, 60]
numbers.rotate(subrange: 3..<6, toStartAt: 4)
// numbers = [20, 30, 10, 50, 60, 40]
This adds the two MutableCollection
methods shown above:
extension MutableCollection {
mutating func rotate(toStartAt p: Index) -> Index
mutating func rotate(
subrange: Range<Index>,
toStartAt p: Index
) -> Index
}
Rotation is a O(n) operation, where n is the length of the range being
rotated. The BidirectionalCollection
version of rotation significantly lowers
the number of swaps required per element, so rotate
would need to be a
MutableCollection
customization point were it adopted by the standard library.
The index parameter has been proposed as shiftingToStart
in the past; this
version uses the toStartAt
label, instead. shiftingToStart
introduces the
idea of a "shift", which can sound like shifting just that single element to the
beginning of the collection.
For the range-based overloads, the label could be omitted. That is, instead of
using subrange:
, the method could be called as
numbers.rotate(0..<3, toStartAt: 2)
. The label is included here for
consistency with other range-based mutating methods.
C++: The <algorithm>
library defines a rotate
function with similar
semantics to this one.
Ruby: You can rotate the elements of an array by a number of positions,
either forward or backward (by passing a negative number). For zero-indexed
collections, forward rotation by e.g. 3 elements is equivalent to
rotate(toStartAt: 3)
.