<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Dec 14, 2015, at 3:59 AM, Sergey Bolshedvorsky &lt;<a href="mailto:sergey@bolshedvorsky.com" class="">sergey@bolshedvorsky.com</a>&gt; wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class="">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 class=""><br class=""></div><div class=""><br class=""></div><div class="">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.&nbsp;</div><div class=""><br class=""></div><div class=""><div class=""><font face="Menlo" class="">template &lt;ForwardIterator I&gt;</font></div><div class=""><font face="Menlo" class="">I rotate(I f, I m, I l, std::forward_iterator_tag) {</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; if (f == m) return l;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; if (m == l) return f;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; pair&lt;I, I&gt; p = swap_ranges(f, m, m, l);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; while (p.first != m || p.second != l) {</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp; &nbsp; if (p.second == l) {</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; rotate_unguarded(p.first, m, l);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return p.first;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp; &nbsp; }</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp; &nbsp; f = m;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp; &nbsp; m = p.second;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp; &nbsp; p = swap_ranges(f, m, m, l);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; }</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; return m;</font></div><div class=""><font face="Menlo" class="">}</font></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">2. The random access iteration can be implement in this way:</div><div class=""><br class=""></div><div class=""><div class=""><font face="Menlo" class="">template &lt;RandomAccessIterator I&gt;</font></div><div class=""><font face="Menlo" class="">I rotate(I f, I m, I l, std::random_access_iterator_tag) {</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; if (f == m) return l;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; if (m == l) return f;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; DifferenceType&lt;I&gt; cycles = gcd(m - f, l - m);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; rotate_transform&lt;I&gt; rotator(f, m, l);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; while (cycles-- &gt; 0) rotate_cycle_from(f + cycles, rotator);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; return rotator.m1;</font></div><div class=""><font face="Menlo" class="">}</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><div class="">3. The bidirectional iteration can be implement by using reverse algorithm in this way:</div><div class=""><br class=""></div><div class=""><div class=""><div class=""><font face="Menlo" class="">template &lt;BidirectionalIterator I&gt;</font></div><div class=""><font face="Menlo" class="">I rotate(I f, I m, I l, bidirectional_iterator_tag) {</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp;reverse(f, m);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp;reverse(m, l);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp;pair&lt;I, I&gt; p = reverse_until(f, m, l);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp;reverse(p.first, p.second);</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp;if (m == p.first) return p.second;</font></div><div class=""><font face="Menlo" class="">&nbsp; &nbsp; &nbsp;return p.first;</font></div><div class=""><font face="Menlo" class="">}</font></div><div class=""><br class=""></div></div><div class=""><div class=""><br class=""></div></div><div class="">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 class=""><br class=""></div><div class="">Shall I create a formal PR to swift-evolution with a proposed solution and detailed design?</div></div></div></div></div></div></div></blockquote><div><br class=""></div>Yes, please!</div><div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><div class=""><div class=""><br class=""></div></div></div><div class="">Sergey</div><div class=""><br class=""></div><br class=""><div class=""><blockquote type="cite" class=""><div class="">On 14 Dec 2015, at 08:51, Dave Abrahams &lt;<a href="mailto:dabrahams@apple.com" class="">dabrahams@apple.com</a>&gt; wrote:</div><br class="Apple-interchange-newline"><div class=""><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class="Apple-interchange-newline">On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>&gt; wrote:<br class=""><br class="">Hi everyone,<br class=""><br class="">I’ve selected a ticket SR-125 as my first task (<a href="https://bugs.swift.org/browse/SR-125" class="">https://bugs.swift.org/browse/SR-125</a>).<br class=""><br class="">I would like to propose an implementation of this method in Swift stdlib.<br class=""><br class="">std::rotate() method performs a left rotation on a range of elements.<br class="">C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)<br class="">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 class="">A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.<br class=""><br class="">What are your thoughts?<br class=""></blockquote><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">This is a really important algorithm, with applications even in GUI programming (see&nbsp;<a href="http://www.bfilipek.com/2014/12/top-5-beautiful-c-std-algorithms.html#slide" class="">slide</a>&nbsp;and&nbsp;<a href="http://www.bfilipek.com/2014/12/top-5-beautiful-c-std-algorithms.html#gather" class="">gather</a>), so I'm really happy someone is taking it on. You'll need different implementations&nbsp;<a href="http://stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast" class="">depending on the index's protocol conformance</a>. &nbsp;C++ implementations can get&nbsp;<a href="http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&amp;pathrev=251836" class="">pretty sophisticated</a>. &nbsp;Would you like additional thoughts (and if so, of what nature), or will those do? ;-)</div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="">-Dave</div></div></div></blockquote></div><br class=""></div></div></blockquote></div><br class=""><div class="">
-Dave<div class=""><br class=""></div><br class="Apple-interchange-newline">

</div>
<br class=""></body></html>