Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for VecDeque::rotate_{left|right} (feature vecdeque_rotate) #56686

Closed
DutchGhost opened this issue Dec 10, 2018 · 10 comments

Comments

Projects
None yet
7 participants
@DutchGhost
Copy link
Contributor

commented Dec 10, 2018

Currently if you want to rotate a VecDeque n elements to the left or right, you'd have to write something like this:

use std::collections::VecDeque;

fn main() {
    let mut v = (0..10).collect::<VecDeque<_>>();
    
    println!("{:?}", v); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    // rotate left by 2,
    for _ in 0..2 {
        if let Some(popped_front) = v.pop_front() {
            v.push_back(popped_front);
        }
    }
    
    println!("{:?}", v); // [2, 3, 4, 5, 6, 7, 8, 9, 0, 1]
    
    // rotate right by 4
    for _ in 0..4 {
        if let Some(popped_back) = v.pop_back() {
            v.push_front(popped_back);
        }
    }
    
    println!("{:?}", v); //[8, 9, 0, 1, 2, 3, 4, 5, 6, 7]
    
}

I wonder if it would be possible to add 2 functions:

  • rotate_left(mid: usize)
  • rotate_right(mid: usize)

You then only have to write:

use std::collections::VecDeque;

fn main() {
    let mut v = (0..10).collect::<VecDeque<_>>();
    
    println!("{:?}", v); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    // rotate left by 2,
    v.rotate_left(2)
    println!("{:?}", v); // [2, 3, 4, 5, 6, 7, 8, 9, 0, 1]
    
    // rotate right by 4
    v.rotate_right(4);
    
    println!("{:?}", v); //[8, 9, 0, 1, 2, 3, 4, 5, 6, 7]
    
}

This would be equal to slice's rotate_left and rotate_right.
It could probably be implemented on a lower level than with pop's and pushes for a little more efficiency.

@scottmcm

This comment has been minimized.

Copy link
Member

commented Dec 15, 2018

Ooh, I like this -- VecDeque is a circular buffer internally, so it should be doable with just a single at most two ptr::copy. EDIT: PR #56842

@scottmcm scottmcm changed the title VecDeque rotation Tracking issue for VecDeque::rotate_{left|right} (feature vecdeque_rotate) Dec 20, 2018

@scottmcm

This comment has been minimized.

Copy link
Member

commented Dec 20, 2018

PR is r+'d, so I turned this into a tracking issue.

pietroalbini added a commit to pietroalbini/rust that referenced this issue Dec 20, 2018

Rollup merge of rust-lang#56842 - scottmcm:vecdeque-rotate, r=alexcri…
…chton

Add unstable VecDeque::rotate_{left|right}

Like the ones on slices, but more efficient because vecdeque is a circular buffer.

Issue that proposed this: rust-lang#56686

~~💣 Please someone look very carefully at the `unsafe` in this!  The `wrap_copy` seems to be exactly what this method needs, and the `len` passed to it is never more than half the length of the deque, but I haven't managed to prove to myself that it's correct 💣~~ I think I proved that this code meets the requirement of the unsafe code it's calling; please double-check, of course.

bors added a commit that referenced this issue Dec 20, 2018

Auto merge of #56842 - scottmcm:vecdeque-rotate, r=alexcrichton
Add unstable VecDeque::rotate_{left|right}

Like the ones on slices, but more efficient because vecdeque is a circular buffer.

Issue that proposed this: #56686

~~💣 Please someone look very carefully at the `unsafe` in this!  The `wrap_copy` seems to be exactly what this method needs, and the `len` passed to it is never more than half the length of the deque, but I haven't managed to prove to myself that it's correct 💣~~ I think I proved that this code meets the requirement of the unsafe code it's calling; please double-check, of course.

pietroalbini added a commit to pietroalbini/rust that referenced this issue Dec 21, 2018

Rollup merge of rust-lang#56842 - scottmcm:vecdeque-rotate, r=alexcri…
…chton

Add unstable VecDeque::rotate_{left|right}

Like the ones on slices, but more efficient because vecdeque is a circular buffer.

Issue that proposed this: rust-lang#56686

~~💣 Please someone look very carefully at the `unsafe` in this!  The `wrap_copy` seems to be exactly what this method needs, and the `len` passed to it is never more than half the length of the deque, but I haven't managed to prove to myself that it's correct 💣~~ I think I proved that this code meets the requirement of the unsafe code it's calling; please double-check, of course.

Centril added a commit to Centril/rust that referenced this issue Dec 22, 2018

Rollup merge of rust-lang#56842 - scottmcm:vecdeque-rotate, r=alexcri…
…chton

Add unstable VecDeque::rotate_{left|right}

Like the ones on slices, but more efficient because vecdeque is a circular buffer.

Issue that proposed this: rust-lang#56686

~~💣 Please someone look very carefully at the `unsafe` in this!  The `wrap_copy` seems to be exactly what this method needs, and the `len` passed to it is never more than half the length of the deque, but I haven't managed to prove to myself that it's correct 💣~~ I think I proved that this code meets the requirement of the unsafe code it's calling; please double-check, of course.

bors added a commit that referenced this issue Dec 22, 2018

Auto merge of #56842 - scottmcm:vecdeque-rotate, r=alexcrichton
Add unstable VecDeque::rotate_{left|right}

Like the ones on slices, but more efficient because vecdeque is a circular buffer.

Issue that proposed this: #56686

~~💣 Please someone look very carefully at the `unsafe` in this!  The `wrap_copy` seems to be exactly what this method needs, and the `len` passed to it is never more than half the length of the deque, but I haven't managed to prove to myself that it's correct 💣~~ I think I proved that this code meets the requirement of the unsafe code it's calling; please double-check, of course.
@DutchGhost

This comment has been minimized.

Copy link
Contributor Author

commented Apr 17, 2019

I've since the feature replaced any code that used the pop - push technique with the rotate methods. This was fairly easy to do.

It's been a few months now, are there any issue's preventing this from landing stable?

@sfackler

This comment has been minimized.

Copy link
Member

commented May 1, 2019

@rfcbot fcp merge

@rfcbot

This comment has been minimized.

Copy link

commented May 1, 2019

Team member @sfackler has proposed to merge this. The next step is review by the rest of the tagged team members:

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

@rfcbot

This comment has been minimized.

Copy link

commented May 8, 2019

🔔 This is now entering its final comment period, as per the review above. 🔔

@WiSaGaN

This comment has been minimized.

Copy link
Contributor

commented May 14, 2019

Is "left" or "right" the word we want to use here? Previously we have deprecated trim_left (trim_right) of String in favor of trim_start and trim_end so that we do not assume the string is laid out from left to right. Here we seem to assume left is to front while right is to back? Are we able to use some words that express the front and back without assuming a left-to-right layout?

@DutchGhost

This comment has been minimized.

Copy link
Contributor Author

commented May 14, 2019

As discussed here, we have to use those names to stay consistent with the slice rotate_{left |right} methods #56842 (comment)

@WiSaGaN

This comment has been minimized.

Copy link
Contributor

commented May 14, 2019

@DutchGhost , sorry I missed that. That makes sense.

@rfcbot

This comment has been minimized.

Copy link

commented May 18, 2019

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

The RFC will be merged soon.

Centril added a commit to Centril/rust that referenced this issue May 19, 2019

Rollup merge of rust-lang#60678 - DutchGhost:master, r=scottmcm
Stabilize vecdeque_rotate

This PR stabilizes the vecdeque_rotate feature.
r? @scottmcm

Closes rust-lang#56686

@bors bors closed this in #60678 May 19, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.