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

[Dmitri Gribenko]

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.

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.

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>*/