src/liballoc/tests/binary_heap.rs

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