]>
Commit | Line | Data |
---|---|---|
cc61c64b | 1 | //! A double-ended queue implemented with a growable ring buffer. |
85aaf69f SL |
2 | //! |
3 | //! This queue has `O(1)` amortized inserts and removals from both ends of the | |
4 | //! container. It also has `O(1)` indexing like a vector. The contained elements | |
5 | //! are not required to be copyable, and the queue will be sendable if the | |
6 | //! contained type is sendable. | |
1a4d82fc | 7 | |
85aaf69f | 8 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 9 | |
416331ca | 10 | use core::array::LengthAtMost32; |
9fa01778 | 11 | use core::cmp::{self, Ordering}; |
1a4d82fc | 12 | use core::fmt; |
e74abb32 XL |
13 | use core::iter::{once, repeat_with, FromIterator, FusedIterator}; |
14 | use core::mem::{self, replace}; | |
0531ce1d | 15 | use core::ops::Bound::{Excluded, Included, Unbounded}; |
9fa01778 XL |
16 | use core::ops::{Index, IndexMut, RangeBounds, Try}; |
17 | use core::ptr::{self, NonNull}; | |
c34b1796 | 18 | use core::slice; |
85aaf69f | 19 | use core::hash::{Hash, Hasher}; |
1a4d82fc | 20 | |
e1599b0c | 21 | use crate::collections::TryReserveError; |
9fa01778 XL |
22 | use crate::raw_vec::RawVec; |
23 | use crate::vec::Vec; | |
b039eaaf | 24 | |
416331ca XL |
25 | #[cfg(test)] |
26 | mod tests; | |
27 | ||
c34b1796 AL |
28 | const INITIAL_CAPACITY: usize = 7; // 2^3 - 1 |
29 | const MINIMUM_CAPACITY: usize = 1; // 2 - 1 | |
a1dfa0c6 XL |
30 | #[cfg(target_pointer_width = "16")] |
31 | const MAXIMUM_ZST_CAPACITY: usize = 1 << (16 - 1); // Largest possible power of two | |
9cc50fc6 SL |
32 | #[cfg(target_pointer_width = "32")] |
33 | const MAXIMUM_ZST_CAPACITY: usize = 1 << (32 - 1); // Largest possible power of two | |
34 | #[cfg(target_pointer_width = "64")] | |
35 | const MAXIMUM_ZST_CAPACITY: usize = 1 << (64 - 1); // Largest possible power of two | |
85aaf69f | 36 | |
cc61c64b | 37 | /// A double-ended queue implemented with a growable ring buffer. |
c1a9b12d | 38 | /// |
cc61c64b XL |
39 | /// The "default" usage of this type as a queue is to use [`push_back`] to add to |
40 | /// the queue, and [`pop_front`] to remove from the queue. [`extend`] and [`append`] | |
b039eaaf SL |
41 | /// push onto the back in this manner, and iterating over `VecDeque` goes front |
42 | /// to back. | |
cc61c64b XL |
43 | /// |
44 | /// [`push_back`]: #method.push_back | |
45 | /// [`pop_front`]: #method.pop_front | |
46 | /// [`extend`]: #method.extend | |
47 | /// [`append`]: #method.append | |
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 | 54 | // is defined as the distance between the two. |
85aaf69f SL |
55 | tail: usize, |
56 | head: usize, | |
c1a9b12d | 57 | buf: RawVec<T>, |
1a4d82fc JJ |
58 | } |
59 | ||
e74abb32 XL |
60 | /// PairSlices pairs up equal length slice parts of two deques |
61 | /// | |
62 | /// For example, given deques "A" and "B" with the following division into slices: | |
63 | /// | |
64 | /// A: [0 1 2] [3 4 5] | |
65 | /// B: [a b] [c d e] | |
66 | /// | |
67 | /// It produces the following sequence of matching slices: | |
68 | /// | |
69 | /// ([0 1], [a b]) | |
70 | /// ([2], [c]) | |
71 | /// ([3 4], [d e]) | |
72 | /// | |
73 | /// and the uneven remainder of either A or B is skipped. | |
74 | struct PairSlices<'a, 'b, T> { | |
75 | a0: &'a mut [T], | |
76 | a1: &'a mut [T], | |
77 | b0: &'b [T], | |
78 | b1: &'b [T], | |
79 | } | |
80 | ||
81 | impl<'a, 'b, T> PairSlices<'a, 'b, T> { | |
82 | fn from(to: &'a mut VecDeque<T>, from: &'b VecDeque<T>) -> Self { | |
83 | let (a0, a1) = to.as_mut_slices(); | |
84 | let (b0, b1) = from.as_slices(); | |
85 | PairSlices { a0, a1, b0, b1 } | |
86 | } | |
87 | ||
88 | fn has_remainder(&self) -> bool { | |
89 | !self.b0.is_empty() | |
90 | } | |
91 | ||
92 | fn remainder(self) -> impl Iterator<Item=&'b [T]> { | |
93 | once(self.b0).chain(once(self.b1)) | |
94 | } | |
95 | } | |
96 | ||
97 | impl<'a, 'b, T> Iterator for PairSlices<'a, 'b, T> | |
98 | { | |
99 | type Item = (&'a mut [T], &'b [T]); | |
100 | fn next(&mut self) -> Option<Self::Item> { | |
101 | // Get next part length | |
102 | let part = cmp::min(self.a0.len(), self.b0.len()); | |
103 | if part == 0 { | |
104 | return None; | |
105 | } | |
106 | let (p0, p1) = replace(&mut self.a0, &mut []).split_at_mut(part); | |
107 | let (q0, q1) = self.b0.split_at(part); | |
108 | ||
109 | // Move a1 into a0, if it's empty (and b1, b0 the same way). | |
110 | self.a0 = p1; | |
111 | self.b0 = q1; | |
112 | if self.a0.is_empty() { | |
113 | self.a0 = replace(&mut self.a1, &mut []); | |
114 | } | |
115 | if self.b0.is_empty() { | |
116 | self.b0 = replace(&mut self.b1, &[]); | |
117 | } | |
118 | Some((p0, q0)) | |
119 | } | |
120 | } | |
121 | ||
85aaf69f SL |
122 | #[stable(feature = "rust1", since = "1.0.0")] |
123 | impl<T: Clone> Clone for VecDeque<T> { | |
124 | fn clone(&self) -> VecDeque<T> { | |
125 | self.iter().cloned().collect() | |
1a4d82fc | 126 | } |
e74abb32 XL |
127 | |
128 | fn clone_from(&mut self, other: &Self) { | |
129 | self.truncate(other.len()); | |
130 | ||
131 | let mut iter = PairSlices::from(self, other); | |
132 | while let Some((dst, src)) = iter.next() { | |
133 | dst.clone_from_slice(&src); | |
134 | } | |
135 | ||
136 | if iter.has_remainder() { | |
137 | for remainder in iter.remainder() { | |
138 | self.extend(remainder.iter().cloned()); | |
139 | } | |
140 | } | |
141 | } | |
1a4d82fc JJ |
142 | } |
143 | ||
85aaf69f | 144 | #[stable(feature = "rust1", since = "1.0.0")] |
32a655c1 | 145 | unsafe impl<#[may_dangle] T> Drop for VecDeque<T> { |
1a4d82fc | 146 | fn drop(&mut self) { |
60c5eb7d XL |
147 | /// Runs the destructor for all items in the slice when it gets dropped (normally or |
148 | /// during unwinding). | |
149 | struct Dropper<'a, T>(&'a mut [T]); | |
150 | ||
151 | impl<'a, T> Drop for Dropper<'a, T> { | |
152 | fn drop(&mut self) { | |
153 | unsafe { | |
154 | ptr::drop_in_place(self.0); | |
155 | } | |
156 | } | |
157 | } | |
158 | ||
54a0048b SL |
159 | let (front, back) = self.as_mut_slices(); |
160 | unsafe { | |
60c5eb7d | 161 | let _back_dropper = Dropper(back); |
54a0048b SL |
162 | // use drop for [T] |
163 | ptr::drop_in_place(front); | |
54a0048b | 164 | } |
c1a9b12d | 165 | // RawVec handles deallocation |
1a4d82fc JJ |
166 | } |
167 | } | |
168 | ||
85aaf69f SL |
169 | #[stable(feature = "rust1", since = "1.0.0")] |
170 | impl<T> Default for VecDeque<T> { | |
9e0c209e | 171 | /// Creates an empty `VecDeque<T>`. |
1a4d82fc | 172 | #[inline] |
92a42be0 SL |
173 | fn default() -> VecDeque<T> { |
174 | VecDeque::new() | |
175 | } | |
1a4d82fc JJ |
176 | } |
177 | ||
85aaf69f | 178 | impl<T> VecDeque<T> { |
c1a9b12d SL |
179 | /// Marginally more convenient |
180 | #[inline] | |
181 | fn ptr(&self) -> *mut T { | |
182 | self.buf.ptr() | |
183 | } | |
184 | ||
185 | /// Marginally more convenient | |
186 | #[inline] | |
187 | fn cap(&self) -> usize { | |
e9174d1e SL |
188 | if mem::size_of::<T>() == 0 { |
189 | // For zero sized types, we are always at maximum capacity | |
190 | MAXIMUM_ZST_CAPACITY | |
191 | } else { | |
416331ca | 192 | self.buf.capacity() |
e9174d1e | 193 | } |
c1a9b12d SL |
194 | } |
195 | ||
1a4d82fc JJ |
196 | /// Turn ptr into a slice |
197 | #[inline] | |
198 | unsafe fn buffer_as_slice(&self) -> &[T] { | |
c1a9b12d | 199 | slice::from_raw_parts(self.ptr(), self.cap()) |
1a4d82fc JJ |
200 | } |
201 | ||
202 | /// Turn ptr into a mut slice | |
203 | #[inline] | |
204 | unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] { | |
c1a9b12d | 205 | slice::from_raw_parts_mut(self.ptr(), self.cap()) |
1a4d82fc JJ |
206 | } |
207 | ||
208 | /// Moves an element out of the buffer | |
209 | #[inline] | |
85aaf69f | 210 | unsafe fn buffer_read(&mut self, off: usize) -> T { |
b7449926 | 211 | ptr::read(self.ptr().add(off)) |
1a4d82fc JJ |
212 | } |
213 | ||
214 | /// Writes an element into the buffer, moving it. | |
215 | #[inline] | |
c1a9b12d | 216 | unsafe fn buffer_write(&mut self, off: usize, value: T) { |
b7449926 | 217 | ptr::write(self.ptr().add(off), value); |
1a4d82fc JJ |
218 | } |
219 | ||
9fa01778 | 220 | /// Returns `true` if the buffer is at full capacity. |
1a4d82fc | 221 | #[inline] |
92a42be0 SL |
222 | fn is_full(&self) -> bool { |
223 | self.cap() - self.len() == 1 | |
224 | } | |
1a4d82fc | 225 | |
85aaf69f SL |
226 | /// Returns the index in the underlying buffer for a given logical element |
227 | /// index. | |
1a4d82fc | 228 | #[inline] |
92a42be0 SL |
229 | fn wrap_index(&self, idx: usize) -> usize { |
230 | wrap_index(idx, self.cap()) | |
231 | } | |
1a4d82fc | 232 | |
c34b1796 AL |
233 | /// Returns the index in the underlying buffer for a given logical element |
234 | /// index + addend. | |
235 | #[inline] | |
236 | fn wrap_add(&self, idx: usize, addend: usize) -> usize { | |
c1a9b12d | 237 | wrap_index(idx.wrapping_add(addend), self.cap()) |
c34b1796 AL |
238 | } |
239 | ||
240 | /// Returns the index in the underlying buffer for a given logical element | |
241 | /// index - subtrahend. | |
242 | #[inline] | |
243 | fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize { | |
c1a9b12d | 244 | wrap_index(idx.wrapping_sub(subtrahend), self.cap()) |
c34b1796 AL |
245 | } |
246 | ||
1a4d82fc JJ |
247 | /// Copies a contiguous block of memory len long from src to dst |
248 | #[inline] | |
85aaf69f | 249 | unsafe fn copy(&self, dst: usize, src: usize, len: usize) { |
92a42be0 SL |
250 | debug_assert!(dst + len <= self.cap(), |
251 | "cpy dst={} src={} len={} cap={}", | |
252 | dst, | |
253 | src, | |
254 | len, | |
c1a9b12d | 255 | self.cap()); |
92a42be0 SL |
256 | debug_assert!(src + len <= self.cap(), |
257 | "cpy dst={} src={} len={} cap={}", | |
258 | dst, | |
259 | src, | |
260 | len, | |
c1a9b12d | 261 | self.cap()); |
b7449926 XL |
262 | ptr::copy(self.ptr().add(src), |
263 | self.ptr().add(dst), | |
92a42be0 | 264 | len); |
1a4d82fc JJ |
265 | } |
266 | ||
267 | /// Copies a contiguous block of memory len long from src to dst | |
268 | #[inline] | |
85aaf69f | 269 | unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) { |
92a42be0 SL |
270 | debug_assert!(dst + len <= self.cap(), |
271 | "cno dst={} src={} len={} cap={}", | |
272 | dst, | |
273 | src, | |
274 | len, | |
c1a9b12d | 275 | self.cap()); |
92a42be0 SL |
276 | debug_assert!(src + len <= self.cap(), |
277 | "cno dst={} src={} len={} cap={}", | |
278 | dst, | |
279 | src, | |
280 | len, | |
c1a9b12d | 281 | self.cap()); |
b7449926 XL |
282 | ptr::copy_nonoverlapping(self.ptr().add(src), |
283 | self.ptr().add(dst), | |
92a42be0 | 284 | len); |
1a4d82fc | 285 | } |
c1a9b12d | 286 | |
b039eaaf SL |
287 | /// Copies a potentially wrapping block of memory len long from src to dest. |
288 | /// (abs(dst - src) + len) must be no larger than cap() (There must be at | |
289 | /// most one continuous overlapping region between src and dest). | |
290 | unsafe fn wrap_copy(&self, dst: usize, src: usize, len: usize) { | |
92a42be0 SL |
291 | #[allow(dead_code)] |
292 | fn diff(a: usize, b: usize) -> usize { | |
32a655c1 | 293 | if a <= b { b - a } else { a - b } |
92a42be0 SL |
294 | } |
295 | debug_assert!(cmp::min(diff(dst, src), self.cap() - diff(dst, src)) + len <= self.cap(), | |
296 | "wrc dst={} src={} len={} cap={}", | |
297 | dst, | |
298 | src, | |
299 | len, | |
300 | self.cap()); | |
b039eaaf | 301 | |
92a42be0 SL |
302 | if src == dst || len == 0 { |
303 | return; | |
304 | } | |
b039eaaf SL |
305 | |
306 | let dst_after_src = self.wrap_sub(dst, src) < len; | |
307 | ||
308 | let src_pre_wrap_len = self.cap() - src; | |
309 | let dst_pre_wrap_len = self.cap() - dst; | |
310 | let src_wraps = src_pre_wrap_len < len; | |
311 | let dst_wraps = dst_pre_wrap_len < len; | |
312 | ||
313 | match (dst_after_src, src_wraps, dst_wraps) { | |
314 | (_, false, false) => { | |
315 | // src doesn't wrap, dst doesn't wrap | |
316 | // | |
317 | // S . . . | |
318 | // 1 [_ _ A A B B C C _] | |
319 | // 2 [_ _ A A A A B B _] | |
320 | // D . . . | |
321 | // | |
322 | self.copy(dst, src, len); | |
323 | } | |
324 | (false, false, true) => { | |
325 | // dst before src, src doesn't wrap, dst wraps | |
326 | // | |
327 | // S . . . | |
328 | // 1 [A A B B _ _ _ C C] | |
329 | // 2 [A A B B _ _ _ A A] | |
330 | // 3 [B B B B _ _ _ A A] | |
331 | // . . D . | |
332 | // | |
333 | self.copy(dst, src, dst_pre_wrap_len); | |
334 | self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len); | |
335 | } | |
336 | (true, false, true) => { | |
337 | // src before dst, src doesn't wrap, dst wraps | |
338 | // | |
339 | // S . . . | |
340 | // 1 [C C _ _ _ A A B B] | |
341 | // 2 [B B _ _ _ A A B B] | |
342 | // 3 [B B _ _ _ A A A A] | |
343 | // . . D . | |
344 | // | |
345 | self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len); | |
346 | self.copy(dst, src, dst_pre_wrap_len); | |
347 | } | |
348 | (false, true, false) => { | |
349 | // dst before src, src wraps, dst doesn't wrap | |
350 | // | |
351 | // . . S . | |
352 | // 1 [C C _ _ _ A A B B] | |
353 | // 2 [C C _ _ _ B B B B] | |
354 | // 3 [C C _ _ _ B B C C] | |
355 | // D . . . | |
356 | // | |
357 | self.copy(dst, src, src_pre_wrap_len); | |
358 | self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len); | |
359 | } | |
360 | (true, true, false) => { | |
361 | // src before dst, src wraps, dst doesn't wrap | |
362 | // | |
363 | // . . S . | |
364 | // 1 [A A B B _ _ _ C C] | |
365 | // 2 [A A A A _ _ _ C C] | |
366 | // 3 [C C A A _ _ _ C C] | |
367 | // D . . . | |
368 | // | |
369 | self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len); | |
370 | self.copy(dst, src, src_pre_wrap_len); | |
371 | } | |
372 | (false, true, true) => { | |
373 | // dst before src, src wraps, dst wraps | |
374 | // | |
375 | // . . . S . | |
376 | // 1 [A B C D _ E F G H] | |
377 | // 2 [A B C D _ E G H H] | |
378 | // 3 [A B C D _ E G H A] | |
379 | // 4 [B C C D _ E G H A] | |
380 | // . . D . . | |
381 | // | |
382 | debug_assert!(dst_pre_wrap_len > src_pre_wrap_len); | |
383 | let delta = dst_pre_wrap_len - src_pre_wrap_len; | |
384 | self.copy(dst, src, src_pre_wrap_len); | |
385 | self.copy(dst + src_pre_wrap_len, 0, delta); | |
386 | self.copy(0, delta, len - dst_pre_wrap_len); | |
387 | } | |
388 | (true, true, true) => { | |
389 | // src before dst, src wraps, dst wraps | |
390 | // | |
391 | // . . S . . | |
392 | // 1 [A B C D _ E F G H] | |
393 | // 2 [A A B D _ E F G H] | |
394 | // 3 [H A B D _ E F G H] | |
395 | // 4 [H A B D _ E F F G] | |
396 | // . . . D . | |
397 | // | |
398 | debug_assert!(src_pre_wrap_len > dst_pre_wrap_len); | |
399 | let delta = src_pre_wrap_len - dst_pre_wrap_len; | |
400 | self.copy(delta, 0, len - src_pre_wrap_len); | |
401 | self.copy(0, self.cap() - delta, delta); | |
402 | self.copy(dst, src, dst_pre_wrap_len); | |
403 | } | |
404 | } | |
405 | } | |
406 | ||
c1a9b12d | 407 | /// Frobs the head and tail sections around to handle the fact that we |
416331ca | 408 | /// just reallocated. Unsafe because it trusts old_capacity. |
c1a9b12d | 409 | #[inline] |
416331ca XL |
410 | unsafe fn handle_capacity_increase(&mut self, old_capacity: usize) { |
411 | let new_capacity = self.cap(); | |
c1a9b12d SL |
412 | |
413 | // Move the shortest contiguous section of the ring buffer | |
414 | // T H | |
415 | // [o o o o o o o . ] | |
416 | // T H | |
417 | // A [o o o o o o o . . . . . . . . . ] | |
418 | // H T | |
419 | // [o o . o o o o o ] | |
420 | // T H | |
421 | // B [. . . o o o o o o o . . . . . . ] | |
422 | // H T | |
423 | // [o o o o o . o o ] | |
424 | // H T | |
425 | // C [o o o o o . . . . . . . . . o o ] | |
426 | ||
92a42be0 SL |
427 | if self.tail <= self.head { |
428 | // A | |
c1a9b12d | 429 | // Nop |
416331ca | 430 | } else if self.head < old_capacity - self.tail { |
92a42be0 | 431 | // B |
416331ca XL |
432 | self.copy_nonoverlapping(old_capacity, 0, self.head); |
433 | self.head += old_capacity; | |
c1a9b12d | 434 | debug_assert!(self.head > self.tail); |
92a42be0 SL |
435 | } else { |
436 | // C | |
416331ca XL |
437 | let new_tail = new_capacity - (old_capacity - self.tail); |
438 | self.copy_nonoverlapping(new_tail, self.tail, old_capacity - self.tail); | |
c1a9b12d SL |
439 | self.tail = new_tail; |
440 | debug_assert!(self.head < self.tail); | |
441 | } | |
442 | debug_assert!(self.head < self.cap()); | |
443 | debug_assert!(self.tail < self.cap()); | |
444 | debug_assert!(self.cap().count_ones() == 1); | |
445 | } | |
1a4d82fc JJ |
446 | } |
447 | ||
85aaf69f SL |
448 | impl<T> VecDeque<T> { |
449 | /// Creates an empty `VecDeque`. | |
5bcae85e SL |
450 | /// |
451 | /// # Examples | |
452 | /// | |
453 | /// ``` | |
454 | /// use std::collections::VecDeque; | |
455 | /// | |
456 | /// let vector: VecDeque<u32> = VecDeque::new(); | |
457 | /// ``` | |
85aaf69f SL |
458 | #[stable(feature = "rust1", since = "1.0.0")] |
459 | pub fn new() -> VecDeque<T> { | |
460 | VecDeque::with_capacity(INITIAL_CAPACITY) | |
1a4d82fc JJ |
461 | } |
462 | ||
48663c56 | 463 | /// Creates an empty `VecDeque` with space for at least `capacity` elements. |
5bcae85e SL |
464 | /// |
465 | /// # Examples | |
466 | /// | |
467 | /// ``` | |
468 | /// use std::collections::VecDeque; | |
469 | /// | |
470 | /// let vector: VecDeque<u32> = VecDeque::with_capacity(10); | |
471 | /// ``` | |
85aaf69f | 472 | #[stable(feature = "rust1", since = "1.0.0")] |
48663c56 | 473 | pub fn with_capacity(capacity: usize) -> VecDeque<T> { |
1a4d82fc | 474 | // +1 since the ringbuffer always leaves one space empty |
48663c56 XL |
475 | let cap = cmp::max(capacity + 1, MINIMUM_CAPACITY + 1).next_power_of_two(); |
476 | assert!(cap > capacity, "capacity overflow"); | |
1a4d82fc | 477 | |
85aaf69f | 478 | VecDeque { |
1a4d82fc JJ |
479 | tail: 0, |
480 | head: 0, | |
c1a9b12d | 481 | buf: RawVec::with_capacity(cap), |
1a4d82fc JJ |
482 | } |
483 | } | |
484 | ||
85aaf69f | 485 | /// Retrieves an element in the `VecDeque` by index. |
1a4d82fc | 486 | /// |
5bcae85e SL |
487 | /// Element at index 0 is the front of the queue. |
488 | /// | |
1a4d82fc JJ |
489 | /// # Examples |
490 | /// | |
c34b1796 | 491 | /// ``` |
85aaf69f | 492 | /// use std::collections::VecDeque; |
1a4d82fc | 493 | /// |
85aaf69f SL |
494 | /// let mut buf = VecDeque::new(); |
495 | /// buf.push_back(3); | |
1a4d82fc JJ |
496 | /// buf.push_back(4); |
497 | /// buf.push_back(5); | |
c1a9b12d | 498 | /// assert_eq!(buf.get(1), Some(&4)); |
1a4d82fc | 499 | /// ``` |
85aaf69f | 500 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d SL |
501 | pub fn get(&self, index: usize) -> Option<&T> { |
502 | if index < self.len() { | |
503 | let idx = self.wrap_add(self.tail, index); | |
b7449926 | 504 | unsafe { Some(&*self.ptr().add(idx)) } |
1a4d82fc JJ |
505 | } else { |
506 | None | |
507 | } | |
508 | } | |
509 | ||
85aaf69f | 510 | /// Retrieves an element in the `VecDeque` mutably by index. |
1a4d82fc | 511 | /// |
5bcae85e SL |
512 | /// Element at index 0 is the front of the queue. |
513 | /// | |
1a4d82fc JJ |
514 | /// # Examples |
515 | /// | |
c34b1796 | 516 | /// ``` |
85aaf69f | 517 | /// use std::collections::VecDeque; |
1a4d82fc | 518 | /// |
85aaf69f SL |
519 | /// let mut buf = VecDeque::new(); |
520 | /// buf.push_back(3); | |
1a4d82fc JJ |
521 | /// buf.push_back(4); |
522 | /// buf.push_back(5); | |
9346a6ac AL |
523 | /// if let Some(elem) = buf.get_mut(1) { |
524 | /// *elem = 7; | |
1a4d82fc JJ |
525 | /// } |
526 | /// | |
527 | /// assert_eq!(buf[1], 7); | |
528 | /// ``` | |
85aaf69f | 529 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d SL |
530 | pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { |
531 | if index < self.len() { | |
532 | let idx = self.wrap_add(self.tail, index); | |
b7449926 | 533 | unsafe { Some(&mut *self.ptr().add(idx)) } |
1a4d82fc JJ |
534 | } else { |
535 | None | |
536 | } | |
537 | } | |
538 | ||
539 | /// Swaps elements at indices `i` and `j`. | |
540 | /// | |
541 | /// `i` and `j` may be equal. | |
542 | /// | |
5bcae85e SL |
543 | /// Element at index 0 is the front of the queue. |
544 | /// | |
ea8adc8c XL |
545 | /// # Panics |
546 | /// | |
547 | /// Panics if either index is out of bounds. | |
548 | /// | |
1a4d82fc JJ |
549 | /// # Examples |
550 | /// | |
c34b1796 | 551 | /// ``` |
85aaf69f | 552 | /// use std::collections::VecDeque; |
1a4d82fc | 553 | /// |
85aaf69f SL |
554 | /// let mut buf = VecDeque::new(); |
555 | /// buf.push_back(3); | |
1a4d82fc JJ |
556 | /// buf.push_back(4); |
557 | /// buf.push_back(5); | |
8bb4bdeb | 558 | /// assert_eq!(buf, [3, 4, 5]); |
1a4d82fc | 559 | /// buf.swap(0, 2); |
8bb4bdeb | 560 | /// assert_eq!(buf, [5, 4, 3]); |
1a4d82fc | 561 | /// ``` |
85aaf69f SL |
562 | #[stable(feature = "rust1", since = "1.0.0")] |
563 | pub fn swap(&mut self, i: usize, j: usize) { | |
1a4d82fc JJ |
564 | assert!(i < self.len()); |
565 | assert!(j < self.len()); | |
c34b1796 AL |
566 | let ri = self.wrap_add(self.tail, i); |
567 | let rj = self.wrap_add(self.tail, j); | |
1a4d82fc | 568 | unsafe { |
b7449926 XL |
569 | ptr::swap(self.ptr().add(ri), |
570 | self.ptr().add(rj)) | |
1a4d82fc JJ |
571 | } |
572 | } | |
573 | ||
85aaf69f | 574 | /// Returns the number of elements the `VecDeque` can hold without |
1a4d82fc JJ |
575 | /// reallocating. |
576 | /// | |
577 | /// # Examples | |
578 | /// | |
579 | /// ``` | |
85aaf69f | 580 | /// use std::collections::VecDeque; |
1a4d82fc | 581 | /// |
85aaf69f | 582 | /// let buf: VecDeque<i32> = VecDeque::with_capacity(10); |
1a4d82fc JJ |
583 | /// assert!(buf.capacity() >= 10); |
584 | /// ``` | |
585 | #[inline] | |
85aaf69f | 586 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
587 | pub fn capacity(&self) -> usize { |
588 | self.cap() - 1 | |
589 | } | |
1a4d82fc JJ |
590 | |
591 | /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the | |
85aaf69f | 592 | /// given `VecDeque`. Does nothing if the capacity is already sufficient. |
1a4d82fc JJ |
593 | /// |
594 | /// Note that the allocator may give the collection more space than it requests. Therefore | |
cc61c64b | 595 | /// capacity can not be relied upon to be precisely minimal. Prefer [`reserve`] if future |
1a4d82fc JJ |
596 | /// insertions are expected. |
597 | /// | |
598 | /// # Panics | |
599 | /// | |
85aaf69f | 600 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
601 | /// |
602 | /// # Examples | |
603 | /// | |
604 | /// ``` | |
85aaf69f | 605 | /// use std::collections::VecDeque; |
1a4d82fc | 606 | /// |
85aaf69f | 607 | /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); |
1a4d82fc JJ |
608 | /// buf.reserve_exact(10); |
609 | /// assert!(buf.capacity() >= 11); | |
610 | /// ``` | |
cc61c64b XL |
611 | /// |
612 | /// [`reserve`]: #method.reserve | |
85aaf69f SL |
613 | #[stable(feature = "rust1", since = "1.0.0")] |
614 | pub fn reserve_exact(&mut self, additional: usize) { | |
1a4d82fc JJ |
615 | self.reserve(additional); |
616 | } | |
617 | ||
618 | /// Reserves capacity for at least `additional` more elements to be inserted in the given | |
c1a9b12d | 619 | /// `VecDeque`. The collection may reserve more space to avoid frequent reallocations. |
1a4d82fc JJ |
620 | /// |
621 | /// # Panics | |
622 | /// | |
85aaf69f | 623 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
624 | /// |
625 | /// # Examples | |
626 | /// | |
627 | /// ``` | |
85aaf69f | 628 | /// use std::collections::VecDeque; |
1a4d82fc | 629 | /// |
85aaf69f | 630 | /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); |
1a4d82fc JJ |
631 | /// buf.reserve(10); |
632 | /// assert!(buf.capacity() >= 11); | |
633 | /// ``` | |
85aaf69f SL |
634 | #[stable(feature = "rust1", since = "1.0.0")] |
635 | pub fn reserve(&mut self, additional: usize) { | |
c1a9b12d SL |
636 | let old_cap = self.cap(); |
637 | let used_cap = self.len() + 1; | |
92a42be0 | 638 | let new_cap = used_cap.checked_add(additional) |
32a655c1 SL |
639 | .and_then(|needed_cap| needed_cap.checked_next_power_of_two()) |
640 | .expect("capacity overflow"); | |
c1a9b12d | 641 | |
3b2f2976 | 642 | if new_cap > old_cap { |
c1a9b12d | 643 | self.buf.reserve_exact(used_cap, new_cap - used_cap); |
92a42be0 | 644 | unsafe { |
416331ca | 645 | self.handle_capacity_increase(old_cap); |
92a42be0 | 646 | } |
1a4d82fc JJ |
647 | } |
648 | } | |
649 | ||
0531ce1d XL |
650 | /// Tries to reserves the minimum capacity for exactly `additional` more elements to |
651 | /// be inserted in the given `VecDeque<T>`. After calling `reserve_exact`, | |
652 | /// capacity will be greater than or equal to `self.len() + additional`. | |
653 | /// Does nothing if the capacity is already sufficient. | |
654 | /// | |
655 | /// Note that the allocator may give the collection more space than it | |
9fa01778 | 656 | /// requests. Therefore, capacity can not be relied upon to be precisely |
0531ce1d XL |
657 | /// minimal. Prefer `reserve` if future insertions are expected. |
658 | /// | |
659 | /// # Errors | |
660 | /// | |
661 | /// If the capacity overflows, or the allocator reports a failure, then an error | |
662 | /// is returned. | |
663 | /// | |
664 | /// # Examples | |
665 | /// | |
666 | /// ``` | |
667 | /// #![feature(try_reserve)] | |
e1599b0c | 668 | /// use std::collections::TryReserveError; |
0531ce1d XL |
669 | /// use std::collections::VecDeque; |
670 | /// | |
e1599b0c | 671 | /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> { |
0531ce1d XL |
672 | /// let mut output = VecDeque::new(); |
673 | /// | |
674 | /// // Pre-reserve the memory, exiting if we can't | |
675 | /// output.try_reserve_exact(data.len())?; | |
676 | /// | |
677 | /// // Now we know this can't OOM in the middle of our complex work | |
678 | /// output.extend(data.iter().map(|&val| { | |
679 | /// val * 2 + 5 // very complicated | |
680 | /// })); | |
681 | /// | |
682 | /// Ok(output) | |
683 | /// } | |
684 | /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); | |
685 | /// ``` | |
686 | #[unstable(feature = "try_reserve", reason = "new API", issue="48043")] | |
e1599b0c | 687 | pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { |
0531ce1d XL |
688 | self.try_reserve(additional) |
689 | } | |
690 | ||
691 | /// Tries to reserve capacity for at least `additional` more elements to be inserted | |
692 | /// in the given `VecDeque<T>`. The collection may reserve more space to avoid | |
693 | /// frequent reallocations. After calling `reserve`, capacity will be | |
694 | /// greater than or equal to `self.len() + additional`. Does nothing if | |
695 | /// capacity is already sufficient. | |
696 | /// | |
697 | /// # Errors | |
698 | /// | |
699 | /// If the capacity overflows, or the allocator reports a failure, then an error | |
700 | /// is returned. | |
701 | /// | |
702 | /// # Examples | |
703 | /// | |
704 | /// ``` | |
705 | /// #![feature(try_reserve)] | |
e1599b0c | 706 | /// use std::collections::TryReserveError; |
0531ce1d XL |
707 | /// use std::collections::VecDeque; |
708 | /// | |
e1599b0c | 709 | /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> { |
0531ce1d XL |
710 | /// let mut output = VecDeque::new(); |
711 | /// | |
712 | /// // Pre-reserve the memory, exiting if we can't | |
713 | /// output.try_reserve(data.len())?; | |
714 | /// | |
715 | /// // Now we know this can't OOM in the middle of our complex work | |
716 | /// output.extend(data.iter().map(|&val| { | |
717 | /// val * 2 + 5 // very complicated | |
718 | /// })); | |
719 | /// | |
720 | /// Ok(output) | |
721 | /// } | |
722 | /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); | |
723 | /// ``` | |
724 | #[unstable(feature = "try_reserve", reason = "new API", issue="48043")] | |
e1599b0c | 725 | pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { |
0531ce1d XL |
726 | let old_cap = self.cap(); |
727 | let used_cap = self.len() + 1; | |
728 | let new_cap = used_cap.checked_add(additional) | |
729 | .and_then(|needed_cap| needed_cap.checked_next_power_of_two()) | |
e1599b0c | 730 | .ok_or(TryReserveError::CapacityOverflow)?; |
0531ce1d XL |
731 | |
732 | if new_cap > old_cap { | |
733 | self.buf.try_reserve_exact(used_cap, new_cap - used_cap)?; | |
734 | unsafe { | |
416331ca | 735 | self.handle_capacity_increase(old_cap); |
0531ce1d XL |
736 | } |
737 | } | |
738 | Ok(()) | |
739 | } | |
740 | ||
c1a9b12d | 741 | /// Shrinks the capacity of the `VecDeque` as much as possible. |
1a4d82fc JJ |
742 | /// |
743 | /// It will drop down as close as possible to the length but the allocator may still inform the | |
c1a9b12d | 744 | /// `VecDeque` that there is space for a few more elements. |
1a4d82fc JJ |
745 | /// |
746 | /// # Examples | |
747 | /// | |
748 | /// ``` | |
85aaf69f | 749 | /// use std::collections::VecDeque; |
1a4d82fc | 750 | /// |
85aaf69f SL |
751 | /// let mut buf = VecDeque::with_capacity(15); |
752 | /// buf.extend(0..4); | |
1a4d82fc JJ |
753 | /// assert_eq!(buf.capacity(), 15); |
754 | /// buf.shrink_to_fit(); | |
755 | /// assert!(buf.capacity() >= 4); | |
756 | /// ``` | |
b039eaaf | 757 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
1a4d82fc | 758 | pub fn shrink_to_fit(&mut self) { |
0531ce1d XL |
759 | self.shrink_to(0); |
760 | } | |
761 | ||
762 | /// Shrinks the capacity of the `VecDeque` with a lower bound. | |
763 | /// | |
764 | /// The capacity will remain at least as large as both the length | |
765 | /// and the supplied value. | |
766 | /// | |
767 | /// Panics if the current capacity is smaller than the supplied | |
768 | /// minimum capacity. | |
769 | /// | |
770 | /// # Examples | |
771 | /// | |
772 | /// ``` | |
773 | /// #![feature(shrink_to)] | |
774 | /// use std::collections::VecDeque; | |
775 | /// | |
776 | /// let mut buf = VecDeque::with_capacity(15); | |
777 | /// buf.extend(0..4); | |
778 | /// assert_eq!(buf.capacity(), 15); | |
779 | /// buf.shrink_to(6); | |
780 | /// assert!(buf.capacity() >= 6); | |
781 | /// buf.shrink_to(0); | |
782 | /// assert!(buf.capacity() >= 4); | |
783 | /// ``` | |
a1dfa0c6 | 784 | #[unstable(feature = "shrink_to", reason = "new API", issue="56431")] |
0531ce1d XL |
785 | pub fn shrink_to(&mut self, min_capacity: usize) { |
786 | assert!(self.capacity() >= min_capacity, "Tried to shrink to a larger capacity"); | |
787 | ||
1a4d82fc | 788 | // +1 since the ringbuffer always leaves one space empty |
c1a9b12d | 789 | // len + 1 can't overflow for an existing, well-formed ringbuffer. |
0531ce1d XL |
790 | let target_cap = cmp::max( |
791 | cmp::max(min_capacity, self.len()) + 1, | |
792 | MINIMUM_CAPACITY + 1 | |
793 | ).next_power_of_two(); | |
794 | ||
c1a9b12d | 795 | if target_cap < self.cap() { |
1a4d82fc JJ |
796 | // There are three cases of interest: |
797 | // All elements are out of desired bounds | |
798 | // Elements are contiguous, and head is out of desired bounds | |
799 | // Elements are discontiguous, and tail is out of desired bounds | |
800 | // | |
801 | // At all other times, element positions are unaffected. | |
802 | // | |
803 | // Indicates that elements at the head should be moved. | |
804 | let head_outside = self.head == 0 || self.head >= target_cap; | |
805 | // Move elements from out of desired bounds (positions after target_cap) | |
806 | if self.tail >= target_cap && head_outside { | |
807 | // T H | |
808 | // [. . . . . . . . o o o o o o o . ] | |
809 | // T H | |
810 | // [o o o o o o o . ] | |
811 | unsafe { | |
812 | self.copy_nonoverlapping(0, self.tail, self.len()); | |
813 | } | |
814 | self.head = self.len(); | |
815 | self.tail = 0; | |
816 | } else if self.tail != 0 && self.tail < target_cap && head_outside { | |
817 | // T H | |
818 | // [. . . o o o o o o o . . . . . . ] | |
819 | // H T | |
820 | // [o o . o o o o o ] | |
c34b1796 | 821 | let len = self.wrap_sub(self.head, target_cap); |
1a4d82fc JJ |
822 | unsafe { |
823 | self.copy_nonoverlapping(0, target_cap, len); | |
824 | } | |
825 | self.head = len; | |
826 | debug_assert!(self.head < self.tail); | |
827 | } else if self.tail >= target_cap { | |
828 | // H T | |
829 | // [o o o o o . . . . . . . . . o o ] | |
830 | // H T | |
831 | // [o o o o o . o o ] | |
c34b1796 | 832 | debug_assert!(self.wrap_sub(self.head, 1) < target_cap); |
c1a9b12d | 833 | let len = self.cap() - self.tail; |
1a4d82fc JJ |
834 | let new_tail = target_cap - len; |
835 | unsafe { | |
836 | self.copy_nonoverlapping(new_tail, self.tail, len); | |
837 | } | |
838 | self.tail = new_tail; | |
839 | debug_assert!(self.head < self.tail); | |
840 | } | |
841 | ||
c1a9b12d SL |
842 | self.buf.shrink_to_fit(target_cap); |
843 | ||
844 | debug_assert!(self.head < self.cap()); | |
845 | debug_assert!(self.tail < self.cap()); | |
846 | debug_assert!(self.cap().count_ones() == 1); | |
1a4d82fc JJ |
847 | } |
848 | } | |
849 | ||
60c5eb7d XL |
850 | /// Shortens the `VecDeque`, keeping the first `len` elements and dropping |
851 | /// the rest. | |
1a4d82fc | 852 | /// |
c1a9b12d | 853 | /// If `len` is greater than the `VecDeque`'s current length, this has no |
1a4d82fc JJ |
854 | /// effect. |
855 | /// | |
856 | /// # Examples | |
857 | /// | |
858 | /// ``` | |
85aaf69f | 859 | /// use std::collections::VecDeque; |
1a4d82fc | 860 | /// |
85aaf69f SL |
861 | /// let mut buf = VecDeque::new(); |
862 | /// buf.push_back(5); | |
863 | /// buf.push_back(10); | |
1a4d82fc | 864 | /// buf.push_back(15); |
8bb4bdeb | 865 | /// assert_eq!(buf, [5, 10, 15]); |
1a4d82fc | 866 | /// buf.truncate(1); |
8bb4bdeb | 867 | /// assert_eq!(buf, [5]); |
1a4d82fc | 868 | /// ``` |
32a655c1 | 869 | #[stable(feature = "deque_extras", since = "1.16.0")] |
85aaf69f | 870 | pub fn truncate(&mut self, len: usize) { |
60c5eb7d XL |
871 | // Safe because: |
872 | // | |
873 | // * Any slice passed to `drop_in_place` is valid; the second case has | |
874 | // `len <= front.len()` and returning on `len > self.len()` ensures | |
875 | // `begin <= back.len()` in the first case | |
876 | // * The head of the VecDeque is moved before calling `drop_in_place`, | |
877 | // so no value is dropped twice if `drop_in_place` panics | |
878 | unsafe { | |
879 | if len > self.len() { | |
880 | return; | |
881 | } | |
882 | let num_dropped = self.len() - len; | |
883 | let (front, back) = self.as_mut_slices(); | |
884 | if len > front.len() { | |
885 | let begin = len - front.len(); | |
886 | let drop_back = back.get_unchecked_mut(begin..) as *mut _; | |
887 | self.head = self.wrap_sub(self.head, num_dropped); | |
888 | ptr::drop_in_place(drop_back); | |
889 | } else { | |
890 | let drop_back = back as *mut _; | |
891 | let drop_front = front.get_unchecked_mut(len..) as *mut _; | |
892 | self.head = self.wrap_sub(self.head, num_dropped); | |
893 | ptr::drop_in_place(drop_front); | |
894 | ptr::drop_in_place(drop_back); | |
895 | } | |
1a4d82fc JJ |
896 | } |
897 | } | |
898 | ||
899 | /// Returns a front-to-back iterator. | |
900 | /// | |
901 | /// # Examples | |
902 | /// | |
c34b1796 | 903 | /// ``` |
85aaf69f | 904 | /// use std::collections::VecDeque; |
1a4d82fc | 905 | /// |
85aaf69f SL |
906 | /// let mut buf = VecDeque::new(); |
907 | /// buf.push_back(5); | |
1a4d82fc JJ |
908 | /// buf.push_back(3); |
909 | /// buf.push_back(4); | |
910 | /// let b: &[_] = &[&5, &3, &4]; | |
c34b1796 AL |
911 | /// let c: Vec<&i32> = buf.iter().collect(); |
912 | /// assert_eq!(&c[..], b); | |
1a4d82fc | 913 | /// ``` |
85aaf69f | 914 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 915 | pub fn iter(&self) -> Iter<'_, T> { |
1a4d82fc JJ |
916 | Iter { |
917 | tail: self.tail, | |
918 | head: self.head, | |
92a42be0 | 919 | ring: unsafe { self.buffer_as_slice() }, |
1a4d82fc JJ |
920 | } |
921 | } | |
922 | ||
923 | /// Returns a front-to-back iterator that returns mutable references. | |
924 | /// | |
925 | /// # Examples | |
926 | /// | |
c34b1796 | 927 | /// ``` |
85aaf69f | 928 | /// use std::collections::VecDeque; |
1a4d82fc | 929 | /// |
85aaf69f SL |
930 | /// let mut buf = VecDeque::new(); |
931 | /// buf.push_back(5); | |
1a4d82fc JJ |
932 | /// buf.push_back(3); |
933 | /// buf.push_back(4); | |
934 | /// for num in buf.iter_mut() { | |
935 | /// *num = *num - 2; | |
936 | /// } | |
937 | /// let b: &[_] = &[&mut 3, &mut 1, &mut 2]; | |
c34b1796 | 938 | /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b); |
1a4d82fc | 939 | /// ``` |
85aaf69f | 940 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 941 | pub fn iter_mut(&mut self) -> IterMut<'_, T> { |
1a4d82fc JJ |
942 | IterMut { |
943 | tail: self.tail, | |
944 | head: self.head, | |
c34b1796 | 945 | ring: unsafe { self.buffer_as_mut_slice() }, |
1a4d82fc JJ |
946 | } |
947 | } | |
948 | ||
1a4d82fc | 949 | /// Returns a pair of slices which contain, in order, the contents of the |
85aaf69f | 950 | /// `VecDeque`. |
5bcae85e SL |
951 | /// |
952 | /// # Examples | |
953 | /// | |
954 | /// ``` | |
955 | /// use std::collections::VecDeque; | |
956 | /// | |
9e0c209e | 957 | /// let mut vector = VecDeque::new(); |
5bcae85e SL |
958 | /// |
959 | /// vector.push_back(0); | |
960 | /// vector.push_back(1); | |
961 | /// vector.push_back(2); | |
962 | /// | |
9e0c209e | 963 | /// assert_eq!(vector.as_slices(), (&[0, 1, 2][..], &[][..])); |
5bcae85e SL |
964 | /// |
965 | /// vector.push_front(10); | |
966 | /// vector.push_front(9); | |
967 | /// | |
9e0c209e | 968 | /// assert_eq!(vector.as_slices(), (&[9, 10][..], &[0, 1, 2][..])); |
5bcae85e | 969 | /// ``` |
1a4d82fc | 970 | #[inline] |
b039eaaf | 971 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
85aaf69f | 972 | pub fn as_slices(&self) -> (&[T], &[T]) { |
1a4d82fc | 973 | unsafe { |
1a4d82fc | 974 | let buf = self.buffer_as_slice(); |
c30ab7b3 | 975 | RingSlices::ring_slices(buf, self.head, self.tail) |
1a4d82fc JJ |
976 | } |
977 | } | |
978 | ||
979 | /// Returns a pair of slices which contain, in order, the contents of the | |
85aaf69f | 980 | /// `VecDeque`. |
5bcae85e SL |
981 | /// |
982 | /// # Examples | |
983 | /// | |
984 | /// ``` | |
985 | /// use std::collections::VecDeque; | |
986 | /// | |
9e0c209e | 987 | /// let mut vector = VecDeque::new(); |
5bcae85e SL |
988 | /// |
989 | /// vector.push_back(0); | |
990 | /// vector.push_back(1); | |
991 | /// | |
992 | /// vector.push_front(10); | |
993 | /// vector.push_front(9); | |
994 | /// | |
995 | /// vector.as_mut_slices().0[0] = 42; | |
996 | /// vector.as_mut_slices().1[0] = 24; | |
9e0c209e | 997 | /// assert_eq!(vector.as_slices(), (&[42, 10][..], &[24, 1][..])); |
5bcae85e | 998 | /// ``` |
1a4d82fc | 999 | #[inline] |
b039eaaf | 1000 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
85aaf69f | 1001 | pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) { |
1a4d82fc | 1002 | unsafe { |
1a4d82fc JJ |
1003 | let head = self.head; |
1004 | let tail = self.tail; | |
1005 | let buf = self.buffer_as_mut_slice(); | |
c30ab7b3 | 1006 | RingSlices::ring_slices(buf, head, tail) |
1a4d82fc JJ |
1007 | } |
1008 | } | |
1009 | ||
85aaf69f | 1010 | /// Returns the number of elements in the `VecDeque`. |
1a4d82fc JJ |
1011 | /// |
1012 | /// # Examples | |
1013 | /// | |
1014 | /// ``` | |
85aaf69f | 1015 | /// use std::collections::VecDeque; |
1a4d82fc | 1016 | /// |
85aaf69f | 1017 | /// let mut v = VecDeque::new(); |
1a4d82fc | 1018 | /// assert_eq!(v.len(), 0); |
85aaf69f | 1019 | /// v.push_back(1); |
1a4d82fc JJ |
1020 | /// assert_eq!(v.len(), 1); |
1021 | /// ``` | |
85aaf69f | 1022 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
1023 | pub fn len(&self) -> usize { |
1024 | count(self.tail, self.head, self.cap()) | |
1025 | } | |
1a4d82fc | 1026 | |
cc61c64b | 1027 | /// Returns `true` if the `VecDeque` is empty. |
1a4d82fc JJ |
1028 | /// |
1029 | /// # Examples | |
1030 | /// | |
1031 | /// ``` | |
85aaf69f | 1032 | /// use std::collections::VecDeque; |
1a4d82fc | 1033 | /// |
85aaf69f | 1034 | /// let mut v = VecDeque::new(); |
1a4d82fc | 1035 | /// assert!(v.is_empty()); |
85aaf69f | 1036 | /// v.push_front(1); |
1a4d82fc JJ |
1037 | /// assert!(!v.is_empty()); |
1038 | /// ``` | |
85aaf69f | 1039 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 1040 | pub fn is_empty(&self) -> bool { |
476ff2be | 1041 | self.tail == self.head |
92a42be0 | 1042 | } |
1a4d82fc | 1043 | |
9fa01778 | 1044 | /// Creates a draining iterator that removes the specified range in the |
9cc50fc6 | 1045 | /// `VecDeque` and yields the removed items. |
b039eaaf | 1046 | /// |
9cc50fc6 SL |
1047 | /// Note 1: The element range is removed even if the iterator is not |
1048 | /// consumed until the end. | |
1049 | /// | |
1050 | /// Note 2: It is unspecified how many elements are removed from the deque, | |
b039eaaf | 1051 | /// if the `Drain` value is not dropped, but the borrow it holds expires |
9fa01778 | 1052 | /// (e.g., due to `mem::forget`). |
b039eaaf SL |
1053 | /// |
1054 | /// # Panics | |
1055 | /// | |
1056 | /// Panics if the starting point is greater than the end point or if | |
1057 | /// the end point is greater than the length of the vector. | |
1a4d82fc JJ |
1058 | /// |
1059 | /// # Examples | |
1060 | /// | |
1061 | /// ``` | |
85aaf69f | 1062 | /// use std::collections::VecDeque; |
5bcae85e | 1063 | /// |
9cc50fc6 | 1064 | /// let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); |
8bb4bdeb XL |
1065 | /// let drained = v.drain(2..).collect::<VecDeque<_>>(); |
1066 | /// assert_eq!(drained, [3]); | |
1067 | /// assert_eq!(v, [1, 2]); | |
1a4d82fc | 1068 | /// |
9cc50fc6 SL |
1069 | /// // A full range clears all contents |
1070 | /// v.drain(..); | |
1a4d82fc JJ |
1071 | /// assert!(v.is_empty()); |
1072 | /// ``` | |
1073 | #[inline] | |
92a42be0 | 1074 | #[stable(feature = "drain", since = "1.6.0")] |
9fa01778 | 1075 | pub fn drain<R>(&mut self, range: R) -> Drain<'_, T> |
0531ce1d | 1076 | where R: RangeBounds<usize> |
92a42be0 | 1077 | { |
b039eaaf SL |
1078 | // Memory safety |
1079 | // | |
1080 | // When the Drain is first created, the source deque is shortened to | |
1081 | // make sure no uninitialized or moved-from elements are accessible at | |
1082 | // all if the Drain's destructor never gets to run. | |
1083 | // | |
1084 | // Drain will ptr::read out the values to remove. | |
1085 | // When finished, the remaining data will be copied back to cover the hole, | |
1086 | // and the head/tail values will be restored correctly. | |
1087 | // | |
1088 | let len = self.len(); | |
94b46f34 | 1089 | let start = match range.start_bound() { |
32a655c1 SL |
1090 | Included(&n) => n, |
1091 | Excluded(&n) => n + 1, | |
1092 | Unbounded => 0, | |
1093 | }; | |
94b46f34 | 1094 | let end = match range.end_bound() { |
32a655c1 SL |
1095 | Included(&n) => n + 1, |
1096 | Excluded(&n) => n, | |
1097 | Unbounded => len, | |
1098 | }; | |
b039eaaf SL |
1099 | assert!(start <= end, "drain lower bound was too large"); |
1100 | assert!(end <= len, "drain upper bound was too large"); | |
1101 | ||
1102 | // The deque's elements are parted into three segments: | |
1103 | // * self.tail -> drain_tail | |
1104 | // * drain_tail -> drain_head | |
1105 | // * drain_head -> self.head | |
1106 | // | |
1107 | // T = self.tail; H = self.head; t = drain_tail; h = drain_head | |
1108 | // | |
1109 | // We store drain_tail as self.head, and drain_head and self.head as | |
1110 | // after_tail and after_head respectively on the Drain. This also | |
1111 | // truncates the effective array such that if the Drain is leaked, we | |
1112 | // have forgotten about the potentially moved values after the start of | |
1113 | // the drain. | |
1114 | // | |
1115 | // T t h H | |
1116 | // [. . . o o x x o o . . .] | |
1117 | // | |
1118 | let drain_tail = self.wrap_add(self.tail, start); | |
1119 | let drain_head = self.wrap_add(self.tail, end); | |
1120 | let head = self.head; | |
1121 | ||
1122 | // "forget" about the values after the start of the drain until after | |
1123 | // the drain is complete and the Drain destructor is run. | |
1124 | self.head = drain_tail; | |
1125 | ||
1a4d82fc | 1126 | Drain { |
2c00a5a8 | 1127 | deque: NonNull::from(&mut *self), |
b039eaaf SL |
1128 | after_tail: drain_head, |
1129 | after_head: head, | |
1130 | iter: Iter { | |
1131 | tail: drain_tail, | |
1132 | head: drain_head, | |
0731742a XL |
1133 | // Crucially, we only create shared references from `self` here and read from |
1134 | // it. We do not write to `self` nor reborrow to a mutable reference. | |
1135 | // Hence the raw pointer we created above, for `deque`, remains valid. | |
1136 | ring: unsafe { self.buffer_as_slice() }, | |
b039eaaf | 1137 | }, |
1a4d82fc JJ |
1138 | } |
1139 | } | |
1140 | ||
2c00a5a8 | 1141 | /// Clears the `VecDeque`, removing all values. |
1a4d82fc JJ |
1142 | /// |
1143 | /// # Examples | |
1144 | /// | |
1145 | /// ``` | |
85aaf69f | 1146 | /// use std::collections::VecDeque; |
1a4d82fc | 1147 | /// |
85aaf69f SL |
1148 | /// let mut v = VecDeque::new(); |
1149 | /// v.push_back(1); | |
1a4d82fc JJ |
1150 | /// v.clear(); |
1151 | /// assert!(v.is_empty()); | |
1152 | /// ``` | |
85aaf69f | 1153 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1154 | #[inline] |
1155 | pub fn clear(&mut self) { | |
60c5eb7d | 1156 | self.truncate(0); |
1a4d82fc JJ |
1157 | } |
1158 | ||
a7813a04 XL |
1159 | /// Returns `true` if the `VecDeque` contains an element equal to the |
1160 | /// given value. | |
5bcae85e SL |
1161 | /// |
1162 | /// # Examples | |
1163 | /// | |
1164 | /// ``` | |
1165 | /// use std::collections::VecDeque; | |
1166 | /// | |
1167 | /// let mut vector: VecDeque<u32> = VecDeque::new(); | |
1168 | /// | |
1169 | /// vector.push_back(0); | |
1170 | /// vector.push_back(1); | |
1171 | /// | |
1172 | /// assert_eq!(vector.contains(&1), true); | |
1173 | /// assert_eq!(vector.contains(&10), false); | |
1174 | /// ``` | |
1175 | #[stable(feature = "vec_deque_contains", since = "1.12.0")] | |
a7813a04 XL |
1176 | pub fn contains(&self, x: &T) -> bool |
1177 | where T: PartialEq<T> | |
1178 | { | |
1179 | let (a, b) = self.as_slices(); | |
1180 | a.contains(x) || b.contains(x) | |
1181 | } | |
1182 | ||
cc61c64b | 1183 | /// Provides a reference to the front element, or `None` if the `VecDeque` is |
1a4d82fc JJ |
1184 | /// empty. |
1185 | /// | |
1186 | /// # Examples | |
1187 | /// | |
1188 | /// ``` | |
85aaf69f | 1189 | /// use std::collections::VecDeque; |
1a4d82fc | 1190 | /// |
85aaf69f | 1191 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
1192 | /// assert_eq!(d.front(), None); |
1193 | /// | |
85aaf69f SL |
1194 | /// d.push_back(1); |
1195 | /// d.push_back(2); | |
1196 | /// assert_eq!(d.front(), Some(&1)); | |
1a4d82fc | 1197 | /// ``` |
85aaf69f | 1198 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1199 | pub fn front(&self) -> Option<&T> { |
92a42be0 SL |
1200 | if !self.is_empty() { |
1201 | Some(&self[0]) | |
1202 | } else { | |
1203 | None | |
1204 | } | |
1a4d82fc JJ |
1205 | } |
1206 | ||
1207 | /// Provides a mutable reference to the front element, or `None` if the | |
cc61c64b | 1208 | /// `VecDeque` is empty. |
1a4d82fc JJ |
1209 | /// |
1210 | /// # Examples | |
1211 | /// | |
1212 | /// ``` | |
85aaf69f | 1213 | /// use std::collections::VecDeque; |
1a4d82fc | 1214 | /// |
85aaf69f | 1215 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
1216 | /// assert_eq!(d.front_mut(), None); |
1217 | /// | |
85aaf69f SL |
1218 | /// d.push_back(1); |
1219 | /// d.push_back(2); | |
1a4d82fc | 1220 | /// match d.front_mut() { |
85aaf69f | 1221 | /// Some(x) => *x = 9, |
1a4d82fc JJ |
1222 | /// None => (), |
1223 | /// } | |
85aaf69f | 1224 | /// assert_eq!(d.front(), Some(&9)); |
1a4d82fc | 1225 | /// ``` |
85aaf69f | 1226 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1227 | pub fn front_mut(&mut self) -> Option<&mut T> { |
92a42be0 SL |
1228 | if !self.is_empty() { |
1229 | Some(&mut self[0]) | |
1230 | } else { | |
1231 | None | |
1232 | } | |
1a4d82fc JJ |
1233 | } |
1234 | ||
cc61c64b | 1235 | /// Provides a reference to the back element, or `None` if the `VecDeque` is |
1a4d82fc JJ |
1236 | /// empty. |
1237 | /// | |
1238 | /// # Examples | |
1239 | /// | |
1240 | /// ``` | |
85aaf69f | 1241 | /// use std::collections::VecDeque; |
1a4d82fc | 1242 | /// |
85aaf69f | 1243 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
1244 | /// assert_eq!(d.back(), None); |
1245 | /// | |
85aaf69f SL |
1246 | /// d.push_back(1); |
1247 | /// d.push_back(2); | |
1248 | /// assert_eq!(d.back(), Some(&2)); | |
1a4d82fc | 1249 | /// ``` |
85aaf69f | 1250 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1251 | pub fn back(&self) -> Option<&T> { |
92a42be0 SL |
1252 | if !self.is_empty() { |
1253 | Some(&self[self.len() - 1]) | |
1254 | } else { | |
1255 | None | |
1256 | } | |
1a4d82fc JJ |
1257 | } |
1258 | ||
1259 | /// Provides a mutable reference to the back element, or `None` if the | |
cc61c64b | 1260 | /// `VecDeque` is empty. |
1a4d82fc JJ |
1261 | /// |
1262 | /// # Examples | |
1263 | /// | |
1264 | /// ``` | |
85aaf69f | 1265 | /// use std::collections::VecDeque; |
1a4d82fc | 1266 | /// |
85aaf69f | 1267 | /// let mut d = VecDeque::new(); |
1a4d82fc JJ |
1268 | /// assert_eq!(d.back(), None); |
1269 | /// | |
85aaf69f SL |
1270 | /// d.push_back(1); |
1271 | /// d.push_back(2); | |
1a4d82fc | 1272 | /// match d.back_mut() { |
85aaf69f | 1273 | /// Some(x) => *x = 9, |
1a4d82fc JJ |
1274 | /// None => (), |
1275 | /// } | |
85aaf69f | 1276 | /// assert_eq!(d.back(), Some(&9)); |
1a4d82fc | 1277 | /// ``` |
85aaf69f | 1278 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1279 | pub fn back_mut(&mut self) -> Option<&mut T> { |
1280 | let len = self.len(); | |
92a42be0 SL |
1281 | if !self.is_empty() { |
1282 | Some(&mut self[len - 1]) | |
1283 | } else { | |
1284 | None | |
1285 | } | |
1a4d82fc JJ |
1286 | } |
1287 | ||
cc61c64b | 1288 | /// Removes the first element and returns it, or `None` if the `VecDeque` is |
1a4d82fc JJ |
1289 | /// empty. |
1290 | /// | |
1291 | /// # Examples | |
1292 | /// | |
1293 | /// ``` | |
85aaf69f | 1294 | /// use std::collections::VecDeque; |
1a4d82fc | 1295 | /// |
85aaf69f SL |
1296 | /// let mut d = VecDeque::new(); |
1297 | /// d.push_back(1); | |
1298 | /// d.push_back(2); | |
1a4d82fc | 1299 | /// |
85aaf69f SL |
1300 | /// assert_eq!(d.pop_front(), Some(1)); |
1301 | /// assert_eq!(d.pop_front(), Some(2)); | |
1a4d82fc JJ |
1302 | /// assert_eq!(d.pop_front(), None); |
1303 | /// ``` | |
85aaf69f | 1304 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1305 | pub fn pop_front(&mut self) -> Option<T> { |
1306 | if self.is_empty() { | |
1307 | None | |
1308 | } else { | |
1309 | let tail = self.tail; | |
c34b1796 | 1310 | self.tail = self.wrap_add(self.tail, 1); |
1a4d82fc JJ |
1311 | unsafe { Some(self.buffer_read(tail)) } |
1312 | } | |
1313 | } | |
1314 | ||
e1599b0c XL |
1315 | /// Removes the last element from the `VecDeque` and returns it, or `None` if |
1316 | /// it is empty. | |
1317 | /// | |
1318 | /// # Examples | |
1319 | /// | |
1320 | /// ``` | |
1321 | /// use std::collections::VecDeque; | |
1322 | /// | |
1323 | /// let mut buf = VecDeque::new(); | |
1324 | /// assert_eq!(buf.pop_back(), None); | |
1325 | /// buf.push_back(1); | |
1326 | /// buf.push_back(3); | |
1327 | /// assert_eq!(buf.pop_back(), Some(3)); | |
1328 | /// ``` | |
1329 | #[stable(feature = "rust1", since = "1.0.0")] | |
1330 | pub fn pop_back(&mut self) -> Option<T> { | |
1331 | if self.is_empty() { | |
1332 | None | |
1333 | } else { | |
1334 | self.head = self.wrap_sub(self.head, 1); | |
1335 | let head = self.head; | |
1336 | unsafe { Some(self.buffer_read(head)) } | |
1337 | } | |
1338 | } | |
1339 | ||
cc61c64b | 1340 | /// Prepends an element to the `VecDeque`. |
1a4d82fc JJ |
1341 | /// |
1342 | /// # Examples | |
1343 | /// | |
1344 | /// ``` | |
85aaf69f | 1345 | /// use std::collections::VecDeque; |
1a4d82fc | 1346 | /// |
85aaf69f SL |
1347 | /// let mut d = VecDeque::new(); |
1348 | /// d.push_front(1); | |
1349 | /// d.push_front(2); | |
1350 | /// assert_eq!(d.front(), Some(&2)); | |
1a4d82fc | 1351 | /// ``` |
85aaf69f | 1352 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d | 1353 | pub fn push_front(&mut self, value: T) { |
8bb4bdeb | 1354 | self.grow_if_necessary(); |
1a4d82fc | 1355 | |
c34b1796 | 1356 | self.tail = self.wrap_sub(self.tail, 1); |
1a4d82fc | 1357 | let tail = self.tail; |
92a42be0 SL |
1358 | unsafe { |
1359 | self.buffer_write(tail, value); | |
1360 | } | |
1a4d82fc JJ |
1361 | } |
1362 | ||
cc61c64b | 1363 | /// Appends an element to the back of the `VecDeque`. |
1a4d82fc JJ |
1364 | /// |
1365 | /// # Examples | |
1366 | /// | |
c34b1796 | 1367 | /// ``` |
85aaf69f | 1368 | /// use std::collections::VecDeque; |
1a4d82fc | 1369 | /// |
85aaf69f SL |
1370 | /// let mut buf = VecDeque::new(); |
1371 | /// buf.push_back(1); | |
1a4d82fc JJ |
1372 | /// buf.push_back(3); |
1373 | /// assert_eq!(3, *buf.back().unwrap()); | |
1374 | /// ``` | |
85aaf69f | 1375 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d | 1376 | pub fn push_back(&mut self, value: T) { |
8bb4bdeb | 1377 | self.grow_if_necessary(); |
1a4d82fc JJ |
1378 | |
1379 | let head = self.head; | |
c34b1796 | 1380 | self.head = self.wrap_add(self.head, 1); |
c1a9b12d | 1381 | unsafe { self.buffer_write(head, value) } |
1a4d82fc JJ |
1382 | } |
1383 | ||
1a4d82fc JJ |
1384 | #[inline] |
1385 | fn is_contiguous(&self) -> bool { | |
1386 | self.tail <= self.head | |
1387 | } | |
1388 | ||
e1599b0c XL |
1389 | /// Removes an element from anywhere in the `VecDeque` and returns it, |
1390 | /// replacing it with the first element. | |
1a4d82fc JJ |
1391 | /// |
1392 | /// This does not preserve ordering, but is O(1). | |
1393 | /// | |
1394 | /// Returns `None` if `index` is out of bounds. | |
1395 | /// | |
5bcae85e SL |
1396 | /// Element at index 0 is the front of the queue. |
1397 | /// | |
1a4d82fc JJ |
1398 | /// # Examples |
1399 | /// | |
1400 | /// ``` | |
85aaf69f | 1401 | /// use std::collections::VecDeque; |
1a4d82fc | 1402 | /// |
85aaf69f | 1403 | /// let mut buf = VecDeque::new(); |
e1599b0c | 1404 | /// assert_eq!(buf.swap_remove_front(0), None); |
c1a9b12d SL |
1405 | /// buf.push_back(1); |
1406 | /// buf.push_back(2); | |
1407 | /// buf.push_back(3); | |
8bb4bdeb | 1408 | /// assert_eq!(buf, [1, 2, 3]); |
c1a9b12d | 1409 | /// |
e1599b0c XL |
1410 | /// assert_eq!(buf.swap_remove_front(2), Some(3)); |
1411 | /// assert_eq!(buf, [2, 1]); | |
1a4d82fc | 1412 | /// ``` |
b039eaaf | 1413 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
e1599b0c | 1414 | pub fn swap_remove_front(&mut self, index: usize) -> Option<T> { |
1a4d82fc | 1415 | let length = self.len(); |
e1599b0c XL |
1416 | if length > 0 && index < length && index != 0 { |
1417 | self.swap(index, 0); | |
1a4d82fc JJ |
1418 | } else if index >= length { |
1419 | return None; | |
1420 | } | |
e1599b0c | 1421 | self.pop_front() |
1a4d82fc JJ |
1422 | } |
1423 | ||
e1599b0c XL |
1424 | /// Removes an element from anywhere in the `VecDeque` and returns it, replacing it with the |
1425 | /// last element. | |
1a4d82fc JJ |
1426 | /// |
1427 | /// This does not preserve ordering, but is O(1). | |
1428 | /// | |
1429 | /// Returns `None` if `index` is out of bounds. | |
1430 | /// | |
5bcae85e SL |
1431 | /// Element at index 0 is the front of the queue. |
1432 | /// | |
1a4d82fc JJ |
1433 | /// # Examples |
1434 | /// | |
1435 | /// ``` | |
85aaf69f | 1436 | /// use std::collections::VecDeque; |
1a4d82fc | 1437 | /// |
85aaf69f | 1438 | /// let mut buf = VecDeque::new(); |
e1599b0c | 1439 | /// assert_eq!(buf.swap_remove_back(0), None); |
c1a9b12d SL |
1440 | /// buf.push_back(1); |
1441 | /// buf.push_back(2); | |
1442 | /// buf.push_back(3); | |
8bb4bdeb | 1443 | /// assert_eq!(buf, [1, 2, 3]); |
c1a9b12d | 1444 | /// |
e1599b0c XL |
1445 | /// assert_eq!(buf.swap_remove_back(0), Some(1)); |
1446 | /// assert_eq!(buf, [3, 2]); | |
1a4d82fc | 1447 | /// ``` |
b039eaaf | 1448 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
e1599b0c | 1449 | pub fn swap_remove_back(&mut self, index: usize) -> Option<T> { |
1a4d82fc | 1450 | let length = self.len(); |
e1599b0c XL |
1451 | if length > 0 && index < length - 1 { |
1452 | self.swap(index, length - 1); | |
1a4d82fc JJ |
1453 | } else if index >= length { |
1454 | return None; | |
1455 | } | |
e1599b0c | 1456 | self.pop_back() |
1a4d82fc JJ |
1457 | } |
1458 | ||
32a655c1 SL |
1459 | /// Inserts an element at `index` within the `VecDeque`, shifting all elements with indices |
1460 | /// greater than or equal to `index` towards the back. | |
1a4d82fc | 1461 | /// |
5bcae85e SL |
1462 | /// Element at index 0 is the front of the queue. |
1463 | /// | |
1a4d82fc JJ |
1464 | /// # Panics |
1465 | /// | |
c1a9b12d | 1466 | /// Panics if `index` is greater than `VecDeque`'s length |
1a4d82fc JJ |
1467 | /// |
1468 | /// # Examples | |
32a655c1 | 1469 | /// |
c34b1796 | 1470 | /// ``` |
85aaf69f | 1471 | /// use std::collections::VecDeque; |
1a4d82fc | 1472 | /// |
32a655c1 SL |
1473 | /// let mut vec_deque = VecDeque::new(); |
1474 | /// vec_deque.push_back('a'); | |
1475 | /// vec_deque.push_back('b'); | |
1476 | /// vec_deque.push_back('c'); | |
8bb4bdeb | 1477 | /// assert_eq!(vec_deque, &['a', 'b', 'c']); |
32a655c1 SL |
1478 | /// |
1479 | /// vec_deque.insert(1, 'd'); | |
8bb4bdeb | 1480 | /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c']); |
1a4d82fc | 1481 | /// ``` |
b039eaaf | 1482 | #[stable(feature = "deque_extras_15", since = "1.5.0")] |
c1a9b12d SL |
1483 | pub fn insert(&mut self, index: usize, value: T) { |
1484 | assert!(index <= self.len(), "index out of bounds"); | |
8bb4bdeb | 1485 | self.grow_if_necessary(); |
1a4d82fc JJ |
1486 | |
1487 | // Move the least number of elements in the ring buffer and insert | |
1488 | // the given object | |
1489 | // | |
1490 | // At most len/2 - 1 elements will be moved. O(min(n, n-i)) | |
1491 | // | |
1492 | // There are three main cases: | |
1493 | // Elements are contiguous | |
1494 | // - special case when tail is 0 | |
1495 | // Elements are discontiguous and the insert is in the tail section | |
1496 | // Elements are discontiguous and the insert is in the head section | |
1497 | // | |
1498 | // For each of those there are two more cases: | |
1499 | // Insert is closer to tail | |
1500 | // Insert is closer to head | |
1501 | // | |
1502 | // Key: H - self.head | |
1503 | // T - self.tail | |
1504 | // o - Valid element | |
1505 | // I - Insertion element | |
1506 | // A - The element that should be after the insertion point | |
1507 | // M - Indicates element was moved | |
1508 | ||
c1a9b12d | 1509 | let idx = self.wrap_add(self.tail, index); |
1a4d82fc | 1510 | |
c1a9b12d SL |
1511 | let distance_to_tail = index; |
1512 | let distance_to_head = self.len() - index; | |
1a4d82fc JJ |
1513 | |
1514 | let contiguous = self.is_contiguous(); | |
1515 | ||
32a655c1 | 1516 | match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) { |
c1a9b12d | 1517 | (true, true, _) if index == 0 => { |
1a4d82fc JJ |
1518 | // push_front |
1519 | // | |
1520 | // T | |
1521 | // I H | |
1522 | // [A o o o o o o . . . . . . . . .] | |
1523 | // | |
1524 | // H T | |
1525 | // [A o o o o o o o . . . . . I] | |
1526 | // | |
1527 | ||
c34b1796 | 1528 | self.tail = self.wrap_sub(self.tail, 1); |
92a42be0 SL |
1529 | } |
1530 | (true, true, _) => { | |
1531 | unsafe { | |
1532 | // contiguous, insert closer to tail: | |
1533 | // | |
1534 | // T I H | |
1535 | // [. . . o o A o o o o . . . . . .] | |
1536 | // | |
1537 | // T H | |
1538 | // [. . o o I A o o o o . . . . . .] | |
1539 | // M M | |
1540 | // | |
1541 | // contiguous, insert closer to tail and tail is 0: | |
1542 | // | |
1543 | // | |
1544 | // T I H | |
1545 | // [o o A o o o o . . . . . . . . .] | |
1546 | // | |
1547 | // H T | |
1548 | // [o I A o o o o o . . . . . . . o] | |
1549 | // M M | |
1550 | ||
1551 | let new_tail = self.wrap_sub(self.tail, 1); | |
1552 | ||
1553 | self.copy(new_tail, self.tail, 1); | |
1554 | // Already moved the tail, so we only copy `index - 1` elements. | |
1555 | self.copy(self.tail, self.tail + 1, index - 1); | |
1556 | ||
1557 | self.tail = new_tail; | |
1558 | } | |
1559 | } | |
1560 | (true, false, _) => { | |
1561 | unsafe { | |
1562 | // contiguous, insert closer to head: | |
1563 | // | |
1564 | // T I H | |
1565 | // [. . . o o o o A o o . . . . . .] | |
1566 | // | |
1567 | // T H | |
1568 | // [. . . o o o o I A o o . . . . .] | |
1569 | // M M M | |
1570 | ||
1571 | self.copy(idx + 1, idx, self.head - idx); | |
1572 | self.head = self.wrap_add(self.head, 1); | |
1573 | } | |
1574 | } | |
1575 | (false, true, true) => { | |
1576 | unsafe { | |
1577 | // discontiguous, insert closer to tail, tail section: | |
1578 | // | |
1579 | // H T I | |
1580 | // [o o o o o o . . . . . o o A o o] | |
1581 | // | |
1582 | // H T | |
1583 | // [o o o o o o . . . . o o I A o o] | |
1584 | // M M | |
1585 | ||
1586 | self.copy(self.tail - 1, self.tail, index); | |
1587 | self.tail -= 1; | |
1588 | } | |
1589 | } | |
1590 | (false, false, true) => { | |
1591 | unsafe { | |
1592 | // discontiguous, insert closer to head, tail section: | |
1593 | // | |
1594 | // H T I | |
1595 | // [o o . . . . . . . o o o o o A o] | |
1596 | // | |
1597 | // H T | |
1598 | // [o o o . . . . . . o o o o o I A] | |
1599 | // M M M M | |
1a4d82fc | 1600 | |
92a42be0 SL |
1601 | // copy elements up to new head |
1602 | self.copy(1, 0, self.head); | |
1a4d82fc | 1603 | |
92a42be0 SL |
1604 | // copy last element into empty spot at bottom of buffer |
1605 | self.copy(0, self.cap() - 1, 1); | |
1a4d82fc | 1606 | |
92a42be0 SL |
1607 | // move elements from idx to end forward not including ^ element |
1608 | self.copy(idx + 1, idx, self.cap() - 1 - idx); | |
1a4d82fc | 1609 | |
92a42be0 SL |
1610 | self.head += 1; |
1611 | } | |
1612 | } | |
1613 | (false, true, false) if idx == 0 => { | |
1614 | unsafe { | |
1615 | // discontiguous, insert is closer to tail, head section, | |
1616 | // and is at index zero in the internal buffer: | |
1617 | // | |
1618 | // I H T | |
1619 | // [A o o o o o o o o o . . . o o o] | |
1620 | // | |
1621 | // H T | |
1622 | // [A o o o o o o o o o . . o o o I] | |
1623 | // M M M | |
1624 | ||
1625 | // copy elements up to new tail | |
1626 | self.copy(self.tail - 1, self.tail, self.cap() - self.tail); | |
1627 | ||
1628 | // copy last element into empty spot at bottom of buffer | |
1629 | self.copy(self.cap() - 1, 0, 1); | |
1a4d82fc | 1630 | |
92a42be0 SL |
1631 | self.tail -= 1; |
1632 | } | |
1633 | } | |
1634 | (false, true, false) => { | |
1635 | unsafe { | |
1636 | // discontiguous, insert closer to tail, head section: | |
1637 | // | |
1638 | // I H T | |
1639 | // [o o o A o o o o o o . . . o o o] | |
1640 | // | |
1641 | // H T | |
1642 | // [o o I A o o o o o o . . o o o o] | |
1643 | // M M M M M M | |
1644 | ||
1645 | // copy elements up to new tail | |
1646 | self.copy(self.tail - 1, self.tail, self.cap() - self.tail); | |
1647 | ||
1648 | // copy last element into empty spot at bottom of buffer | |
1649 | self.copy(self.cap() - 1, 0, 1); | |
1a4d82fc | 1650 | |
92a42be0 SL |
1651 | // move elements from idx-1 to end forward not including ^ element |
1652 | self.copy(0, 1, idx - 1); | |
1a4d82fc | 1653 | |
92a42be0 SL |
1654 | self.tail -= 1; |
1655 | } | |
1656 | } | |
1657 | (false, false, false) => { | |
1658 | unsafe { | |
1659 | // discontiguous, insert closer to head, head section: | |
1660 | // | |
1661 | // I H T | |
1662 | // [o o o o A o o . . . . . . o o o] | |
1663 | // | |
1664 | // H T | |
1665 | // [o o o o I A o o . . . . . o o o] | |
1666 | // M M M | |
1667 | ||
1668 | self.copy(idx + 1, idx, self.head - idx); | |
1669 | self.head += 1; | |
1670 | } | |
1a4d82fc JJ |
1671 | } |
1672 | } | |
1673 | ||
1674 | // tail might've been changed so we need to recalculate | |
c1a9b12d | 1675 | let new_idx = self.wrap_add(self.tail, index); |
1a4d82fc | 1676 | unsafe { |
c1a9b12d | 1677 | self.buffer_write(new_idx, value); |
1a4d82fc JJ |
1678 | } |
1679 | } | |
1680 | ||
c1a9b12d | 1681 | /// Removes and returns the element at `index` from the `VecDeque`. |
1a4d82fc JJ |
1682 | /// Whichever end is closer to the removal point will be moved to make |
1683 | /// room, and all the affected elements will be moved to new positions. | |
c1a9b12d | 1684 | /// Returns `None` if `index` is out of bounds. |
1a4d82fc | 1685 | /// |
5bcae85e SL |
1686 | /// Element at index 0 is the front of the queue. |
1687 | /// | |
1a4d82fc | 1688 | /// # Examples |
5bcae85e | 1689 | /// |
c34b1796 | 1690 | /// ``` |
85aaf69f | 1691 | /// use std::collections::VecDeque; |
1a4d82fc | 1692 | /// |
85aaf69f | 1693 | /// let mut buf = VecDeque::new(); |
c1a9b12d SL |
1694 | /// buf.push_back(1); |
1695 | /// buf.push_back(2); | |
1696 | /// buf.push_back(3); | |
8bb4bdeb | 1697 | /// assert_eq!(buf, [1, 2, 3]); |
c1a9b12d SL |
1698 | /// |
1699 | /// assert_eq!(buf.remove(1), Some(2)); | |
8bb4bdeb | 1700 | /// assert_eq!(buf, [1, 3]); |
1a4d82fc | 1701 | /// ``` |
85aaf69f | 1702 | #[stable(feature = "rust1", since = "1.0.0")] |
c1a9b12d SL |
1703 | pub fn remove(&mut self, index: usize) -> Option<T> { |
1704 | if self.is_empty() || self.len() <= index { | |
1a4d82fc JJ |
1705 | return None; |
1706 | } | |
1707 | ||
1708 | // There are three main cases: | |
1709 | // Elements are contiguous | |
1710 | // Elements are discontiguous and the removal is in the tail section | |
1711 | // Elements are discontiguous and the removal is in the head section | |
1712 | // - special case when elements are technically contiguous, | |
1713 | // but self.head = 0 | |
1714 | // | |
1715 | // For each of those there are two more cases: | |
1716 | // Insert is closer to tail | |
1717 | // Insert is closer to head | |
1718 | // | |
1719 | // Key: H - self.head | |
1720 | // T - self.tail | |
1721 | // o - Valid element | |
1722 | // x - Element marked for removal | |
1723 | // R - Indicates element that is being removed | |
1724 | // M - Indicates element was moved | |
1725 | ||
c1a9b12d | 1726 | let idx = self.wrap_add(self.tail, index); |
1a4d82fc | 1727 | |
92a42be0 | 1728 | let elem = unsafe { Some(self.buffer_read(idx)) }; |
1a4d82fc | 1729 | |
c1a9b12d SL |
1730 | let distance_to_tail = index; |
1731 | let distance_to_head = self.len() - index; | |
1a4d82fc JJ |
1732 | |
1733 | let contiguous = self.is_contiguous(); | |
1734 | ||
32a655c1 | 1735 | match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) { |
92a42be0 SL |
1736 | (true, true, _) => { |
1737 | unsafe { | |
1738 | // contiguous, remove closer to tail: | |
1739 | // | |
1740 | // T R H | |
1741 | // [. . . o o x o o o o . . . . . .] | |
1742 | // | |
1743 | // T H | |
1744 | // [. . . . o o o o o o . . . . . .] | |
1745 | // M M | |
1746 | ||
1747 | self.copy(self.tail + 1, self.tail, index); | |
1748 | self.tail += 1; | |
1749 | } | |
1750 | } | |
1751 | (true, false, _) => { | |
1752 | unsafe { | |
1753 | // contiguous, remove closer to head: | |
1754 | // | |
1755 | // T R H | |
1756 | // [. . . o o o o x o o . . . . . .] | |
1757 | // | |
1758 | // T H | |
1759 | // [. . . o o o o o o . . . . . . .] | |
1760 | // M M | |
1761 | ||
1762 | self.copy(idx, idx + 1, self.head - idx - 1); | |
1763 | self.head -= 1; | |
1764 | } | |
1765 | } | |
1766 | (false, true, true) => { | |
1767 | unsafe { | |
1768 | // discontiguous, remove closer to tail, tail section: | |
1769 | // | |
1770 | // H T R | |
1771 | // [o o o o o o . . . . . o o x o o] | |
1772 | // | |
1773 | // H T | |
1774 | // [o o o o o o . . . . . . o o o o] | |
1775 | // M M | |
1776 | ||
1777 | self.copy(self.tail + 1, self.tail, index); | |
1778 | self.tail = self.wrap_add(self.tail, 1); | |
1a4d82fc | 1779 | } |
92a42be0 SL |
1780 | } |
1781 | (false, false, false) => { | |
1782 | unsafe { | |
1783 | // discontiguous, remove closer to head, head section: | |
1784 | // | |
1785 | // R H T | |
1786 | // [o o o o x o o . . . . . . o o o] | |
1787 | // | |
1788 | // H T | |
1789 | // [o o o o o o . . . . . . . o o o] | |
1790 | // M M | |
1791 | ||
1792 | self.copy(idx, idx + 1, self.head - idx - 1); | |
1793 | self.head -= 1; | |
1794 | } | |
1795 | } | |
1796 | (false, false, true) => { | |
1797 | unsafe { | |
1798 | // discontiguous, remove closer to head, tail section: | |
1799 | // | |
1800 | // H T R | |
1801 | // [o o o . . . . . . o o o o o x o] | |
1802 | // | |
1803 | // H T | |
1804 | // [o o . . . . . . . o o o o o o o] | |
1805 | // M M M M | |
1806 | // | |
1807 | // or quasi-discontiguous, remove next to head, tail section: | |
1808 | // | |
1809 | // H T R | |
1810 | // [. . . . . . . . . o o o o o x o] | |
1811 | // | |
1812 | // T H | |
1813 | // [. . . . . . . . . o o o o o o .] | |
1814 | // M | |
1815 | ||
1816 | // draw in elements in the tail section | |
1817 | self.copy(idx, idx + 1, self.cap() - idx - 1); | |
1818 | ||
1819 | // Prevents underflow. | |
1820 | if self.head != 0 { | |
1821 | // copy first element into empty spot | |
1822 | self.copy(self.cap() - 1, 0, 1); | |
1823 | ||
1824 | // move elements in the head section backwards | |
1825 | self.copy(0, 1, self.head - 1); | |
1826 | } | |
1a4d82fc | 1827 | |
92a42be0 SL |
1828 | self.head = self.wrap_sub(self.head, 1); |
1829 | } | |
1830 | } | |
1831 | (false, true, false) => { | |
1832 | unsafe { | |
1833 | // discontiguous, remove closer to tail, head section: | |
1834 | // | |
1835 | // R H T | |
1836 | // [o o x o o o o o o o . . . o o o] | |
1837 | // | |
1838 | // H T | |
1839 | // [o o o o o o o o o o . . . . o o] | |
1840 | // M M M M M | |
1a4d82fc | 1841 | |
92a42be0 SL |
1842 | // draw in elements up to idx |
1843 | self.copy(1, 0, idx); | |
1a4d82fc | 1844 | |
92a42be0 SL |
1845 | // copy last element into empty spot |
1846 | self.copy(0, self.cap() - 1, 1); | |
1a4d82fc | 1847 | |
92a42be0 SL |
1848 | // move elements from tail to end forward, excluding the last one |
1849 | self.copy(self.tail + 1, self.tail, self.cap() - self.tail - 1); | |
1a4d82fc | 1850 | |
92a42be0 SL |
1851 | self.tail = self.wrap_add(self.tail, 1); |
1852 | } | |
1a4d82fc JJ |
1853 | } |
1854 | } | |
1855 | ||
e74abb32 | 1856 | elem |
1a4d82fc | 1857 | } |
85aaf69f | 1858 | |
2c00a5a8 | 1859 | /// Splits the `VecDeque` into two at the given index. |
85aaf69f | 1860 | /// |
2c00a5a8 XL |
1861 | /// Returns a newly allocated `VecDeque`. `self` contains elements `[0, at)`, |
1862 | /// and the returned `VecDeque` contains elements `[at, len)`. | |
85aaf69f SL |
1863 | /// |
1864 | /// Note that the capacity of `self` does not change. | |
1865 | /// | |
5bcae85e SL |
1866 | /// Element at index 0 is the front of the queue. |
1867 | /// | |
85aaf69f SL |
1868 | /// # Panics |
1869 | /// | |
2c00a5a8 | 1870 | /// Panics if `at > len`. |
85aaf69f SL |
1871 | /// |
1872 | /// # Examples | |
1873 | /// | |
1874 | /// ``` | |
1875 | /// use std::collections::VecDeque; | |
1876 | /// | |
1877 | /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect(); | |
1878 | /// let buf2 = buf.split_off(1); | |
8bb4bdeb XL |
1879 | /// assert_eq!(buf, [1]); |
1880 | /// assert_eq!(buf2, [2, 3]); | |
85aaf69f SL |
1881 | /// ``` |
1882 | #[inline] | |
e9174d1e | 1883 | #[stable(feature = "split_off", since = "1.4.0")] |
85aaf69f SL |
1884 | pub fn split_off(&mut self, at: usize) -> Self { |
1885 | let len = self.len(); | |
1886 | assert!(at <= len, "`at` out of bounds"); | |
1887 | ||
1888 | let other_len = len - at; | |
1889 | let mut other = VecDeque::with_capacity(other_len); | |
1890 | ||
1891 | unsafe { | |
1892 | let (first_half, second_half) = self.as_slices(); | |
1893 | ||
1894 | let first_len = first_half.len(); | |
1895 | let second_len = second_half.len(); | |
1896 | if at < first_len { | |
1897 | // `at` lies in the first half. | |
1898 | let amount_in_first = first_len - at; | |
1899 | ||
b7449926 | 1900 | ptr::copy_nonoverlapping(first_half.as_ptr().add(at), |
c1a9b12d | 1901 | other.ptr(), |
c34b1796 | 1902 | amount_in_first); |
85aaf69f SL |
1903 | |
1904 | // just take all of the second half. | |
c34b1796 | 1905 | ptr::copy_nonoverlapping(second_half.as_ptr(), |
b7449926 | 1906 | other.ptr().add(amount_in_first), |
c34b1796 | 1907 | second_len); |
85aaf69f SL |
1908 | } else { |
1909 | // `at` lies in the second half, need to factor in the elements we skipped | |
1910 | // in the first half. | |
1911 | let offset = at - first_len; | |
1912 | let amount_in_second = second_len - offset; | |
b7449926 | 1913 | ptr::copy_nonoverlapping(second_half.as_ptr().add(offset), |
c1a9b12d | 1914 | other.ptr(), |
c34b1796 | 1915 | amount_in_second); |
85aaf69f SL |
1916 | } |
1917 | } | |
1918 | ||
1919 | // Cleanup where the ends of the buffers are | |
c34b1796 | 1920 | self.head = self.wrap_sub(self.head, other_len); |
85aaf69f SL |
1921 | other.head = other.wrap_index(other_len); |
1922 | ||
1923 | other | |
1924 | } | |
1925 | ||
e1599b0c | 1926 | /// Moves all the elements of `other` into `self`, leaving `other` empty. |
85aaf69f SL |
1927 | /// |
1928 | /// # Panics | |
1929 | /// | |
1930 | /// Panics if the new number of elements in self overflows a `usize`. | |
1931 | /// | |
1932 | /// # Examples | |
1933 | /// | |
1934 | /// ``` | |
1935 | /// use std::collections::VecDeque; | |
1936 | /// | |
8bb4bdeb XL |
1937 | /// let mut buf: VecDeque<_> = vec![1, 2].into_iter().collect(); |
1938 | /// let mut buf2: VecDeque<_> = vec![3, 4].into_iter().collect(); | |
85aaf69f | 1939 | /// buf.append(&mut buf2); |
8bb4bdeb XL |
1940 | /// assert_eq!(buf, [1, 2, 3, 4]); |
1941 | /// assert_eq!(buf2, []); | |
85aaf69f SL |
1942 | /// ``` |
1943 | #[inline] | |
e9174d1e | 1944 | #[stable(feature = "append", since = "1.4.0")] |
85aaf69f | 1945 | pub fn append(&mut self, other: &mut Self) { |
4462d4a0 XL |
1946 | // naive impl |
1947 | self.extend(other.drain(..)); | |
85aaf69f | 1948 | } |
d9579d0f AL |
1949 | |
1950 | /// Retains only the elements specified by the predicate. | |
1951 | /// | |
1952 | /// In other words, remove all elements `e` such that `f(&e)` returns false. | |
48663c56 XL |
1953 | /// This method operates in place, visiting each element exactly once in the |
1954 | /// original order, and preserves the order of the retained elements. | |
d9579d0f AL |
1955 | /// |
1956 | /// # Examples | |
1957 | /// | |
1958 | /// ``` | |
d9579d0f AL |
1959 | /// use std::collections::VecDeque; |
1960 | /// | |
1961 | /// let mut buf = VecDeque::new(); | |
1962 | /// buf.extend(1..5); | |
e1599b0c | 1963 | /// buf.retain(|&x| x % 2 == 0); |
8bb4bdeb | 1964 | /// assert_eq!(buf, [2, 4]); |
d9579d0f | 1965 | /// ``` |
48663c56 XL |
1966 | /// |
1967 | /// The exact order may be useful for tracking external state, like an index. | |
1968 | /// | |
1969 | /// ``` | |
1970 | /// use std::collections::VecDeque; | |
1971 | /// | |
1972 | /// let mut buf = VecDeque::new(); | |
1973 | /// buf.extend(1..6); | |
1974 | /// | |
1975 | /// let keep = [false, true, true, false, true]; | |
1976 | /// let mut i = 0; | |
1977 | /// buf.retain(|_| (keep[i], i += 1).0); | |
1978 | /// assert_eq!(buf, [2, 3, 5]); | |
1979 | /// ``` | |
e9174d1e | 1980 | #[stable(feature = "vec_deque_retain", since = "1.4.0")] |
92a42be0 SL |
1981 | pub fn retain<F>(&mut self, mut f: F) |
1982 | where F: FnMut(&T) -> bool | |
1983 | { | |
d9579d0f AL |
1984 | let len = self.len(); |
1985 | let mut del = 0; | |
1986 | for i in 0..len { | |
1987 | if !f(&self[i]) { | |
1988 | del += 1; | |
1989 | } else if del > 0 { | |
92a42be0 | 1990 | self.swap(i - del, i); |
d9579d0f AL |
1991 | } |
1992 | } | |
1993 | if del > 0 { | |
1994 | self.truncate(len - del); | |
1995 | } | |
1996 | } | |
8bb4bdeb XL |
1997 | |
1998 | // This may panic or abort | |
1999 | #[inline] | |
2000 | fn grow_if_necessary(&mut self) { | |
2001 | if self.is_full() { | |
2002 | let old_cap = self.cap(); | |
2003 | self.buf.double(); | |
2004 | unsafe { | |
416331ca | 2005 | self.handle_capacity_increase(old_cap); |
8bb4bdeb XL |
2006 | } |
2007 | debug_assert!(!self.is_full()); | |
2008 | } | |
2009 | } | |
a1dfa0c6 XL |
2010 | |
2011 | /// Modifies the `VecDeque` in-place so that `len()` is equal to `new_len`, | |
2012 | /// either by removing excess elements from the back or by appending | |
2013 | /// elements generated by calling `generator` to the back. | |
2014 | /// | |
2015 | /// # Examples | |
2016 | /// | |
2017 | /// ``` | |
a1dfa0c6 XL |
2018 | /// use std::collections::VecDeque; |
2019 | /// | |
2020 | /// let mut buf = VecDeque::new(); | |
2021 | /// buf.push_back(5); | |
2022 | /// buf.push_back(10); | |
2023 | /// buf.push_back(15); | |
2024 | /// assert_eq!(buf, [5, 10, 15]); | |
2025 | /// | |
2026 | /// buf.resize_with(5, Default::default); | |
2027 | /// assert_eq!(buf, [5, 10, 15, 0, 0]); | |
2028 | /// | |
2029 | /// buf.resize_with(2, || unreachable!()); | |
2030 | /// assert_eq!(buf, [5, 10]); | |
2031 | /// | |
2032 | /// let mut state = 100; | |
2033 | /// buf.resize_with(5, || { state += 1; state }); | |
2034 | /// assert_eq!(buf, [5, 10, 101, 102, 103]); | |
2035 | /// ``` | |
0731742a | 2036 | #[stable(feature = "vec_resize_with", since = "1.33.0")] |
a1dfa0c6 XL |
2037 | pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut()->T) { |
2038 | let len = self.len(); | |
2039 | ||
2040 | if new_len > len { | |
2041 | self.extend(repeat_with(generator).take(new_len - len)) | |
2042 | } else { | |
2043 | self.truncate(new_len); | |
2044 | } | |
2045 | } | |
0731742a XL |
2046 | |
2047 | /// Rotates the double-ended queue `mid` places to the left. | |
2048 | /// | |
2049 | /// Equivalently, | |
2050 | /// - Rotates item `mid` into the first position. | |
2051 | /// - Pops the first `mid` items and pushes them to the end. | |
2052 | /// - Rotates `len() - mid` places to the right. | |
2053 | /// | |
2054 | /// # Panics | |
2055 | /// | |
9fa01778 | 2056 | /// If `mid` is greater than `len()`. Note that `mid == len()` |
0731742a XL |
2057 | /// does _not_ panic and is a no-op rotation. |
2058 | /// | |
2059 | /// # Complexity | |
2060 | /// | |
2061 | /// Takes `O(min(mid, len() - mid))` time and no extra space. | |
2062 | /// | |
2063 | /// # Examples | |
2064 | /// | |
2065 | /// ``` | |
0731742a XL |
2066 | /// use std::collections::VecDeque; |
2067 | /// | |
2068 | /// let mut buf: VecDeque<_> = (0..10).collect(); | |
2069 | /// | |
2070 | /// buf.rotate_left(3); | |
2071 | /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]); | |
2072 | /// | |
2073 | /// for i in 1..10 { | |
2074 | /// assert_eq!(i * 3 % 10, buf[0]); | |
2075 | /// buf.rotate_left(3); | |
2076 | /// } | |
2077 | /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); | |
2078 | /// ``` | |
48663c56 | 2079 | #[stable(feature = "vecdeque_rotate", since = "1.36.0")] |
0731742a XL |
2080 | pub fn rotate_left(&mut self, mid: usize) { |
2081 | assert!(mid <= self.len()); | |
2082 | let k = self.len() - mid; | |
2083 | if mid <= k { | |
2084 | unsafe { self.rotate_left_inner(mid) } | |
2085 | } else { | |
2086 | unsafe { self.rotate_right_inner(k) } | |
2087 | } | |
2088 | } | |
2089 | ||
2090 | /// Rotates the double-ended queue `k` places to the right. | |
2091 | /// | |
2092 | /// Equivalently, | |
2093 | /// - Rotates the first item into position `k`. | |
2094 | /// - Pops the last `k` items and pushes them to the front. | |
2095 | /// - Rotates `len() - k` places to the left. | |
2096 | /// | |
2097 | /// # Panics | |
2098 | /// | |
9fa01778 | 2099 | /// If `k` is greater than `len()`. Note that `k == len()` |
0731742a XL |
2100 | /// does _not_ panic and is a no-op rotation. |
2101 | /// | |
2102 | /// # Complexity | |
2103 | /// | |
2104 | /// Takes `O(min(k, len() - k))` time and no extra space. | |
2105 | /// | |
2106 | /// # Examples | |
2107 | /// | |
2108 | /// ``` | |
0731742a XL |
2109 | /// use std::collections::VecDeque; |
2110 | /// | |
2111 | /// let mut buf: VecDeque<_> = (0..10).collect(); | |
2112 | /// | |
2113 | /// buf.rotate_right(3); | |
2114 | /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]); | |
2115 | /// | |
2116 | /// for i in 1..10 { | |
2117 | /// assert_eq!(0, buf[i * 3 % 10]); | |
2118 | /// buf.rotate_right(3); | |
2119 | /// } | |
2120 | /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); | |
2121 | /// ``` | |
48663c56 | 2122 | #[stable(feature = "vecdeque_rotate", since = "1.36.0")] |
0731742a XL |
2123 | pub fn rotate_right(&mut self, k: usize) { |
2124 | assert!(k <= self.len()); | |
2125 | let mid = self.len() - k; | |
2126 | if k <= mid { | |
2127 | unsafe { self.rotate_right_inner(k) } | |
2128 | } else { | |
2129 | unsafe { self.rotate_left_inner(mid) } | |
2130 | } | |
2131 | } | |
2132 | ||
2133 | // Safety: the following two methods require that the rotation amount | |
2134 | // be less than half the length of the deque. | |
2135 | // | |
2136 | // `wrap_copy` requres that `min(x, cap() - x) + copy_len <= cap()`, | |
2137 | // but than `min` is never more than half the capacity, regardless of x, | |
2138 | // so it's sound to call here because we're calling with something | |
2139 | // less than half the length, which is never above half the capacity. | |
2140 | ||
2141 | unsafe fn rotate_left_inner(&mut self, mid: usize) { | |
2142 | debug_assert!(mid * 2 <= self.len()); | |
2143 | self.wrap_copy(self.head, self.tail, mid); | |
2144 | self.head = self.wrap_add(self.head, mid); | |
2145 | self.tail = self.wrap_add(self.tail, mid); | |
2146 | } | |
2147 | ||
2148 | unsafe fn rotate_right_inner(&mut self, k: usize) { | |
2149 | debug_assert!(k * 2 <= self.len()); | |
2150 | self.head = self.wrap_sub(self.head, k); | |
2151 | self.tail = self.wrap_sub(self.tail, k); | |
2152 | self.wrap_copy(self.tail, self.head, k); | |
2153 | } | |
1a4d82fc JJ |
2154 | } |
2155 | ||
85aaf69f | 2156 | impl<T: Clone> VecDeque<T> { |
c1a9b12d | 2157 | /// Modifies the `VecDeque` in-place so that `len()` is equal to new_len, |
2c00a5a8 XL |
2158 | /// either by removing excess elements from the back or by appending clones of `value` |
2159 | /// to the back. | |
1a4d82fc JJ |
2160 | /// |
2161 | /// # Examples | |
2162 | /// | |
2163 | /// ``` | |
85aaf69f | 2164 | /// use std::collections::VecDeque; |
1a4d82fc | 2165 | /// |
85aaf69f SL |
2166 | /// let mut buf = VecDeque::new(); |
2167 | /// buf.push_back(5); | |
2168 | /// buf.push_back(10); | |
1a4d82fc | 2169 | /// buf.push_back(15); |
8bb4bdeb XL |
2170 | /// assert_eq!(buf, [5, 10, 15]); |
2171 | /// | |
1a4d82fc | 2172 | /// buf.resize(2, 0); |
8bb4bdeb XL |
2173 | /// assert_eq!(buf, [5, 10]); |
2174 | /// | |
2175 | /// buf.resize(5, 20); | |
2176 | /// assert_eq!(buf, [5, 10, 20, 20, 20]); | |
1a4d82fc | 2177 | /// ``` |
32a655c1 | 2178 | #[stable(feature = "deque_extras", since = "1.16.0")] |
85aaf69f | 2179 | pub fn resize(&mut self, new_len: usize, value: T) { |
a1dfa0c6 | 2180 | self.resize_with(new_len, || value.clone()); |
1a4d82fc JJ |
2181 | } |
2182 | } | |
2183 | ||
2184 | /// Returns the index in the underlying buffer for a given logical element index. | |
2185 | #[inline] | |
85aaf69f | 2186 | fn wrap_index(index: usize, size: usize) -> usize { |
1a4d82fc | 2187 | // size is always a power of 2 |
e9174d1e | 2188 | debug_assert!(size.is_power_of_two()); |
1a4d82fc JJ |
2189 | index & (size - 1) |
2190 | } | |
2191 | ||
cc61c64b | 2192 | /// Returns the two slices that cover the `VecDeque`'s valid range |
32a655c1 | 2193 | trait RingSlices: Sized { |
c30ab7b3 SL |
2194 | fn slice(self, from: usize, to: usize) -> Self; |
2195 | fn split_at(self, i: usize) -> (Self, Self); | |
2196 | ||
2197 | fn ring_slices(buf: Self, head: usize, tail: usize) -> (Self, Self) { | |
2198 | let contiguous = tail <= head; | |
2199 | if contiguous { | |
2200 | let (empty, buf) = buf.split_at(0); | |
2201 | (buf.slice(tail, head), empty) | |
2202 | } else { | |
2203 | let (mid, right) = buf.split_at(tail); | |
2204 | let (left, _) = mid.split_at(head); | |
2205 | (right, left) | |
2206 | } | |
2207 | } | |
2208 | } | |
2209 | ||
9fa01778 | 2210 | impl<T> RingSlices for &[T] { |
c30ab7b3 SL |
2211 | fn slice(self, from: usize, to: usize) -> Self { |
2212 | &self[from..to] | |
2213 | } | |
2214 | fn split_at(self, i: usize) -> (Self, Self) { | |
2215 | (*self).split_at(i) | |
2216 | } | |
2217 | } | |
2218 | ||
9fa01778 | 2219 | impl<T> RingSlices for &mut [T] { |
c30ab7b3 SL |
2220 | fn slice(self, from: usize, to: usize) -> Self { |
2221 | &mut self[from..to] | |
2222 | } | |
2223 | fn split_at(self, i: usize) -> (Self, Self) { | |
2224 | (*self).split_at_mut(i) | |
2225 | } | |
2226 | } | |
2227 | ||
1a4d82fc JJ |
2228 | /// Calculate the number of elements left to be read in the buffer |
2229 | #[inline] | |
85aaf69f | 2230 | fn count(tail: usize, head: usize, size: usize) -> usize { |
1a4d82fc | 2231 | // size is always a power of 2 |
c34b1796 | 2232 | (head.wrapping_sub(tail)) & (size - 1) |
1a4d82fc JJ |
2233 | } |
2234 | ||
cc61c64b XL |
2235 | /// An iterator over the elements of a `VecDeque`. |
2236 | /// | |
2237 | /// This `struct` is created by the [`iter`] method on [`VecDeque`]. See its | |
2238 | /// documentation for more. | |
2239 | /// | |
2240 | /// [`iter`]: struct.VecDeque.html#method.iter | |
2241 | /// [`VecDeque`]: struct.VecDeque.html | |
85aaf69f | 2242 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 2243 | pub struct Iter<'a, T: 'a> { |
1a4d82fc | 2244 | ring: &'a [T], |
85aaf69f | 2245 | tail: usize, |
92a42be0 | 2246 | head: usize, |
1a4d82fc JJ |
2247 | } |
2248 | ||
8bb4bdeb | 2249 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
2250 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
2251 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
b7449926 | 2252 | let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); |
8bb4bdeb | 2253 | f.debug_tuple("Iter") |
b7449926 XL |
2254 | .field(&front) |
2255 | .field(&back) | |
2256 | .finish() | |
8bb4bdeb XL |
2257 | } |
2258 | } | |
2259 | ||
ea8adc8c | 2260 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
92a42be0 | 2261 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 XL |
2262 | impl<T> Clone for Iter<'_, T> { |
2263 | fn clone(&self) -> Self { | |
1a4d82fc JJ |
2264 | Iter { |
2265 | ring: self.ring, | |
2266 | tail: self.tail, | |
92a42be0 | 2267 | head: self.head, |
1a4d82fc JJ |
2268 | } |
2269 | } | |
2270 | } | |
2271 | ||
85aaf69f | 2272 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
2273 | impl<'a, T> Iterator for Iter<'a, T> { |
2274 | type Item = &'a T; | |
2275 | ||
2276 | #[inline] | |
2277 | fn next(&mut self) -> Option<&'a T> { | |
2278 | if self.tail == self.head { | |
2279 | return None; | |
2280 | } | |
2281 | let tail = self.tail; | |
c34b1796 | 2282 | self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); |
1a4d82fc JJ |
2283 | unsafe { Some(self.ring.get_unchecked(tail)) } |
2284 | } | |
2285 | ||
2286 | #[inline] | |
85aaf69f | 2287 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
2288 | let len = count(self.tail, self.head, self.ring.len()); |
2289 | (len, Some(len)) | |
2290 | } | |
c30ab7b3 SL |
2291 | |
2292 | fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc | |
32a655c1 | 2293 | where F: FnMut(Acc, Self::Item) -> Acc |
c30ab7b3 SL |
2294 | { |
2295 | let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); | |
2296 | accum = front.iter().fold(accum, &mut f); | |
2297 | back.iter().fold(accum, &mut f) | |
2298 | } | |
9fa01778 XL |
2299 | |
2300 | fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
2301 | where | |
2302 | Self: Sized, | |
2303 | F: FnMut(B, Self::Item) -> R, | |
2304 | R: Try<Ok = B>, | |
2305 | { | |
2306 | let (mut iter, final_res); | |
2307 | if self.tail <= self.head { | |
2308 | // single slice self.ring[self.tail..self.head] | |
2309 | iter = self.ring[self.tail..self.head].iter(); | |
2310 | final_res = iter.try_fold(init, &mut f); | |
2311 | } else { | |
2312 | // two slices: self.ring[self.tail..], self.ring[..self.head] | |
2313 | let (front, back) = self.ring.split_at(self.tail); | |
2314 | let mut back_iter = back.iter(); | |
2315 | let res = back_iter.try_fold(init, &mut f); | |
2316 | let len = self.ring.len(); | |
2317 | self.tail = (self.ring.len() - back_iter.len()) & (len - 1); | |
2318 | iter = front[..self.head].iter(); | |
2319 | final_res = iter.try_fold(res?, &mut f); | |
2320 | } | |
2321 | self.tail = self.head - iter.len(); | |
2322 | final_res | |
2323 | } | |
416331ca | 2324 | |
e74abb32 XL |
2325 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
2326 | if n >= count(self.tail, self.head, self.ring.len()) { | |
2327 | self.tail = self.head; | |
2328 | None | |
2329 | } else { | |
2330 | self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len()); | |
2331 | self.next() | |
2332 | } | |
2333 | } | |
2334 | ||
416331ca XL |
2335 | #[inline] |
2336 | fn last(mut self) -> Option<&'a T> { | |
2337 | self.next_back() | |
2338 | } | |
1a4d82fc JJ |
2339 | } |
2340 | ||
85aaf69f | 2341 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
2342 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
2343 | #[inline] | |
2344 | fn next_back(&mut self) -> Option<&'a T> { | |
2345 | if self.tail == self.head { | |
2346 | return None; | |
2347 | } | |
c34b1796 | 2348 | self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); |
1a4d82fc JJ |
2349 | unsafe { Some(self.ring.get_unchecked(self.head)) } |
2350 | } | |
ea8adc8c XL |
2351 | |
2352 | fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc | |
2353 | where F: FnMut(Acc, Self::Item) -> Acc | |
2354 | { | |
2355 | let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); | |
2356 | accum = back.iter().rfold(accum, &mut f); | |
2357 | front.iter().rfold(accum, &mut f) | |
2358 | } | |
9fa01778 XL |
2359 | |
2360 | fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
2361 | where | |
2362 | Self: Sized, | |
2363 | F: FnMut(B, Self::Item) -> R, | |
2364 | R: Try<Ok = B>, | |
2365 | { | |
2366 | let (mut iter, final_res); | |
2367 | if self.tail <= self.head { | |
2368 | // single slice self.ring[self.tail..self.head] | |
2369 | iter = self.ring[self.tail..self.head].iter(); | |
2370 | final_res = iter.try_rfold(init, &mut f); | |
2371 | } else { | |
2372 | // two slices: self.ring[self.tail..], self.ring[..self.head] | |
2373 | let (front, back) = self.ring.split_at(self.tail); | |
2374 | let mut front_iter = front[..self.head].iter(); | |
2375 | let res = front_iter.try_rfold(init, &mut f); | |
2376 | self.head = front_iter.len(); | |
2377 | iter = back.iter(); | |
2378 | final_res = iter.try_rfold(res?, &mut f); | |
2379 | } | |
2380 | self.head = self.tail + iter.len(); | |
2381 | final_res | |
2382 | } | |
1a4d82fc JJ |
2383 | } |
2384 | ||
85aaf69f | 2385 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 2386 | impl<T> ExactSizeIterator for Iter<'_, T> { |
476ff2be SL |
2387 | fn is_empty(&self) -> bool { |
2388 | self.head == self.tail | |
2389 | } | |
2390 | } | |
1a4d82fc | 2391 | |
0531ce1d | 2392 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 2393 | impl<T> FusedIterator for Iter<'_, T> {} |
9e0c209e SL |
2394 | |
2395 | ||
cc61c64b XL |
2396 | /// A mutable iterator over the elements of a `VecDeque`. |
2397 | /// | |
2398 | /// This `struct` is created by the [`iter_mut`] method on [`VecDeque`]. See its | |
2399 | /// documentation for more. | |
2400 | /// | |
2401 | /// [`iter_mut`]: struct.VecDeque.html#method.iter_mut | |
2402 | /// [`VecDeque`]: struct.VecDeque.html | |
85aaf69f | 2403 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 2404 | pub struct IterMut<'a, T: 'a> { |
c34b1796 | 2405 | ring: &'a mut [T], |
85aaf69f SL |
2406 | tail: usize, |
2407 | head: usize, | |
1a4d82fc JJ |
2408 | } |
2409 | ||
8bb4bdeb | 2410 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
2411 | impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { |
2412 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
b7449926 | 2413 | let (front, back) = RingSlices::ring_slices(&*self.ring, self.head, self.tail); |
8bb4bdeb | 2414 | f.debug_tuple("IterMut") |
b7449926 XL |
2415 | .field(&front) |
2416 | .field(&back) | |
2417 | .finish() | |
8bb4bdeb XL |
2418 | } |
2419 | } | |
2420 | ||
85aaf69f | 2421 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
2422 | impl<'a, T> Iterator for IterMut<'a, T> { |
2423 | type Item = &'a mut T; | |
2424 | ||
2425 | #[inline] | |
2426 | fn next(&mut self) -> Option<&'a mut T> { | |
2427 | if self.tail == self.head { | |
2428 | return None; | |
2429 | } | |
2430 | let tail = self.tail; | |
c34b1796 | 2431 | self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); |
1a4d82fc JJ |
2432 | |
2433 | unsafe { | |
c34b1796 AL |
2434 | let elem = self.ring.get_unchecked_mut(tail); |
2435 | Some(&mut *(elem as *mut _)) | |
1a4d82fc JJ |
2436 | } |
2437 | } | |
2438 | ||
2439 | #[inline] | |
85aaf69f | 2440 | fn size_hint(&self) -> (usize, Option<usize>) { |
c34b1796 | 2441 | let len = count(self.tail, self.head, self.ring.len()); |
1a4d82fc JJ |
2442 | (len, Some(len)) |
2443 | } | |
c30ab7b3 SL |
2444 | |
2445 | fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc | |
32a655c1 | 2446 | where F: FnMut(Acc, Self::Item) -> Acc |
c30ab7b3 SL |
2447 | { |
2448 | let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); | |
2449 | accum = front.iter_mut().fold(accum, &mut f); | |
2450 | back.iter_mut().fold(accum, &mut f) | |
2451 | } | |
416331ca | 2452 | |
e74abb32 XL |
2453 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
2454 | if n >= count(self.tail, self.head, self.ring.len()) { | |
2455 | self.tail = self.head; | |
2456 | None | |
2457 | } else { | |
2458 | self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len()); | |
2459 | self.next() | |
2460 | } | |
2461 | } | |
2462 | ||
416331ca XL |
2463 | #[inline] |
2464 | fn last(mut self) -> Option<&'a mut T> { | |
2465 | self.next_back() | |
2466 | } | |
1a4d82fc JJ |
2467 | } |
2468 | ||
85aaf69f | 2469 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
2470 | impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { |
2471 | #[inline] | |
2472 | fn next_back(&mut self) -> Option<&'a mut T> { | |
2473 | if self.tail == self.head { | |
2474 | return None; | |
2475 | } | |
c34b1796 | 2476 | self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); |
1a4d82fc JJ |
2477 | |
2478 | unsafe { | |
c34b1796 AL |
2479 | let elem = self.ring.get_unchecked_mut(self.head); |
2480 | Some(&mut *(elem as *mut _)) | |
1a4d82fc JJ |
2481 | } |
2482 | } | |
ea8adc8c XL |
2483 | |
2484 | fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc | |
2485 | where F: FnMut(Acc, Self::Item) -> Acc | |
2486 | { | |
2487 | let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail); | |
2488 | accum = back.iter_mut().rfold(accum, &mut f); | |
2489 | front.iter_mut().rfold(accum, &mut f) | |
2490 | } | |
1a4d82fc JJ |
2491 | } |
2492 | ||
85aaf69f | 2493 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 2494 | impl<T> ExactSizeIterator for IterMut<'_, T> { |
476ff2be SL |
2495 | fn is_empty(&self) -> bool { |
2496 | self.head == self.tail | |
2497 | } | |
2498 | } | |
1a4d82fc | 2499 | |
0531ce1d | 2500 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 2501 | impl<T> FusedIterator for IterMut<'_, T> {} |
9e0c209e | 2502 | |
cc61c64b XL |
2503 | /// An owning iterator over the elements of a `VecDeque`. |
2504 | /// | |
2505 | /// This `struct` is created by the [`into_iter`] method on [`VecDeque`][`VecDeque`] | |
2506 | /// (provided by the `IntoIterator` trait). See its documentation for more. | |
2507 | /// | |
2508 | /// [`into_iter`]: struct.VecDeque.html#method.into_iter | |
2509 | /// [`VecDeque`]: struct.VecDeque.html | |
c34b1796 | 2510 | #[derive(Clone)] |
85aaf69f | 2511 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 2512 | pub struct IntoIter<T> { |
85aaf69f | 2513 | inner: VecDeque<T>, |
1a4d82fc JJ |
2514 | } |
2515 | ||
8bb4bdeb XL |
2516 | #[stable(feature = "collection_debug", since = "1.17.0")] |
2517 | impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { | |
9fa01778 | 2518 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
8bb4bdeb | 2519 | f.debug_tuple("IntoIter") |
cc61c64b | 2520 | .field(&self.inner) |
8bb4bdeb XL |
2521 | .finish() |
2522 | } | |
2523 | } | |
2524 | ||
85aaf69f | 2525 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
2526 | impl<T> Iterator for IntoIter<T> { |
2527 | type Item = T; | |
2528 | ||
2529 | #[inline] | |
2530 | fn next(&mut self) -> Option<T> { | |
2531 | self.inner.pop_front() | |
2532 | } | |
2533 | ||
2534 | #[inline] | |
85aaf69f | 2535 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
2536 | let len = self.inner.len(); |
2537 | (len, Some(len)) | |
2538 | } | |
2539 | } | |
2540 | ||
85aaf69f | 2541 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
2542 | impl<T> DoubleEndedIterator for IntoIter<T> { |
2543 | #[inline] | |
2544 | fn next_back(&mut self) -> Option<T> { | |
2545 | self.inner.pop_back() | |
2546 | } | |
2547 | } | |
2548 | ||
85aaf69f | 2549 | #[stable(feature = "rust1", since = "1.0.0")] |
476ff2be SL |
2550 | impl<T> ExactSizeIterator for IntoIter<T> { |
2551 | fn is_empty(&self) -> bool { | |
2552 | self.inner.is_empty() | |
2553 | } | |
2554 | } | |
1a4d82fc | 2555 | |
0531ce1d | 2556 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
2557 | impl<T> FusedIterator for IntoIter<T> {} |
2558 | ||
cc61c64b XL |
2559 | /// A draining iterator over the elements of a `VecDeque`. |
2560 | /// | |
2561 | /// This `struct` is created by the [`drain`] method on [`VecDeque`]. See its | |
2562 | /// documentation for more. | |
2563 | /// | |
2564 | /// [`drain`]: struct.VecDeque.html#method.drain | |
2565 | /// [`VecDeque`]: struct.VecDeque.html | |
92a42be0 | 2566 | #[stable(feature = "drain", since = "1.6.0")] |
1a4d82fc | 2567 | pub struct Drain<'a, T: 'a> { |
b039eaaf SL |
2568 | after_tail: usize, |
2569 | after_head: usize, | |
2570 | iter: Iter<'a, T>, | |
2c00a5a8 | 2571 | deque: NonNull<VecDeque<T>>, |
1a4d82fc JJ |
2572 | } |
2573 | ||
8bb4bdeb | 2574 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
2575 | impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> { |
2576 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
8bb4bdeb | 2577 | f.debug_tuple("Drain") |
cc61c64b XL |
2578 | .field(&self.after_tail) |
2579 | .field(&self.after_head) | |
2580 | .field(&self.iter) | |
8bb4bdeb XL |
2581 | .finish() |
2582 | } | |
2583 | } | |
2584 | ||
92a42be0 | 2585 | #[stable(feature = "drain", since = "1.6.0")] |
9fa01778 | 2586 | unsafe impl<T: Sync> Sync for Drain<'_, T> {} |
92a42be0 | 2587 | #[stable(feature = "drain", since = "1.6.0")] |
9fa01778 | 2588 | unsafe impl<T: Send> Send for Drain<'_, T> {} |
b039eaaf | 2589 | |
c30ab7b3 | 2590 | #[stable(feature = "drain", since = "1.6.0")] |
9fa01778 | 2591 | impl<T> Drop for Drain<'_, T> { |
1a4d82fc | 2592 | fn drop(&mut self) { |
83c7162d | 2593 | self.for_each(drop); |
b039eaaf | 2594 | |
7cac9316 | 2595 | let source_deque = unsafe { self.deque.as_mut() }; |
b039eaaf SL |
2596 | |
2597 | // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head | |
2598 | // | |
2599 | // T t h H | |
2600 | // [. . . o o x x o o . . .] | |
2601 | // | |
2602 | let orig_tail = source_deque.tail; | |
2603 | let drain_tail = source_deque.head; | |
2604 | let drain_head = self.after_tail; | |
2605 | let orig_head = self.after_head; | |
2606 | ||
2607 | let tail_len = count(orig_tail, drain_tail, source_deque.cap()); | |
2608 | let head_len = count(drain_head, orig_head, source_deque.cap()); | |
2609 | ||
2610 | // Restore the original head value | |
2611 | source_deque.head = orig_head; | |
2612 | ||
2613 | match (tail_len, head_len) { | |
2614 | (0, 0) => { | |
2615 | source_deque.head = 0; | |
2616 | source_deque.tail = 0; | |
2617 | } | |
2618 | (0, _) => { | |
2619 | source_deque.tail = drain_head; | |
2620 | } | |
2621 | (_, 0) => { | |
2622 | source_deque.head = drain_tail; | |
2623 | } | |
32a655c1 SL |
2624 | _ => unsafe { |
2625 | if tail_len <= head_len { | |
2626 | source_deque.tail = source_deque.wrap_sub(drain_head, tail_len); | |
2627 | source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len); | |
2628 | } else { | |
2629 | source_deque.head = source_deque.wrap_add(drain_tail, head_len); | |
2630 | source_deque.wrap_copy(drain_tail, drain_head, head_len); | |
b039eaaf | 2631 | } |
32a655c1 | 2632 | }, |
b039eaaf | 2633 | } |
1a4d82fc JJ |
2634 | } |
2635 | } | |
2636 | ||
c30ab7b3 | 2637 | #[stable(feature = "drain", since = "1.6.0")] |
9fa01778 | 2638 | impl<T> Iterator for Drain<'_, T> { |
1a4d82fc JJ |
2639 | type Item = T; |
2640 | ||
2641 | #[inline] | |
2642 | fn next(&mut self) -> Option<T> { | |
92a42be0 | 2643 | self.iter.next().map(|elt| unsafe { ptr::read(elt) }) |
1a4d82fc JJ |
2644 | } |
2645 | ||
2646 | #[inline] | |
85aaf69f | 2647 | fn size_hint(&self) -> (usize, Option<usize>) { |
b039eaaf | 2648 | self.iter.size_hint() |
1a4d82fc JJ |
2649 | } |
2650 | } | |
2651 | ||
c30ab7b3 | 2652 | #[stable(feature = "drain", since = "1.6.0")] |
9fa01778 | 2653 | impl<T> DoubleEndedIterator for Drain<'_, T> { |
1a4d82fc JJ |
2654 | #[inline] |
2655 | fn next_back(&mut self) -> Option<T> { | |
92a42be0 | 2656 | self.iter.next_back().map(|elt| unsafe { ptr::read(elt) }) |
1a4d82fc JJ |
2657 | } |
2658 | } | |
2659 | ||
c30ab7b3 | 2660 | #[stable(feature = "drain", since = "1.6.0")] |
9fa01778 | 2661 | impl<T> ExactSizeIterator for Drain<'_, T> {} |
1a4d82fc | 2662 | |
0531ce1d | 2663 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 2664 | impl<T> FusedIterator for Drain<'_, T> {} |
9e0c209e | 2665 | |
85aaf69f SL |
2666 | #[stable(feature = "rust1", since = "1.0.0")] |
2667 | impl<A: PartialEq> PartialEq for VecDeque<A> { | |
2668 | fn eq(&self, other: &VecDeque<A>) -> bool { | |
7453a54e SL |
2669 | if self.len() != other.len() { |
2670 | return false; | |
2671 | } | |
2672 | let (sa, sb) = self.as_slices(); | |
2673 | let (oa, ob) = other.as_slices(); | |
2674 | if sa.len() == oa.len() { | |
2675 | sa == oa && sb == ob | |
2676 | } else if sa.len() < oa.len() { | |
2677 | // Always divisible in three sections, for example: | |
2678 | // self: [a b c|d e f] | |
2679 | // other: [0 1 2 3|4 5] | |
2680 | // front = 3, mid = 1, | |
2681 | // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5] | |
2682 | let front = sa.len(); | |
2683 | let mid = oa.len() - front; | |
2684 | ||
2685 | let (oa_front, oa_mid) = oa.split_at(front); | |
2686 | let (sb_mid, sb_back) = sb.split_at(mid); | |
2687 | debug_assert_eq!(sa.len(), oa_front.len()); | |
2688 | debug_assert_eq!(sb_mid.len(), oa_mid.len()); | |
2689 | debug_assert_eq!(sb_back.len(), ob.len()); | |
2690 | sa == oa_front && sb_mid == oa_mid && sb_back == ob | |
2691 | } else { | |
2692 | let front = oa.len(); | |
2693 | let mid = sa.len() - front; | |
2694 | ||
2695 | let (sa_front, sa_mid) = sa.split_at(front); | |
2696 | let (ob_mid, ob_back) = ob.split_at(mid); | |
2697 | debug_assert_eq!(sa_front.len(), oa.len()); | |
2698 | debug_assert_eq!(sa_mid.len(), ob_mid.len()); | |
2699 | debug_assert_eq!(sb.len(), ob_back.len()); | |
2700 | sa_front == oa && sa_mid == ob_mid && sb == ob_back | |
2701 | } | |
1a4d82fc JJ |
2702 | } |
2703 | } | |
2704 | ||
85aaf69f SL |
2705 | #[stable(feature = "rust1", since = "1.0.0")] |
2706 | impl<A: Eq> Eq for VecDeque<A> {} | |
1a4d82fc | 2707 | |
8bb4bdeb | 2708 | macro_rules! __impl_slice_eq1 { |
416331ca | 2709 | ([$($vars:tt)*] $lhs:ty, $rhs:ty, $($constraints:tt)*) => { |
b7449926 | 2710 | #[stable(feature = "vec_deque_partial_eq_slice", since = "1.17.0")] |
416331ca XL |
2711 | impl<A, B, $($vars)*> PartialEq<$rhs> for $lhs |
2712 | where | |
2713 | A: PartialEq<B>, | |
2714 | $($constraints)* | |
2715 | { | |
2716 | fn eq(&self, other: &$rhs) -> bool { | |
8bb4bdeb XL |
2717 | if self.len() != other.len() { |
2718 | return false; | |
2719 | } | |
2720 | let (sa, sb) = self.as_slices(); | |
2721 | let (oa, ob) = other[..].split_at(sa.len()); | |
2722 | sa == oa && sb == ob | |
2723 | } | |
2724 | } | |
2725 | } | |
2726 | } | |
2727 | ||
416331ca XL |
2728 | __impl_slice_eq1! { [] VecDeque<A>, Vec<B>, } |
2729 | __impl_slice_eq1! { [] VecDeque<A>, &[B], } | |
2730 | __impl_slice_eq1! { [] VecDeque<A>, &mut [B], } | |
2731 | __impl_slice_eq1! { [const N: usize] VecDeque<A>, [B; N], [B; N]: LengthAtMost32 } | |
2732 | __impl_slice_eq1! { [const N: usize] VecDeque<A>, &[B; N], [B; N]: LengthAtMost32 } | |
2733 | __impl_slice_eq1! { [const N: usize] VecDeque<A>, &mut [B; N], [B; N]: LengthAtMost32 } | |
8bb4bdeb | 2734 | |
85aaf69f SL |
2735 | #[stable(feature = "rust1", since = "1.0.0")] |
2736 | impl<A: PartialOrd> PartialOrd for VecDeque<A> { | |
2737 | fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering> { | |
e9174d1e | 2738 | self.iter().partial_cmp(other.iter()) |
1a4d82fc JJ |
2739 | } |
2740 | } | |
2741 | ||
85aaf69f SL |
2742 | #[stable(feature = "rust1", since = "1.0.0")] |
2743 | impl<A: Ord> Ord for VecDeque<A> { | |
1a4d82fc | 2744 | #[inline] |
85aaf69f | 2745 | fn cmp(&self, other: &VecDeque<A>) -> Ordering { |
e9174d1e | 2746 | self.iter().cmp(other.iter()) |
1a4d82fc JJ |
2747 | } |
2748 | } | |
2749 | ||
85aaf69f | 2750 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
2751 | impl<A: Hash> Hash for VecDeque<A> { |
2752 | fn hash<H: Hasher>(&self, state: &mut H) { | |
2753 | self.len().hash(state); | |
7453a54e SL |
2754 | let (a, b) = self.as_slices(); |
2755 | Hash::hash_slice(a, state); | |
2756 | Hash::hash_slice(b, state); | |
1a4d82fc JJ |
2757 | } |
2758 | } | |
2759 | ||
85aaf69f SL |
2760 | #[stable(feature = "rust1", since = "1.0.0")] |
2761 | impl<A> Index<usize> for VecDeque<A> { | |
1a4d82fc JJ |
2762 | type Output = A; |
2763 | ||
2764 | #[inline] | |
c1a9b12d SL |
2765 | fn index(&self, index: usize) -> &A { |
2766 | self.get(index).expect("Out of bounds access") | |
1a4d82fc JJ |
2767 | } |
2768 | } | |
2769 | ||
85aaf69f SL |
2770 | #[stable(feature = "rust1", since = "1.0.0")] |
2771 | impl<A> IndexMut<usize> for VecDeque<A> { | |
1a4d82fc | 2772 | #[inline] |
c1a9b12d SL |
2773 | fn index_mut(&mut self, index: usize) -> &mut A { |
2774 | self.get_mut(index).expect("Out of bounds access") | |
1a4d82fc JJ |
2775 | } |
2776 | } | |
2777 | ||
85aaf69f SL |
2778 | #[stable(feature = "rust1", since = "1.0.0")] |
2779 | impl<A> FromIterator<A> for VecDeque<A> { | |
54a0048b SL |
2780 | fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> VecDeque<A> { |
2781 | let iterator = iter.into_iter(); | |
1a4d82fc | 2782 | let (lower, _) = iterator.size_hint(); |
85aaf69f | 2783 | let mut deq = VecDeque::with_capacity(lower); |
1a4d82fc JJ |
2784 | deq.extend(iterator); |
2785 | deq | |
2786 | } | |
2787 | } | |
2788 | ||
85aaf69f SL |
2789 | #[stable(feature = "rust1", since = "1.0.0")] |
2790 | impl<T> IntoIterator for VecDeque<T> { | |
2791 | type Item = T; | |
2792 | type IntoIter = IntoIter<T>; | |
2793 | ||
2c00a5a8 | 2794 | /// Consumes the `VecDeque` into a front-to-back iterator yielding elements by |
9346a6ac | 2795 | /// value. |
85aaf69f | 2796 | fn into_iter(self) -> IntoIter<T> { |
92a42be0 | 2797 | IntoIter { inner: self } |
85aaf69f SL |
2798 | } |
2799 | } | |
2800 | ||
2801 | #[stable(feature = "rust1", since = "1.0.0")] | |
2802 | impl<'a, T> IntoIterator for &'a VecDeque<T> { | |
2803 | type Item = &'a T; | |
2804 | type IntoIter = Iter<'a, T>; | |
2805 | ||
2806 | fn into_iter(self) -> Iter<'a, T> { | |
2807 | self.iter() | |
2808 | } | |
2809 | } | |
2810 | ||
2811 | #[stable(feature = "rust1", since = "1.0.0")] | |
2812 | impl<'a, T> IntoIterator for &'a mut VecDeque<T> { | |
2813 | type Item = &'a mut T; | |
2814 | type IntoIter = IterMut<'a, T>; | |
2815 | ||
3b2f2976 | 2816 | fn into_iter(self) -> IterMut<'a, T> { |
85aaf69f SL |
2817 | self.iter_mut() |
2818 | } | |
2819 | } | |
2820 | ||
2821 | #[stable(feature = "rust1", since = "1.0.0")] | |
2822 | impl<A> Extend<A> for VecDeque<A> { | |
92a42be0 | 2823 | fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) { |
60c5eb7d XL |
2824 | // This function should be the moral equivalent of: |
2825 | // | |
2826 | // for item in iter.into_iter() { | |
2827 | // self.push_back(item); | |
2828 | // } | |
2829 | let mut iter = iter.into_iter(); | |
2830 | while let Some(element) = iter.next() { | |
2831 | if self.len() == self.capacity() { | |
2832 | let (lower, _) = iter.size_hint(); | |
2833 | self.reserve(lower.saturating_add(1)); | |
2834 | } | |
2835 | ||
2836 | let head = self.head; | |
2837 | self.head = self.wrap_add(self.head, 1); | |
2838 | unsafe { self.buffer_write(head, element); } | |
2839 | } | |
1a4d82fc JJ |
2840 | } |
2841 | } | |
2842 | ||
62682a34 SL |
2843 | #[stable(feature = "extend_ref", since = "1.2.0")] |
2844 | impl<'a, T: 'a + Copy> Extend<&'a T> for VecDeque<T> { | |
92a42be0 | 2845 | fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { |
62682a34 SL |
2846 | self.extend(iter.into_iter().cloned()); |
2847 | } | |
2848 | } | |
2849 | ||
85aaf69f SL |
2850 | #[stable(feature = "rust1", since = "1.0.0")] |
2851 | impl<T: fmt::Debug> fmt::Debug for VecDeque<T> { | |
9fa01778 | 2852 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
b039eaaf | 2853 | f.debug_list().entries(self).finish() |
1a4d82fc JJ |
2854 | } |
2855 | } | |
2856 | ||
a7813a04 XL |
2857 | #[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")] |
2858 | impl<T> From<Vec<T>> for VecDeque<T> { | |
dc9dc135 XL |
2859 | /// Turn a [`Vec<T>`] into a [`VecDeque<T>`]. |
2860 | /// | |
416331ca XL |
2861 | /// [`Vec<T>`]: crate::vec::Vec |
2862 | /// [`VecDeque<T>`]: crate::collections::VecDeque | |
2863 | /// | |
dc9dc135 XL |
2864 | /// This avoids reallocating where possible, but the conditions for that are |
2865 | /// strict, and subject to change, and so shouldn't be relied upon unless the | |
2866 | /// `Vec<T>` came from `From<VecDeque<T>>` and hasn't been reallocated. | |
a7813a04 XL |
2867 | fn from(mut other: Vec<T>) -> Self { |
2868 | unsafe { | |
2869 | let other_buf = other.as_mut_ptr(); | |
2870 | let mut buf = RawVec::from_raw_parts(other_buf, other.capacity()); | |
2871 | let len = other.len(); | |
2872 | mem::forget(other); | |
2873 | ||
2874 | // We need to extend the buf if it's not a power of two, too small | |
2875 | // or doesn't have at least one free space | |
416331ca XL |
2876 | if !buf.capacity().is_power_of_two() || (buf.capacity() < (MINIMUM_CAPACITY + 1)) || |
2877 | (buf.capacity() == len) { | |
2878 | let cap = cmp::max(buf.capacity() + 1, MINIMUM_CAPACITY + 1).next_power_of_two(); | |
a7813a04 XL |
2879 | buf.reserve_exact(len, cap - len); |
2880 | } | |
2881 | ||
2882 | VecDeque { | |
2883 | tail: 0, | |
2884 | head: len, | |
3b2f2976 | 2885 | buf, |
a7813a04 XL |
2886 | } |
2887 | } | |
2888 | } | |
2889 | } | |
2890 | ||
2891 | #[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")] | |
2892 | impl<T> From<VecDeque<T>> for Vec<T> { | |
dc9dc135 XL |
2893 | /// Turn a [`VecDeque<T>`] into a [`Vec<T>`]. |
2894 | /// | |
416331ca XL |
2895 | /// [`Vec<T>`]: crate::vec::Vec |
2896 | /// [`VecDeque<T>`]: crate::collections::VecDeque | |
2897 | /// | |
dc9dc135 XL |
2898 | /// This never needs to re-allocate, but does need to do O(n) data movement if |
2899 | /// the circular buffer doesn't happen to be at the beginning of the allocation. | |
2900 | /// | |
2901 | /// # Examples | |
2902 | /// | |
2903 | /// ``` | |
2904 | /// use std::collections::VecDeque; | |
2905 | /// | |
2906 | /// // This one is O(1). | |
2907 | /// let deque: VecDeque<_> = (1..5).collect(); | |
2908 | /// let ptr = deque.as_slices().0.as_ptr(); | |
2909 | /// let vec = Vec::from(deque); | |
2910 | /// assert_eq!(vec, [1, 2, 3, 4]); | |
2911 | /// assert_eq!(vec.as_ptr(), ptr); | |
2912 | /// | |
2913 | /// // This one needs data rearranging. | |
2914 | /// let mut deque: VecDeque<_> = (1..5).collect(); | |
2915 | /// deque.push_front(9); | |
2916 | /// deque.push_front(8); | |
2917 | /// let ptr = deque.as_slices().1.as_ptr(); | |
2918 | /// let vec = Vec::from(deque); | |
2919 | /// assert_eq!(vec, [8, 9, 1, 2, 3, 4]); | |
2920 | /// assert_eq!(vec.as_ptr(), ptr); | |
2921 | /// ``` | |
a7813a04 XL |
2922 | fn from(other: VecDeque<T>) -> Self { |
2923 | unsafe { | |
2924 | let buf = other.buf.ptr(); | |
2925 | let len = other.len(); | |
2926 | let tail = other.tail; | |
2927 | let head = other.head; | |
2928 | let cap = other.cap(); | |
2929 | ||
2930 | // Need to move the ring to the front of the buffer, as vec will expect this. | |
2931 | if other.is_contiguous() { | |
b7449926 | 2932 | ptr::copy(buf.add(tail), buf, len); |
a7813a04 | 2933 | } else { |
2c00a5a8 | 2934 | if (tail - head) >= cmp::min(cap - tail, head) { |
a7813a04 XL |
2935 | // There is enough free space in the centre for the shortest block so we can |
2936 | // do this in at most three copy moves. | |
2937 | if (cap - tail) > head { | |
2938 | // right hand block is the long one; move that enough for the left | |
b7449926 XL |
2939 | ptr::copy(buf.add(tail), |
2940 | buf.add(tail - head), | |
32a655c1 | 2941 | cap - tail); |
a7813a04 | 2942 | // copy left in the end |
b7449926 | 2943 | ptr::copy(buf, buf.add(cap - head), head); |
a7813a04 | 2944 | // shift the new thing to the start |
b7449926 | 2945 | ptr::copy(buf.add(tail - head), buf, len); |
a7813a04 XL |
2946 | } else { |
2947 | // left hand block is the long one, we can do it in two! | |
b7449926 XL |
2948 | ptr::copy(buf, buf.add(cap - tail), head); |
2949 | ptr::copy(buf.add(tail), buf, cap - tail); | |
a7813a04 XL |
2950 | } |
2951 | } else { | |
2952 | // Need to use N swaps to move the ring | |
2953 | // We can use the space at the end of the ring as a temp store | |
2954 | ||
2955 | let mut left_edge: usize = 0; | |
2956 | let mut right_edge: usize = tail; | |
2957 | ||
2958 | // The general problem looks like this | |
2959 | // GHIJKLM...ABCDEF - before any swaps | |
2960 | // ABCDEFM...GHIJKL - after 1 pass of swaps | |
2961 | // ABCDEFGHIJM...KL - swap until the left edge reaches the temp store | |
2962 | // - then restart the algorithm with a new (smaller) store | |
2963 | // Sometimes the temp store is reached when the right edge is at the end | |
2964 | // of the buffer - this means we've hit the right order with fewer swaps! | |
2965 | // E.g | |
2966 | // EF..ABCD | |
2967 | // ABCDEF.. - after four only swaps we've finished | |
2968 | ||
2969 | while left_edge < len && right_edge != cap { | |
2970 | let mut right_offset = 0; | |
2971 | for i in left_edge..right_edge { | |
2972 | right_offset = (i - left_edge) % (cap - right_edge); | |
4462d4a0 XL |
2973 | let src: isize = (right_edge + right_offset) as isize; |
2974 | ptr::swap(buf.add(i), buf.offset(src)); | |
a7813a04 XL |
2975 | } |
2976 | let n_ops = right_edge - left_edge; | |
2977 | left_edge += n_ops; | |
2978 | right_edge += right_offset + 1; | |
2979 | ||
2980 | } | |
2981 | } | |
2982 | ||
2983 | } | |
2984 | let out = Vec::from_raw_parts(buf, len, cap); | |
2985 | mem::forget(other); | |
2986 | out | |
2987 | } | |
2988 | } | |
2989 | } |