src/libcollectionstest/slice.rs

   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.
   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::cmp::Ordering::{Equal, Greater, Less};
  12 use std::mem;
  13 use std::__rand::{Rng, thread_rng};
  14 use std::rc::Rc;
  15
  16 fn square(n: usize) -> usize {
  17     n * n
  18 }
  19
  20 fn is_odd(n: &usize) -> bool {
  21     *n % 2 == 1
  22 }
  23
  24 #[test]
  25 fn test_from_fn() {
  26     // Test on-stack from_fn.
  27     let mut v: Vec<_> = (0..3).map(square).collect();
  28     {
  29         let v = v;
  30         assert_eq!(v.len(), 3);
  31         assert_eq!(v[0], 0);
  32         assert_eq!(v[1], 1);
  33         assert_eq!(v[2], 4);
  34     }
  35
  36     // Test on-heap from_fn.
  37     v = (0..5).map(square).collect();
  38     {
  39         let v = v;
  40         assert_eq!(v.len(), 5);
  41         assert_eq!(v[0], 0);
  42         assert_eq!(v[1], 1);
  43         assert_eq!(v[2], 4);
  44         assert_eq!(v[3], 9);
  45         assert_eq!(v[4], 16);
  46     }
  47 }
  48
  49 #[test]
  50 fn test_from_elem() {
  51     // Test on-stack from_elem.
  52     let mut v = vec![10, 10];
  53     {
  54         let v = v;
  55         assert_eq!(v.len(), 2);
  56         assert_eq!(v[0], 10);
  57         assert_eq!(v[1], 10);
  58     }
  59
  60     // Test on-heap from_elem.
  61     v = vec![20; 6];
  62     {
  63         let v = &v[..];
  64         assert_eq!(v[0], 20);
  65         assert_eq!(v[1], 20);
  66         assert_eq!(v[2], 20);
  67         assert_eq!(v[3], 20);
  68         assert_eq!(v[4], 20);
  69         assert_eq!(v[5], 20);
  70     }
  71 }
  72
  73 #[test]
  74 fn test_is_empty() {
  75     let xs: [i32; 0] = [];
  76     assert!(xs.is_empty());
  77     assert!(![0].is_empty());
  78 }
  79
  80 #[test]
  81 fn test_len_divzero() {
  82     type Z = [i8; 0];
  83     let v0: &[Z] = &[];
  84     let v1: &[Z] = &[[]];
  85     let v2: &[Z] = &[[], []];
  86     assert_eq!(mem::size_of::<Z>(), 0);
  87     assert_eq!(v0.len(), 0);
  88     assert_eq!(v1.len(), 1);
  89     assert_eq!(v2.len(), 2);
  90 }
  91
  92 #[test]
  93 fn test_get() {
  94     let mut a = vec![11];
  95     assert_eq!(a.get(1), None);
  96     a = vec![11, 12];
  97     assert_eq!(a.get(1).unwrap(), &12);
  98     a = vec![11, 12, 13];
  99     assert_eq!(a.get(1).unwrap(), &12);
 100 }
 101
 102 #[test]
 103 fn test_first() {
 104     let mut a = vec![];
 105     assert_eq!(a.first(), None);
 106     a = vec![11];
 107     assert_eq!(a.first().unwrap(), &11);
 108     a = vec![11, 12];
 109     assert_eq!(a.first().unwrap(), &11);
 110 }
 111
 112 #[test]
 113 fn test_first_mut() {
 114     let mut a = vec![];
 115     assert_eq!(a.first_mut(), None);
 116     a = vec![11];
 117     assert_eq!(*a.first_mut().unwrap(), 11);
 118     a = vec![11, 12];
 119     assert_eq!(*a.first_mut().unwrap(), 11);
 120 }
 121
 122 #[test]
 123 fn test_split_first() {
 124     let mut a = vec![11];
 125     let b: &[i32] = &[];
 126     assert!(b.split_first().is_none());
 127     assert_eq!(a.split_first(), Some((&11, b)));
 128     a = vec![11, 12];
 129     let b: &[i32] = &[12];
 130     assert_eq!(a.split_first(), Some((&11, b)));
 131 }
 132
 133 #[test]
 134 fn test_split_first_mut() {
 135     let mut a = vec![11];
 136     let b: &mut [i32] = &mut [];
 137     assert!(b.split_first_mut().is_none());
 138     assert!(a.split_first_mut() == Some((&mut 11, b)));
 139     a = vec![11, 12];
 140     let b: &mut [_] = &mut [12];
 141     assert!(a.split_first_mut() == Some((&mut 11, b)));
 142 }
 143
 144 #[test]
 145 fn test_split_last() {
 146     let mut a = vec![11];
 147     let b: &[i32] = &[];
 148     assert!(b.split_last().is_none());
 149     assert_eq!(a.split_last(), Some((&11, b)));
 150     a = vec![11, 12];
 151     let b: &[_] = &[11];
 152     assert_eq!(a.split_last(), Some((&12, b)));
 153 }
 154
 155 #[test]
 156 fn test_split_last_mut() {
 157     let mut a = vec![11];
 158     let b: &mut [i32] = &mut [];
 159     assert!(b.split_last_mut().is_none());
 160     assert!(a.split_last_mut() == Some((&mut 11, b)));
 161
 162     a = vec![11, 12];
 163     let b: &mut [_] = &mut [11];
 164     assert!(a.split_last_mut() == Some((&mut 12, b)));
 165 }
 166
 167 #[test]
 168 fn test_last() {
 169     let mut a = vec![];
 170     assert_eq!(a.last(), None);
 171     a = vec![11];
 172     assert_eq!(a.last().unwrap(), &11);
 173     a = vec![11, 12];
 174     assert_eq!(a.last().unwrap(), &12);
 175 }
 176
 177 #[test]
 178 fn test_last_mut() {
 179     let mut a = vec![];
 180     assert_eq!(a.last_mut(), None);
 181     a = vec![11];
 182     assert_eq!(*a.last_mut().unwrap(), 11);
 183     a = vec![11, 12];
 184     assert_eq!(*a.last_mut().unwrap(), 12);
 185 }
 186
 187 #[test]
 188 fn test_slice() {
 189     // Test fixed length vector.
 190     let vec_fixed = [1, 2, 3, 4];
 191     let v_a = vec_fixed[1..vec_fixed.len()].to_vec();
 192     assert_eq!(v_a.len(), 3);
 193
 194     assert_eq!(v_a[0], 2);
 195     assert_eq!(v_a[1], 3);
 196     assert_eq!(v_a[2], 4);
 197
 198     // Test on stack.
 199     let vec_stack: &[_] = &[1, 2, 3];
 200     let v_b = vec_stack[1..3].to_vec();
 201     assert_eq!(v_b.len(), 2);
 202
 203     assert_eq!(v_b[0], 2);
 204     assert_eq!(v_b[1], 3);
 205
 206     // Test `Box<[T]>`
 207     let vec_unique = vec![1, 2, 3, 4, 5, 6];
 208     let v_d = vec_unique[1..6].to_vec();
 209     assert_eq!(v_d.len(), 5);
 210
 211     assert_eq!(v_d[0], 2);
 212     assert_eq!(v_d[1], 3);
 213     assert_eq!(v_d[2], 4);
 214     assert_eq!(v_d[3], 5);
 215     assert_eq!(v_d[4], 6);
 216 }
 217
 218 #[test]
 219 fn test_slice_from() {
 220     let vec: &[_] = &[1, 2, 3, 4];
 221     assert_eq!(&vec[..], vec);
 222     let b: &[_] = &[3, 4];
 223     assert_eq!(&vec[2..], b);
 224     let b: &[_] = &[];
 225     assert_eq!(&vec[4..], b);
 226 }
 227
 228 #[test]
 229 fn test_slice_to() {
 230     let vec: &[_] = &[1, 2, 3, 4];
 231     assert_eq!(&vec[..4], vec);
 232     let b: &[_] = &[1, 2];
 233     assert_eq!(&vec[..2], b);
 234     let b: &[_] = &[];
 235     assert_eq!(&vec[..0], b);
 236 }
 237
 238
 239 #[test]
 240 fn test_pop() {
 241     let mut v = vec![5];
 242     let e = v.pop();
 243     assert_eq!(v.len(), 0);
 244     assert_eq!(e, Some(5));
 245     let f = v.pop();
 246     assert_eq!(f, None);
 247     let g = v.pop();
 248     assert_eq!(g, None);
 249 }
 250
 251 #[test]
 252 fn test_swap_remove() {
 253     let mut v = vec![1, 2, 3, 4, 5];
 254     let mut e = v.swap_remove(0);
 255     assert_eq!(e, 1);
 256     assert_eq!(v, [5, 2, 3, 4]);
 257     e = v.swap_remove(3);
 258     assert_eq!(e, 4);
 259     assert_eq!(v, [5, 2, 3]);
 260 }
 261
 262 #[test]
 263 #[should_panic]
 264 fn test_swap_remove_fail() {
 265     let mut v = vec![1];
 266     let _ = v.swap_remove(0);
 267     let _ = v.swap_remove(0);
 268 }
 269
 270 #[test]
 271 fn test_swap_remove_noncopyable() {
 272     // Tests that we don't accidentally run destructors twice.
 273     let mut v: Vec<Box<_>> = Vec::new();
 274     v.push(box 0);
 275     v.push(box 0);
 276     v.push(box 0);
 277     let mut _e = v.swap_remove(0);
 278     assert_eq!(v.len(), 2);
 279     _e = v.swap_remove(1);
 280     assert_eq!(v.len(), 1);
 281     _e = v.swap_remove(0);
 282     assert_eq!(v.len(), 0);
 283 }
 284
 285 #[test]
 286 fn test_push() {
 287     // Test on-stack push().
 288     let mut v = vec![];
 289     v.push(1);
 290     assert_eq!(v.len(), 1);
 291     assert_eq!(v[0], 1);
 292
 293     // Test on-heap push().
 294     v.push(2);
 295     assert_eq!(v.len(), 2);
 296     assert_eq!(v[0], 1);
 297     assert_eq!(v[1], 2);
 298 }
 299
 300 #[test]
 301 fn test_truncate() {
 302     let mut v: Vec<Box<_>> = vec![box 6, box 5, box 4];
 303     v.truncate(1);
 304     let v = v;
 305     assert_eq!(v.len(), 1);
 306     assert_eq!(*(v[0]), 6);
 307     // If the unsafe block didn't drop things properly, we blow up here.
 308 }
 309
 310 #[test]
 311 fn test_clear() {
 312     let mut v: Vec<Box<_>> = vec![box 6, box 5, box 4];
 313     v.clear();
 314     assert_eq!(v.len(), 0);
 315     // If the unsafe block didn't drop things properly, we blow up here.
 316 }
 317
 318 #[test]
 319 fn test_retain() {
 320     let mut v = vec![1, 2, 3, 4, 5];
 321     v.retain(is_odd);
 322     assert_eq!(v, [1, 3, 5]);
 323 }
 324
 325 #[test]
 326 fn test_binary_search() {
 327     assert_eq!([1, 2, 3, 4, 5].binary_search(&5).ok(), Some(4));
 328     assert_eq!([1, 2, 3, 4, 5].binary_search(&4).ok(), Some(3));
 329     assert_eq!([1, 2, 3, 4, 5].binary_search(&3).ok(), Some(2));
 330     assert_eq!([1, 2, 3, 4, 5].binary_search(&2).ok(), Some(1));
 331     assert_eq!([1, 2, 3, 4, 5].binary_search(&1).ok(), Some(0));
 332
 333     assert_eq!([2, 4, 6, 8, 10].binary_search(&1).ok(), None);
 334     assert_eq!([2, 4, 6, 8, 10].binary_search(&5).ok(), None);
 335     assert_eq!([2, 4, 6, 8, 10].binary_search(&4).ok(), Some(1));
 336     assert_eq!([2, 4, 6, 8, 10].binary_search(&10).ok(), Some(4));
 337
 338     assert_eq!([2, 4, 6, 8].binary_search(&1).ok(), None);
 339     assert_eq!([2, 4, 6, 8].binary_search(&5).ok(), None);
 340     assert_eq!([2, 4, 6, 8].binary_search(&4).ok(), Some(1));
 341     assert_eq!([2, 4, 6, 8].binary_search(&8).ok(), Some(3));
 342
 343     assert_eq!([2, 4, 6].binary_search(&1).ok(), None);
 344     assert_eq!([2, 4, 6].binary_search(&5).ok(), None);
 345     assert_eq!([2, 4, 6].binary_search(&4).ok(), Some(1));
 346     assert_eq!([2, 4, 6].binary_search(&6).ok(), Some(2));
 347
 348     assert_eq!([2, 4].binary_search(&1).ok(), None);
 349     assert_eq!([2, 4].binary_search(&5).ok(), None);
 350     assert_eq!([2, 4].binary_search(&2).ok(), Some(0));
 351     assert_eq!([2, 4].binary_search(&4).ok(), Some(1));
 352
 353     assert_eq!([2].binary_search(&1).ok(), None);
 354     assert_eq!([2].binary_search(&5).ok(), None);
 355     assert_eq!([2].binary_search(&2).ok(), Some(0));
 356
 357     assert_eq!([].binary_search(&1).ok(), None);
 358     assert_eq!([].binary_search(&5).ok(), None);
 359
 360     assert!([1, 1, 1, 1, 1].binary_search(&1).ok() != None);
 361     assert!([1, 1, 1, 1, 2].binary_search(&1).ok() != None);
 362     assert!([1, 1, 1, 2, 2].binary_search(&1).ok() != None);
 363     assert!([1, 1, 2, 2, 2].binary_search(&1).ok() != None);
 364     assert_eq!([1, 2, 2, 2, 2].binary_search(&1).ok(), Some(0));
 365
 366     assert_eq!([1, 2, 3, 4, 5].binary_search(&6).ok(), None);
 367     assert_eq!([1, 2, 3, 4, 5].binary_search(&0).ok(), None);
 368 }
 369
 370 #[test]
 371 fn test_reverse() {
 372     let mut v = vec![10, 20];
 373     assert_eq!(v[0], 10);
 374     assert_eq!(v[1], 20);
 375     v.reverse();
 376     assert_eq!(v[0], 20);
 377     assert_eq!(v[1], 10);
 378
 379     let mut v3 = Vec::<i32>::new();
 380     v3.reverse();
 381     assert!(v3.is_empty());
 382 }
 383
 384 #[test]
 385 fn test_sort() {
 386     for len in 4..25 {
 387         for _ in 0..100 {
 388             let mut v: Vec<_> = thread_rng().gen_iter::<i32>().take(len).collect();
 389             let mut v1 = v.clone();
 390
 391             v.sort();
 392             assert!(v.windows(2).all(|w| w[0] <= w[1]));
 393
 394             v1.sort_by(|a, b| a.cmp(b));
 395             assert!(v1.windows(2).all(|w| w[0] <= w[1]));
 396
 397             v1.sort_by(|a, b| b.cmp(a));
 398             assert!(v1.windows(2).all(|w| w[0] >= w[1]));
 399         }
 400     }
 401
 402     // shouldn't panic
 403     let mut v: [i32; 0] = [];
 404     v.sort();
 405
 406     let mut v = [0xDEADBEEFu64];
 407     v.sort();
 408     assert!(v == [0xDEADBEEF]);
 409 }
 410
 411 #[test]
 412 fn test_sort_stability() {
 413     for len in 4..25 {
 414         for _ in 0..10 {
 415             let mut counts = [0; 10];
 416
 417             // create a vector like [(6, 1), (5, 1), (6, 2), ...],
 418             // where the first item of each tuple is random, but
 419             // the second item represents which occurrence of that
 420             // number this element is, i.e. the second elements
 421             // will occur in sorted order.
 422             let mut v: Vec<_> = (0..len)
 423                 .map(|_| {
 424                     let n = thread_rng().gen::<usize>() % 10;
 425                     counts[n] += 1;
 426                     (n, counts[n])
 427                 })
 428                 .collect();
 429
 430             // only sort on the first element, so an unstable sort
 431             // may mix up the counts.
 432             v.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 433
 434             // this comparison includes the count (the second item
 435             // of the tuple), so elements with equal first items
 436             // will need to be ordered with increasing
 437             // counts... i.e. exactly asserting that this sort is
 438             // stable.
 439             assert!(v.windows(2).all(|w| w[0] <= w[1]));
 440         }
 441     }
 442 }
 443
 444 #[test]
 445 fn test_concat() {
 446     let v: [Vec<i32>; 0] = [];
 447     let c = v.concat();
 448     assert_eq!(c, []);
 449     let d = [vec![1], vec![2, 3]].concat();
 450     assert_eq!(d, [1, 2, 3]);
 451
 452     let v: &[&[_]] = &[&[1], &[2, 3]];
 453     assert_eq!(v.join(&0), [1, 0, 2, 3]);
 454     let v: &[&[_]] = &[&[1], &[2], &[3]];
 455     assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
 456 }
 457
 458 #[test]
 459 fn test_join() {
 460     let v: [Vec<i32>; 0] = [];
 461     assert_eq!(v.join(&0), []);
 462     assert_eq!([vec![1], vec![2, 3]].join(&0), [1, 0, 2, 3]);
 463     assert_eq!([vec![1], vec![2], vec![3]].join(&0), [1, 0, 2, 0, 3]);
 464
 465     let v: [&[_]; 2] = [&[1], &[2, 3]];
 466     assert_eq!(v.join(&0), [1, 0, 2, 3]);
 467     let v: [&[_]; 3] = [&[1], &[2], &[3]];
 468     assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
 469 }
 470
 471 #[test]
 472 fn test_insert() {
 473     let mut a = vec![1, 2, 4];
 474     a.insert(2, 3);
 475     assert_eq!(a, [1, 2, 3, 4]);
 476
 477     let mut a = vec![1, 2, 3];
 478     a.insert(0, 0);
 479     assert_eq!(a, [0, 1, 2, 3]);
 480
 481     let mut a = vec![1, 2, 3];
 482     a.insert(3, 4);
 483     assert_eq!(a, [1, 2, 3, 4]);
 484
 485     let mut a = vec![];
 486     a.insert(0, 1);
 487     assert_eq!(a, [1]);
 488 }
 489
 490 #[test]
 491 #[should_panic]
 492 fn test_insert_oob() {
 493     let mut a = vec![1, 2, 3];
 494     a.insert(4, 5);
 495 }
 496
 497 #[test]
 498 fn test_remove() {
 499     let mut a = vec![1, 2, 3, 4];
 500
 501     assert_eq!(a.remove(2), 3);
 502     assert_eq!(a, [1, 2, 4]);
 503
 504     assert_eq!(a.remove(2), 4);
 505     assert_eq!(a, [1, 2]);
 506
 507     assert_eq!(a.remove(0), 1);
 508     assert_eq!(a, [2]);
 509
 510     assert_eq!(a.remove(0), 2);
 511     assert_eq!(a, []);
 512 }
 513
 514 #[test]
 515 #[should_panic]
 516 fn test_remove_fail() {
 517     let mut a = vec![1];
 518     let _ = a.remove(0);
 519     let _ = a.remove(0);
 520 }
 521
 522 #[test]
 523 fn test_capacity() {
 524     let mut v = vec![0];
 525     v.reserve_exact(10);
 526     assert!(v.capacity() >= 11);
 527 }
 528
 529 #[test]
 530 fn test_slice_2() {
 531     let v = vec![1, 2, 3, 4, 5];
 532     let v = &v[1..3];
 533     assert_eq!(v.len(), 2);
 534     assert_eq!(v[0], 2);
 535     assert_eq!(v[1], 3);
 536 }
 537
 538 macro_rules! assert_order {
 539     (Greater, $a:expr, $b:expr) => {
 540         assert_eq!($a.cmp($b), Greater);
 541         assert!($a > $b);
 542     };
 543     (Less, $a:expr, $b:expr) => {
 544         assert_eq!($a.cmp($b), Less);
 545         assert!($a < $b);
 546     };
 547     (Equal, $a:expr, $b:expr) => {
 548         assert_eq!($a.cmp($b), Equal);
 549         assert_eq!($a, $b);
 550     }
 551 }
 552
 553 #[test]
 554 fn test_total_ord_u8() {
 555     let c = &[1u8, 2, 3];
 556     assert_order!(Greater, &[1u8, 2, 3, 4][..], &c[..]);
 557     let c = &[1u8, 2, 3, 4];
 558     assert_order!(Less, &[1u8, 2, 3][..], &c[..]);
 559     let c = &[1u8, 2, 3, 6];
 560     assert_order!(Equal, &[1u8, 2, 3, 6][..], &c[..]);
 561     let c = &[1u8, 2, 3, 4, 5, 6];
 562     assert_order!(Less, &[1u8, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
 563     let c = &[1u8, 2, 3, 4];
 564     assert_order!(Greater, &[2u8, 2][..], &c[..]);
 565 }
 566
 567
 568 #[test]
 569 fn test_total_ord_i32() {
 570     let c = &[1, 2, 3];
 571     assert_order!(Greater, &[1, 2, 3, 4][..], &c[..]);
 572     let c = &[1, 2, 3, 4];
 573     assert_order!(Less, &[1, 2, 3][..], &c[..]);
 574     let c = &[1, 2, 3, 6];
 575     assert_order!(Equal, &[1, 2, 3, 6][..], &c[..]);
 576     let c = &[1, 2, 3, 4, 5, 6];
 577     assert_order!(Less, &[1, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
 578     let c = &[1, 2, 3, 4];
 579     assert_order!(Greater, &[2, 2][..], &c[..]);
 580 }
 581
 582 #[test]
 583 fn test_iterator() {
 584     let xs = [1, 2, 5, 10, 11];
 585     let mut it = xs.iter();
 586     assert_eq!(it.size_hint(), (5, Some(5)));
 587     assert_eq!(it.next().unwrap(), &1);
 588     assert_eq!(it.size_hint(), (4, Some(4)));
 589     assert_eq!(it.next().unwrap(), &2);
 590     assert_eq!(it.size_hint(), (3, Some(3)));
 591     assert_eq!(it.next().unwrap(), &5);
 592     assert_eq!(it.size_hint(), (2, Some(2)));
 593     assert_eq!(it.next().unwrap(), &10);
 594     assert_eq!(it.size_hint(), (1, Some(1)));
 595     assert_eq!(it.next().unwrap(), &11);
 596     assert_eq!(it.size_hint(), (0, Some(0)));
 597     assert!(it.next().is_none());
 598 }
 599
 600 #[test]
 601 fn test_iter_size_hints() {
 602     let mut xs = [1, 2, 5, 10, 11];
 603     assert_eq!(xs.iter().size_hint(), (5, Some(5)));
 604     assert_eq!(xs.iter_mut().size_hint(), (5, Some(5)));
 605 }
 606
 607 #[test]
 608 fn test_iter_as_slice() {
 609     let xs = [1, 2, 5, 10, 11];
 610     let mut iter = xs.iter();
 611     assert_eq!(iter.as_slice(), &[1, 2, 5, 10, 11]);
 612     iter.next();
 613     assert_eq!(iter.as_slice(), &[2, 5, 10, 11]);
 614 }
 615
 616 #[test]
 617 fn test_iter_as_ref() {
 618     let xs = [1, 2, 5, 10, 11];
 619     let mut iter = xs.iter();
 620     assert_eq!(iter.as_ref(), &[1, 2, 5, 10, 11]);
 621     iter.next();
 622     assert_eq!(iter.as_ref(), &[2, 5, 10, 11]);
 623 }
 624
 625 #[test]
 626 fn test_iter_clone() {
 627     let xs = [1, 2, 5];
 628     let mut it = xs.iter();
 629     it.next();
 630     let mut jt = it.clone();
 631     assert_eq!(it.next(), jt.next());
 632     assert_eq!(it.next(), jt.next());
 633     assert_eq!(it.next(), jt.next());
 634 }
 635
 636 #[test]
 637 fn test_mut_iterator() {
 638     let mut xs = [1, 2, 3, 4, 5];
 639     for x in &mut xs {
 640         *x += 1;
 641     }
 642     assert!(xs == [2, 3, 4, 5, 6])
 643 }
 644
 645 #[test]
 646 fn test_rev_iterator() {
 647
 648     let xs = [1, 2, 5, 10, 11];
 649     let ys = [11, 10, 5, 2, 1];
 650     let mut i = 0;
 651     for &x in xs.iter().rev() {
 652         assert_eq!(x, ys[i]);
 653         i += 1;
 654     }
 655     assert_eq!(i, 5);
 656 }
 657
 658 #[test]
 659 fn test_mut_rev_iterator() {
 660     let mut xs = [1, 2, 3, 4, 5];
 661     for (i, x) in xs.iter_mut().rev().enumerate() {
 662         *x += i;
 663     }
 664     assert!(xs == [5, 5, 5, 5, 5])
 665 }
 666
 667 #[test]
 668 fn test_move_iterator() {
 669     let xs = vec![1, 2, 3, 4, 5];
 670     assert_eq!(xs.into_iter().fold(0, |a: usize, b: usize| 10 * a + b),
 671                12345);
 672 }
 673
 674 #[test]
 675 fn test_move_rev_iterator() {
 676     let xs = vec![1, 2, 3, 4, 5];
 677     assert_eq!(xs.into_iter().rev().fold(0, |a: usize, b: usize| 10 * a + b),
 678                54321);
 679 }
 680
 681 #[test]
 682 fn test_splitator() {
 683     let xs = &[1, 2, 3, 4, 5];
 684
 685     let splits: &[&[_]] = &[&[1], &[3], &[5]];
 686     assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 687     let splits: &[&[_]] = &[&[], &[2, 3, 4, 5]];
 688     assert_eq!(xs.split(|x| *x == 1).collect::<Vec<_>>(), splits);
 689     let splits: &[&[_]] = &[&[1, 2, 3, 4], &[]];
 690     assert_eq!(xs.split(|x| *x == 5).collect::<Vec<_>>(), splits);
 691     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 692     assert_eq!(xs.split(|x| *x == 10).collect::<Vec<_>>(), splits);
 693     let splits: &[&[_]] = &[&[], &[], &[], &[], &[], &[]];
 694     assert_eq!(xs.split(|_| true).collect::<Vec<&[i32]>>(), splits);
 695
 696     let xs: &[i32] = &[];
 697     let splits: &[&[i32]] = &[&[]];
 698     assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[i32]>>(), splits);
 699 }
 700
 701 #[test]
 702 fn test_splitnator() {
 703     let xs = &[1, 2, 3, 4, 5];
 704
 705     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 706     assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 707     let splits: &[&[_]] = &[&[1], &[3, 4, 5]];
 708     assert_eq!(xs.splitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 709     let splits: &[&[_]] = &[&[], &[], &[], &[4, 5]];
 710     assert_eq!(xs.splitn(4, |_| true).collect::<Vec<_>>(), splits);
 711
 712     let xs: &[i32] = &[];
 713     let splits: &[&[i32]] = &[&[]];
 714     assert_eq!(xs.splitn(2, |x| *x == 5).collect::<Vec<_>>(), splits);
 715 }
 716
 717 #[test]
 718 fn test_splitnator_mut() {
 719     let xs = &mut [1, 2, 3, 4, 5];
 720
 721     let splits: &[&mut [_]] = &[&mut [1, 2, 3, 4, 5]];
 722     assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
 723                splits);
 724     let splits: &[&mut [_]] = &[&mut [1], &mut [3, 4, 5]];
 725     assert_eq!(xs.splitn_mut(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
 726                splits);
 727     let splits: &[&mut [_]] = &[&mut [], &mut [], &mut [], &mut [4, 5]];
 728     assert_eq!(xs.splitn_mut(4, |_| true).collect::<Vec<_>>(), splits);
 729
 730     let xs: &mut [i32] = &mut [];
 731     let splits: &[&mut [i32]] = &[&mut []];
 732     assert_eq!(xs.splitn_mut(2, |x| *x == 5).collect::<Vec<_>>(), splits);
 733 }
 734
 735 #[test]
 736 fn test_rsplitator() {
 737     let xs = &[1, 2, 3, 4, 5];
 738
 739     let splits: &[&[_]] = &[&[5], &[3], &[1]];
 740     assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<_>>(), splits);
 741     let splits: &[&[_]] = &[&[2, 3, 4, 5], &[]];
 742     assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<_>>(), splits);
 743     let splits: &[&[_]] = &[&[], &[1, 2, 3, 4]];
 744     assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
 745     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 746     assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<_>>(), splits);
 747
 748     let xs: &[i32] = &[];
 749     let splits: &[&[i32]] = &[&[]];
 750     assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[i32]>>(), splits);
 751 }
 752
 753 #[test]
 754 fn test_rsplitnator() {
 755     let xs = &[1, 2, 3, 4, 5];
 756
 757     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 758     assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 759     let splits: &[&[_]] = &[&[5], &[1, 2, 3]];
 760     assert_eq!(xs.rsplitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 761     let splits: &[&[_]] = &[&[], &[], &[], &[1, 2]];
 762     assert_eq!(xs.rsplitn(4, |_| true).collect::<Vec<_>>(), splits);
 763
 764     let xs: &[i32] = &[];
 765     let splits: &[&[i32]] = &[&[]];
 766     assert_eq!(xs.rsplitn(2, |x| *x == 5).collect::<Vec<&[i32]>>(), splits);
 767     assert!(xs.rsplitn(0, |x| *x % 2 == 0).next().is_none());
 768 }
 769
 770 #[test]
 771 fn test_windowsator() {
 772     let v = &[1, 2, 3, 4];
 773
 774     let wins: &[&[_]] = &[&[1, 2], &[2, 3], &[3, 4]];
 775     assert_eq!(v.windows(2).collect::<Vec<_>>(), wins);
 776
 777     let wins: &[&[_]] = &[&[1, 2, 3], &[2, 3, 4]];
 778     assert_eq!(v.windows(3).collect::<Vec<_>>(), wins);
 779     assert!(v.windows(6).next().is_none());
 780
 781     let wins: &[&[_]] = &[&[3, 4], &[2, 3], &[1, 2]];
 782     assert_eq!(v.windows(2).rev().collect::<Vec<&[_]>>(), wins);
 783 }
 784
 785 #[test]
 786 #[should_panic]
 787 fn test_windowsator_0() {
 788     let v = &[1, 2, 3, 4];
 789     let _it = v.windows(0);
 790 }
 791
 792 #[test]
 793 fn test_chunksator() {
 794     let v = &[1, 2, 3, 4, 5];
 795
 796     assert_eq!(v.chunks(2).len(), 3);
 797
 798     let chunks: &[&[_]] = &[&[1, 2], &[3, 4], &[5]];
 799     assert_eq!(v.chunks(2).collect::<Vec<_>>(), chunks);
 800     let chunks: &[&[_]] = &[&[1, 2, 3], &[4, 5]];
 801     assert_eq!(v.chunks(3).collect::<Vec<_>>(), chunks);
 802     let chunks: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 803     assert_eq!(v.chunks(6).collect::<Vec<_>>(), chunks);
 804
 805     let chunks: &[&[_]] = &[&[5], &[3, 4], &[1, 2]];
 806     assert_eq!(v.chunks(2).rev().collect::<Vec<_>>(), chunks);
 807 }
 808
 809 #[test]
 810 #[should_panic]
 811 fn test_chunksator_0() {
 812     let v = &[1, 2, 3, 4];
 813     let _it = v.chunks(0);
 814 }
 815
 816 #[test]
 817 fn test_reverse_part() {
 818     let mut values = [1, 2, 3, 4, 5];
 819     values[1..4].reverse();
 820     assert!(values == [1, 4, 3, 2, 5]);
 821 }
 822
 823 #[test]
 824 fn test_show() {
 825     macro_rules! test_show_vec {
 826         ($x:expr, $x_str:expr) => ({
 827             let (x, x_str) = ($x, $x_str);
 828             assert_eq!(format!("{:?}", x), x_str);
 829             assert_eq!(format!("{:?}", x), x_str);
 830         })
 831     }
 832     let empty = Vec::<i32>::new();
 833     test_show_vec!(empty, "[]");
 834     test_show_vec!(vec![1], "[1]");
 835     test_show_vec!(vec![1, 2, 3], "[1, 2, 3]");
 836     test_show_vec!(vec![vec![], vec![1], vec![1, 1]], "[[], [1], [1, 1]]");
 837
 838     let empty_mut: &mut [i32] = &mut [];
 839     test_show_vec!(empty_mut, "[]");
 840     let v = &mut [1];
 841     test_show_vec!(v, "[1]");
 842     let v = &mut [1, 2, 3];
 843     test_show_vec!(v, "[1, 2, 3]");
 844     let v: &mut [&mut [_]] = &mut [&mut [], &mut [1], &mut [1, 1]];
 845     test_show_vec!(v, "[[], [1], [1, 1]]");
 846 }
 847
 848 #[test]
 849 fn test_vec_default() {
 850     macro_rules! t {
 851         ($ty:ty) => {{
 852             let v: $ty = Default::default();
 853             assert!(v.is_empty());
 854         }}
 855     }
 856
 857     t!(&[i32]);
 858     t!(Vec<i32>);
 859 }
 860
 861 #[test]
 862 #[should_panic]
 863 fn test_overflow_does_not_cause_segfault() {
 864     let mut v = vec![];
 865     v.reserve_exact(!0);
 866     v.push(1);
 867     v.push(2);
 868 }
 869
 870 #[test]
 871 #[should_panic]
 872 fn test_overflow_does_not_cause_segfault_managed() {
 873     let mut v = vec![Rc::new(1)];
 874     v.reserve_exact(!0);
 875     v.push(Rc::new(2));
 876 }
 877
 878 #[test]
 879 fn test_mut_split_at() {
 880     let mut values = [1, 2, 3, 4, 5];
 881     {
 882         let (left, right) = values.split_at_mut(2);
 883         {
 884             let left: &[_] = left;
 885             assert!(left[..left.len()] == [1, 2]);
 886         }
 887         for p in left {
 888             *p += 1;
 889         }
 890
 891         {
 892             let right: &[_] = right;
 893             assert!(right[..right.len()] == [3, 4, 5]);
 894         }
 895         for p in right {
 896             *p += 2;
 897         }
 898     }
 899
 900     assert!(values == [2, 3, 5, 6, 7]);
 901 }
 902
 903 #[derive(Clone, PartialEq)]
 904 struct Foo;
 905
 906 #[test]
 907 fn test_iter_zero_sized() {
 908     let mut v = vec![Foo, Foo, Foo];
 909     assert_eq!(v.len(), 3);
 910     let mut cnt = 0;
 911
 912     for f in &v {
 913         assert!(*f == Foo);
 914         cnt += 1;
 915     }
 916     assert_eq!(cnt, 3);
 917
 918     for f in &v[1..3] {
 919         assert!(*f == Foo);
 920         cnt += 1;
 921     }
 922     assert_eq!(cnt, 5);
 923
 924     for f in &mut v {
 925         assert!(*f == Foo);
 926         cnt += 1;
 927     }
 928     assert_eq!(cnt, 8);
 929
 930     for f in v {
 931         assert!(f == Foo);
 932         cnt += 1;
 933     }
 934     assert_eq!(cnt, 11);
 935
 936     let xs: [Foo; 3] = [Foo, Foo, Foo];
 937     cnt = 0;
 938     for f in &xs {
 939         assert!(*f == Foo);
 940         cnt += 1;
 941     }
 942     assert!(cnt == 3);
 943 }
 944
 945 #[test]
 946 fn test_shrink_to_fit() {
 947     let mut xs = vec![0, 1, 2, 3];
 948     for i in 4..100 {
 949         xs.push(i)
 950     }
 951     assert_eq!(xs.capacity(), 128);
 952     xs.shrink_to_fit();
 953     assert_eq!(xs.capacity(), 100);
 954     assert_eq!(xs, (0..100).collect::<Vec<_>>());
 955 }
 956
 957 #[test]
 958 fn test_starts_with() {
 959     assert!(b"foobar".starts_with(b"foo"));
 960     assert!(!b"foobar".starts_with(b"oob"));
 961     assert!(!b"foobar".starts_with(b"bar"));
 962     assert!(!b"foo".starts_with(b"foobar"));
 963     assert!(!b"bar".starts_with(b"foobar"));
 964     assert!(b"foobar".starts_with(b"foobar"));
 965     let empty: &[u8] = &[];
 966     assert!(empty.starts_with(empty));
 967     assert!(!empty.starts_with(b"foo"));
 968     assert!(b"foobar".starts_with(empty));
 969 }
 970
 971 #[test]
 972 fn test_ends_with() {
 973     assert!(b"foobar".ends_with(b"bar"));
 974     assert!(!b"foobar".ends_with(b"oba"));
 975     assert!(!b"foobar".ends_with(b"foo"));
 976     assert!(!b"foo".ends_with(b"foobar"));
 977     assert!(!b"bar".ends_with(b"foobar"));
 978     assert!(b"foobar".ends_with(b"foobar"));
 979     let empty: &[u8] = &[];
 980     assert!(empty.ends_with(empty));
 981     assert!(!empty.ends_with(b"foo"));
 982     assert!(b"foobar".ends_with(empty));
 983 }
 984
 985 #[test]
 986 fn test_mut_splitator() {
 987     let mut xs = [0, 1, 0, 2, 3, 0, 0, 4, 5, 0];
 988     assert_eq!(xs.split_mut(|x| *x == 0).count(), 6);
 989     for slice in xs.split_mut(|x| *x == 0) {
 990         slice.reverse();
 991     }
 992     assert!(xs == [0, 1, 0, 3, 2, 0, 0, 5, 4, 0]);
 993
 994     let mut xs = [0, 1, 0, 2, 3, 0, 0, 4, 5, 0, 6, 7];
 995     for slice in xs.split_mut(|x| *x == 0).take(5) {
 996         slice.reverse();
 997     }
 998     assert!(xs == [0, 1, 0, 3, 2, 0, 0, 5, 4, 0, 6, 7]);
 999 }
1000
1001 #[test]
1002 fn test_mut_splitator_rev() {
1003     let mut xs = [1, 2, 0, 3, 4, 0, 0, 5, 6, 0];
1004     for slice in xs.split_mut(|x| *x == 0).rev().take(4) {
1005         slice.reverse();
1006     }
1007     assert!(xs == [1, 2, 0, 4, 3, 0, 0, 6, 5, 0]);
1008 }
1009
1010 #[test]
1011 fn test_get_mut() {
1012     let mut v = [0, 1, 2];
1013     assert_eq!(v.get_mut(3), None);
1014     v.get_mut(1).map(|e| *e = 7);
1015     assert_eq!(v[1], 7);
1016     let mut x = 2;
1017     assert_eq!(v.get_mut(2), Some(&mut x));
1018 }
1019
1020 #[test]
1021 fn test_mut_chunks() {
1022     let mut v = [0, 1, 2, 3, 4, 5, 6];
1023     assert_eq!(v.chunks_mut(2).len(), 4);
1024     for (i, chunk) in v.chunks_mut(3).enumerate() {
1025         for x in chunk {
1026             *x = i as u8;
1027         }
1028     }
1029     let result = [0, 0, 0, 1, 1, 1, 2];
1030     assert!(v == result);
1031 }
1032
1033 #[test]
1034 fn test_mut_chunks_rev() {
1035     let mut v = [0, 1, 2, 3, 4, 5, 6];
1036     for (i, chunk) in v.chunks_mut(3).rev().enumerate() {
1037         for x in chunk {
1038             *x = i as u8;
1039         }
1040     }
1041     let result = [2, 2, 2, 1, 1, 1, 0];
1042     assert!(v == result);
1043 }
1044
1045 #[test]
1046 #[should_panic]
1047 fn test_mut_chunks_0() {
1048     let mut v = [1, 2, 3, 4];
1049     let _it = v.chunks_mut(0);
1050 }
1051
1052 #[test]
1053 fn test_mut_last() {
1054     let mut x = [1, 2, 3, 4, 5];
1055     let h = x.last_mut();
1056     assert_eq!(*h.unwrap(), 5);
1057
1058     let y: &mut [i32] = &mut [];
1059     assert!(y.last_mut().is_none());
1060 }
1061
1062 #[test]
1063 fn test_to_vec() {
1064     let xs: Box<_> = box [1, 2, 3];
1065     let ys = xs.to_vec();
1066     assert_eq!(ys, [1, 2, 3]);
1067 }
1068
1069 #[test]
1070 fn test_box_slice_clone() {
1071     let data = vec![vec![0, 1], vec![0], vec![1]];
1072     let data2 = data.clone().into_boxed_slice().clone().to_vec();
1073
1074     assert_eq!(data, data2);
1075 }
1076
1077 #[test]
1078 #[cfg_attr(target_os = "emscripten", ignore)]
1079 fn test_box_slice_clone_panics() {
1080     use std::sync::Arc;
1081     use std::sync::atomic::{AtomicUsize, Ordering};
1082     use std::thread::spawn;
1083
1084     struct Canary {
1085         count: Arc<AtomicUsize>,
1086         panics: bool,
1087     }
1088
1089     impl Drop for Canary {
1090         fn drop(&mut self) {
1091             self.count.fetch_add(1, Ordering::SeqCst);
1092         }
1093     }
1094
1095     impl Clone for Canary {
1096         fn clone(&self) -> Self {
1097             if self.panics {
1098                 panic!()
1099             }
1100
1101             Canary {
1102                 count: self.count.clone(),
1103                 panics: self.panics,
1104             }
1105         }
1106     }
1107
1108     let drop_count = Arc::new(AtomicUsize::new(0));
1109     let canary = Canary {
1110         count: drop_count.clone(),
1111         panics: false,
1112     };
1113     let panic = Canary {
1114         count: drop_count.clone(),
1115         panics: true,
1116     };
1117
1118     spawn(move || {
1119             // When xs is dropped, +5.
1120             let xs = vec![canary.clone(), canary.clone(), canary.clone(), panic, canary]
1121                 .into_boxed_slice();
1122
1123             // When panic is cloned, +3.
1124             xs.clone();
1125         })
1126         .join()
1127         .unwrap_err();
1128
1129     // Total = 8
1130     assert_eq!(drop_count.load(Ordering::SeqCst), 8);
1131 }
1132
1133 #[test]
1134 fn test_copy_from_slice() {
1135     let src = [0, 1, 2, 3, 4, 5];
1136     let mut dst = [0; 6];
1137     dst.copy_from_slice(&src);
1138     assert_eq!(src, dst)
1139 }
1140
1141 #[test]
1142 #[should_panic(expected = "destination and source slices have different lengths")]
1143 fn test_copy_from_slice_dst_longer() {
1144     let src = [0, 1, 2, 3];
1145     let mut dst = [0; 5];
1146     dst.copy_from_slice(&src);
1147 }
1148
1149 #[test]
1150 #[should_panic(expected = "destination and source slices have different lengths")]
1151 fn test_copy_from_slice_dst_shorter() {
1152     let src = [0, 1, 2, 3];
1153     let mut dst = [0; 3];
1154     dst.copy_from_slice(&src);
1155 }
1156
1157 mod bench {
1158     use std::{mem, ptr};
1159     use std::__rand::{Rng, thread_rng};
1160
1161     use test::{Bencher, black_box};
1162
1163     #[bench]
1164     fn iterator(b: &mut Bencher) {
1165         // peculiar numbers to stop LLVM from optimising the summation
1166         // out.
1167         let v: Vec<_> = (0..100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect();
1168
1169         b.iter(|| {
1170             let mut sum = 0;
1171             for x in &v {
1172                 sum += *x;
1173             }
1174             // sum == 11806, to stop dead code elimination.
1175             if sum == 0 {
1176                 panic!()
1177             }
1178         })
1179     }
1180
1181     #[bench]
1182     fn mut_iterator(b: &mut Bencher) {
1183         let mut v = vec![0; 100];
1184
1185         b.iter(|| {
1186             let mut i = 0;
1187             for x in &mut v {
1188                 *x = i;
1189                 i += 1;
1190             }
1191         })
1192     }
1193
1194     #[bench]
1195     fn concat(b: &mut Bencher) {
1196         let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
1197         b.iter(|| {
1198             xss.concat();
1199         });
1200     }
1201
1202     #[bench]
1203     fn join(b: &mut Bencher) {
1204         let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
1205         b.iter(|| xss.join(&0));
1206     }
1207
1208     #[bench]
1209     fn push(b: &mut Bencher) {
1210         let mut vec = Vec::<i32>::new();
1211         b.iter(|| {
1212             vec.push(0);
1213             black_box(&vec);
1214         });
1215     }
1216
1217     #[bench]
1218     fn starts_with_same_vector(b: &mut Bencher) {
1219         let vec: Vec<_> = (0..100).collect();
1220         b.iter(|| vec.starts_with(&vec))
1221     }
1222
1223     #[bench]
1224     fn starts_with_single_element(b: &mut Bencher) {
1225         let vec: Vec<_> = vec![0];
1226         b.iter(|| vec.starts_with(&vec))
1227     }
1228
1229     #[bench]
1230     fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
1231         let vec: Vec<_> = (0..100).collect();
1232         let mut match_vec: Vec<_> = (0..99).collect();
1233         match_vec.push(0);
1234         b.iter(|| vec.starts_with(&match_vec))
1235     }
1236
1237     #[bench]
1238     fn ends_with_same_vector(b: &mut Bencher) {
1239         let vec: Vec<_> = (0..100).collect();
1240         b.iter(|| vec.ends_with(&vec))
1241     }
1242
1243     #[bench]
1244     fn ends_with_single_element(b: &mut Bencher) {
1245         let vec: Vec<_> = vec![0];
1246         b.iter(|| vec.ends_with(&vec))
1247     }
1248
1249     #[bench]
1250     fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
1251         let vec: Vec<_> = (0..100).collect();
1252         let mut match_vec: Vec<_> = (0..100).collect();
1253         match_vec[0] = 200;
1254         b.iter(|| vec.starts_with(&match_vec))
1255     }
1256
1257     #[bench]
1258     fn contains_last_element(b: &mut Bencher) {
1259         let vec: Vec<_> = (0..100).collect();
1260         b.iter(|| vec.contains(&99))
1261     }
1262
1263     #[bench]
1264     fn zero_1kb_from_elem(b: &mut Bencher) {
1265         b.iter(|| vec![0u8; 1024]);
1266     }
1267
1268     #[bench]
1269     fn zero_1kb_set_memory(b: &mut Bencher) {
1270         b.iter(|| {
1271             let mut v = Vec::<u8>::with_capacity(1024);
1272             unsafe {
1273                 let vp = v.as_mut_ptr();
1274                 ptr::write_bytes(vp, 0, 1024);
1275                 v.set_len(1024);
1276             }
1277             v
1278         });
1279     }
1280
1281     #[bench]
1282     fn zero_1kb_loop_set(b: &mut Bencher) {
1283         b.iter(|| {
1284             let mut v = Vec::<u8>::with_capacity(1024);
1285             unsafe {
1286                 v.set_len(1024);
1287             }
1288             for i in 0..1024 {
1289                 v[i] = 0;
1290             }
1291         });
1292     }
1293
1294     #[bench]
1295     fn zero_1kb_mut_iter(b: &mut Bencher) {
1296         b.iter(|| {
1297             let mut v = Vec::<u8>::with_capacity(1024);
1298             unsafe {
1299                 v.set_len(1024);
1300             }
1301             for x in &mut v {
1302                 *x = 0;
1303             }
1304             v
1305         });
1306     }
1307
1308     #[bench]
1309     fn random_inserts(b: &mut Bencher) {
1310         let mut rng = thread_rng();
1311         b.iter(|| {
1312             let mut v = vec![(0, 0); 30];
1313             for _ in 0..100 {
1314                 let l = v.len();
1315                 v.insert(rng.gen::<usize>() % (l + 1), (1, 1));
1316             }
1317         })
1318     }
1319     #[bench]
1320     fn random_removes(b: &mut Bencher) {
1321         let mut rng = thread_rng();
1322         b.iter(|| {
1323             let mut v = vec![(0, 0); 130];
1324             for _ in 0..100 {
1325                 let l = v.len();
1326                 v.remove(rng.gen::<usize>() % l);
1327             }
1328         })
1329     }
1330
1331     #[bench]
1332     fn sort_random_small(b: &mut Bencher) {
1333         let mut rng = thread_rng();
1334         b.iter(|| {
1335             let mut v: Vec<_> = rng.gen_iter::<u64>().take(5).collect();
1336             v.sort();
1337         });
1338         b.bytes = 5 * mem::size_of::<u64>() as u64;
1339     }
1340
1341     #[bench]
1342     fn sort_random_medium(b: &mut Bencher) {
1343         let mut rng = thread_rng();
1344         b.iter(|| {
1345             let mut v: Vec<_> = rng.gen_iter::<u64>().take(100).collect();
1346             v.sort();
1347         });
1348         b.bytes = 100 * mem::size_of::<u64>() as u64;
1349     }
1350
1351     #[bench]
1352     fn sort_random_large(b: &mut Bencher) {
1353         let mut rng = thread_rng();
1354         b.iter(|| {
1355             let mut v: Vec<_> = rng.gen_iter::<u64>().take(10000).collect();
1356             v.sort();
1357         });
1358         b.bytes = 10000 * mem::size_of::<u64>() as u64;
1359     }
1360
1361     #[bench]
1362     fn sort_sorted(b: &mut Bencher) {
1363         let mut v: Vec<_> = (0..10000).collect();
1364         b.iter(|| {
1365             v.sort();
1366         });
1367         b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
1368     }
1369
1370     type BigSortable = (u64, u64, u64, u64);
1371
1372     #[bench]
1373     fn sort_big_random_small(b: &mut Bencher) {
1374         let mut rng = thread_rng();
1375         b.iter(|| {
1376             let mut v = rng.gen_iter::<BigSortable>()
1377                 .take(5)
1378                 .collect::<Vec<BigSortable>>();
1379             v.sort();
1380         });
1381         b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
1382     }
1383
1384     #[bench]
1385     fn sort_big_random_medium(b: &mut Bencher) {
1386         let mut rng = thread_rng();
1387         b.iter(|| {
1388             let mut v = rng.gen_iter::<BigSortable>()
1389                 .take(100)
1390                 .collect::<Vec<BigSortable>>();
1391             v.sort();
1392         });
1393         b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
1394     }
1395
1396     #[bench]
1397     fn sort_big_random_large(b: &mut Bencher) {
1398         let mut rng = thread_rng();
1399         b.iter(|| {
1400             let mut v = rng.gen_iter::<BigSortable>()
1401                 .take(10000)
1402                 .collect::<Vec<BigSortable>>();
1403             v.sort();
1404         });
1405         b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
1406     }
1407
1408     #[bench]
1409     fn sort_big_sorted(b: &mut Bencher) {
1410         let mut v: Vec<BigSortable> = (0..10000).map(|i| (i, i, i, i)).collect();
1411         b.iter(|| {
1412             v.sort();
1413         });
1414         b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
1415     }
1416 }