algo-rs 0.1.0

use crate::data_structure::heap::{Heap, HeapFn};

pub struct BinaryHeap<T> {
    cmp: HeapFn<T>,
    inner: Vec<T>,
}

impl<T> BinaryHeap<T> {
    pub fn new(cmp: HeapFn<T>) -> Self {
        Self {
            cmp,
            inner: Vec::<T>::new(),
        }
    }

    pub fn with_capacity(cmp: HeapFn<T>, size: usize) -> Self {
        Self {
            cmp,
            inner: Vec::<T>::with_capacity(size),
        }
    }

    fn sift_down(&mut self) {
        let size = self.inner.len();
        let mut current = 0usize;
        let mut running = true;

        while running {
            let left = current * 2 + 1;
            let right = current * 2 + 2;
            running = false;
            if right < size && (self.cmp)(&self.inner[left], &self.inner[right]) {
                if (self.cmp)(&self.inner[current], &self.inner[right]) {
                    self.inner.swap(current, right);
                    current = right;
                    running = true;
                }
            } else if left < size {
                if (self.cmp)(&self.inner[current], &self.inner[left]) {
                    self.inner.swap(current, left);
                    current = left;
                    running = true;
                }
            }
        }
    }

    fn sift_up(&mut self) {
        let mut current = self.inner.len() - 1;

        while current > 0 {
            let parent = (current - 1) / 2;
            if (self.cmp)(&self.inner[parent], &self.inner[current]) {
                self.inner.swap(parent, current);
            } else {
                break;
            }

            current = parent;
        }
    }
}

impl<T> Heap<T> for BinaryHeap<T> {
    fn push(&mut self, item: T) {
        self.inner.push(item);
        self.sift_up();
    }

    fn pop(&mut self) -> Option<T> {
        if self.inner.is_empty() {
            return None;
        }

        let last = self.inner.len() - 1;
        self.inner.swap(0, last);
        let result = self.inner.pop();
        self.sift_down();
        result
    }

    fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    fn peek(&self) -> Option<&T> {
        return self.inner.first();
    }
}

#[cfg(test)]
mod tests {
    use crate::data_structure::heap::binary_heap::BinaryHeap;
    use crate::data_structure::heap::min_binary_heap::MinBinaryHeap;
    use crate::data_structure::heap::Heap;
    use std::collections;
    extern crate test;
    use test::Bencher;

    #[test]
    fn test_push_pop() {
        let mut heap = BinaryHeap::new(|left, right| -> bool { left > right });
        heap.push(3);
        heap.push(2);
        heap.push(1);
        assert_eq!(Some(1), heap.pop());
        assert_eq!(Some(2), heap.pop());
        assert_eq!(Some(3), heap.pop());
        assert_eq!(None, heap.pop());
    }

    #[test]
    fn test_is_empty() {
        let mut heap = BinaryHeap::new(|left, right| -> bool { left < right });
        assert_eq!(true, heap.is_empty());
        heap.push(3);
        assert_eq!(false, heap.is_empty());
        heap.pop();
        assert_eq!(true, heap.is_empty());
    }

    #[test]
    fn test_peek() {
        let mut heap = BinaryHeap::new(|left, right| -> bool { left < right });
        assert_eq!(None, heap.peek());
        heap.push(3);
        assert_eq!(Some(&3), heap.peek());
        heap.pop();
        assert_eq!(None, heap.peek());
    }

    #[bench]
    fn bench_binary_heap_push_pop(b: &mut Bencher) {
        b.iter(|| {
            let mut heap = BinaryHeap::with_capacity(|left, right| -> bool { left < right }, 10000);
            for i in 1..10000 {
                heap.push(i)
            }

            for _ in 1..10000 {
                heap.pop();
            }
        });
    }

    #[bench]
    fn bench_min_binary_heap_push_pop(b: &mut Bencher) {
        b.iter(|| {
            let mut heap = MinBinaryHeap::with_capacity(10000);
            for i in 1..10000 {
                heap.push(i)
            }

            for _ in 1..10000 {
                heap.pop();
            }
        });
    }

    #[bench]
    fn bench_std_binary_heap_push_pop(b: &mut Bencher) {
        b.iter(|| {
            let mut heap = collections::BinaryHeap::with_capacity(10000);
            for i in 1..10000 {
                heap.push(i)
            }

            for _ in 1..10000 {
                heap.pop();
            }
        });
    }
}