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::default::Default;
  13 use std::iter::RandomAccessIterator;
  14 use std::mem;
  15 use std::__rand::{Rng, thread_rng};
  16 use std::rc::Rc;
  17 use std::slice::ElementSwaps;
  18
  19 fn square(n: usize) -> usize { n * n }
  20
  21 fn is_odd(n: &usize) -> bool { *n % 2 == 1 }
  22
  23 #[test]
  24 fn test_from_fn() {
  25     // Test on-stack from_fn.
  26     let mut v: Vec<_> = (0..3).map(square).collect();
  27     {
  28         let v = v;
  29         assert_eq!(v.len(), 3);
  30         assert_eq!(v[0], 0);
  31         assert_eq!(v[1], 1);
  32         assert_eq!(v[2], 4);
  33     }
  34
  35     // Test on-heap from_fn.
  36     v = (0..5).map(square).collect();
  37     {
  38         let v = v;
  39         assert_eq!(v.len(), 5);
  40         assert_eq!(v[0], 0);
  41         assert_eq!(v[1], 1);
  42         assert_eq!(v[2], 4);
  43         assert_eq!(v[3], 9);
  44         assert_eq!(v[4], 16);
  45     }
  46 }
  47
  48 #[test]
  49 fn test_from_elem() {
  50     // Test on-stack from_elem.
  51     let mut v = vec![10, 10];
  52     {
  53         let v = v;
  54         assert_eq!(v.len(), 2);
  55         assert_eq!(v[0], 10);
  56         assert_eq!(v[1], 10);
  57     }
  58
  59     // Test on-heap from_elem.
  60     v = vec![20; 6];
  61     {
  62         let v = &v[..];
  63         assert_eq!(v[0], 20);
  64         assert_eq!(v[1], 20);
  65         assert_eq!(v[2], 20);
  66         assert_eq!(v[3], 20);
  67         assert_eq!(v[4], 20);
  68         assert_eq!(v[5], 20);
  69     }
  70 }
  71
  72 #[test]
  73 fn test_is_empty() {
  74     let xs: [i32; 0] = [];
  75     assert!(xs.is_empty());
  76     assert!(![0].is_empty());
  77 }
  78
  79 #[test]
  80 fn test_len_divzero() {
  81     type Z = [i8; 0];
  82     let v0 : &[Z] = &[];
  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);
  89 }
  90
  91 #[test]
  92 fn test_get() {
  93     let mut a = vec![11];
  94     assert_eq!(a.get(1), None);
  95     a = vec![11, 12];
  96     assert_eq!(a.get(1).unwrap(), &12);
  97     a = vec![11, 12, 13];
  98     assert_eq!(a.get(1).unwrap(), &12);
  99 }
 100
 101 #[test]
 102 fn test_first() {
 103     let mut a = vec![];
 104     assert_eq!(a.first(), None);
 105     a = vec![11];
 106     assert_eq!(a.first().unwrap(), &11);
 107     a = vec![11, 12];
 108     assert_eq!(a.first().unwrap(), &11);
 109 }
 110
 111 #[test]
 112 fn test_first_mut() {
 113     let mut a = vec![];
 114     assert_eq!(a.first_mut(), None);
 115     a = vec![11];
 116     assert_eq!(*a.first_mut().unwrap(), 11);
 117     a = vec![11, 12];
 118     assert_eq!(*a.first_mut().unwrap(), 11);
 119 }
 120
 121 #[test]
 122 fn test_split_first() {
 123     let mut a = vec![11];
 124     let b: &[i32] = &[];
 125     assert!(b.split_first().is_none());
 126     assert_eq!(a.split_first(), Some((&11, b)));
 127     a = vec![11, 12];
 128     let b: &[i32] = &[12];
 129     assert_eq!(a.split_first(), Some((&11, b)));
 130 }
 131
 132 #[test]
 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)));
 138     a = vec![11, 12];
 139     let b: &mut [_] = &mut [12];
 140     assert!(a.split_first_mut() == Some((&mut 11, b)));
 141 }
 142
 143 #[test]
 144 fn test_split_last() {
 145     let mut a = vec![11];
 146     let b: &[i32] = &[];
 147     assert!(b.split_last().is_none());
 148     assert_eq!(a.split_last(), Some((&11, b)));
 149     a = vec![11, 12];
 150     let b: &[_] = &[11];
 151     assert_eq!(a.split_last(), Some((&12, b)));
 152 }
 153
 154 #[test]
 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)));
 160
 161     a = vec![11, 12];
 162     let b: &mut [_] = &mut [11];
 163     assert!(a.split_last_mut() == Some((&mut 12, b)));
 164 }
 165
 166 #[test]
 167 fn test_last() {
 168     let mut a = vec![];
 169     assert_eq!(a.last(), None);
 170     a = vec![11];
 171     assert_eq!(a.last().unwrap(), &11);
 172     a = vec![11, 12];
 173     assert_eq!(a.last().unwrap(), &12);
 174 }
 175
 176 #[test]
 177 fn test_last_mut() {
 178     let mut a = vec![];
 179     assert_eq!(a.last_mut(), None);
 180     a = vec![11];
 181     assert_eq!(*a.last_mut().unwrap(), 11);
 182     a = vec![11, 12];
 183     assert_eq!(*a.last_mut().unwrap(), 12);
 184 }
 185
 186 #[test]
 187 fn test_slice() {
 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);
 192
 193     assert_eq!(v_a[0], 2);
 194     assert_eq!(v_a[1], 3);
 195     assert_eq!(v_a[2], 4);
 196
 197     // Test on stack.
 198     let vec_stack: &[_] = &[1, 2, 3];
 199     let v_b = vec_stack[1..3].to_vec();
 200     assert_eq!(v_b.len(), 2);
 201
 202     assert_eq!(v_b[0], 2);
 203     assert_eq!(v_b[1], 3);
 204
 205     // Test `Box<[T]>`
 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);
 209
 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);
 215 }
 216
 217 #[test]
 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);
 223     let b: &[_] = &[];
 224     assert_eq!(&vec[4..], b);
 225 }
 226
 227 #[test]
 228 fn test_slice_to() {
 229     let vec: &[_] = &[1, 2, 3, 4];
 230     assert_eq!(&vec[..4], vec);
 231     let b: &[_] = &[1, 2];
 232     assert_eq!(&vec[..2], b);
 233     let b: &[_] = &[];
 234     assert_eq!(&vec[..0], b);
 235 }
 236
 237
 238 #[test]
 239 fn test_pop() {
 240     let mut v = vec![5];
 241     let e = v.pop();
 242     assert_eq!(v.len(), 0);
 243     assert_eq!(e, Some(5));
 244     let f = v.pop();
 245     assert_eq!(f, None);
 246     let g = v.pop();
 247     assert_eq!(g, None);
 248 }
 249
 250 #[test]
 251 fn test_swap_remove() {
 252     let mut v = vec![1, 2, 3, 4, 5];
 253     let mut e = v.swap_remove(0);
 254     assert_eq!(e, 1);
 255     assert_eq!(v, [5, 2, 3, 4]);
 256     e = v.swap_remove(3);
 257     assert_eq!(e, 4);
 258     assert_eq!(v, [5, 2, 3]);
 259 }
 260
 261 #[test]
 262 #[should_panic]
 263 fn test_swap_remove_fail() {
 264     let mut v = vec![1];
 265     let _ = v.swap_remove(0);
 266     let _ = v.swap_remove(0);
 267 }
 268
 269 #[test]
 270 fn test_swap_remove_noncopyable() {
 271     // Tests that we don't accidentally run destructors twice.
 272     let mut v: Vec<Box<_>> = Vec::new();
 273     v.push(box 0u8);
 274     v.push(box 0u8);
 275     v.push(box 0u8);
 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);
 282 }
 283
 284 #[test]
 285 fn test_push() {
 286     // Test on-stack push().
 287     let mut v = vec![];
 288     v.push(1);
 289     assert_eq!(v.len(), 1);
 290     assert_eq!(v[0], 1);
 291
 292     // Test on-heap push().
 293     v.push(2);
 294     assert_eq!(v.len(), 2);
 295     assert_eq!(v[0], 1);
 296     assert_eq!(v[1], 2);
 297 }
 298
 299 #[test]
 300 fn test_truncate() {
 301     let mut v: Vec<Box<_>> = vec![box 6,box 5,box 4];
 302     v.truncate(1);
 303     let v = v;
 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.
 307 }
 308
 309 #[test]
 310 fn test_clear() {
 311     let mut v: Vec<Box<_>> = vec![box 6,box 5,box 4];
 312     v.clear();
 313     assert_eq!(v.len(), 0);
 314     // If the unsafe block didn't drop things properly, we blow up here.
 315 }
 316
 317 #[test]
 318 fn test_dedup() {
 319     fn case(a: Vec<i32>, b: Vec<i32>) {
 320         let mut v = a;
 321         v.dedup();
 322         assert_eq!(v, b);
 323     }
 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]);
 332 }
 333
 334 #[test]
 335 fn test_dedup_unique() {
 336     let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
 337     v0.dedup();
 338     let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
 339     v1.dedup();
 340     let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
 341     v2.dedup();
 342     /*
 343      * If the boxed pointers were leaked or otherwise misused, valgrind
 344      * and/or rt should raise errors.
 345      */
 346 }
 347
 348 #[test]
 349 fn test_dedup_shared() {
 350     let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
 351     v0.dedup();
 352     let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
 353     v1.dedup();
 354     let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
 355     v2.dedup();
 356     /*
 357      * If the pointers were leaked or otherwise misused, valgrind and/or
 358      * rt should raise errors.
 359      */
 360 }
 361
 362 #[test]
 363 fn test_retain() {
 364     let mut v = vec![1, 2, 3, 4, 5];
 365     v.retain(is_odd);
 366     assert_eq!(v, [1, 3, 5]);
 367 }
 368
 369 #[test]
 370 fn test_element_swaps() {
 371     let mut v = [1, 2, 3];
 372     for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
 373         v.swap(a, b);
 374         match i {
 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]),
 381             _ => panic!(),
 382         }
 383     }
 384 }
 385
 386 #[test]
 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];
 392     assert!(v == b);
 393     assert!(v.prev_permutation());
 394     let b: &mut[_] = &mut[1, 2, 3, 4, 5];
 395     assert!(v == b);
 396     assert!(v.next_permutation());
 397     assert!(v.next_permutation());
 398     let b: &mut[_] = &mut[1, 2, 4, 3, 5];
 399     assert!(v == b);
 400     assert!(v.next_permutation());
 401     let b: &mut[_] = &mut[1, 2, 4, 5, 3];
 402     assert!(v == b);
 403
 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];
 408     assert!(v == b);
 409     assert!(v.prev_permutation());
 410     let b: &mut[_] = &mut[0, 0, 1, 0];
 411     assert!(v == b);
 412     assert!(v.prev_permutation());
 413     let b: &mut[_] = &mut[0, 0, 0, 1];
 414     assert!(v == b);
 415     assert!(v.prev_permutation() == false);
 416 }
 417
 418 #[test]
 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[];
 423     assert!(empty == b);
 424     assert!(empty.prev_permutation() == false);
 425     assert!(empty == b);
 426
 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);
 433
 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);
 447 }
 448
 449 #[test]
 450 fn test_position_elem() {
 451     assert!([].position_elem(&1).is_none());
 452
 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());
 458 }
 459
 460 #[test]
 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));
 467
 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));
 472
 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));
 477
 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));
 482
 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));
 487
 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));
 491
 492     assert_eq!([].binary_search(&1).ok(), None);
 493     assert_eq!([].binary_search(&5).ok(), None);
 494
 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));
 500
 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);
 503 }
 504
 505 #[test]
 506 fn test_reverse() {
 507     let mut v = vec![10, 20];
 508     assert_eq!(v[0], 10);
 509     assert_eq!(v[1], 20);
 510     v.reverse();
 511     assert_eq!(v[0], 20);
 512     assert_eq!(v[1], 10);
 513
 514     let mut v3 = Vec::<i32>::new();
 515     v3.reverse();
 516     assert!(v3.is_empty());
 517 }
 518
 519 #[test]
 520 fn test_sort() {
 521     for len in 4..25 {
 522         for _ in 0..100 {
 523             let mut v: Vec<_> = thread_rng().gen_iter::<i32>().take(len).collect();
 524             let mut v1 = v.clone();
 525
 526             v.sort();
 527             assert!(v.windows(2).all(|w| w[0] <= w[1]));
 528
 529             v1.sort_by(|a, b| a.cmp(b));
 530             assert!(v1.windows(2).all(|w| w[0] <= w[1]));
 531
 532             v1.sort_by(|a, b| b.cmp(a));
 533             assert!(v1.windows(2).all(|w| w[0] >= w[1]));
 534         }
 535     }
 536
 537     // shouldn't panic
 538     let mut v: [i32; 0] = [];
 539     v.sort();
 540
 541     let mut v = [0xDEADBEEFu64];
 542     v.sort();
 543     assert!(v == [0xDEADBEEF]);
 544 }
 545
 546 #[test]
 547 fn test_sort_stability() {
 548     for len in 4..25 {
 549         for _ in 0..10 {
 550             let mut counts = [0; 10];
 551
 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;
 559                     counts[n] += 1;
 560                     (n, counts[n])
 561                 }).collect();
 562
 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));
 566
 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
 571             // stable.
 572             assert!(v.windows(2).all(|w| w[0] <= w[1]));
 573         }
 574     }
 575 }
 576
 577 #[test]
 578 fn test_concat() {
 579     let v: [Vec<i32>; 0] = [];
 580     let c = v.concat();
 581     assert_eq!(c, []);
 582     let d = [vec![1], vec![2, 3]].concat();
 583     assert_eq!(d, [1, 2, 3]);
 584
 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]);
 589 }
 590
 591 #[test]
 592 fn test_join() {
 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]);
 597
 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]);
 602 }
 603
 604 #[test]
 605 fn test_insert() {
 606     let mut a = vec![1, 2, 4];
 607     a.insert(2, 3);
 608     assert_eq!(a, [1, 2, 3, 4]);
 609
 610     let mut a = vec![1, 2, 3];
 611     a.insert(0, 0);
 612     assert_eq!(a, [0, 1, 2, 3]);
 613
 614     let mut a = vec![1, 2, 3];
 615     a.insert(3, 4);
 616     assert_eq!(a, [1, 2, 3, 4]);
 617
 618     let mut a = vec![];
 619     a.insert(0, 1);
 620     assert_eq!(a, [1]);
 621 }
 622
 623 #[test]
 624 #[should_panic]
 625 fn test_insert_oob() {
 626     let mut a = vec![1, 2, 3];
 627     a.insert(4, 5);
 628 }
 629
 630 #[test]
 631 fn test_remove() {
 632     let mut a = vec![1, 2, 3, 4];
 633
 634     assert_eq!(a.remove(2), 3);
 635     assert_eq!(a, [1, 2, 4]);
 636
 637     assert_eq!(a.remove(2), 4);
 638     assert_eq!(a, [1, 2]);
 639
 640     assert_eq!(a.remove(0), 1);
 641     assert_eq!(a, [2]);
 642
 643     assert_eq!(a.remove(0), 2);
 644     assert_eq!(a, []);
 645 }
 646
 647 #[test]
 648 #[should_panic]
 649 fn test_remove_fail() {
 650     let mut a = vec![1];
 651     let _ = a.remove(0);
 652     let _ = a.remove(0);
 653 }
 654
 655 #[test]
 656 fn test_capacity() {
 657     let mut v = vec![0];
 658     v.reserve_exact(10);
 659     assert!(v.capacity() >= 11);
 660 }
 661
 662 #[test]
 663 fn test_slice_2() {
 664     let v = vec![1, 2, 3, 4, 5];
 665     let v = &v[1..3];
 666     assert_eq!(v.len(), 2);
 667     assert_eq!(v[0], 2);
 668     assert_eq!(v[1], 3);
 669 }
 670
 671 #[test]
 672 #[should_panic]
 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))];
 677     let mut i = 0;
 678     for _ in v.permutations() {
 679         if i == 2 {
 680             panic!()
 681         }
 682         i += 1;
 683     }
 684 }
 685
 686 #[test]
 687 fn test_total_ord() {
 688     let c = &[1, 2, 3];
 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;
 698 }
 699
 700 #[test]
 701 fn test_iterator() {
 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());
 716 }
 717
 718 #[test]
 719 fn test_random_access_iterator() {
 720     let xs = [1, 2, 5, 10, 11];
 721     let mut it = xs.iter();
 722
 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());
 728
 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());
 734
 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());
 739
 740     assert_eq!(it.next().unwrap(), &5);
 741     assert_eq!(it.indexable(), 2);
 742     assert_eq!(it.idx(1).unwrap(), &11);
 743
 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());
 748
 749     assert_eq!(it.next().unwrap(), &11);
 750     assert_eq!(it.indexable(), 0);
 751     assert!(it.idx(0).is_none());
 752
 753     assert!(it.next().is_none());
 754 }
 755
 756 #[test]
 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)));
 761 }
 762
 763 #[test]
 764 fn test_iter_clone() {
 765     let xs = [1, 2, 5];
 766     let mut it = xs.iter();
 767     it.next();
 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());
 772 }
 773
 774 #[test]
 775 fn test_mut_iterator() {
 776     let mut xs = [1, 2, 3, 4, 5];
 777     for x in &mut xs {
 778         *x += 1;
 779     }
 780     assert!(xs == [2, 3, 4, 5, 6])
 781 }
 782
 783 #[test]
 784 fn test_rev_iterator() {
 785
 786     let xs = [1, 2, 5, 10, 11];
 787     let ys = [11, 10, 5, 2, 1];
 788     let mut i = 0;
 789     for &x in xs.iter().rev() {
 790         assert_eq!(x, ys[i]);
 791         i += 1;
 792     }
 793     assert_eq!(i, 5);
 794 }
 795
 796 #[test]
 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() {
 800         *x += i;
 801     }
 802     assert!(xs == [5, 5, 5, 5, 5])
 803 }
 804
 805 #[test]
 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);
 809 }
 810
 811 #[test]
 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);
 815 }
 816
 817 #[test]
 818 fn test_splitator() {
 819     let xs = &[1,2,3,4,5];
 820
 821     let splits: &[&[_]] = &[&[1], &[3], &[5]];
 822     assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<_>>(),
 823                splits);
 824     let splits: &[&[_]] = &[&[], &[2,3,4,5]];
 825     assert_eq!(xs.split(|x| *x == 1).collect::<Vec<_>>(),
 826                splits);
 827     let splits: &[&[_]] = &[&[1,2,3,4], &[]];
 828     assert_eq!(xs.split(|x| *x == 5).collect::<Vec<_>>(),
 829                splits);
 830     let splits: &[&[_]] = &[&[1,2,3,4,5]];
 831     assert_eq!(xs.split(|x| *x == 10).collect::<Vec<_>>(),
 832                splits);
 833     let splits: &[&[_]] = &[&[], &[], &[], &[], &[], &[]];
 834     assert_eq!(xs.split(|_| true).collect::<Vec<&[i32]>>(),
 835                splits);
 836
 837     let xs: &[i32] = &[];
 838     let splits: &[&[i32]] = &[&[]];
 839     assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[i32]>>(), splits);
 840 }
 841
 842 #[test]
 843 fn test_splitnator() {
 844     let xs = &[1,2,3,4,5];
 845
 846     let splits: &[&[_]] = &[&[1,2,3,4,5]];
 847     assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
 848                splits);
 849     let splits: &[&[_]] = &[&[1], &[3,4,5]];
 850     assert_eq!(xs.splitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
 851                splits);
 852     let splits: &[&[_]] = &[&[], &[], &[], &[4,5]];
 853     assert_eq!(xs.splitn(4, |_| true).collect::<Vec<_>>(),
 854                splits);
 855
 856     let xs: &[i32] = &[];
 857     let splits: &[&[i32]] = &[&[]];
 858     assert_eq!(xs.splitn(2, |x| *x == 5).collect::<Vec<_>>(), splits);
 859 }
 860
 861 #[test]
 862 fn test_splitnator_mut() {
 863     let xs = &mut [1,2,3,4,5];
 864
 865     let splits: &[&mut[_]] = &[&mut [1,2,3,4,5]];
 866     assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
 867                splits);
 868     let splits: &[&mut[_]] = &[&mut [1], &mut [3,4,5]];
 869     assert_eq!(xs.splitn_mut(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
 870                splits);
 871     let splits: &[&mut[_]] = &[&mut [], &mut [], &mut [], &mut [4,5]];
 872     assert_eq!(xs.splitn_mut(4, |_| true).collect::<Vec<_>>(),
 873                splits);
 874
 875     let xs: &mut [i32] = &mut [];
 876     let splits: &[&mut[i32]] = &[&mut []];
 877     assert_eq!(xs.splitn_mut(2, |x| *x == 5).collect::<Vec<_>>(),
 878                splits);
 879 }
 880
 881 #[test]
 882 fn test_rsplitator() {
 883     let xs = &[1,2,3,4,5];
 884
 885     let splits: &[&[_]] = &[&[5], &[3], &[1]];
 886     assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<_>>(),
 887                splits);
 888     let splits: &[&[_]] = &[&[2,3,4,5], &[]];
 889     assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<_>>(),
 890                splits);
 891     let splits: &[&[_]] = &[&[], &[1,2,3,4]];
 892     assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<_>>(),
 893                splits);
 894     let splits: &[&[_]] = &[&[1,2,3,4,5]];
 895     assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<_>>(),
 896                splits);
 897
 898     let xs: &[i32] = &[];
 899     let splits: &[&[i32]] = &[&[]];
 900     assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[i32]>>(), splits);
 901 }
 902
 903 #[test]
 904 fn test_rsplitnator() {
 905     let xs = &[1,2,3,4,5];
 906
 907     let splits: &[&[_]] = &[&[1,2,3,4,5]];
 908     assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
 909                splits);
 910     let splits: &[&[_]] = &[&[5], &[1,2,3]];
 911     assert_eq!(xs.rsplitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
 912                splits);
 913     let splits: &[&[_]] = &[&[], &[], &[], &[1,2]];
 914     assert_eq!(xs.rsplitn(4, |_| true).collect::<Vec<_>>(),
 915                splits);
 916
 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());
 921 }
 922
 923 #[test]
 924 fn test_windowsator() {
 925     let v = &[1,2,3,4];
 926
 927     let wins: &[&[_]] = &[&[1,2], &[2,3], &[3,4]];
 928     assert_eq!(v.windows(2).collect::<Vec<_>>(), wins);
 929
 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());
 933
 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);
 945 }
 946
 947 #[test]
 948 #[should_panic]
 949 fn test_windowsator_0() {
 950     let v = &[1,2,3,4];
 951     let _it = v.windows(0);
 952 }
 953
 954 #[test]
 955 fn test_chunksator() {
 956     let v = &[1,2,3,4,5];
 957
 958     assert_eq!(v.chunks(2).len(), 3);
 959
 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);
 966
 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);
 971
 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);
 979 }
 980
 981 #[test]
 982 #[should_panic]
 983 fn test_chunksator_0() {
 984     let v = &[1,2,3,4];
 985     let _it = v.chunks(0);
 986 }
 987
 988 #[test]
 989 fn test_move_from() {
 990     let mut a = [1,2,3,4,5];
 991     let b = vec![6,7,8];
 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]);
