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