//! `flat-tree` helps you represent a binary tree in a simple flat list.
//!
//! The tree will be saved using the following structure
//!
//!```c
//!      3
//!  1       5
//!0   2   4   6  ...
//!```

#[derive(Debug)]
pub enum TreeError {
    NonZeroDepth,
    ChildNotExists
}

/// return a vector contains all the full roots whos index < i
pub fn full_roots(i: usize) -> Result<Vec<usize>, TreeError> {
    let mut result = vec![];
    if is_odd(i) {
        return Err(TreeError::NonZeroDepth)
    }

    let mut initial = i / 2;
    let mut offset = 0;
    let mut factor = 1;

    loop {
        if initial == 0 { return Ok(result) }

        while factor * 2 <= initial { factor *= 2 }
        result.push(offset + factor - 1);
        offset = offset + 2 * factor;
        initial -= factor;
        factor = 1;
    }
}

/// returns the depth of an element
pub fn depth(index: usize) -> usize {
    let mut depth = 0;
    let mut i = index + 1;

    while is_even(i) {
        depth+=1;
        i = right_shift(i);
    }

    return depth
}

/// returns the index of the element's sibling
pub fn sibling(i: usize) -> usize {
    let offset = offset(i);
    let depth = depth(i);

    if is_odd(offset) {
        return index(depth, offset - 1)
    } else {
        return index(depth, offset + 1)
    }
}

/// returns the index of the parent of the element
pub fn parent(i: usize) -> usize {
    let offset = offset(i);

    let depth = depth(i);
    index(depth + 1, right_shift(offset))
}

/// returns the index of the left child of the element
pub fn left_child(i: usize) -> Result<usize, TreeError> {
    if is_even(i) { return Err(TreeError::ChildNotExists) }

    let depth = depth(i);
    Ok(index(depth-1, offset(i) * 2))
}

/// returns the index of the right child of the element
pub fn right_child(i: usize) -> Result<usize, TreeError> {
    if is_even(i) { return Err(TreeError::ChildNotExists) }

    let depth = depth(i);
    Ok(index(depth-1, 1 + offset(i) * 2))
}

/// returns [left_child, right_child] of the element
pub fn children(i: usize) -> Result<Vec<usize>, TreeError> {
    if is_even(i) { return Err(TreeError::ChildNotExists) }

    let offset = offset(i) * 2;
    let depth = depth(i);

    return Ok(vec![
              index(depth-1, offset),
              index(depth-1, offset+1)
    ])
}

pub fn left_span(i: usize) -> usize {
    if is_even(i) { return i }

    let depth = depth(i);

    offset(i) * two_pow(depth + 1)
}

pub fn right_span(i: usize) -> usize {
    if is_even(i) { return i }

    let depth = depth(i);

    (offset(i) + 1) * two_pow(depth + 1) - 2
}

pub fn count(i: usize) -> usize {
    if is_even(i) { return 1 }
    let depth = depth(i);

    two_pow(depth + 1) - 1
}

pub fn spans(i: usize) -> Vec<usize> {
    if is_even(i) { return vec![i, i] }

    let depth = depth(i);
    let offset = offset(i);
    let width = two_pow(depth + 1);

    vec![offset * width, (offset+1) * width - 2]
}

pub fn offset(index: usize) -> usize {
    if is_even(index) { return index / 2 }
    let depth = depth(index);

    ((index+1) / two_pow(depth) - 1) / 2
}


pub fn index(depth: usize, offset: usize) -> usize {
    (1 + 2 * offset) * two_pow(depth) - 1
}

fn is_odd(n: usize) -> bool {
    (n & 1) == 1
}

fn is_even(n: usize) -> bool {
    (n & 1) == 0
}

fn right_shift(n: usize) -> usize {
    (n - (n & 1)) / 2
}

