]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
85aaf69f SL |
11 | //! VecDeque is a double-ended queue, which is implemented with the help of a |
12 | //! growing ring buffer. | |
13 | //! | |
14 | //! This queue has `O(1)` amortized inserts and removals from both ends of the | |
15 | //! container. It also has `O(1)` indexing like a vector. The contained elements | |
16 | //! are not required to be copyable, and the queue will be sendable if the | |
17 | //! contained type is sendable. | |
1a4d82fc | 18 | |
85aaf69f | 19 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 20 | |
1a4d82fc | 21 | use core::cmp::Ordering; |
1a4d82fc | 22 | use core::fmt; |
e9174d1e SL |
23 | use core::iter::{repeat, FromIterator}; |
24 | use core::mem; | |
1a4d82fc | 25 | use core::ops::{Index, IndexMut}; |
c1a9b12d | 26 | use core::ptr; |
c34b1796 | 27 | use core::slice; |
e9174d1e | 28 | use core::usize; |
1a4d82fc | 29 | |
85aaf69f | 30 | use core::hash::{Hash, Hasher}; |
85aaf69f | 31 | use core::cmp; |
1a4d82fc | 32 | |
c1a9b12d | 33 | use alloc::raw_vec::RawVec; |
1a4d82fc | 34 | |
b039eaaf SL |
35 | use super::range::RangeArgument; |
36 | ||
c34b1796 AL |
37 | const INITIAL_CAPACITY: usize = 7; // 2^3 - 1 |
38 | const MINIMUM_CAPACITY: usize = 1; // 2 - 1 | |
e9174d1e | 39 | const MAXIMUM_ZST_CAPACITY: usize = 1 << (usize::BITS - 1); // Largest possible power of two |
85aaf69f | 40 | |
b039eaaf SL |
41 | /// `VecDeque` is a growable ring buffer, which can be used as a double-ended |
42 | /// queue efficiently. | |
c1a9b12d | 43 | /// |
b039eaaf SL |
44 | /// The "default" usage of this type as a queue is to use `push_back` to add to |
45 | /// the queue, and `pop_front` to remove from the queue. `extend` and `append` | |
46 | /// push onto the back in this manner, and iterating over `VecDeque` goes front | |
47 | /// to back. | |
85aaf69f SL |
48 | #[stable(feature = "rust1", since = "1.0.0")] |
49 | pub struct VecDeque<T> { | |
1a4d82fc JJ |
50 | // tail and head are pointers into the buffer. Tail always points |
51 | // to the first element that could be read, Head always points | |
52 | // to where data should be written. | |
c1a9b12d | 53 | // If tail == head the buffer is empty. The length of the ringbuffer |
1a4d82fc JJ |
54 | // is defined as the distance between the two. |
55 | ||
85aaf69f SL |
56 | tail: usize, |
57 | head: usize, | |
c1a9b12d | 58 | buf: RawVec<T>, |
1a4d82fc JJ |
59 | } |
60 | ||
85aaf69f SL |
61 | #[stable(feature = "rust1", since = "1.0.0")] |
62 | impl<T: Clone> Clone for VecDeque<T> { | |
63 | fn clone(&self) -> VecDeque<T> { | |
64 | self.iter().cloned().collect() | |
1a4d82fc JJ |
65 | } |
66 | } | |
67 | ||
85aaf69f SL |
68 | #[stable(feature = "rust1", since = "1.0.0")] |
69 | impl<T> Drop for VecDeque<T> { | |
b039eaaf | 70 | #[unsafe_destructor_blind_to_params] |
1a4d82fc JJ |
71 | fn drop(&mut self) { |
72 | self.clear(); | |
c1a9b12d | 73 | // RawVec handles deallocation |
1a4d82fc JJ |
74 | } |
75 | } | |
76 | ||
85aaf69f SL |
77 | #[stable(feature = "rust1", since = "1.0.0")] |
78 | impl<T> Default for VecDeque<T> { | |
1a4d82fc | 79 | #[inline] |
85aaf69f | 80 | fn default() -> VecDeque<T> { VecDeque::new() } |
1a4d82fc JJ |
81 | } |
82 | ||
85aaf69f | 83 | impl<T> VecDeque<T> { |
c1a9b12d SL |
84 | /// Marginally more convenient |
85 | #[inline] | |
86 | fn ptr(&self) -> *mut T { | |
87 | self.buf.ptr() | |
88 | } | |
89 | ||
90 | /// Marginally more convenient | |
91 | #[inline] | |
92 | fn cap(&self) -> usize { | |
e9174d1e SL |
93 | if mem::size_of::<T>() == 0 { |
94 | // For zero sized types, we are always at maximum capacity | |
95 | MAXIMUM_ZST_CAPACITY | |
96 | } else { | |
97 | self.buf.cap() | |
98 | } | |
c1a9b12d SL |
99 | } |
100 | ||
1a4d82fc JJ |
101 | /// Turn ptr into a slice |
102 | #[inline] | |
103 | unsafe fn buffer_as_slice(&self) -> &[T] { | |
c1a9b12d | 104 | slice::from_raw_parts(self.ptr(), self.cap()) |
1a4d82fc JJ |
105 | } |
106 | ||
107 | /// Turn ptr into a mut slice | |
108 | #[inline] | |
109 | unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] { | |
c1a9b12d | 110 | slice::from_raw_parts_mut(self.ptr(), self.cap()) |
1a4d82fc JJ |
111 | } |
112 | ||
113 | /// Moves an element out of the buffer | |
114 | #[inline] | |
85aaf69f | 115 | unsafe fn buffer_read(&mut self, off: usize) -> T { |
c1a9b12d | 116 | ptr::read(self.ptr().offset(off as isize)) |
1a4d82fc JJ |
117 | } |
118 | ||
119 | /// Writes an element into the buffer, moving it. | |
120 | #[inline] | |
c1a9b12d SL |
121 | unsafe fn buffer_write(&mut self, off: usize, value: T) { |
122 | ptr::write(self.ptr().offset(off as isize), value); | |
1a4d82fc JJ |
123 | } |
124 | ||
c1a9b12d | 125 | /// Returns true if and only if the buffer is at capacity |
1a4d82fc | 126 | #[inline] |
c1a9b12d | 127 | fn is_full(&self) -> bool { self.cap() - self.len() == 1 } |
1a4d82fc | 128 | |
85aaf69f SL |
129 | /// Returns the index in the underlying buffer for a given logical element |
130 | /// index. | |
1a4d82fc | 131 | #[inline] |
c1a9b12d | 132 | fn wrap_index(&self, idx: usize) -> usize { wrap_index(idx, self.cap()) } |
1a4d82fc | 133 | |
c34b1796 AL |
134 | /// Returns the index in the underlying buffer for a given logical element |
135 | /// index + addend. | |
136 | #[inline] | |
137 | fn wrap_add(&self, idx: usize, addend: usize) -> usize { | |
c1a9b12d | 138 | wrap_index(idx.wrapping_add(addend), self.cap()) |
c34b1796 AL |
139 | } |
140 | ||
141 | /// Returns the index in the underlying buffer for a given logical element | |
142 | /// index - subtrahend. | |
143 | #[inline] | |
144 | fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize { | |
c1a9b12d | 145 | wrap_index(idx.wrapping_sub(subtrahend), self.cap()) |
c34b1796 AL |
146 | } |
147 | ||
1a4d82fc JJ |
148 | /// Copies a contiguous block of memory len long from src to dst |
149 | #[inline] | |
85aaf69f | 150 | unsafe fn copy(&self, dst: usize, src: usize, len: usize) { |
c1a9b12d SL |
151 | debug_assert!(dst + len <= self.cap(), "dst={} src={} len={} cap={}", dst, src, len, |
152 | self.cap()); | |
153 | debug_assert!(src + len <= self.cap(), "dst={} src={} len={} cap={}", dst, src, len, | |
154 | self.cap()); | |
c34b1796 | 155 | ptr::copy( |
c1a9b12d SL |
156 | self.ptr().offset(src as isize), |
157 | self.ptr().offset(dst as isize), | |
1a4d82fc JJ |
158 | len); |
159 | } | |
160 | ||
161 | /// Copies a contiguous block of memory len long from src to dst | |
162 | #[inline] | |
85aaf69f | 163 | unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) { |
c1a9b12d SL |
164 | debug_assert!(dst + len <= self.cap(), "dst={} src={} len={} cap={}", dst, src, len, |
165 | self.cap()); | |
166 | debug_assert!(src + len <= self.cap(), "dst={} src={} len={} cap={}", dst, src, len, | |
167 | self.cap()); | |
c34b1796 | 168 | ptr::copy_nonoverlapping( |
c1a9b12d SL |
169 | self.ptr().offset(src as isize), |
170 | self.ptr().offset(dst as isize), | |
1a4d82fc JJ |
171 | len); |
172 | } | |
c1a9b12d | 173 | |
b039eaaf SL |
174 | /// Copies a potentially wrapping block of memory len long from src to dest. |
175 | /// (abs(dst - src) + len) must be no larger than cap() (There must be at | |
176 | /// most one continuous overlapping region between src and dest). | |
177 | unsafe fn wrap_copy(&self, dst: usize, src: usize, len: usize) { | |
178 | debug_assert!( | |
179 | (if src <= dst { dst - src } else { src - dst }) + len <= self.cap(), | |
180 | "dst={} src={} len={} cap={}", dst, src, len, self.cap()); | |
181 | ||
182 | if src == dst || len == 0 { return } | |
183 | ||
184 | let dst_after_src = self.wrap_sub(dst, src) < len; | |
185 | ||
186 | let src_pre_wrap_len = self.cap() - src; | |
187 | let dst_pre_wrap_len = self.cap() - dst; | |
188 | let src_wraps = src_pre_wrap_len < len; | |
189 | let dst_wraps = dst_pre_wrap_len < len; | |
190 | ||
191 | match (dst_after_src, src_wraps, dst_wraps) { | |
192 | (_, false, false) => { | |
193 | // src doesn't wrap, dst doesn't wrap | |
194 | // | |
195 | // S . . . | |
196 | // 1 [_ _ A A B B C C _] | |
197 | // 2 [_ _ A A A A B B _] | |
198 | // D . . . | |
199 | // | |
200 | self.copy(dst, src, len); | |
201 | } | |
202 | (false, false, true) => { | |
203 | // dst before src, src doesn't wrap, dst wraps | |
204 | // | |
205 | // S . . . | |
206 | // 1 [A A B B _ _ _ C C] | |
207 | // 2 [A A B B _ _ _ A A] | |
208 | // 3 [B B B B _ _ _ A A] | |
209 | // . . D . | |
210 | // | |
211 | self.copy(dst, src, dst_pre_wrap_len); | |
212 | self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len); | |
213 | } | |
214 | (true, false, true) => { | |
215 | // src before dst, src doesn't wrap, dst wraps | |
216 | // | |
217 | // S . . . | |
218 | // 1 [C C _ _ _ A A B B] | |
219 | // 2 [B B _ _ _ A A B B] | |
220 | // 3 [B B _ _ _ A A A A] | |
221 | // . . D . | |
222 | // | |
223 | self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len); | |
224 | self.copy(dst, src, dst_pre_wrap_len); | |
225 | } | |
226 | (false, true, false) => { | |
227 | // dst before src, src wraps, dst doesn't wrap | |
228 | // | |
229 | // . . S . | |
230 | // 1 [C C _ _ _ A A B B] | |
231 | // 2 [C C _ _ _ B B B B] | |
232 | // 3 [C C _ _ _ B B C C] | |
233 | // D . . . | |
234 | // | |
235 | self.copy(dst, src, src_pre_wrap_len); | |
236 | self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len); | |
237 | } | |
238 | (true, true, false) => { | |
239 | // src before dst, src wraps, dst doesn't wrap | |
240 | // | |
241 | // . . S . | |
242 | // 1 [A A B B _ _ _ C C] | |
243 | // 2 [A A A A _ _ _ C C] | |
244 | // 3 [C C A A _ _ _ C C] | |
245 | // D . . . | |
246 | // | |
247 | self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len); | |
248 | self.copy(dst, src, src_pre_wrap_len); | |
249 | } | |
250 | (false, true, true) => { | |
251 | // dst before src, src wraps, dst wraps | |
252 | // | |
253 | // . . . S . | |
254 | // 1 [A B C D _ E F G H] | |
255 | // 2 [A B C D _ E G H H] | |
256 | // 3 [A B C D _ E G H A] | |
257 | // 4 [B C C D _ E G H A] | |
258 | // . . D . . | |
259 | // | |
260 | debug_assert!(dst_pre_wrap_len > src_pre_wrap_len); | |
261 | let delta = dst_pre_wrap_len - src_pre_wrap_len; | |
262 | self.copy(dst, src, src_pre_wrap_len); | |
263 | self.copy(dst + src_pre_wrap_len, 0, delta); | |
264 | self.copy(0, delta, len - dst_pre_wrap_len); | |
265 | } | |
266 | (true, true, true) => { | |
267 | // src before dst, src wraps, dst wraps | |
268 | // | |
269 | // . . S . . | |
270 | // 1 [A B C D _ E F G H] | |
271 | // 2 [A A B D _ E F G H] | |
272 | // 3 [H A B D _ E F G H] | |
273 | // 4 [H A B D _ E F F G] | |
274 | // . . . D . | |
275 | // | |
276 | debug_assert!(src_pre_wrap_len > dst_pre_wrap_len); | |
277 | let delta = src_pre_wrap_len - dst_pre_wrap_len; | |
278 | self.copy(delta, 0, len - src_pre_wrap_len); | |
279 | self.copy(0, self.cap() - delta, delta); | |
280 | self.copy(dst, src, dst_pre_wrap_len); | |
281 | } | |
282 | } | |
283 | } | |
284 | ||
c1a9b12d SL |
285 | /// Frobs the head and tail sections around to handle the fact that we |
286 | /// just reallocated. Unsafe because it trusts old_cap. | |
287 | #[inline] | |
288 | unsafe fn handle_cap_increase(&mut self, old_cap: usize) { | |
289 | let new_cap = self.cap(); | |
290 | ||
291 | // Move the shortest contiguous section of the ring buffer | |
292 | // T H | |
293 | // [o o o o o o o . ] | |
294 | // T H | |
295 | // A [o o o o o o o . . . . . . . . . ] | |
296 | // H T | |
297 | // [o o . o o o o o ] | |
298 | // T H | |
299 | // B [. . . o o o o o o o . . . . . . ] | |
300 | // H T | |
301 | // [o o o o o . o o ] | |
302 | // H T | |
303 | // C [o o o o o . . . . . . . . . o o ] | |
304 | ||
305 | if self.tail <= self.head { // A | |
306 | // Nop | |
307 | } else if self.head < old_cap - self.tail { // B | |
308 | self.copy_nonoverlapping(old_cap, 0, self.head); | |
309 | self.head += old_cap; | |
310 | debug_assert!(self.head > self.tail); | |
311 | } else { // C | |
312 | let new_tail = new_cap - (old_cap - self.tail); | |
313 | self.copy_nonoverlapping(new_tail, self.tail, old_cap - self.tail); | |
314 | self.tail = new_tail; | |
315 | debug_assert!(self.head < self.tail); | |
316 | } | |
317 | debug_assert!(self.head < self.cap()); | |
318 | debug_assert!(self.tail < self.cap()); | |
319 | debug_assert!(self.cap().count_ones() == 1); | |
320 | } | |
1a4d82fc JJ |
321 | } |
322 | ||
85aaf69f SL |
323 | impl<T> VecDeque<T> { |
324 | /// Creates an empty `VecDeque`. | |
325 | #[stable(feature = "rust1", since = "1.0.0")] | |
326 | pub fn new() -> VecDeque<T> { | |
327 | VecDeque::with_capacity(INITIAL_CAPACITY) | |
1a4d82fc JJ |
328 | } |
329 | ||
85aaf69f SL |
330 | /// Creates an empty `VecDeque` with space for at least `n` elements. |
331 | #[stable(feature = "rust1", since = "1.0.0")] | |
332 | pub fn with_capacity(n: usize) -> VecDeque<T> { | |
1a4d82fc JJ |
333 | // +1 since the ringbuffer always leaves one space empty |
334 | let cap = cmp::max(n + 1, MINIMUM_CAPACITY + 1).next_power_of_two(); | |
335 | assert!(cap > n, "capacity overflow"); | |
1a4d82fc | 336 | |
85aaf69f | 337 | VecDeque { |
1a4d82fc JJ |
338 | tail: 0, |
339 | head: 0, | |
c1a9b12d | 340 | buf: RawVec::with_capacity(cap), |
1a4d82fc JJ |
341 | } |
342 | } | |
343 | ||
85aaf69f | 344 | /// Retrieves an element in the `VecDeque` by index. |
1a4d82fc JJ |
345 | /// |
346 | /// # Examples | |
347 | /// | |
c34b1796 | 348 | /// ``` |
85aaf69f | 349 | /// use std::collections::VecDeque; |
1a4d82fc | 350 | /// |
85aaf69f SL |
351 | /// let mut buf = VecDeque::new(); |
352 | /// buf.push_back(3); | |
1a4d82fc JJ |
353 | /// buf.push_back(4); |
354 | /// buf.push_back(5); | |
c1a9b12d | 355 | /// assert_eq!(buf.get(1), Some(&4)); |
1a4d82fc | 356 | /// ``` |
85aaf69f | 357 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d SL |
358 | pub fn get(&self, index: usize) -> Option<&T> { |
359 | if index < self.len() { | |
360 | let idx = self.wrap_add(self.tail, index); | |
361 | unsafe { Some(&*self.ptr().offset(idx as isize)) } | |
1a4d82fc JJ |
362 | } else { |
363 | None | |
364 | } | |
365 | } | |
366 | ||
85aaf69f | 367 | /// Retrieves an element in the `VecDeque` mutably by index. |
1a4d82fc JJ |
368 | /// |
369 | /// # Examples | |
370 | /// | |
c34b1796 | 371 | /// ``` |
85aaf69f | 372 | /// use std::collections::VecDeque; |
1a4d82fc | 373 | /// |
85aaf69f SL |
374 | /// let mut buf = VecDeque::new(); |
375 | /// buf.push_back(3); | |
1a4d82fc JJ |
376 | /// buf.push_back(4); |
377 | /// buf.push_back(5); | |
9346a6ac AL |
378 | /// if let Some(elem) = buf.get_mut(1) { |
379 | /// *elem = 7; | |
1a4d82fc JJ |
380 | /// } |
381 | /// | |
382 | /// assert_eq!(buf[1], 7); | |
383 | /// ``` | |
85aaf69f | 384 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d SL |
385 | pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { |
386 | if index < self.len() { | |
387 | let idx = self.wrap_add(self.tail, index); | |
388 | unsafe { Some(&mut *self.ptr().offset(idx as isize)) } | |
1a4d82fc JJ |
389 | } else { |
390 | None | |
391 | } | |
392 | } | |
393 | ||
394 | /// Swaps elements at indices `i` and `j`. | |
395 | /// | |
396 | /// `i` and `j` may be equal. | |
397 | /// | |
398 | /// Fails if there is no element with either index. | |
399 | /// | |
400 | /// # Examples | |
401 | /// | |
c34b1796 | 402 | /// ``` |
85aaf69f | 403 | /// use std::collections::VecDeque; |
1a4d82fc | 404 | /// |
85aaf69f SL |
405 | /// let mut buf = VecDeque::new(); |
406 | /// buf.push_back(3); | |
1a4d82fc JJ |
407 | /// buf.push_back(4); |
408 | /// buf.push_back(5); | |
409 | /// buf.swap(0, 2); | |
410 | /// assert_eq!(buf[0], 5); | |
411 | /// assert_eq!(buf[2], 3); | |
412 | /// ``` | |
85aaf69f SL |
413 | #[stable(feature = "rust1", since = "1.0.0")] |
414 | pub fn swap(&mut self, i: usize, j: usize) { | |
1a4d82fc JJ |
415 | assert!(i < self.len()); |
416 | assert!(j < self.len()); | |
c34b1796 AL |
417 | let ri = self.wrap_add(self.tail, i); |
418 | let rj = self.wrap_add(self.tail, j); | |
1a4d82fc | 419 | unsafe { |
c1a9b12d | 420 | ptr::swap(self.ptr().offset(ri as isize), self.ptr().offset(rj as isize)) |
1a4d82fc JJ |
421 | } |
422 | } | |
423 | ||
85aaf69f | 424 | /// Returns the number of elements the `VecDeque` can hold without |
1a4d82fc JJ |
425 | /// reallocating. |
426 | /// | |
427 | /// # Examples | |
428 | /// | |
429 | /// ``` | |
85aaf69f | 430 | /// use std::collections::VecDeque; |
1a4d82fc | 431 | /// |
85aaf69f | 432 | /// let buf: VecDeque<i32> = VecDeque::with_capacity(10); |
1a4d82fc JJ |
433 | /// assert!(buf.capacity() >= 10); |
434 | /// ``` | |
435 | #[inline] | |
85aaf69f | 436 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d | 437 | pub fn capacity(&self) -> usize { self.cap() - 1 } |
1a4d82fc JJ |
438 | |
439 | /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the | |
85aaf69f | 440 | /// given `VecDeque`. Does nothing if the capacity is already sufficient. |
1a4d82fc JJ |
441 | /// |
442 | /// Note that the allocator may give the collection more space than it requests. Therefore | |
443 | /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future | |
444 | /// insertions are expected. | |
445 | /// | |
446 | /// # Panics | |
447 | /// | |
85aaf69f | 448 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
449 | /// |
450 | /// # Examples | |
451 | /// | |
452 | /// ``` | |
85aaf69f | 453 | /// use std::collections::VecDeque; |
1a4d82fc | 454 | /// |
85aaf69f | 455 | /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); |
1a4d82fc JJ |
456 | /// buf.reserve_exact(10); |
457 | /// assert!(buf.capacity() >= 11); | |
458 | /// ``` | |
85aaf69f SL |
459 | #[stable(feature = "rust1", since = "1.0.0")] |
460 | pub fn reserve_exact(&mut self, additional: usize) { | |
1a4d82fc JJ |
461 | self.reserve(additional); |
462 | } | |
463 | ||
464 | /// Reserves capacity for at least `additional` more elements to be inserted in the given | |
c1a9b12d | 465 | /// `VecDeque`. The collection may reserve more space to avoid frequent reallocations. |
1a4d82fc JJ |
466 | /// |
467 | /// # Panics | |
468 | /// | |
85aaf69f | 469 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
470 | /// |
471 | /// # Examples | |
472 | /// | |
473 | /// ``` | |
85aaf69f | 474 | /// use std::collections::VecDeque; |
1a4d82fc | 475 | /// |
85aaf69f | 476 | /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); |
1a4d82fc JJ |
477 | /// buf.reserve(10); |
478 | /// assert!(buf.capacity() >= 11); | |
479 | /// ``` | |
85aaf69f SL |
480 | #[stable(feature = "rust1", since = "1.0.0")] |
481 | pub fn reserve(&mut self, additional: usize) { | |
c1a9b12d SL |
482 | let old_cap = self.cap(); |
483 | let used_cap = self.len() + 1; | |
484 | let new_cap = used_cap | |
485 | .checked_add(additional) | |
486 | .and_then(|needed_cap| needed_cap.checked_next_power_of_two()) | |
487 | .expect("capacity overflow"); | |
488 | ||
489 | if new_cap > self.capacity() { | |
490 | self.buf.reserve_exact(used_cap, new_cap - used_cap); | |
491 | unsafe { self.handle_cap_increase(old_cap); } | |
1a4d82fc JJ |
492 | } |
493 | } | |
494 | ||
c1a9b12d | 495 | /// Shrinks the capacity of the `VecDeque` as much as possible. |
1a4d82fc JJ |
496 | /// |
497 | /// It will drop down as close as possible to the length but the allocator may still inform the | |
c1a9b12d | 498 | /// `VecDeque` that there is space for a few more elements. |
1a4d82fc JJ |
499 | /// |
500 | /// # Examples | |
501 | /// | |
502 | /// ``` | |
85aaf69f | 503 | /// use std::collections::VecDeque; |
1a4d82fc | 504 | /// |
85aaf69f SL |
505 | /// let mut buf = VecDeque::with_capacity(15); |
506 | /// buf.extend(0..4); | |
1a4d82fc JJ |
507 | /// assert_eq!(buf.capacity(), 15); |
508 | /// buf.shrink_to_fit(); | |
509 | /// assert!(buf.capacity() >= 4); | |
510 | /// ``` | |
b039eaaf | 511 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
1a4d82fc JJ |
512 | pub fn shrink_to_fit(&mut self) { |
513 | // +1 since the ringbuffer always leaves one space empty | |
c1a9b12d | 514 | // len + 1 can't overflow for an existing, well-formed ringbuffer. |
1a4d82fc | 515 | let target_cap = cmp::max(self.len() + 1, MINIMUM_CAPACITY + 1).next_power_of_two(); |
c1a9b12d | 516 | if target_cap < self.cap() { |
1a4d82fc JJ |
517 | // There are three cases of interest: |
518 | // All elements are out of desired bounds | |
519 | // Elements are contiguous, and head is out of desired bounds | |
520 | // Elements are discontiguous, and tail is out of desired bounds | |
521 | // | |
522 | // At all other times, element positions are unaffected. | |
523 | // | |
524 | // Indicates that elements at the head should be moved. | |
525 | let head_outside = self.head == 0 || self.head >= target_cap; | |
526 | // Move elements from out of desired bounds (positions after target_cap) | |
527 | if self.tail >= target_cap && head_outside { | |
528 | // T H | |
529 | // [. . . . . . . . o o o o o o o . ] | |
530 | // T H | |
531 | // [o o o o o o o . ] | |
532 | unsafe { | |
533 | self.copy_nonoverlapping(0, self.tail, self.len()); | |
534 | } | |
535 | self.head = self.len(); | |
536 | self.tail = 0; | |
537 | } else if self.tail != 0 && self.tail < target_cap && head_outside { | |
538 | // T H | |
539 | // [. . . o o o o o o o . . . . . . ] | |
540 | // H T | |
541 | // [o o . o o o o o ] | |
c34b1796 | 542 | let len = self.wrap_sub(self.head, target_cap); |
1a4d82fc JJ |
543 | unsafe { |
544 | self.copy_nonoverlapping(0, target_cap, len); | |
545 | } | |
546 | self.head = len; | |
547 | debug_assert!(self.head < self.tail); | |
548 | } else if self.tail >= target_cap { | |
549 | // H T | |
550 | // [o o o o o . . . . . . . . . o o ] | |
551 | // H T | |
552 | // [o o o o o . o o ] | |
c34b1796 | 553 | debug_assert!(self.wrap_sub(self.head, 1) < target_cap); |
c1a9b12d | 554 | let len = self.cap() - self.tail; |
1a4d82fc JJ |
555 | let new_tail = target_cap - len; |
556 | unsafe { | |
557 | self.copy_nonoverlapping(new_tail, self.tail, len); | |
558 | } | |
559 | self.tail = new_tail; | |
560 | debug_assert!(self.head < self.tail); | |
561 | } | |
562 | ||
c1a9b12d SL |
563 | self.buf.shrink_to_fit(target_cap); |
564 | ||
565 | debug_assert!(self.head < self.cap()); | |
566 | debug_assert!(self.tail < self.cap()); | |
567 | debug_assert!(self.cap().count_ones() == 1); | |
1a4d82fc JJ |
568 | } |
569 | } | |
570 | ||
c1a9b12d | 571 | /// Shortens a `VecDeque`, dropping excess elements from the back. |
1a4d82fc | 572 | /// |
c1a9b12d | 573 | /// If `len` is greater than the `VecDeque`'s current length, this has no |
1a4d82fc JJ |
574 | /// effect. |
575 | /// | |
576 | /// # Examples | |
577 | /// | |
578 | /// ``` | |
c1a9b12d SL |
579 | /// #![feature(deque_extras)] |
580 | /// | |
85aaf69f | 581 | /// use std::collections::VecDeque; |
1a4d82fc | 582 | /// |
85aaf69f SL |
583 | /// let mut buf = VecDeque::new(); |
584 | /// buf.push_back(5); | |
585 | /// buf.push_back(10); | |
1a4d82fc JJ |
586 | /// buf.push_back(15); |
587 | /// buf.truncate(1); | |
588 | /// assert_eq!(buf.len(), 1); | |
589 | /// assert_eq!(Some(&5), buf.get(0)); | |
590 | /// ``` | |
62682a34 | 591 | #[unstable(feature = "deque_extras", |
e9174d1e SL |
592 | reason = "matches collection reform specification; waiting on panic semantics", |
593 | issue = "27788")] | |
85aaf69f SL |
594 | pub fn truncate(&mut self, len: usize) { |
595 | for _ in len..self.len() { | |
1a4d82fc JJ |
596 | self.pop_back(); |
597 | } | |
598 | } | |
599 | ||
600 | /// Returns a front-to-back iterator. | |
601 | /// | |
602 | /// # Examples | |
603 | /// | |
c34b1796 | 604 | /// ``` |
85aaf69f | 605 | /// use std::collections::VecDeque; |
1a4d82fc | 606 | /// |
85aaf69f SL |
607 | /// let mut buf = VecDeque::new(); |
608 | /// buf.push_back(5); | |
1a4d82fc JJ |
609 | /// buf.push_back(3); |
610 | /// buf.push_back(4); | |
611 | /// let b: &[_] = &[&5, &3, &4]; | |
c34b1796 AL |
612 | /// let c: Vec<&i32> = buf.iter().collect(); |
613 | /// assert_eq!(&c[..], b); | |
1a4d82fc | 614 | /// ``` |
85aaf69f | 615 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
616 | pub fn iter(&self) -> Iter<T> { |
617 | Iter { | |
618 | tail: self.tail, | |
619 | head: self.head, | |
620 | ring: unsafe { self.buffer_as_slice() } | |
621 | } | |
622 | } | |
623 | ||
624 | /// Returns a front-to-back iterator that returns mutable references. | |
625 | /// | |
626 | /// # Examples | |
627 | /// | |
c34b1796 | 628 | /// ``` |
85aaf69f | 629 | /// use std::collections::VecDeque; |
1a4d82fc | 630 | /// |
85aaf69f SL |
631 | /// let mut buf = VecDeque::new(); |
632 | /// buf.push_back(5); | |
1a4d82fc JJ |
633 | /// buf.push_back(3); |
634 | /// buf.push_back(4); | |
635 | /// for num in buf.iter_mut() { | |
636 | /// *num = *num - 2; | |
637 | /// } | |
638 | /// let b: &[_] = &[&mut 3, &mut 1, &mut 2]; | |
c34b1796 | 639 | /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b); |
1a4d82fc | 640 | /// ``` |
85aaf69f SL |
641 | #[stable(feature = "rust1", since = "1.0.0")] |
642 | pub fn iter_mut(&mut self) -> IterMut<T> { | |
1a4d82fc JJ |
643 | IterMut { |
644 | tail: self.tail, | |
645 | head: self.head, | |
c34b1796 | 646 | ring: unsafe { self.buffer_as_mut_slice() }, |
1a4d82fc JJ |
647 | } |
648 | } | |
649 | ||
1a4d82fc | 650 | /// Returns a pair of slices which contain, in order, the contents of the |
85aaf69f | 651 | /// `VecDeque`. |
1a4d82fc | 652 | #[inline] |
b039eaaf | 653 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
85aaf69f | 654 | pub fn as_slices(&self) -> (&[T], &[T]) { |
1a4d82fc JJ |
655 | unsafe { |
656 | let contiguous = self.is_contiguous(); | |
657 | let buf = self.buffer_as_slice(); | |
658 | if contiguous { | |
659 | let (empty, buf) = buf.split_at(0); | |
660 | (&buf[self.tail..self.head], empty) | |
661 | } else { | |
662 | let (mid, right) = buf.split_at(self.tail); | |
663 | let (left, _) = mid.split_at(self.head); | |
664 | (right, left) | |
665 | } | |
666 | } | |
667 | } | |
668 | ||
669 | /// Returns a pair of slices which contain, in order, the contents of the | |
85aaf69f | 670 | /// `VecDeque`. |
1a4d82fc | 671 | #[inline] |
b039eaaf | 672 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
85aaf69f | 673 | pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) { |
1a4d82fc JJ |
674 | unsafe { |
675 | let contiguous = self.is_contiguous(); | |
676 | let head = self.head; | |
677 | let tail = self.tail; | |
678 | let buf = self.buffer_as_mut_slice(); | |
679 | ||
680 | if contiguous { | |
681 | let (empty, buf) = buf.split_at_mut(0); | |
85aaf69f | 682 | (&mut buf[tail .. head], empty) |
1a4d82fc JJ |
683 | } else { |
684 | let (mid, right) = buf.split_at_mut(tail); | |
685 | let (left, _) = mid.split_at_mut(head); | |
686 | ||
687 | (right, left) | |
688 | } | |
689 | } | |
690 | } | |
691 | ||
85aaf69f | 692 | /// Returns the number of elements in the `VecDeque`. |
1a4d82fc JJ |
693 | /// |
694 | /// # Examples | |
695 | /// | |
696 | /// ``` | |
85aaf69f | 697 | /// use std::collections::VecDeque; |
1a4d82fc | 698 | /// |
85aaf69f | 699 | /// let mut v = VecDeque::new(); |
1a4d82fc | 700 | /// assert_eq!(v.len(), 0); |
85aaf69f | 701 | /// v.push_back(1); |
1a4d82fc JJ |
702 | /// assert_eq!(v.len(), 1); |
703 | /// ``` | |
85aaf69f | 704 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d | 705 | pub fn len(&self) -> usize { count(self.tail, self.head, self.cap()) } |
1a4d82fc JJ |
706 | |
707 | /// Returns true if the buffer contains no elements | |
708 | /// | |
709 | /// # Examples | |
710 | /// | |
711 | /// ``` | |
85aaf69f | 712 | /// use std::collections::VecDeque; |
1a4d82fc | 713 | /// |
85aaf69f | 714 | /// let mut v = VecDeque::new(); |
1a4d82fc | 715 | /// assert!(v.is_empty()); |
85aaf69f | 716 | /// v.push_front(1); |
1a4d82fc JJ |
717 | /// assert!(!v.is_empty()); |
718 | /// ``` | |
85aaf69f | 719 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
720 | pub fn is_empty(&self) -> bool { self.len() == 0 } |
721 | ||
b039eaaf SL |
722 | /// Create a draining iterator that removes the specified range in the |
723 | /// `VecDeque` and yields the removed items from start to end. The element | |
724 | /// range is removed even if the iterator is not consumed until the end. | |
725 | /// | |
726 | /// Note: It is unspecified how many elements are removed from the deque, | |
727 | /// if the `Drain` value is not dropped, but the borrow it holds expires | |
728 | /// (eg. due to mem::forget). | |
729 | /// | |
730 | /// # Panics | |
731 | /// | |
732 | /// Panics if the starting point is greater than the end point or if | |
733 | /// the end point is greater than the length of the vector. | |
1a4d82fc JJ |
734 | /// |
735 | /// # Examples | |
736 | /// | |
737 | /// ``` | |
c1a9b12d SL |
738 | /// #![feature(drain)] |
739 | /// | |
85aaf69f | 740 | /// use std::collections::VecDeque; |
1a4d82fc | 741 | /// |
b039eaaf | 742 | /// // draining using `..` clears the whole deque. |
85aaf69f SL |
743 | /// let mut v = VecDeque::new(); |
744 | /// v.push_back(1); | |
b039eaaf | 745 | /// assert_eq!(v.drain(..).next(), Some(1)); |
1a4d82fc JJ |
746 | /// assert!(v.is_empty()); |
747 | /// ``` | |
748 | #[inline] | |
62682a34 | 749 | #[unstable(feature = "drain", |
e9174d1e SL |
750 | reason = "matches collection reform specification, waiting for dust to settle", |
751 | issue = "27711")] | |
b039eaaf SL |
752 | pub fn drain<R>(&mut self, range: R) -> Drain<T> where R: RangeArgument<usize> { |
753 | // Memory safety | |
754 | // | |
755 | // When the Drain is first created, the source deque is shortened to | |
756 | // make sure no uninitialized or moved-from elements are accessible at | |
757 | // all if the Drain's destructor never gets to run. | |
758 | // | |
759 | // Drain will ptr::read out the values to remove. | |
760 | // When finished, the remaining data will be copied back to cover the hole, | |
761 | // and the head/tail values will be restored correctly. | |
762 | // | |
763 | let len = self.len(); | |
764 | let start = *range.start().unwrap_or(&0); | |
765 | let end = *range.end().unwrap_or(&len); | |
766 | assert!(start <= end, "drain lower bound was too large"); | |
767 | assert!(end <= len, "drain upper bound was too large"); | |
768 | ||
769 | // The deque's elements are parted into three segments: | |
770 | // * self.tail -> drain_tail | |
771 | // * drain_tail -> drain_head | |
772 | // * drain_head -> self.head | |
773 | // | |
774 | // T = self.tail; H = self.head; t = drain_tail; h = drain_head | |
775 | // | |
776 | // We store drain_tail as self.head, and drain_head and self.head as | |
777 | // after_tail and after_head respectively on the Drain. This also | |
778 | // truncates the effective array such that if the Drain is leaked, we | |
779 | // have forgotten about the potentially moved values after the start of | |
780 | // the drain. | |
781 | // | |
782 | // T t h H | |
783 | // [. . . o o x x o o . . .] | |
784 | // | |
785 | let drain_tail = self.wrap_add(self.tail, start); | |
786 | let drain_head = self.wrap_add(self.tail, end); | |
787 | let head = self.head; | |
788 | ||
789 | // "forget" about the values after the start of the drain until after | |
790 | // the drain is complete and the Drain destructor is run. | |
791 | self.head = drain_tail; | |
792 | ||
1a4d82fc | 793 | Drain { |
b039eaaf SL |
794 | deque: self as *mut _, |
795 | after_tail: drain_head, | |
796 | after_head: head, | |
797 | iter: Iter { | |
798 | tail: drain_tail, | |
799 | head: drain_head, | |
800 | ring: unsafe { self.buffer_as_mut_slice() }, | |
801 | }, | |
1a4d82fc JJ |
802 | } |
803 | } | |
804 | ||
805 | /// Clears the buffer, removing all values. | |
806 | /// | |
807 | /// # Examples | |
808 | /// | |
809 | /// ``` | |
85aaf69f | 810 | /// use std::collections::VecDeque; |
1a4d82fc | 811 | /// |
85aaf69f SL |
812 | /// let mut v = VecDeque::new(); |
813 | /// v.push_back(1); | |
1a4d82fc JJ |
814 | /// v.clear(); |
815 | /// assert!(v.is_empty()); | |
816 | /// ``` | |
85aaf69f | 817 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
818 | #[inline] |
819 | pub fn clear(&mut self) { | |
b039eaaf | 820 | self.drain(..); |
1a4d82fc JJ |
821 | } |
822 | ||
823 | /// Provides a reference to the front element, or `None` if the sequence is | |
824 | /// empty. | |
825 | /// | |
826 | /// # Examples | |
827 | /// | |
828 | /// ``` | |
85aaf69f | 829 | /// use std::collections::VecDeque; |
1a4d82fc | 830 | /// |
85aaf69f | 831 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
832 | /// assert_eq!(d.front(), None); |
833 | /// | |
85aaf69f SL |
834 | /// d.push_back(1); |
835 | /// d.push_back(2); | |
836 | /// assert_eq!(d.front(), Some(&1)); | |
1a4d82fc | 837 | /// ``` |
85aaf69f | 838 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
839 | pub fn front(&self) -> Option<&T> { |
840 | if !self.is_empty() { Some(&self[0]) } else { None } | |
841 | } | |
842 | ||
843 | /// Provides a mutable reference to the front element, or `None` if the | |
844 | /// sequence is empty. | |
845 | /// | |
846 | /// # Examples | |
847 | /// | |
848 | /// ``` | |
85aaf69f | 849 | /// use std::collections::VecDeque; |
1a4d82fc | 850 | /// |
85aaf69f | 851 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
852 | /// assert_eq!(d.front_mut(), None); |
853 | /// | |
85aaf69f SL |
854 | /// d.push_back(1); |
855 | /// d.push_back(2); | |
1a4d82fc | 856 | /// match d.front_mut() { |
85aaf69f | 857 | /// Some(x) => *x = 9, |
1a4d82fc JJ |
858 | /// None => (), |
859 | /// } | |
85aaf69f | 860 | /// assert_eq!(d.front(), Some(&9)); |
1a4d82fc | 861 | /// ``` |
85aaf69f | 862 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
863 | pub fn front_mut(&mut self) -> Option<&mut T> { |
864 | if !self.is_empty() { Some(&mut self[0]) } else { None } | |
865 | } | |
866 | ||
867 | /// Provides a reference to the back element, or `None` if the sequence is | |
868 | /// empty. | |
869 | /// | |
870 | /// # Examples | |
871 | /// | |
872 | /// ``` | |
85aaf69f | 873 | /// use std::collections::VecDeque; |
1a4d82fc | 874 | /// |
85aaf69f | 875 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
876 | /// assert_eq!(d.back(), None); |
877 | /// | |
85aaf69f SL |
878 | /// d.push_back(1); |
879 | /// d.push_back(2); | |
880 | /// assert_eq!(d.back(), Some(&2)); | |
1a4d82fc | 881 | /// ``` |
85aaf69f | 882 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
883 | pub fn back(&self) -> Option<&T> { |
884 | if !self.is_empty() { Some(&self[self.len() - 1]) } else { None } | |
885 | } | |
886 | ||
887 | /// Provides a mutable reference to the back element, or `None` if the | |
888 | /// sequence is empty. | |
889 | /// | |
890 | /// # Examples | |
891 | /// | |
892 | /// ``` | |
85aaf69f | 893 | /// use std::collections::VecDeque; |
1a4d82fc | 894 | /// |
85aaf69f | 895 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
896 | /// assert_eq!(d.back(), None); |
897 | /// | |
85aaf69f SL |
898 | /// d.push_back(1); |
899 | /// d.push_back(2); | |
1a4d82fc | 900 | /// match d.back_mut() { |
85aaf69f | 901 | /// Some(x) => *x = 9, |
1a4d82fc JJ |
902 | /// None => (), |
903 | /// } | |
85aaf69f | 904 | /// assert_eq!(d.back(), Some(&9)); |
1a4d82fc | 905 | /// ``` |
85aaf69f | 906 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
907 | pub fn back_mut(&mut self) -> Option<&mut T> { |
908 | let len = self.len(); | |
909 | if !self.is_empty() { Some(&mut self[len - 1]) } else { None } | |
910 | } | |
911 | ||
912 | /// Removes the first element and returns it, or `None` if the sequence is | |
913 | /// empty. | |
914 | /// | |
915 | /// # Examples | |
916 | /// | |
917 | /// ``` | |
85aaf69f | 918 | /// use std::collections::VecDeque; |
1a4d82fc | 919 | /// |
85aaf69f SL |
920 | /// let mut d = VecDeque::new(); |
921 | /// d.push_back(1); | |
922 | /// d.push_back(2); | |
1a4d82fc | 923 | /// |
85aaf69f SL |
924 | /// assert_eq!(d.pop_front(), Some(1)); |
925 | /// assert_eq!(d.pop_front(), Some(2)); | |
1a4d82fc JJ |
926 | /// assert_eq!(d.pop_front(), None); |
927 | /// ``` | |
85aaf69f | 928 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
929 | pub fn pop_front(&mut self) -> Option<T> { |
930 | if self.is_empty() { | |
931 | None | |
932 | } else { | |
933 | let tail = self.tail; | |
c34b1796 | 934 | self.tail = self.wrap_add(self.tail, 1); |
1a4d82fc JJ |
935 | unsafe { Some(self.buffer_read(tail)) } |
936 | } | |
937 | } | |
938 | ||
939 | /// Inserts an element first in the sequence. | |
940 | /// | |
941 | /// # Examples | |
942 | /// | |
943 | /// ``` | |
85aaf69f | 944 | /// use std::collections::VecDeque; |
1a4d82fc | 945 | /// |
85aaf69f SL |
946 | /// let mut d = VecDeque::new(); |
947 | /// d.push_front(1); | |
948 | /// d.push_front(2); | |
949 | /// assert_eq!(d.front(), Some(&2)); | |
1a4d82fc | 950 | /// ``` |
85aaf69f | 951 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d | 952 | pub fn push_front(&mut self, value: T) { |
1a4d82fc | 953 | if self.is_full() { |
c1a9b12d SL |
954 | let old_cap = self.cap(); |
955 | self.buf.double(); | |
956 | unsafe { self.handle_cap_increase(old_cap); } | |
1a4d82fc JJ |
957 | debug_assert!(!self.is_full()); |
958 | } | |
959 | ||
c34b1796 | 960 | self.tail = self.wrap_sub(self.tail, 1); |
1a4d82fc | 961 | let tail = self.tail; |
c1a9b12d | 962 | unsafe { self.buffer_write(tail, value); } |
1a4d82fc JJ |
963 | } |
964 | ||
965 | /// Appends an element to the back of a buffer | |
966 | /// | |
967 | /// # Examples | |
968 | /// | |
c34b1796 | 969 | /// ``` |
85aaf69f | 970 | /// use std::collections::VecDeque; |
1a4d82fc | 971 | /// |
85aaf69f SL |
972 | /// let mut buf = VecDeque::new(); |
973 | /// buf.push_back(1); | |
1a4d82fc JJ |
974 | /// buf.push_back(3); |
975 | /// assert_eq!(3, *buf.back().unwrap()); | |
976 | /// ``` | |
85aaf69f | 977 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d | 978 | pub fn push_back(&mut self, value: T) { |
1a4d82fc | 979 | if self.is_full() { |
c1a9b12d SL |
980 | let old_cap = self.cap(); |
981 | self.buf.double(); | |
982 | unsafe { self.handle_cap_increase(old_cap); } | |
1a4d82fc JJ |
983 | debug_assert!(!self.is_full()); |
984 | } | |
985 | ||
986 | let head = self.head; | |
c34b1796 | 987 | self.head = self.wrap_add(self.head, 1); |
c1a9b12d | 988 | unsafe { self.buffer_write(head, value) } |
1a4d82fc JJ |
989 | } |
990 | ||
991 | /// Removes the last element from a buffer and returns it, or `None` if | |
992 | /// it is empty. | |
993 | /// | |
994 | /// # Examples | |
995 | /// | |
c34b1796 | 996 | /// ``` |
85aaf69f | 997 | /// use std::collections::VecDeque; |
1a4d82fc | 998 | /// |
85aaf69f | 999 | /// let mut buf = VecDeque::new(); |
1a4d82fc | 1000 | /// assert_eq!(buf.pop_back(), None); |
85aaf69f | 1001 | /// buf.push_back(1); |
1a4d82fc JJ |
1002 | /// buf.push_back(3); |
1003 | /// assert_eq!(buf.pop_back(), Some(3)); | |
1004 | /// ``` | |
85aaf69f | 1005 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1006 | pub fn pop_back(&mut self) -> Option<T> { |
1007 | if self.is_empty() { | |
1008 | None | |
1009 | } else { | |
c34b1796 | 1010 | self.head = self.wrap_sub(self.head, 1); |
1a4d82fc JJ |
1011 | let head = self.head; |
1012 | unsafe { Some(self.buffer_read(head)) } | |
1013 | } | |
1014 | } | |
1015 | ||
1016 | #[inline] | |
1017 | fn is_contiguous(&self) -> bool { | |
1018 | self.tail <= self.head | |
1019 | } | |
1020 | ||
c1a9b12d SL |
1021 | /// Removes an element from anywhere in the `VecDeque` and returns it, replacing it with the |
1022 | /// last element. | |
1a4d82fc JJ |
1023 | /// |
1024 | /// This does not preserve ordering, but is O(1). | |
1025 | /// | |
1026 | /// Returns `None` if `index` is out of bounds. | |
1027 | /// | |
1028 | /// # Examples | |
1029 | /// | |
1030 | /// ``` | |
85aaf69f | 1031 | /// use std::collections::VecDeque; |
1a4d82fc | 1032 | /// |
85aaf69f | 1033 | /// let mut buf = VecDeque::new(); |
b039eaaf | 1034 | /// assert_eq!(buf.swap_remove_back(0), None); |
c1a9b12d SL |
1035 | /// buf.push_back(1); |
1036 | /// buf.push_back(2); | |
1037 | /// buf.push_back(3); | |
1038 | /// | |
b039eaaf | 1039 | /// assert_eq!(buf.swap_remove_back(0), Some(1)); |
c1a9b12d SL |
1040 | /// assert_eq!(buf.len(), 2); |
1041 | /// assert_eq!(buf[0], 3); | |
1042 | /// assert_eq!(buf[1], 2); | |
1a4d82fc | 1043 | /// ``` |
b039eaaf SL |
1044 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
1045 | pub fn swap_remove_back(&mut self, index: usize) -> Option<T> { | |
1a4d82fc JJ |
1046 | let length = self.len(); |
1047 | if length > 0 && index < length - 1 { | |
1048 | self.swap(index, length - 1); | |
1049 | } else if index >= length { | |
1050 | return None; | |
1051 | } | |
1052 | self.pop_back() | |
1053 | } | |
1054 | ||
b039eaaf SL |
1055 | /// deprecated |
1056 | #[unstable(feature = "deque_extras", | |
1057 | reason = "the naming of this function may be altered", | |
1058 | issue = "27788")] | |
1059 | #[deprecated(since = "1.5.0", reason = "renamed to swap_remove_back")] | |
1060 | pub fn swap_back_remove(&mut self, index: usize) -> Option<T> { | |
1061 | self.swap_remove_back(index) | |
1062 | } | |
1063 | ||
c1a9b12d | 1064 | /// Removes an element from anywhere in the `VecDeque` and returns it, |
62682a34 | 1065 | /// replacing it with the first element. |
1a4d82fc JJ |
1066 | /// |
1067 | /// This does not preserve ordering, but is O(1). | |
1068 | /// | |
1069 | /// Returns `None` if `index` is out of bounds. | |
1070 | /// | |
1071 | /// # Examples | |
1072 | /// | |
1073 | /// ``` | |
85aaf69f | 1074 | /// use std::collections::VecDeque; |
1a4d82fc | 1075 | /// |
85aaf69f | 1076 | /// let mut buf = VecDeque::new(); |
b039eaaf | 1077 | /// assert_eq!(buf.swap_remove_front(0), None); |
c1a9b12d SL |
1078 | /// buf.push_back(1); |
1079 | /// buf.push_back(2); | |
1080 | /// buf.push_back(3); | |
1081 | /// | |
b039eaaf | 1082 | /// assert_eq!(buf.swap_remove_front(2), Some(3)); |
c1a9b12d SL |
1083 | /// assert_eq!(buf.len(), 2); |
1084 | /// assert_eq!(buf[0], 2); | |
1085 | /// assert_eq!(buf[1], 1); | |
1a4d82fc | 1086 | /// ``` |
b039eaaf SL |
1087 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
1088 | pub fn swap_remove_front(&mut self, index: usize) -> Option<T> { | |
1a4d82fc JJ |
1089 | let length = self.len(); |
1090 | if length > 0 && index < length && index != 0 { | |
1091 | self.swap(index, 0); | |
1092 | } else if index >= length { | |
1093 | return None; | |
1094 | } | |
1095 | self.pop_front() | |
1096 | } | |
1097 | ||
b039eaaf SL |
1098 | /// deprecated |
1099 | #[unstable(feature = "deque_extras", | |
1100 | reason = "the naming of this function may be altered", | |
1101 | issue = "27788")] | |
1102 | #[deprecated(since = "1.5.0", reason = "renamed to swap_remove_front")] | |
1103 | pub fn swap_front_remove(&mut self, index: usize) -> Option<T> { | |
1104 | self.swap_remove_front(index) | |
1105 | } | |
1106 | ||
c1a9b12d | 1107 | /// Inserts an element at `index` within the `VecDeque`. Whichever |
1a4d82fc JJ |
1108 | /// end is closer to the insertion point will be moved to make room, |
1109 | /// and all the affected elements will be moved to new positions. | |
1110 | /// | |
1111 | /// # Panics | |
1112 | /// | |
c1a9b12d | 1113 | /// Panics if `index` is greater than `VecDeque`'s length |
1a4d82fc JJ |
1114 | /// |
1115 | /// # Examples | |
c34b1796 | 1116 | /// ``` |
85aaf69f | 1117 | /// use std::collections::VecDeque; |
1a4d82fc | 1118 | /// |
85aaf69f SL |
1119 | /// let mut buf = VecDeque::new(); |
1120 | /// buf.push_back(10); | |
1a4d82fc | 1121 | /// buf.push_back(12); |
c1a9b12d | 1122 | /// buf.insert(1, 11); |
1a4d82fc JJ |
1123 | /// assert_eq!(Some(&11), buf.get(1)); |
1124 | /// ``` | |
b039eaaf | 1125 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
c1a9b12d SL |
1126 | pub fn insert(&mut self, index: usize, value: T) { |
1127 | assert!(index <= self.len(), "index out of bounds"); | |
1a4d82fc | 1128 | if self.is_full() { |
c1a9b12d SL |
1129 | let old_cap = self.cap(); |
1130 | self.buf.double(); | |
1131 | unsafe { self.handle_cap_increase(old_cap); } | |
1a4d82fc JJ |
1132 | debug_assert!(!self.is_full()); |
1133 | } | |
1134 | ||
1135 | // Move the least number of elements in the ring buffer and insert | |
1136 | // the given object | |
1137 | // | |
1138 | // At most len/2 - 1 elements will be moved. O(min(n, n-i)) | |
1139 | // | |
1140 | // There are three main cases: | |
1141 | // Elements are contiguous | |
1142 | // - special case when tail is 0 | |
1143 | // Elements are discontiguous and the insert is in the tail section | |
1144 | // Elements are discontiguous and the insert is in the head section | |
1145 | // | |
1146 | // For each of those there are two more cases: | |
1147 | // Insert is closer to tail | |
1148 | // Insert is closer to head | |
1149 | // | |
1150 | // Key: H - self.head | |
1151 | // T - self.tail | |
1152 | // o - Valid element | |
1153 | // I - Insertion element | |
1154 | // A - The element that should be after the insertion point | |
1155 | // M - Indicates element was moved | |
1156 | ||
c1a9b12d | 1157 | let idx = self.wrap_add(self.tail, index); |
1a4d82fc | 1158 | |
c1a9b12d SL |
1159 | let distance_to_tail = index; |
1160 | let distance_to_head = self.len() - index; | |
1a4d82fc JJ |
1161 | |
1162 | let contiguous = self.is_contiguous(); | |
1163 | ||
1164 | match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) { | |
c1a9b12d | 1165 | (true, true, _) if index == 0 => { |
1a4d82fc JJ |
1166 | // push_front |
1167 | // | |
1168 | // T | |
1169 | // I H | |
1170 | // [A o o o o o o . . . . . . . . .] | |
1171 | // | |
1172 | // H T | |
1173 | // [A o o o o o o o . . . . . I] | |
1174 | // | |
1175 | ||
c34b1796 | 1176 | self.tail = self.wrap_sub(self.tail, 1); |
1a4d82fc JJ |
1177 | }, |
1178 | (true, true, _) => unsafe { | |
1179 | // contiguous, insert closer to tail: | |
1180 | // | |
1181 | // T I H | |
1182 | // [. . . o o A o o o o . . . . . .] | |
1183 | // | |
1184 | // T H | |
1185 | // [. . o o I A o o o o . . . . . .] | |
1186 | // M M | |
1187 | // | |
1188 | // contiguous, insert closer to tail and tail is 0: | |
1189 | // | |
1190 | // | |
1191 | // T I H | |
1192 | // [o o A o o o o . . . . . . . . .] | |
1193 | // | |
1194 | // H T | |
1195 | // [o I A o o o o o . . . . . . . o] | |
1196 | // M M | |
1197 | ||
c34b1796 | 1198 | let new_tail = self.wrap_sub(self.tail, 1); |
1a4d82fc JJ |
1199 | |
1200 | self.copy(new_tail, self.tail, 1); | |
c1a9b12d SL |
1201 | // Already moved the tail, so we only copy `index - 1` elements. |
1202 | self.copy(self.tail, self.tail + 1, index - 1); | |
1a4d82fc JJ |
1203 | |
1204 | self.tail = new_tail; | |
1205 | }, | |
1206 | (true, false, _) => unsafe { | |
1207 | // contiguous, insert closer to head: | |
1208 | // | |
1209 | // T I H | |
1210 | // [. . . o o o o A o o . . . . . .] | |
1211 | // | |
1212 | // T H | |
1213 | // [. . . o o o o I A o o . . . . .] | |
1214 | // M M M | |
1215 | ||
1216 | self.copy(idx + 1, idx, self.head - idx); | |
c34b1796 | 1217 | self.head = self.wrap_add(self.head, 1); |
1a4d82fc JJ |
1218 | }, |
1219 | (false, true, true) => unsafe { | |
1220 | // discontiguous, insert closer to tail, tail section: | |
1221 | // | |
1222 | // H T I | |
1223 | // [o o o o o o . . . . . o o A o o] | |
1224 | // | |
1225 | // H T | |
1226 | // [o o o o o o . . . . o o I A o o] | |
1227 | // M M | |
1228 | ||
c1a9b12d | 1229 | self.copy(self.tail - 1, self.tail, index); |
1a4d82fc JJ |
1230 | self.tail -= 1; |
1231 | }, | |
1232 | (false, false, true) => unsafe { | |
1233 | // discontiguous, insert closer to head, tail section: | |
1234 | // | |
1235 | // H T I | |
1236 | // [o o . . . . . . . o o o o o A o] | |
1237 | // | |
1238 | // H T | |
1239 | // [o o o . . . . . . o o o o o I A] | |
1240 | // M M M M | |
1241 | ||
1242 | // copy elements up to new head | |
1243 | self.copy(1, 0, self.head); | |
1244 | ||
1245 | // copy last element into empty spot at bottom of buffer | |
c1a9b12d | 1246 | self.copy(0, self.cap() - 1, 1); |
1a4d82fc JJ |
1247 | |
1248 | // move elements from idx to end forward not including ^ element | |
c1a9b12d | 1249 | self.copy(idx + 1, idx, self.cap() - 1 - idx); |
1a4d82fc JJ |
1250 | |
1251 | self.head += 1; | |
1252 | }, | |
1253 | (false, true, false) if idx == 0 => unsafe { | |
1254 | // discontiguous, insert is closer to tail, head section, | |
1255 | // and is at index zero in the internal buffer: | |
1256 | // | |
1257 | // I H T | |
1258 | // [A o o o o o o o o o . . . o o o] | |
1259 | // | |
1260 | // H T | |
1261 | // [A o o o o o o o o o . . o o o I] | |
1262 | // M M M | |
1263 | ||
1264 | // copy elements up to new tail | |
c1a9b12d | 1265 | self.copy(self.tail - 1, self.tail, self.cap() - self.tail); |
1a4d82fc JJ |
1266 | |
1267 | // copy last element into empty spot at bottom of buffer | |
c1a9b12d | 1268 | self.copy(self.cap() - 1, 0, 1); |
1a4d82fc JJ |
1269 | |
1270 | self.tail -= 1; | |
1271 | }, | |
1272 | (false, true, false) => unsafe { | |
1273 | // discontiguous, insert closer to tail, head section: | |
1274 | // | |
1275 | // I H T | |
1276 | // [o o o A o o o o o o . . . o o o] | |
1277 | // | |
1278 | // H T | |
1279 | // [o o I A o o o o o o . . o o o o] | |
1280 | // M M M M M M | |
1281 | ||
1282 | // copy elements up to new tail | |
c1a9b12d | 1283 | self.copy(self.tail - 1, self.tail, self.cap() - self.tail); |
1a4d82fc JJ |
1284 | |
1285 | // copy last element into empty spot at bottom of buffer | |
c1a9b12d | 1286 | self.copy(self.cap() - 1, 0, 1); |
1a4d82fc JJ |
1287 | |
1288 | // move elements from idx-1 to end forward not including ^ element | |
1289 | self.copy(0, 1, idx - 1); | |
1290 | ||
1291 | self.tail -= 1; | |
1292 | }, | |
1293 | (false, false, false) => unsafe { | |
1294 | // discontiguous, insert closer to head, head section: | |
1295 | // | |
1296 | // I H T | |
1297 | // [o o o o A o o . . . . . . o o o] | |
1298 | // | |
1299 | // H T | |
1300 | // [o o o o I A o o . . . . . o o o] | |
1301 | // M M M | |
1302 | ||
1303 | self.copy(idx + 1, idx, self.head - idx); | |
1304 | self.head += 1; | |
1305 | } | |
1306 | } | |
1307 | ||
1308 | // tail might've been changed so we need to recalculate | |
c1a9b12d | 1309 | let new_idx = self.wrap_add(self.tail, index); |
1a4d82fc | 1310 | unsafe { |
c1a9b12d | 1311 | self.buffer_write(new_idx, value); |
1a4d82fc JJ |
1312 | } |
1313 | } | |
1314 | ||
c1a9b12d | 1315 | /// Removes and returns the element at `index` from the `VecDeque`. |
1a4d82fc JJ |
1316 | /// Whichever end is closer to the removal point will be moved to make |
1317 | /// room, and all the affected elements will be moved to new positions. | |
c1a9b12d | 1318 | /// Returns `None` if `index` is out of bounds. |
1a4d82fc JJ |
1319 | /// |
1320 | /// # Examples | |
c34b1796 | 1321 | /// ``` |
85aaf69f | 1322 | /// use std::collections::VecDeque; |
1a4d82fc | 1323 | /// |
85aaf69f | 1324 | /// let mut buf = VecDeque::new(); |
c1a9b12d SL |
1325 | /// buf.push_back(1); |
1326 | /// buf.push_back(2); | |
1327 | /// buf.push_back(3); | |
1328 | /// | |
1329 | /// assert_eq!(buf.remove(1), Some(2)); | |
1330 | /// assert_eq!(buf.get(1), Some(&3)); | |
1a4d82fc | 1331 | /// ``` |
85aaf69f | 1332 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d SL |
1333 | pub fn remove(&mut self, index: usize) -> Option<T> { |
1334 | if self.is_empty() || self.len() <= index { | |
1a4d82fc JJ |
1335 | return None; |
1336 | } | |
1337 | ||
1338 | // There are three main cases: | |
1339 | // Elements are contiguous | |
1340 | // Elements are discontiguous and the removal is in the tail section | |
1341 | // Elements are discontiguous and the removal is in the head section | |
1342 | // - special case when elements are technically contiguous, | |
1343 | // but self.head = 0 | |
1344 | // | |
1345 | // For each of those there are two more cases: | |
1346 | // Insert is closer to tail | |
1347 | // Insert is closer to head | |
1348 | // | |
1349 | // Key: H - self.head | |
1350 | // T - self.tail | |
1351 | // o - Valid element | |
1352 | // x - Element marked for removal | |
1353 | // R - Indicates element that is being removed | |
1354 | // M - Indicates element was moved | |
1355 | ||
c1a9b12d | 1356 | let idx = self.wrap_add(self.tail, index); |
1a4d82fc JJ |
1357 | |
1358 | let elem = unsafe { | |
1359 | Some(self.buffer_read(idx)) | |
1360 | }; | |
1361 | ||
c1a9b12d SL |
1362 | let distance_to_tail = index; |
1363 | let distance_to_head = self.len() - index; | |
1a4d82fc JJ |
1364 | |
1365 | let contiguous = self.is_contiguous(); | |
1366 | ||
1367 | match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) { | |
1368 | (true, true, _) => unsafe { | |
1369 | // contiguous, remove closer to tail: | |
1370 | // | |
1371 | // T R H | |
1372 | // [. . . o o x o o o o . . . . . .] | |
1373 | // | |
1374 | // T H | |
1375 | // [. . . . o o o o o o . . . . . .] | |
1376 | // M M | |
1377 | ||
c1a9b12d | 1378 | self.copy(self.tail + 1, self.tail, index); |
1a4d82fc JJ |
1379 | self.tail += 1; |
1380 | }, | |
1381 | (true, false, _) => unsafe { | |
1382 | // contiguous, remove closer to head: | |
1383 | // | |
1384 | // T R H | |
1385 | // [. . . o o o o x o o . . . . . .] | |
1386 | // | |
1387 | // T H | |
1388 | // [. . . o o o o o o . . . . . . .] | |
1389 | // M M | |
1390 | ||
1391 | self.copy(idx, idx + 1, self.head - idx - 1); | |
1392 | self.head -= 1; | |
1393 | }, | |
1394 | (false, true, true) => unsafe { | |
1395 | // discontiguous, remove closer to tail, tail section: | |
1396 | // | |
1397 | // H T R | |
1398 | // [o o o o o o . . . . . o o x o o] | |
1399 | // | |
1400 | // H T | |
1401 | // [o o o o o o . . . . . . o o o o] | |
1402 | // M M | |
1403 | ||
c1a9b12d | 1404 | self.copy(self.tail + 1, self.tail, index); |
c34b1796 | 1405 | self.tail = self.wrap_add(self.tail, 1); |
1a4d82fc JJ |
1406 | }, |
1407 | (false, false, false) => unsafe { | |
1408 | // discontiguous, remove closer to head, head section: | |
1409 | // | |
1410 | // R H T | |
1411 | // [o o o o x o o . . . . . . o o o] | |
1412 | // | |
1413 | // H T | |
1414 | // [o o o o o o . . . . . . . o o o] | |
1415 | // M M | |
1416 | ||
1417 | self.copy(idx, idx + 1, self.head - idx - 1); | |
1418 | self.head -= 1; | |
1419 | }, | |
1420 | (false, false, true) => unsafe { | |
1421 | // discontiguous, remove closer to head, tail section: | |
1422 | // | |
1423 | // H T R | |
1424 | // [o o o . . . . . . o o o o o x o] | |
1425 | // | |
1426 | // H T | |
1427 | // [o o . . . . . . . o o o o o o o] | |
1428 | // M M M M | |
1429 | // | |
1430 | // or quasi-discontiguous, remove next to head, tail section: | |
1431 | // | |
1432 | // H T R | |
1433 | // [. . . . . . . . . o o o o o x o] | |
1434 | // | |
1435 | // T H | |
1436 | // [. . . . . . . . . o o o o o o .] | |
1437 | // M | |
1438 | ||
1439 | // draw in elements in the tail section | |
c1a9b12d | 1440 | self.copy(idx, idx + 1, self.cap() - idx - 1); |
1a4d82fc JJ |
1441 | |
1442 | // Prevents underflow. | |
1443 | if self.head != 0 { | |
1444 | // copy first element into empty spot | |
c1a9b12d | 1445 | self.copy(self.cap() - 1, 0, 1); |
1a4d82fc JJ |
1446 | |
1447 | // move elements in the head section backwards | |
1448 | self.copy(0, 1, self.head - 1); | |
1449 | } | |
1450 | ||
c34b1796 | 1451 | self.head = self.wrap_sub(self.head, 1); |
1a4d82fc JJ |
1452 | }, |
1453 | (false, true, false) => unsafe { | |
1454 | // discontiguous, remove closer to tail, head section: | |
1455 | // | |
1456 | // R H T | |
1457 | // [o o x o o o o o o o . . . o o o] | |
1458 | // | |
1459 | // H T | |
1460 | // [o o o o o o o o o o . . . . o o] | |
1461 | // M M M M M | |
1462 | ||
1463 | // draw in elements up to idx | |
1464 | self.copy(1, 0, idx); | |
1465 | ||
1466 | // copy last element into empty spot | |
c1a9b12d | 1467 | self.copy(0, self.cap() - 1, 1); |
1a4d82fc JJ |
1468 | |
1469 | // move elements from tail to end forward, excluding the last one | |
c1a9b12d | 1470 | self.copy(self.tail + 1, self.tail, self.cap() - self.tail - 1); |
1a4d82fc | 1471 | |
c34b1796 | 1472 | self.tail = self.wrap_add(self.tail, 1); |
1a4d82fc JJ |
1473 | } |
1474 | } | |
1475 | ||
1476 | return elem; | |
1477 | } | |
85aaf69f SL |
1478 | |
1479 | /// Splits the collection into two at the given index. | |
1480 | /// | |
1481 | /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`, | |
1482 | /// and the returned `Self` contains elements `[at, len)`. | |
1483 | /// | |
1484 | /// Note that the capacity of `self` does not change. | |
1485 | /// | |
1486 | /// # Panics | |
1487 | /// | |
1488 | /// Panics if `at > len` | |
1489 | /// | |
1490 | /// # Examples | |
1491 | /// | |
1492 | /// ``` | |
1493 | /// use std::collections::VecDeque; | |
1494 | /// | |
1495 | /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect(); | |
1496 | /// let buf2 = buf.split_off(1); | |
1497 | /// // buf = [1], buf2 = [2, 3] | |
1498 | /// assert_eq!(buf.len(), 1); | |
1499 | /// assert_eq!(buf2.len(), 2); | |
1500 | /// ``` | |
1501 | #[inline] | |
e9174d1e | 1502 | #[stable(feature = "split_off", since = "1.4.0")] |
85aaf69f SL |
1503 | pub fn split_off(&mut self, at: usize) -> Self { |
1504 | let len = self.len(); | |
1505 | assert!(at <= len, "`at` out of bounds"); | |
1506 | ||
1507 | let other_len = len - at; | |
1508 | let mut other = VecDeque::with_capacity(other_len); | |
1509 | ||
1510 | unsafe { | |
1511 | let (first_half, second_half) = self.as_slices(); | |
1512 | ||
1513 | let first_len = first_half.len(); | |
1514 | let second_len = second_half.len(); | |
1515 | if at < first_len { | |
1516 | // `at` lies in the first half. | |
1517 | let amount_in_first = first_len - at; | |
1518 | ||
c34b1796 | 1519 | ptr::copy_nonoverlapping(first_half.as_ptr().offset(at as isize), |
c1a9b12d | 1520 | other.ptr(), |
c34b1796 | 1521 | amount_in_first); |
85aaf69f SL |
1522 | |
1523 | // just take all of the second half. | |
c34b1796 | 1524 | ptr::copy_nonoverlapping(second_half.as_ptr(), |
c1a9b12d | 1525 | other.ptr().offset(amount_in_first as isize), |
c34b1796 | 1526 | second_len); |
85aaf69f SL |
1527 | } else { |
1528 | // `at` lies in the second half, need to factor in the elements we skipped | |
1529 | // in the first half. | |
1530 | let offset = at - first_len; | |
1531 | let amount_in_second = second_len - offset; | |
c34b1796 | 1532 | ptr::copy_nonoverlapping(second_half.as_ptr().offset(offset as isize), |
c1a9b12d | 1533 | other.ptr(), |
c34b1796 | 1534 | amount_in_second); |
85aaf69f SL |
1535 | } |
1536 | } | |
1537 | ||
1538 | // Cleanup where the ends of the buffers are | |
c34b1796 | 1539 | self.head = self.wrap_sub(self.head, other_len); |
85aaf69f SL |
1540 | other.head = other.wrap_index(other_len); |
1541 | ||
1542 | other | |
1543 | } | |
1544 | ||
1545 | /// Moves all the elements of `other` into `Self`, leaving `other` empty. | |
1546 | /// | |
1547 | /// # Panics | |
1548 | /// | |
1549 | /// Panics if the new number of elements in self overflows a `usize`. | |
1550 | /// | |
1551 | /// # Examples | |
1552 | /// | |
1553 | /// ``` | |
1554 | /// use std::collections::VecDeque; | |
1555 | /// | |
1556 | /// let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); | |
1557 | /// let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect(); | |
1558 | /// buf.append(&mut buf2); | |
1559 | /// assert_eq!(buf.len(), 6); | |
1560 | /// assert_eq!(buf2.len(), 0); | |
1561 | /// ``` | |
1562 | #[inline] | |
e9174d1e | 1563 | #[stable(feature = "append", since = "1.4.0")] |
85aaf69f SL |
1564 | pub fn append(&mut self, other: &mut Self) { |
1565 | // naive impl | |
b039eaaf | 1566 | self.extend(other.drain(..)); |
85aaf69f | 1567 | } |
d9579d0f AL |
1568 | |
1569 | /// Retains only the elements specified by the predicate. | |
1570 | /// | |
1571 | /// In other words, remove all elements `e` such that `f(&e)` returns false. | |
1572 | /// This method operates in place and preserves the order of the retained | |
1573 | /// elements. | |
1574 | /// | |
1575 | /// # Examples | |
1576 | /// | |
1577 | /// ``` | |
d9579d0f AL |
1578 | /// use std::collections::VecDeque; |
1579 | /// | |
1580 | /// let mut buf = VecDeque::new(); | |
1581 | /// buf.extend(1..5); | |
1582 | /// buf.retain(|&x| x%2 == 0); | |
1583 | /// | |
1584 | /// let v: Vec<_> = buf.into_iter().collect(); | |
1585 | /// assert_eq!(&v[..], &[2, 4]); | |
1586 | /// ``` | |
e9174d1e | 1587 | #[stable(feature = "vec_deque_retain", since = "1.4.0")] |
d9579d0f AL |
1588 | pub fn retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool { |
1589 | let len = self.len(); | |
1590 | let mut del = 0; | |
1591 | for i in 0..len { | |
1592 | if !f(&self[i]) { | |
1593 | del += 1; | |
1594 | } else if del > 0 { | |
1595 | self.swap(i-del, i); | |
1596 | } | |
1597 | } | |
1598 | if del > 0 { | |
1599 | self.truncate(len - del); | |
1600 | } | |
1601 | } | |
1a4d82fc JJ |
1602 | } |
1603 | ||
85aaf69f | 1604 | impl<T: Clone> VecDeque<T> { |
c1a9b12d | 1605 | /// Modifies the `VecDeque` in-place so that `len()` is equal to new_len, |
1a4d82fc JJ |
1606 | /// either by removing excess elements or by appending copies of a value to the back. |
1607 | /// | |
1608 | /// # Examples | |
1609 | /// | |
1610 | /// ``` | |
c1a9b12d SL |
1611 | /// #![feature(deque_extras)] |
1612 | /// | |
85aaf69f | 1613 | /// use std::collections::VecDeque; |
1a4d82fc | 1614 | /// |
85aaf69f SL |
1615 | /// let mut buf = VecDeque::new(); |
1616 | /// buf.push_back(5); | |
1617 | /// buf.push_back(10); | |
1a4d82fc JJ |
1618 | /// buf.push_back(15); |
1619 | /// buf.resize(2, 0); | |
1620 | /// buf.resize(6, 20); | |
62682a34 | 1621 | /// for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(&buf) { |
1a4d82fc JJ |
1622 | /// assert_eq!(a, b); |
1623 | /// } | |
1624 | /// ``` | |
62682a34 | 1625 | #[unstable(feature = "deque_extras", |
e9174d1e SL |
1626 | reason = "matches collection reform specification; waiting on panic semantics", |
1627 | issue = "27788")] | |
85aaf69f | 1628 | pub fn resize(&mut self, new_len: usize, value: T) { |
1a4d82fc JJ |
1629 | let len = self.len(); |
1630 | ||
1631 | if new_len > len { | |
1632 | self.extend(repeat(value).take(new_len - len)) | |
1633 | } else { | |
1634 | self.truncate(new_len); | |
1635 | } | |
1636 | } | |
1637 | } | |
1638 | ||
1639 | /// Returns the index in the underlying buffer for a given logical element index. | |
1640 | #[inline] | |
85aaf69f | 1641 | fn wrap_index(index: usize, size: usize) -> usize { |
1a4d82fc | 1642 | // size is always a power of 2 |
e9174d1e | 1643 | debug_assert!(size.is_power_of_two()); |
1a4d82fc JJ |
1644 | index & (size - 1) |
1645 | } | |
1646 | ||
1647 | /// Calculate the number of elements left to be read in the buffer | |
1648 | #[inline] | |
85aaf69f | 1649 | fn count(tail: usize, head: usize, size: usize) -> usize { |
1a4d82fc | 1650 | // size is always a power of 2 |
c34b1796 | 1651 | (head.wrapping_sub(tail)) & (size - 1) |
1a4d82fc JJ |
1652 | } |
1653 | ||
85aaf69f SL |
1654 | /// `VecDeque` iterator. |
1655 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
1656 | pub struct Iter<'a, T:'a> { |
1657 | ring: &'a [T], | |
85aaf69f SL |
1658 | tail: usize, |
1659 | head: usize | |
1a4d82fc JJ |
1660 | } |
1661 | ||
1662 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
1663 | impl<'a, T> Clone for Iter<'a, T> { | |
1664 | fn clone(&self) -> Iter<'a, T> { | |
1665 | Iter { | |
1666 | ring: self.ring, | |
1667 | tail: self.tail, | |
1668 | head: self.head | |
1669 | } | |
1670 | } | |
1671 | } | |
1672 | ||
85aaf69f | 1673 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1674 | impl<'a, T> Iterator for Iter<'a, T> { |
1675 | type Item = &'a T; | |
1676 | ||
1677 | #[inline] | |
1678 | fn next(&mut self) -> Option<&'a T> { | |
1679 | if self.tail == self.head { | |
1680 | return None; | |
1681 | } | |
1682 | let tail = self.tail; | |
c34b1796 | 1683 | self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); |
1a4d82fc JJ |
1684 | unsafe { Some(self.ring.get_unchecked(tail)) } |
1685 | } | |
1686 | ||
1687 | #[inline] | |
85aaf69f | 1688 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1689 | let len = count(self.tail, self.head, self.ring.len()); |
1690 | (len, Some(len)) | |
1691 | } | |
1692 | } | |
1693 | ||
85aaf69f | 1694 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1695 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
1696 | #[inline] | |
1697 | fn next_back(&mut self) -> Option<&'a T> { | |
1698 | if self.tail == self.head { | |
1699 | return None; | |
1700 | } | |
c34b1796 | 1701 | self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); |
1a4d82fc JJ |
1702 | unsafe { Some(self.ring.get_unchecked(self.head)) } |
1703 | } | |
1704 | } | |
1705 | ||
85aaf69f | 1706 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1707 | impl<'a, T> ExactSizeIterator for Iter<'a, T> {} |
1708 | ||
85aaf69f SL |
1709 | /// `VecDeque` mutable iterator. |
1710 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 1711 | pub struct IterMut<'a, T:'a> { |
c34b1796 | 1712 | ring: &'a mut [T], |
85aaf69f SL |
1713 | tail: usize, |
1714 | head: usize, | |
1a4d82fc JJ |
1715 | } |
1716 | ||
85aaf69f | 1717 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1718 | impl<'a, T> Iterator for IterMut<'a, T> { |
1719 | type Item = &'a mut T; | |
1720 | ||
1721 | #[inline] | |
1722 | fn next(&mut self) -> Option<&'a mut T> { | |
1723 | if self.tail == self.head { | |
1724 | return None; | |
1725 | } | |
1726 | let tail = self.tail; | |
c34b1796 | 1727 | self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); |
1a4d82fc JJ |
1728 | |
1729 | unsafe { | |
c34b1796 AL |
1730 | let elem = self.ring.get_unchecked_mut(tail); |
1731 | Some(&mut *(elem as *mut _)) | |
1a4d82fc JJ |
1732 | } |
1733 | } | |
1734 | ||
1735 | #[inline] | |
85aaf69f | 1736 | fn size_hint(&self) -> (usize, Option<usize>) { |
c34b1796 | 1737 | let len = count(self.tail, self.head, self.ring.len()); |
1a4d82fc JJ |
1738 | (len, Some(len)) |
1739 | } | |
1740 | } | |
1741 | ||
85aaf69f | 1742 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1743 | impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { |
1744 | #[inline] | |
1745 | fn next_back(&mut self) -> Option<&'a mut T> { | |
1746 | if self.tail == self.head { | |
1747 | return None; | |
1748 | } | |
c34b1796 | 1749 | self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); |
1a4d82fc JJ |
1750 | |
1751 | unsafe { | |
c34b1796 AL |
1752 | let elem = self.ring.get_unchecked_mut(self.head); |
1753 | Some(&mut *(elem as *mut _)) | |
1a4d82fc JJ |
1754 | } |
1755 | } | |
1756 | } | |
1757 | ||
85aaf69f | 1758 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1759 | impl<'a, T> ExactSizeIterator for IterMut<'a, T> {} |
1760 | ||
85aaf69f | 1761 | /// A by-value VecDeque iterator |
c34b1796 | 1762 | #[derive(Clone)] |
85aaf69f | 1763 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1764 | pub struct IntoIter<T> { |
85aaf69f | 1765 | inner: VecDeque<T>, |
1a4d82fc JJ |
1766 | } |
1767 | ||
85aaf69f | 1768 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1769 | impl<T> Iterator for IntoIter<T> { |
1770 | type Item = T; | |
1771 | ||
1772 | #[inline] | |
1773 | fn next(&mut self) -> Option<T> { | |
1774 | self.inner.pop_front() | |
1775 | } | |
1776 | ||
1777 | #[inline] | |
85aaf69f | 1778 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1779 | let len = self.inner.len(); |
1780 | (len, Some(len)) | |
1781 | } | |
1782 | } | |
1783 | ||
85aaf69f | 1784 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1785 | impl<T> DoubleEndedIterator for IntoIter<T> { |
1786 | #[inline] | |
1787 | fn next_back(&mut self) -> Option<T> { | |
1788 | self.inner.pop_back() | |
1789 | } | |
1790 | } | |
1791 | ||
85aaf69f | 1792 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1793 | impl<T> ExactSizeIterator for IntoIter<T> {} |
1794 | ||
85aaf69f | 1795 | /// A draining VecDeque iterator |
62682a34 | 1796 | #[unstable(feature = "drain", |
e9174d1e SL |
1797 | reason = "matches collection reform specification, waiting for dust to settle", |
1798 | issue = "27711")] | |
1a4d82fc | 1799 | pub struct Drain<'a, T: 'a> { |
b039eaaf SL |
1800 | after_tail: usize, |
1801 | after_head: usize, | |
1802 | iter: Iter<'a, T>, | |
1803 | deque: *mut VecDeque<T>, | |
1a4d82fc JJ |
1804 | } |
1805 | ||
b039eaaf SL |
1806 | unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {} |
1807 | unsafe impl<'a, T: Send> Send for Drain<'a, T> {} | |
1808 | ||
85aaf69f | 1809 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1810 | impl<'a, T: 'a> Drop for Drain<'a, T> { |
1811 | fn drop(&mut self) { | |
85aaf69f | 1812 | for _ in self.by_ref() {} |
b039eaaf SL |
1813 | |
1814 | let source_deque = unsafe { &mut *self.deque }; | |
1815 | ||
1816 | // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head | |
1817 | // | |
1818 | // T t h H | |
1819 | // [. . . o o x x o o . . .] | |
1820 | // | |
1821 | let orig_tail = source_deque.tail; | |
1822 | let drain_tail = source_deque.head; | |
1823 | let drain_head = self.after_tail; | |
1824 | let orig_head = self.after_head; | |
1825 | ||
1826 | let tail_len = count(orig_tail, drain_tail, source_deque.cap()); | |
1827 | let head_len = count(drain_head, orig_head, source_deque.cap()); | |
1828 | ||
1829 | // Restore the original head value | |
1830 | source_deque.head = orig_head; | |
1831 | ||
1832 | match (tail_len, head_len) { | |
1833 | (0, 0) => { | |
1834 | source_deque.head = 0; | |
1835 | source_deque.tail = 0; | |
1836 | } | |
1837 | (0, _) => { | |
1838 | source_deque.tail = drain_head; | |
1839 | } | |
1840 | (_, 0) => { | |
1841 | source_deque.head = drain_tail; | |
1842 | } | |
1843 | _ => unsafe { | |
1844 | if tail_len <= head_len { | |
1845 | source_deque.tail = source_deque.wrap_sub(drain_head, tail_len); | |
1846 | source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len); | |
1847 | } else { | |
1848 | source_deque.head = source_deque.wrap_add(drain_tail, head_len); | |
1849 | source_deque.wrap_copy(drain_tail, drain_head, head_len); | |
1850 | } | |
1851 | } | |
1852 | } | |
1a4d82fc JJ |
1853 | } |
1854 | } | |
1855 | ||
85aaf69f | 1856 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1857 | impl<'a, T: 'a> Iterator for Drain<'a, T> { |
1858 | type Item = T; | |
1859 | ||
1860 | #[inline] | |
1861 | fn next(&mut self) -> Option<T> { | |
b039eaaf SL |
1862 | self.iter.next().map(|elt| |
1863 | unsafe { | |
1864 | ptr::read(elt) | |
1865 | } | |
1866 | ) | |
1a4d82fc JJ |
1867 | } |
1868 | ||
1869 | #[inline] | |
85aaf69f | 1870 | fn size_hint(&self) -> (usize, Option<usize>) { |
b039eaaf | 1871 | self.iter.size_hint() |
1a4d82fc JJ |
1872 | } |
1873 | } | |
1874 | ||
85aaf69f | 1875 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1876 | impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> { |
1877 | #[inline] | |
1878 | fn next_back(&mut self) -> Option<T> { | |
b039eaaf SL |
1879 | self.iter.next_back().map(|elt| |
1880 | unsafe { | |
1881 | ptr::read(elt) | |
1882 | } | |
1883 | ) | |
1a4d82fc JJ |
1884 | } |
1885 | } | |
1886 | ||
85aaf69f | 1887 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1888 | impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {} |
1889 | ||
85aaf69f SL |
1890 | #[stable(feature = "rust1", since = "1.0.0")] |
1891 | impl<A: PartialEq> PartialEq for VecDeque<A> { | |
1892 | fn eq(&self, other: &VecDeque<A>) -> bool { | |
1a4d82fc | 1893 | self.len() == other.len() && |
62682a34 | 1894 | self.iter().zip(other).all(|(a, b)| a.eq(b)) |
1a4d82fc JJ |
1895 | } |
1896 | } | |
1897 | ||
85aaf69f SL |
1898 | #[stable(feature = "rust1", since = "1.0.0")] |
1899 | impl<A: Eq> Eq for VecDeque<A> {} | |
1a4d82fc | 1900 | |
85aaf69f SL |
1901 | #[stable(feature = "rust1", since = "1.0.0")] |
1902 | impl<A: PartialOrd> PartialOrd for VecDeque<A> { | |
1903 | fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering> { | |
e9174d1e | 1904 | self.iter().partial_cmp(other.iter()) |
1a4d82fc JJ |
1905 | } |
1906 | } | |
1907 | ||
85aaf69f SL |
1908 | #[stable(feature = "rust1", since = "1.0.0")] |
1909 | impl<A: Ord> Ord for VecDeque<A> { | |
1a4d82fc | 1910 | #[inline] |
85aaf69f | 1911 | fn cmp(&self, other: &VecDeque<A>) -> Ordering { |
e9174d1e | 1912 | self.iter().cmp(other.iter()) |
1a4d82fc JJ |
1913 | } |
1914 | } | |
1915 | ||
85aaf69f | 1916 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
1917 | impl<A: Hash> Hash for VecDeque<A> { |
1918 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1919 | self.len().hash(state); | |
1920 | for elt in self { | |
1a4d82fc JJ |
1921 | elt.hash(state); |
1922 | } | |
1923 | } | |
1924 | } | |
1925 | ||
85aaf69f SL |
1926 | #[stable(feature = "rust1", since = "1.0.0")] |
1927 | impl<A> Index<usize> for VecDeque<A> { | |
1a4d82fc JJ |
1928 | type Output = A; |
1929 | ||
1930 | #[inline] | |
c1a9b12d SL |
1931 | fn index(&self, index: usize) -> &A { |
1932 | self.get(index).expect("Out of bounds access") | |
1a4d82fc JJ |
1933 | } |
1934 | } | |
1935 | ||
85aaf69f SL |
1936 | #[stable(feature = "rust1", since = "1.0.0")] |
1937 | impl<A> IndexMut<usize> for VecDeque<A> { | |
1a4d82fc | 1938 | #[inline] |
c1a9b12d SL |
1939 | fn index_mut(&mut self, index: usize) -> &mut A { |
1940 | self.get_mut(index).expect("Out of bounds access") | |
1a4d82fc JJ |
1941 | } |
1942 | } | |
1943 | ||
85aaf69f SL |
1944 | #[stable(feature = "rust1", since = "1.0.0")] |
1945 | impl<A> FromIterator<A> for VecDeque<A> { | |
1946 | fn from_iter<T: IntoIterator<Item=A>>(iterable: T) -> VecDeque<A> { | |
1947 | let iterator = iterable.into_iter(); | |
1a4d82fc | 1948 | let (lower, _) = iterator.size_hint(); |
85aaf69f | 1949 | let mut deq = VecDeque::with_capacity(lower); |
1a4d82fc JJ |
1950 | deq.extend(iterator); |
1951 | deq | |
1952 | } | |
1953 | } | |
1954 | ||
85aaf69f SL |
1955 | #[stable(feature = "rust1", since = "1.0.0")] |
1956 | impl<T> IntoIterator for VecDeque<T> { | |
1957 | type Item = T; | |
1958 | type IntoIter = IntoIter<T>; | |
1959 | ||
9346a6ac AL |
1960 | /// Consumes the list into a front-to-back iterator yielding elements by |
1961 | /// value. | |
85aaf69f | 1962 | fn into_iter(self) -> IntoIter<T> { |
9346a6ac AL |
1963 | IntoIter { |
1964 | inner: self, | |
1965 | } | |
85aaf69f SL |
1966 | } |
1967 | } | |
1968 | ||
1969 | #[stable(feature = "rust1", since = "1.0.0")] | |
1970 | impl<'a, T> IntoIterator for &'a VecDeque<T> { | |
1971 | type Item = &'a T; | |
1972 | type IntoIter = Iter<'a, T>; | |
1973 | ||
1974 | fn into_iter(self) -> Iter<'a, T> { | |
1975 | self.iter() | |
1976 | } | |
1977 | } | |
1978 | ||
1979 | #[stable(feature = "rust1", since = "1.0.0")] | |
1980 | impl<'a, T> IntoIterator for &'a mut VecDeque<T> { | |
1981 | type Item = &'a mut T; | |
1982 | type IntoIter = IterMut<'a, T>; | |
1983 | ||
1984 | fn into_iter(mut self) -> IterMut<'a, T> { | |
1985 | self.iter_mut() | |
1986 | } | |
1987 | } | |
1988 | ||
1989 | #[stable(feature = "rust1", since = "1.0.0")] | |
1990 | impl<A> Extend<A> for VecDeque<A> { | |
1991 | fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T) { | |
1992 | for elt in iter { | |
1a4d82fc JJ |
1993 | self.push_back(elt); |
1994 | } | |
1995 | } | |
1996 | } | |
1997 | ||
62682a34 SL |
1998 | #[stable(feature = "extend_ref", since = "1.2.0")] |
1999 | impl<'a, T: 'a + Copy> Extend<&'a T> for VecDeque<T> { | |
2000 | fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) { | |
2001 | self.extend(iter.into_iter().cloned()); | |
2002 | } | |
2003 | } | |
2004 | ||
85aaf69f SL |
2005 | #[stable(feature = "rust1", since = "1.0.0")] |
2006 | impl<T: fmt::Debug> fmt::Debug for VecDeque<T> { | |
1a4d82fc | 2007 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
b039eaaf | 2008 | f.debug_list().entries(self).finish() |
1a4d82fc JJ |
2009 | } |
2010 | } | |
2011 | ||
2012 | #[cfg(test)] | |
d9579d0f | 2013 | mod tests { |
62682a34 | 2014 | use core::iter::Iterator; |
c34b1796 AL |
2015 | use core::option::Option::Some; |
2016 | ||
1a4d82fc JJ |
2017 | use test; |
2018 | ||
85aaf69f | 2019 | use super::VecDeque; |
1a4d82fc | 2020 | |
1a4d82fc JJ |
2021 | #[bench] |
2022 | fn bench_push_back_100(b: &mut test::Bencher) { | |
85aaf69f | 2023 | let mut deq = VecDeque::with_capacity(101); |
1a4d82fc | 2024 | b.iter(|| { |
85aaf69f | 2025 | for i in 0..100 { |
1a4d82fc JJ |
2026 | deq.push_back(i); |
2027 | } | |
2028 | deq.head = 0; | |
2029 | deq.tail = 0; | |
2030 | }) | |
2031 | } | |
2032 | ||
2033 | #[bench] | |
2034 | fn bench_push_front_100(b: &mut test::Bencher) { | |
85aaf69f | 2035 | let mut deq = VecDeque::with_capacity(101); |
1a4d82fc | 2036 | b.iter(|| { |
85aaf69f | 2037 | for i in 0..100 { |
1a4d82fc JJ |
2038 | deq.push_front(i); |
2039 | } | |
2040 | deq.head = 0; | |
2041 | deq.tail = 0; | |
2042 | }) | |
2043 | } | |
2044 | ||
2045 | #[bench] | |
2046 | fn bench_pop_back_100(b: &mut test::Bencher) { | |
85aaf69f | 2047 | let mut deq= VecDeque::<i32>::with_capacity(101); |
1a4d82fc JJ |
2048 | |
2049 | b.iter(|| { | |
2050 | deq.head = 100; | |
2051 | deq.tail = 0; | |
2052 | while !deq.is_empty() { | |
2053 | test::black_box(deq.pop_back()); | |
2054 | } | |
2055 | }) | |
2056 | } | |
2057 | ||
2058 | #[bench] | |
2059 | fn bench_pop_front_100(b: &mut test::Bencher) { | |
85aaf69f | 2060 | let mut deq = VecDeque::<i32>::with_capacity(101); |
1a4d82fc JJ |
2061 | |
2062 | b.iter(|| { | |
2063 | deq.head = 100; | |
2064 | deq.tail = 0; | |
2065 | while !deq.is_empty() { | |
2066 | test::black_box(deq.pop_front()); | |
2067 | } | |
2068 | }) | |
2069 | } | |
2070 | ||
1a4d82fc JJ |
2071 | #[test] |
2072 | fn test_swap_front_back_remove() { | |
2073 | fn test(back: bool) { | |
2074 | // This test checks that every single combination of tail position and length is tested. | |
2075 | // Capacity 15 should be large enough to cover every case. | |
85aaf69f | 2076 | let mut tester = VecDeque::with_capacity(15); |
1a4d82fc JJ |
2077 | let usable_cap = tester.capacity(); |
2078 | let final_len = usable_cap / 2; | |
2079 | ||
85aaf69f | 2080 | for len in 0..final_len { |
1a4d82fc | 2081 | let expected = if back { |
85aaf69f | 2082 | (0..len).collect() |
1a4d82fc | 2083 | } else { |
85aaf69f | 2084 | (0..len).rev().collect() |
1a4d82fc | 2085 | }; |
85aaf69f | 2086 | for tail_pos in 0..usable_cap { |
1a4d82fc JJ |
2087 | tester.tail = tail_pos; |
2088 | tester.head = tail_pos; | |
2089 | if back { | |
85aaf69f | 2090 | for i in 0..len * 2 { |
1a4d82fc JJ |
2091 | tester.push_front(i); |
2092 | } | |
85aaf69f | 2093 | for i in 0..len { |
1a4d82fc JJ |
2094 | assert_eq!(tester.swap_back_remove(i), Some(len * 2 - 1 - i)); |
2095 | } | |
2096 | } else { | |
85aaf69f | 2097 | for i in 0..len * 2 { |
1a4d82fc JJ |
2098 | tester.push_back(i); |
2099 | } | |
85aaf69f | 2100 | for i in 0..len { |
1a4d82fc JJ |
2101 | let idx = tester.len() - 1 - i; |
2102 | assert_eq!(tester.swap_front_remove(idx), Some(len * 2 - 1 - i)); | |
2103 | } | |
2104 | } | |
c1a9b12d SL |
2105 | assert!(tester.tail < tester.cap()); |
2106 | assert!(tester.head < tester.cap()); | |
1a4d82fc JJ |
2107 | assert_eq!(tester, expected); |
2108 | } | |
2109 | } | |
2110 | } | |
2111 | test(true); | |
2112 | test(false); | |
2113 | } | |
2114 | ||
2115 | #[test] | |
2116 | fn test_insert() { | |
2117 | // This test checks that every single combination of tail position, length, and | |
2118 | // insertion position is tested. Capacity 15 should be large enough to cover every case. | |
2119 | ||
85aaf69f | 2120 | let mut tester = VecDeque::with_capacity(15); |
1a4d82fc JJ |
2121 | // can't guarantee we got 15, so have to get what we got. |
2122 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
2123 | // this test isn't covering what it wants to | |
2124 | let cap = tester.capacity(); | |
2125 | ||
2126 | ||
2127 | // len is the length *after* insertion | |
85aaf69f | 2128 | for len in 1..cap { |
1a4d82fc | 2129 | // 0, 1, 2, .., len - 1 |
c34b1796 | 2130 | let expected = (0..).take(len).collect(); |
85aaf69f SL |
2131 | for tail_pos in 0..cap { |
2132 | for to_insert in 0..len { | |
1a4d82fc JJ |
2133 | tester.tail = tail_pos; |
2134 | tester.head = tail_pos; | |
85aaf69f | 2135 | for i in 0..len { |
1a4d82fc JJ |
2136 | if i != to_insert { |
2137 | tester.push_back(i); | |
2138 | } | |
2139 | } | |
2140 | tester.insert(to_insert, to_insert); | |
c1a9b12d SL |
2141 | assert!(tester.tail < tester.cap()); |
2142 | assert!(tester.head < tester.cap()); | |
1a4d82fc JJ |
2143 | assert_eq!(tester, expected); |
2144 | } | |
2145 | } | |
2146 | } | |
2147 | } | |
2148 | ||
2149 | #[test] | |
2150 | fn test_remove() { | |
2151 | // This test checks that every single combination of tail position, length, and | |
2152 | // removal position is tested. Capacity 15 should be large enough to cover every case. | |
2153 | ||
85aaf69f | 2154 | let mut tester = VecDeque::with_capacity(15); |
1a4d82fc JJ |
2155 | // can't guarantee we got 15, so have to get what we got. |
2156 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
2157 | // this test isn't covering what it wants to | |
2158 | let cap = tester.capacity(); | |
2159 | ||
2160 | // len is the length *after* removal | |
85aaf69f | 2161 | for len in 0..cap - 1 { |
1a4d82fc | 2162 | // 0, 1, 2, .., len - 1 |
c34b1796 | 2163 | let expected = (0..).take(len).collect(); |
85aaf69f SL |
2164 | for tail_pos in 0..cap { |
2165 | for to_remove in 0..len + 1 { | |
1a4d82fc JJ |
2166 | tester.tail = tail_pos; |
2167 | tester.head = tail_pos; | |
85aaf69f | 2168 | for i in 0..len { |
1a4d82fc JJ |
2169 | if i == to_remove { |
2170 | tester.push_back(1234); | |
2171 | } | |
2172 | tester.push_back(i); | |
2173 | } | |
2174 | if to_remove == len { | |
2175 | tester.push_back(1234); | |
2176 | } | |
2177 | tester.remove(to_remove); | |
c1a9b12d SL |
2178 | assert!(tester.tail < tester.cap()); |
2179 | assert!(tester.head < tester.cap()); | |
1a4d82fc JJ |
2180 | assert_eq!(tester, expected); |
2181 | } | |
2182 | } | |
2183 | } | |
2184 | } | |
2185 | ||
b039eaaf SL |
2186 | #[test] |
2187 | fn test_drain() { | |
2188 | let mut tester: VecDeque<usize> = VecDeque::with_capacity(7); | |
2189 | ||
2190 | let cap = tester.capacity(); | |
2191 | for len in 0..cap + 1 { | |
2192 | for tail in 0..cap + 1 { | |
2193 | for drain_start in 0..len + 1 { | |
2194 | for drain_end in drain_start..len + 1 { | |
2195 | tester.tail = tail; | |
2196 | tester.head = tail; | |
2197 | for i in 0..len { | |
2198 | tester.push_back(i); | |
2199 | } | |
2200 | ||
2201 | // Check that we drain the correct values | |
2202 | let drained: VecDeque<_> = | |
2203 | tester.drain(drain_start..drain_end).collect(); | |
2204 | let drained_expected: VecDeque<_> = | |
2205 | (drain_start..drain_end).collect(); | |
2206 | assert_eq!(drained, drained_expected); | |
2207 | ||
2208 | // We shouldn't have changed the capacity or made the | |
2209 | // head or tail out of bounds | |
2210 | assert_eq!(tester.capacity(), cap); | |
2211 | assert!(tester.tail < tester.cap()); | |
2212 | assert!(tester.head < tester.cap()); | |
2213 | ||
2214 | // We should see the correct values in the VecDeque | |
2215 | let expected: VecDeque<_> = | |
2216 | (0..drain_start).chain(drain_end..len).collect(); | |
2217 | assert_eq!(expected, tester); | |
2218 | } | |
2219 | } | |
2220 | } | |
2221 | } | |
2222 | } | |
2223 | ||
1a4d82fc JJ |
2224 | #[test] |
2225 | fn test_shrink_to_fit() { | |
2226 | // This test checks that every single combination of head and tail position, | |
2227 | // is tested. Capacity 15 should be large enough to cover every case. | |
2228 | ||
85aaf69f | 2229 | let mut tester = VecDeque::with_capacity(15); |
1a4d82fc JJ |
2230 | // can't guarantee we got 15, so have to get what we got. |
2231 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
2232 | // this test isn't covering what it wants to | |
2233 | let cap = tester.capacity(); | |
2234 | tester.reserve(63); | |
2235 | let max_cap = tester.capacity(); | |
2236 | ||
85aaf69f | 2237 | for len in 0..cap + 1 { |
1a4d82fc | 2238 | // 0, 1, 2, .., len - 1 |
c34b1796 | 2239 | let expected = (0..).take(len).collect(); |
85aaf69f | 2240 | for tail_pos in 0..max_cap + 1 { |
1a4d82fc JJ |
2241 | tester.tail = tail_pos; |
2242 | tester.head = tail_pos; | |
2243 | tester.reserve(63); | |
85aaf69f | 2244 | for i in 0..len { |
1a4d82fc JJ |
2245 | tester.push_back(i); |
2246 | } | |
2247 | tester.shrink_to_fit(); | |
2248 | assert!(tester.capacity() <= cap); | |
c1a9b12d SL |
2249 | assert!(tester.tail < tester.cap()); |
2250 | assert!(tester.head < tester.cap()); | |
1a4d82fc JJ |
2251 | assert_eq!(tester, expected); |
2252 | } | |
2253 | } | |
2254 | } | |
2255 | ||
85aaf69f SL |
2256 | #[test] |
2257 | fn test_split_off() { | |
2258 | // This test checks that every single combination of tail position, length, and | |
2259 | // split position is tested. Capacity 15 should be large enough to cover every case. | |
2260 | ||
2261 | let mut tester = VecDeque::with_capacity(15); | |
2262 | // can't guarantee we got 15, so have to get what we got. | |
2263 | // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else | |
2264 | // this test isn't covering what it wants to | |
2265 | let cap = tester.capacity(); | |
2266 | ||
2267 | // len is the length *before* splitting | |
2268 | for len in 0..cap { | |
2269 | // index to split at | |
2270 | for at in 0..len + 1 { | |
2271 | // 0, 1, 2, .., at - 1 (may be empty) | |
c34b1796 | 2272 | let expected_self = (0..).take(at).collect(); |
85aaf69f | 2273 | // at, at + 1, .., len - 1 (may be empty) |
c34b1796 | 2274 | let expected_other = (at..).take(len - at).collect(); |
85aaf69f SL |
2275 | |
2276 | for tail_pos in 0..cap { | |
2277 | tester.tail = tail_pos; | |
2278 | tester.head = tail_pos; | |
2279 | for i in 0..len { | |
2280 | tester.push_back(i); | |
2281 | } | |
2282 | let result = tester.split_off(at); | |
c1a9b12d SL |
2283 | assert!(tester.tail < tester.cap()); |
2284 | assert!(tester.head < tester.cap()); | |
2285 | assert!(result.tail < result.cap()); | |
2286 | assert!(result.head < result.cap()); | |
85aaf69f SL |
2287 | assert_eq!(tester, expected_self); |
2288 | assert_eq!(result, expected_other); | |
2289 | } | |
2290 | } | |
2291 | } | |
2292 | } | |
e9174d1e SL |
2293 | |
2294 | #[test] | |
2295 | fn test_zst_push() { | |
2296 | const N: usize = 8; | |
2297 | ||
2298 | // Zero sized type | |
2299 | struct Zst; | |
2300 | ||
2301 | // Test that for all possible sequences of push_front / push_back, | |
2302 | // we end up with a deque of the correct size | |
2303 | ||
2304 | for len in 0..N { | |
2305 | let mut tester = VecDeque::with_capacity(len); | |
2306 | assert_eq!(tester.len(), 0); | |
2307 | assert!(tester.capacity() >= len); | |
2308 | for case in 0..(1 << len) { | |
2309 | assert_eq!(tester.len(), 0); | |
2310 | for bit in 0..len { | |
2311 | if case & (1 << bit) != 0 { | |
2312 | tester.push_front(Zst); | |
2313 | } else { | |
2314 | tester.push_back(Zst); | |
2315 | } | |
2316 | } | |
2317 | assert_eq!(tester.len(), len); | |
2318 | assert_eq!(tester.iter().count(), len); | |
2319 | tester.clear(); | |
2320 | } | |
2321 | } | |
2322 | } | |
1a4d82fc | 2323 | } |