Hello everyone!
I'd like to pitch the formalization of ordered collections as well as the addition of diffing functionality and related types necessary to provide easy creation, representation, and application of ordered collection state transitions.
Formalizing the notion of ordered collections would be accomplished by the addition of an OrderedCollection protocol (and its adoption by suitable types):
@available(swift, introduced: 5.1)
public protocol OrderedCollection : Collection
where SubSequence : OrderedCollection
{
func elementsEqual<C>(
_ other: C, by areEquivalent: (Element, C.Element) throws -> Bool
) rethrows -> Bool where C : OrderedCollection
}
extension OrderedCollection {
public func difference<C>(
from other: C, by areEquivalent: (Element, C.Element) -> Bool
) -> OrderedCollectionDifference<Element>
where C : OrderedCollection, C.Element == Self.Element
}
extension OrderedCollection where Element: Equatable {
public func difference<C>(from other: C) -> OrderedCollectionDifference<Element>
where C: OrderedCollection, C.Element == Self.Element
public func elementsEqual<C>(_ other: C) -> Bool
where C : OrderedCollection, C.Element == Element
}
extension BidirectionalCollection : OrderedCollection {}
extension CountingIndexCollection : OrderedCollection where Base : OrderedCollection {}
extension Slice : OrderedCollection where Base : OrderedCollection {}
extension UnsafeMutableRawBufferPointer : OrderedCollection {}
extension UnsafeRawBufferPointer : OrderedCollection {}
The difference(from:) method produces an instance of a new type, OrderedCollectionDifference:
@available(swift, introduced: 5.1)
public struct OrderedCollectionDifference<ChangeElement> {
public enum Change {
case insert(offset: Int, element: ChangeElement, associatedWith: Int?)
case remove(offset: Int, element: ChangeElement, associatedWith: Int?)
}
public init?<C: Collection>(_ c: C) where C.Element == Change
public var insertions: [Change] { get }
public var removals: [Change] { get }
}
extension OrderedCollectionDifference : Collection {
public typealias Element = OrderedCollectionDifference<ChangeElement>.Change
public struct Index: Comparable, Hashable {}
}
extension OrderedCollectionDifference.Change: Equatable where ChangeElement: Equatable {}
extension OrderedCollectionDifference: Equatable where ChangeElement: Equatable {}
extension OrderedCollectionDifference.Change: Hashable where ChangeElement: Hashable {}
extension OrderedCollectionDifference: Hashable where ChangeElement: Hashable {
public func inferringMoves() -> OrderedCollectionDifference<ChangeElement>
}
extension OrderedCollectionDifference: Codable where ChangeElement: Codable {}
A difference could be applied to any compatible instance of RangeReplaceableCollection:
extension RangeReplaceableCollection {
@available(swift, introduced: 5.1)
public func applying(_ difference: OrderedCollectionDifference<Element>) -> Self?
}
There's a more complete proposal (including headerdocs) posted as a PR on swift-evolution, and a working prototype is available as a Swift package for anyone who's interested in experimenting with the API.