algo-rs 0.1.0

use crate::data_structure::heap::Heap;

pub struct MaxBinaryHeap<T: PartialOrd> {
    inner: Vec<T>,
}

impl<T: PartialOrd> MaxBinaryHeap<T> {
    pub fn new() -> Self {
        Self {
            inner: Vec::<T>::new(),
        }
    }

    pub fn with_capacity(size: usize) -> Self {
        Self {
            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.inner[left].lt(&self.inner[right]) {
                if self.inner[current].lt(&self.inner[right]) {
                    self.inner.swap(current, right);
                    current = right;
                    running = true;
                }
            } else if left < size {
                if self.inner[current].lt(&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.inner[parent].lt(&self.inner[current]) {
                self.inner.swap(parent, current);
            } else {
                break;
            }

            current = parent;
        }
    }
}

impl<T: PartialOrd> Heap<T> for MaxBinaryHeap<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::max_binary_heap::MaxBinaryHeap;
    use crate::data_structure::heap::Heap;
    extern crate test;

    #[test]
    fn test_push_pop() {
        let mut heap = MaxBinaryHeap::new();
        heap.push(3);
        heap.push(2);
        heap.push(1);
        assert_eq!(Some(3), heap.pop());
        assert_eq!(Some(2), heap.pop());
        assert_eq!(Some(1), heap.pop());
        assert_eq!(None, heap.pop());
    }

    #[test]
    fn test_is_empty() {
        let mut heap = MaxBinaryHeap::new();
        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 = MaxBinaryHeap::new();
        assert_eq!(None, heap.peek());
        heap.push(3);
        assert_eq!(Some(&3), heap.peek());
        heap.pop();
        assert_eq!(None, heap.peek());
    }
}