fn two_pow(n: usize) -> usize {
    if n < 31 {
        1 << n
    } else {
        ((1 << 30) * (1 << n - 30))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_child_to_parent_to_child() {
        let mut child = 0;
        let mut i = 0;
        while i < 50 {
            child = parent(child);
            i+=1;
        }
        assert_eq!(child, 1125899906842623);
        i = 0;
        while i < 50 {
            child = left_child(child).unwrap();
            i+=1;
        }
        assert_eq!(child, 0);
    }

    #[test]
    fn test_offset() {
        assert_eq!(offset(0), 0);
        assert_eq!(offset(1), 0);
        assert_eq!(offset(2), 1);
        assert_eq!(offset(3), 0);
        assert_eq!(offset(4), 2);
    }

    #[test]
    fn test_span() {
        assert_eq!(spans(0), vec![0,0]);
        assert_eq!(spans(1), vec![0,2]);
        assert_eq!(spans(3), vec![0,6]);
        assert_eq!(spans(23), vec![16,30]);
        assert_eq!(spans(27), vec![24,30]);
    }

    #[test]
    fn test_full_roots() {
        assert_eq!(full_roots(0).unwrap(), vec![]);
        assert_eq!(full_roots(2).unwrap(), vec![0]);
        assert_eq!(full_roots(8).unwrap(), vec![3]);
        assert_eq!(full_roots(20).unwrap(), vec![7, 17]);
        assert_eq!(full_roots(18).unwrap(), vec![7, 16]);
        assert_eq!(full_roots(16).unwrap(), vec![7]);
    }

    #[test]
    fn test_depth() {
        assert_eq!(depth(0), 0);
        assert_eq!(depth(1), 1);
        assert_eq!(depth(2), 0);
        assert_eq!(depth(3), 2);
        assert_eq!(depth(4), 0);
    }

    #[test]
    fn test_sibling() {
        assert_eq!(sibling(0), 2);
        assert_eq!(sibling(2), 0);
        assert_eq!(sibling(1), 5);
        assert_eq!(sibling(5), 1);
    }

    #[test]
    fn test_parent() {
        assert_eq!(index(1, 0), 1);
        assert_eq!(index(1, 1), 5);
        assert_eq!(index(2, 0), 3);
        assert_eq!(parent(0), 1);
        assert_eq!(parent(2), 1);
        assert_eq!(parent(1), 3);
    }

    #[test]
    fn test_left_child() {
        assert!(left_child(0).is_err());
        assert_eq!(left_child(1).unwrap(), 0);
        assert_eq!(left_child(3).unwrap(), 1);
    }

    #[test]
    fn test_children() {
        assert!(children(0).is_err());
        assert_eq!(children(1).unwrap(), [0, 2]);
        assert_eq!(children(3).unwrap(), [1, 5]);
    }

    #[test]
    fn test_right_child() {
        assert!(right_child(0).is_err());
        assert_eq!(right_child(1).unwrap(), 2);
        assert_eq!(right_child(3).unwrap(), 5);
    }
    #[test]
    fn test_left_span() {
        assert_eq!(left_span(0), 0);
        assert_eq!(left_span(1), 0);
        assert_eq!(left_span(3), 0);
        assert_eq!(left_span(23), 16);
        assert_eq!(left_span(27), 24);
    }

    #[test]
    fn test_right_span() {
        assert_eq!(right_span(0), 0);
        assert_eq!(right_span(1), 2);
        assert_eq!(right_span(3), 6);
        assert_eq!(right_span(23), 30);
        assert_eq!(right_span(27), 30);
    }

    #[test]
    fn test_count() {
        assert_eq!(count(0), 1);
        assert_eq!(count(1), 3);
        assert_eq!(count(3), 7);
        assert_eq!(count(5), 3);
        assert_eq!(count(23), 15);
        assert_eq!(count(27), 7);
    }

    #[test]
    fn test_on_vector() {
        let mut tree = vec![0,1,2];
        *(tree.get_mut(parent(2)).unwrap()) = 4;

        assert_eq!(tree.get(parent(2)).unwrap(), &4)
    }
}