]>
Commit | Line | Data |
---|---|---|
c34b1796 AL |
1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | use std::collections::VecDeque; | |
12 | use std::fmt::Debug; | |
8bb4bdeb | 13 | use std::collections::vec_deque::{Drain}; |
c34b1796 AL |
14 | |
15 | use self::Taggy::*; | |
16 | use self::Taggypar::*; | |
17 | ||
18 | #[test] | |
19 | fn test_simple() { | |
20 | let mut d = VecDeque::new(); | |
21 | assert_eq!(d.len(), 0); | |
22 | d.push_front(17); | |
23 | d.push_front(42); | |
24 | d.push_back(137); | |
25 | assert_eq!(d.len(), 3); | |
26 | d.push_back(137); | |
27 | assert_eq!(d.len(), 4); | |
28 | assert_eq!(*d.front().unwrap(), 42); | |
29 | assert_eq!(*d.back().unwrap(), 137); | |
30 | let mut i = d.pop_front(); | |
31 | assert_eq!(i, Some(42)); | |
32 | i = d.pop_back(); | |
33 | assert_eq!(i, Some(137)); | |
34 | i = d.pop_back(); | |
35 | assert_eq!(i, Some(137)); | |
36 | i = d.pop_back(); | |
37 | assert_eq!(i, Some(17)); | |
38 | assert_eq!(d.len(), 0); | |
39 | d.push_back(3); | |
40 | assert_eq!(d.len(), 1); | |
41 | d.push_front(2); | |
42 | assert_eq!(d.len(), 2); | |
43 | d.push_back(4); | |
44 | assert_eq!(d.len(), 3); | |
45 | d.push_front(1); | |
46 | assert_eq!(d.len(), 4); | |
c34b1796 AL |
47 | assert_eq!(d[0], 1); |
48 | assert_eq!(d[1], 2); | |
49 | assert_eq!(d[2], 3); | |
50 | assert_eq!(d[3], 4); | |
51 | } | |
52 | ||
53 | #[cfg(test)] | |
3157f602 | 54 | fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) { |
c34b1796 AL |
55 | let mut deq = VecDeque::new(); |
56 | assert_eq!(deq.len(), 0); | |
57 | deq.push_front(a.clone()); | |
58 | deq.push_front(b.clone()); | |
59 | deq.push_back(c.clone()); | |
60 | assert_eq!(deq.len(), 3); | |
61 | deq.push_back(d.clone()); | |
62 | assert_eq!(deq.len(), 4); | |
63 | assert_eq!((*deq.front().unwrap()).clone(), b.clone()); | |
64 | assert_eq!((*deq.back().unwrap()).clone(), d.clone()); | |
65 | assert_eq!(deq.pop_front().unwrap(), b.clone()); | |
66 | assert_eq!(deq.pop_back().unwrap(), d.clone()); | |
67 | assert_eq!(deq.pop_back().unwrap(), c.clone()); | |
68 | assert_eq!(deq.pop_back().unwrap(), a.clone()); | |
69 | assert_eq!(deq.len(), 0); | |
70 | deq.push_back(c.clone()); | |
71 | assert_eq!(deq.len(), 1); | |
72 | deq.push_front(b.clone()); | |
73 | assert_eq!(deq.len(), 2); | |
74 | deq.push_back(d.clone()); | |
75 | assert_eq!(deq.len(), 3); | |
76 | deq.push_front(a.clone()); | |
77 | assert_eq!(deq.len(), 4); | |
78 | assert_eq!(deq[0].clone(), a.clone()); | |
79 | assert_eq!(deq[1].clone(), b.clone()); | |
80 | assert_eq!(deq[2].clone(), c.clone()); | |
81 | assert_eq!(deq[3].clone(), d.clone()); | |
82 | } | |
83 | ||
84 | #[test] | |
85 | fn test_push_front_grow() { | |
86 | let mut deq = VecDeque::new(); | |
87 | for i in 0..66 { | |
88 | deq.push_front(i); | |
89 | } | |
90 | assert_eq!(deq.len(), 66); | |
91 | ||
92 | for i in 0..66 { | |
93 | assert_eq!(deq[i], 65 - i); | |
94 | } | |
95 | ||
96 | let mut deq = VecDeque::new(); | |
97 | for i in 0..66 { | |
98 | deq.push_back(i); | |
99 | } | |
100 | ||
101 | for i in 0..66 { | |
102 | assert_eq!(deq[i], i); | |
103 | } | |
104 | } | |
105 | ||
106 | #[test] | |
107 | fn test_index() { | |
108 | let mut deq = VecDeque::new(); | |
109 | for i in 1..4 { | |
110 | deq.push_front(i); | |
111 | } | |
112 | assert_eq!(deq[1], 2); | |
113 | } | |
114 | ||
115 | #[test] | |
116 | #[should_panic] | |
117 | fn test_index_out_of_bounds() { | |
118 | let mut deq = VecDeque::new(); | |
119 | for i in 1..4 { | |
120 | deq.push_front(i); | |
121 | } | |
122 | deq[3]; | |
123 | } | |
124 | ||
c34b1796 AL |
125 | #[derive(Clone, PartialEq, Debug)] |
126 | enum Taggy { | |
127 | One(i32), | |
128 | Two(i32, i32), | |
129 | Three(i32, i32, i32), | |
130 | } | |
131 | ||
132 | #[derive(Clone, PartialEq, Debug)] | |
133 | enum Taggypar<T> { | |
134 | Onepar(T), | |
135 | Twopar(T, T), | |
136 | Threepar(T, T, T), | |
137 | } | |
138 | ||
139 | #[derive(Clone, PartialEq, Debug)] | |
140 | struct RecCy { | |
141 | x: i32, | |
142 | y: i32, | |
3157f602 | 143 | t: Taggy, |
c34b1796 AL |
144 | } |
145 | ||
146 | #[test] | |
147 | fn test_param_int() { | |
148 | test_parameterized::<i32>(5, 72, 64, 175); | |
149 | } | |
150 | ||
151 | #[test] | |
152 | fn test_param_taggy() { | |
153 | test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42)); | |
154 | } | |
155 | ||
156 | #[test] | |
157 | fn test_param_taggypar() { | |
158 | test_parameterized::<Taggypar<i32>>(Onepar::<i32>(1), | |
159 | Twopar::<i32>(1, 2), | |
160 | Threepar::<i32>(1, 2, 3), | |
161 | Twopar::<i32>(17, 42)); | |
162 | } | |
163 | ||
164 | #[test] | |
165 | fn test_param_reccy() { | |
3157f602 XL |
166 | let reccy1 = RecCy { |
167 | x: 1, | |
168 | y: 2, | |
169 | t: One(1), | |
170 | }; | |
171 | let reccy2 = RecCy { | |
172 | x: 345, | |
173 | y: 2, | |
174 | t: Two(1, 2), | |
175 | }; | |
176 | let reccy3 = RecCy { | |
177 | x: 1, | |
178 | y: 777, | |
179 | t: Three(1, 2, 3), | |
180 | }; | |
181 | let reccy4 = RecCy { | |
182 | x: 19, | |
183 | y: 252, | |
184 | t: Two(17, 42), | |
185 | }; | |
c34b1796 AL |
186 | test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4); |
187 | } | |
188 | ||
189 | #[test] | |
190 | fn test_with_capacity() { | |
191 | let mut d = VecDeque::with_capacity(0); | |
192 | d.push_back(1); | |
193 | assert_eq!(d.len(), 1); | |
194 | let mut d = VecDeque::with_capacity(50); | |
195 | d.push_back(1); | |
196 | assert_eq!(d.len(), 1); | |
197 | } | |
198 | ||
199 | #[test] | |
200 | fn test_with_capacity_non_power_two() { | |
201 | let mut d3 = VecDeque::with_capacity(3); | |
202 | d3.push_back(1); | |
203 | ||
204 | // X = None, | = lo | |
205 | // [|1, X, X] | |
206 | assert_eq!(d3.pop_front(), Some(1)); | |
207 | // [X, |X, X] | |
208 | assert_eq!(d3.front(), None); | |
209 | ||
210 | // [X, |3, X] | |
211 | d3.push_back(3); | |
212 | // [X, |3, 6] | |
213 | d3.push_back(6); | |
214 | // [X, X, |6] | |
215 | assert_eq!(d3.pop_front(), Some(3)); | |
216 | ||
217 | // Pushing the lo past half way point to trigger | |
218 | // the 'B' scenario for growth | |
219 | // [9, X, |6] | |
220 | d3.push_back(9); | |
221 | // [9, 12, |6] | |
222 | d3.push_back(12); | |
223 | ||
224 | d3.push_back(15); | |
225 | // There used to be a bug here about how the | |
226 | // VecDeque made growth assumptions about the | |
227 | // underlying Vec which didn't hold and lead | |
228 | // to corruption. | |
229 | // (Vec grows to next power of two) | |
3157f602 XL |
230 | // good- [9, 12, 15, X, X, X, X, |6] |
231 | // bug- [15, 12, X, X, X, |6, X, X] | |
c34b1796 AL |
232 | assert_eq!(d3.pop_front(), Some(6)); |
233 | ||
234 | // Which leads us to the following state which | |
235 | // would be a failure case. | |
3157f602 | 236 | // bug- [15, 12, X, X, X, X, |X, X] |
c34b1796 AL |
237 | assert_eq!(d3.front(), Some(&9)); |
238 | } | |
239 | ||
240 | #[test] | |
241 | fn test_reserve_exact() { | |
242 | let mut d = VecDeque::new(); | |
243 | d.push_back(0); | |
244 | d.reserve_exact(50); | |
245 | assert!(d.capacity() >= 51); | |
246 | } | |
247 | ||
248 | #[test] | |
249 | fn test_reserve() { | |
250 | let mut d = VecDeque::new(); | |
251 | d.push_back(0); | |
252 | d.reserve(50); | |
253 | assert!(d.capacity() >= 51); | |
254 | } | |
255 | ||
256 | #[test] | |
257 | fn test_swap() { | |
258 | let mut d: VecDeque<_> = (0..5).collect(); | |
259 | d.pop_front(); | |
260 | d.swap(0, 3); | |
261 | assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]); | |
262 | } | |
263 | ||
264 | #[test] | |
265 | fn test_iter() { | |
266 | let mut d = VecDeque::new(); | |
267 | assert_eq!(d.iter().next(), None); | |
268 | assert_eq!(d.iter().size_hint(), (0, Some(0))); | |
269 | ||
270 | for i in 0..5 { | |
271 | d.push_back(i); | |
272 | } | |
273 | { | |
3157f602 | 274 | let b: &[_] = &[&0, &1, &2, &3, &4]; |
c34b1796 AL |
275 | assert_eq!(d.iter().collect::<Vec<_>>(), b); |
276 | } | |
277 | ||
278 | for i in 6..9 { | |
279 | d.push_front(i); | |
280 | } | |
281 | { | |
3157f602 | 282 | let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4]; |
c34b1796 AL |
283 | assert_eq!(d.iter().collect::<Vec<_>>(), b); |
284 | } | |
285 | ||
286 | let mut it = d.iter(); | |
287 | let mut len = d.len(); | |
288 | loop { | |
289 | match it.next() { | |
290 | None => break, | |
3157f602 XL |
291 | _ => { |
292 | len -= 1; | |
293 | assert_eq!(it.size_hint(), (len, Some(len))) | |
294 | } | |
c34b1796 AL |
295 | } |
296 | } | |
297 | } | |
298 | ||
299 | #[test] | |
300 | fn test_rev_iter() { | |
301 | let mut d = VecDeque::new(); | |
302 | assert_eq!(d.iter().rev().next(), None); | |
303 | ||
304 | for i in 0..5 { | |
305 | d.push_back(i); | |
306 | } | |
307 | { | |
3157f602 | 308 | let b: &[_] = &[&4, &3, &2, &1, &0]; |
c34b1796 AL |
309 | assert_eq!(d.iter().rev().collect::<Vec<_>>(), b); |
310 | } | |
311 | ||
312 | for i in 6..9 { | |
313 | d.push_front(i); | |
314 | } | |
3157f602 | 315 | let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8]; |
c34b1796 AL |
316 | assert_eq!(d.iter().rev().collect::<Vec<_>>(), b); |
317 | } | |
318 | ||
319 | #[test] | |
320 | fn test_mut_rev_iter_wrap() { | |
321 | let mut d = VecDeque::with_capacity(3); | |
322 | assert!(d.iter_mut().rev().next().is_none()); | |
323 | ||
324 | d.push_back(1); | |
325 | d.push_back(2); | |
326 | d.push_back(3); | |
327 | assert_eq!(d.pop_front(), Some(1)); | |
328 | d.push_back(4); | |
329 | ||
330 | assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), | |
331 | vec![4, 3, 2]); | |
332 | } | |
333 | ||
334 | #[test] | |
335 | fn test_mut_iter() { | |
336 | let mut d = VecDeque::new(); | |
337 | assert!(d.iter_mut().next().is_none()); | |
338 | ||
339 | for i in 0..3 { | |
340 | d.push_front(i); | |
341 | } | |
342 | ||
343 | for (i, elt) in d.iter_mut().enumerate() { | |
344 | assert_eq!(*elt, 2 - i); | |
345 | *elt = i; | |
346 | } | |
347 | ||
348 | { | |
349 | let mut it = d.iter_mut(); | |
350 | assert_eq!(*it.next().unwrap(), 0); | |
351 | assert_eq!(*it.next().unwrap(), 1); | |
352 | assert_eq!(*it.next().unwrap(), 2); | |
353 | assert!(it.next().is_none()); | |
354 | } | |
355 | } | |
356 | ||
357 | #[test] | |
358 | fn test_mut_rev_iter() { | |
359 | let mut d = VecDeque::new(); | |
360 | assert!(d.iter_mut().rev().next().is_none()); | |
361 | ||
362 | for i in 0..3 { | |
363 | d.push_front(i); | |
364 | } | |
365 | ||
366 | for (i, elt) in d.iter_mut().rev().enumerate() { | |
367 | assert_eq!(*elt, i); | |
368 | *elt = i; | |
369 | } | |
370 | ||
371 | { | |
372 | let mut it = d.iter_mut().rev(); | |
373 | assert_eq!(*it.next().unwrap(), 0); | |
374 | assert_eq!(*it.next().unwrap(), 1); | |
375 | assert_eq!(*it.next().unwrap(), 2); | |
376 | assert!(it.next().is_none()); | |
377 | } | |
378 | } | |
379 | ||
380 | #[test] | |
381 | fn test_into_iter() { | |
382 | ||
383 | // Empty iter | |
384 | { | |
385 | let d: VecDeque<i32> = VecDeque::new(); | |
386 | let mut iter = d.into_iter(); | |
387 | ||
388 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
389 | assert_eq!(iter.next(), None); | |
390 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
391 | } | |
392 | ||
393 | // simple iter | |
394 | { | |
395 | let mut d = VecDeque::new(); | |
396 | for i in 0..5 { | |
397 | d.push_back(i); | |
398 | } | |
399 | ||
3157f602 | 400 | let b = vec![0, 1, 2, 3, 4]; |
c34b1796 AL |
401 | assert_eq!(d.into_iter().collect::<Vec<_>>(), b); |
402 | } | |
403 | ||
404 | // wrapped iter | |
405 | { | |
406 | let mut d = VecDeque::new(); | |
407 | for i in 0..5 { | |
408 | d.push_back(i); | |
409 | } | |
410 | for i in 6..9 { | |
411 | d.push_front(i); | |
412 | } | |
413 | ||
3157f602 | 414 | let b = vec![8, 7, 6, 0, 1, 2, 3, 4]; |
c34b1796 AL |
415 | assert_eq!(d.into_iter().collect::<Vec<_>>(), b); |
416 | } | |
417 | ||
418 | // partially used | |
419 | { | |
420 | let mut d = VecDeque::new(); | |
421 | for i in 0..5 { | |
422 | d.push_back(i); | |
423 | } | |
424 | for i in 6..9 { | |
425 | d.push_front(i); | |
426 | } | |
427 | ||
428 | let mut it = d.into_iter(); | |
429 | assert_eq!(it.size_hint(), (8, Some(8))); | |
430 | assert_eq!(it.next(), Some(8)); | |
431 | assert_eq!(it.size_hint(), (7, Some(7))); | |
432 | assert_eq!(it.next_back(), Some(4)); | |
433 | assert_eq!(it.size_hint(), (6, Some(6))); | |
434 | assert_eq!(it.next(), Some(7)); | |
435 | assert_eq!(it.size_hint(), (5, Some(5))); | |
436 | } | |
437 | } | |
438 | ||
439 | #[test] | |
440 | fn test_drain() { | |
441 | ||
442 | // Empty iter | |
443 | { | |
444 | let mut d: VecDeque<i32> = VecDeque::new(); | |
445 | ||
446 | { | |
b039eaaf | 447 | let mut iter = d.drain(..); |
c34b1796 AL |
448 | |
449 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
450 | assert_eq!(iter.next(), None); | |
451 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
452 | } | |
453 | ||
454 | assert!(d.is_empty()); | |
455 | } | |
456 | ||
457 | // simple iter | |
458 | { | |
459 | let mut d = VecDeque::new(); | |
460 | for i in 0..5 { | |
461 | d.push_back(i); | |
462 | } | |
463 | ||
b039eaaf | 464 | assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]); |
c34b1796 AL |
465 | assert!(d.is_empty()); |
466 | } | |
467 | ||
468 | // wrapped iter | |
469 | { | |
470 | let mut d = VecDeque::new(); | |
471 | for i in 0..5 { | |
472 | d.push_back(i); | |
473 | } | |
474 | for i in 6..9 { | |
475 | d.push_front(i); | |
476 | } | |
477 | ||
3157f602 | 478 | assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]); |
c34b1796 AL |
479 | assert!(d.is_empty()); |
480 | } | |
481 | ||
482 | // partially used | |
483 | { | |
484 | let mut d: VecDeque<_> = VecDeque::new(); | |
485 | for i in 0..5 { | |
486 | d.push_back(i); | |
487 | } | |
488 | for i in 6..9 { | |
489 | d.push_front(i); | |
490 | } | |
491 | ||
492 | { | |
b039eaaf | 493 | let mut it = d.drain(..); |
c34b1796 AL |
494 | assert_eq!(it.size_hint(), (8, Some(8))); |
495 | assert_eq!(it.next(), Some(8)); | |
496 | assert_eq!(it.size_hint(), (7, Some(7))); | |
497 | assert_eq!(it.next_back(), Some(4)); | |
498 | assert_eq!(it.size_hint(), (6, Some(6))); | |
499 | assert_eq!(it.next(), Some(7)); | |
500 | assert_eq!(it.size_hint(), (5, Some(5))); | |
501 | } | |
502 | assert!(d.is_empty()); | |
503 | } | |
504 | } | |
505 | ||
506 | #[test] | |
507 | fn test_from_iter() { | |
3157f602 | 508 | let v = vec![1, 2, 3, 4, 5, 6, 7]; |
c34b1796 AL |
509 | let deq: VecDeque<_> = v.iter().cloned().collect(); |
510 | let u: Vec<_> = deq.iter().cloned().collect(); | |
511 | assert_eq!(u, v); | |
512 | ||
7cac9316 XL |
513 | // FIXME #27741: Remove `.skip(0)` when Range::step_by is fully removed |
514 | let seq = (0..).skip(0).step_by(2).take(256); | |
c34b1796 AL |
515 | let deq: VecDeque<_> = seq.collect(); |
516 | for (i, &x) in deq.iter().enumerate() { | |
3157f602 | 517 | assert_eq!(2 * i, x); |
c34b1796 AL |
518 | } |
519 | assert_eq!(deq.len(), 256); | |
520 | } | |
521 | ||
522 | #[test] | |
523 | fn test_clone() { | |
524 | let mut d = VecDeque::new(); | |
525 | d.push_front(17); | |
526 | d.push_front(42); | |
527 | d.push_back(137); | |
528 | d.push_back(137); | |
529 | assert_eq!(d.len(), 4); | |
530 | let mut e = d.clone(); | |
531 | assert_eq!(e.len(), 4); | |
532 | while !d.is_empty() { | |
533 | assert_eq!(d.pop_back(), e.pop_back()); | |
534 | } | |
535 | assert_eq!(d.len(), 0); | |
536 | assert_eq!(e.len(), 0); | |
537 | } | |
538 | ||
539 | #[test] | |
540 | fn test_eq() { | |
541 | let mut d = VecDeque::new(); | |
542 | assert!(d == VecDeque::with_capacity(0)); | |
543 | d.push_front(137); | |
544 | d.push_front(17); | |
545 | d.push_front(42); | |
546 | d.push_back(137); | |
547 | let mut e = VecDeque::with_capacity(0); | |
548 | e.push_back(42); | |
549 | e.push_back(17); | |
550 | e.push_back(137); | |
551 | e.push_back(137); | |
552 | assert!(&e == &d); | |
553 | e.pop_back(); | |
554 | e.push_back(0); | |
555 | assert!(e != d); | |
556 | e.clear(); | |
557 | assert!(e == VecDeque::new()); | |
558 | } | |
559 | ||
8bb4bdeb XL |
560 | #[test] |
561 | fn test_partial_eq_array() { | |
562 | let d = VecDeque::<char>::new(); | |
563 | assert!(d == []); | |
564 | ||
565 | let mut d = VecDeque::new(); | |
566 | d.push_front('a'); | |
567 | assert!(d == ['a']); | |
568 | ||
569 | let mut d = VecDeque::new(); | |
570 | d.push_back('a'); | |
571 | assert!(d == ['a']); | |
572 | ||
573 | let mut d = VecDeque::new(); | |
574 | d.push_back('a'); | |
575 | d.push_back('b'); | |
576 | assert!(d == ['a', 'b']); | |
577 | } | |
578 | ||
c34b1796 AL |
579 | #[test] |
580 | fn test_hash() { | |
3157f602 XL |
581 | let mut x = VecDeque::new(); |
582 | let mut y = VecDeque::new(); | |
c34b1796 | 583 | |
3157f602 XL |
584 | x.push_back(1); |
585 | x.push_back(2); | |
586 | x.push_back(3); | |
c34b1796 | 587 | |
3157f602 XL |
588 | y.push_back(0); |
589 | y.push_back(1); | |
590 | y.pop_front(); | |
591 | y.push_back(2); | |
592 | y.push_back(3); | |
c34b1796 | 593 | |
3157f602 | 594 | assert!(::hash(&x) == ::hash(&y)); |
c34b1796 AL |
595 | } |
596 | ||
7453a54e SL |
597 | #[test] |
598 | fn test_hash_after_rotation() { | |
599 | // test that two deques hash equal even if elements are laid out differently | |
600 | let len = 28; | |
601 | let mut ring: VecDeque<i32> = (0..len as i32).collect(); | |
602 | let orig = ring.clone(); | |
603 | for _ in 0..ring.capacity() { | |
604 | // shift values 1 step to the right by pop, sub one, push | |
605 | ring.pop_front(); | |
606 | for elt in &mut ring { | |
607 | *elt -= 1; | |
608 | } | |
609 | ring.push_back(len - 1); | |
610 | assert_eq!(::hash(&orig), ::hash(&ring)); | |
611 | assert_eq!(orig, ring); | |
612 | assert_eq!(ring, orig); | |
613 | } | |
614 | } | |
615 | ||
616 | #[test] | |
617 | fn test_eq_after_rotation() { | |
618 | // test that two deques are equal even if elements are laid out differently | |
619 | let len = 28; | |
620 | let mut ring: VecDeque<i32> = (0..len as i32).collect(); | |
621 | let mut shifted = ring.clone(); | |
622 | for _ in 0..10 { | |
623 | // shift values 1 step to the right by pop, sub one, push | |
624 | ring.pop_front(); | |
625 | for elt in &mut ring { | |
626 | *elt -= 1; | |
627 | } | |
628 | ring.push_back(len - 1); | |
629 | } | |
630 | ||
631 | // try every shift | |
632 | for _ in 0..shifted.capacity() { | |
633 | shifted.pop_front(); | |
634 | for elt in &mut shifted { | |
635 | *elt -= 1; | |
636 | } | |
637 | shifted.push_back(len - 1); | |
638 | assert_eq!(shifted, ring); | |
639 | assert_eq!(ring, shifted); | |
640 | } | |
641 | } | |
642 | ||
c34b1796 AL |
643 | #[test] |
644 | fn test_ord() { | |
645 | let x = VecDeque::new(); | |
646 | let mut y = VecDeque::new(); | |
647 | y.push_back(1); | |
648 | y.push_back(2); | |
649 | y.push_back(3); | |
650 | assert!(x < y); | |
651 | assert!(y > x); | |
652 | assert!(x <= x); | |
653 | assert!(x >= x); | |
654 | } | |
655 | ||
656 | #[test] | |
657 | fn test_show() { | |
658 | let ringbuf: VecDeque<_> = (0..10).collect(); | |
659 | assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); | |
660 | ||
3157f602 | 661 | let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"] |
c30ab7b3 SL |
662 | .iter() |
663 | .cloned() | |
664 | .collect(); | |
3157f602 XL |
665 | assert_eq!(format!("{:?}", ringbuf), |
666 | "[\"just\", \"one\", \"test\", \"more\"]"); | |
c34b1796 AL |
667 | } |
668 | ||
669 | #[test] | |
670 | fn test_drop() { | |
c30ab7b3 | 671 | static mut DROPS: i32 = 0; |
c34b1796 AL |
672 | struct Elem; |
673 | impl Drop for Elem { | |
674 | fn drop(&mut self) { | |
3157f602 | 675 | unsafe { |
c30ab7b3 | 676 | DROPS += 1; |
3157f602 | 677 | } |
c34b1796 AL |
678 | } |
679 | } | |
680 | ||
681 | let mut ring = VecDeque::new(); | |
682 | ring.push_back(Elem); | |
683 | ring.push_front(Elem); | |
684 | ring.push_back(Elem); | |
685 | ring.push_front(Elem); | |
686 | drop(ring); | |
687 | ||
c30ab7b3 | 688 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
689 | } |
690 | ||
691 | #[test] | |
692 | fn test_drop_with_pop() { | |
c30ab7b3 | 693 | static mut DROPS: i32 = 0; |
c34b1796 AL |
694 | struct Elem; |
695 | impl Drop for Elem { | |
696 | fn drop(&mut self) { | |
3157f602 | 697 | unsafe { |
c30ab7b3 | 698 | DROPS += 1; |
3157f602 | 699 | } |
c34b1796 AL |
700 | } |
701 | } | |
702 | ||
703 | let mut ring = VecDeque::new(); | |
704 | ring.push_back(Elem); | |
705 | ring.push_front(Elem); | |
706 | ring.push_back(Elem); | |
707 | ring.push_front(Elem); | |
708 | ||
709 | drop(ring.pop_back()); | |
710 | drop(ring.pop_front()); | |
c30ab7b3 | 711 | assert_eq!(unsafe { DROPS }, 2); |
c34b1796 AL |
712 | |
713 | drop(ring); | |
c30ab7b3 | 714 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
715 | } |
716 | ||
717 | #[test] | |
718 | fn test_drop_clear() { | |
c30ab7b3 | 719 | static mut DROPS: i32 = 0; |
c34b1796 AL |
720 | struct Elem; |
721 | impl Drop for Elem { | |
722 | fn drop(&mut self) { | |
3157f602 | 723 | unsafe { |
c30ab7b3 | 724 | DROPS += 1; |
3157f602 | 725 | } |
c34b1796 AL |
726 | } |
727 | } | |
728 | ||
729 | let mut ring = VecDeque::new(); | |
730 | ring.push_back(Elem); | |
731 | ring.push_front(Elem); | |
732 | ring.push_back(Elem); | |
733 | ring.push_front(Elem); | |
734 | ring.clear(); | |
c30ab7b3 | 735 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
736 | |
737 | drop(ring); | |
c30ab7b3 | 738 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
739 | } |
740 | ||
741 | #[test] | |
742 | fn test_reserve_grow() { | |
743 | // test growth path A | |
744 | // [T o o H] -> [T o o H . . . . ] | |
745 | let mut ring = VecDeque::with_capacity(4); | |
746 | for i in 0..3 { | |
747 | ring.push_back(i); | |
748 | } | |
749 | ring.reserve(7); | |
750 | for i in 0..3 { | |
751 | assert_eq!(ring.pop_front(), Some(i)); | |
752 | } | |
753 | ||
754 | // test growth path B | |
755 | // [H T o o] -> [. T o o H . . . ] | |
756 | let mut ring = VecDeque::with_capacity(4); | |
757 | for i in 0..1 { | |
758 | ring.push_back(i); | |
759 | assert_eq!(ring.pop_front(), Some(i)); | |
760 | } | |
761 | for i in 0..3 { | |
762 | ring.push_back(i); | |
763 | } | |
764 | ring.reserve(7); | |
765 | for i in 0..3 { | |
766 | assert_eq!(ring.pop_front(), Some(i)); | |
767 | } | |
768 | ||
769 | // test growth path C | |
770 | // [o o H T] -> [o o H . . . . T ] | |
771 | let mut ring = VecDeque::with_capacity(4); | |
772 | for i in 0..3 { | |
773 | ring.push_back(i); | |
774 | assert_eq!(ring.pop_front(), Some(i)); | |
775 | } | |
776 | for i in 0..3 { | |
777 | ring.push_back(i); | |
778 | } | |
779 | ring.reserve(7); | |
780 | for i in 0..3 { | |
781 | assert_eq!(ring.pop_front(), Some(i)); | |
782 | } | |
783 | } | |
784 | ||
785 | #[test] | |
786 | fn test_get() { | |
787 | let mut ring = VecDeque::new(); | |
788 | ring.push_back(0); | |
789 | assert_eq!(ring.get(0), Some(&0)); | |
790 | assert_eq!(ring.get(1), None); | |
791 | ||
792 | ring.push_back(1); | |
793 | assert_eq!(ring.get(0), Some(&0)); | |
794 | assert_eq!(ring.get(1), Some(&1)); | |
795 | assert_eq!(ring.get(2), None); | |
796 | ||
797 | ring.push_back(2); | |
798 | assert_eq!(ring.get(0), Some(&0)); | |
799 | assert_eq!(ring.get(1), Some(&1)); | |
800 | assert_eq!(ring.get(2), Some(&2)); | |
801 | assert_eq!(ring.get(3), None); | |
802 | ||
803 | assert_eq!(ring.pop_front(), Some(0)); | |
804 | assert_eq!(ring.get(0), Some(&1)); | |
805 | assert_eq!(ring.get(1), Some(&2)); | |
806 | assert_eq!(ring.get(2), None); | |
807 | ||
808 | assert_eq!(ring.pop_front(), Some(1)); | |
809 | assert_eq!(ring.get(0), Some(&2)); | |
810 | assert_eq!(ring.get(1), None); | |
811 | ||
812 | assert_eq!(ring.pop_front(), Some(2)); | |
813 | assert_eq!(ring.get(0), None); | |
814 | assert_eq!(ring.get(1), None); | |
815 | } | |
816 | ||
817 | #[test] | |
818 | fn test_get_mut() { | |
819 | let mut ring = VecDeque::new(); | |
820 | for i in 0..3 { | |
821 | ring.push_back(i); | |
822 | } | |
823 | ||
824 | match ring.get_mut(1) { | |
825 | Some(x) => *x = -1, | |
3157f602 | 826 | None => (), |
c34b1796 AL |
827 | }; |
828 | ||
829 | assert_eq!(ring.get_mut(0), Some(&mut 0)); | |
830 | assert_eq!(ring.get_mut(1), Some(&mut -1)); | |
831 | assert_eq!(ring.get_mut(2), Some(&mut 2)); | |
832 | assert_eq!(ring.get_mut(3), None); | |
833 | ||
834 | assert_eq!(ring.pop_front(), Some(0)); | |
835 | assert_eq!(ring.get_mut(0), Some(&mut -1)); | |
836 | assert_eq!(ring.get_mut(1), Some(&mut 2)); | |
837 | assert_eq!(ring.get_mut(2), None); | |
838 | } | |
839 | ||
840 | #[test] | |
841 | fn test_front() { | |
842 | let mut ring = VecDeque::new(); | |
843 | ring.push_back(10); | |
844 | ring.push_back(20); | |
845 | assert_eq!(ring.front(), Some(&10)); | |
846 | ring.pop_front(); | |
847 | assert_eq!(ring.front(), Some(&20)); | |
848 | ring.pop_front(); | |
849 | assert_eq!(ring.front(), None); | |
850 | } | |
851 | ||
852 | #[test] | |
853 | fn test_as_slices() { | |
854 | let mut ring: VecDeque<i32> = VecDeque::with_capacity(127); | |
855 | let cap = ring.capacity() as i32; | |
3157f602 XL |
856 | let first = cap / 2; |
857 | let last = cap - first; | |
c34b1796 AL |
858 | for i in 0..first { |
859 | ring.push_back(i); | |
860 | ||
861 | let (left, right) = ring.as_slices(); | |
3157f602 | 862 | let expected: Vec<_> = (0..i + 1).collect(); |
c34b1796 AL |
863 | assert_eq!(left, &expected[..]); |
864 | assert_eq!(right, []); | |
865 | } | |
866 | ||
867 | for j in -last..0 { | |
868 | ring.push_front(j); | |
869 | let (left, right) = ring.as_slices(); | |
3157f602 | 870 | let expected_left: Vec<_> = (-last..j + 1).rev().collect(); |
c34b1796 AL |
871 | let expected_right: Vec<_> = (0..first).collect(); |
872 | assert_eq!(left, &expected_left[..]); | |
873 | assert_eq!(right, &expected_right[..]); | |
874 | } | |
875 | ||
876 | assert_eq!(ring.len() as i32, cap); | |
877 | assert_eq!(ring.capacity() as i32, cap); | |
878 | } | |
879 | ||
880 | #[test] | |
881 | fn test_as_mut_slices() { | |
882 | let mut ring: VecDeque<i32> = VecDeque::with_capacity(127); | |
883 | let cap = ring.capacity() as i32; | |
3157f602 XL |
884 | let first = cap / 2; |
885 | let last = cap - first; | |
c34b1796 AL |
886 | for i in 0..first { |
887 | ring.push_back(i); | |
888 | ||
889 | let (left, right) = ring.as_mut_slices(); | |
3157f602 | 890 | let expected: Vec<_> = (0..i + 1).collect(); |
c34b1796 AL |
891 | assert_eq!(left, &expected[..]); |
892 | assert_eq!(right, []); | |
893 | } | |
894 | ||
895 | for j in -last..0 { | |
896 | ring.push_front(j); | |
897 | let (left, right) = ring.as_mut_slices(); | |
3157f602 | 898 | let expected_left: Vec<_> = (-last..j + 1).rev().collect(); |
c34b1796 AL |
899 | let expected_right: Vec<_> = (0..first).collect(); |
900 | assert_eq!(left, &expected_left[..]); | |
901 | assert_eq!(right, &expected_right[..]); | |
902 | } | |
903 | ||
904 | assert_eq!(ring.len() as i32, cap); | |
905 | assert_eq!(ring.capacity() as i32, cap); | |
906 | } | |
907 | ||
908 | #[test] | |
909 | fn test_append() { | |
910 | let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); | |
911 | let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect(); | |
912 | ||
913 | // normal append | |
914 | a.append(&mut b); | |
915 | assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]); | |
916 | assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []); | |
917 | ||
918 | // append nothing to something | |
919 | a.append(&mut b); | |
920 | assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]); | |
921 | assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []); | |
922 | ||
923 | // append something to nothing | |
924 | b.append(&mut a); | |
925 | assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]); | |
926 | assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []); | |
927 | } | |
d9579d0f AL |
928 | |
929 | #[test] | |
930 | fn test_retain() { | |
931 | let mut buf = VecDeque::new(); | |
932 | buf.extend(1..5); | |
933 | buf.retain(|&x| x % 2 == 0); | |
934 | let v: Vec<_> = buf.into_iter().collect(); | |
935 | assert_eq!(&v[..], &[2, 4]); | |
936 | } | |
62682a34 SL |
937 | |
938 | #[test] | |
939 | fn test_extend_ref() { | |
940 | let mut v = VecDeque::new(); | |
941 | v.push_back(1); | |
942 | v.extend(&[2, 3, 4]); | |
943 | ||
944 | assert_eq!(v.len(), 4); | |
945 | assert_eq!(v[0], 1); | |
946 | assert_eq!(v[1], 2); | |
947 | assert_eq!(v[2], 3); | |
948 | assert_eq!(v[3], 4); | |
949 | ||
950 | let mut w = VecDeque::new(); | |
951 | w.push_back(5); | |
952 | w.push_back(6); | |
953 | v.extend(&w); | |
954 | ||
955 | assert_eq!(v.len(), 6); | |
956 | assert_eq!(v[0], 1); | |
957 | assert_eq!(v[1], 2); | |
958 | assert_eq!(v[2], 3); | |
959 | assert_eq!(v[3], 4); | |
960 | assert_eq!(v[4], 5); | |
961 | assert_eq!(v[5], 6); | |
962 | } | |
a7813a04 XL |
963 | |
964 | #[test] | |
965 | fn test_contains() { | |
966 | let mut v = VecDeque::new(); | |
967 | v.extend(&[2, 3, 4]); | |
968 | ||
969 | assert!(v.contains(&3)); | |
970 | assert!(!v.contains(&1)); | |
971 | ||
972 | v.clear(); | |
973 | ||
974 | assert!(!v.contains(&3)); | |
975 | } | |
9e0c209e SL |
976 | |
977 | #[allow(dead_code)] | |
978 | fn assert_covariance() { | |
c30ab7b3 SL |
979 | fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { |
980 | d | |
981 | } | |
9e0c209e | 982 | } |
476ff2be SL |
983 | |
984 | #[test] | |
985 | fn test_is_empty() { | |
986 | let mut v = VecDeque::<i32>::new(); | |
987 | assert!(v.is_empty()); | |
988 | assert!(v.iter().is_empty()); | |
989 | assert!(v.iter_mut().is_empty()); | |
990 | v.extend(&[2, 3, 4]); | |
991 | assert!(!v.is_empty()); | |
992 | assert!(!v.iter().is_empty()); | |
993 | assert!(!v.iter_mut().is_empty()); | |
994 | while let Some(_) = v.pop_front() { | |
995 | assert_eq!(v.is_empty(), v.len() == 0); | |
996 | assert_eq!(v.iter().is_empty(), v.iter().len() == 0); | |
997 | assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0); | |
998 | } | |
999 | assert!(v.is_empty()); | |
1000 | assert!(v.iter().is_empty()); | |
1001 | assert!(v.iter_mut().is_empty()); | |
1002 | assert!(v.into_iter().is_empty()); | |
1003 | } | |
8bb4bdeb XL |
1004 | |
1005 | #[test] | |
1006 | fn test_placement_in() { | |
1007 | let mut buf: VecDeque<isize> = VecDeque::new(); | |
1008 | buf.place_back() <- 1; | |
1009 | buf.place_back() <- 2; | |
1010 | assert_eq!(buf, [1,2]); | |
1011 | ||
1012 | buf.place_front() <- 3; | |
1013 | buf.place_front() <- 4; | |
1014 | assert_eq!(buf, [4,3,1,2]); | |
1015 | ||
1016 | { | |
1017 | let ptr_head = buf.place_front() <- 5; | |
1018 | assert_eq!(*ptr_head, 5); | |
1019 | } | |
1020 | { | |
1021 | let ptr_tail = buf.place_back() <- 6; | |
1022 | assert_eq!(*ptr_tail, 6); | |
1023 | } | |
1024 | assert_eq!(buf, [5,4,3,1,2,6]); | |
1025 | } |