Add element-moving methods to MutableCollection

Evolution Pitches
1

Continuing the discussion from Add MutableCollection.swapRanges(_: Range<Index>, _: Range<Index>)?:

While writing the swapping methods, I realized that simple element movement would be defined in terms of swapping, and that there isn't currently any moving methods in MutableCollection. So the sample code includes moving methods. Should those be added to the Standard Library?

1 Like
2

What does move mean here? Is it move in the UnsafeMutablePointer sense? (Doesn't seem like it to me, and it's a pre-existing definition in Swift.) Apple Developer Documentation

3

That one seems nice :))
It would be awesome to have a rotated() method on the stdlib.
Few points here:

  • The rotated part was already discussed in SE-078. And it was based on the same cpp std::rotate() implementation.
  • Maybe it doesn't necessarily need to be eager. It could be a lazy view on top of a base collection.
  • Question: could swapRanges(Range<Index>) be changed to a generic swapRanges<R: RangeExpression>(_: R) where R.Bound == Index and use relative to collection on the implementation?
4

No, it's not in the sense of C++-11 move-semantics, like UnsafeMutablePointer.move. It's more of a removal and reinsertion, except it's on MutableCollection instead of RangeReplaceableCollection. If we move an element from second to tenth, we make an opening between the ninth and (current) tenth elements, made up by closing the gap between the first and third. All Index values between i and j, inclusive, get shifted, but all outside elements keep their index values.

5
  • The rotate methods I've provided are just placeholders until something official goes in.
  • I have a separate file with more rotation stuff, and it includes a lazy view. But I don't think that would be helpful for moves, because I don't think multiple moves stack in a non-compact fashion. (A rotation on a rotation can just store the truly base collection with the combined rotation.)
  • I just did your suggestion in the latest (i.e. second) version. And I renamed the single-move method.
1 Like
6

I don't think this would make a good addition to the library. Generally speaking, I don't think there's significant need for a single method to move a single element from one position to another as a one-off. When you want to do this, it's usually part of a bigger picture i.e. you are implementing an algorithm that moves various elements around in order to partition, rotate etc. But it would be a disaster to actually use this method in that case, because it is O(n), and you're likely to be using it in a loop. So best case, this is of marginal utility, and worst case, it encourages performance traps.

A solid list of real-world use cases of this method that don't involve repeated calls might be able to make the case.

2 Likes
7

The main version of the method moves a Range of elements; the single-element version just makes a single-unit range and calls the ranged version. But this only makes a difference if you're moving multiple elements in formation. Do you mean this? Or are you thinking of algorithms that move multiple elements that are scattered relative to each other?

8

I'm similarly skeptical of a range-based move operation – though it is at least a bit more general so less of a lift.

All these algorithms need to be justified by real-world use cases that would call for stand-alone move operations. Many use cases turn out to be more complex in practice. For example, dragging and dropping elements in a list UI would not use these operations, because most UIs allow you to select multiple discontiguous elements to drag, which are first gathered and then inserted.

9

Well the obvious use case is reordering items in a list/table in a UI.