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

[Dmitri Gribenko]

On Tue, Dec 29, 2015 at 5:30 PM, Sergey Bolshedvorsky
<sergey at bolshedvorsky.com> wrote:
> Hi Dmitri,
>
> Thank you for your feedback! I’ve updated a proposal based on your comments:
> https://github.com/apple/swift-evolution/pull/77
>
> What jumps at me immediately is that the APIs are using integers to specify
> positions in the collection.  I think they should be using collection's
> indices instead.
>
> Yes you are right, the APIs should use collection indexes.
>
> I'm unsure why we need `first` and `last` -- shouldn't the API operate on
> the whole collection?  We have slices to operate on subsequences.
>
> The C++ implementation allows to rotate all elements of collection or only
> some of them. A precondition of this function is that
> 0 <= first <= middle <= last < count

Right, but this question is relevant for every algorithm (sort,
partition, etc.).  That's why we have writeback through slices:

myArray[first..<last].sortInPlace()

instead of adding `first` and `last` to every algorithm.

Dmitri

> Another point to consider is how the call site of these functions looks
> like:
>
>
>  I’ve added 2 API usage examples to PR:
>
> Example of rotating all elements of the collection:
>
> let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
> let rotated = numbers.rotateFrom(0, middle: 3, last: 8)
> // rotated contains [4, 5, 6, 7, 8, 9, 1, 2, 3]
>
> Example of rotating some elements of the collection:
>
> let numbers = [10, 12, 13, 11, 15, 14]
> let rotated = numbers.rotateFrom(1, middle: 3, last: 4)
> // rotated contains [10, 11, 12, 13, 15, 14]
>
>
> It is interesting that you are proposing that the new algorithms should
> produce lazy views.  I agree this is consistent with the rest of the
> library, but I'm worried about the performance implications.  Have you
> thought about this?  One point to keep in mind is that you can implement the
> `_copyToNativeArrayBuffer()` and `_initializeTo()` entry points in all new
> lazy collections, using the optimal eager algorithm.  This way, converting
> them to arrays will be fast.
>
> Thanks for pointing out the performance issue with lazy views. I will draft
> the implementation of algorithms for regular collections at first and then I
> will think how it can be reused with lazy views.
>
> Sergey
>
>
>
> On 29 Dec 2015, at 06:38, Dmitri Gribenko <gribozavr at gmail.com> wrote:
>
> On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution
> <swift-evolution at swift.org> wrote:
>>
>> Hi all,
>>
>> I have created a PR with with a formal proposal for this feature:
>> https://github.com/apple/swift-evolution/pull/77
>>
>> What are your thoughts?
>
>
> Thank you for the proposal!
>
> What jumps at me immediately is that the APIs are using integers to specify
> positions in the collection.  I think they should be using collection's
> indices instead.
>
> I'm unsure why we need `first` and `last` -- shouldn't the API operate on
> the whole collection?  We have slices to operate on subsequences.
>
> It is interesting that you are proposing that the new algorithms should
> produce lazy views.  I agree this is consistent with the rest of the
> library, but I'm worried about the performance implications.  Have you
> thought about this?  One point to keep in mind is that you can implement the
> `_copyToNativeArrayBuffer()` and `_initializeTo()` entry points in all new
> lazy collections, using the optimal eager algorithm.  This way, converting
> them to arrays will be fast.
>
> Another point to consider is how the call site of these functions looks
> like:
>
> collection.rotate(10, middle: 20, last: 30)
>
> The first number hangs in the air, it is unclear what its meaning is.
>
> 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>*/
>
>



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