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

[Nate Cook]

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.

> Could you add complexity clauses to all new documentation comments?
> 
> We have discussed the names for these functions at length.  We felt
> like the argument in 'rotate(firstFrom:)' does not convey the
> argument's role well.  Our suggestion is to use
> 'rotate(shiftingToStart:)' and 'rotated(shiftingToStart:)'.  These
> names emphasize that methods operate on the whole collection, shifting
> all elements.  The argument is the index of the element that is moved
> to the start index, and we tried to convey that by using the word
> 'start' instead of 'first'.  In the standard library, 'first' refers
> to the element itself, not the index.  Indices use 'startIndex' and
> 'endIndex'.
> 
> We have considered a lot of alternative names, including
> 'swapSubranges(boundedBy:)', 'rewind', 'splitAndSwap', 'swapHalves'
> and others, but they were not as good.  The problems are:
> 
> - 'swapSubranges' is mostly good, but 'subranges' does not imply that
> the two subranges cover the whole collection.  The user might
> reasonably expect to pass two subranges that will be swapped.
> 
> - 'Half' implies that two parts make a whole, but it also implies that
> two parts are of equal size, which is not the case for this API.
> 
> - 'splitAndSwap' implies that we are operating on the whole, but feels
> a very roundabout way to describe the operation.

Agreed on all of this. The rotate name is hard to beat!

> For a non-mutating rotation we suggest defining separate types,
> RotatedCollection, RotatedBidirectionalCollection, and
> RotatedRandomAccessCollection, instead of returning a
> FlattenCollection.  This has a few advantages.
> 
> - We can change the non-mutating 'rotated()' to just return the
> collection instead of returning tuples of the collection and the
> index.  The index of the former first element can be stored inside the
> RotatedCollection in a property.  This change allows easier chaining
> on '.rotated()', and goes in line with the return value of the
> mutating 'rotate()' being discardable.
> 
> - Using an array in the return type of 'rotated()'
> (FlattenCollection<[Self.SubSequence]>) would be less efficient than
> it could be (extra allocation), and also feels like exposing too many
> implementation details that we might want to change in future (for
> example, if we get a CollectionOfTwo type).
> 
> - In future, when we have conditional protocol conformances in the
> language, we would fold the three RotatedCollection types into one
> type that conditionally conforms to collection protocols based on the
> capabilities of the underlying collection.  We won't be able to do
> that if some overloads return a FlattenCollection.
> 
> For lazy 'rotated()', just like for non-mutating 'rotated()', we
> recommend returning only one value, a LazyCollection that wraps an
> appropriate RotatedCollection.  The RotatedCollection will store the
> index of the former first element in a property.
> 
> 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>*/