1006 }
1007
1008 #[test]
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]);
1013 }
1014
1015 #[test]
1016 fn test_show() {
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);
1022         })
1023     }
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]]");
1030
1031     let empty_mut: &mut [i32] = &mut[];
1032     test_show_vec!(empty_mut, "[]");
1033     let v = &mut[1];
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]]");
1039 }
1040
1041 #[test]
1042 fn test_vec_default() {
1043     macro_rules! t {
1044         ($ty:ty) => {{
1045             let v: $ty = Default::default();
1046             assert!(v.is_empty());
1047         }}
1048     }
1049
1050     t!(&[i32]);
1051     t!(Vec<i32>);
1052 }
1053
1054 #[test]
1055 fn test_bytes_set_memory() {
1056     use std::slice::bytes::MutableByteVector;
1057
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]);
1063 }
1064
1065 #[test]
1066 #[should_panic]
1067 fn test_overflow_does_not_cause_segfault() {
1068     let mut v = vec![];
1069     v.reserve_exact(!0);
1070     v.push(1);
1071     v.push(2);
1072 }
1073
1074 #[test]
1075 #[should_panic]
1076 fn test_overflow_does_not_cause_segfault_managed() {
1077     let mut v = vec![Rc::new(1)];
1078     v.reserve_exact(!0);
1079     v.push(Rc::new(2));
1080 }
1081
1082 #[test]
1083 fn test_mut_split_at() {
1084     let mut values = [1u8,2,3,4,5];
1085     {
1086         let (left, right) = values.split_at_mut(2);
1087         {
1088             let left: &[_] = left;
1089             assert!(left[..left.len()] == [1, 2]);
1090         }
1091         for p in left {
1092             *p += 1;
1093         }
1094
1095         {
1096             let right: &[_] = right;
1097             assert!(right[..right.len()] == [3, 4, 5]);
1098         }
1099         for p in right {
1100             *p += 2;
1101         }
1102     }
1103
1104     assert!(values == [2, 3, 5, 6, 7]);
1105 }
1106
1107 #[derive(Clone, PartialEq)]
1108 struct Foo;
1109
1110 #[test]
1111 fn test_iter_zero_sized() {
1112     let mut v = vec![Foo, Foo, Foo];
1113     assert_eq!(v.len(), 3);
1114     let mut cnt = 0;
1115
1116     for f in &v {
1117         assert!(*f == Foo);
1118         cnt += 1;
1119     }
1120     assert_eq!(cnt, 3);
1121
1122     for f in &v[1..3] {
1123         assert!(*f == Foo);
1124         cnt += 1;
1125     }
1126     assert_eq!(cnt, 5);
1127
1128     for f in &mut v {
1129         assert!(*f == Foo);
1130         cnt += 1;
1131     }
1132     assert_eq!(cnt, 8);
1133
1134     for f in v {
1135         assert!(f == Foo);
1136         cnt += 1;
1137     }
1138     assert_eq!(cnt, 11);
1139
1140     let xs: [Foo; 3] = [Foo, Foo, Foo];
1141     cnt = 0;
1142     for f in &xs {
1143         assert!(*f == Foo);
1144         cnt += 1;
1145     }
1146     assert!(cnt == 3);
1147 }
1148
1149 #[test]
1150 fn test_shrink_to_fit() {
1151     let mut xs = vec![0, 1, 2, 3];
1152     for i in 4..100 {
1153         xs.push(i)
1154     }
1155     assert_eq!(xs.capacity(), 128);
1156     xs.shrink_to_fit();
1157     assert_eq!(xs.capacity(), 100);
1158     assert_eq!(xs, (0..100).collect::<Vec<_>>());
1159 }
1160
1161 #[test]
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));
1173 }
1174
1175 #[test]
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));
1187 }
1188
1189 #[test]
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) {
1194         slice.reverse();
1195     }
1196     assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
1197
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) {
1200         slice.reverse();
1201     }
1202     assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
1203 }
1204
1205 #[test]
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) {
1209         slice.reverse();
1210     }
1211     assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
1212 }
1213
1214 #[test]
1215 fn test_get_mut() {
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);
1220     let mut x = 2;
1221     assert_eq!(v.get_mut(2), Some(&mut x));
1222 }
1223
1224 #[test]
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() {
1229         for x in chunk {
1230             *x = i as u8;
1231         }
1232     }
1233     let result = [0, 0, 0, 1, 1, 1, 2];
1234     assert!(v == result);
1235 }
1236
1237 #[test]
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() {
1241         for x in chunk {
1242             *x = i as u8;
1243         }
1244     }
1245     let result = [2, 2, 2, 1, 1, 1, 0];
1246     assert!(v == result);
1247 }
1248
1249 #[test]
1250 #[should_panic]
1251 fn test_mut_chunks_0() {
1252     let mut v = [1, 2, 3, 4];
1253     let _it = v.chunks_mut(0);
1254 }
1255
1256 #[test]
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);
1261
1262     let y: &mut [i32] = &mut [];
1263     assert!(y.last_mut().is_none());
1264 }
1265
1266 #[test]
1267 fn test_to_vec() {
1268     let xs: Box<_> = box [1, 2, 3];
1269     let ys = xs.to_vec();
1270     assert_eq!(ys, [1, 2, 3]);
1271 }
1272
1273 #[test]
1274 fn test_box_slice_clone() {
1275     let data = vec![vec![0, 1], vec![0], vec![1]];
1276     let data2 = data.clone().into_boxed_slice().clone().to_vec();
1277
1278     assert_eq!(data, data2);
1279 }
1280
1281 #[test]
1282 fn test_box_slice_clone_panics() {
1283     use std::sync::Arc;
1284     use std::sync::atomic::{AtomicUsize, Ordering};
1285     use std::thread::spawn;
1286
1287     struct Canary {
1288         count: Arc<AtomicUsize>,
1289         panics: bool
1290     }
1291
1292     impl Drop for Canary {
1293         fn drop(&mut self) {
1294             self.count.fetch_add(1, Ordering::SeqCst);
1295         }
1296     }
1297
1298     impl Clone for Canary {
1299         fn clone(&self) -> Self {
1300             if self.panics { panic!() }
1301
1302             Canary {
1303                 count: self.count.clone(),
1304                 panics: self.panics
1305             }
1306         }
1307     }
1308
1309     let drop_count = Arc::new(AtomicUsize::new(0));
1310     let canary = Canary { count: drop_count.clone(), panics: false };
1311     let panic = Canary { count: drop_count.clone(), panics: true };
1312
1313     spawn(move || {
1314         // When xs is dropped, +5.
1315         let xs = vec![canary.clone(), canary.clone(), canary.clone(),
1316                       panic, canary].into_boxed_slice();
1317
1318         // When panic is cloned, +3.
1319         xs.clone();
1320     }).join().unwrap_err();
1321
1322     // Total = 8
1323     assert_eq!(drop_count.load(Ordering::SeqCst), 8);
1324 }
1325
1326 mod bench {
1327     use std::iter::repeat;
1328     use std::{mem, ptr};
1329     use std::__rand::{Rng, thread_rng};
1330
1331     use test::{Bencher, black_box};
1332
1333     #[bench]
1334     fn iterator(b: &mut Bencher) {
1335         // peculiar numbers to stop LLVM from optimising the summation
1336         // out.
1337         let v: Vec<_> = (0..100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect();
1338
1339         b.iter(|| {
1340             let mut sum = 0;
1341             for x in &v {
1342                 sum += *x;
1343             }
1344             // sum == 11806, to stop dead code elimination.
1345             if sum == 0 {panic!()}
1346         })
1347     }
1348
1349     #[bench]
1350     fn mut_iterator(b: &mut Bencher) {
1351         let mut v = vec![0; 100];
1352
1353         b.iter(|| {
1354             let mut i = 0;
1355             for x in &mut v {
1356                 *x = i;
1357                 i += 1;
1358             }
1359         })
1360     }
1361
1362     #[bench]
1363     fn concat(b: &mut Bencher) {
1364         let xss: Vec<Vec<i32>> =
1365             (0..100).map(|i| (0..i).collect()).collect();
1366         b.iter(|| {
1367             xss.concat();
1368         });
1369     }
1370
1371     #[bench]
1372     fn join(b: &mut Bencher) {
1373         let xss: Vec<Vec<i32>> =
1374             (0..100).map(|i| (0..i).collect()).collect();
1375         b.iter(|| {
1376             xss.join(&0)
1377         });
1378     }
1379
1380     #[bench]
1381     fn push(b: &mut Bencher) {
1382         let mut vec = Vec::<i32>::new();
1383         b.iter(|| {
1384             vec.push(0);
1385             black_box(&vec);
1386         });
1387     }
1388
1389     #[bench]
1390     fn starts_with_same_vector(b: &mut Bencher) {
1391         let vec: Vec<_> = (0..100).collect();
1392         b.iter(|| {
1393             vec.starts_with(&vec)
1394         })
1395     }
1396
1397     #[bench]
1398     fn starts_with_single_element(b: &mut Bencher) {
1399         let vec: Vec<_> = vec![0];
1400         b.iter(|| {
1401             vec.starts_with(&vec)
1402         })
1403     }
1404
1405     #[bench]
1406     fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
1407         let vec: Vec<_> = (0..100).collect();
1408         let mut match_vec: Vec<_> = (0..99).collect();
1409         match_vec.push(0);
1410         b.iter(|| {
1411             vec.starts_with(&match_vec)
1412         })
1413     }
1414
1415     #[bench]
1416     fn ends_with_same_vector(b: &mut Bencher) {
1417         let vec: Vec<_> = (0..100).collect();
1418         b.iter(|| {
1419             vec.ends_with(&vec)
1420         })
1421     }
1422
1423     #[bench]
1424     fn ends_with_single_element(b: &mut Bencher) {
1425         let vec: Vec<_> = vec![0];
1426         b.iter(|| {
1427             vec.ends_with(&vec)
1428         })
1429     }
1430
1431     #[bench]
1432     fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
1433         let vec: Vec<_> = (0..100).collect();
1434         let mut match_vec: Vec<_> = (0..100).collect();
1435         match_vec[0] = 200;
1436         b.iter(|| {
1437             vec.starts_with(&match_vec)
1438         })
1439     }
1440
1441     #[bench]
1442     fn contains_last_element(b: &mut Bencher) {
1443         let vec: Vec<_> = (0..100).collect();
1444         b.iter(|| {
1445             vec.contains(&99)
1446         })
1447     }
1448
1449     #[bench]
1450     fn zero_1kb_from_elem(b: &mut Bencher) {
1451         b.iter(|| {
1452             vec![0u8; 1024]
1453         });
1454     }
1455
1456     #[bench]
1457     fn zero_1kb_set_memory(b: &mut Bencher) {
1458         b.iter(|| {
1459             let mut v = Vec::<u8>::with_capacity(1024);
1460             unsafe {
1461                 let vp = v.as_mut_ptr();
1462                 ptr::write_bytes(vp, 0, 1024);
1463                 v.set_len(1024);
1464             }
1465             v
1466         });
1467     }
1468
1469     #[bench]
1470     fn zero_1kb_loop_set(b: &mut Bencher) {
1471         b.iter(|| {
1472             let mut v = Vec::<u8>::with_capacity(1024);
1473             unsafe {
1474                 v.set_len(1024);
1475             }
1476             for i in 0..1024 {
1477                 v[i] = 0;
1478             }
1479         });
1480     }
1481
1482     #[bench]
1483     fn zero_1kb_mut_iter(b: &mut Bencher) {
1484         b.iter(|| {
1485             let mut v = Vec::<u8>::with_capacity(1024);
1486             unsafe {
1487                 v.set_len(1024);
1488             }
1489             for x in &mut v {
1490                 *x = 0;
1491             }
1492             v
1493         });
1494     }
1495
1496     #[bench]
1497     fn random_inserts(b: &mut Bencher) {
1498         let mut rng = thread_rng();
1499         b.iter(|| {
1500             let mut v = vec![(0, 0); 30];
1501             for _ in 0..100 {
1502                 let l = v.len();
1503                 v.insert(rng.gen::<usize>() % (l + 1),
1504                          (1, 1));
1505             }
1506         })
1507     }
1508     #[bench]
1509     fn random_removes(b: &mut Bencher) {
1510         let mut rng = thread_rng();
1511         b.iter(|| {
1512             let mut v = vec![(0, 0); 130];
1513             for _ in 0..100 {
1514                 let l = v.len();
1515                 v.remove(rng.gen::<usize>() % l);
1516             }
1517         })
1518     }
1519
1520     #[bench]
1521     fn sort_random_small(b: &mut Bencher) {
1522         let mut rng = thread_rng();
1523         b.iter(|| {
1524             let mut v: Vec<_> = rng.gen_iter::<u64>().take(5).collect();
1525             v.sort();
1526         });
1527         b.bytes = 5 * mem::size_of::<u64>() as u64;
1528     }
1529
1530     #[bench]
1531     fn sort_random_medium(b: &mut Bencher) {
1532         let mut rng = thread_rng();
1533         b.iter(|| {
1534             let mut v: Vec<_> = rng.gen_iter::<u64>().take(100).collect();
1535             v.sort();
1536         });
1537         b.bytes = 100 * mem::size_of::<u64>() as u64;
1538     }
1539
1540     #[bench]
1541     fn sort_random_large(b: &mut Bencher) {
1542         let mut rng = thread_rng();
1543         b.iter(|| {
1544             let mut v: Vec<_> = rng.gen_iter::<u64>().take(10000).collect();
1545             v.sort();
1546         });
1547         b.bytes = 10000 * mem::size_of::<u64>() as u64;
1548     }
1549
1550     #[bench]
1551     fn sort_sorted(b: &mut Bencher) {
1552         let mut v: Vec<_> = (0..10000).collect();
1553         b.iter(|| {
1554             v.sort();
1555         });
1556         b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
1557     }
1558
1559     type BigSortable = (u64, u64, u64, u64);
1560
1561     #[bench]
1562     fn sort_big_random_small(b: &mut Bencher) {
1563         let mut rng = thread_rng();
1564         b.iter(|| {
1565             let mut v = rng.gen_iter::<BigSortable>().take(5)
1566                            .collect::<Vec<BigSortable>>();
1567             v.sort();
1568         });
1569         b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
1570     }
1571
1572     #[bench]
1573     fn sort_big_random_medium(b: &mut Bencher) {
1574         let mut rng = thread_rng();
1575         b.iter(|| {
1576             let mut v = rng.gen_iter::<BigSortable>().take(100)
1577                            .collect::<Vec<BigSortable>>();
1578             v.sort();
1579         });
1580         b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
1581     }
1582
1583     #[bench]
1584     fn sort_big_random_large(b: &mut Bencher) {
1585         let mut rng = thread_rng();
1586         b.iter(|| {
1587             let mut v = rng.gen_iter::<BigSortable>().take(10000)
1588                            .collect::<Vec<BigSortable>>();
1589             v.sort();
1590         });
1591         b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
1592     }
1593
1594     #[bench]
1595     fn sort_big_sorted(b: &mut Bencher) {
1596         let mut v: Vec<BigSortable> = (0..10000).map(|i| (i, i, i, i)).collect();
1597         b.iter(|| {
1598             v.sort();
1599         });
1600         b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
1601     }
1602 }