1 // Copyright 2012-2015 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.
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.
11 use std::cmp::Ordering::{Equal, Greater, Less};
12 use std::default::Default;
13 use std::iter::RandomAccessIterator;
15 use std::__rand::{Rng, thread_rng};
17 use std::slice::ElementSwaps;
19 fn square(n: usize) -> usize { n * n }
21 fn is_odd(n: &usize) -> bool { *n % 2 == 1 }
25 // Test on-stack from_fn.
26 let mut v: Vec<_> = (0..3).map(square).collect();
29 assert_eq!(v.len(), 3);
35 // Test on-heap from_fn.
36 v = (0..5).map(square).collect();
39 assert_eq!(v.len(), 5);
50 // Test on-stack from_elem.
51 let mut v = vec![10, 10];
54 assert_eq!(v.len(), 2);
59 // Test on-heap from_elem.
74 let xs: [i32; 0] = [];
75 assert!(xs.is_empty());
76 assert!(![0].is_empty());
80 fn test_len_divzero() {
83 let v1 : &[Z] = &[[]];
84 let v2 : &[Z] = &[[], []];
85 assert_eq!(mem::size_of::<Z>(), 0);
86 assert_eq!(v0.len(), 0);
87 assert_eq!(v1.len(), 1);
88 assert_eq!(v2.len(), 2);
94 assert_eq!(a.get(1), None);
96 assert_eq!(a.get(1).unwrap(), &12);
98 assert_eq!(a.get(1).unwrap(), &12);
104 assert_eq!(a.first(), None);
106 assert_eq!(a.first().unwrap(), &11);
108 assert_eq!(a.first().unwrap(), &11);
112 fn test_first_mut() {
114 assert_eq!(a.first_mut(), None);
116 assert_eq!(*a.first_mut().unwrap(), 11);
118 assert_eq!(*a.first_mut().unwrap(), 11);
122 fn test_split_first() {
123 let mut a = vec![11];
125 assert!(b.split_first().is_none());
126 assert_eq!(a.split_first(), Some((&11, b)));
128 let b: &[i32] = &[12];
129 assert_eq!(a.split_first(), Some((&11, b)));
133 fn test_split_first_mut() {
134 let mut a = vec![11];
135 let b: &mut [i32] = &mut [];
136 assert!(b.split_first_mut().is_none());
137 assert!(a.split_first_mut() == Some((&mut 11, b)));
139 let b: &mut [_] = &mut [12];
140 assert!(a.split_first_mut() == Some((&mut 11, b)));
144 fn test_split_last() {
145 let mut a = vec![11];
147 assert!(b.split_last().is_none());
148 assert_eq!(a.split_last(), Some((&11, b)));
151 assert_eq!(a.split_last(), Some((&12, b)));
155 fn test_split_last_mut() {
156 let mut a = vec![11];
157 let b: &mut [i32] = &mut [];
158 assert!(b.split_last_mut().is_none());
159 assert!(a.split_last_mut() == Some((&mut 11, b)));
162 let b: &mut [_] = &mut [11];
163 assert!(a.split_last_mut() == Some((&mut 12, b)));
169 assert_eq!(a.last(), None);
171 assert_eq!(a.last().unwrap(), &11);
173 assert_eq!(a.last().unwrap(), &12);
179 assert_eq!(a.last_mut(), None);
181 assert_eq!(*a.last_mut().unwrap(), 11);
183 assert_eq!(*a.last_mut().unwrap(), 12);
188 // Test fixed length vector.
189 let vec_fixed = [1, 2, 3, 4];
190 let v_a = vec_fixed[1..vec_fixed.len()].to_vec();
191 assert_eq!(v_a.len(), 3);
193 assert_eq!(v_a[0], 2);
194 assert_eq!(v_a[1], 3);
195 assert_eq!(v_a[2], 4);
198 let vec_stack: &[_] = &[1, 2, 3];
199 let v_b = vec_stack[1..3].to_vec();
200 assert_eq!(v_b.len(), 2);
202 assert_eq!(v_b[0], 2);
203 assert_eq!(v_b[1], 3);
206 let vec_unique = vec![1, 2, 3, 4, 5, 6];
207 let v_d = vec_unique[1..6].to_vec();
208 assert_eq!(v_d.len(), 5);
210 assert_eq!(v_d[0], 2);
211 assert_eq!(v_d[1], 3);
212 assert_eq!(v_d[2], 4);
213 assert_eq!(v_d[3], 5);
214 assert_eq!(v_d[4], 6);
218 fn test_slice_from() {
219 let vec: &[_] = &[1, 2, 3, 4];
220 assert_eq!(&vec[..], vec);
221 let b: &[_] = &[3, 4];
222 assert_eq!(&vec[2..], b);
224 assert_eq!(&vec[4..], b);
229 let vec: &[_] = &[1, 2, 3, 4];
230 assert_eq!(&vec[..4], vec);
231 let b: &[_] = &[1, 2];
232 assert_eq!(&vec[..2], b);
234 assert_eq!(&vec[..0], b);
242 assert_eq!(v.len(), 0);
243 assert_eq!(e, Some(5));
251 fn test_swap_remove() {
252 let mut v = vec![1, 2, 3, 4, 5];
253 let mut e = v.swap_remove(0);
255 assert_eq!(v, [5, 2, 3, 4]);
256 e = v.swap_remove(3);
258 assert_eq!(v, [5, 2, 3]);
263 fn test_swap_remove_fail() {
265 let _ = v.swap_remove(0);
266 let _ = v.swap_remove(0);
270 fn test_swap_remove_noncopyable() {
271 // Tests that we don't accidentally run destructors twice.
272 let mut v: Vec<Box<_>> = Vec::new();
276 let mut _e = v.swap_remove(0);
277 assert_eq!(v.len(), 2);
278 _e = v.swap_remove(1);
279 assert_eq!(v.len(), 1);
280 _e = v.swap_remove(0);
281 assert_eq!(v.len(), 0);
286 // Test on-stack push().
289 assert_eq!(v.len(), 1);
292 // Test on-heap push().
294 assert_eq!(v.len(), 2);
301 let mut v: Vec<Box<_>> = vec![box 6,box 5,box 4];
304 assert_eq!(v.len(), 1);
305 assert_eq!(*(v[0]), 6);
306 // If the unsafe block didn't drop things properly, we blow up here.
311 let mut v: Vec<Box<_>> = vec![box 6,box 5,box 4];
313 assert_eq!(v.len(), 0);
314 // If the unsafe block didn't drop things properly, we blow up here.
319 fn case(a: Vec<i32>, b: Vec<i32>) {
324 case(vec![], vec![]);
325 case(vec![1], vec![1]);
326 case(vec![1,1], vec![1]);
327 case(vec![1,2,3], vec![1,2,3]);
328 case(vec![1,1,2,3], vec![1,2,3]);
329 case(vec![1,2,2,3], vec![1,2,3]);
330 case(vec![1,2,3,3], vec![1,2,3]);
331 case(vec![1,1,2,2,2,3,3], vec![1,2,3]);
335 fn test_dedup_unique() {
336 let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
338 let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
340 let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
343 * If the boxed pointers were leaked or otherwise misused, valgrind
344 * and/or rt should raise errors.
349 fn test_dedup_shared() {
350 let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
352 let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
354 let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
357 * If the pointers were leaked or otherwise misused, valgrind and/or
358 * rt should raise errors.
364 let mut v = vec![1, 2, 3, 4, 5];
366 assert_eq!(v, [1, 3, 5]);
370 fn test_element_swaps() {
371 let mut v = [1, 2, 3];
372 for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
375 0 => assert!(v == [1, 3, 2]),
376 1 => assert!(v == [3, 1, 2]),
377 2 => assert!(v == [3, 2, 1]),
378 3 => assert!(v == [2, 3, 1]),
379 4 => assert!(v == [2, 1, 3]),
380 5 => assert!(v == [1, 2, 3]),
387 fn test_lexicographic_permutations() {
388 let v : &mut[_] = &mut[1, 2, 3, 4, 5];
389 assert!(v.prev_permutation() == false);
390 assert!(v.next_permutation());
391 let b: &mut[_] = &mut[1, 2, 3, 5, 4];
393 assert!(v.prev_permutation());
394 let b: &mut[_] = &mut[1, 2, 3, 4, 5];
396 assert!(v.next_permutation());
397 assert!(v.next_permutation());
398 let b: &mut[_] = &mut[1, 2, 4, 3, 5];
400 assert!(v.next_permutation());
401 let b: &mut[_] = &mut[1, 2, 4, 5, 3];
404 let v : &mut[_] = &mut[1, 0, 0, 0];
405 assert!(v.next_permutation() == false);
406 assert!(v.prev_permutation());
407 let b: &mut[_] = &mut[0, 1, 0, 0];
409 assert!(v.prev_permutation());
410 let b: &mut[_] = &mut[0, 0, 1, 0];
412 assert!(v.prev_permutation());
413 let b: &mut[_] = &mut[0, 0, 0, 1];
415 assert!(v.prev_permutation() == false);
419 fn test_lexicographic_permutations_empty_and_short() {
420 let empty : &mut[i32] = &mut[];
421 assert!(empty.next_permutation() == false);
422 let b: &mut[i32] = &mut[];
424 assert!(empty.prev_permutation() == false);
427 let one_elem : &mut[_] = &mut[4];
428 assert!(one_elem.prev_permutation() == false);
429 let b: &mut[_] = &mut[4];
430 assert!(one_elem == b);
431 assert!(one_elem.next_permutation() == false);
432 assert!(one_elem == b);
434 let two_elem : &mut[_] = &mut[1, 2];
435 assert!(two_elem.prev_permutation() == false);
436 let b : &mut[_] = &mut[1, 2];
437 let c : &mut[_] = &mut[2, 1];
438 assert!(two_elem == b);
439 assert!(two_elem.next_permutation());
440 assert!(two_elem == c);
441 assert!(two_elem.next_permutation() == false);
442 assert!(two_elem == c);
443 assert!(two_elem.prev_permutation());
444 assert!(two_elem == b);
445 assert!(two_elem.prev_permutation() == false);
446 assert!(two_elem == b);
450 fn test_position_elem() {
451 assert!([].position_elem(&1).is_none());
453 let v1 = vec![1, 2, 3, 3, 2, 5];
454 assert_eq!(v1.position_elem(&1), Some(0));
455 assert_eq!(v1.position_elem(&2), Some(1));
456 assert_eq!(v1.position_elem(&5), Some(5));
457 assert!(v1.position_elem(&4).is_none());
461 fn test_binary_search() {
462 assert_eq!([1,2,3,4,5].binary_search(&5).ok(), Some(4));
463 assert_eq!([1,2,3,4,5].binary_search(&4).ok(), Some(3));
464 assert_eq!([1,2,3,4,5].binary_search(&3).ok(), Some(2));
465 assert_eq!([1,2,3,4,5].binary_search(&2).ok(), Some(1));
466 assert_eq!([1,2,3,4,5].binary_search(&1).ok(), Some(0));
468 assert_eq!([2,4,6,8,10].binary_search(&1).ok(), None);
469 assert_eq!([2,4,6,8,10].binary_search(&5).ok(), None);
470 assert_eq!([2,4,6,8,10].binary_search(&4).ok(), Some(1));
471 assert_eq!([2,4,6,8,10].binary_search(&10).ok(), Some(4));
473 assert_eq!([2,4,6,8].binary_search(&1).ok(), None);
474 assert_eq!([2,4,6,8].binary_search(&5).ok(), None);
475 assert_eq!([2,4,6,8].binary_search(&4).ok(), Some(1));
476 assert_eq!([2,4,6,8].binary_search(&8).ok(), Some(3));
478 assert_eq!([2,4,6].binary_search(&1).ok(), None);
479 assert_eq!([2,4,6].binary_search(&5).ok(), None);
480 assert_eq!([2,4,6].binary_search(&4).ok(), Some(1));
481 assert_eq!([2,4,6].binary_search(&6).ok(), Some(2));
483 assert_eq!([2,4].binary_search(&1).ok(), None);
484 assert_eq!([2,4].binary_search(&5).ok(), None);
485 assert_eq!([2,4].binary_search(&2).ok(), Some(0));
486 assert_eq!([2,4].binary_search(&4).ok(), Some(1));
488 assert_eq!([2].binary_search(&1).ok(), None);
489 assert_eq!([2].binary_search(&5).ok(), None);
490 assert_eq!([2].binary_search(&2).ok(), Some(0));
492 assert_eq!([].binary_search(&1).ok(), None);
493 assert_eq!([].binary_search(&5).ok(), None);
495 assert!([1,1,1,1,1].binary_search(&1).ok() != None);
496 assert!([1,1,1,1,2].binary_search(&1).ok() != None);
497 assert!([1,1,1,2,2].binary_search(&1).ok() != None);
498 assert!([1,1,2,2,2].binary_search(&1).ok() != None);
499 assert_eq!([1,2,2,2,2].binary_search(&1).ok(), Some(0));
501 assert_eq!([1,2,3,4,5].binary_search(&6).ok(), None);
502 assert_eq!([1,2,3,4,5].binary_search(&0).ok(), None);
507 let mut v = vec![10, 20];
508 assert_eq!(v[0], 10);
509 assert_eq!(v[1], 20);
511 assert_eq!(v[0], 20);
512 assert_eq!(v[1], 10);
514 let mut v3 = Vec::<i32>::new();
516 assert!(v3.is_empty());
523 let mut v: Vec<_> = thread_rng().gen_iter::<i32>().take(len).collect();
524 let mut v1 = v.clone();
527 assert!(v.windows(2).all(|w| w[0] <= w[1]));
529 v1.sort_by(|a, b| a.cmp(b));
530 assert!(v1.windows(2).all(|w| w[0] <= w[1]));
532 v1.sort_by(|a, b| b.cmp(a));
533 assert!(v1.windows(2).all(|w| w[0] >= w[1]));
538 let mut v: [i32; 0] = [];
541 let mut v = [0xDEADBEEFu64];
543 assert!(v == [0xDEADBEEF]);
547 fn test_sort_stability() {
550 let mut counts = [0; 10];
552 // create a vector like [(6, 1), (5, 1), (6, 2), ...],
553 // where the first item of each tuple is random, but
554 // the second item represents which occurrence of that
555 // number this element is, i.e. the second elements
556 // will occur in sorted order.
557 let mut v: Vec<_> = (0..len).map(|_| {
558 let n = thread_rng().gen::<usize>() % 10;
563 // only sort on the first element, so an unstable sort
564 // may mix up the counts.
565 v.sort_by(|&(a,_), &(b,_)| a.cmp(&b));
567 // this comparison includes the count (the second item
568 // of the tuple), so elements with equal first items
569 // will need to be ordered with increasing
570 // counts... i.e. exactly asserting that this sort is
572 assert!(v.windows(2).all(|w| w[0] <= w[1]));
579 let v: [Vec<i32>; 0] = [];
582 let d = [vec![1], vec![2, 3]].concat();
583 assert_eq!(d, [1, 2, 3]);
585 let v: &[&[_]] = &[&[1], &[2, 3]];
586 assert_eq!(v.join(&0), [1, 0, 2, 3]);
587 let v: &[&[_]] = &[&[1], &[2], &[3]];
588 assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
593 let v: [Vec<i32>; 0] = [];
594 assert_eq!(v.join(&0), []);
595 assert_eq!([vec![1], vec![2, 3]].join(&0), [1, 0, 2, 3]);
596 assert_eq!([vec![1], vec![2], vec![3]].join(&0), [1, 0, 2, 0, 3]);
598 let v: [&[_]; 2] = [&[1], &[2, 3]];
599 assert_eq!(v.join(&0), [1, 0, 2, 3]);
600 let v: [&[_]; 3] = [&[1], &[2], &[3]];
601 assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
606 let mut a = vec![1, 2, 4];
608 assert_eq!(a, [1, 2, 3, 4]);
610 let mut a = vec![1, 2, 3];
612 assert_eq!(a, [0, 1, 2, 3]);
614 let mut a = vec![1, 2, 3];
616 assert_eq!(a, [1, 2, 3, 4]);
625 fn test_insert_oob() {
626 let mut a = vec![1, 2, 3];
632 let mut a = vec![1, 2, 3, 4];
634 assert_eq!(a.remove(2), 3);
635 assert_eq!(a, [1, 2, 4]);
637 assert_eq!(a.remove(2), 4);
638 assert_eq!(a, [1, 2]);
640 assert_eq!(a.remove(0), 1);
643 assert_eq!(a.remove(0), 2);
649 fn test_remove_fail() {
659 assert!(v.capacity() >= 11);
664 let v = vec![1, 2, 3, 4, 5];
666 assert_eq!(v.len(), 2);
673 fn test_permute_fail() {
674 let v: [(Box<_>, Rc<_>); 4] =
675 [(box 0, Rc::new(0)), (box 0, Rc::new(0)),
676 (box 0, Rc::new(0)), (box 0, Rc::new(0))];
678 for _ in v.permutations() {
687 fn test_total_ord() {
689 [1, 2, 3, 4][..].cmp(c) == Greater;
690 let c = &[1, 2, 3, 4];
691 [1, 2, 3][..].cmp(c) == Less;
692 let c = &[1, 2, 3, 6];
693 [1, 2, 3, 4][..].cmp(c) == Equal;
694 let c = &[1, 2, 3, 4, 5, 6];
695 [1, 2, 3, 4, 5, 5, 5, 5][..].cmp(c) == Less;
696 let c = &[1, 2, 3, 4];
697 [2, 2][..].cmp(c) == Greater;
702 let xs = [1, 2, 5, 10, 11];
703 let mut it = xs.iter();
704 assert_eq!(it.size_hint(), (5, Some(5)));
705 assert_eq!(it.next().unwrap(), &1);
706 assert_eq!(it.size_hint(), (4, Some(4)));
707 assert_eq!(it.next().unwrap(), &2);
708 assert_eq!(it.size_hint(), (3, Some(3)));
709 assert_eq!(it.next().unwrap(), &5);
710 assert_eq!(it.size_hint(), (2, Some(2)));
711 assert_eq!(it.next().unwrap(), &10);
712 assert_eq!(it.size_hint(), (1, Some(1)));
713 assert_eq!(it.next().unwrap(), &11);
714 assert_eq!(it.size_hint(), (0, Some(0)));
715 assert!(it.next().is_none());
719 fn test_random_access_iterator() {
720 let xs = [1, 2, 5, 10, 11];
721 let mut it = xs.iter();
723 assert_eq!(it.indexable(), 5);
724 assert_eq!(it.idx(0).unwrap(), &1);
725 assert_eq!(it.idx(2).unwrap(), &5);
726 assert_eq!(it.idx(4).unwrap(), &11);
727 assert!(it.idx(5).is_none());
729 assert_eq!(it.next().unwrap(), &1);
730 assert_eq!(it.indexable(), 4);
731 assert_eq!(it.idx(0).unwrap(), &2);
732 assert_eq!(it.idx(3).unwrap(), &11);
733 assert!(it.idx(4).is_none());
735 assert_eq!(it.next().unwrap(), &2);
736 assert_eq!(it.indexable(), 3);
737 assert_eq!(it.idx(1).unwrap(), &10);
738 assert!(it.idx(3).is_none());
740 assert_eq!(it.next().unwrap(), &5);
741 assert_eq!(it.indexable(), 2);
742 assert_eq!(it.idx(1).unwrap(), &11);
744 assert_eq!(it.next().unwrap(), &10);
745 assert_eq!(it.indexable(), 1);
746 assert_eq!(it.idx(0).unwrap(), &11);
747 assert!(it.idx(1).is_none());
749 assert_eq!(it.next().unwrap(), &11);
750 assert_eq!(it.indexable(), 0);
751 assert!(it.idx(0).is_none());
753 assert!(it.next().is_none());
757 fn test_iter_size_hints() {
758 let mut xs = [1, 2, 5, 10, 11];
759 assert_eq!(xs.iter().size_hint(), (5, Some(5)));
760 assert_eq!(xs.iter_mut().size_hint(), (5, Some(5)));
764 fn test_iter_clone() {
766 let mut it = xs.iter();
768 let mut jt = it.clone();
769 assert_eq!(it.next(), jt.next());
770 assert_eq!(it.next(), jt.next());
771 assert_eq!(it.next(), jt.next());
775 fn test_mut_iterator() {
776 let mut xs = [1, 2, 3, 4, 5];
780 assert!(xs == [2, 3, 4, 5, 6])
784 fn test_rev_iterator() {
786 let xs = [1, 2, 5, 10, 11];
787 let ys = [11, 10, 5, 2, 1];
789 for &x in xs.iter().rev() {
790 assert_eq!(x, ys[i]);
797 fn test_mut_rev_iterator() {
798 let mut xs = [1, 2, 3, 4, 5];
799 for (i,x) in xs.iter_mut().rev().enumerate() {
802 assert!(xs == [5, 5, 5, 5, 5])
806 fn test_move_iterator() {
807 let xs = vec![1,2,3,4,5];
808 assert_eq!(xs.into_iter().fold(0, |a: usize, b: usize| 10*a + b), 12345);
812 fn test_move_rev_iterator() {
813 let xs = vec![1,2,3,4,5];
814 assert_eq!(xs.into_iter().rev().fold(0, |a: usize, b: usize| 10*a + b), 54321);
818 fn test_splitator() {
819 let xs = &[1,2,3,4,5];
821 let splits: &[&[_]] = &[&[1], &[3], &[5]];
822 assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<_>>(),
824 let splits: &[&[_]] = &[&[], &[2,3,4,5]];
825 assert_eq!(xs.split(|x| *x == 1).collect::<Vec<_>>(),
827 let splits: &[&[_]] = &[&[1,2,3,4], &[]];
828 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<_>>(),
830 let splits: &[&[_]] = &[&[1,2,3,4,5]];
831 assert_eq!(xs.split(|x| *x == 10).collect::<Vec<_>>(),
833 let splits: &[&[_]] = &[&[], &[], &[], &[], &[], &[]];
834 assert_eq!(xs.split(|_| true).collect::<Vec<&[i32]>>(),
837 let xs: &[i32] = &[];
838 let splits: &[&[i32]] = &[&[]];
839 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[i32]>>(), splits);
843 fn test_splitnator() {
844 let xs = &[1,2,3,4,5];
846 let splits: &[&[_]] = &[&[1,2,3,4,5]];
847 assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
849 let splits: &[&[_]] = &[&[1], &[3,4,5]];
850 assert_eq!(xs.splitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
852 let splits: &[&[_]] = &[&[], &[], &[], &[4,5]];
853 assert_eq!(xs.splitn(4, |_| true).collect::<Vec<_>>(),
856 let xs: &[i32] = &[];
857 let splits: &[&[i32]] = &[&[]];
858 assert_eq!(xs.splitn(2, |x| *x == 5).collect::<Vec<_>>(), splits);
862 fn test_splitnator_mut() {
863 let xs = &mut [1,2,3,4,5];
865 let splits: &[&mut[_]] = &[&mut [1,2,3,4,5]];
866 assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
868 let splits: &[&mut[_]] = &[&mut [1], &mut [3,4,5]];
869 assert_eq!(xs.splitn_mut(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
871 let splits: &[&mut[_]] = &[&mut [], &mut [], &mut [], &mut [4,5]];
872 assert_eq!(xs.splitn_mut(4, |_| true).collect::<Vec<_>>(),
875 let xs: &mut [i32] = &mut [];
876 let splits: &[&mut[i32]] = &[&mut []];
877 assert_eq!(xs.splitn_mut(2, |x| *x == 5).collect::<Vec<_>>(),
882 fn test_rsplitator() {
883 let xs = &[1,2,3,4,5];
885 let splits: &[&[_]] = &[&[5], &[3], &[1]];
886 assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<_>>(),
888 let splits: &[&[_]] = &[&[2,3,4,5], &[]];
889 assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<_>>(),
891 let splits: &[&[_]] = &[&[], &[1,2,3,4]];
892 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<_>>(),
894 let splits: &[&[_]] = &[&[1,2,3,4,5]];
895 assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<_>>(),
898 let xs: &[i32] = &[];
899 let splits: &[&[i32]] = &[&[]];
900 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[i32]>>(), splits);
904 fn test_rsplitnator() {
905 let xs = &[1,2,3,4,5];
907 let splits: &[&[_]] = &[&[1,2,3,4,5]];
908 assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
910 let splits: &[&[_]] = &[&[5], &[1,2,3]];
911 assert_eq!(xs.rsplitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
913 let splits: &[&[_]] = &[&[], &[], &[], &[1,2]];
914 assert_eq!(xs.rsplitn(4, |_| true).collect::<Vec<_>>(),
917 let xs: &[i32] = &[];
918 let splits: &[&[i32]] = &[&[]];
919 assert_eq!(xs.rsplitn(2, |x| *x == 5).collect::<Vec<&[i32]>>(), splits);
920 assert!(xs.rsplitn(0, |x| *x % 2 == 0).next().is_none());
924 fn test_windowsator() {
927 let wins: &[&[_]] = &[&[1,2], &[2,3], &[3,4]];
928 assert_eq!(v.windows(2).collect::<Vec<_>>(), wins);
930 let wins: &[&[_]] = &[&[1,2,3], &[2,3,4]];
931 assert_eq!(v.windows(3).collect::<Vec<_>>(), wins);
932 assert!(v.windows(6).next().is_none());
934 let wins: &[&[_]] = &[&[3,4], &[2,3], &[1,2]];
935 assert_eq!(v.windows(2).rev().collect::<Vec<&[_]>>(), wins);
936 let mut it = v.windows(2);
937 assert_eq!(it.indexable(), 3);
938 let win: &[_] = &[1,2];
939 assert_eq!(it.idx(0).unwrap(), win);
940 let win: &[_] = &[2,3];
941 assert_eq!(it.idx(1).unwrap(), win);
942 let win: &[_] = &[3,4];
943 assert_eq!(it.idx(2).unwrap(), win);
944 assert_eq!(it.idx(3), None);
949 fn test_windowsator_0() {
951 let _it = v.windows(0);
955 fn test_chunksator() {
956 let v = &[1,2,3,4,5];
958 assert_eq!(v.chunks(2).len(), 3);
960 let chunks: &[&[_]] = &[&[1,2], &[3,4], &[5]];
961 assert_eq!(v.chunks(2).collect::<Vec<_>>(), chunks);
962 let chunks: &[&[_]] = &[&[1,2,3], &[4,5]];
963 assert_eq!(v.chunks(3).collect::<Vec<_>>(), chunks);
964 let chunks: &[&[_]] = &[&[1,2,3,4,5]];
965 assert_eq!(v.chunks(6).collect::<Vec<_>>(), chunks);
967 let chunks: &[&[_]] = &[&[5], &[3,4], &[1,2]];
968 assert_eq!(v.chunks(2).rev().collect::<Vec<_>>(), chunks);
969 let mut it = v.chunks(2);
970 assert_eq!(it.indexable(), 3);
972 let chunk: &[_] = &[1,2];
973 assert_eq!(it.idx(0).unwrap(), chunk);
974 let chunk: &[_] = &[3,4];
975 assert_eq!(it.idx(1).unwrap(), chunk);
976 let chunk: &[_] = &[5];
977 assert_eq!(it.idx(2).unwrap(), chunk);
978 assert_eq!(it.idx(3), None);
983 fn test_chunksator_0() {
985 let _it = v.chunks(0);
989 fn test_move_from() {
990 let mut a = [1,2,3,4,5];
992 assert_eq!(a.move_from(b, 0, 3), 3);
993 assert!(a == [6,7,8,4,5]);
994 let mut a = [7,2,8,1];
995 let b = vec![3,1,4,1,5,9];
996 assert_eq!(a.move_from(b, 0, 6), 4);
997 assert!(a == [3,1,4,1]);
998 let mut a = [1,2,3,4];
999 let b = vec![5,6,7,8,9,0];
1000 assert_eq!(a.move_from(b, 2, 3), 1);
1001 assert!(a == [7,2,3,4]);
1002 let mut a = [1,2,3,4,5];
1003 let b = vec![5,6,7,8,9,0];
1004 assert_eq!(a[2..4].move_from(b,1,6), 2);
1005 assert!(a == [1,2,6,7,5]);
1009 fn test_reverse_part() {
1010 let mut values = [1,2,3,4,5];
1011 values[1..4].reverse();
1012 assert!(values == [1,4,3,2,5]);
1017 macro_rules! test_show_vec {
1018 ($x:expr, $x_str:expr) => ({
1019 let (x, x_str) = ($x, $x_str);
1020 assert_eq!(format!("{:?}", x), x_str);
1021 assert_eq!(format!("{:?}", x), x_str);
1024 let empty = Vec::<i32>::new();
1025 test_show_vec!(empty, "[]");
1026 test_show_vec!(vec![1], "[1]");
1027 test_show_vec!(vec![1, 2, 3], "[1, 2, 3]");
1028 test_show_vec!(vec![vec![], vec![1], vec![1, 1]],
1029 "[[], [1], [1, 1]]");
1031 let empty_mut: &mut [i32] = &mut[];
1032 test_show_vec!(empty_mut, "[]");
1034 test_show_vec!(v, "[1]");
1035 let v = &mut[1, 2, 3];
1036 test_show_vec!(v, "[1, 2, 3]");
1037 let v: &mut[&mut[_]] = &mut[&mut[], &mut[1], &mut[1, 1]];
1038 test_show_vec!(v, "[[], [1], [1, 1]]");
1042 fn test_vec_default() {
1045 let v: $ty = Default::default();
1046 assert!(v.is_empty());
1055 fn test_bytes_set_memory() {
1056 use std::slice::bytes::MutableByteVector;
1058 let mut values = [1,2,3,4,5];
1059 values[0..5].set_memory(0xAB);
1060 assert!(values == [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
1061 values[2..4].set_memory(0xFF);
1062 assert!(values == [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
1067 fn test_overflow_does_not_cause_segfault() {
1069 v.reserve_exact(!0);
1076 fn test_overflow_does_not_cause_segfault_managed() {
1077 let mut v = vec![Rc::new(1)];
1078 v.reserve_exact(!0);
1083 fn test_mut_split_at() {
1084 let mut values = [1u8,2,3,4,5];
1086 let (left, right) = values.split_at_mut(2);
1088 let left: &[_] = left;
1089 assert!(left[..left.len()] == [1, 2]);
1096 let right: &[_] = right;
1097 assert!(right[..right.len()] == [3, 4, 5]);
1104 assert!(values == [2, 3, 5, 6, 7]);
1107 #[derive(Clone, PartialEq)]
1111 fn test_iter_zero_sized() {
1112 let mut v = vec![Foo, Foo, Foo];
1113 assert_eq!(v.len(), 3);
1138 assert_eq!(cnt, 11);
1140 let xs: [Foo; 3] = [Foo, Foo, Foo];
1150 fn test_shrink_to_fit() {
1151 let mut xs = vec![0, 1, 2, 3];
1155 assert_eq!(xs.capacity(), 128);
1157 assert_eq!(xs.capacity(), 100);
1158 assert_eq!(xs, (0..100).collect::<Vec<_>>());
1162 fn test_starts_with() {
1163 assert!(b"foobar".starts_with(b"foo"));
1164 assert!(!b"foobar".starts_with(b"oob"));
1165 assert!(!b"foobar".starts_with(b"bar"));
1166 assert!(!b"foo".starts_with(b"foobar"));
1167 assert!(!b"bar".starts_with(b"foobar"));
1168 assert!(b"foobar".starts_with(b"foobar"));
1169 let empty: &[u8] = &[];
1170 assert!(empty.starts_with(empty));
1171 assert!(!empty.starts_with(b"foo"));
1172 assert!(b"foobar".starts_with(empty));
1176 fn test_ends_with() {
1177 assert!(b"foobar".ends_with(b"bar"));
1178 assert!(!b"foobar".ends_with(b"oba"));
1179 assert!(!b"foobar".ends_with(b"foo"));
1180 assert!(!b"foo".ends_with(b"foobar"));
1181 assert!(!b"bar".ends_with(b"foobar"));
1182 assert!(b"foobar".ends_with(b"foobar"));
1183 let empty: &[u8] = &[];
1184 assert!(empty.ends_with(empty));
1185 assert!(!empty.ends_with(b"foo"));
1186 assert!(b"foobar".ends_with(empty));
1190 fn test_mut_splitator() {
1191 let mut xs = [0,1,0,2,3,0,0,4,5,0];
1192 assert_eq!(xs.split_mut(|x| *x == 0).count(), 6);
1193 for slice in xs.split_mut(|x| *x == 0) {
1196 assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
1198 let mut xs = [0,1,0,2,3,0,0,4,5,0,6,7];
1199 for slice in xs.split_mut(|x| *x == 0).take(5) {
1202 assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
1206 fn test_mut_splitator_rev() {
1207 let mut xs = [1,2,0,3,4,0,0,5,6,0];
1208 for slice in xs.split_mut(|x| *x == 0).rev().take(4) {
1211 assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
1216 let mut v = [0,1,2];
1217 assert_eq!(v.get_mut(3), None);
1218 v.get_mut(1).map(|e| *e = 7);
1219 assert_eq!(v[1], 7);
1221 assert_eq!(v.get_mut(2), Some(&mut x));
1225 fn test_mut_chunks() {
1226 let mut v = [0, 1, 2, 3, 4, 5, 6];
1227 assert_eq!(v.chunks_mut(2).len(), 4);
1228 for (i, chunk) in v.chunks_mut(3).enumerate() {
1233 let result = [0, 0, 0, 1, 1, 1, 2];
1234 assert!(v == result);
1238 fn test_mut_chunks_rev() {
1239 let mut v = [0, 1, 2, 3, 4, 5, 6];
1240 for (i, chunk) in v.chunks_mut(3).rev().enumerate() {
1245 let result = [2, 2, 2, 1, 1, 1, 0];
1246 assert!(v == result);
1251 fn test_mut_chunks_0() {
1252 let mut v = [1, 2, 3, 4];
1253 let _it = v.chunks_mut(0);
1257 fn test_mut_last() {
1258 let mut x = [1, 2, 3, 4, 5];
1259 let h = x.last_mut();
1260 assert_eq!(*h.unwrap(), 5);
1262 let y: &mut [i32] = &mut [];
1263 assert!(y.last_mut().is_none());
1268 let xs: Box<_> = box [1, 2, 3];
1269 let ys = xs.to_vec();
1270 assert_eq!(ys, [1, 2, 3]);
1274 use std::iter::repeat;
1275 use std::{mem, ptr};
1276 use std::__rand::{Rng, thread_rng};
1278 use test::{Bencher, black_box};
1281 fn iterator(b: &mut Bencher) {
1282 // peculiar numbers to stop LLVM from optimising the summation
1284 let v: Vec<_> = (0..100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect();
1291 // sum == 11806, to stop dead code elimination.
1292 if sum == 0 {panic!()}
1297 fn mut_iterator(b: &mut Bencher) {
1298 let mut v = vec![0; 100];
1310 fn concat(b: &mut Bencher) {
1311 let xss: Vec<Vec<i32>> =
1312 (0..100).map(|i| (0..i).collect()).collect();
1319 fn join(b: &mut Bencher) {
1320 let xss: Vec<Vec<i32>> =
1321 (0..100).map(|i| (0..i).collect()).collect();
1328 fn push(b: &mut Bencher) {
1329 let mut vec = Vec::<i32>::new();
1337 fn starts_with_same_vector(b: &mut Bencher) {
1338 let vec: Vec<_> = (0..100).collect();
1340 vec.starts_with(&vec)
1345 fn starts_with_single_element(b: &mut Bencher) {
1346 let vec: Vec<_> = vec![0];
1348 vec.starts_with(&vec)
1353 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
1354 let vec: Vec<_> = (0..100).collect();
1355 let mut match_vec: Vec<_> = (0..99).collect();
1358 vec.starts_with(&match_vec)
1363 fn ends_with_same_vector(b: &mut Bencher) {
1364 let vec: Vec<_> = (0..100).collect();
1371 fn ends_with_single_element(b: &mut Bencher) {
1372 let vec: Vec<_> = vec![0];
1379 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
1380 let vec: Vec<_> = (0..100).collect();
1381 let mut match_vec: Vec<_> = (0..100).collect();
1384 vec.starts_with(&match_vec)
1389 fn contains_last_element(b: &mut Bencher) {
1390 let vec: Vec<_> = (0..100).collect();
1397 fn zero_1kb_from_elem(b: &mut Bencher) {
1404 fn zero_1kb_set_memory(b: &mut Bencher) {
1406 let mut v = Vec::<u8>::with_capacity(1024);
1408 let vp = v.as_mut_ptr();
1409 ptr::write_bytes(vp, 0, 1024);
1417 fn zero_1kb_loop_set(b: &mut Bencher) {
1419 let mut v = Vec::<u8>::with_capacity(1024);
1430 fn zero_1kb_mut_iter(b: &mut Bencher) {
1432 let mut v = Vec::<u8>::with_capacity(1024);
1444 fn random_inserts(b: &mut Bencher) {
1445 let mut rng = thread_rng();
1447 let mut v = vec![(0, 0); 30];
1450 v.insert(rng.gen::<usize>() % (l + 1),
1456 fn random_removes(b: &mut Bencher) {
1457 let mut rng = thread_rng();
1459 let mut v = vec![(0, 0); 130];
1462 v.remove(rng.gen::<usize>() % l);
1468 fn sort_random_small(b: &mut Bencher) {
1469 let mut rng = thread_rng();
1471 let mut v: Vec<_> = rng.gen_iter::<u64>().take(5).collect();
1474 b.bytes = 5 * mem::size_of::<u64>() as u64;
1478 fn sort_random_medium(b: &mut Bencher) {
1479 let mut rng = thread_rng();
1481 let mut v: Vec<_> = rng.gen_iter::<u64>().take(100).collect();
1484 b.bytes = 100 * mem::size_of::<u64>() as u64;
1488 fn sort_random_large(b: &mut Bencher) {
1489 let mut rng = thread_rng();
1491 let mut v: Vec<_> = rng.gen_iter::<u64>().take(10000).collect();
1494 b.bytes = 10000 * mem::size_of::<u64>() as u64;
1498 fn sort_sorted(b: &mut Bencher) {
1499 let mut v: Vec<_> = (0..10000).collect();
1503 b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
1506 type BigSortable = (u64, u64, u64, u64);
1509 fn sort_big_random_small(b: &mut Bencher) {
1510 let mut rng = thread_rng();
1512 let mut v = rng.gen_iter::<BigSortable>().take(5)
1513 .collect::<Vec<BigSortable>>();
1516 b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
1520 fn sort_big_random_medium(b: &mut Bencher) {
1521 let mut rng = thread_rng();
1523 let mut v = rng.gen_iter::<BigSortable>().take(100)
1524 .collect::<Vec<BigSortable>>();
1527 b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
1531 fn sort_big_random_large(b: &mut Bencher) {
1532 let mut rng = thread_rng();
1534 let mut v = rng.gen_iter::<BigSortable>().take(10000)
1535 .collect::<Vec<BigSortable>>();
1538 b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
1542 fn sort_big_sorted(b: &mut Bencher) {
1543 let mut v: Vec<BigSortable> = (0..10000).map(|i| (i, i, i, i)).collect();
1547 b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;