rotate.swift

extension MutableCollectionType where Index: ForwardIndexType {
    /// Swaps the elements in the `lower` and `upper` ranges until one of the 
    /// ranges runs out.
    ///
    /// - Returns: The end point for the actually swapped lower and upper ranges.
    ///   At least of one of `lower` and `upper` will be it's respective range's 
    ///   `endIndex`.
    mutating func swapRanges(lower: Range<Index>, _ upper: Range<Index>)
        -> (lower: Index, upper: Index)
    {
        var (l, u) = (lower.startIndex, upper.startIndex)
        while l != lower.endIndex && u != upper.endIndex {
            swap(&self[l], &self[u])
            l = l.successor()
            u = u.successor()
        }
        return (l, u)
    }
    
    /// Rotates without checking bounds of `index`.
    mutating func unguardedRotate(index: Index) {
        var (start, index) = (startIndex, index)
        var (lowerPivot, upperPivot) = swapRanges(start..<index, index..<endIndex)
        while lowerPivot != index || upperPivot != endIndex {
            start = lowerPivot
            if index == start {
                index = upperPivot
            }
            (lowerPivot, upperPivot) = swapRanges(start..<index, index..<endIndex)
        }
    }
    
    /// Rotates the collection left so the element at `index` ends up first.
    /// - Returns: The new position for the element that was previously at `startIndex`.
    mutating func rotate(index: Index) -> Index {
        if index == startIndex { return endIndex }
        if index == endIndex { return startIndex }
        
        var (start, index) = (startIndex, index)
        var (lowerPivot, upperPivot) = swapRanges(start..<index, index..<endIndex)
        while lowerPivot != index || upperPivot != endIndex {
            if upperPivot == endIndex {
                self[lowerPivot..<endIndex].unguardedRotate(index)
                return lowerPivot
            }
            (start, index) = (index, upperPivot)
            (lowerPivot, upperPivot) = swapRanges(start..<index, index..<endIndex)
        }
        return index
    }
}