library/alloc/src/collections/binary_heap/tests.rs

   1 use super::*;
   2 use crate::boxed::Box;
   3 use crate::testing::crash_test::{CrashTestDummy, Panic};
   4 use std::iter::TrustedLen;
   5 use std::panic::{catch_unwind, AssertUnwindSafe};
   6
   7 #[test]
   8 fn test_iterator() {
   9     let data = vec![5, 9, 3];
  10     let iterout = [9, 5, 3];
  11     let heap = BinaryHeap::from(data);
  12     let mut i = 0;
  13     for el in &heap {
  14         assert_eq!(*el, iterout[i]);
  15         i += 1;
  16     }
  17 }
  18
  19 #[test]
  20 fn test_iter_rev_cloned_collect() {
  21     let data = vec![5, 9, 3];
  22     let iterout = vec![3, 5, 9];
  23     let pq = BinaryHeap::from(data);
  24
  25     let v: Vec<_> = pq.iter().rev().cloned().collect();
  26     assert_eq!(v, iterout);
  27 }
  28
  29 #[test]
  30 fn test_into_iter_collect() {
  31     let data = vec![5, 9, 3];
  32     let iterout = vec![9, 5, 3];
  33     let pq = BinaryHeap::from(data);
  34
  35     let v: Vec<_> = pq.into_iter().collect();
  36     assert_eq!(v, iterout);
  37 }
  38
  39 #[test]
  40 fn test_into_iter_size_hint() {
  41     let data = vec![5, 9];
  42     let pq = BinaryHeap::from(data);
  43
  44     let mut it = pq.into_iter();
  45
  46     assert_eq!(it.size_hint(), (2, Some(2)));
  47     assert_eq!(it.next(), Some(9));
  48
  49     assert_eq!(it.size_hint(), (1, Some(1)));
  50     assert_eq!(it.next(), Some(5));
  51
  52     assert_eq!(it.size_hint(), (0, Some(0)));
  53     assert_eq!(it.next(), None);
  54 }
  55
  56 #[test]
  57 fn test_into_iter_rev_collect() {
  58     let data = vec![5, 9, 3];
  59     let iterout = vec![3, 5, 9];
  60     let pq = BinaryHeap::from(data);
  61
  62     let v: Vec<_> = pq.into_iter().rev().collect();
  63     assert_eq!(v, iterout);
  64 }
  65
  66 #[test]
  67 fn test_into_iter_sorted_collect() {
  68     let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
  69     let it = heap.into_iter_sorted();
  70     let sorted = it.collect::<Vec<_>>();
  71     assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
  72 }
  73
  74 #[test]
  75 fn test_drain_sorted_collect() {
  76     let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
  77     let it = heap.drain_sorted();
  78     let sorted = it.collect::<Vec<_>>();
  79     assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
  80 }
  81
  82 fn check_exact_size_iterator<I: ExactSizeIterator>(len: usize, it: I) {
  83     let mut it = it;
  84
  85     for i in 0..it.len() {
  86         let (lower, upper) = it.size_hint();
  87         assert_eq!(Some(lower), upper);
  88         assert_eq!(lower, len - i);
  89         assert_eq!(it.len(), len - i);
  90         it.next();
  91     }
  92     assert_eq!(it.len(), 0);
  93     assert!(it.is_empty());
  94 }
  95
  96 #[test]
  97 fn test_exact_size_iterator() {
  98     let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
  99     check_exact_size_iterator(heap.len(), heap.iter());
 100     check_exact_size_iterator(heap.len(), heap.clone().into_iter());
 101     check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted());
 102     check_exact_size_iterator(heap.len(), heap.clone().drain());
 103     check_exact_size_iterator(heap.len(), heap.clone().drain_sorted());
 104 }
 105
 106 fn check_trusted_len<I: TrustedLen>(len: usize, it: I) {
 107     let mut it = it;
 108     for i in 0..len {
 109         let (lower, upper) = it.size_hint();
 110         if upper.is_some() {
 111             assert_eq!(Some(lower), upper);
 112             assert_eq!(lower, len - i);
 113         }
 114         it.next();
 115     }
 116 }
 117
 118 #[test]
 119 fn test_trusted_len() {
 120     let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
 121     check_trusted_len(heap.len(), heap.clone().into_iter_sorted());
 122     check_trusted_len(heap.len(), heap.clone().drain_sorted());
 123 }
 124
 125 #[test]
 126 fn test_peek_and_pop() {
 127     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
 128     let mut sorted = data.clone();
 129     sorted.sort();
 130     let mut heap = BinaryHeap::from(data);
 131     while !heap.is_empty() {
 132         assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
 133         assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
 134     }
 135 }
 136
 137 #[test]
 138 fn test_peek_mut() {
 139     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
 140     let mut heap = BinaryHeap::from(data);
 141     assert_eq!(heap.peek(), Some(&10));
 142     {
 143         let mut top = heap.peek_mut().unwrap();
 144         *top -= 2;
 145     }
 146     assert_eq!(heap.peek(), Some(&9));
 147 }
 148
 149 #[test]
 150 fn test_peek_mut_pop() {
 151     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
 152     let mut heap = BinaryHeap::from(data);
 153     assert_eq!(heap.peek(), Some(&10));
 154     {
 155         let mut top = heap.peek_mut().unwrap();
 156         *top -= 2;
 157         assert_eq!(PeekMut::pop(top), 8);
 158     }
 159     assert_eq!(heap.peek(), Some(&9));
 160 }
 161
 162 #[test]
 163 fn test_push() {
 164     let mut heap = BinaryHeap::from(vec![2, 4, 9]);
 165     assert_eq!(heap.len(), 3);
 166     assert!(*heap.peek().unwrap() == 9);
 167     heap.push(11);
 168     assert_eq!(heap.len(), 4);
 169     assert!(*heap.peek().unwrap() == 11);
 170     heap.push(5);
 171     assert_eq!(heap.len(), 5);
 172     assert!(*heap.peek().unwrap() == 11);
 173     heap.push(27);
 174     assert_eq!(heap.len(), 6);
 175     assert!(*heap.peek().unwrap() == 27);
 176     heap.push(3);
 177     assert_eq!(heap.len(), 7);
 178     assert!(*heap.peek().unwrap() == 27);
 179     heap.push(103);
 180     assert_eq!(heap.len(), 8);
 181     assert!(*heap.peek().unwrap() == 103);
 182 }
 183
 184 #[test]
 185 fn test_push_unique() {
 186     let mut heap = BinaryHeap::<Box<_>>::from(vec![Box::new(2), Box::new(4), Box::new(9)]);
 187     assert_eq!(heap.len(), 3);
 188     assert!(**heap.peek().unwrap() == 9);
 189     heap.push(Box::new(11));
 190     assert_eq!(heap.len(), 4);
 191     assert!(**heap.peek().unwrap() == 11);
 192     heap.push(Box::new(5));
 193     assert_eq!(heap.len(), 5);
 194     assert!(**heap.peek().unwrap() == 11);
 195     heap.push(Box::new(27));
 196     assert_eq!(heap.len(), 6);
 197     assert!(**heap.peek().unwrap() == 27);
 198     heap.push(Box::new(3));
 199     assert_eq!(heap.len(), 7);
 200     assert!(**heap.peek().unwrap() == 27);
 201     heap.push(Box::new(103));
 202     assert_eq!(heap.len(), 8);
 203     assert!(**heap.peek().unwrap() == 103);
 204 }
 205
 206 fn check_to_vec(mut data: Vec<i32>) {
 207     let heap = BinaryHeap::from(data.clone());
 208     let mut v = heap.clone().into_vec();
 209     v.sort();
 210     data.sort();
 211
 212     assert_eq!(v, data);
 213     assert_eq!(heap.into_sorted_vec(), data);
 214 }
 215
 216 #[test]
 217 fn test_to_vec() {
 218     check_to_vec(vec![]);
 219     check_to_vec(vec![5]);
 220     check_to_vec(vec![3, 2]);
 221     check_to_vec(vec![2, 3]);
 222     check_to_vec(vec![5, 1, 2]);
 223     check_to_vec(vec![1, 100, 2, 3]);
 224     check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
 225     check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
 226     check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
 227     check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 228     check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
 229     check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
 230     check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
 231 }
 232
 233 #[test]
 234 fn test_in_place_iterator_specialization() {
 235     let src: Vec<usize> = vec![1, 2, 3];
 236     let src_ptr = src.as_ptr();
 237     let heap: BinaryHeap<_> = src.into_iter().map(std::convert::identity).collect();
 238     let heap_ptr = heap.iter().next().unwrap() as *const usize;
 239     assert_eq!(src_ptr, heap_ptr);
 240     let sink: Vec<_> = heap.into_iter().map(std::convert::identity).collect();
 241     let sink_ptr = sink.as_ptr();
 242     assert_eq!(heap_ptr, sink_ptr);
 243 }
 244
 245 #[test]
 246 fn test_empty_pop() {
 247     let mut heap = BinaryHeap::<i32>::new();
 248     assert!(heap.pop().is_none());
 249 }
 250
 251 #[test]
 252 fn test_empty_peek() {
 253     let empty = BinaryHeap::<i32>::new();
 254     assert!(empty.peek().is_none());
 255 }
 256
 257 #[test]
 258 fn test_empty_peek_mut() {
 259     let mut empty = BinaryHeap::<i32>::new();
 260     assert!(empty.peek_mut().is_none());
 261 }
 262
 263 #[test]
 264 fn test_from_iter() {
 265     let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
 266
 267     let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
 268
 269     for &x in &xs {
 270         assert_eq!(q.pop().unwrap(), x);
 271     }
 272 }
 273
 274 #[test]
 275 fn test_drain() {
 276     let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
 277
 278     assert_eq!(q.drain().take(5).count(), 5);
 279
 280     assert!(q.is_empty());
 281 }
 282
 283 #[test]
 284 fn test_drain_sorted() {
 285     let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
 286
 287     assert_eq!(q.drain_sorted().take(5).collect::<Vec<_>>(), vec![9, 8, 7, 6, 5]);
 288
 289     assert!(q.is_empty());
 290 }
 291
 292 #[test]
 293 fn test_drain_sorted_leak() {
 294     let d0 = CrashTestDummy::new(0);
 295     let d1 = CrashTestDummy::new(1);
 296     let d2 = CrashTestDummy::new(2);
 297     let d3 = CrashTestDummy::new(3);
 298     let d4 = CrashTestDummy::new(4);
 299     let d5 = CrashTestDummy::new(5);
 300     let mut q = BinaryHeap::from(vec![
 301         d0.spawn(Panic::Never),
 302         d1.spawn(Panic::Never),
 303         d2.spawn(Panic::Never),
 304         d3.spawn(Panic::InDrop),
 305         d4.spawn(Panic::Never),
 306         d5.spawn(Panic::Never),
 307     ]);
 308
 309     catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).unwrap_err();
 310
 311     assert_eq!(d0.dropped(), 1);
 312     assert_eq!(d1.dropped(), 1);
 313     assert_eq!(d2.dropped(), 1);
 314     assert_eq!(d3.dropped(), 1);
 315     assert_eq!(d4.dropped(), 1);
 316     assert_eq!(d5.dropped(), 1);
 317     assert!(q.is_empty());
 318 }
 319
 320 #[test]
 321 fn test_drain_forget() {
 322     let a = CrashTestDummy::new(0);
 323     let b = CrashTestDummy::new(1);
 324     let c = CrashTestDummy::new(2);
 325     let mut q =
 326         BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]);
 327
 328     catch_unwind(AssertUnwindSafe(|| {
 329         let mut it = q.drain();
 330         it.next();
 331         mem::forget(it);
 332     }))
 333     .unwrap();
 334     // Behaviour after leaking is explicitly unspecified and order is arbitrary,
 335     // so it's fine if these start failing, but probably worth knowing.
 336     assert!(q.is_empty());
 337     assert_eq!(a.dropped() + b.dropped() + c.dropped(), 1);
 338     assert_eq!(a.dropped(), 0);
 339     assert_eq!(b.dropped(), 0);
 340     assert_eq!(c.dropped(), 1);
 341     drop(q);
 342     assert_eq!(a.dropped(), 0);
 343     assert_eq!(b.dropped(), 0);
 344     assert_eq!(c.dropped(), 1);
 345 }
 346
 347 #[test]
 348 fn test_drain_sorted_forget() {
 349     let a = CrashTestDummy::new(0);
 350     let b = CrashTestDummy::new(1);
 351     let c = CrashTestDummy::new(2);
 352     let mut q =
 353         BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]);
 354
 355     catch_unwind(AssertUnwindSafe(|| {
 356         let mut it = q.drain_sorted();
 357         it.next();
 358         mem::forget(it);
 359     }))
 360     .unwrap();
 361     // Behaviour after leaking is explicitly unspecified,
 362     // so it's fine if these start failing, but probably worth knowing.
 363     assert_eq!(q.len(), 2);
 364     assert_eq!(a.dropped(), 0);
 365     assert_eq!(b.dropped(), 0);
 366     assert_eq!(c.dropped(), 1);
 367     drop(q);
 368     assert_eq!(a.dropped(), 1);
 369     assert_eq!(b.dropped(), 1);
 370     assert_eq!(c.dropped(), 1);
 371 }
 372
 373 #[test]
 374 fn test_extend_ref() {
 375     let mut a = BinaryHeap::new();
 376     a.push(1);
 377     a.push(2);
 378
 379     a.extend(&[3, 4, 5]);
 380
 381     assert_eq!(a.len(), 5);
 382     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 383
 384     let mut a = BinaryHeap::new();
 385     a.push(1);
 386     a.push(2);
 387     let mut b = BinaryHeap::new();
 388     b.push(3);
 389     b.push(4);
 390     b.push(5);
 391
 392     a.extend(&b);
 393
 394     assert_eq!(a.len(), 5);
 395     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 396 }
 397
 398 #[test]
 399 fn test_append() {
 400     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 401     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 402
 403     a.append(&mut b);
 404
 405     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 406     assert!(b.is_empty());
 407 }
 408
 409 #[test]
 410 fn test_append_to_empty() {
 411     let mut a = BinaryHeap::new();
 412     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 413
 414     a.append(&mut b);
 415
 416     assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
 417     assert!(b.is_empty());
 418 }
 419
 420 #[test]
 421 fn test_extend_specialization() {
 422     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 423     let b = BinaryHeap::from(vec![-20, 5, 43]);
 424
 425     a.extend(b);
 426
 427     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 428 }
 429
 430 #[allow(dead_code)]
 431 fn assert_covariance() {
 432     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 433         d
 434     }
 435 }
 436
 437 #[test]
 438 fn test_retain() {
 439     let mut a = BinaryHeap::from(vec![100, 10, 50, 1, 2, 20, 30]);
 440     a.retain(|&x| x != 2);
 441
 442     // Check that 20 moved into 10's place.
 443     assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
 444
 445     a.retain(|_| true);
 446
 447     assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
 448
 449     a.retain(|&x| x < 50);
 450
 451     assert_eq!(a.clone().into_vec(), [30, 20, 10, 1]);
 452
 453     a.retain(|_| false);
 454
 455     assert!(a.is_empty());
 456 }
 457
 458 // old binaryheap failed this test
 459 //
 460 // Integrity means that all elements are present after a comparison panics,
 461 // even if the order might not be correct.
 462 //
 463 // Destructors must be called exactly once per element.
 464 // FIXME: re-enable emscripten once it can unwind again
 465 #[test]
 466 #[cfg(not(target_os = "emscripten"))]
 467 fn panic_safe() {
 468     use rand::seq::SliceRandom;
 469     use std::cmp;
 470     use std::panic::{self, AssertUnwindSafe};
 471     use std::sync::atomic::{AtomicUsize, Ordering};
 472
 473     static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
 474
 475     #[derive(Eq, PartialEq, Ord, Clone, Debug)]
 476     struct PanicOrd<T>(T, bool);
 477
 478     impl<T> Drop for PanicOrd<T> {
 479         fn drop(&mut self) {
 480             // update global drop count
 481             DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
 482         }
 483     }
 484
 485     impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
 486         fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
 487             if self.1 || other.1 {
 488                 panic!("Panicking comparison");
 489             }
 490             self.0.partial_cmp(&other.0)
 491         }
 492     }
 493     let mut rng = crate::test_helpers::test_rng();
 494     const DATASZ: usize = 32;
 495     // Miri is too slow
 496     let ntest = if cfg!(miri) { 1 } else { 10 };
 497
 498     // don't use 0 in the data -- we want to catch the zeroed-out case.
 499     let data = (1..=DATASZ).collect::<Vec<_>>();
 500
 501     // since it's a fuzzy test, run several tries.
 502     for _ in 0..ntest {
 503         for i in 1..=DATASZ {
 504             DROP_COUNTER.store(0, Ordering::SeqCst);
 505
 506             let mut panic_ords: Vec<_> =
 507                 data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect();
 508             let panic_item = PanicOrd(i, true);
 509
 510             // heapify the sane items
 511             panic_ords.shuffle(&mut rng);
 512             let mut heap = BinaryHeap::from(panic_ords);
 513             let inner_data;
 514
 515             {
 516                 // push the panicking item to the heap and catch the panic
 517                 let thread_result = {
 518                     let mut heap_ref = AssertUnwindSafe(&mut heap);
 519                     panic::catch_unwind(move || {
 520                         heap_ref.push(panic_item);
 521                     })
 522                 };
 523                 assert!(thread_result.is_err());
 524
 525                 // Assert no elements were dropped
 526                 let drops = DROP_COUNTER.load(Ordering::SeqCst);
 527                 assert!(drops == 0, "Must not drop items. drops={}", drops);
 528                 inner_data = heap.clone().into_vec();
 529                 drop(heap);
 530             }
 531             let drops = DROP_COUNTER.load(Ordering::SeqCst);
 532             assert_eq!(drops, DATASZ);
 533
 534             let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
 535             data_sorted.sort();
 536             assert_eq!(data_sorted, data);
 537         }
 538     }
 539 }