]>
Commit | Line | Data |
---|---|---|
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 | } |