> On Jan 1, 2016, at 2:28 PM, Sergey Bolshedvorsky <[email protected]>
> wrote:
>
> 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 */ {
Now that I look, “rotatingFirstFrom” might be better, since it makes it very
clear what middle does.
> // 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 {
These should be called “rotateFirstFrom.” The API guidelines are moving toward
dropping the InPlace convention where possible.
> // 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
> }
> }
I have heard one C++ stdlib developer argue that only two of these algorithms
are needed. I don’t know whether to believe him, but it might be worth doing
some benchmarks.
> 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.
> }
> }
I think maybe you want another version for bidirectional collections?
> Sergey
>
>
>> On 29 Dec 2015, at 23:27, Dave Abrahams <[email protected]
>> <mailto:[email protected]>> wrote:
>>
>>>
>>> On Dec 29, 2015, at 7:30 AM, Sergey Bolshedvorsky <[email protected]
>>> <mailto:[email protected]>> 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 <[email protected]
>>>> <mailto:[email protected]>> wrote:
>>>>
>>>> On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution
>>>> <[email protected] <mailto:[email protected]>> 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 <[email protected]
>>>> <mailto:[email protected]>>*/
>
-Dave
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
