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 <[email protected]> wrote: > >> >> On Dec 14, 2015, at 3:59 AM, Sergey Bolshedvorsky <[email protected] >> <mailto:[email protected]>> 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 <[email protected] >>> <mailto:[email protected]>> wrote: >>> >>>> >>>> On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution >>>> <[email protected] <mailto:[email protected]>> 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
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
