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