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

[Sergey Bolshedvorsky]

Hi All,

I would like to clarify the API endpoints based on your feedback. Am I missing something?

extension CollectionType {
    @warn_unused_result
    public func rotatedAt(middle: Index) /* -> Return Type */ {
        // This should be handled by slicing and rotating a slice.
        // let result = c.flatten(CollectionOfTwo(c[midPoint..<c.endIndex], c[startIndex..<midPoint] ))
        // return (result, calculateIndexOfMidPoint())
    }
}

extension CollectionType where Index : ForwardIndexType {
    @warn_unused_result
    public mutating func rotatedInPlace(middle: Index) -> Index {
        // Implement ForwardIndexType algorithm
	// Return the index of the old start element
    }
}

extension CollectionType where Index : BidirectionalIndexType {
    @warn_unused_result
    public mutating func rotatedInPlace(middle: Index) -> Index {
        // Implement BidirectionalIndexType algorithm
	// Return the index of the old start element
    }
}

extension CollectionType where Index : RandomAccessIndexType {
    @warn_unused_result
    public mutating func rotatedInPlace(middle: Index) -> Index {
        // Implement RandomAccessIndexType algorithm
	// Return the index of the old start element
    }
}

extension LazyCollectionType {
    @warn_unused_result
    public func rotatedAt(middle: Index) /* -> Return Type */ {
        // Many of our eager algorithms for are implemented by copying lazy views to an array.
        // calculateIndexOfMidPoint can start out being O(N) if necessary; you should be able to add enough
        // API to the LazyFlattenCollection that you can synthesize the position more efficiently though.
    }
}

Sergey


> On 29 Dec 2015, at 23:27, Dave Abrahams <dabrahams at apple.com> wrote:
> 
>> 
>> On Dec 29, 2015, at 7:30 AM, Sergey Bolshedvorsky <sergey at bolshedvorsky.com <mailto: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 <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
> 
> This should be handled by slicing and rotating a slice. In-place slice mutation is not yet efficient, but we have an open radar asking for the necessary core language feature to make it so (non-pointer proxy addressors).
> 
>>> 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]
> 
> There should be an in-place rotation algorithm as well, and for both varieties we should have a way of getting back the index of the old start element in the rotated collection.  I would start with the in-place algorithms are likely more of a challenge.
> 
>> 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.
> 
> Err, I don’t think Dmitri pointed anything out; he merely asked you to consider performance.  But I must admit that I don’t understand the concern.  Many of our eager algorithms for are implemented by copying lazy views to an array.
> 
> Personally, I would implement a rotate as something like:
> 
> extension CollectionType {
>   func rotatedAt(midPoint: Index) -> /* Return type */{
>     let result = c.lazy.flatten([ c[midPoint..<c.endIndex], c[startIndex..<midPoint] ])
>     // or, for optimization, c.flatten(CollectionOfTwo(c[midPoint..<c.endIndex], c[startIndex..<midPoint] )) 
>     return (result, calculateIndexOfMidPoint())
>   }
> }  
> 
> calculateIndexOfMidPoint can start out being O(N) if necessary; you should be able to add enough API to the LazyFlattenCollection that you can synthesize the position more efficiently though.
> 
>> 
>> Sergey
>> 
>> 
>> 
>>> On 29 Dec 2015, at 06:38, Dmitri Gribenko <gribozavr at gmail.com <mailto:gribozavr at gmail.com>> wrote:
>>> 
>>> On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution <swift-evolution at swift.org <mailto: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 <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 <mailto:gribozavr at gmail.com>>*/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160101/064d7b3f/attachment.html>