This seems like the sort of think that a third-party library could supply. Have you considered making a new package for it yourself?<br><div class="gmail_quote"><div dir="ltr">On Mon, Dec 14, 2015 at 7:00 AM Sergey Bolshedvorsky via swift-evolution <<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><br></div><div><br></div><div>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</div><div><br></div><div><br></div><div>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. </div><div><br></div><div><div><font face="Menlo">template <ForwardIterator I></font></div><div><font face="Menlo">I rotate(I f, I m, I l, std::forward_iterator_tag) {</font></div><div><font face="Menlo"> if (f == m) return l;</font></div><div><font face="Menlo"> if (m == l) return f;</font></div><div><font face="Menlo"> pair<I, I> p = swap_ranges(f, m, m, l);</font></div><div><font face="Menlo"> while (p.first != m || p.second != l) {</font></div><div><font face="Menlo"> if (p.second == l) {</font></div><div><font face="Menlo"> rotate_unguarded(p.first, m, l);</font></div><div><font face="Menlo"> return p.first;</font></div><div><font face="Menlo"> }</font></div><div><font face="Menlo"> f = m;</font></div><div><font face="Menlo"> m = p.second;</font></div><div><font face="Menlo"> p = swap_ranges(f, m, m, l);</font></div><div><font face="Menlo"> }</font></div><div><font face="Menlo"> return m;</font></div><div><font face="Menlo">}</font></div><div><br></div><div><br></div><div>2. The random access iteration can be implement in this way:</div><div><br></div><div><div><font face="Menlo">template <RandomAccessIterator I></font></div><div><font face="Menlo">I rotate(I f, I m, I l, std::random_access_iterator_tag) {</font></div><div><font face="Menlo"> if (f == m) return l;</font></div><div><font face="Menlo"> if (m == l) return f;</font></div><div><font face="Menlo"> DifferenceType<I> cycles = gcd(m - f, l - m);</font></div><div><font face="Menlo"> rotate_transform<I> rotator(f, m, l);</font></div><div><font face="Menlo"> while (cycles-- > 0) rotate_cycle_from(f + cycles, rotator);</font></div><div><font face="Menlo"> return rotator.m1;</font></div><div><font face="Menlo">}</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo"><br></font></div><div><div>3. The bidirectional iteration can be implement by using reverse algorithm in this way:</div><div><br></div><div><div><div><font face="Menlo">template <BidirectionalIterator I></font></div><div><font face="Menlo">I rotate(I f, I m, I l, bidirectional_iterator_tag) {</font></div><div><font face="Menlo"> reverse(f, m);</font></div><div><font face="Menlo"> reverse(m, l);</font></div><div><font face="Menlo"> pair<I, I> p = reverse_until(f, m, l);</font></div><div><font face="Menlo"> reverse(p.first, p.second);</font></div><div><font face="Menlo"> if (m == p.first) return p.second;</font></div><div><font face="Menlo"> return p.first;</font></div><div><font face="Menlo">}</font></div><div><br></div></div><div><div><br></div></div><div>We need to hide the complexity of these algorithms, therefore we need to write a simple version that works for any type of iterations.</div><div><br></div><div>Shall I create a formal PR to swift-evolution with a proposed solution and detailed design?</div></div></div><div><br></div></div></div></div><div style="word-wrap:break-word"><div>Sergey</div></div><div style="word-wrap:break-word"><div><br></div><br><div><blockquote type="cite"><div>On 14 Dec 2015, at 08:51, Dave Abrahams <<a href="mailto:dabrahams@apple.com" target="_blank">dabrahams@apple.com</a>> wrote:</div><br><div><blockquote type="cite" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br>On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:<br><br>Hi everyone,<br><br>I’ve selected a ticket SR-125 as my first task (<a href="https://bugs.swift.org/browse/SR-125" target="_blank">https://bugs.swift.org/browse/SR-125</a>).<br><br>I would like to propose an implementation of this method in Swift stdlib.<br><br>std::rotate() method performs a left rotation on a range of elements.<br>C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)<br>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.<br>A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.<br><br>What are your thoughts?<br></blockquote><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">This is a really important algorithm, with applications even in GUI programming (see <a href="http://www.bfilipek.com/2014/12/top-5-beautiful-c-std-algorithms.html#slide" target="_blank">slide</a> and <a href="http://www.bfilipek.com/2014/12/top-5-beautiful-c-std-algorithms.html#gather" target="_blank">gather</a>), so I'm really happy someone is taking it on. You'll need different implementations <a href="http://stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast" target="_blank">depending on the index's protocol conformance</a>. C++ implementations can get <a href="http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836" target="_blank">pretty sophisticated</a>. Would you like additional thoughts (and if so, of what nature), or will those do? ;-)</div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div>-Dave</div></div></div></blockquote></div><br>
<img src="https://u2002410.ct.sendgrid.net/wf/open?upn=RVJ3oK8DhV2nk8GArr3gdANobsvHsf4-2FLojnVnW4LzZwFRv961-2BXmRfRhVi-2BXFuBwczW3J-2Fozwxro1L9Tt-2B35Z01FSwatOH7VdBcsacnFzpjJ78X3UiT4szmnkLNNRFqHMcVe4mOs9mlMu-2Bf505hLoOxa-2FrS3AVKrtr0lMeXaz2aE0MR6Iakkl1azjR-2FT36Zb2cXFdISmj26EIvSfecMkw-3D-3D" alt="" width="1" height="1" border="0" style="min-height:1px!important;width:1px!important;border-width:0!important;margin-top:0!important;margin-bottom:0!important;margin-right:0!important;margin-left:0!important;padding-top:0!important;padding-bottom:0!important;padding-right:0!important;padding-left:0!important">
</div>
_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</blockquote></div>