diff options
Diffstat (limited to 'src/liballoc/collections/vec_deque.rs')
| -rw-r--r-- | src/liballoc/collections/vec_deque.rs | 126 |
1 files changed, 113 insertions, 13 deletions
diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index 0c5926fbaf1..b3f7ef5fd6e 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -1,13 +1,3 @@ -// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - //! A double-ended queue implemented with a growable ring buffer. //! //! This queue has `O(1)` amortized inserts and removals from both ends of the @@ -1897,8 +1887,6 @@ impl<T> VecDeque<T> { /// # Examples /// /// ``` - /// #![feature(vec_resize_with)] - /// /// use std::collections::VecDeque; /// /// let mut buf = VecDeque::new(); @@ -1917,7 +1905,7 @@ impl<T> VecDeque<T> { /// buf.resize_with(5, || { state += 1; state }); /// assert_eq!(buf, [5, 10, 101, 102, 103]); /// ``` - #[unstable(feature = "vec_resize_with", issue = "41758")] + #[stable(feature = "vec_resize_with", since = "1.33.0")] pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut()->T) { let len = self.len(); @@ -1927,6 +1915,118 @@ impl<T> VecDeque<T> { self.truncate(new_len); } } + + /// Rotates the double-ended queue `mid` places to the left. + /// + /// Equivalently, + /// - Rotates item `mid` into the first position. + /// - Pops the first `mid` items and pushes them to the end. + /// - Rotates `len() - mid` places to the right. + /// + /// # Panics + /// + /// If `mid` is greater than `len()`. Note that `mid == len()` + /// does _not_ panic and is a no-op rotation. + /// + /// # Complexity + /// + /// Takes `O(min(mid, len() - mid))` time and no extra space. + /// + /// # Examples + /// + /// ``` + /// #![feature(vecdeque_rotate)] + /// + /// use std::collections::VecDeque; + /// + /// let mut buf: VecDeque<_> = (0..10).collect(); + /// + /// buf.rotate_left(3); + /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]); + /// + /// for i in 1..10 { + /// assert_eq!(i * 3 % 10, buf[0]); + /// buf.rotate_left(3); + /// } + /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); + /// ``` + #[unstable(feature = "vecdeque_rotate", issue = "56686")] + pub fn rotate_left(&mut self, mid: usize) { + assert!(mid <= self.len()); + let k = self.len() - mid; + if mid <= k { + unsafe { self.rotate_left_inner(mid) } + } else { + unsafe { self.rotate_right_inner(k) } + } + } + + /// Rotates the double-ended queue `k` places to the right. + /// + /// Equivalently, + /// - Rotates the first item into position `k`. + /// - Pops the last `k` items and pushes them to the front. + /// - Rotates `len() - k` places to the left. + /// + /// # Panics + /// + /// If `k` is greater than `len()`. Note that `k == len()` + /// does _not_ panic and is a no-op rotation. + /// + /// # Complexity + /// + /// Takes `O(min(k, len() - k))` time and no extra space. + /// + /// # Examples + /// + /// ``` + /// #![feature(vecdeque_rotate)] + /// + /// use std::collections::VecDeque; + /// + /// let mut buf: VecDeque<_> = (0..10).collect(); + /// + /// buf.rotate_right(3); + /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]); + /// + /// for i in 1..10 { + /// assert_eq!(0, buf[i * 3 % 10]); + /// buf.rotate_right(3); + /// } + /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); + /// ``` + #[unstable(feature = "vecdeque_rotate", issue = "56686")] + pub fn rotate_right(&mut self, k: usize) { + assert!(k <= self.len()); + let mid = self.len() - k; + if k <= mid { + unsafe { self.rotate_right_inner(k) } + } else { + unsafe { self.rotate_left_inner(mid) } + } + } + + // Safety: the following two methods require that the rotation amount + // be less than half the length of the deque. + // + // `wrap_copy` requres that `min(x, cap() - x) + copy_len <= cap()`, + // but than `min` is never more than half the capacity, regardless of x, + // so it's sound to call here because we're calling with something + // less than half the length, which is never above half the capacity. + + unsafe fn rotate_left_inner(&mut self, mid: usize) { + debug_assert!(mid * 2 <= self.len()); + self.wrap_copy(self.head, self.tail, mid); + self.head = self.wrap_add(self.head, mid); + self.tail = self.wrap_add(self.tail, mid); + } + + unsafe fn rotate_right_inner(&mut self, k: usize) { + debug_assert!(k * 2 <= self.len()); + self.head = self.wrap_sub(self.head, k); + self.tail = self.wrap_sub(self.tail, k); + self.wrap_copy(self.tail, self.head, k); + } } impl<T: Clone> VecDeque<T> { |