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.
11 use std::collections::BinaryHeap;
15 let data = vec![5, 9, 3];
16 let iterout = [9, 5, 3];
17 let heap = BinaryHeap::from_vec(data);
20 assert_eq!(*el, iterout[i]);
26 fn test_iterator_reverse() {
27 let data = vec![5, 9, 3];
28 let iterout = vec![3, 5, 9];
29 let pq = BinaryHeap::from_vec(data);
31 let v: Vec<_> = pq.iter().rev().cloned().collect();
32 assert_eq!(v, iterout);
37 let data = vec![5, 9, 3];
38 let iterout = vec![9, 5, 3];
39 let pq = BinaryHeap::from_vec(data);
41 let v: Vec<_> = pq.into_iter().collect();
42 assert_eq!(v, iterout);
46 fn test_move_iter_size_hint() {
47 let data = vec![5, 9];
48 let pq = BinaryHeap::from_vec(data);
50 let mut it = pq.into_iter();
52 assert_eq!(it.size_hint(), (2, Some(2)));
53 assert_eq!(it.next(), Some(9));
55 assert_eq!(it.size_hint(), (1, Some(1)));
56 assert_eq!(it.next(), Some(5));
58 assert_eq!(it.size_hint(), (0, Some(0)));
59 assert_eq!(it.next(), None);
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_vec(data);
68 let v: Vec<_> = pq.into_iter().rev().collect();
69 assert_eq!(v, iterout);
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();
77 let mut heap = BinaryHeap::from_vec(data);
78 while !heap.is_empty() {
79 assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
80 assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
86 let mut heap = BinaryHeap::from_vec(vec![2, 4, 9]);
87 assert_eq!(heap.len(), 3);
88 assert!(*heap.peek().unwrap() == 9);
90 assert_eq!(heap.len(), 4);
91 assert!(*heap.peek().unwrap() == 11);
93 assert_eq!(heap.len(), 5);
94 assert!(*heap.peek().unwrap() == 11);
96 assert_eq!(heap.len(), 6);
97 assert!(*heap.peek().unwrap() == 27);
99 assert_eq!(heap.len(), 7);
100 assert!(*heap.peek().unwrap() == 27);
102 assert_eq!(heap.len(), 8);
103 assert!(*heap.peek().unwrap() == 103);
107 fn test_push_unique() {
108 let mut heap = BinaryHeap::<Box<_>>::from_vec(vec![box 2, box 4, box 9]);
109 assert_eq!(heap.len(), 3);
110 assert!(*heap.peek().unwrap() == box 9);
112 assert_eq!(heap.len(), 4);
113 assert!(*heap.peek().unwrap() == box 11);
115 assert_eq!(heap.len(), 5);
116 assert!(*heap.peek().unwrap() == box 11);
118 assert_eq!(heap.len(), 6);
119 assert!(*heap.peek().unwrap() == box 27);
121 assert_eq!(heap.len(), 7);
122 assert!(*heap.peek().unwrap() == box 27);
124 assert_eq!(heap.len(), 8);
125 assert!(*heap.peek().unwrap() == box 103);
130 let mut heap = BinaryHeap::from_vec(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);
144 let mut heap = BinaryHeap::from_vec(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);
156 fn check_to_vec(mut data: Vec<i32>) {
157 let heap = BinaryHeap::from_vec(data.clone());
158 let mut v = heap.clone().into_vec();
163 assert_eq!(heap.into_sorted_vec(), data);
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]);
184 fn test_empty_pop() {
185 let mut heap = BinaryHeap::<i32>::new();
186 assert!(heap.pop().is_none());
190 fn test_empty_peek() {
191 let empty = BinaryHeap::<i32>::new();
192 assert!(empty.peek().is_none());
196 fn test_empty_replace() {
197 let mut heap = BinaryHeap::new();
198 assert!(heap.replace(5).is_none());
202 fn test_from_iter() {
203 let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
205 let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
208 assert_eq!(q.pop().unwrap(), x);
214 let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
216 assert_eq!(q.drain().take(5).count(), 5);
218 assert!(q.is_empty());
222 fn test_extend_ref() {
223 let mut a = BinaryHeap::new();
227 a.extend(&[3, 4, 5]);
229 assert_eq!(a.len(), 5);
230 assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
232 let mut a = BinaryHeap::new();
235 let mut b = BinaryHeap::new();
242 assert_eq!(a.len(), 5);
243 assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);