binary_heap_plus/
lib.rs

1//! This crate provides [`BinaryHeap`] which is backward-compatible with
2//! [`std::collections::BinaryHeap`].
3//!
4//! Added features include:
5//! * Heaps other than max heap.
6//! * Optional [`serde`] feature.
7//!
8//! [`BinaryHeap`]: struct.BinaryHeap.html
9//! [`std::collections::BinaryHeap`]:
10//! https://doc.rust-lang.org/stable/std/collections/struct.BinaryHeap.html
11//! [`serde`]: https://docs.serde.rs/serde/
12//!
13//! # Quick start
14//!
15//! ## Max/Min Heap
16//!
17//! For max heap, [`BinaryHeap::from_vec()`] is the most versatile way to create a heap.
18//!
19//! ```rust
20//! use binary_heap_plus::*;
21//!
22//! // max heap
23//! let mut h: BinaryHeap<i32> = BinaryHeap::from_vec(vec![]);
24//! // max heap with initial capacity
25//! let mut h: BinaryHeap<i32> = BinaryHeap::from_vec(Vec::with_capacity(16));
26//! // max heap from iterator
27//! let mut h: BinaryHeap<i32> = BinaryHeap::from_vec((0..42).collect());
28//! assert_eq!(h.pop(), Some(41));
29//! ```
30//!
31//! Min heap is similar, but requires type annotation.
32//!
33//! ```rust
34//! use binary_heap_plus::*;
35//!
36//! // min heap
37//! let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(vec![]);
38//! // min heap with initial capacity
39//! let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(Vec::with_capacity(16));
40//! // min heap from iterator
41//! let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec((0..42).collect());
42//! assert_eq!(h.pop(), Some(0));
43//! ```
44//!
45//! [`BinaryHeap::from_vec()`]: struct.BinaryHeap.html#method.from_vec
46//!
47//! ## Custom Heap
48//!
49//! For custom heap, [`BinaryHeap::from_vec_cmp()`] works in a similar way to max/min heap. The
50//! only difference is that you add the comparator closure with apropriate signature.
51//!
52//! ```rust
53//! use binary_heap_plus::*;
54//!
55//! // custom heap: ordered by second value (_.1) of the tuples; min first
56//! let mut h = BinaryHeap::from_vec_cmp(
57//!     vec![(1, 5), (3, 2), (2, 3)],
58//!     |a: &(i32, i32), b: &(i32, i32)| b.1.cmp(&a.1), // comparator closure here
59//! );
60//! assert_eq!(h.pop(), Some((3, 2)));
61//! ```
62//!
63//! [`BinaryHeap::from_vec_cmp()`]: struct.BinaryHeap.html#method.from_vec_cmp
64//!
65//! # Constructers
66//!
67//! ## Generic methods to create different kind of heaps from initial `vec` data.
68//!
69//! * [`BinaryHeap::from_vec`]`(vec)`
70//! * [`BinaryHeap::from_vec_cmp`]`(vec, cmp)`
71//!
72//! [`BinaryHeap::from_vec`]: struct.BinaryHeap.html#method.from_vec
73//! [`BinaryHeap::from_vec_cmp`]: struct.BinaryHeap.html#method.from_vec_cmp
74//!
75//! ```
76//! use binary_heap_plus::*;
77//!
78//! // max heap (default)
79//! let mut heap: BinaryHeap<i32> = BinaryHeap::from_vec(vec![1,5,3]);
80//! assert_eq!(heap.pop(), Some(5));
81//!
82//! // min heap
83//! let mut heap: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(vec![1,5,3]);
84//! assert_eq!(heap.pop(), Some(1));
85//!
86//! // custom-sort heap
87//! let mut heap = BinaryHeap::from_vec_cmp(vec![1,5,3], |a: &i32, b: &i32| b.cmp(a));
88//! assert_eq!(heap.pop(), Some(1));
89//!
90//! // custom-key heap
91//! let mut heap = BinaryHeap::from_vec_cmp(vec![6,3,1], KeyComparator(|k: &i32| k % 4));
92//! assert_eq!(heap.pop(), Some(3));
93//!
94//! // TIP: How to reuse a comparator
95//! let mod4_comparator = KeyComparator(|k: &_| k % 4);
96//! let mut heap1 = BinaryHeap::from_vec_cmp(vec![6,3,1], mod4_comparator);
97//! assert_eq!(heap1.pop(), Some(3));
98//! let mut heap2 = BinaryHeap::from_vec_cmp(vec![2,4,1], mod4_comparator);
99//! assert_eq!(heap2.pop(), Some(2));
100//! ```
101//!
102//! ## Dedicated methods to create different kind of heaps
103//!
104//! * [`BinaryHeap::new()`] creates a max heap.
105//! * [`BinaryHeap::new_min()`] creates a min heap.
106//! * [`BinaryHeap::new_by()`] creates a heap sorted by the given closure.
107//! * [`BinaryHeap::new_by_key()`] creates a heap sorted by the key generated by the given closure.
108//!
109//! [`BinaryHeap::new()`]: struct.BinaryHeap.html#method.new
110//! [`BinaryHeap::new_min()`]: struct.BinaryHeap.html#method.new_min
111//! [`BinaryHeap::new_by()`]: struct.BinaryHeap.html#method.new_by
112//! [`BinaryHeap::new_by_key()`]: struct.BinaryHeap.html#method.new_by_key
113
114mod binary_heap;
115pub use crate::binary_heap::*;
116
117/// An intermediate trait for specialization of `Extend`.
118// #[doc(hidden)]
119// trait SpecExtend<I: IntoIterator> {
120//     /// Extends `self` with the contents of the given iterator.
121//     fn spec_extend(&mut self, iter: I);
122// }
123
124#[cfg(test)]
125mod from_liballoc {
126    // The following tests copyed from liballoc/tests/binary_heap.rs
127
128    use super::binary_heap::*;
129    // use std::panic;
130    // use std::collections::BinaryHeap;
131    // use std::collections::binary_heap::{Drain, PeekMut};
132
133    #[test]
134    fn test_iterator() {
135        let data = vec![5, 9, 3];
136        let iterout = [9, 5, 3];
137        let heap = BinaryHeap::from(data);
138        let mut i = 0;
139        for el in &heap {
140            assert_eq!(*el, iterout[i]);
141            i += 1;
142        }
143    }
144
145    #[test]
146    fn test_iterator_reverse() {
147        let data = vec![5, 9, 3];
148        let iterout = vec![3, 5, 9];
149        let pq = BinaryHeap::from(data);
150
151        let v: Vec<_> = pq.iter().rev().cloned().collect();
152        assert_eq!(v, iterout);
153    }
154
155    #[test]
156    fn test_move_iter() {
157        let data = vec![5, 9, 3];
158        let iterout = vec![9, 5, 3];
159        let pq = BinaryHeap::from(data);
160
161        let v: Vec<_> = pq.into_iter().collect();
162        assert_eq!(v, iterout);
163    }
164
165    #[test]
166    fn test_move_iter_size_hint() {
167        let data = vec![5, 9];
168        let pq = BinaryHeap::from(data);
169
170        let mut it = pq.into_iter();
171
172        assert_eq!(it.size_hint(), (2, Some(2)));
173        assert_eq!(it.next(), Some(9));
174
175        assert_eq!(it.size_hint(), (1, Some(1)));
176        assert_eq!(it.next(), Some(5));
177
178        assert_eq!(it.size_hint(), (0, Some(0)));
179        assert_eq!(it.next(), None);
180    }
181
182    #[test]
183    fn test_move_iter_reverse() {
184        let data = vec![5, 9, 3];
185        let iterout = vec![3, 5, 9];
186        let pq = BinaryHeap::from(data);
187
188        let v: Vec<_> = pq.into_iter().rev().collect();
189        assert_eq!(v, iterout);
190    }
191
192    #[test]
193    fn test_into_iter_sorted_collect() {
194        let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
195        let it = heap.into_iter_sorted();
196        let sorted = it.collect::<Vec<_>>();
197        assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
198    }
199
200    #[test]
201    fn test_peek_and_pop() {
202        let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
203        let mut sorted = data.clone();
204        sorted.sort();
205        let mut heap = BinaryHeap::from(data);
206        while !heap.is_empty() {
207            assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
208            assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
209        }
210    }
211
212    #[test]
213    fn test_peek_mut() {
214        let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
215        let mut heap = BinaryHeap::from(data);
216        assert_eq!(heap.peek(), Some(&10));
217        {
218            let mut top = heap.peek_mut().unwrap();
219            *top -= 2;
220        }
221        assert_eq!(heap.peek(), Some(&9));
222    }
223
224    #[test]
225    fn test_peek_mut_pop() {
226        let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
227        let mut heap = BinaryHeap::from(data);
228        assert_eq!(heap.peek(), Some(&10));
229        {
230            let mut top = heap.peek_mut().unwrap();
231            *top -= 2;
232            assert_eq!(PeekMut::pop(top), 8);
233        }
234        assert_eq!(heap.peek(), Some(&9));
235    }
236
237    #[test]
238    fn test_push() {
239        let mut heap = BinaryHeap::from(vec![2, 4, 9]);
240        assert_eq!(heap.len(), 3);
241        assert!(*heap.peek().unwrap() == 9);
242        heap.push(11);
243        assert_eq!(heap.len(), 4);
244        assert!(*heap.peek().unwrap() == 11);
245        heap.push(5);
246        assert_eq!(heap.len(), 5);
247        assert!(*heap.peek().unwrap() == 11);
248        heap.push(27);
249        assert_eq!(heap.len(), 6);
250        assert!(*heap.peek().unwrap() == 27);
251        heap.push(3);
252        assert_eq!(heap.len(), 7);
253        assert!(*heap.peek().unwrap() == 27);
254        heap.push(103);
255        assert_eq!(heap.len(), 8);
256        assert!(*heap.peek().unwrap() == 103);
257    }
258
259    // #[test]
260    // fn test_push_unique() {
261    //     let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
262    //     assert_eq!(heap.len(), 3);
263    //     assert!(**heap.peek().unwrap() == 9);
264    //     heap.push(box 11);
265    //     assert_eq!(heap.len(), 4);
266    //     assert!(**heap.peek().unwrap() == 11);
267    //     heap.push(box 5);
268    //     assert_eq!(heap.len(), 5);
269    //     assert!(**heap.peek().unwrap() == 11);
270    //     heap.push(box 27);
271    //     assert_eq!(heap.len(), 6);
272    //     assert!(**heap.peek().unwrap() == 27);
273    //     heap.push(box 3);
274    //     assert_eq!(heap.len(), 7);
275    //     assert!(**heap.peek().unwrap() == 27);
276    //     heap.push(box 103);
277    //     assert_eq!(heap.len(), 8);
278    //     assert!(**heap.peek().unwrap() == 103);
279    // }
280
281    fn check_to_vec(mut data: Vec<i32>) {
282        let heap = BinaryHeap::from(data.clone());
283        let mut v = heap.clone().into_vec();
284        v.sort();
285        data.sort();
286
287        assert_eq!(v, data);
288        assert_eq!(heap.into_sorted_vec(), data);
289    }
290
291    #[test]
292    fn test_to_vec() {
293        check_to_vec(vec![]);
294        check_to_vec(vec![5]);
295        check_to_vec(vec![3, 2]);
296        check_to_vec(vec![2, 3]);
297        check_to_vec(vec![5, 1, 2]);
298        check_to_vec(vec![1, 100, 2, 3]);
299        check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
300        check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
301        check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
302        check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
303        check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
304        check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
305        check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
306    }
307
308    #[test]
309    fn test_empty_pop() {
310        let mut heap = BinaryHeap::<i32>::new();
311        assert!(heap.pop().is_none());
312    }
313
314    #[test]
315    fn test_empty_peek() {
316        let empty = BinaryHeap::<i32>::new();
317        assert!(empty.peek().is_none());
318    }
319
320    #[test]
321    fn test_empty_peek_mut() {
322        let mut empty = BinaryHeap::<i32>::new();
323        assert!(empty.peek_mut().is_none());
324    }
325
326    #[test]
327    fn test_from_iter() {
328        let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
329
330        let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
331
332        for &x in &xs {
333            assert_eq!(q.pop().unwrap(), x);
334        }
335    }
336
337    #[test]
338    fn test_drain() {
339        let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
340
341        assert_eq!(q.drain().take(5).count(), 5);
342
343        assert!(q.is_empty());
344    }
345
346    #[test]
347    fn test_extend_ref() {
348        let mut a = BinaryHeap::new();
349        a.push(1);
350        a.push(2);
351
352        a.extend(&[3, 4, 5]);
353
354        assert_eq!(a.len(), 5);
355        assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
356
357        let mut a = BinaryHeap::new();
358        a.push(1);
359        a.push(2);
360        let mut b = BinaryHeap::new();
361        b.push(3);
362        b.push(4);
363        b.push(5);
364
365        a.extend(&b);
366
367        assert_eq!(a.len(), 5);
368        assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
369    }
370
371    #[test]
372    fn test_append() {
373        let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
374        let mut b = BinaryHeap::from(vec![-20, 5, 43]);
375
376        a.append(&mut b);
377
378        assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
379        assert!(b.is_empty());
380    }
381
382    #[test]
383    fn test_append_to_empty() {
384        let mut a = BinaryHeap::new();
385        let mut b = BinaryHeap::from(vec![-20, 5, 43]);
386
387        a.append(&mut b);
388
389        assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
390        assert!(b.is_empty());
391    }
392
393    #[test]
394    fn test_extend_specialization() {
395        let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
396        let b = BinaryHeap::from(vec![-20, 5, 43]);
397
398        a.extend(b);
399
400        assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
401    }
402
403    // #[test]
404    // fn test_placement() {
405    //     let mut a = BinaryHeap::new();
406    //     &mut a <- 2;
407    //     &mut a <- 4;
408    //     &mut a <- 3;
409    //     assert_eq!(a.peek(), Some(&4));
410    //     assert_eq!(a.len(), 3);
411    //     &mut a <- 1;
412    //     assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
413    // }
414
415    // #[test]
416    // fn test_placement_panic() {
417    //     let mut heap = BinaryHeap::from(vec![1, 2, 3]);
418    //     fn mkpanic() -> usize {
419    //         panic!()
420    //     }
421    //     let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| {
422    //         &mut heap <- mkpanic();
423    //     }));
424    //     assert_eq!(heap.len(), 3);
425    // }
426
427    #[allow(dead_code)]
428    fn assert_covariance() {
429        fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
430            d
431        }
432    }
433
434    // old binaryheap failed this test
435    //
436    // Integrity means that all elements are present after a comparison panics,
437    // even if the order might not be correct.
438    //
439    // Destructors must be called exactly once per element.
440    // FIXME: re-enable emscripten once it can unwind again
441    #[test]
442    #[cfg(not(target_os = "emscripten"))]
443    fn panic_safe() {
444        use std::cmp;
445        use std::panic::{self, AssertUnwindSafe};
446        use std::sync::atomic::{AtomicUsize, Ordering};
447
448        use rand::{seq::SliceRandom, thread_rng};
449
450        static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
451
452        #[derive(Eq, PartialEq, PartialOrd, Clone, Debug)]
453        struct PanicOrd<T>(T, bool);
454
455        impl<T> Drop for PanicOrd<T> {
456            fn drop(&mut self) {
457                // update global drop count
458                DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
459            }
460        }
461
462        impl<T: Ord> Ord for PanicOrd<T> {
463            fn cmp(&self, other: &Self) -> cmp::Ordering {
464                if self.1 || other.1 {
465                    panic!("Panicking comparison");
466                }
467                self.0.cmp(&other.0)
468            }
469        }
470        let mut rng = thread_rng();
471        const DATASZ: usize = 32;
472        // Miri is too slow
473        let ntest = if cfg!(miri) { 1 } else { 10 };
474
475        // don't use 0 in the data -- we want to catch the zeroed-out case.
476        let data = (1..=DATASZ).collect::<Vec<_>>();
477
478        // since it's a fuzzy test, run several tries.
479        for _ in 0..ntest {
480            for i in 1..=DATASZ {
481                DROP_COUNTER.store(0, Ordering::SeqCst);
482
483                let mut panic_ords: Vec<_> = data
484                    .iter()
485                    .filter(|&&x| x != i)
486                    .map(|&x| PanicOrd(x, false))
487                    .collect();
488                let panic_item = PanicOrd(i, true);
489
490                // heapify the sane items
491                panic_ords.shuffle(&mut rng);
492                let mut heap = BinaryHeap::from(panic_ords);
493                let inner_data;
494
495                {
496                    // push the panicking item to the heap and catch the panic
497                    let thread_result = {
498                        let mut heap_ref = AssertUnwindSafe(&mut heap);
499                        panic::catch_unwind(move || {
500                            heap_ref.push(panic_item);
501                        })
502                    };
503                    assert!(thread_result.is_err());
504
505                    // Assert no elements were dropped
506                    let drops = DROP_COUNTER.load(Ordering::SeqCst);
507                    assert!(drops == 0, "Must not drop items. drops={}", drops);
508                    inner_data = heap.clone().into_vec();
509                    drop(heap);
510                }
511                let drops = DROP_COUNTER.load(Ordering::SeqCst);
512                assert_eq!(drops, DATASZ);
513
514                let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
515                data_sorted.sort();
516                assert_eq!(data_sorted, data);
517            }
518        }
519    }
520}
521
522#[cfg(feature = "serde")]
523#[cfg(test)]
524mod tests_serde {
525    use super::binary_heap::*;
526    use serde_json;
527
528    #[test]
529    fn deserialized_same_small_vec() {
530        let heap = BinaryHeap::from(vec![1, 2, 3]);
531        let serialized = serde_json::to_string(&heap).unwrap();
532        let deserialized: BinaryHeap<i32> = serde_json::from_str(&serialized).unwrap();
533
534        let v0: Vec<_> = heap.into_iter().collect();
535        let v1: Vec<_> = deserialized.into_iter().collect();
536        assert_eq!(v0, v1);
537    }
538    #[test]
539    fn deserialized_same() {
540        let vec: Vec<i32> = (0..1000).collect();
541        let heap = BinaryHeap::from(vec);
542        let serialized = serde_json::to_string(&heap).unwrap();
543        let deserialized: BinaryHeap<i32> = serde_json::from_str(&serialized).unwrap();
544
545        let v0: Vec<_> = heap.into_iter().collect();
546        let v1: Vec<_> = deserialized.into_iter().collect();
547        assert_eq!(v0, v1);
548    }
549}
binary_heap_plus/lib.rs

binary_heap_plus/
lib.rs
