library/alloc/tests/binary_heap.rs

   1 use std::collections::binary_heap::{Drain, PeekMut};
   2 use std::collections::BinaryHeap;
   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_empty_pop() {
 235     let mut heap = BinaryHeap::<i32>::new();
 236     assert!(heap.pop().is_none());
 237 }
 238
 239 #[test]
 240 fn test_empty_peek() {
 241     let empty = BinaryHeap::<i32>::new();
 242     assert!(empty.peek().is_none());
 243 }
 244
 245 #[test]
 246 fn test_empty_peek_mut() {
 247     let mut empty = BinaryHeap::<i32>::new();
 248     assert!(empty.peek_mut().is_none());
 249 }
 250
 251 #[test]
 252 fn test_from_iter() {
 253     let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
 254
 255     let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
 256
 257     for &x in &xs {
 258         assert_eq!(q.pop().unwrap(), x);
 259     }
 260 }
 261
 262 #[test]
 263 fn test_drain() {
 264     let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
 265
 266     assert_eq!(q.drain().take(5).count(), 5);
 267
 268     assert!(q.is_empty());
 269 }
 270
 271 #[test]
 272 fn test_drain_sorted() {
 273     let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
 274
 275     assert_eq!(q.drain_sorted().take(5).collect::<Vec<_>>(), vec![9, 8, 7, 6, 5]);
 276
 277     assert!(q.is_empty());
 278 }
 279
 280 #[test]
 281 fn test_drain_sorted_leak() {
 282     static DROPS: AtomicU32 = AtomicU32::new(0);
 283
 284     #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
 285     struct D(u32, bool);
 286
 287     impl Drop for D {
 288         fn drop(&mut self) {
 289             DROPS.fetch_add(1, Ordering::SeqCst);
 290
 291             if self.1 {
 292                 panic!("panic in `drop`");
 293             }
 294         }
 295     }
 296
 297     let mut q = BinaryHeap::from(vec![
 298         D(0, false),
 299         D(1, false),
 300         D(2, false),
 301         D(3, true),
 302         D(4, false),
 303         D(5, false),
 304     ]);
 305
 306     catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok();
 307
 308     assert_eq!(DROPS.load(Ordering::SeqCst), 6);
 309 }
 310
 311 #[test]
 312 fn test_extend_ref() {
 313     let mut a = BinaryHeap::new();
 314     a.push(1);
 315     a.push(2);
 316
 317     a.extend(&[3, 4, 5]);
 318
 319     assert_eq!(a.len(), 5);
 320     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 321
 322     let mut a = BinaryHeap::new();
 323     a.push(1);
 324     a.push(2);
 325     let mut b = BinaryHeap::new();
 326     b.push(3);
 327     b.push(4);
 328     b.push(5);
 329
 330     a.extend(&b);
 331
 332     assert_eq!(a.len(), 5);
 333     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 334 }
 335
 336 #[test]
 337 fn test_append() {
 338     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 339     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 340
 341     a.append(&mut b);
 342
 343     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 344     assert!(b.is_empty());
 345 }
 346
 347 #[test]
 348 fn test_append_to_empty() {
 349     let mut a = BinaryHeap::new();
 350     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 351
 352     a.append(&mut b);
 353
 354     assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
 355     assert!(b.is_empty());
 356 }
 357
 358 #[test]
 359 fn test_extend_specialization() {
 360     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 361     let b = BinaryHeap::from(vec![-20, 5, 43]);
 362
 363     a.extend(b);
 364
 365     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 366 }
 367
 368 #[allow(dead_code)]
 369 fn assert_covariance() {
 370     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 371         d
 372     }
 373 }
 374
 375 #[test]
 376 fn test_retain() {
 377     let mut a = BinaryHeap::from(vec![-10, -5, 1, 2, 4, 13]);
 378     a.retain(|x| x % 2 == 0);
 379
 380     assert_eq!(a.into_sorted_vec(), [-10, 2, 4])
 381 }
 382
 383 // old binaryheap failed this test
 384 //
 385 // Integrity means that all elements are present after a comparison panics,
 386 // even if the order may not be correct.
 387 //
 388 // Destructors must be called exactly once per element.
 389 // FIXME: re-enable emscripten once it can unwind again
 390 #[test]
 391 #[cfg(not(target_os = "emscripten"))]
 392 fn panic_safe() {
 393     use rand::{seq::SliceRandom, thread_rng};
 394     use std::cmp;
 395     use std::panic::{self, AssertUnwindSafe};
 396     use std::sync::atomic::{AtomicUsize, Ordering};
 397
 398     static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
 399
 400     #[derive(Eq, PartialEq, Ord, Clone, Debug)]
 401     struct PanicOrd<T>(T, bool);
 402
 403     impl<T> Drop for PanicOrd<T> {
 404         fn drop(&mut self) {
 405             // update global drop count
 406             DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
 407         }
 408     }
 409
 410     impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
 411         fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
 412             if self.1 || other.1 {
 413                 panic!("Panicking comparison");
 414             }
 415             self.0.partial_cmp(&other.0)
 416         }
 417     }
 418     let mut rng = thread_rng();
 419     const DATASZ: usize = 32;
 420     // Miri is too slow
 421     let ntest = if cfg!(miri) { 1 } else { 10 };
 422
 423     // don't use 0 in the data -- we want to catch the zeroed-out case.
 424     let data = (1..=DATASZ).collect::<Vec<_>>();
 425
 426     // since it's a fuzzy test, run several tries.
 427     for _ in 0..ntest {
 428         for i in 1..=DATASZ {
 429             DROP_COUNTER.store(0, Ordering::SeqCst);
 430
 431             let mut panic_ords: Vec<_> =
 432                 data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect();
 433             let panic_item = PanicOrd(i, true);
 434
 435             // heapify the sane items
 436             panic_ords.shuffle(&mut rng);
 437             let mut heap = BinaryHeap::from(panic_ords);
 438             let inner_data;
 439
 440             {
 441                 // push the panicking item to the heap and catch the panic
 442                 let thread_result = {
 443                     let mut heap_ref = AssertUnwindSafe(&mut heap);
 444                     panic::catch_unwind(move || {
 445                         heap_ref.push(panic_item);
 446                     })
 447                 };
 448                 assert!(thread_result.is_err());
 449
 450                 // Assert no elements were dropped
 451                 let drops = DROP_COUNTER.load(Ordering::SeqCst);
 452                 assert!(drops == 0, "Must not drop items. drops={}", drops);
 453                 inner_data = heap.clone().into_vec();
 454                 drop(heap);
 455             }
 456             let drops = DROP_COUNTER.load(Ordering::SeqCst);
 457             assert_eq!(drops, DATASZ);
 458
 459             let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
 460             data_sorted.sort();
 461             assert_eq!(data_sorted, data);
 462         }
 463     }
 464 }