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

[Nate Cook]

> On May 6, 2016, at 12:35 AM, Dmitri Gribenko <gribozavr at gmail.com> wrote:
> 
> On Thu, May 5, 2016 at 5:11 PM, Nate Cook <natecook at gmail.com <mailto:natecook at gmail.com>> wrote:
>> Thanks for the feedback, Dmitri &co, this all looks excellent! I'll work on updating the proposal.
>> 
>>> On May 5, 2016, at 6:13 PM, Dmitri Gribenko <gribozavr at gmail.com> wrote:
>>> 
>>> On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution
>>> <swift-evolution at swift.org> wrote:
>>>> Hello Swift community,
>>>> 
>>>> The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.
>>> 
>>> Hi,
>>> 
>>> I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
>>> myself.  We met and discussed the proposal in great detail.
>>> 
>>> First of all, we want to thank Nate and Sergey for proposing this API,
>>> which is an important and useful algorithm.  We are generally in favor
>>> of the proposal, but we would like to request a few changes.
>>> 
>>> Could you make 'func rotate' a requirement in the MutableCollection
>>> protocol?  This allows selecting the best implementation for a given
>>> concrete type, even when calling from generic code.
>>> 
>>> Could you explain why do we need a special implementation of
>>> 'reverse()' for RandomAccessCollection?  We couldn't think of a
>>> performance reason for this.
>> 
>> With a bidirectional collection, you have to compare the high and low index at each iteration, stopping when low >= high (before indices were Comparable, this required two equality comparisons per iteration). With a random-access collection, you can optimize the loop to use a fixed number of iterations, which should be more efficient.
> 
> Good point!  In that case, 'reverse()' should also be a protocol
> requirement, to allow dispatch to the most efficient version.

That brings up the question of which protocol to add the requirement to? Without a MutableBidirectionalProtocol (which we don't want, right?), we'd need to add it to MutableCollection. While a mutating reverse() is possible for a forward collection, it has significant space complexity, since it works either by creating an array of the indices or through recursion. We would also have reverse() available on some collections that don't have reversed(). Does that sound alright?

> Dmitri
> 
> -- 
> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com <mailto:gribozavr at gmail.com>>*/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160506/22bf0cfd/attachment.html>