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