src/liballoc/tests/binary_heap.rs

   1 use std::collections::BinaryHeap;
   2 use std::collections::binary_heap::{Drain, PeekMut};
   3 use std::iter::TrustedLen;
   4
   5 #[test]
   6 fn test_iterator() {
   7     let data = vec![5, 9, 3];
   8     let iterout = [9, 5, 3];
   9     let heap = BinaryHeap::from(data);
  10     let mut i = 0;
  11     for el in &heap {
  12         assert_eq!(*el, iterout[i]);
  13         i += 1;
  14     }
  15 }
  16
  17 #[test]
  18 fn test_iter_rev_cloned_collect() {
  19     let data = vec![5, 9, 3];
  20     let iterout = vec![3, 5, 9];
  21     let pq = BinaryHeap::from(data);
  22
  23     let v: Vec<_> = pq.iter().rev().cloned().collect();
  24     assert_eq!(v, iterout);
  25 }
  26
  27 #[test]
  28 fn test_into_iter_collect() {
  29     let data = vec![5, 9, 3];
  30     let iterout = vec![9, 5, 3];
  31     let pq = BinaryHeap::from(data);
  32
  33     let v: Vec<_> = pq.into_iter().collect();
  34     assert_eq!(v, iterout);
  35 }
  36
  37 #[test]
  38 fn test_into_iter_size_hint() {
  39     let data = vec![5, 9];
  40     let pq = BinaryHeap::from(data);
  41
  42     let mut it = pq.into_iter();
  43
  44     assert_eq!(it.size_hint(), (2, Some(2)));
  45     assert_eq!(it.next(), Some(9));
  46
  47     assert_eq!(it.size_hint(), (1, Some(1)));
  48     assert_eq!(it.next(), Some(5));
  49
  50     assert_eq!(it.size_hint(), (0, Some(0)));
  51     assert_eq!(it.next(), None);
  52 }
  53
  54 #[test]
  55 fn test_into_iter_rev_collect() {
  56     let data = vec![5, 9, 3];
  57     let iterout = vec![3, 5, 9];
  58     let pq = BinaryHeap::from(data);
  59
  60     let v: Vec<_> = pq.into_iter().rev().collect();
  61     assert_eq!(v, iterout);
  62 }
  63
  64 #[test]
  65 fn test_into_iter_sorted_collect() {
  66     let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
  67     let it = heap.into_iter_sorted();
  68     let sorted = it.collect::<Vec<_>>();
  69     assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
  70 }
  71
  72 #[test]
  73 fn test_drain_sorted_collect() {
  74     let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
  75     let it = heap.drain_sorted();
  76     let sorted = it.collect::<Vec<_>>();
  77     assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
  78 }
  79
  80 fn check_exact_size_iterator<I: ExactSizeIterator>(len: usize, it: I) {
  81     let mut it = it;
  82
  83     for i in 0..it.len() {
  84         let (lower, upper) = it.size_hint();
  85         assert_eq!(Some(lower), upper);
  86         assert_eq!(lower, len - i);
  87         assert_eq!(it.len(), len - i);
  88         it.next();
  89     }
  90     assert_eq!(it.len(), 0);
  91     assert!(it.is_empty());
  92 }
  93
  94 #[test]
  95 fn test_exact_size_iterator() {
  96     let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
  97     check_exact_size_iterator(heap.len(), heap.iter());
  98     check_exact_size_iterator(heap.len(), heap.clone().into_iter());
  99     check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted());
 100     check_exact_size_iterator(heap.len(), heap.clone().drain());
 101     check_exact_size_iterator(heap.len(), heap.clone().drain_sorted());
 102 }
 103
 104 fn check_trusted_len<I: TrustedLen>(len: usize, it: I) {
 105     let mut it = it;
 106     for i in 0..len {
 107         let (lower, upper) = it.size_hint();
 108         if upper.is_some() {
 109             assert_eq!(Some(lower), upper);
 110             assert_eq!(lower, len - i);
 111         }
 112         it.next();
 113     }
 114 }
 115
 116 #[test]
 117 fn test_trusted_len() {
 118     let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
 119     check_trusted_len(heap.len(), heap.clone().into_iter_sorted());
 120     check_trusted_len(heap.len(), heap.clone().drain_sorted());
 121 }
 122
 123 #[test]
 124 fn test_peek_and_pop() {
 125     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
 126     let mut sorted = data.clone();
 127     sorted.sort();
 128     let mut heap = BinaryHeap::from(data);
 129     while !heap.is_empty() {
 130         assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
 131         assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
 132     }
 133 }
 134
 135 #[test]
 136 fn test_peek_mut() {
 137     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
 138     let mut heap = BinaryHeap::from(data);
 139     assert_eq!(heap.peek(), Some(&10));
 140     {
 141         let mut top = heap.peek_mut().unwrap();
 142         *top -= 2;
 143     }
 144     assert_eq!(heap.peek(), Some(&9));
 145 }
 146
 147 #[test]
 148 fn test_peek_mut_pop() {
 149     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
 150     let mut heap = BinaryHeap::from(data);
 151     assert_eq!(heap.peek(), Some(&10));
 152     {
 153         let mut top = heap.peek_mut().unwrap();
 154         *top -= 2;
 155         assert_eq!(PeekMut::pop(top), 8);
 156     }
 157     assert_eq!(heap.peek(), Some(&9));
 158 }
 159
 160 #[test]
 161 fn test_push() {
 162     let mut heap = BinaryHeap::from(vec![2, 4, 9]);
 163     assert_eq!(heap.len(), 3);
 164     assert!(*heap.peek().unwrap() == 9);
 165     heap.push(11);
 166     assert_eq!(heap.len(), 4);
 167     assert!(*heap.peek().unwrap() == 11);
 168     heap.push(5);
 169     assert_eq!(heap.len(), 5);
 170     assert!(*heap.peek().unwrap() == 11);
 171     heap.push(27);
 172     assert_eq!(heap.len(), 6);
 173     assert!(*heap.peek().unwrap() == 27);
 174     heap.push(3);
 175     assert_eq!(heap.len(), 7);
 176     assert!(*heap.peek().unwrap() == 27);
 177     heap.push(103);
 178     assert_eq!(heap.len(), 8);
 179     assert!(*heap.peek().unwrap() == 103);
 180 }
 181
 182 #[test]
 183 fn test_push_unique() {
 184     let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
 185     assert_eq!(heap.len(), 3);
 186     assert!(**heap.peek().unwrap() == 9);
 187     heap.push(box 11);
 188     assert_eq!(heap.len(), 4);
 189     assert!(**heap.peek().unwrap() == 11);
 190     heap.push(box 5);
 191     assert_eq!(heap.len(), 5);
 192     assert!(**heap.peek().unwrap() == 11);
 193     heap.push(box 27);
 194     assert_eq!(heap.len(), 6);
 195     assert!(**heap.peek().unwrap() == 27);
 196     heap.push(box 3);
 197     assert_eq!(heap.len(), 7);
 198     assert!(**heap.peek().unwrap() == 27);
 199     heap.push(box 103);
 200     assert_eq!(heap.len(), 8);
 201     assert!(**heap.peek().unwrap() == 103);
 202 }
 203
 204 fn check_to_vec(mut data: Vec<i32>) {
 205     let heap = BinaryHeap::from(data.clone());
 206     let mut v = heap.clone().into_vec();
 207     v.sort();
 208     data.sort();
 209
 210     assert_eq!(v, data);
 211     assert_eq!(heap.into_sorted_vec(), data);
 212 }
 213
 214 #[test]
 215 fn test_to_vec() {
 216     check_to_vec(vec![]);
 217     check_to_vec(vec![5]);
 218     check_to_vec(vec![3, 2]);
 219     check_to_vec(vec![2, 3]);
 220     check_to_vec(vec![5, 1, 2]);
 221     check_to_vec(vec![1, 100, 2, 3]);
 222     check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
 223     check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
 224     check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
 225     check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 226     check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
 227     check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
 228     check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
 229 }
 230
 231 #[test]
 232 fn test_empty_pop() {
 233     let mut heap = BinaryHeap::<i32>::new();
 234     assert!(heap.pop().is_none());
 235 }
 236
 237 #[test]
 238 fn test_empty_peek() {
 239     let empty = BinaryHeap::<i32>::new();
 240     assert!(empty.peek().is_none());
 241 }
 242
 243 #[test]
 244 fn test_empty_peek_mut() {
 245     let mut empty = BinaryHeap::<i32>::new();
 246     assert!(empty.peek_mut().is_none());
 247 }
 248
 249 #[test]
 250 fn test_from_iter() {
 251     let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
 252
 253     let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
 254
 255     for &x in &xs {
 256         assert_eq!(q.pop().unwrap(), x);
 257     }
 258 }
 259
 260 #[test]
 261 fn test_drain() {
 262     let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
 263
 264     assert_eq!(q.drain().take(5).count(), 5);
 265
 266     assert!(q.is_empty());
 267 }
 268
 269 #[test]
 270 fn test_drain_sorted() {
 271     let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
 272
 273     assert_eq!(q.drain_sorted().take(5).collect::<Vec<_>>(), vec![9, 8, 7, 6, 5]);
 274
 275     assert!(q.is_empty());
 276 }
 277
 278 #[test]
 279 fn test_extend_ref() {
 280     let mut a = BinaryHeap::new();
 281     a.push(1);
 282     a.push(2);
 283
 284     a.extend(&[3, 4, 5]);
 285
 286     assert_eq!(a.len(), 5);
 287     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 288
 289     let mut a = BinaryHeap::new();
 290     a.push(1);
 291     a.push(2);
 292     let mut b = BinaryHeap::new();
 293     b.push(3);
 294     b.push(4);
 295     b.push(5);
 296
 297     a.extend(&b);
 298
 299     assert_eq!(a.len(), 5);
 300     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 301 }
 302
 303 #[test]
 304 fn test_append() {
 305     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 306     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 307
 308     a.append(&mut b);
 309
 310     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 311     assert!(b.is_empty());
 312 }
 313
 314 #[test]
 315 fn test_append_to_empty() {
 316     let mut a = BinaryHeap::new();
 317     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 318
 319     a.append(&mut b);
 320
 321     assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
 322     assert!(b.is_empty());
 323 }
 324
 325 #[test]
 326 fn test_extend_specialization() {
 327     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 328     let b = BinaryHeap::from(vec![-20, 5, 43]);
 329
 330     a.extend(b);
 331
 332     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 333 }
 334
 335 #[allow(dead_code)]
 336 fn assert_covariance() {
 337     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 338         d
 339     }
 340 }
 341
 342 // old binaryheap failed this test
 343 //
 344 // Integrity means that all elements are present after a comparison panics,
 345 // even if the order may not be correct.
 346 //
 347 // Destructors must be called exactly once per element.
 348 // FIXME: re-enable emscripten once it can unwind again
 349 #[test]
 350 #[cfg(not(target_os = "emscripten"))]
 351 fn panic_safe() {
 352     use std::cmp;
 353     use std::panic::{self, AssertUnwindSafe};
 354     use std::sync::atomic::{AtomicUsize, Ordering};
 355     use rand::{thread_rng, seq::SliceRandom};
 356
 357     static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
 358
 359     #[derive(Eq, PartialEq, Ord, Clone, Debug)]
 360     struct PanicOrd<T>(T, bool);
 361
 362     impl<T> Drop for PanicOrd<T> {
 363         fn drop(&mut self) {
 364             // update global drop count
 365             DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
 366         }
 367     }
 368
 369     impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
 370         fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
 371             if self.1 || other.1 {
 372                 panic!("Panicking comparison");
 373             }
 374             self.0.partial_cmp(&other.0)
 375         }
 376     }
 377     let mut rng = thread_rng();
 378     const DATASZ: usize = 32;
 379     #[cfg(not(miri))] // Miri is too slow
 380     const NTEST: usize = 10;
 381     #[cfg(miri)]
 382     const NTEST: usize = 1;
 383
 384     // don't use 0 in the data -- we want to catch the zeroed-out case.
 385     let data = (1..=DATASZ).collect::<Vec<_>>();
 386
 387     // since it's a fuzzy test, run several tries.
 388     for _ in 0..NTEST {
 389         for i in 1..=DATASZ {
 390             DROP_COUNTER.store(0, Ordering::SeqCst);
 391
 392             let mut panic_ords: Vec<_> = data.iter()
 393                                              .filter(|&&x| x != i)
 394                                              .map(|&x| PanicOrd(x, false))
 395                                              .collect();
 396             let panic_item = PanicOrd(i, true);
 397
 398             // heapify the sane items
 399             panic_ords.shuffle(&mut rng);
 400             let mut heap = BinaryHeap::from(panic_ords);
 401             let inner_data;
 402
 403             {
 404                 // push the panicking item to the heap and catch the panic
 405                 let thread_result = {
 406                     let mut heap_ref = AssertUnwindSafe(&mut heap);
 407                     panic::catch_unwind(move || {
 408                         heap_ref.push(panic_item);
 409                     })
 410                 };
 411                 assert!(thread_result.is_err());
 412
 413                 // Assert no elements were dropped
 414                 let drops = DROP_COUNTER.load(Ordering::SeqCst);
 415                 assert!(drops == 0, "Must not drop items. drops={}", drops);
 416                 inner_data = heap.clone().into_vec();
 417                 drop(heap);
 418             }
 419             let drops = DROP_COUNTER.load(Ordering::SeqCst);
 420             assert_eq!(drops, DATASZ);
 421
 422             let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
 423             data_sorted.sort();
 424             assert_eq!(data_sorted, data);
 425         }
 426     }
 427 }