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