sbral 0.1.0

use std::mem;

use arrayvec::ArrayVec;

use crate::constants::*;
use crate::subtree::{self, Subtree};

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

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
// An instance of InnerSkewList represents a digit in a skew number; the linked list of them
// provided by Tail represents a digit string.
pub struct InnerSkewList<T> {
    // The last entry is only used for the skew value.  Most of the time it will be unoccupied.
    // At most this will amount to only log(N) wasted entries.
    pub values: ArrayVec<ChildNodes<T>>,
    pub tree_size: usize,
    // size is just tree_size * values.len() so it doesn't have to be stored, but it helps a little
    // bit on lookups (~3%) to not have to calculate it for each digit, and it doesn't appear to
    // affect append time measurably. The memory overhead is 96 bytes at most for 12 digits.
    pub size: usize,
    pub tail: Option<Ref<InnerSkewList<T>>>,
}

impl<T> InnerSkewList<T> {
    pub fn empty() -> Self {
        InnerSkewList {
            values: ArrayVec::new(),
            tree_size: NODE_SIZE,
            size: 0,
            tail: None,
        }
    }

    pub fn new(node: FullChunk<T>) -> Self {
        let mut self_ = InnerSkewList::empty();
        self_.push(Subtree::new_leaf(node));
        self_
    }

    pub fn full(nodes: ChildNodes<T>, tree_size: usize) -> Self {
        InnerSkewList {
            values: ArrayVec::from(nodes),
            tree_size,
            size: tree_size * FANOUT,
            tail: None,
        }
    }

    fn push(&mut self, node: Subtree<T>) {
        self.values.push(node);
        self.size += self.tree_size;
    }

    fn pop(&mut self) -> Option<Subtree<T>> {
        let popped = self.values.pop()?;
        self.size -= self.tree_size;
        Some(popped)
    }

    fn lookup_local(&self, i: usize) -> Result<&T, usize> {
        if i >= self.size {
            Err(i - self.size)
        } else {
            let (idx, new_i) = get_idx(i, self.tree_size);
            Ok(self.values[self.values.len() - 1 - idx].get(new_i, self.tree_size))
        }
    }
    fn lookup_static(mut skew_list: &Self, mut i: usize) -> Option<&T> {
        loop {
            match skew_list.lookup_local(i) {
                Ok(value) => {
                    break Some(value);
                }
                Err(new_i) => {
                    i = new_i;
                    skew_list = match skew_list.tail {
                        Some(ref x) => &**x,
                        None => {
                            break None;
                        }
                    };
                }
            }
        }
    }
    pub fn get(&self, i: usize) -> Option<&T> {
        Self::lookup_static(self, i)
    }
    pub fn add_one(self_: &mut Ref<Self>, tree: FullChunk<T>) {
        if self_.values.len() == FANOUT {
            Self::upgrade(self_, tree);
        } else if self_.tree_size == NODE_SIZE {
            let mut_self = Ref::make_mut(self_);
            mut_self.push(Subtree::new_leaf(tree));
        } else {
            let new_head = Self::new(tree);
            let old_self = mem::replace(self_, Ref::new(new_head));
            // this will never clone, since this is a brand-new Rc
            let mut_head = Ref::make_mut(self_);
            mut_head.tail = Some(old_self);
        }
    }

    pub fn subtract_one(self_: &mut Ref<Self>) -> Option<FullChunk<T>> {
        let mut_self = Ref::make_mut(self_);
        let child = mut_self.pop()?;
        let (children_opt, values) = child.downgrade();
        if let Some(children_rc) = children_opt {
            // our children are branch nodes and need to be added back in
            Self::downgrade(self_, children_rc);
        } else if self_.values.is_empty() {
            // our child was a leaf node and it was our last one, we can disappear
            if let Some(tail) = Ref::make_mut(self_).tail.take() {
                mem::replace(self_, tail);
            }
        }
        Some(values)
    }

    pub fn upgrade(self_: &mut Ref<Self>, new_root: FullChunk<T>) {
        let new_tree_size = increment_tree_size(self_.tree_size);
        let mut_self = Ref::make_mut(self_);

        if mut_self
            .tail
            .as_ref()
            .map(|tail| tail.tree_size == new_tree_size)
            .unwrap_or(false)
        {
            // We carried over to an existing digit, let's get vored by them.
            // I'm not going to tiptoe around it and pretend something else is happening.  You've
            // heard about 7.  You know what numbers get up to.
            // (If you haven't heard about 7, it's a terrible joke: https://duckduckgo.com/?q=why+was+6+afraid+of+7)

            // Point our parent to our tail so we can move out of self.values, and later be
            // dropped
            // infallible: we just confirmed we have a tail
            let tail_rc = mut_self.tail.take().unwrap();
            let old_self_rc = mem::replace(self_, tail_rc);
            let tail = self_;
            // infallible: we called Rc::make_mut() on it at the start of the function
            let old_self = Ref::try_unwrap(old_self_rc).ok().unwrap();
            // this should have been verified before calling upgrade()
            let values = old_self.values.into_inner().ok().unwrap();

            let new_subtree = Subtree::upgrade(values, new_root);
            let mut_tail = Ref::make_mut(tail);
            // infallible: the last element represents the extra skew value.
            // It will only ever be present on the lowest digit (us)
            mut_tail.push(new_subtree);
        } else {
            // Upgrade in place
            let old_array = mem::replace(&mut mut_self.values, ArrayVec::new());
            // infallible: this was verified before calling upgrade()
            let values = old_array.into_inner().ok().unwrap();
            let new_subtree = Subtree::upgrade(values, new_root);
            mut_self.values.push(new_subtree);
            mut_self.tree_size = new_tree_size;
            mut_self.size = new_tree_size;
        }
    }

