container 0.1.0

const HEAP_CONTAINER_MAX_SIZE: usize = 2147483647;

pub trait HeapContainer {
    type T: PartialEq + PartialOrd;
    
    fn size(&self) -> usize;
    fn less(&self, i: usize, j: usize) -> bool;
    fn swap(&mut self, usize, usize);
    fn push_back(&mut self, _: Self::T);
    fn pop_back(&mut self) -> Option<Self::T>;
}

pub struct Heap<C: HeapContainer> {
    data: C,
}

impl<C: HeapContainer> Heap<C> {
    pub fn new(c: C) -> Heap<C> {
        Heap {
            data: c,
        }
    }
    
    pub fn size(&self) -> usize {
        self.data.size()
    }
    
    pub fn push(&mut self, t: C::T) {
        let n = self.size();
        self.data.push_back(t);
        self._up(n);
    }
    
    pub fn pop(&mut self) -> Option<C::T> {
        let len = self.size();
        if len == 0 {
            return None;
        }
        let n = len - 1;
        self.data.swap(0, n);
        self._down(0, n);
        self.data.pop_back()
    }
    
    pub fn remove(&mut self, i: usize) -> Option<C::T> {
        let n = self.size() - 1;
        if n != i {
            self.data.swap(i, n);
            self._down(i, n);
            self._up(i);
        }
        self.data.pop_back()
    }
    
    pub fn fix(&mut self, i: usize) {
        let len = self.size();
        self._down(i, len);
        self._up(i);
    }
    
    fn _up(&mut self, i: usize) {
        let mut i = i;
        while i > 0 {
            let j = (i-1)/2;
            if i == j || !self.data.less(i, j) {
                break
            }
            self.data.swap(i, j);
            i = j;
        }
    }
    
    fn _down(&mut self, i: usize, n: usize) {
        let mut i = i;
        loop {
            let j1 = 2*i+1;
            if j1 >=n || j1 > HEAP_CONTAINER_MAX_SIZE {
                break;
            }
            let mut j = j1;
            let j2 = j1+1;
            if j2 < n && !self.data.less(j1, j2) {
                j = j2;
            }
            if !self.data.less(j, i) {
                break;
            }
            self.data.swap(i, j);
            i = j;
        }
    }
}