Permutable adj. - capable of changing sequence
Introduction
This proposal aims to add a PermutableCollection protocol that would sit between Collection and MutableCollection within the collection protocol hierarchy.
Motivation
There are instances where one desires the ability to move and sort elements, while disallowing (or constraining) the mutation of an element. It is a notable ommission given the sheer number of less consequential collection protocols. When creating custom collection types, a PermutableCollection protocol would be preferred in any ordered collection that enforces element uniqueness and/or identity. Use cases would include the forthcoming OrderedDictionary and OrderedSet. For immutable and mutable collections, it could also serve to provide unified access to the underlying (and presumably highly optimized) sorting algorithms used by Swift.
Design
The protocol design is simple with a single swapAt requirement
/// A collection that supports sorting.
protocol PermutableCollection<Element> : Collection where Self.SubSequence : PermutableCollection {
mutable func swapAt(_ i: Index, _ j: Index)
}
Through the swapAt function, additional sorting functions implementations are added via extension
extension PermutableCollection {
mutating func move(fromOffsets source: IndexSet, toOffset destination: Int) {
// move algorithm enacts changes via swapAt()
}
mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
// partition algorithm enacts changes via swapAt()
}
mutating func sort() where Self: RandomAccessCollection, Self.Element: Comparable {
// partition algorithm enacts changes via swapAt()
}
// ... more permutation operations that mimic those available for MutableCollection
}
I have created a working (but unoptimized) example of PermutableCollection and posted it here.
Alternatives
Alternative #1: when sorting functionality is needed, add it manually.
This certainly works, but requires significant boilerplate code. And without an underlying protocol, the existence of functions and their naming is not strictly enforced. When added manually, there is unfortunately no guarantee that the sorting algorithms are equivalent to those in MutableCollection and RangeReplaceableCollection
Alternative #2: just use MutableCollection which 'automatically' implements various sorting algorithms
While this approach quickly adds the desired sorting functions (swap, partition, move, sort, etc), it makes a promise that each element can be mutated at any time to any value. There are many situations where this is promise is undesirable. Furthermore, the majority of the permutation operations result in transient duplicate values during the permutation. I anticipate that many of the use-cases for PermutableCollection would be in situations where some form of uniqueness is enforced and duplicates (even transient ones) may violate the contraints of the collection. I can also envision a collection where the indices may be in a separate store than the elements. The way that MutableCollection permutations are implemented, it is not possible to update the indices without updating the elements as well (though a hacky version of this version might be possible if the elements were all uniquely identified).
Potential Shortcomings
- There are forseeable compatibility issues with MutableCollection and RangeReplaceableCollection
- Performing the permutable operations strictly via swapAt may result in performance degredation
Conclusion and Future Directions
PermutableCollection seems like an overlooked protocol in Swift that would see immediate use in the forthcoming OrderedSet and OrderedDictionary. In addition to allowing for easier creation of new collection types, it also has the advantage of consolidating all of the permutation operations via the swapAt function.
Though I anticipate some compatibility issues, it may also be desirable to have MutableCollection and RangeReplaceableCollection route all of their permutation operations through swapAt as well. This would foster more consistent behaviour of the various collection protocols. In such a scenario, all of the collection protocols (and not just PermutableCollection) could 'override' the handling of permutation operations by defining a swapAt function.
I have no idea what I'm doing.