src/libcore/tests/slice.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use core::cmp::Ordering::{Equal, Greater, Less};
  12 use core::slice::heapsort;
  13 use core::result::Result::{Ok, Err};
  14 use rand::{Rng, XorShiftRng};
  15
  16 #[test]
  17 fn test_binary_search() {
  18     let b = [1, 2, 4, 6, 8, 9];
  19     assert!(b.binary_search_by(|v| v.cmp(&6)) == Ok(3));
  20     assert!(b.binary_search_by(|v| v.cmp(&5)) == Err(3));
  21     let b = [1, 2, 4, 6, 7, 8, 9];
  22     assert!(b.binary_search_by(|v| v.cmp(&6)) == Ok(3));
  23     assert!(b.binary_search_by(|v| v.cmp(&5)) == Err(3));
  24     let b = [1, 2, 4, 6, 8, 9];
  25     assert!(b.binary_search_by(|v| v.cmp(&8)) == Ok(4));
  26     assert!(b.binary_search_by(|v| v.cmp(&7)) == Err(4));
  27     let b = [1, 2, 4, 6, 7, 8, 9];
  28     assert!(b.binary_search_by(|v| v.cmp(&8)) == Ok(5));
  29     let b = [1, 2, 4, 5, 6, 8, 9];
  30     assert!(b.binary_search_by(|v| v.cmp(&7)) == Err(5));
  31     assert!(b.binary_search_by(|v| v.cmp(&0)) == Err(0));
  32     let b = [1, 2, 4, 5, 6, 8];
  33     assert!(b.binary_search_by(|v| v.cmp(&9)) == Err(6));
  34 }
  35
  36 #[test]
  37 fn test_iterator_nth() {
  38     let v: &[_] = &[0, 1, 2, 3, 4];
  39     for i in 0..v.len() {
  40         assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
  41     }
  42     assert_eq!(v.iter().nth(v.len()), None);
  43
  44     let mut iter = v.iter();
  45     assert_eq!(iter.nth(2).unwrap(), &v[2]);
  46     assert_eq!(iter.nth(1).unwrap(), &v[4]);
  47 }
  48
  49 #[test]
  50 fn test_iterator_last() {
  51     let v: &[_] = &[0, 1, 2, 3, 4];
  52     assert_eq!(v.iter().last().unwrap(), &4);
  53     assert_eq!(v[..1].iter().last().unwrap(), &0);
  54 }
  55
  56 #[test]
  57 fn test_iterator_count() {
  58     let v: &[_] = &[0, 1, 2, 3, 4];
  59     assert_eq!(v.iter().count(), 5);
  60
  61     let mut iter2 = v.iter();
  62     iter2.next();
  63     iter2.next();
  64     assert_eq!(iter2.count(), 3);
  65 }
  66
  67 #[test]
  68 fn test_chunks_count() {
  69     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
  70     let c = v.chunks(3);
  71     assert_eq!(c.count(), 2);
  72
  73     let v2: &[i32] = &[0, 1, 2, 3, 4];
  74     let c2 = v2.chunks(2);
  75     assert_eq!(c2.count(), 3);
  76
  77     let v3: &[i32] = &[];
  78     let c3 = v3.chunks(2);
  79     assert_eq!(c3.count(), 0);
  80 }
  81
  82 #[test]
  83 fn test_chunks_nth() {
  84     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
  85     let mut c = v.chunks(2);
  86     assert_eq!(c.nth(1).unwrap()[1], 3);
  87     assert_eq!(c.next().unwrap()[0], 4);
  88
  89     let v2: &[i32] = &[0, 1, 2, 3, 4];
  90     let mut c2 = v2.chunks(3);
  91     assert_eq!(c2.nth(1).unwrap()[1], 4);
  92     assert_eq!(c2.next(), None);
  93 }
  94
  95 #[test]
  96 fn test_chunks_last() {
  97     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
  98     let c = v.chunks(2);
  99     assert_eq!(c.last().unwrap()[1], 5);
 100
 101     let v2: &[i32] = &[0, 1, 2, 3, 4];
 102     let c2 = v2.chunks(2);
 103     assert_eq!(c2.last().unwrap()[0], 4);
 104 }
 105
 106 #[test]
 107 fn test_chunks_mut_count() {
 108     let mut v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 109     let c = v.chunks_mut(3);
 110     assert_eq!(c.count(), 2);
 111
 112     let mut v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 113     let c2 = v2.chunks_mut(2);
 114     assert_eq!(c2.count(), 3);
 115
 116     let mut v3: &mut [i32] = &mut [];
 117     let c3 = v3.chunks_mut(2);
 118     assert_eq!(c3.count(), 0);
 119 }
 120
 121 #[test]
 122 fn test_chunks_mut_nth() {
 123     let mut v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 124     let mut c = v.chunks_mut(2);
 125     assert_eq!(c.nth(1).unwrap()[1], 3);
 126     assert_eq!(c.next().unwrap()[0], 4);
 127
 128     let mut v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 129     let mut c2 = v2.chunks_mut(3);
 130     assert_eq!(c2.nth(1).unwrap()[1], 4);
 131     assert_eq!(c2.next(), None);
 132 }
 133
 134 #[test]
 135 fn test_chunks_mut_last() {
 136     let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 137     let c = v.chunks_mut(2);
 138     assert_eq!(c.last().unwrap()[1], 5);
 139
 140     let v2: &mut [i32] = &mut [0, 1, 2, 3, 4];
 141     let c2 = v2.chunks_mut(2);
 142     assert_eq!(c2.last().unwrap()[0], 4);
 143 }
 144
 145 #[test]
 146 fn test_windows_count() {
 147     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 148     let c = v.windows(3);
 149     assert_eq!(c.count(), 4);
 150
 151     let v2: &[i32] = &[0, 1, 2, 3, 4];
 152     let c2 = v2.windows(6);
 153     assert_eq!(c2.count(), 0);
 154
 155     let v3: &[i32] = &[];
 156     let c3 = v3.windows(2);
 157     assert_eq!(c3.count(), 0);
 158 }
 159
 160 #[test]
 161 fn test_windows_nth() {
 162     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 163     let mut c = v.windows(2);
 164     assert_eq!(c.nth(2).unwrap()[1], 3);
 165     assert_eq!(c.next().unwrap()[0], 3);
 166
 167     let v2: &[i32] = &[0, 1, 2, 3, 4];
 168     let mut c2 = v2.windows(4);
 169     assert_eq!(c2.nth(1).unwrap()[1], 2);
 170     assert_eq!(c2.next(), None);
 171 }
 172
 173 #[test]
 174 fn test_windows_last() {
 175     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 176     let c = v.windows(2);
 177     assert_eq!(c.last().unwrap()[1], 5);
 178
 179     let v2: &[i32] = &[0, 1, 2, 3, 4];
 180     let c2 = v2.windows(2);
 181     assert_eq!(c2.last().unwrap()[0], 3);
 182 }
 183
 184 #[test]
 185 fn get_range() {
 186     let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 187     assert_eq!(v.get(..), Some(&[0, 1, 2, 3, 4, 5][..]));
 188     assert_eq!(v.get(..2), Some(&[0, 1][..]));
 189     assert_eq!(v.get(2..), Some(&[2, 3, 4, 5][..]));
 190     assert_eq!(v.get(1..4), Some(&[1, 2, 3][..]));
 191     assert_eq!(v.get(7..), None);
 192     assert_eq!(v.get(7..10), None);
 193 }
 194
 195 #[test]
 196 fn get_mut_range() {
 197     let mut v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 198     assert_eq!(v.get_mut(..), Some(&mut [0, 1, 2, 3, 4, 5][..]));
 199     assert_eq!(v.get_mut(..2), Some(&mut [0, 1][..]));
 200     assert_eq!(v.get_mut(2..), Some(&mut [2, 3, 4, 5][..]));
 201     assert_eq!(v.get_mut(1..4), Some(&mut [1, 2, 3][..]));
 202     assert_eq!(v.get_mut(7..), None);
 203     assert_eq!(v.get_mut(7..10), None);
 204 }
 205
 206 #[test]
 207 fn get_unchecked_range() {
 208     unsafe {
 209         let v: &[i32] = &[0, 1, 2, 3, 4, 5];
 210         assert_eq!(v.get_unchecked(..), &[0, 1, 2, 3, 4, 5][..]);
 211         assert_eq!(v.get_unchecked(..2), &[0, 1][..]);
 212         assert_eq!(v.get_unchecked(2..), &[2, 3, 4, 5][..]);
 213         assert_eq!(v.get_unchecked(1..4), &[1, 2, 3][..]);
 214     }
 215 }
 216
 217 #[test]
 218 fn get_unchecked_mut_range() {
 219     unsafe {
 220         let v: &mut [i32] = &mut [0, 1, 2, 3, 4, 5];
 221         assert_eq!(v.get_unchecked_mut(..), &mut [0, 1, 2, 3, 4, 5][..]);
 222         assert_eq!(v.get_unchecked_mut(..2), &mut [0, 1][..]);
 223         assert_eq!(v.get_unchecked_mut(2..), &mut[2, 3, 4, 5][..]);
 224         assert_eq!(v.get_unchecked_mut(1..4), &mut [1, 2, 3][..]);
 225     }
 226 }
 227
 228 #[test]
 229 fn test_find_rfind() {
 230     let v = [0, 1, 2, 3, 4, 5];
 231     let mut iter = v.iter();
 232     let mut i = v.len();
 233     while let Some(&elt) = iter.rfind(|_| true) {
 234         i -= 1;
 235         assert_eq!(elt, v[i]);
 236     }
 237     assert_eq!(i, 0);
 238     assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3));
 239 }
 240
 241 #[test]
 242 fn sort_unstable() {
 243     let mut v = [0; 600];
 244     let mut tmp = [0; 600];
 245     let mut rng = XorShiftRng::new_unseeded();
 246
 247     for len in (2..25).chain(500..510) {
 248         let v = &mut v[0..len];
 249         let tmp = &mut tmp[0..len];
 250
 251         for &modulus in &[5, 10, 100, 1000] {
 252             for _ in 0..100 {
 253                 for i in 0..len {
 254                     v[i] = rng.gen::<i32>() % modulus;
 255                 }
 256
 257                 // Sort in default order.
 258                 tmp.copy_from_slice(v);
 259                 tmp.sort_unstable();
 260                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 261
 262                 // Sort in ascending order.
 263                 tmp.copy_from_slice(v);
 264                 tmp.sort_unstable_by(|a, b| a.cmp(b));
 265                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 266
 267                 // Sort in descending order.
 268                 tmp.copy_from_slice(v);
 269                 tmp.sort_unstable_by(|a, b| b.cmp(a));
 270                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 271
 272                 // Test heapsort using `<` operator.
 273                 tmp.copy_from_slice(v);
 274                 heapsort(tmp, |a, b| a < b);
 275                 assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
 276
 277                 // Test heapsort using `>` operator.
 278                 tmp.copy_from_slice(v);
 279                 heapsort(tmp, |a, b| a > b);
 280                 assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
 281             }
 282         }
 283     }
 284
 285     // Sort using a completely random comparison function.
 286     // This will reorder the elements *somehow*, but won't panic.
 287     for i in 0..v.len() {
 288         v[i] = i as i32;
 289     }
 290     v.sort_unstable_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
 291     v.sort_unstable();
 292     for i in 0..v.len() {
 293         assert_eq!(v[i], i as i32);
 294     }
 295
 296     // Should not panic.
 297     [0i32; 0].sort_unstable();
 298     [(); 10].sort_unstable();
 299     [(); 100].sort_unstable();
 300
 301     let mut v = [0xDEADBEEFu64];
 302     v.sort_unstable();
 303     assert!(v == [0xDEADBEEF]);
 304 }