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

[Sergey Bolshedvorsky]

Hi all,

I have created a PR with with a formal proposal for this feature: https://github.com/apple/swift-evolution/pull/77

What are your thoughts?

Sergey

> On 14 Dec 2015, at 15:48, Dave Abrahams <dabrahams at apple.com> wrote:
> 
>> 
>> On Dec 14, 2015, at 3:59 AM, Sergey Bolshedvorsky <sergey at bolshedvorsky.com <mailto:sergey at bolshedvorsky.com>> wrote:
>> 
>> 
>> 
>> 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?
> 
> Yes, please!
> 
>> 
>> Sergey
>> 
>> 
>>> On 14 Dec 2015, at 08:51, Dave Abrahams <dabrahams at apple.com <mailto: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.
>>>> 
>>>> What are your thoughts?
>>> 
>>> This is a really important algorithm, with applications even in GUI programming (see slide <http://www.bfilipek.com/2014/12/top-5-beautiful-c-std-algorithms.html#slide> and gather <http://www.bfilipek.com/2014/12/top-5-beautiful-c-std-algorithms.html#gather>), so I'm really happy someone is taking it on. You'll need different implementations depending on the index's protocol conformance <http://stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast>.  C++ implementations can get pretty sophisticated <http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836>.  Would you like additional thoughts (and if so, of what nature), or will those do? ;-)
>>> 
>>> 
>>> -Dave
>> 
> 
> -Dave

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151228/8b1a194c/attachment.html>