sbral 0.1.0

use std::iter;
use std::iter::FromIterator;
use std::mem;
use std::ops::{Index, IndexMut};
use std::slice;

use crate::constants::*;
use crate::inner_skew_list::{self, InnerSkewList};

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SkewList<T> {
    buffer: Chunk<T>,
    tail: Ref<InnerSkewList<T>>,
}

impl<T> SkewList<T> {
    /// Create an empty SkewList.
    pub fn new() -> Self {
        SkewList {
            buffer: Chunk::new(),
            tail: Ref::new(InnerSkewList::default()),
        }
    }

    /// Retrieve an element by index.  This takes O(log index): accessing elements near the front
    /// of the list is faster than ones toward the back, but never slower than O(log N).
    pub fn get(&self, mut i: usize) -> Option<&T> {
        if i < self.buffer.len() {
            let pos = self.buffer.len() - 1 - i;
            Some(&self.buffer[pos])
        } else {
            i -= self.buffer.len();
            self.tail.get(i)
        }
    }

    /// Return an iterator over the elements of the list.
    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(self)
    }

    /// Get the length of the list.  This is O(log N) - if you need to refer to it often, track it
    /// outside of the list!
    pub fn get_len(&self) -> usize {
        self.buffer.len() + self.tail.get_len()
    }

    /// Returns whether the list contains any elements.  This is O(1), but if you store the length
    /// externally you should compare that to 0 instead.
    pub fn is_empty(&self) -> bool {
        // todo: In the future, pop() could leave empty digits behind.  The len() test should catch
        // it when it causes a regression here, but I don't feel completely confident that it will.
        self.buffer.is_empty() && self.tail.values.is_empty()
    }
}

impl<T> SkewList<T>
where
    T: Clone,
{
    fn replace_buffer(&mut self, value: T) -> Chunk<T> {
        let mut new_buffer = Chunk::new();
        new_buffer.push(value);
        mem::replace(&mut self.buffer, new_buffer)
    }

    #[cold]
    fn push_full(&mut self, value: T) {
        let values = self.replace_buffer(value);
        InnerSkewList::add_one(&mut self.tail, values.upgrade());
    }

    /// Prepend a new element to the front of the list.  This is O(1).
    pub fn push(&mut self, value: T) {
        if self.buffer.len() < NODE_SIZE {
            self.buffer.push(value);
        } else {
            // If we don't split this off into a cold function, push_full and everything it calls
            // wil be inlined into push(), since they're not called anywhere else.  Since we expect
            // it to be called only 1 in every NODE_SIZE times, it's much better to instead give
            // push() the best shot at being inlined into its caller.
            self.push_full(value)
        }
    }

    /// Get a mutable reference to an element, cloning as necessary.  This takes O(log index).
    pub fn get_mut(&mut self, mut i: usize) -> Option<&mut T> {
        if i < self.buffer.len() {
            let pos = self.buffer.len() - 1 - i;
            Some(&mut self.buffer[pos])
        } else {
            i -= self.buffer.len();
            Ref::make_mut(&mut self.tail).get_mut(i)
        }
    }

    /// Pop an element from the front of the list.  This is O(1).
    pub fn pop(&mut self) -> Option<T> {
        if let Some(popped) = self.buffer.pop() {
            return Some(popped);
        }
        if let Some(buffer_rc) = InnerSkewList::subtract_one(&mut self.tail) {
            self.buffer = buffer_rc.downgrade();
            self.buffer.pop()
        } else {
            None
        }
    }
}

impl<T> Default for SkewList<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> FromIterator<T> for SkewList<T>
where
    T: Clone,
{
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut self_ = Self::default();
        self_.extend(iter);
        self_
    }
}

impl<T> IntoIterator for SkewList<T>
where
    T: Clone,
{
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}

impl<T> Index<usize> for SkewList<T> {
    type Output = T;
    fn index(&self, index: usize) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl<T> IndexMut<usize> for SkewList<T>
where
    T: Clone,
{
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}

impl<T> Extend<T> for SkewList<T>
where
    T: Clone,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T>,
    {
        // I'm not sure if there are any reasonable ways to improve on this.  Appending is already
        // O(1) - that's the point - and most of the work is things we would need to do anyway.
        // We could keep around zero digits and remove them when we're done, instead of dropping
        // and recreating them.  Not dropping them wouldn't add a lot of complexity to
        // inner_skew_list::upgrade(), but we'd have to manually maintain canonical skew form.
        for item in iter {
            self.push(item);
        }
    }
}

