apple
Implement `move(fromOffsets:toOffset:)` and `remove(atOffsets:)`
SwiftUI defines MutableCollection.move(fromOffsets:toOffset:) and RangeReplaceableCollection.remove(atOffsets:) methods, which make it easy to interface with the onMove(perform:) and onDelete(perform:) view modifiers.
It'd be nice if the appropriate collections herein implemented the same functionality.
We've implemented both in our Identified Collections package, since the IdentifiedArray type is intended to be used in SwiftUI:
-
move(fromOffsets:toOffset:)https://github.com/pointfreeco/swift-identified-collections/blob/8eb04f22a74aa8b373468772baa12588b9404943/Sources/IdentifiedCollections/IdentifiedArray/IdentifiedArray%2BPartial%20MutableCollection.swift#L112-L134 -
remove(atOffsets:)https://github.com/pointfreeco/swift-identified-collections/blob/main/Sources/IdentifiedCollections/IdentifiedArray/IdentifiedArray%2BPartial%20RangeReplaceableCollection.swift#L151-L160
But it'd be nice to leverage more performant, upstream implementations on the OrderedDictionary it wraps instead.
Adopting these APIs as they are isn't going to work due to a layering violation: these methods use IndexSet, which is a Foundation type. (Swift Collections is intended to be a proving grounds for potential future stdlib additions, and the Swift stdlib sits below Foundation.)
Perhaps more importantly, though, this functionality is covered by SE-0270 RangeSet and Collection Operations. I don't like the idea of embracing alternative APIs to do the same thing -- I'd much rather see that proposal get out of preview limbo.
Note: SwiftUI's implementations of move(fromOffsets:toOffset:)/remove(atOffsets:) are based on partitioning algorithms, and they work in O(n * log(n)) and O(n) time, respectively. I highly recommend adopting the same approach for IdentifiedArray -- its current implementations are both quadratic.
Quick followup: I forgot to state above that this functionality would be very much desirable for both OrderedSet and OrderedDictionary.Elements -- the issue is simply that we should start by first implementing these for MutableCollection within the stdlib, and until we have decided how we go about it there, it would feel premature to add them to these two types.
SE-0270 is supposed to define the stdlib way of doing this; however, it did not exactly have a smooth ride on Swift Evolution, and while it is currently in preview, it's not yet officially part of the Standard Library. It's possible the SE-0270 APIs may change before they land there.
That said, there is no technical reason Swift Collections couldn't add a dependency on the swift-se0270-range-set package -- there is no layering violation there.
What gives me pause though is that I'd prefer not to get into the business of manually duplicating individual algorithms on OrderedSet/OrderedDictionary. Ideally these should all be generic over some new PermutableCollection protocol that sits between Collection and MutableCollection. (For remove(atOffsets:) we would also need a RangeRemovableCollection protocol.)
I think prototyping such extensions to the Collection hierarchy would be within the mandate of this package -- although such experiments could be tricky to maintain long term, so we should tread very carefully. (The public API of this package will very quickly ossify as more and more people start adding it as a dependency to their projects. It would be unfortunate if we would end up needing to forever maintain source compatibility with failed experiments.)
@lorentey Feel free to close this or convert to a discussion! And thanks for the suggestion of fixing our performance issue. We believe we've done so here: https://github.com/pointfreeco/swift-identified-collections/pull/16
I think it makes sense to leave this open, if only to remind us to revisit this once the dust has settled around RangeSet.
Re pointfreeco/swift-identified-collections#16: I suspect the move operation will need to use a stable partition, or the order of elements will be scrambled. 🤔
Re pointfreeco/swift-identified-collections#16: I suspect the move operation will need to use a stable partition, or the order of elements will be scrambled. 🤔
Ah thanks! I've instead cribbed the operations from SE-0270 for now: https://github.com/pointfreeco/swift-identified-collections/pull/17