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.
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.
12 use std::collections::BinaryHeap;
13 use std::collections::binary_heap::{Drain, PeekMut};
17 let data = vec![5, 9, 3];
18 let iterout = [9, 5, 3];
19 let heap = BinaryHeap::from(data);
22 assert_eq!(*el, iterout[i]);
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);
33 let v: Vec<_> = pq.iter().rev().cloned().collect();
34 assert_eq!(v, iterout);
39 let data = vec![5, 9, 3];
40 let iterout = vec![9, 5, 3];
41 let pq = BinaryHeap::from(data);
43 let v: Vec<_> = pq.into_iter().collect();
44 assert_eq!(v, iterout);
48 fn test_move_iter_size_hint() {
49 let data = vec![5, 9];
50 let pq = BinaryHeap::from(data);
52 let mut it = pq.into_iter();
54 assert_eq!(it.size_hint(), (2, Some(2)));
55 assert_eq!(it.next(), Some(9));
57 assert_eq!(it.size_hint(), (1, Some(1)));
58 assert_eq!(it.next(), Some(5));
60 assert_eq!(it.size_hint(), (0, Some(0)));
61 assert_eq!(it.next(), None);
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);
70 let v: Vec<_> = pq.into_iter().rev().collect();
71 assert_eq!(v, iterout);
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();
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());
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));
92 let mut top = heap.peek_mut().unwrap();
95 assert_eq!(heap.peek(), Some(&9));
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));
104 let mut top = heap.peek_mut().unwrap();
106 assert_eq!(PeekMut::pop(top), 8);
108 assert_eq!(heap.peek(), Some(&9));
113 let mut heap = BinaryHeap::from(vec![2, 4, 9]);
114 assert_eq!(heap.len(), 3);
115 assert!(*heap.peek().unwrap() == 9);
117 assert_eq!(heap.len(), 4);
118 assert!(*heap.peek().unwrap() == 11);
120 assert_eq!(heap.len(), 5);
121 assert!(*heap.peek().unwrap() == 11);
123 assert_eq!(heap.len(), 6);
124 assert!(*heap.peek().unwrap() == 27);
126 assert_eq!(heap.len(), 7);
127 assert!(*heap.peek().unwrap() == 27);
129 assert_eq!(heap.len(), 8);
130 assert!(*heap.peek().unwrap() == 103);
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);
139 assert_eq!(heap.len(), 4);
140 assert!(*heap.peek().unwrap() == box 11);
142 assert_eq!(heap.len(), 5);
143 assert!(*heap.peek().unwrap() == box 11);
145 assert_eq!(heap.len(), 6);
146 assert!(*heap.peek().unwrap() == box 27);
148 assert_eq!(heap.len(), 7);
149 assert!(*heap.peek().unwrap() == box 27);
151 assert_eq!(heap.len(), 8);
152 assert!(*heap.peek().unwrap() == box 103);
155 fn check_to_vec(mut data: Vec<i32>) {
156 let heap = BinaryHeap::from(data.clone());
157 let mut v = heap.clone().into_vec();
162 assert_eq!(heap.into_sorted_vec(), data);
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]);
183 fn test_empty_pop() {
184 let mut heap = BinaryHeap::<i32>::new();
185 assert!(heap.pop().is_none());
189 fn test_empty_peek() {
190 let empty = BinaryHeap::<i32>::new();
191 assert!(empty.peek().is_none());
195 fn test_empty_peek_mut() {
196 let mut empty = BinaryHeap::<i32>::new();
197 assert!(empty.peek_mut().is_none());
201 fn test_from_iter() {
202 let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
204 let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
207 assert_eq!(q.pop().unwrap(), x);
213 let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
215 assert_eq!(q.drain().take(5).count(), 5);
217 assert!(q.is_empty());
221 fn test_extend_ref() {
222 let mut a = BinaryHeap::new();
226 a.extend(&[3, 4, 5]);
228 assert_eq!(a.len(), 5);
229 assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
231 let mut a = BinaryHeap::new();
234 let mut b = BinaryHeap::new();
241 assert_eq!(a.len(), 5);
242 assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
247 let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
248 let mut b = BinaryHeap::from(vec![-20, 5, 43]);
252 assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
253 assert!(b.is_empty());
257 fn test_append_to_empty() {
258 let mut a = BinaryHeap::new();
259 let mut b = BinaryHeap::from(vec![-20, 5, 43]);
263 assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
264 assert!(b.is_empty());
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]);
274 assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
278 fn test_placement() {
279 let mut a = BinaryHeap::new();
283 assert_eq!(a.peek(), Some(&4));
284 assert_eq!(a.len(), 3);
286 assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
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);
298 fn assert_covariance() {
299 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {