1pub mod heap;
2
3pub use heap::{BoundedBinaryHeap, BoundedBinaryHeaper, heapify, verify_heap};
4
5#[cfg(test)]
6mod tests {
7 use heap::{BoundedBinaryHeap, BoundedBinaryHeaper, heapify, verify_heap};
8 #[test]
9 fn test_empty_heap() {
10 let h: BoundedBinaryHeap<i32> = BoundedBinaryHeap::new(3);
11 assert_eq!(h.capacity(), 3);
12 assert_eq!(h.len(), 0);
13 assert!(h.is_empty());
14 }
15
16 #[test]
17 fn test_heap() {
18 let mut h = BoundedBinaryHeap::new(3);
19 h.push(10);
20 h.push(9);
21 h.push(8);
22 h.push(7);
23 h.push(6);
24 h.push(5);
25 assert_eq!(h.len(), 3);
26 assert_eq!(h.capacity(), 3);
27 assert_eq!(*h.peek().unwrap(), 8);
28 assert_eq!(h.pop().unwrap(), 8);
29 assert_eq!(h.pop().unwrap(), 9);
30 assert_eq!(h.pop().unwrap(), 10);
31 assert_eq!(h.pop(), None);
32 assert!(h.is_empty());
33 }
34
35 #[test]
36 fn test_heap_heapify() {
37 let mut h = BoundedBinaryHeap::from(&[7,9,8]);
38 assert_eq!(h.capacity(), 3);
39 assert_eq!(h.len(), 3);
40 assert!(!h.is_empty());
41 h.push(10);
42 h.push(6);
43 h.push(5);
44 assert_eq!(h.len(), 3);
45 assert_eq!(h.capacity(), 3);
46 assert_eq!(*h.peek().unwrap(), 8);
47 assert_eq!(h.pop().unwrap(), 8);
48 assert_eq!(h.pop().unwrap(), 9);
49 assert_eq!(h.pop().unwrap(), 10);
50 assert_eq!(h.pop(), None);
51 assert!(h.is_empty());
52 }
53
54 #[test]
55 fn test_heap_heapify_with_capacity() {
56 let mut h = BoundedBinaryHeap::from_slice_with_capacity(&[7,9,8], 5);
57 assert_eq!(h.capacity(), 5);
58 assert_eq!(h.len(), 3);
59 assert!(!h.is_empty());
60 h.push(6);
61 h.push(5);
62 h.push(10);
63 assert_eq!(h.len(), 5);
64 assert_eq!(h.capacity(), 5);
65 assert_eq!(*h.peek().unwrap(), 6);
66 assert_eq!(h.pop().unwrap(), 6);
67 assert_eq!(h.pop().unwrap(), 7);
68 assert_eq!(h.pop().unwrap(), 8);
69 assert_eq!(h.pop().unwrap(), 9);
70 assert_eq!(h.pop().unwrap(), 10);
71 assert_eq!(h.pop(), None);
72 assert!(h.is_empty());
73 }
74
75 #[test]
76 fn test_heaper() {
77 let mut v=[10, 9, 8];
78 let mut h = BoundedBinaryHeaper::from(&mut v);
79 h.push(7);
80 h.push(6);
81 h.push(5);
82 assert_eq!(h.len(), 3);
83 assert_eq!(h.capacity(), 3);
84 assert_eq!(*h.peek().unwrap(), 8);
85 assert_eq!(*h.pop().unwrap(), 8);
86 assert_eq!(*h.pop().unwrap(), 9);
87 assert_eq!(*h.pop().unwrap(), 10);
88 assert_eq!(h.pop(), None);
89 assert!(h.is_empty());
90 }
91
92 #[test]
93 fn test_heapify() {
94 let mut v=[10, 12, 9, 8, 7, 6, 5, 11, 3];
95 heapify(&mut v);
96 assert_eq!(v[0], 3);
97 assert!(verify_heap(&v));
98 }
99
100}