binary_heap_plus2/
lib.rs

1//! This is a fork of [binary-heap-plus](https://github.com/sekineh/binary-heap-plus-rs),
2//! add a new generic constructor `BinaryHeap::from_vec_cmp_rebuild()`.
3//!
4//! `binary-heap-plus` is recommended if there are no special requirements.
5//!
6//! This crate provides `BinaryHeap` which is backward-compatible with `std::collections::BinaryHeap`.
7//!
8//! Added features include:
9//! * Heaps other than max heap.
10//! * Optional `serde` feature.
11//!
12//! # Quick start
13//!
14//! ## Max/Min Heap
15//!
16//! For max heap, `BiaryHeap::from_vec()` is the most versatile way to create a heap.
17//!
18//! ```rust
19//!     use binary_heap_plus2::*;
20//!
21//!     // max heap
22//!     let mut h: BinaryHeap<i32> = BinaryHeap::from_vec(vec![]);
23//!     // max heap with initial capacity
24//!     let mut h: BinaryHeap<i32> = BinaryHeap::from_vec(Vec::with_capacity(16));
25//!     // max heap from iterator
26//!     let mut h: BinaryHeap<i32> = BinaryHeap::from_vec((0..42).collect());
27//!     assert_eq!(h.pop(), Some(41));
28//! ```
29//!
30//! Min heap is similar, but requires type annotation.
31//!
32//! ```rust
33//!     use binary_heap_plus2::*;
34//!
35//!     // min heap
36//!     let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(vec![]);
37//!     // min heap with initial capacity
38//!     let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(Vec::with_capacity(16));
39//!     // min heap from iterator
40//!     let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec((0..42).collect());
41//!     assert_eq!(h.pop(), Some(0));
42//! ```
43//!
44//! ## Custom Heap
45//!
46//! For custom heap, `BinaryHeap::from_vec_cmp()` works in a similar way to max/min heap. The only difference is that you add the comparator closure with apropriate signature.
47//!
48//! ```rust
49//!     use binary_heap_plus2::*;
50//!
51//!     // custom heap: ordered by second value (_.1) of the tuples; min first
52//!     let mut h = BinaryHeap::from_vec_cmp(
53//!         vec![(1, 5), (3, 2), (2, 3)],
54//!         |a: &(i32, i32), b: &(i32, i32)| b.1.cmp(&a.1), // comparator closure here
55//!     );
56//!     assert_eq!(h.pop(), Some((3, 2)));
57//! ```
58//!
59//! # Constructers
60//!
61//! ## Generic methods to create different kind of heaps from initial `vec` data.
62//!
63//! * `BinaryHeap::from_vec(vec)`
64//! * `BinaryHeap::from_vec_cmp(vec, cmp)`
65//!
66//! ```
67//! use binary_heap_plus2::*;
68//!
69//! // max heap (default)
70//! let mut heap: BinaryHeap<i32> = BinaryHeap::from_vec(vec![1,5,3]);
71//! assert_eq!(heap.pop(), Some(5));
72//!
73//! // min heap
74//! let mut heap: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(vec![1,5,3]);
75//! assert_eq!(heap.pop(), Some(1));
76//!
77//! // custom-sort heap
78//! let mut heap = BinaryHeap::from_vec_cmp(vec![1,5,3], |a: &i32, b: &i32| b.cmp(a));
79//! assert_eq!(heap.pop(), Some(1));
80//!
81//! // custom-key heap
82//! let mut heap = BinaryHeap::from_vec_cmp(vec![6,3,1], KeyComparator(|k: &i32| k % 4));
83//! assert_eq!(heap.pop(), Some(3));
84//!
85//! // TIP: How to reuse a comparator
86//! let mod4_comparator = KeyComparator(|k: &_| k % 4);
87//! let mut heap1 = BinaryHeap::from_vec_cmp(vec![6,3,1], mod4_comparator);
88//! assert_eq!(heap1.pop(), Some(3));
89//! let mut heap2 = BinaryHeap::from_vec_cmp(vec![2,4,1], mod4_comparator);
90//! assert_eq!(heap2.pop(), Some(2));
91//! ```
92//!
93//! ## Dedicated methods to create different kind of heaps
94//!
95//! * `BinaryHeap::new()` creates a max heap.
96//! * `BinaryHeap::new_min()` creates a min heap.
97//! * `BinaryHeap::new_by()` creates a heap sorted by the given closure.
98//! * `BinaryHeap::new_by_key()` creates a heap sorted by the key generated by the given closure.
99//!
100
101mod binary_heap;
102pub use crate::binary_heap::*;
103
104/// An intermediate trait for specialization of `Extend`.
105// #[doc(hidden)]
106// trait SpecExtend<I: IntoIterator> {
107//     /// Extends `self` with the contents of the given iterator.
108//     fn spec_extend(&mut self, iter: I);
109// }
110
111#[cfg(test)]
112mod from_liballoc {
113    // The following tests copyed from liballoc/tests/binary_heap.rs
114
115    use super::binary_heap::*;
116    // use std::panic;
117    // use std::collections::BinaryHeap;
118    // use std::collections::binary_heap::{Drain, PeekMut};
119
120    #[test]
121    fn test_iterator() {
122        let data = vec![5, 9, 3];
123        let iterout = [9, 5, 3];
124        let heap = BinaryHeap::from(data);
125        let mut i = 0;
126        for el in &heap {
127            assert_eq!(*el, iterout[i]);
128            i += 1;
129        }
130    }
131
132    #[test]
133    fn test_iterator_reverse() {
134        let data = vec![5, 9, 3];
135        let iterout = vec![3, 5, 9];
136        let pq = BinaryHeap::from(data);
137
138        let v: Vec<_> = pq.iter().rev().cloned().collect();
139        assert_eq!(v, iterout);
140    }
141
142    #[test]
143    fn test_move_iter() {
144        let data = vec![5, 9, 3];
145        let iterout = vec![9, 5, 3];
146        let pq = BinaryHeap::from(data);
147
148        let v: Vec<_> = pq.into_iter().collect();
149        assert_eq!(v, iterout);
150    }
151
152    #[test]
153    fn test_move_iter_size_hint() {
154        let data = vec![5, 9];
155        let pq = BinaryHeap::from(data);
156
157        let mut it = pq.into_iter();
158
159        assert_eq!(it.size_hint(), (2, Some(2)));
160        assert_eq!(it.next(), Some(9));
161
162        assert_eq!(it.size_hint(), (1, Some(1)));
163        assert_eq!(it.next(), Some(5));
164
165        assert_eq!(it.size_hint(), (0, Some(0)));
166        assert_eq!(it.next(), None);
167    }
168
169    #[test]
170    fn test_move_iter_reverse() {
171        let data = vec![5, 9, 3];
172        let iterout = vec![3, 5, 9];
173        let pq = BinaryHeap::from(data);
174
175        let v: Vec<_> = pq.into_iter().rev().collect();
176        assert_eq!(v, iterout);
177    }
178
179    #[test]
180    fn test_into_iter_sorted_collect() {
181        let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
182        let it = heap.into_iter_sorted();
183        let sorted = it.collect::<Vec<_>>();
184        assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
185    }
186
187    #[test]
188    fn test_peek_and_pop() {
189        let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
190        let mut sorted = data.clone();
191        sorted.sort();
192        let mut heap = BinaryHeap::from(data);
193        while !heap.is_empty() {
194            assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
195            assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
196        }
197    }
198
199    #[test]
200    fn test_peek_mut() {
201        let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
202        let mut heap = BinaryHeap::from(data);
203        assert_eq!(heap.peek(), Some(&10));
204        {
205            let mut top = heap.peek_mut().unwrap();
206            *top -= 2;
207        }
208        assert_eq!(heap.peek(), Some(&9));
209    }
210
211    #[test]
212    fn test_peek_mut_pop() {
213        let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
214        let mut heap = BinaryHeap::from(data);
215        assert_eq!(heap.peek(), Some(&10));
216        {
217            let mut top = heap.peek_mut().unwrap();
218            *top -= 2;
219            assert_eq!(PeekMut::pop(top), 8);
220        }
221        assert_eq!(heap.peek(), Some(&9));
222    }
223
224    #[test]
225    fn test_push() {
226        let mut heap = BinaryHeap::from(vec![2, 4, 9]);
227        assert_eq!(heap.len(), 3);
228        assert!(*heap.peek().unwrap() == 9);
229        heap.push(11);
230        assert_eq!(heap.len(), 4);
231        assert!(*heap.peek().unwrap() == 11);
232        heap.push(5);
233        assert_eq!(heap.len(), 5);
234        assert!(*heap.peek().unwrap() == 11);
235        heap.push(27);
236        assert_eq!(heap.len(), 6);
237        assert!(*heap.peek().unwrap() == 27);
238        heap.push(3);
239        assert_eq!(heap.len(), 7);
240        assert!(*heap.peek().unwrap() == 27);
241        heap.push(103);
242        assert_eq!(heap.len(), 8);
243        assert!(*heap.peek().unwrap() == 103);
244    }
245
246    // #[test]
247    // fn test_push_unique() {
248    //     let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
249    //     assert_eq!(heap.len(), 3);
250    //     assert!(**heap.peek().unwrap() == 9);
251    //     heap.push(box 11);
252    //     assert_eq!(heap.len(), 4);
253    //     assert!(**heap.peek().unwrap() == 11);
254    //     heap.push(box 5);
255    //     assert_eq!(heap.len(), 5);
256    //     assert!(**heap.peek().unwrap() == 11);
257    //     heap.push(box 27);
258    //     assert_eq!(heap.len(), 6);
259    //     assert!(**heap.peek().unwrap() == 27);
260    //     heap.push(box 3);
261    //     assert_eq!(heap.len(), 7);
262    //     assert!(**heap.peek().unwrap() == 27);
263    //     heap.push(box 103);
264    //     assert_eq!(heap.len(), 8);
265    //     assert!(**heap.peek().unwrap() == 103);
266    // }
267
268    fn check_to_vec(mut data: Vec<i32>) {
269        let heap = BinaryHeap::from(data.clone());
270        let mut v = heap.clone().into_vec();
271        v.sort();
272        data.sort();
273
274        assert_eq!(v, data);
275        assert_eq!(heap.into_sorted_vec(), data);
276    }
277
278    #[test]
279    fn test_to_vec() {
280        check_to_vec(vec![]);
281        check_to_vec(vec![5]);
282        check_to_vec(vec![3, 2]);
283        check_to_vec(vec![2, 3]);
284        check_to_vec(vec![5, 1, 2]);
285        check_to_vec(vec![1, 100, 2, 3]);
286        check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
287        check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
288        check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
289        check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
290        check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
291        check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
292        check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
293    }
294
295    #[test]
296    fn test_empty_pop() {
297        let mut heap = BinaryHeap::<i32>::new();
298        assert!(heap.pop().is_none());
299    }
300
301    #[test]
302    fn test_empty_peek() {
303        let empty = BinaryHeap::<i32>::new();
304        assert!(empty.peek().is_none());
305    }
306
307    #[test]
308    fn test_empty_peek_mut() {
309        let mut empty = BinaryHeap::<i32>::new();
310        assert!(empty.peek_mut().is_none());
311    }
312
313    #[test]
314    fn test_from_iter() {
315        let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
316
317        let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
318
319        for &x in &xs {
320            assert_eq!(q.pop().unwrap(), x);
321        }
322    }
323
324    #[test]
325    fn test_drain() {
326        let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
327
328        assert_eq!(q.drain().take(5).count(), 5);
329
330        assert!(q.is_empty());
331    }
332
333    #[test]
334    fn test_extend_ref() {
335        let mut a = BinaryHeap::new();
336        a.push(1);
337        a.push(2);
338
339        a.extend(&[3, 4, 5]);
340
341        assert_eq!(a.len(), 5);
342        assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
343
344        let mut a = BinaryHeap::new();
345        a.push(1);
346        a.push(2);
347        let mut b = BinaryHeap::new();
348        b.push(3);
349        b.push(4);
350        b.push(5);
351
352        a.extend(&b);
353
354        assert_eq!(a.len(), 5);
355        assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
356    }
357
358    #[test]
359    fn test_append() {
360        let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
361        let mut b = BinaryHeap::from(vec![-20, 5, 43]);
362
363        a.append(&mut b);
364
365        assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
366        assert!(b.is_empty());
367    }
368
369    #[test]
370    fn test_append_to_empty() {
371        let mut a = BinaryHeap::new();
372        let mut b = BinaryHeap::from(vec![-20, 5, 43]);
373
374        a.append(&mut b);
375
376        assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
377        assert!(b.is_empty());
378    }
379
380    #[test]
381    fn test_extend_specialization() {
382        let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
383        let b = BinaryHeap::from(vec![-20, 5, 43]);
384
385        a.extend(b);
386
387        assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
388    }
389
390    // #[test]
391    // fn test_placement() {
392    //     let mut a = BinaryHeap::new();
393    //     &mut a <- 2;
394    //     &mut a <- 4;
395    //     &mut a <- 3;
396    //     assert_eq!(a.peek(), Some(&4));
397    //     assert_eq!(a.len(), 3);
398    //     &mut a <- 1;
399    //     assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
400    // }
401
402    // #[test]
403    // fn test_placement_panic() {
404    //     let mut heap = BinaryHeap::from(vec![1, 2, 3]);
405    //     fn mkpanic() -> usize {
406    //         panic!()
407    //     }
408    //     let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| {
409    //         &mut heap <- mkpanic();
410    //     }));
411    //     assert_eq!(heap.len(), 3);
412    // }
413
414    #[allow(dead_code)]
415    fn assert_covariance() {
416        fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
417            d
418        }
419    }
420}
421
422#[cfg(feature = "serde")]
423#[cfg(test)]
424mod tests_serde {
425    use super::binary_heap::*;
426    use serde_json;
427
428    #[test]
429    fn deserialized_same_small_vec() {
430        let heap = BinaryHeap::from(vec![1, 2, 3]);
431        let serialized = serde_json::to_string(&heap).unwrap();
432        let deserialized: BinaryHeap<i32> = serde_json::from_str(&serialized).unwrap();
433
434        let v0: Vec<_> = heap.into_iter().collect();
435        let v1: Vec<_> = deserialized.into_iter().collect();
436        assert_eq!(v0, v1);
437    }
438    #[test]
439    fn deserialized_same() {
440        let vec: Vec<i32> = (0..1000).collect();
441        let heap = BinaryHeap::from(vec);
442        let serialized = serde_json::to_string(&heap).unwrap();
443        let deserialized: BinaryHeap<i32> = serde_json::from_str(&serialized).unwrap();
444
445        let v0: Vec<_> = heap.into_iter().collect();
446        let v1: Vec<_> = deserialized.into_iter().collect();
447        assert_eq!(v0, v1);
448    }
449}
binary_heap_plus2/lib.rs

binary_heap_plus2/
lib.rs