    pub fn downgrade(self_: &mut Ref<Self>, values: Ref<ChildNodes<T>>) {
        let values = Ref::try_unwrap(values).unwrap_or_else(|rc| (&*rc).clone());
        let new_tree_size = decrement_tree_size(self_.tree_size);
        // this was our last child, downgrade in place
        if self_.values.is_empty() {
            let mut_self = Ref::make_mut(self_);
            mut_self.values = ArrayVec::from(values);
            mut_self.tree_size = decrement_tree_size(mut_self.tree_size);
            mut_self.size = mut_self.tree_size * FANOUT;
        } else {
            // prepend our child
            let mut new_head = InnerSkewList::full(values, new_tree_size);
            // todo: can we do this without make_mut or clone?
            new_head.tail = Some(self_.clone());
            mem::replace(self_, Ref::new(new_head));
        }
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(self)
    }

    fn len_static(mut skew_list: &Self) -> usize {
        let mut len = 0;
        loop {
            len += skew_list.size;
            skew_list = match skew_list.tail {
                Some(ref tail) => &**tail,
                None => {
                    break len;
                }
            };
        }
    }

    pub fn get_len(&self) -> usize {
        Self::len_static(self)
    }
}
impl<T> InnerSkewList<T>
where
    T: Clone,
{
    fn lookup_local_mut(
        values: &mut ArrayVec<ChildNodes<T>>,
        i: usize,
        tree_size: usize,
        size: usize,
    ) -> Result<&mut T, usize> {
        // Just checking the index works ok, but checking if we are even in the right place before
        // starting helps a surprising amount.
        if i >= size {
            Err(i - size)
        } else {
            let (idx, new_i) = get_idx(i, tree_size);
            let real_idx = values.len() - 1 - idx;
            Ok(values[real_idx].get_mut(new_i, tree_size))
        }
    }

    fn get_mut_static(mut skew_list: &mut Self, mut i: usize) -> Option<&mut T> {
        loop {
            match Self::lookup_local_mut(
                &mut skew_list.values,
                i,
                skew_list.tree_size,
                skew_list.size,
            ) {
                Ok(value) => {
                    return Some(value);
                }
                Err(new_i) => {
                    i = new_i;
                    skew_list = match skew_list.tail.as_mut() {
                        Some(x) => Ref::make_mut(x),
                        None => {
                            return None;
                        }
                    };
                }
            };
        }
    }
    pub fn get_mut(&mut self, i: usize) -> Option<&mut T> {
        Self::get_mut_static(self, i)
    }
}

impl<T> Default for InnerSkewList<T> {
    fn default() -> Self {
        Self::empty()
    }
}

impl<T> Clone for InnerSkewList<T> {
    fn clone(&self) -> Self {
        InnerSkewList {
            values: self.values.clone(),
            tree_size: self.tree_size,
            tail: self.tail.clone(),
            size: self.size,
        }
    }
}

pub struct Iter<'a, T> {
    tree_iter: subtree::Iter<'a, T>,
    trees: iter::Rev<slice::Iter<'a, Subtree<T>>>,
    tail: Option<&'a InnerSkewList<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some(item) = self.tree_iter.next() {
                return Some(item);
            }
            loop {
                if let Some(next_tree) = self.trees.next() {
                    self.tree_iter = next_tree.iter();
                    break;
                }
                if let Some(tail) = self.tail {
                    self.trees = tail.values.iter().rev();
                    self.tail = tail.tail.as_ref().map(|x| &**x);
                } else {
                    return None;
                }
            }
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        // it's probably not worth figuring out where we are in the subtree
        if let Some(ref tail) = self.tail {
            let tail_len = tail.get_len();
            (
                tail_len,
                tail_len.checked_add(decrement_tree_size(tail.tree_size)),
            )
        } else {
            (0, None)
        }
    }
}

impl<'a, T> Iter<'a, T> {
    fn new(list: &'a InnerSkewList<T>) -> Self {
        Iter {
            tree_iter: subtree::Iter::default(),
            trees: list.values.iter().rev(),
            tail: list.tail.as_ref().map(|x| &**x),
        }
    }
}
impl<'a, T> Default for Iter<'a, T> {
    fn default() -> Self {
        Iter {
            tree_iter: subtree::Iter::default(),
            trees: [].iter().rev(),
            tail: None,
        }
    }
}