# [swift-evolution] Proposal: Implement a rotate algorithm, equivalent to std::rotate() in C++

Sergey Bolshedvorsky sergey at bolshedvorsky.com
Mon Dec 14 05:59:40 CST 2015

```
There are 3 main algorithms: forward iteration, random access iteration and bidirectional iteration. All excerpts from the book Alexander A. Stepanov. “From Mathematics to Generic Programming”, Chapters 11.3 - 11.6

1. The forward iteration can be implemented by using Gries-Mills algorithm. This algorithm returns a new middle: a position where the first element moved.

template <ForwardIterator I>
I rotate(I f, I m, I l, std::forward_iterator_tag) {
if (f == m) return l;
if (m == l) return f;
pair<I, I> p = swap_ranges(f, m, m, l);
while (p.first != m || p.second != l) {
if (p.second == l) {
rotate_unguarded(p.first, m, l);
return p.first;
}
f = m;
m = p.second;
p = swap_ranges(f, m, m, l);
}
return m;
}

2. The random access iteration can be implement in this way:

template <RandomAccessIterator I>
I rotate(I f, I m, I l, std::random_access_iterator_tag) {
if (f == m) return l;
if (m == l) return f;
DifferenceType<I> cycles = gcd(m - f, l - m);
rotate_transform<I> rotator(f, m, l);
while (cycles-- > 0) rotate_cycle_from(f + cycles, rotator);
return rotator.m1;
}

3. The bidirectional iteration can be implement by using reverse algorithm in this way:

template <BidirectionalIterator I>
I rotate(I f, I m, I l, bidirectional_iterator_tag) {
reverse(f, m);
reverse(m, l);
pair<I, I> p = reverse_until(f, m, l);
reverse(p.first, p.second);
if (m == p.first) return p.second;
return p.first;
}

We need to hide the complexity of these algorithms, therefore we need to write a simple version that works for any type of iterations.

Shall I create a formal PR to swift-evolution with a proposed solution and detailed design?

Sergey

> On 14 Dec 2015, at 08:51, Dave Abrahams <dabrahams at apple.com> wrote:
>
>>
>> On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>
>> Hi everyone,
>>
>> I’ve selected a ticket SR-125 as my first task (https://bugs.swift.org/browse/SR-125 <https://bugs.swift.org/browse/SR-125>).
>>
>> I would like to propose an implementation of this method in Swift stdlib.
>>
>> std::rotate() method performs a left rotation on a range of elements.
>> C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
>> Specifically, it swaps the elements in the range [first, last) in such a way that the element middle becomes the first element of the new range and middle - 1 becomes the last element.
>> A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.
>>