pub enum Iter<'a, T> {
    InBuffer(iter::Rev<slice::Iter<'a, T>>, &'a SkewList<T>),
    InSkewList(inner_skew_list::Iter<'a, T>),
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let replacement;
            match *self {
                Iter::InBuffer(ref mut buffer_iter, ref first_skew_list) => {
                    if let Some(next) = buffer_iter.next() {
                        return Some(next);
                    }
                    replacement = Iter::InSkewList(first_skew_list.tail.iter());
                }
                Iter::InSkewList(ref mut list_iter) => {
                    return list_iter.next();
                }
            }
            *self = replacement;
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        // todo: do we want to store our length? It's expensive to calculate, and difficult after
        // we enter the skew list, but is that worth worrying about?  Getting it accurately once is
        // enough to optimize e.g. Vec::from_iter().
        match *self {
            Iter::InBuffer(ref buf, ref tail) => {
                let len = buf.len() + tail.get_len();
                (len, Some(len))
            }
            Iter::InSkewList(ref iter) => iter.size_hint(),
        }
    }
}

pub struct IntoIter<T>(SkewList<T>);

impl<T> Iterator for IntoIter<T>
where
    T: Clone,
{
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.0.get_len();
        (len, Some(len))
    }
}

impl<'a, T> Iter<'a, T> {
    fn new(list: &'a SkewList<T>) -> Self {
        Iter::InBuffer(list.buffer.iter().rev(), list)
    }
}

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

    use proptest::prelude::*;

    proptest! {
        #[test]
        fn get(len in 0..1000i32, pos in 0..1000i32) {
            let list: SkewList<i32> = (0..len).rev().collect();
            if pos >= len {
                assert_eq!(list.get(pos as usize), None);
            }
            if len != 0 {
                let inbounds = pos % len;
                assert_eq!(list[inbounds as usize], inbounds);
            }
        }

        #[test]
        fn get_mut(len in 0..1000i32, pos in 0..1000i32) {
            let mut list: SkewList<i32> = (0..len).rev().collect();
            if pos >= len {
                assert_eq!(list.get_mut(pos as usize), None);
            }
            if len != 0 {
                let inbounds = pos % len;
                assert_eq!(list.get_mut(inbounds as usize).cloned(), Some(inbounds));
            }
        }

        #[test]
        fn iterate(len in 0..1000i32) {
            let list: SkewList<i32> = (0..len).rev().collect();
            assert!(list.iter().cloned().eq(0..len));
        }

        #[test]
        fn push(len in 0..1000i32) {
            let mut list: SkewList<i32> = (1..(len + 1)).rev().collect();
            list.push(0);
            let mut expected: VecDeque<i32> = (1..(len + 1)).collect();
            expected.push_front(0);
            assert!(list.iter().eq(expected.iter()));
        }

        #[test]
        fn pop(len in 0..1000i32) {
            let list: SkewList<i32> = (0..len).rev().collect();
            let collected: Vec<_> = list.into_iter().collect();
            let expected: Vec<_> = (0..len).collect();
            assert_eq!(collected, expected);
        }

        #[test]
        fn len(len in 0..1000i32, pop in 0..1000i32) {
            let mut list: SkewList<i32> = (0..len).rev().collect();
            let list_len = list.get_len();
            assert_eq!(list_len, len as usize, "initial len");
            assert_eq!(list.is_empty(), len == 0, "initial is_empty");
            for _ in 0..pop {
                list.pop();
            }
            let new_len = (len - pop).max(0);
            assert_eq!(list.get_len(), new_len as usize, "len after pop");
            assert_eq!(list.is_empty(), new_len == 0, "is_empty after pop");
        }
    }

    // Make sure we haven't accidentally introduced any non-thread-safe types
    #[test]
    #[cfg(feature = "threadsafe")]
    fn threadsafe() {
        it_works::<SkewList<()>>();
        fn it_works<T: Sync>() {}
    }

    #[test]
    fn get_idx_covers_all_usize() {
        use crate::constants::{get_idx, TREE_SIZE_MAX};
        let tree_sizes: Vec<_> = iter::successors(Some(NODE_SIZE), |&size| {
            size.checked_mul(FANOUT)?.checked_add(NODE_SIZE)
        })
        .collect();
        assert_eq!(*tree_sizes.last().unwrap(), TREE_SIZE_MAX);
        for tree_size in tree_sizes {
            assert_eq!(get_idx(tree_size * 2 + 1, tree_size), (2, 1));
        }
    }
}