src/libcollections/tests/binary_heap.rs

   1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::panic;
  12 use std::collections::BinaryHeap;
  13 use std::collections::binary_heap::{Drain, PeekMut};
  14
  15 #[test]
  16 fn test_iterator() {
  17     let data = vec![5, 9, 3];
  18     let iterout = [9, 5, 3];
  19     let heap = BinaryHeap::from(data);
  20     let mut i = 0;
  21     for el in &heap {
  22         assert_eq!(*el, iterout[i]);
  23         i += 1;
  24     }
  25 }
  26
  27 #[test]
  28 fn test_iterator_reverse() {
  29     let data = vec![5, 9, 3];
  30     let iterout = vec![3, 5, 9];
  31     let pq = BinaryHeap::from(data);
  32
  33     let v: Vec<_> = pq.iter().rev().cloned().collect();
  34     assert_eq!(v, iterout);
  35 }
  36
  37 #[test]
  38 fn test_move_iter() {
  39     let data = vec![5, 9, 3];
  40     let iterout = vec![9, 5, 3];
  41     let pq = BinaryHeap::from(data);
  42
  43     let v: Vec<_> = pq.into_iter().collect();
  44     assert_eq!(v, iterout);
  45 }
  46
  47 #[test]
  48 fn test_move_iter_size_hint() {
  49     let data = vec![5, 9];
  50     let pq = BinaryHeap::from(data);
  51
  52     let mut it = pq.into_iter();
  53
  54     assert_eq!(it.size_hint(), (2, Some(2)));
  55     assert_eq!(it.next(), Some(9));
  56
  57     assert_eq!(it.size_hint(), (1, Some(1)));
  58     assert_eq!(it.next(), Some(5));
  59
  60     assert_eq!(it.size_hint(), (0, Some(0)));
  61     assert_eq!(it.next(), None);
  62 }
  63
  64 #[test]
  65 fn test_move_iter_reverse() {
  66     let data = vec![5, 9, 3];
  67     let iterout = vec![3, 5, 9];
  68     let pq = BinaryHeap::from(data);
  69
  70     let v: Vec<_> = pq.into_iter().rev().collect();
  71     assert_eq!(v, iterout);
  72 }
  73
  74 #[test]
  75 fn test_peek_and_pop() {
  76     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
  77     let mut sorted = data.clone();
  78     sorted.sort();
  79     let mut heap = BinaryHeap::from(data);
  80     while !heap.is_empty() {
  81         assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
  82         assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
  83     }
  84 }
  85
  86 #[test]
  87 fn test_peek_mut() {
  88     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
  89     let mut heap = BinaryHeap::from(data);
  90     assert_eq!(heap.peek(), Some(&10));
  91     {
  92         let mut top = heap.peek_mut().unwrap();
  93         *top -= 2;
  94     }
  95     assert_eq!(heap.peek(), Some(&9));
  96 }
  97
  98 #[test]
  99 fn test_peek_mut_pop() {
 100     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
 101     let mut heap = BinaryHeap::from(data);
 102     assert_eq!(heap.peek(), Some(&10));
 103     {
 104         let mut top = heap.peek_mut().unwrap();
 105         *top -= 2;
 106         assert_eq!(PeekMut::pop(top), 8);
 107     }
 108     assert_eq!(heap.peek(), Some(&9));
 109 }
 110
 111 #[test]
 112 fn test_push() {
 113     let mut heap = BinaryHeap::from(vec![2, 4, 9]);
 114     assert_eq!(heap.len(), 3);
 115     assert!(*heap.peek().unwrap() == 9);
 116     heap.push(11);
 117     assert_eq!(heap.len(), 4);
 118     assert!(*heap.peek().unwrap() == 11);
 119     heap.push(5);
 120     assert_eq!(heap.len(), 5);
 121     assert!(*heap.peek().unwrap() == 11);
 122     heap.push(27);
 123     assert_eq!(heap.len(), 6);
 124     assert!(*heap.peek().unwrap() == 27);
 125     heap.push(3);
 126     assert_eq!(heap.len(), 7);
 127     assert!(*heap.peek().unwrap() == 27);
 128     heap.push(103);
 129     assert_eq!(heap.len(), 8);
 130     assert!(*heap.peek().unwrap() == 103);
 131 }
 132
 133 #[test]
 134 fn test_push_unique() {
 135     let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
 136     assert_eq!(heap.len(), 3);
 137     assert!(*heap.peek().unwrap() == box 9);
 138     heap.push(box 11);
 139     assert_eq!(heap.len(), 4);
 140     assert!(*heap.peek().unwrap() == box 11);
 141     heap.push(box 5);
 142     assert_eq!(heap.len(), 5);
 143     assert!(*heap.peek().unwrap() == box 11);
 144     heap.push(box 27);
 145     assert_eq!(heap.len(), 6);
 146     assert!(*heap.peek().unwrap() == box 27);
 147     heap.push(box 3);
 148     assert_eq!(heap.len(), 7);
 149     assert!(*heap.peek().unwrap() == box 27);
 150     heap.push(box 103);
 151     assert_eq!(heap.len(), 8);
 152     assert!(*heap.peek().unwrap() == box 103);
 153 }
 154
 155 fn check_to_vec(mut data: Vec<i32>) {
 156     let heap = BinaryHeap::from(data.clone());
 157     let mut v = heap.clone().into_vec();
 158     v.sort();
 159     data.sort();
 160
 161     assert_eq!(v, data);
 162     assert_eq!(heap.into_sorted_vec(), data);
 163 }
 164
 165 #[test]
 166 fn test_to_vec() {
 167     check_to_vec(vec![]);
 168     check_to_vec(vec![5]);
 169     check_to_vec(vec![3, 2]);
 170     check_to_vec(vec![2, 3]);
 171     check_to_vec(vec![5, 1, 2]);
 172     check_to_vec(vec![1, 100, 2, 3]);
 173     check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
 174     check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
 175     check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
 176     check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 177     check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
 178     check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
 179     check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
 180 }
 181
 182 #[test]
 183 fn test_empty_pop() {
 184     let mut heap = BinaryHeap::<i32>::new();
 185     assert!(heap.pop().is_none());
 186 }
 187
 188 #[test]
 189 fn test_empty_peek() {
 190     let empty = BinaryHeap::<i32>::new();
 191     assert!(empty.peek().is_none());
 192 }
 193
 194 #[test]
 195 fn test_empty_peek_mut() {
 196     let mut empty = BinaryHeap::<i32>::new();
 197     assert!(empty.peek_mut().is_none());
 198 }
 199
 200 #[test]
 201 fn test_from_iter() {
 202     let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
 203
 204     let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
 205
 206     for &x in &xs {
 207         assert_eq!(q.pop().unwrap(), x);
 208     }
 209 }
 210
 211 #[test]
 212 fn test_drain() {
 213     let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
 214
 215     assert_eq!(q.drain().take(5).count(), 5);
 216
 217     assert!(q.is_empty());
 218 }
 219
 220 #[test]
 221 fn test_extend_ref() {
 222     let mut a = BinaryHeap::new();
 223     a.push(1);
 224     a.push(2);
 225
 226     a.extend(&[3, 4, 5]);
 227
 228     assert_eq!(a.len(), 5);
 229     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 230
 231     let mut a = BinaryHeap::new();
 232     a.push(1);
 233     a.push(2);
 234     let mut b = BinaryHeap::new();
 235     b.push(3);
 236     b.push(4);
 237     b.push(5);
 238
 239     a.extend(&b);
 240
 241     assert_eq!(a.len(), 5);
 242     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 243 }
 244
 245 #[test]
 246 fn test_append() {
 247     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 248     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 249
 250     a.append(&mut b);
 251
 252     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 253     assert!(b.is_empty());
 254 }
 255
 256 #[test]
 257 fn test_append_to_empty() {
 258     let mut a = BinaryHeap::new();
 259     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 260
 261     a.append(&mut b);
 262
 263     assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
 264     assert!(b.is_empty());
 265 }
 266
 267 #[test]
 268 fn test_extend_specialization() {
 269     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 270     let b = BinaryHeap::from(vec![-20, 5, 43]);
 271
 272     a.extend(b);
 273
 274     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 275 }
 276
 277 #[test]
 278 fn test_placement() {
 279     let mut a = BinaryHeap::new();
 280     &mut a <- 2;
 281     &mut a <- 4;
 282     &mut a <- 3;
 283     assert_eq!(a.peek(), Some(&4));
 284     assert_eq!(a.len(), 3);
 285     &mut a <- 1;
 286     assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
 287 }
 288
 289 #[test]
 290 fn test_placement_panic() {
 291     let mut heap = BinaryHeap::from(vec![1, 2, 3]);
 292     fn mkpanic() -> usize { panic!() }
 293     let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { &mut heap <- mkpanic(); }));
 294     assert_eq!(heap.len(), 3);
 295 }
 296
 297 #[allow(dead_code)]
 298 fn assert_covariance() {
 299     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 300         d
 301     }
 302 }