]>
Commit | Line | Data |
---|---|---|
04454e1e FG |
1 | use super::*; |
2 | use crate::boxed::Box; | |
e74abb32 | 3 | use std::iter::TrustedLen; |
74b04a01 XL |
4 | use std::panic::{catch_unwind, AssertUnwindSafe}; |
5 | use std::sync::atomic::{AtomicU32, Ordering}; | |
c34b1796 AL |
6 | |
7 | #[test] | |
8 | fn test_iterator() { | |
9 | let data = vec![5, 9, 3]; | |
10 | let iterout = [9, 5, 3]; | |
9cc50fc6 | 11 | let heap = BinaryHeap::from(data); |
c34b1796 AL |
12 | let mut i = 0; |
13 | for el in &heap { | |
14 | assert_eq!(*el, iterout[i]); | |
15 | i += 1; | |
16 | } | |
17 | } | |
18 | ||
19 | #[test] | |
e74abb32 | 20 | fn test_iter_rev_cloned_collect() { |
c34b1796 AL |
21 | let data = vec![5, 9, 3]; |
22 | let iterout = vec![3, 5, 9]; | |
9cc50fc6 | 23 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
24 | |
25 | let v: Vec<_> = pq.iter().rev().cloned().collect(); | |
26 | assert_eq!(v, iterout); | |
27 | } | |
28 | ||
29 | #[test] | |
e74abb32 | 30 | fn test_into_iter_collect() { |
c34b1796 AL |
31 | let data = vec![5, 9, 3]; |
32 | let iterout = vec![9, 5, 3]; | |
9cc50fc6 | 33 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
34 | |
35 | let v: Vec<_> = pq.into_iter().collect(); | |
36 | assert_eq!(v, iterout); | |
37 | } | |
38 | ||
39 | #[test] | |
e74abb32 | 40 | fn test_into_iter_size_hint() { |
c34b1796 | 41 | let data = vec![5, 9]; |
9cc50fc6 | 42 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
43 | |
44 | let mut it = pq.into_iter(); | |
45 | ||
46 | assert_eq!(it.size_hint(), (2, Some(2))); | |
47 | assert_eq!(it.next(), Some(9)); | |
48 | ||
49 | assert_eq!(it.size_hint(), (1, Some(1))); | |
50 | assert_eq!(it.next(), Some(5)); | |
51 | ||
52 | assert_eq!(it.size_hint(), (0, Some(0))); | |
53 | assert_eq!(it.next(), None); | |
54 | } | |
55 | ||
56 | #[test] | |
e74abb32 | 57 | fn test_into_iter_rev_collect() { |
c34b1796 AL |
58 | let data = vec![5, 9, 3]; |
59 | let iterout = vec![3, 5, 9]; | |
9cc50fc6 | 60 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
61 | |
62 | let v: Vec<_> = pq.into_iter().rev().collect(); | |
63 | assert_eq!(v, iterout); | |
64 | } | |
65 | ||
e74abb32 XL |
66 | #[test] |
67 | fn test_into_iter_sorted_collect() { | |
68 | let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); | |
69 | let it = heap.into_iter_sorted(); | |
70 | let sorted = it.collect::<Vec<_>>(); | |
71 | assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]); | |
72 | } | |
73 | ||
74 | #[test] | |
75 | fn test_drain_sorted_collect() { | |
76 | let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); | |
77 | let it = heap.drain_sorted(); | |
78 | let sorted = it.collect::<Vec<_>>(); | |
79 | assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]); | |
80 | } | |
81 | ||
82 | fn check_exact_size_iterator<I: ExactSizeIterator>(len: usize, it: I) { | |
83 | let mut it = it; | |
84 | ||
85 | for i in 0..it.len() { | |
86 | let (lower, upper) = it.size_hint(); | |
87 | assert_eq!(Some(lower), upper); | |
88 | assert_eq!(lower, len - i); | |
89 | assert_eq!(it.len(), len - i); | |
90 | it.next(); | |
91 | } | |
92 | assert_eq!(it.len(), 0); | |
93 | assert!(it.is_empty()); | |
94 | } | |
95 | ||
96 | #[test] | |
97 | fn test_exact_size_iterator() { | |
98 | let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); | |
99 | check_exact_size_iterator(heap.len(), heap.iter()); | |
100 | check_exact_size_iterator(heap.len(), heap.clone().into_iter()); | |
101 | check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted()); | |
102 | check_exact_size_iterator(heap.len(), heap.clone().drain()); | |
103 | check_exact_size_iterator(heap.len(), heap.clone().drain_sorted()); | |
104 | } | |
105 | ||
106 | fn check_trusted_len<I: TrustedLen>(len: usize, it: I) { | |
107 | let mut it = it; | |
108 | for i in 0..len { | |
109 | let (lower, upper) = it.size_hint(); | |
110 | if upper.is_some() { | |
111 | assert_eq!(Some(lower), upper); | |
112 | assert_eq!(lower, len - i); | |
113 | } | |
114 | it.next(); | |
115 | } | |
116 | } | |
117 | ||
118 | #[test] | |
119 | fn test_trusted_len() { | |
120 | let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); | |
121 | check_trusted_len(heap.len(), heap.clone().into_iter_sorted()); | |
122 | check_trusted_len(heap.len(), heap.clone().drain_sorted()); | |
123 | } | |
124 | ||
c34b1796 AL |
125 | #[test] |
126 | fn test_peek_and_pop() { | |
127 | let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; | |
128 | let mut sorted = data.clone(); | |
129 | sorted.sort(); | |
9cc50fc6 | 130 | let mut heap = BinaryHeap::from(data); |
c34b1796 AL |
131 | while !heap.is_empty() { |
132 | assert_eq!(heap.peek().unwrap(), sorted.last().unwrap()); | |
133 | assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap()); | |
134 | } | |
135 | } | |
136 | ||
3157f602 XL |
137 | #[test] |
138 | fn test_peek_mut() { | |
139 | let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; | |
140 | let mut heap = BinaryHeap::from(data); | |
141 | assert_eq!(heap.peek(), Some(&10)); | |
142 | { | |
143 | let mut top = heap.peek_mut().unwrap(); | |
144 | *top -= 2; | |
145 | } | |
146 | assert_eq!(heap.peek(), Some(&9)); | |
147 | } | |
148 | ||
32a655c1 SL |
149 | #[test] |
150 | fn test_peek_mut_pop() { | |
151 | let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; | |
152 | let mut heap = BinaryHeap::from(data); | |
153 | assert_eq!(heap.peek(), Some(&10)); | |
154 | { | |
155 | let mut top = heap.peek_mut().unwrap(); | |
156 | *top -= 2; | |
157 | assert_eq!(PeekMut::pop(top), 8); | |
158 | } | |
159 | assert_eq!(heap.peek(), Some(&9)); | |
160 | } | |
161 | ||
c34b1796 AL |
162 | #[test] |
163 | fn test_push() { | |
9cc50fc6 | 164 | let mut heap = BinaryHeap::from(vec![2, 4, 9]); |
c34b1796 AL |
165 | assert_eq!(heap.len(), 3); |
166 | assert!(*heap.peek().unwrap() == 9); | |
167 | heap.push(11); | |
168 | assert_eq!(heap.len(), 4); | |
169 | assert!(*heap.peek().unwrap() == 11); | |
170 | heap.push(5); | |
171 | assert_eq!(heap.len(), 5); | |
172 | assert!(*heap.peek().unwrap() == 11); | |
173 | heap.push(27); | |
174 | assert_eq!(heap.len(), 6); | |
175 | assert!(*heap.peek().unwrap() == 27); | |
176 | heap.push(3); | |
177 | assert_eq!(heap.len(), 7); | |
178 | assert!(*heap.peek().unwrap() == 27); | |
179 | heap.push(103); | |
180 | assert_eq!(heap.len(), 8); | |
181 | assert!(*heap.peek().unwrap() == 103); | |
182 | } | |
183 | ||
184 | #[test] | |
185 | fn test_push_unique() { | |
923072b8 | 186 | let mut heap = BinaryHeap::<Box<_>>::from(vec![Box::new(2), Box::new(4), Box::new(9)]); |
c34b1796 | 187 | assert_eq!(heap.len(), 3); |
7cac9316 | 188 | assert!(**heap.peek().unwrap() == 9); |
923072b8 | 189 | heap.push(Box::new(11)); |
c34b1796 | 190 | assert_eq!(heap.len(), 4); |
7cac9316 | 191 | assert!(**heap.peek().unwrap() == 11); |
923072b8 | 192 | heap.push(Box::new(5)); |
c34b1796 | 193 | assert_eq!(heap.len(), 5); |
7cac9316 | 194 | assert!(**heap.peek().unwrap() == 11); |
923072b8 | 195 | heap.push(Box::new(27)); |
c34b1796 | 196 | assert_eq!(heap.len(), 6); |
7cac9316 | 197 | assert!(**heap.peek().unwrap() == 27); |
923072b8 | 198 | heap.push(Box::new(3)); |
c34b1796 | 199 | assert_eq!(heap.len(), 7); |
7cac9316 | 200 | assert!(**heap.peek().unwrap() == 27); |
923072b8 | 201 | heap.push(Box::new(103)); |
c34b1796 | 202 | assert_eq!(heap.len(), 8); |
7cac9316 | 203 | assert!(**heap.peek().unwrap() == 103); |
c34b1796 AL |
204 | } |
205 | ||
c34b1796 | 206 | fn check_to_vec(mut data: Vec<i32>) { |
9cc50fc6 | 207 | let heap = BinaryHeap::from(data.clone()); |
c34b1796 AL |
208 | let mut v = heap.clone().into_vec(); |
209 | v.sort(); | |
210 | data.sort(); | |
211 | ||
212 | assert_eq!(v, data); | |
213 | assert_eq!(heap.into_sorted_vec(), data); | |
214 | } | |
215 | ||
216 | #[test] | |
217 | fn test_to_vec() { | |
218 | check_to_vec(vec![]); | |
219 | check_to_vec(vec![5]); | |
220 | check_to_vec(vec![3, 2]); | |
221 | check_to_vec(vec![2, 3]); | |
222 | check_to_vec(vec![5, 1, 2]); | |
223 | check_to_vec(vec![1, 100, 2, 3]); | |
224 | check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]); | |
225 | check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); | |
226 | check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]); | |
227 | check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); | |
228 | check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]); | |
229 | check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]); | |
230 | check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]); | |
231 | } | |
232 | ||
1b1a35ee XL |
233 | #[test] |
234 | fn test_in_place_iterator_specialization() { | |
235 | let src: Vec<usize> = vec![1, 2, 3]; | |
236 | let src_ptr = src.as_ptr(); | |
237 | let heap: BinaryHeap<_> = src.into_iter().map(std::convert::identity).collect(); | |
238 | let heap_ptr = heap.iter().next().unwrap() as *const usize; | |
239 | assert_eq!(src_ptr, heap_ptr); | |
240 | let sink: Vec<_> = heap.into_iter().map(std::convert::identity).collect(); | |
241 | let sink_ptr = sink.as_ptr(); | |
242 | assert_eq!(heap_ptr, sink_ptr); | |
243 | } | |
244 | ||
c34b1796 AL |
245 | #[test] |
246 | fn test_empty_pop() { | |
247 | let mut heap = BinaryHeap::<i32>::new(); | |
248 | assert!(heap.pop().is_none()); | |
249 | } | |
250 | ||
251 | #[test] | |
252 | fn test_empty_peek() { | |
253 | let empty = BinaryHeap::<i32>::new(); | |
254 | assert!(empty.peek().is_none()); | |
255 | } | |
256 | ||
3157f602 XL |
257 | #[test] |
258 | fn test_empty_peek_mut() { | |
259 | let mut empty = BinaryHeap::<i32>::new(); | |
260 | assert!(empty.peek_mut().is_none()); | |
261 | } | |
262 | ||
c34b1796 AL |
263 | #[test] |
264 | fn test_from_iter() { | |
265 | let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1]; | |
266 | ||
267 | let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect(); | |
268 | ||
269 | for &x in &xs { | |
270 | assert_eq!(q.pop().unwrap(), x); | |
271 | } | |
272 | } | |
273 | ||
274 | #[test] | |
275 | fn test_drain() { | |
276 | let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect(); | |
277 | ||
278 | assert_eq!(q.drain().take(5).count(), 5); | |
279 | ||
280 | assert!(q.is_empty()); | |
281 | } | |
62682a34 | 282 | |
e74abb32 XL |
283 | #[test] |
284 | fn test_drain_sorted() { | |
285 | let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect(); | |
286 | ||
287 | assert_eq!(q.drain_sorted().take(5).collect::<Vec<_>>(), vec![9, 8, 7, 6, 5]); | |
288 | ||
289 | assert!(q.is_empty()); | |
290 | } | |
291 | ||
74b04a01 XL |
292 | #[test] |
293 | fn test_drain_sorted_leak() { | |
294 | static DROPS: AtomicU32 = AtomicU32::new(0); | |
295 | ||
296 | #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)] | |
297 | struct D(u32, bool); | |
298 | ||
299 | impl Drop for D { | |
300 | fn drop(&mut self) { | |
301 | DROPS.fetch_add(1, Ordering::SeqCst); | |
302 | ||
303 | if self.1 { | |
304 | panic!("panic in `drop`"); | |
305 | } | |
306 | } | |
307 | } | |
308 | ||
309 | let mut q = BinaryHeap::from(vec![ | |
310 | D(0, false), | |
311 | D(1, false), | |
312 | D(2, false), | |
313 | D(3, true), | |
314 | D(4, false), | |
315 | D(5, false), | |
316 | ]); | |
317 | ||
318 | catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).ok(); | |
319 | ||
320 | assert_eq!(DROPS.load(Ordering::SeqCst), 6); | |
321 | } | |
322 | ||
62682a34 SL |
323 | #[test] |
324 | fn test_extend_ref() { | |
325 | let mut a = BinaryHeap::new(); | |
326 | a.push(1); | |
327 | a.push(2); | |
328 | ||
329 | a.extend(&[3, 4, 5]); | |
330 | ||
331 | assert_eq!(a.len(), 5); | |
332 | assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); | |
333 | ||
334 | let mut a = BinaryHeap::new(); | |
335 | a.push(1); | |
336 | a.push(2); | |
337 | let mut b = BinaryHeap::new(); | |
338 | b.push(3); | |
339 | b.push(4); | |
340 | b.push(5); | |
341 | ||
342 | a.extend(&b); | |
343 | ||
344 | assert_eq!(a.len(), 5); | |
345 | assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); | |
346 | } | |
a7813a04 XL |
347 | |
348 | #[test] | |
349 | fn test_append() { | |
350 | let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); | |
351 | let mut b = BinaryHeap::from(vec![-20, 5, 43]); | |
352 | ||
353 | a.append(&mut b); | |
354 | ||
355 | assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); | |
356 | assert!(b.is_empty()); | |
357 | } | |
358 | ||
359 | #[test] | |
360 | fn test_append_to_empty() { | |
361 | let mut a = BinaryHeap::new(); | |
362 | let mut b = BinaryHeap::from(vec![-20, 5, 43]); | |
363 | ||
364 | a.append(&mut b); | |
365 | ||
366 | assert_eq!(a.into_sorted_vec(), [-20, 5, 43]); | |
367 | assert!(b.is_empty()); | |
368 | } | |
369 | ||
370 | #[test] | |
371 | fn test_extend_specialization() { | |
372 | let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); | |
373 | let b = BinaryHeap::from(vec![-20, 5, 43]); | |
374 | ||
375 | a.extend(b); | |
376 | ||
377 | assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); | |
378 | } | |
5bcae85e SL |
379 | |
380 | #[allow(dead_code)] | |
381 | fn assert_covariance() { | |
c30ab7b3 SL |
382 | fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { |
383 | d | |
384 | } | |
5bcae85e | 385 | } |
0531ce1d | 386 | |
f9f354fc XL |
387 | #[test] |
388 | fn test_retain() { | |
cdc7bbd5 XL |
389 | let mut a = BinaryHeap::from(vec![100, 10, 50, 1, 2, 20, 30]); |
390 | a.retain(|&x| x != 2); | |
f9f354fc | 391 | |
cdc7bbd5 XL |
392 | // Check that 20 moved into 10's place. |
393 | assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]); | |
394 | ||
395 | a.retain(|_| true); | |
396 | ||
397 | assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]); | |
398 | ||
399 | a.retain(|&x| x < 50); | |
400 | ||
401 | assert_eq!(a.clone().into_vec(), [30, 20, 10, 1]); | |
402 | ||
403 | a.retain(|_| false); | |
404 | ||
405 | assert!(a.is_empty()); | |
f9f354fc XL |
406 | } |
407 | ||
0531ce1d XL |
408 | // old binaryheap failed this test |
409 | // | |
410 | // Integrity means that all elements are present after a comparison panics, | |
94222f64 | 411 | // even if the order might not be correct. |
0531ce1d XL |
412 | // |
413 | // Destructors must be called exactly once per element. | |
e74abb32 | 414 | // FIXME: re-enable emscripten once it can unwind again |
0531ce1d | 415 | #[test] |
60c5eb7d | 416 | #[cfg(not(target_os = "emscripten"))] |
0531ce1d | 417 | fn panic_safe() { |
dfeec247 | 418 | use rand::{seq::SliceRandom, thread_rng}; |
e74abb32 XL |
419 | use std::cmp; |
420 | use std::panic::{self, AssertUnwindSafe}; | |
421 | use std::sync::atomic::{AtomicUsize, Ordering}; | |
e74abb32 | 422 | |
9fa01778 | 423 | static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0); |
0531ce1d XL |
424 | |
425 | #[derive(Eq, PartialEq, Ord, Clone, Debug)] | |
426 | struct PanicOrd<T>(T, bool); | |
427 | ||
428 | impl<T> Drop for PanicOrd<T> { | |
429 | fn drop(&mut self) { | |
430 | // update global drop count | |
431 | DROP_COUNTER.fetch_add(1, Ordering::SeqCst); | |
432 | } | |
433 | } | |
434 | ||
435 | impl<T: PartialOrd> PartialOrd for PanicOrd<T> { | |
436 | fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> { | |
437 | if self.1 || other.1 { | |
438 | panic!("Panicking comparison"); | |
439 | } | |
440 | self.0.partial_cmp(&other.0) | |
441 | } | |
442 | } | |
443 | let mut rng = thread_rng(); | |
444 | const DATASZ: usize = 32; | |
f9f354fc XL |
445 | // Miri is too slow |
446 | let ntest = if cfg!(miri) { 1 } else { 10 }; | |
0531ce1d XL |
447 | |
448 | // don't use 0 in the data -- we want to catch the zeroed-out case. | |
0731742a | 449 | let data = (1..=DATASZ).collect::<Vec<_>>(); |
0531ce1d XL |
450 | |
451 | // since it's a fuzzy test, run several tries. | |
f9f354fc | 452 | for _ in 0..ntest { |
0731742a | 453 | for i in 1..=DATASZ { |
0531ce1d XL |
454 | DROP_COUNTER.store(0, Ordering::SeqCst); |
455 | ||
dfeec247 XL |
456 | let mut panic_ords: Vec<_> = |
457 | data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect(); | |
0531ce1d XL |
458 | let panic_item = PanicOrd(i, true); |
459 | ||
460 | // heapify the sane items | |
0731742a | 461 | panic_ords.shuffle(&mut rng); |
0531ce1d XL |
462 | let mut heap = BinaryHeap::from(panic_ords); |
463 | let inner_data; | |
464 | ||
465 | { | |
466 | // push the panicking item to the heap and catch the panic | |
467 | let thread_result = { | |
468 | let mut heap_ref = AssertUnwindSafe(&mut heap); | |
469 | panic::catch_unwind(move || { | |
470 | heap_ref.push(panic_item); | |
471 | }) | |
472 | }; | |
473 | assert!(thread_result.is_err()); | |
474 | ||
475 | // Assert no elements were dropped | |
476 | let drops = DROP_COUNTER.load(Ordering::SeqCst); | |
477 | assert!(drops == 0, "Must not drop items. drops={}", drops); | |
478 | inner_data = heap.clone().into_vec(); | |
479 | drop(heap); | |
480 | } | |
481 | let drops = DROP_COUNTER.load(Ordering::SeqCst); | |
482 | assert_eq!(drops, DATASZ); | |
483 | ||
484 | let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>(); | |
485 | data_sorted.sort(); | |
486 | assert_eq!(data_sorted, data); | |
487 | } | |
488 | } | |
489 | } |