A collection that supports moving and sorting of elements.

PermutableCollection.swift

/// A collection that supports moving and sorting of elements.
public protocol PermutableCollection: Collection {
    
    mutating func swapAt(_ i: Self.Index, _ j: Self.Index)
    
    // mutating func move(fromOffsets source: IndexSet, toOffset destination: Int)

    // mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index

}

public extension PermutableCollection {
    
    mutating func sort(by: EnumeratedSequence<Self>.Offsets) { ... swap ... }
    
    mutating func move(fromOffsets source: IndexSet, toOffset destination: Int) {
        var offsets = self.enumerated().map { $0.offset }
        offsets.move(fromOffsets: source, toOffset: destination)
        self._sort(by: offsets)
    }
    
    mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
        var enumerated = self.enumerated().map { $0 }
        let partitionOffset = try enumerated.partition { try belongsInSecondPartition($0.element) }
        self._sort(by: enumerated)
        return self.index(startIndex, offsetBy: partitionOffset)
    }
    
}

public extension PermutableCollection where Self: RandomAccessCollection {
    
    mutating func shuffle() where Self: RandomAccessCollection {
        let offsets = self.enumerated().shuffled().map { $0.offset }
        _sort(by: offsets)
    }
    
    mutating func shuffle<T>(using generator: inout T) where T : RandomNumberGenerator {
        let offsets = self.enumerated().shuffled(using: &generator).map { $0.offset }
        _sort(by: offsets)
    }
    
    mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        let enumerated = try self.enumerated().sorted { try areInIncreasingOrder($0.element, $1.element)}
        _sort(by: enumerated)
    }
    
    mutating func sort<Comparator>(using comparator: Comparator) where Comparator : SortComparator, Element == Comparator.Compared {
        let enumerated = self.enumerated().sorted { comparator.compare($0.element, $1.element) == .orderedAscending }
        _sort(by: enumerated)
    }

    mutating func sort<S, Comparator>(using comparators: S) where S : Sequence, Comparator : SortComparator, Comparator == S.Element, Element == Comparator.Compared {
        var enumerated = self.enumerated().map { $0 }
        for comparator in comparators {
            enumerated = enumerated.sorted { comparator.compare($0.element, $1.element) == .orderedAscending }
        }
        _sort(by: enumerated)
    }
}

public extension PermutableCollection where Self: RandomAccessCollection, Element: Comparable {
    
    mutating func sort() where Self.Element: Comparable {
        let enumerated = self.enumerated().sorted { $0.element < $1.element}
        _sort(by: enumerated)
    }
}


public extension PermutableCollection where Self: BidirectionalCollection {
    
    mutating func reverse() {
        let offsets = self.enumerated().reversed().map { $0.offset }
        self._sort(by: offsets)
    }
}

fileprivate extension PermutableCollection {
    
    mutating func _swapAt(offsets: (Int, Int)) {
        let i = self.index(startIndex, offsetBy: offsets.0)
        let j = self.index(startIndex, offsetBy: offsets.1)
        swapAt(i, j)
    }
    
    mutating func _sort(by offsets: [Int]) {
        var offsets = offsets.enumerated().map { (old: $0.element, new: $0.offset) }
        
        for index in offsets.indices {
            let offset = offsets[index]
            guard offset.old != offset.new else { continue }
            _swapAt(offsets: (offset.old, offset.new))
            if let newIndex = offsets.firstIndex(where: { offset.new == $0.old}) {
                offsets[newIndex] = (old: newIndex, new: offsets[newIndex].new)
            }
        }
    }
    
    mutating func _sort(by enumerated: [(offset: Int, element: Element)]) {
        _sort(by: enumerated.map { $0.offset })
    }
}