Proposal: Implement a rotate algorithm, equivalent to std::rotate() in C++

Sergey_Bolshedvorsky · December 13, 2015, 10:20am

Hi everyone,

I’ve selected a ticket SR-125 as my first task (https://bugs.swift.org/browse/SR-125\).

I would like to propose an implementation of this method in Swift stdlib.

std::rotate() method performs a left rotation on a range of elements.
C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
Specifically, it swaps the elements in the range [first, last) in such a way that the element middle becomes the first element of the new range and middle - 1 becomes the last element.
A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.

What are your thoughts?

Sergey

dabrahams · December 14, 2015, 8:51am

This is a really important algorithm, with applications even in GUI programming (see slide <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories; and gather <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories), so I'm really happy someone is taking it on. You'll need different implementations depending on the index's protocol conformance <c++ - Why is std::rotate so fast? - Stack Overflow. C++ implementations can get pretty sophisticated <http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836>\. Would you like additional thoughts (and if so, of what nature), or will those do? ;-)

-Dave

···

On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org> wrote:

Hi everyone,

I’ve selected a ticket SR-125 as my first task (https://bugs.swift.org/browse/SR-125\).

I would like to propose an implementation of this method in Swift stdlib.

std::rotate() method performs a left rotation on a range of elements.
C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
Specifically, it swaps the elements in the range [first, last) in such a way that the element middle becomes the first element of the new range and middle - 1 becomes the last element.
A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.

What are your thoughts?

Sergey_Bolshedvorsky · December 14, 2015, 11:59am

There are 3 main algorithms: forward iteration, random access iteration and bidirectional iteration. All excerpts from the book Alexander A. Stepanov. “From Mathematics to Generic Programming”, Chapters 11.3 - 11.6

1. The forward iteration can be implemented by using Gries-Mills algorithm. This algorithm returns a new middle: a position where the first element moved.

template <ForwardIterator I>
I rotate(I f, I m, I l, std::forward_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 pair<I, I> p = swap_ranges(f, m, m, l);
 while (p.first != m || p.second != l) {
 if (p.second == l) {
 rotate_unguarded(p.first, m, l);
 return p.first;
 }
 f = m;
 m = p.second;
 p = swap_ranges(f, m, m, l);
 }
 return m;
}

2. The random access iteration can be implement in this way:

template <RandomAccessIterator I>
I rotate(I f, I m, I l, std::random_access_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 DifferenceType cycles = gcd(m - f, l - m);
 rotate_transform rotator(f, m, l);
 while (cycles-- > 0) rotate_cycle_from(f + cycles, rotator);
 return rotator.m1;
}

3. The bidirectional iteration can be implement by using reverse algorithm in this way:

template <BidirectionalIterator I>
I rotate(I f, I m, I l, bidirectional_iterator_tag) {
 reverse(f, m);
 reverse(m, l);
 pair<I, I> p = reverse_until(f, m, l);
 reverse(p.first, p.second);
 if (m == p.first) return p.second;
 return p.first;
}

We need to hide the complexity of these algorithms, therefore we need to write a simple version that works for any type of iterations.

Shall I create a formal PR to swift-evolution with a proposed solution and detailed design?

Sergey

···

On 14 Dec 2015, at 08:51, Dave Abrahams <dabrahams@apple.com> wrote:

On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi everyone,

I’ve selected a ticket SR-125 as my first task (https://bugs.swift.org/browse/SR-125\).

I would like to propose an implementation of this method in Swift stdlib.

std::rotate() method performs a left rotation on a range of elements.
C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
Specifically, it swaps the elements in the range [first, last) in such a way that the element middle becomes the first element of the new range and middle - 1 becomes the last element.
A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.

What are your thoughts?

This is a really important algorithm, with applications even in GUI programming (see slide <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories; and gather <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories), so I'm really happy someone is taking it on. You'll need different implementations depending on the index's protocol conformance <c++ - Why is std::rotate so fast? - Stack Overflow. C++ implementations can get pretty sophisticated <http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836>\. Would you like additional thoughts (and if so, of what nature), or will those do? ;-)

-Dave

dabrahams · December 14, 2015, 3:48pm

There are 3 main algorithms: forward iteration, random access iteration and bidirectional iteration. All excerpts from the book Alexander A. Stepanov. “From Mathematics to Generic Programming”, Chapters 11.3 - 11.6

1. The forward iteration can be implemented by using Gries-Mills algorithm. This algorithm returns a new middle: a position where the first element moved.

template <ForwardIterator I>
I rotate(I f, I m, I l, std::forward_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 pair<I, I> p = swap_ranges(f, m, m, l);
 while (p.first != m || p.second != l) {
 if (p.second == l) {
 rotate_unguarded(p.first, m, l);
 return p.first;
 }
 f = m;
 m = p.second;
 p = swap_ranges(f, m, m, l);
 }
 return m;
}

2. The random access iteration can be implement in this way:

template <RandomAccessIterator I>
I rotate(I f, I m, I l, std::random_access_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 DifferenceType cycles = gcd(m - f, l - m);
 rotate_transform rotator(f, m, l);
 while (cycles-- > 0) rotate_cycle_from(f + cycles, rotator);
 return rotator.m1;
}

3. The bidirectional iteration can be implement by using reverse algorithm in this way:

template <BidirectionalIterator I>
I rotate(I f, I m, I l, bidirectional_iterator_tag) {
 reverse(f, m);
 reverse(m, l);
 pair<I, I> p = reverse_until(f, m, l);
 reverse(p.first, p.second);
 if (m == p.first) return p.second;
 return p.first;
}

We need to hide the complexity of these algorithms, therefore we need to write a simple version that works for any type of iterations.

Shall I create a formal PR to swift-evolution with a proposed solution and detailed design?

Yes, please!

Sergey

Hi everyone,

I’ve selected a ticket SR-125 as my first task (https://bugs.swift.org/browse/SR-125\).

I would like to propose an implementation of this method in Swift stdlib.

std::rotate() method performs a left rotation on a range of elements.
C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
Specifically, it swaps the elements in the range [first, last) in such a way that the element middle becomes the first element of the new range and middle - 1 becomes the last element.
A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.

What are your thoughts?

This is a really important algorithm, with applications even in GUI programming (see slide <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories; and gather <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories), so I'm really happy someone is taking it on. You'll need different implementations depending on the index's protocol conformance <c++ - Why is std::rotate so fast? - Stack Overflow. C++ implementations can get pretty sophisticated <http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836>\. Would you like additional thoughts (and if so, of what nature), or will those do? ;-)

-Dave

-Dave

···

On Dec 14, 2015, at 3:59 AM, Sergey Bolshedvorsky <sergey@bolshedvorsky.com> wrote:

On 14 Dec 2015, at 08:51, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

tal · December 14, 2015, 1:50pm

This seems like the sort of think that a third-party library could supply.
Have you considered making a new package for it yourself?

···

On Mon, Dec 14, 2015 at 7:00 AM Sergey Bolshedvorsky via swift-evolution < swift-evolution@swift.org> wrote:

There are 3 main algorithms: forward iteration, random access iteration
and bidirectional iteration. All excerpts from the book Alexander A.
Stepanov. “From Mathematics to Generic Programming”, Chapters 11.3 - 11.6

1. The forward iteration can be implemented by using Gries-Mills
algorithm. This algorithm returns a new middle: a position where the first
element moved.

template <ForwardIterator I>
I rotate(I f, I m, I l, std::forward_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 pair<I, I> p = swap_ranges(f, m, m, l);
 while (p.first != m || p.second != l) {
 if (p.second == l) {
 rotate_unguarded(p.first, m, l);
 return p.first;
 }
 f = m;
 m = p.second;
 p = swap_ranges(f, m, m, l);
 }
 return m;
}

2. The random access iteration can be implement in this way:

template <RandomAccessIterator I>
I rotate(I f, I m, I l, std::random_access_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 DifferenceType cycles = gcd(m - f, l - m);
 rotate_transform rotator(f, m, l);
 while (cycles-- > 0) rotate_cycle_from(f + cycles, rotator);
 return rotator.m1;
}

3. The bidirectional iteration can be implement by using reverse algorithm
in this way:

template <BidirectionalIterator I>
I rotate(I f, I m, I l, bidirectional_iterator_tag) {
 reverse(f, m);
 reverse(m, l);
 pair<I, I> p = reverse_until(f, m, l);
 reverse(p.first, p.second);
 if (m == p.first) return p.second;
 return p.first;
}

We need to hide the complexity of these algorithms, therefore we need to
write a simple version that works for any type of iterations.

Shall I create a formal PR to swift-evolution with a proposed solution and
detailed design?

Sergey

On 14 Dec 2015, at 08:51, Dave Abrahams <dabrahams@apple.com> wrote:

On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution < > swift-evolution@swift.org> wrote:

Hi everyone,

I’ve selected a ticket SR-125 as my first task (
https://bugs.swift.org/browse/SR-125\).

I would like to propose an implementation of this method in Swift stdlib.

std::rotate() method performs a left rotation on a range of elements.
C++ declaration is void rotate (ForwardIterator first, ForwardIterator
middle, ForwardIterator last)
Specifically, it swaps the elements in the range [first, last) in such a
way that the element middle becomes the first element of the new range and
middle - 1 becomes the last element.
A precondition of this function is that [first, n_first) and [middle,
last) are valid ranges.

What are your thoughts?

This is a really important algorithm, with applications even in GUI
programming (see slide
<Top 5 Beautiful C++ std Algorithms Examples - C++ Stories;
and gather
<Top 5 Beautiful C++ std Algorithms Examples - C++ Stories),
so I'm really happy someone is taking it on. You'll need different
implementations depending on the index's protocol conformance
<c++ - Why is std::rotate so fast? - Stack Overflow.
C++ implementations can get pretty sophisticated
<http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836>\.
Would you like additional thoughts (and if so, of what nature), or will
those do? ;-)

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Sergey_Bolshedvorsky · December 28, 2015, 8:29pm

Hi all,

I have created a PR with with a formal proposal for this feature: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

What are your thoughts?

Sergey

···

On 14 Dec 2015, at 15:48, Dave Abrahams <dabrahams@apple.com> wrote:

On Dec 14, 2015, at 3:59 AM, Sergey Bolshedvorsky <sergey@bolshedvorsky.com <mailto:sergey@bolshedvorsky.com>> wrote:

There are 3 main algorithms: forward iteration, random access iteration and bidirectional iteration. All excerpts from the book Alexander A. Stepanov. “From Mathematics to Generic Programming”, Chapters 11.3 - 11.6

1. The forward iteration can be implemented by using Gries-Mills algorithm. This algorithm returns a new middle: a position where the first element moved.

template <ForwardIterator I>
I rotate(I f, I m, I l, std::forward_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 pair<I, I> p = swap_ranges(f, m, m, l);
 while (p.first != m || p.second != l) {
 if (p.second == l) {
 rotate_unguarded(p.first, m, l);
 return p.first;
 }
 f = m;
 m = p.second;
 p = swap_ranges(f, m, m, l);
 }
 return m;
}

2. The random access iteration can be implement in this way:

template <RandomAccessIterator I>
I rotate(I f, I m, I l, std::random_access_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 DifferenceType cycles = gcd(m - f, l - m);
 rotate_transform rotator(f, m, l);
 while (cycles-- > 0) rotate_cycle_from(f + cycles, rotator);
 return rotator.m1;
}

3. The bidirectional iteration can be implement by using reverse algorithm in this way:

template <BidirectionalIterator I>
I rotate(I f, I m, I l, bidirectional_iterator_tag) {
 reverse(f, m);
 reverse(m, l);
 pair<I, I> p = reverse_until(f, m, l);
 reverse(p.first, p.second);
 if (m == p.first) return p.second;
 return p.first;
}

We need to hide the complexity of these algorithms, therefore we need to write a simple version that works for any type of iterations.

Shall I create a formal PR to swift-evolution with a proposed solution and detailed design?

Yes, please!

Sergey

On 14 Dec 2015, at 08:51, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi everyone,

I’ve selected a ticket SR-125 as my first task (https://bugs.swift.org/browse/SR-125\).

I would like to propose an implementation of this method in Swift stdlib.

std::rotate() method performs a left rotation on a range of elements.
C++ declaration is void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
Specifically, it swaps the elements in the range [first, last) in such a way that the element middle becomes the first element of the new range and middle - 1 becomes the last element.
A precondition of this function is that [first, n_first) and [middle, last) are valid ranges.

What are your thoughts?

This is a really important algorithm, with applications even in GUI programming (see slide <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories; and gather <Top 5 Beautiful C++ std Algorithms Examples - C++ Stories), so I'm really happy someone is taking it on. You'll need different implementations depending on the index's protocol conformance <c++ - Why is std::rotate so fast? - Stack Overflow. C++ implementations can get pretty sophisticated <http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836>\. Would you like additional thoughts (and if so, of what nature), or will those do? ;-)

-Dave

-Dave

fluidsonic · December 14, 2015, 2:19pm

This is a language restriction/limitation which libraries can't fix.

···

On Mon, Dec 14, 2015 at 2:50 PM, Tal Atlas via swift-evolution < swift-evolution@swift.org> wrote:

This seems like the sort of think that a third-party library could supply.
Have you considered making a new package for it yourself?
On Mon, Dec 14, 2015 at 7:00 AM Sergey Bolshedvorsky via swift-evolution < > swift-evolution@swift.org> wrote:

There are 3 main algorithms: forward iteration, random access iteration
and bidirectional iteration. All excerpts from the book Alexander A.
Stepanov. “From Mathematics to Generic Programming”, Chapters 11.3 - 11.6

1. The forward iteration can be implemented by using Gries-Mills
algorithm. This algorithm returns a new middle: a position where the first
element moved.

template <ForwardIterator I>
I rotate(I f, I m, I l, std::forward_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 pair<I, I> p = swap_ranges(f, m, m, l);
 while (p.first != m || p.second != l) {
 if (p.second == l) {
 rotate_unguarded(p.first, m, l);
 return p.first;
 }
 f = m;
 m = p.second;
 p = swap_ranges(f, m, m, l);
 }
 return m;
}

2. The random access iteration can be implement in this way:

template <RandomAccessIterator I>
I rotate(I f, I m, I l, std::random_access_iterator_tag) {
 if (f == m) return l;
 if (m == l) return f;
 DifferenceType cycles = gcd(m - f, l - m);
 rotate_transform rotator(f, m, l);
 while (cycles-- > 0) rotate_cycle_from(f + cycles, rotator);
 return rotator.m1;
}

3. The bidirectional iteration can be implement by using reverse
algorithm in this way:

template <BidirectionalIterator I>
I rotate(I f, I m, I l, bidirectional_iterator_tag) {
 reverse(f, m);
 reverse(m, l);
 pair<I, I> p = reverse_until(f, m, l);
 reverse(p.first, p.second);
 if (m == p.first) return p.second;
 return p.first;
}

We need to hide the complexity of these algorithms, therefore we need to
write a simple version that works for any type of iterations.

Shall I create a formal PR to swift-evolution with a proposed solution
and detailed design?

Sergey

On 14 Dec 2015, at 08:51, Dave Abrahams <dabrahams@apple.com> wrote:

On Dec 13, 2015, at 2:20 AM, Sergey Bolshedvorsky via swift-evolution < >> swift-evolution@swift.org> wrote:

Hi everyone,

I’ve selected a ticket SR-125 as my first task (
https://bugs.swift.org/browse/SR-125\).

I would like to propose an implementation of this method in Swift stdlib.

std::rotate() method performs a left rotation on a range of elements.
C++ declaration is void rotate (ForwardIterator first, ForwardIterator
middle, ForwardIterator last)
Specifically, it swaps the elements in the range [first, last) in such a
way that the element middle becomes the first element of the new range and
middle - 1 becomes the last element.
A precondition of this function is that [first, n_first) and [middle,
last) are valid ranges.

What are your thoughts?

This is a really important algorithm, with applications even in GUI
programming (see slide
<Top 5 Beautiful C++ std Algorithms Examples - C++ Stories;
and gather
<Top 5 Beautiful C++ std Algorithms Examples - C++ Stories),
so I'm really happy someone is taking it on. You'll need different
implementations depending on the index's protocol conformance
<c++ - Why is std::rotate so fast? - Stack Overflow.
C++ implementations can get pretty sophisticated
<http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?view=markup&pathrev=251836>\.
Would you like additional thoughts (and if so, of what nature), or will
those do? ;-)

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

gribozavr · December 29, 2015, 6:38am

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

···

On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution < swift-evolution@swift.org> wrote:

Hi all,

I have created a PR with with a formal proposal for this feature:
Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

What are your thoughts?

--
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@gmail.com>*/

Sergey_Bolshedvorsky · December 29, 2015, 3:30pm

Hi Dmitri,

Thank you for your feedback! I’ve updated a proposal based on your comments: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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

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@gmail.com> wrote:

On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Hi all,

I have created a PR with with a formal proposal for this feature: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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@gmail.com <mailto:gribozavr@gmail.com>>*/

dabrahams · December 29, 2015, 11:27pm

Hi Dmitri,

Thank you for your feedback! I’ve updated a proposal based on your comments: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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.

···

On Dec 29, 2015, at 7:30 AM, Sergey Bolshedvorsky <sergey@bolshedvorsky.com> wrote:

Sergey

On 29 Dec 2015, at 06:38, Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>> wrote:

On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Hi all,

I have created a PR with with a formal proposal for this feature: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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@gmail.com <mailto:gribozavr@gmail.com>>*/

gribozavr · December 29, 2015, 9:52pm

Hi Dmitri,

Thank you for your feedback! I’ve updated a proposal based on your comments:
Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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

···

On Tue, Dec 29, 2015 at 5:30 PM, Sergey Bolshedvorsky <sergey@bolshedvorsky.com> wrote:

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@gmail.com> wrote:

On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution > <swift-evolution@swift.org> wrote:

Hi all,

I have created a PR with with a formal proposal for this feature:
Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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@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@gmail.com>*/

Sergey_Bolshedvorsky · January 1, 2016, 10:28pm

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@apple.com> wrote:

On Dec 29, 2015, at 7:30 AM, Sergey Bolshedvorsky <sergey@bolshedvorsky.com <mailto:sergey@bolshedvorsky.com>> wrote:

Hi Dmitri,

Thank you for your feedback! I’ve updated a proposal based on your comments: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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@gmail.com <mailto:gribozavr@gmail.com>> wrote:

On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Hi all,

I have created a PR with with a formal proposal for this feature: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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@gmail.com <mailto:gribozavr@gmail.com>>*/

dabrahams · January 2, 2016, 2:51am

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

Hi Dmitri,

Thank you for your feedback! I’ve updated a proposal based on your comments: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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

Hi all,

I have created a PR with with a formal proposal for this feature: Proposal for adding rotate algorithm similar to std::rotate() by bolshedvorsky · Pull Request #77 · apple/swift-evolution · GitHub

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@gmail.com <mailto:gribozavr@gmail.com>>*/

-Dave

···

On Jan 1, 2016, at 2:28 PM, Sergey Bolshedvorsky <sergey@bolshedvorsky.com> wrote:

On 29 Dec 2015, at 23:27, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 29, 2015, at 7:30 AM, Sergey Bolshedvorsky <sergey@bolshedvorsky.com <mailto:sergey@bolshedvorsky.com>> wrote:

On 29 Dec 2015, at 06:38, Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>> wrote:
On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: