sakurai 0.1.1

use core::mem::MaybeUninit;
use core::ptr;

pub type Pivot<T, const N: usize> = PivotBuffer<T, N>;

#[derive(Clone)]
pub struct PivotBuffer<T, const N: usize>
where
    T: Clone + Copy,
{
    data: [MaybeUninit<T>; N],
    pivot: usize,
    left_count: usize,
    right_count: usize,
}

impl<T, const N: usize> PivotBuffer<T, N>
where
    T: Clone + Copy,
{
    pub const fn new() -> Self {
        assert!(N > 0, "PivotBuffer size must be greater than 0");

        Self {
            data: unsafe { MaybeUninit::uninit().assume_init() },
            pivot: N / 2,
            left_count: 0,
            right_count: 0,
        }
    }

    #[inline]
    pub const fn capacity(&self) -> usize {
        N
    }

    #[inline]
    pub const fn len(&self) -> usize {
        self.left_count + self.right_count
    }

    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.left_count == 0 && self.right_count == 0
    }

    #[inline]
    pub const fn is_full(&self) -> bool {
        self.len() == N
    }

    #[inline]
    pub const fn pivot_index(&self) -> usize {
        self.pivot
    }

    #[inline]
    pub const fn left_count(&self) -> usize {
        self.left_count
    }

    #[inline]
    pub const fn right_count(&self) -> usize {
        self.right_count
    }

    pub fn push_left(&mut self, item: T) -> Result<(), PivotBufferError> {
        if self.is_full() {
            return Err(PivotBufferError::Full);
        }

        let left_pos = if self.pivot > self.left_count {
            self.pivot - 1 - self.left_count
        } else {
            if self.right_count + self.left_count >= N {
                return Err(PivotBufferError::Full);
            }
            self.shift_right();
            self.pivot - 1 - self.left_count
        };
        unsafe {
            ptr::write(self.data[left_pos].as_mut_ptr(), item);
        }
        self.left_count += 1;
        Ok(())
    }

    pub fn push_right(&mut self, item: T) -> Result<(), PivotBufferError> {
        if self.is_full() {
            return Err(PivotBufferError::Full);
        }

        let right_pos = self.pivot + 1 + self.right_count;
        if right_pos >= N {
            if self.left_count + self.right_count >= N {
                return Err(PivotBufferError::Full);
            }
            self.shift_left();
        }

        let right_pos = self.pivot + 1 + self.right_count;
        unsafe {
            ptr::write(self.data[right_pos].as_mut_ptr(), item);
        }
        self.right_count += 1;
        Ok(())
    }

    pub fn pop_left(&mut self) -> Result<T, PivotBufferError> {
        if self.left_count == 0 {
            return Err(PivotBufferError::EmptyLeft);
        }

        if self.pivot < self.left_count {
            return Err(PivotBufferError::EmptyLeft);
        }

        let left_pos = self.pivot - self.left_count;
        let item = unsafe { ptr::read(self.data[left_pos].as_ptr()) };
        self.left_count -= 1;
        Ok(item)
    }

    pub fn pop_right(&mut self) -> Result<T, PivotBufferError> {
        if self.right_count == 0 {
            return Err(PivotBufferError::EmptyRight);
        }

        let right_pos = self.pivot + self.right_count;
        if right_pos >= N {
            return Err(PivotBufferError::EmptyRight);
        }

        let item = unsafe { ptr::read(self.data[right_pos].as_ptr()) };
        self.right_count -= 1;
        Ok(item)
    }

    pub fn peek_left(&self) -> Option<&T> {
        if self.left_count == 0 || self.pivot < self.left_count {
            None
        } else {
            let left_pos = self.pivot - self.left_count;
            Some(unsafe { &*self.data[left_pos].as_ptr() })
        }
    }

    pub fn peek_right(&self) -> Option<&T> {
        if self.right_count == 0 {
            None
        } else {
            let right_pos = self.pivot + self.right_count;
            if right_pos >= N {
                None
            } else {
                Some(unsafe { &*self.data[right_pos].as_ptr() })
            }
        }
    }

    pub fn clear(&mut self) {
        while self.pop_left().is_ok() {}
        while self.pop_right().is_ok() {}
    }

    pub fn get(&self, offset: isize) -> Option<&T> {
        if offset < 0 {
            let left_idx = (-offset) as usize;
            if left_idx <= self.left_count && left_idx > 0 {
                let pos = self.pivot - left_idx;
                Some(unsafe { &*self.data[pos].as_ptr() })
            } else {
                None
            }
        } else if offset > 0 {
            let right_idx = offset as usize;
            if right_idx <= self.right_count {
                let pos = self.pivot + right_idx;
                Some(unsafe { &*self.data[pos].as_ptr() })
            } else {
                None
            }
        } else {
            None
        }
    }

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

    fn shift_right(&mut self) {
        if self.pivot >= N - 1 {
            return;
        }

        for i in 0..self.left_count {
            let from_pos = self.pivot - 1 - i;
            let to_pos = self.pivot - i;
            unsafe {
                let item = ptr::read(self.data[from_pos].as_ptr());
                ptr::write(self.data[to_pos].as_mut_ptr(), item);
            }
        }

        for i in 0..self.right_count {
            let from_pos = self.pivot + 1 + i;
            let to_pos = self.pivot + 2 + i;
            unsafe {
                let item = ptr::read(self.data[from_pos].as_ptr());
                ptr::write(self.data[to_pos].as_mut_ptr(), item);
            }
        }

        self.pivot += 1;
    }

    fn shift_left(&mut self) {
        if self.pivot == 0 {
            return;
        }

        for i in 0..self.left_count {
            let from_pos = self.pivot - 1 - i;
            if self.pivot >= 2 + i {
                let to_pos = self.pivot - 2 - i;
                unsafe {
                    let item = ptr::read(self.data[from_pos].as_ptr());
                    ptr::write(self.data[to_pos].as_mut_ptr(), item);
                }
            }
        }

        for i in 0..self.right_count {
            let from_pos = self.pivot + 1 + i;
            let to_pos = self.pivot + i;
            unsafe {
                let item = ptr::read(self.data[from_pos].as_ptr());
                ptr::write(self.data[to_pos].as_mut_ptr(), item);
            }
        }

        self.pivot -= 1;
    }
}

impl<T, const N: usize> Default for PivotBuffer<T, N>
where
    T: Clone + Copy,
{
    fn default() -> Self {
        Self::new()
    }
}

impl<T, const N: usize> Drop for PivotBuffer<T, N>
where
    T: Clone + Copy,
{
    fn drop(&mut self) {
        self.clear();
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PivotBufferError {
    Full,
    EmptyLeft,
    EmptyRight,
}

pub struct PivotBufferIter<'a, T, const N: usize>
where
    T: Clone + Copy,
{
    buffer: &'a PivotBuffer<T, N>,
    current_offset: isize,
}

impl<'a, T, const N: usize> PivotBufferIter<'a, T, N>
where
    T: Clone + Copy,
{
    fn new(buffer: &'a PivotBuffer<T, N>) -> Self {
        // start from leftmost element
        let start_offset = if buffer.left_count > 0 {
            -(buffer.left_count as isize)
        } else if buffer.right_count > 0 {
            1
        } else {
            0
        };

        Self {
            buffer,
            current_offset: start_offset,
        }
    }
}

impl<'a, T, const N: usize> Iterator for PivotBufferIter<'a, T, N>
where
    T: Clone + Copy,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.buffer.is_empty() {
            return None;
        }

        if self.current_offset == 0 {
            self.current_offset = 1;
        }

        if self.current_offset < -(self.buffer.left_count as isize)
            || self.current_offset > self.buffer.right_count as isize
        {
            return None;
        }

        let item = self.buffer.get(self.current_offset);
        self.current_offset += 1;
        if self.current_offset == 0 {
            self.current_offset = 1;
        }

        item
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.buffer.len();
        (remaining, Some(remaining))
    }
}

impl<'a, T, const N: usize> ExactSizeIterator for PivotBufferIter<'a, T, N>
where
    T: Clone + Copy,
{
    fn len(&self) -> usize {
        self.buffer.len()
    }
}

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

    #[test]
    fn test_new_pivot_buffer() {
        let buffer = PivotBuffer::<i32, 8>::new();
        assert_eq!(buffer.capacity(), 8);
        assert_eq!(buffer.len(), 0);
        assert!(buffer.is_empty());
        assert!(!buffer.is_full());
        assert_eq!(buffer.pivot_index(), 4); // N/2 = 8/2 = 4
    }

    #[test]
    fn test_push_left_right() {
        let mut buffer = PivotBuffer::<i32, 8>::new();

        assert!(buffer.push_right(1).is_ok());
        assert!(buffer.push_right(2).is_ok());
        assert_eq!(buffer.right_count(), 2);
        assert_eq!(buffer.len(), 2);

        assert!(buffer.push_left(10).is_ok());
        assert!(buffer.push_left(20).is_ok());
        assert_eq!(buffer.left_count(), 2);
        assert_eq!(buffer.len(), 4);
    }

    #[test]
    fn test_pop_left_right() {
        let mut buffer = PivotBuffer::<i32, 8>::new();

        buffer.push_left(10).unwrap();
        buffer.push_left(20).unwrap();
        buffer.push_right(1).unwrap();
        buffer.push_right(2).unwrap();

        assert_eq!(buffer.pop_left().unwrap(), 20);
        assert_eq!(buffer.pop_left().unwrap(), 10);
        assert_eq!(buffer.left_count(), 0);

        assert_eq!(buffer.pop_right().unwrap(), 2);
        assert_eq!(buffer.pop_right().unwrap(), 1);
        assert_eq!(buffer.right_count(), 0);

        assert!(buffer.is_empty());
    }

    #[test]
    fn test_peek() {
        let mut buffer = PivotBuffer::<i32, 8>::new();

        assert!(buffer.peek_left().is_none());
        assert!(buffer.peek_right().is_none());

        buffer.push_left(10).unwrap();
        buffer.push_right(20).unwrap();

        assert_eq!(buffer.peek_left(), Some(&10));
        assert_eq!(buffer.peek_right(), Some(&20));

        assert_eq!(buffer.len(), 2);
    }

    #[test]
    fn test_get_by_offset() {
        let mut buffer = PivotBuffer::<i32, 8>::new();

        buffer.push_left(10).unwrap(); // offset -1
        buffer.push_left(20).unwrap(); // offset -2
        buffer.push_right(30).unwrap(); // offset 1
        buffer.push_right(40).unwrap(); // offset 2

        assert_eq!(buffer.get(-2), Some(&20));
        assert_eq!(buffer.get(-1), Some(&10));
        assert_eq!(buffer.get(0), None); // pivot position
        assert_eq!(buffer.get(1), Some(&30));
        assert_eq!(buffer.get(2), Some(&40));
        assert_eq!(buffer.get(3), None); // out of bounds
    }

    #[test]
    fn test_full_buffer() {
        let mut buffer = PivotBuffer::<i32, 4>::new();

        assert!(buffer.push_left(1).is_ok());
        assert!(buffer.push_left(2).is_ok());
        assert!(buffer.push_right(3).is_ok());
        assert!(buffer.push_right(4).is_ok());

        assert!(buffer.is_full());
        assert_eq!(buffer.push_left(5), Err(PivotBufferError::Full));
        assert_eq!(buffer.push_right(6), Err(PivotBufferError::Full));
    }

    #[test]
    fn test_empty_buffer() {
        let mut buffer = PivotBuffer::<i32, 4>::new();

        assert_eq!(buffer.pop_left(), Err(PivotBufferError::EmptyLeft));
        assert_eq!(buffer.pop_right(), Err(PivotBufferError::EmptyRight));
    }

    #[test]
    fn test_clear() {
        let mut buffer = PivotBuffer::<i32, 8>::new();

        buffer.push_left(1).unwrap();
        buffer.push_right(2).unwrap();
        assert_eq!(buffer.len(), 2);

        buffer.clear();
        assert_eq!(buffer.len(), 0);
        assert!(buffer.is_empty());
    }

    #[test]
    fn test_shifting_behavior() {
        let mut buffer = PivotBuffer::<i32, 6>::new();

        buffer.push_left(1).unwrap(); // at index 2
        buffer.push_left(2).unwrap(); // at index 1  
        buffer.push_left(3).unwrap(); // at index 0, should trigger shift

        buffer.push_right(10).unwrap(); // at index 4
        buffer.push_right(20).unwrap(); // at index 5

        assert_eq!(buffer.len(), 5);
        assert_eq!(buffer.pop_left().unwrap(), 3);
        assert_eq!(buffer.pop_left().unwrap(), 2);
        assert_eq!(buffer.pop_left().unwrap(), 1);
        assert_eq!(buffer.pop_right().unwrap(), 20);
        assert_eq!(buffer.pop_right().unwrap(), 10);
    }

    #[test]
    fn test_iterator() {
        let mut buffer = PivotBuffer::<i32, 8>::new();

        buffer.push_left(10).unwrap(); // offset -1
        buffer.push_left(20).unwrap(); // offset -2
        buffer.push_right(30).unwrap(); // offset 1
        buffer.push_right(40).unwrap(); // offset 2

        let mut iter = buffer.iter();
        assert_eq!(iter.next(), Some(&20));
        assert_eq!(iter.next(), Some(&10));
        assert_eq!(iter.next(), Some(&30));
        assert_eq!(iter.next(), Some(&40));
        assert_eq!(iter.next(), None);

        let iter = buffer.iter();
        assert_eq!(iter.size_hint(), (4, Some(4)));
        assert_eq!(iter.len(), 4);
    }

    #[test]
    fn test_iterator_empty() {
        let buffer = PivotBuffer::<i32, 8>::new();
        let mut iter = buffer.iter();
        assert_eq!(iter.next(), None);

        let iter = buffer.iter();
        assert_eq!(iter.size_hint(), (0, Some(0)));
        assert_eq!(iter.len(), 0);
    }

    #[test]
    fn test_iterator_single_side() {
        let mut buffer = PivotBuffer::<i32, 8>::new();

        buffer.push_left(1).unwrap();
        buffer.push_left(2).unwrap();

        let mut iter = buffer.iter();
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), None);

        buffer.clear();

        buffer.push_right(10).unwrap();
        buffer.push_right(20).unwrap();

        let mut iter = buffer.iter();
        assert_eq!(iter.next(), Some(&10));
        assert_eq!(iter.next(), Some(&20));
        assert_eq!(iter.next(), None);
    }
}