# \[Review\] SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++

**URL:** <https://forums.swift.org/t/review-se-0078-implement-a-rotate-algorithm-equivalent-to-std-rotate-in-c/2440>\
**Category:** Announcements\
**Created:** [May 4, 2016, 3:57am UTC](https://forums.swift.org/t/review-se-0078-implement-a-rotate-algorithm-equivalent-to-std-rotate-in-c/2440 "2016-05-04T03:57:34Z")\
**Posts on this page:** 1\
**Showing post:** 3

<div class="post-metadata">

**Author:** ![gribozavr](https://avatars.discourse-cdn.com/v4/letter/g/65b543/32.png) [@gribozavr](https://forums.swift.org/u/gribozavr)\
**Post date:** [May 5, 2016, 11:13pm UTC](https://forums.swift.org/t/review-se-0078-implement-a-rotate-algorithm-equivalent-to-std-rotate-in-c/2440/3 "2016-05-05T23:13:33Z")

</div>

Hi,

I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and  
myself. We met and discussed the proposal in great detail.

First of all, we want to thank Nate and Sergey for proposing this API,  
which is an important and useful algorithm. We are generally in favor  
of the proposal, but we would like to request a few changes.

Could you make 'func rotate' a requirement in the MutableCollection  
protocol? This allows selecting the best implementation for a given  
concrete type, even when calling from generic code.

Could you explain why do we need a special implementation of  
'reverse()' for RandomAccessCollection? We couldn't think of a  
performance reason for this.

Could you add complexity clauses to all new documentation comments?

We have discussed the names for these functions at length. We felt  
like the argument in 'rotate(firstFrom:)' does not convey the  
argument's role well. Our suggestion is to use  
'rotate(shiftingToStart:)' and 'rotated(shiftingToStart:)'. These  
names emphasize that methods operate on the whole collection, shifting  
all elements. The argument is the index of the element that is moved  
to the start index, and we tried to convey that by using the word  
'start' instead of 'first'. In the standard library, 'first' refers  
to the element itself, not the index. Indices use 'startIndex' and  
'endIndex'.

We have considered a lot of alternative names, including  
'swapSubranges(boundedBy:)', 'rewind', 'splitAndSwap', 'swapHalves'  
and others, but they were not as good. The problems are:

- 'swapSubranges' is mostly good, but 'subranges' does not imply that  
the two subranges cover the whole collection. The user might  
reasonably expect to pass two subranges that will be swapped.

- 'Half' implies that two parts make a whole, but it also implies that  
two parts are of equal size, which is not the case for this API.

- 'splitAndSwap' implies that we are operating on the whole, but feels  
a very roundabout way to describe the operation.

For a non-mutating rotation we suggest defining separate types,  
RotatedCollection, RotatedBidirectionalCollection, and  
RotatedRandomAccessCollection, instead of returning a  
FlattenCollection. This has a few advantages.

- We can change the non-mutating 'rotated()' to just return the  
collection instead of returning tuples of the collection and the  
index. The index of the former first element can be stored inside the  
RotatedCollection in a property. This change allows easier chaining  
on '.rotated()', and goes in line with the return value of the  
mutating 'rotate()' being discardable.

- Using an array in the return type of 'rotated()'  
(FlattenCollection\<[Self.SubSequence]\>) would be less efficient than  
it could be (extra allocation), and also feels like exposing too many  
implementation details that we might want to change in future (for  
example, if we get a CollectionOfTwo type).

- In future, when we have conditional protocol conformances in the  
language, we would fold the three RotatedCollection types into one  
type that conditionally conforms to collection protocols based on the  
capabilities of the underlying collection. We won't be able to do  
that if some overloads return a FlattenCollection.

For lazy 'rotated()', just like for non-mutating 'rotated()', we  
recommend returning only one value, a LazyCollection that wraps an  
appropriate RotatedCollection. The RotatedCollection will store the  
index of the former first element in a property.

Dmitri

> **···**
>
> On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution \<swift-evolution@swift.org\> wrote:
> 
> > Hello Swift community,
> > 
> > The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.
> 
> --  
> main(i,j){for(i=2;;i++){for(j=2;j\<i;j++){if(!(i%j)){j=0;break;}}if  
> (j){printf("%d\n",i);}}} /\*Dmitri Gribenko \<gribozavr@gmail.com\>\*/

---

_[View the full topic](https://forums.swift.org/t/review-se-0078-implement-a-rotate-algorithm-equivalent-to-std-rotate-in-c/2440)._