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

[Tal Atlas]

This seems like the sort of think that a third-party library could supply.
Have you considered making a new package for it yourself?
On Mon, Dec 14, 2015 at 7:00 AM Sergey Bolshedvorsky via swift-evolution <
swift-evolution at swift.org> 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?
>
> 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> wrote:
>
> Hi everyone,
>
> I’ve selected a ticket SR-125 as my first task (
> 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
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151214/ae1d94ea/attachment.html>