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

   1 use super::*;
   2 use crate::boxed::Box;
   3 use std::iter::TrustedLen;
   4 use std::panic::{catch_unwind, AssertUnwindSafe};
   5 use std::sync::atomic::{AtomicU32, Ordering};
   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 2, box 4, box 9]);
 187     assert_eq!(heap.len(), 3);
 188     assert!(**heap.peek().unwrap() == 9);
 189     heap.push(box 11);
 190     assert_eq!(heap.len(), 4);
 191     assert!(**heap.peek().unwrap() == 11);
 192     heap.push(box 5);
 193     assert_eq!(heap.len(), 5);
 194     assert!(**heap.peek().unwrap() == 11);
 195     heap.push(box 27);
 196     assert_eq!(heap.len(), 6);
 197     assert!(**heap.peek().unwrap() == 27);
 198     heap.push(box 3);
 199     assert_eq!(heap.len(), 7);
 200     assert!(**heap.peek().unwrap() == 27);
 201     heap.push(box 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     static DROPS: AtomicU32 = AtomicU32::new(0);
 295
 296     #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
 297     struct D(u32, bool);
 298
 299     impl Drop for D {
 300         fn drop(&mut self) {
 301             DROPS.fetch_add(1, Ordering::SeqCst);
 302
 303             if self.1 {
 304                 panic!("panic in `drop`");
 305             }
 306         }
 307     }
 308
 309     let mut q = BinaryHeap::from(vec![
 310         D(0, false),
 311         D(1, false),
 312         D(2, false),
 313         D(3, true),
 314         D(4, false),
 315         D(5, false),
 316     ]);
 317
 318     catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok();
 319
 320     assert_eq!(DROPS.load(Ordering::SeqCst), 6);
 321 }
 322
 323 #[test]
 324 fn test_extend_ref() {
 325     let mut a = BinaryHeap::new();
 326     a.push(1);
 327     a.push(2);
 328
 329     a.extend(&[3, 4, 5]);
 330
 331     assert_eq!(a.len(), 5);
 332     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 333
 334     let mut a = BinaryHeap::new();
 335     a.push(1);
 336     a.push(2);
 337     let mut b = BinaryHeap::new();
 338     b.push(3);
 339     b.push(4);
 340     b.push(5);
 341
 342     a.extend(&b);
 343
 344     assert_eq!(a.len(), 5);
 345     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 346 }
 347
 348 #[test]
 349 fn test_append() {
 350     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 351     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 352
 353     a.append(&mut b);
 354
 355     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 356     assert!(b.is_empty());
 357 }
 358
 359 #[test]
 360 fn test_append_to_empty() {
 361     let mut a = BinaryHeap::new();
 362     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 363
 364     a.append(&mut b);
 365
 366     assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
 367     assert!(b.is_empty());
 368 }
 369
 370 #[test]
 371 fn test_extend_specialization() {
 372     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 373     let b = BinaryHeap::from(vec![-20, 5, 43]);
 374
 375     a.extend(b);
 376
 377     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 378 }
 379
 380 #[allow(dead_code)]
 381 fn assert_covariance() {
 382     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 383         d
 384     }
 385 }
 386
 387 #[test]
 388 fn test_retain() {
 389     let mut a = BinaryHeap::from(vec![100, 10, 50, 1, 2, 20, 30]);
 390     a.retain(|&x| x != 2);
 391
 392     // Check that 20 moved into 10's place.
 393     assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
 394
 395     a.retain(|_| true);
 396
 397     assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
 398
 399     a.retain(|&x| x < 50);
 400
 401     assert_eq!(a.clone().into_vec(), [30, 20, 10, 1]);
 402
 403     a.retain(|_| false);
 404
 405     assert!(a.is_empty());
 406 }
 407
 408 // old binaryheap failed this test
 409 //
 410 // Integrity means that all elements are present after a comparison panics,
 411 // even if the order might not be correct.
 412 //
 413 // Destructors must be called exactly once per element.
 414 // FIXME: re-enable emscripten once it can unwind again
 415 #[test]
 416 #[cfg(not(target_os = "emscripten"))]
 417 fn panic_safe() {
 418     use rand::{seq::SliceRandom, thread_rng};
 419     use std::cmp;
 420     use std::panic::{self, AssertUnwindSafe};
 421     use std::sync::atomic::{AtomicUsize, Ordering};
 422
 423     static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
 424
 425     #[derive(Eq, PartialEq, Ord, Clone, Debug)]
 426     struct PanicOrd<T>(T, bool);
 427
 428     impl<T> Drop for PanicOrd<T> {
 429         fn drop(&mut self) {
 430             // update global drop count
 431             DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
 432         }
 433     }
 434
 435     impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
 436         fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
 437             if self.1 || other.1 {
 438                 panic!("Panicking comparison");
 439             }
 440             self.0.partial_cmp(&other.0)
 441         }
 442     }
 443     let mut rng = thread_rng();
 444     const DATASZ: usize = 32;
 445     // Miri is too slow
 446     let ntest = if cfg!(miri) { 1 } else { 10 };
 447
 448     // don't use 0 in the data -- we want to catch the zeroed-out case.
 449     let data = (1..=DATASZ).collect::<Vec<_>>();
 450
 451     // since it's a fuzzy test, run several tries.
 452     for _ in 0..ntest {
 453         for i in 1..=DATASZ {
 454             DROP_COUNTER.store(0, Ordering::SeqCst);
 455
 456             let mut panic_ords: Vec<_> =
 457                 data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect();
 458             let panic_item = PanicOrd(i, true);
 459
 460             // heapify the sane items
 461             panic_ords.shuffle(&mut rng);
 462             let mut heap = BinaryHeap::from(panic_ords);
 463             let inner_data;
 464
 465             {
 466                 // push the panicking item to the heap and catch the panic
 467                 let thread_result = {
 468                     let mut heap_ref = AssertUnwindSafe(&mut heap);
 469                     panic::catch_unwind(move || {
 470                         heap_ref.push(panic_item);
 471                     })
 472                 };
 473                 assert!(thread_result.is_err());
 474
 475                 // Assert no elements were dropped
 476                 let drops = DROP_COUNTER.load(Ordering::SeqCst);
 477                 assert!(drops == 0, "Must not drop items. drops={}", drops);
 478                 inner_data = heap.clone().into_vec();
 479                 drop(heap);
 480             }
 481             let drops = DROP_COUNTER.load(Ordering::SeqCst);
 482             assert_eq!(drops, DATASZ);
 483
 484             let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
 485             data_sorted.sort();
 486             assert_eq!(data_sorted, data);
 487         }
 488     }
 489 }