sbral 0.1.0

use std::iter;
use std::slice;

use crate::constants::*;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Subtree<T> {
    values: FullChunk<T>,
    // Does this make sense as an Option?  All of the child nodes at a given level will be the
    // same.  In fact, we know what they'll be all the way back at the root.
    children: Option<Ref<ChildNodes<T>>>,
}

impl<T> Subtree<T> {
    pub fn new_leaf(values: FullChunk<T>) -> Self {
        Subtree {
            values,
            children: None,
        }
    }
    fn get_child_position(&self, i: usize, child_tree_size: usize) -> (&Self, usize) {
        let children = self
            .children
            .as_ref()
            .unwrap_or_else(|| panic!("tried to get children of leaf!"));
        // Linear search is faster for FANOUT < 10 or so
        // Division by big-match-statement-of-constant-divisions is ~30% faster than integer divison
        // which is faster than linear search for FANOUT = 32.
        // Binary search doesn't hold up to linear at the low end or division at the high end.  It
        // might have a lead in the middle?
        // It would be nice to do the entire lookup as a switch statement with fallthrough, since
        // we descend down the tree and tree sizes in a fixed order.
        let (idx, remainder) = get_idx(i, child_tree_size);
        (&children[FANOUT - idx - 1], remainder)
    }
    fn get_child_position_mut(&mut self, i: usize, child_tree_size: usize) -> (&mut Self, usize) {
        let children = self
            .children
            .as_mut()
            .unwrap_or_else(|| panic!("tried to get children of leaf!"));
        let (idx, remainder) = get_idx(i, child_tree_size);
        (&mut Ref::make_mut(children)[FANOUT - idx - 1], remainder)
    }
    fn lookup_static(mut subtree: &Self, mut i: usize, mut tree_size: usize) -> &T {
        loop {
            if i < NODE_SIZE {
                // lookup from the end, because the values we get from FirstSkewList also do that
                break &subtree.values[NODE_SIZE - 1 - i];
            } else {
                i -= NODE_SIZE;
                tree_size = (tree_size - NODE_SIZE) / FANOUT;
                let (new_subtree, new_i) = subtree.get_child_position(i, tree_size);
                subtree = new_subtree;
                i = new_i;
            }
        }
    }
    pub fn get(&self, i: usize, tree_size: usize) -> &T {
        Self::lookup_static(self, i, tree_size)
    }
    pub fn upgrade(children: ChildNodes<T>, new_root: FullChunk<T>) -> Self {
        Subtree {
            values: new_root,
            children: Some(Ref::new(children)),
        }
    }
    pub fn downgrade(self) -> (Option<Ref<ChildNodes<T>>>, FullChunk<T>) {
        (self.children, self.values)
    }
    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(self)
    }
}
impl<T> Subtree<T>
where
    T: Clone,
{
    fn get_mut_static(mut subtree: &mut Self, mut i: usize, mut tree_size: usize) -> &mut T {
        loop {
            if i < NODE_SIZE {
                break &mut subtree.values[NODE_SIZE - 1 - i];
            } else {
                i -= NODE_SIZE;
                tree_size = (tree_size - NODE_SIZE) / FANOUT;
                let (new_subtree, new_i) = subtree.get_child_position_mut(i, tree_size);
                subtree = new_subtree;
                i = new_i;
            }
        }
    }
    pub fn get_mut(&mut self, i: usize, tree_size: usize) -> &mut T {
        Self::get_mut_static(self, i, tree_size)
    }
}

impl<T> Clone for Subtree<T> {
    fn clone(&self) -> Self {
        Subtree {
            values: self.values.clone(),
            children: self.children.clone(),
        }
    }
}

pub struct Iter<'a, T> {
    items: iter::Rev<slice::Iter<'a, T>>,
    children: Vec<iter::Rev<std::slice::Iter<'a, Subtree<T>>>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some(next_item) = self.items.next() {
                return Some(next_item);
            }
            if self.children.is_empty() {
                return None;
            }
            // infallible: we just checked and it's not empty
            let next_child = self.children.last_mut().unwrap().next();
            if let Some(next_child) = next_child {
                self.add_child(next_child);
            } else {
                self.children.pop();
            }
        }
    }
}
impl<'a, T> Iter<'a, T> {
    fn add_child(&mut self, child: &'a Subtree<T>) {
        self.items = child.values.iter().rev();
        if let Some(ref grandchildren) = child.children {
            self.children.push(grandchildren.iter().rev());
        }
    }
    fn new(subtree: &'a Subtree<T>) -> Self {
        let mut tmp = Self::default();
        tmp.add_child(subtree);
        tmp
    }
}
impl<'a, T> Default for Iter<'a, T> {
    fn default() -> Self {
        Iter {
            items: [].iter().rev(),
            children: Vec::new(),
        }
    }
}