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