bump-stack 0.5.0

use bump_stack::Stack;
use pretty_assertions::{assert_eq, assert_ne};

#[test]
fn stack_ctor() {
    let s = Stack::<i32>::new();
    assert_eq!(s.capacity(), 0);
    assert_eq!(s.len(), 0);

    let s = Stack::<i32>::default();
    assert_eq!(s.capacity(), 0);
    assert_eq!(s.len(), 0);

    let s = Stack::<()>::default();
    assert_eq!(s.capacity(), usize::MAX);
    assert_eq!(s.len(), 0);

    let s = Stack::<i32>::with_capacity(10);
    assert!(s.capacity() >= 10);
    assert_eq!(s.len(), 0);

    let s = Stack::<()>::with_capacity(10);
    assert_eq!(s.capacity(), usize::MAX);
    assert_eq!(s.len(), 0);

    let s = Stack::from([Box::new(1), Box::new(2), Box::new(4)]);
    assert!(s.capacity() >= 3);
    assert_eq!(s.len(), 3);

    let s = Stack::from(&[1, 2, 4]);
    assert!(s.capacity() >= 3);
    assert_eq!(s.len(), 3);

    let s = Stack::from(&mut [1, 2, 4]);
    assert!(s.capacity() >= 3);
    assert_eq!(s.len(), 3);

    let s = Stack::from([1, 2, 4].as_slice());
    assert!(s.capacity() >= 3);
    assert_eq!(s.len(), 3);

    let s = Stack::from([1, 2, 4].as_mut_slice());
    assert!(s.capacity() >= 3);
    assert_eq!(s.len(), 3);
}

#[test]
fn stack_push_pop() {
    let mut stack = Stack::default();
    const MAX: usize = 1 << 10;
    for i in 0..MAX {
        assert_eq!(stack.len(), i);
        stack.push(i);
    }
    for i in (0..MAX).rev() {
        assert_eq!(stack.pop(), Some(i));
    }
    assert_eq!(stack.len(), 0);
    assert!(stack.len() < stack.capacity());

    let stack = Stack::default();
    stack.push(42);

    let mut stack = Stack::<u8>::default();
    assert_eq!(stack.pop(), None);
}

#[test]
fn stack_push_mut() {
    let mut stk = Stack::from([1, 2]);
    let last = stk.push_mut(3);
    assert_eq!(*last, 3);
    assert_eq!(stk, [3, 2, 1]);

    let last = stk.push_mut(3);
    *last += 1;
    assert_eq!(stk, [4, 3, 2, 1]);
}

#[test]
fn stack_push_mut_zst() {
    let mut stk = Stack::from([(), ()]);
    let last = stk.push_mut(());
    assert_eq!(*last, ());
    *last = ();
    assert_eq!(stk, [(), (), ()]);
}

#[test]
fn stack_push_pop_zst() {
    let mut stack = Stack::default();
    const MAX: usize = 1 << 10;
    for i in 0..MAX {
        assert_eq!(stack.len(), i);
        stack.push(());
    }
    for i in (0..MAX).rev() {
        assert_eq!(stack.len(), i + 1);
        assert_eq!(stack.pop(), Some(()));
    }
    assert_eq!(stack.len(), 0);
    assert!(stack.len() < stack.capacity());

    let stack = Stack::default();
    stack.push(());
}

#[test]
fn stack_push_pop_if() {
    let mut stk = Stack::from([1, 2, 3, 4]);
    let pred = |x: &mut i32| *x % 2 == 0;

    assert_eq!(stk.pop_if(pred), Some(4));
    assert_eq!(stk, [3, 2, 1]);
    assert_eq!(stk.pop_if(pred), None);
}

#[test]
fn stack_first() {
    let mut stack = Stack::default();
    assert_eq!(stack.first(), None);
    stack.push(42);
    assert_eq!(stack.first(), Some(&42));
    stack.push(24);
    assert_eq!(stack.first(), Some(&42));
    stack.pop();
    assert_eq!(stack.first(), Some(&42));
    stack.pop();
    assert_eq!(stack.first(), None);
    stack.pop();
    assert_eq!(stack.first(), None);
}

#[test]
fn stack_first_zst() {
    let mut stack = Stack::<()>::default();
    assert_eq!(stack.first(), None);
    stack.push(());
    assert_eq!(stack.first(), Some(&()));
    stack.push(());
    assert_eq!(stack.first(), Some(&()));
    stack.pop();
    assert_eq!(stack.first(), Some(&()));
    stack.pop();
    assert_eq!(stack.first(), None);
    stack.pop();
    assert_eq!(stack.first(), None);
}

#[test]
fn stack_first_mut() {
    let mut stack = Stack::default();
    assert_eq!(stack.first_mut(), None);
    stack.push(42);
    assert_eq!(stack.first_mut(), Some(&mut 42));
    if let Some(first) = stack.first_mut() {
        assert_eq!(first, &mut 42);
        *first = 24;
    }
    assert_eq!(stack.first_mut(), Some(&mut 24));
}

#[test]
fn stack_last() {
    let mut stack = Stack::default();
    assert_eq!(stack.last(), None);

    stack.push(0);
    let capacity = stack.capacity();

    for i in 1..capacity + 1 {
        stack.push(i);
        assert_eq!(stack.last(), Some(&i));
    }

    for i in (0..capacity + 1).rev() {
        assert_eq!(stack.last(), Some(&i));
        stack.pop();
    }
    assert_eq!(stack.last(), None);
}

#[test]
fn stack_last_zst() {
    let mut stack = Stack::<()>::default();
    assert_eq!(stack.last(), None);
    stack.push(());
    assert_eq!(stack.last(), Some(&()));
    stack.pop();
    assert_eq!(stack.last(), None);
}

#[test]
fn stack_last_mut() {
    let mut stk = Stack::new();
    assert_eq!(None, stk.last_mut());

    stk.push(5);
    assert_eq!(Some(&mut 5), stk.last_mut());

    if let Some(last) = stk.last_mut() {
        *last = 10;
    }
    assert_eq!(Some(&mut 10), stk.last_mut());

    stk.pop();
    assert_eq!(None, stk.last_mut());

    let mut capacity = stk.capacity();
    for mut i in 0..capacity + 1 {
        stk.push(i);
        assert_eq!(stk.last_mut(), Some(&mut i));
    }
    assert_eq!(stk.last_mut(), Some(&mut capacity));
    stk.pop();
    assert_eq!(stk.last_mut(), Some(&mut (capacity - 1)));
}

#[test]
fn stack_contains() {
    let mut stk = Stack::new();
    assert!(!stk.contains(&5));

    stk.push(5);
    assert!(stk.contains(&5));

    stk.push(10);
    assert!(stk.contains(&5));
    assert!(stk.contains(&10));

    stk.pop();
    assert!(stk.contains(&5));
    assert!(!stk.contains(&10));

    stk.pop();
    assert!(!stk.contains(&5));
    assert!(!stk.contains(&10));
}

#[test]
fn stack_from_iter() {
    let stk = Stack::from_iter([10, 40, 30]);
    assert_eq!(stk, [30, 40, 10]);
}

#[test]
fn stack_to_vec() {
    let stk = Stack::from([10, 40, 30]);

    let mut vec = stk.to_vec();
    assert_eq!(vec, [30, 40, 10]);
    vec[0] = 20;
    assert_eq!(vec, [20, 40, 10]);
    assert_eq!(stk, [30, 40, 10]);
}

#[test]
fn stack_debug_fmt() {
    let mut stack = Stack::from(&[1, 2, 3]);
    assert_eq!(format!("{:?}", stack), "[3, 2, 1]");

    stack.push(4);
    assert_eq!(format!("{:?}", stack), "[4, 3, 2, 1]");

    stack.push(5);
    assert_eq!(format!("{:?}", stack), "[5, 4, 3, 2, 1]");

    stack.pop();
    assert_eq!(format!("{:?}", stack), "[4, 3, 2, 1]");

    stack.pop();
    assert_eq!(format!("{:?}", stack), "[3, 2, 1]");
}

#[test]
fn stack_iter() {
    let stk = Stack::new();
    stk.push(0);
    let capacity_1 = stk.capacity();
    for i in 1..capacity_1 {
        stk.push(i);
    }
    assert_eq!(stk.len(), capacity_1);

    let len = stk.len();
    for (i, elem) in stk.iter().enumerate() {
        assert_eq!(*elem, len - i - 1);
    }

    for (i, elem) in stk.iter().rev().enumerate() {
        assert_eq!(*elem, i);
    }

    stk.push(capacity_1);
    let capacity_12 = stk.capacity();
    for i in capacity_1 + 1..capacity_12 {
        stk.push(i);
    }
    assert_eq!(stk.len(), capacity_12);

    let len = stk.len();
    for (i, elem) in stk.iter().enumerate() {
        assert_eq!(*elem, len - i - 1);
    }

    for (i, elem) in stk.iter().rev().enumerate() {
        assert_eq!(*elem, i);
    }

    let mut iter = stk.iter();
    for _ in 0..capacity_12 - capacity_1 {
        iter.next();
    }
    for _ in 0..capacity_1 {
        iter.next_back();
    }
    assert_eq!(iter.next_back(), None);

    // double the stack
    let len_before = stk.len();
    for elem in &stk {
        stk.push(*elem);
    }
    let len_after = stk.len();
    assert_eq!(2 * len_before, len_after);

    let mut iter = stk.iter();
    while let Some(l_elem) = iter.next()
        && let Some(r_elem) = iter.next_back()
    {
        assert_eq!(l_elem, r_elem);
    }
    assert_eq!(iter.next(), None);
    assert_eq!(iter.next_back(), None);
}

#[test]
fn stack_iter_zst() {
    let stk = Stack::from([(), (), (), ()]);
    let count = stk.iter().fold(0, |count, _| count + 1);
    assert_eq!(stk.len(), count);

    let stk = Stack::from([(), (), (), ()]);
    let count = stk.iter().rev().fold(0, |count, _| count + 1);
    assert_eq!(stk.len(), count);

    let stk = Stack::from([(), (), (), ()]);
    let mut iter = stk.iter();
    assert_eq!((4, Some(4)), iter.size_hint());
    iter.next_back();
    assert_eq!((3, Some(3)), iter.size_hint());
    iter.next();
    assert_eq!((2, Some(2)), iter.size_hint());
    iter.next_back();
    assert_eq!((1, Some(1)), iter.size_hint());
    iter.next();
    assert_eq!((0, Some(0)), iter.size_hint());
    iter.next_back();
    assert_eq!((0, Some(0)), iter.size_hint());
}

#[test]
fn stack_iter_mut() {
    let mut stk = Stack::new();
    stk.push(0);
    let capacity_1 = stk.capacity();
    for i in 1..capacity_1 {
        stk.push(i);
    }
    assert_eq!(stk.len(), capacity_1);

    let len = stk.len();
    for (i, elem) in stk.iter_mut().enumerate() {
        assert_eq!(*elem, len - i - 1);
    }

    for (i, elem) in stk.iter_mut().rev().enumerate() {
        assert_eq!(*elem, i);
    }

    stk.push(capacity_1);
    let capacity_12 = stk.capacity();
    for i in capacity_1 + 1..capacity_12 {
        stk.push(i);
    }
    assert_eq!(stk.len(), capacity_12);

    let len = stk.len();
    for (i, elem) in stk.iter_mut().enumerate() {
        assert_eq!(*elem, len - i - 1);
    }

    for (i, elem) in stk.iter_mut().rev().enumerate() {
        assert_eq!(*elem, i);
    }

    let mut iter = stk.iter_mut();
    for _ in 0..capacity_12 - capacity_1 {
        iter.next();
    }
    for _ in 0..capacity_1 {
        iter.next_back();
    }
    assert_eq!(iter.next_back(), None);
    drop(iter);

    // double the stack
    let len_before = stk.len();
    for elem in &stk {
        stk.push(*elem);
    }
    let len_after = stk.len();
    assert_eq!(2 * len_before, len_after);

    let mut iter = stk.iter_mut();
    while let Some(l_elem) = iter.next()
        && let Some(r_elem) = iter.next_back()
    {
        assert_eq!(l_elem, r_elem);
    }
    assert_eq!(iter.next(), None);
    assert_eq!(iter.next_back(), None);

    let mut stk = Stack::from([1, 2, 3]);
    for elem in &mut stk {
        *elem *= 2;
    }
    assert_eq!(stk, [6, 4, 2]);
}

#[test]
fn stack_iter_mut_zst() {
    let mut stk = Stack::from([(), (), (), ()]);
    let count = stk.iter().fold(0, |count, _| count + 1);
    assert_eq!(stk.len(), count);

    #[allow(clippy::manual_slice_fill)]
    for elem in &mut stk {
        *elem = ();
    }
    assert_eq!(stk.iter_mut().count(), 4);
}

#[test]
fn stack_into_iter() {
    let stk = Stack::from([Box::new(1), Box::new(2), Box::new(3)]);
    let new_stk = Stack::new();
    for elem in stk {
        new_stk.push(elem);
    }
    for elem in new_stk {
        if *elem == 2 {
            break;
        }
    }
    let stk = Stack::from([(), (), (), ()]);
    assert_eq!(stk.into_iter().count(), 4);
}

#[test]
fn stack_iter_count() {
    let stk = Stack::from([1, 2, 4, 7]);
    for i in 0..stk.capacity() {
        stk.push(i);
    }
    assert_eq!(stk.len(), stk.iter().count());

    let stk = Stack::new();
    stk.push(());
    stk.push(());
    stk.push(());
    stk.push(());
    assert_eq!(4, stk.iter().count());
}

#[test]
fn stack_iter_size_hint() {
    let stk = Stack::from([1, 2, 4, 7]);
    assert_eq!((0, None), stk.iter().size_hint());

    let stk = Stack::from([(), (), (), ()]);
    assert_eq!((4, Some(4)), stk.iter().size_hint());
}

#[test]
#[allow(clippy::iter_nth_zero)]
fn stack_iter_nth_zst() {
    let stk = Stack::new();
    stk.push(());
    stk.push(());
    stk.push(());
    stk.push(());
    let mut iter = stk.iter();
    assert_eq!(iter.nth(1), Some(&()));
    assert_eq!(iter.nth(1), Some(&()));
    assert_eq!(iter.nth(0), None);
}

#[test]
#[allow(clippy::iter_nth_zero)]
fn stack_iter_nth() {
    let mut stk = Stack::new();
    stk.push(0);
    let capacity = stk.capacity();
    for i in 1..capacity {
        stk.push(i);
    }

    {
        let mut iter = stk.iter();
        assert_eq!(iter.nth(1), Some(&(capacity - 2)));
        assert_eq!(iter.nth(1), Some(&(capacity - 4)));
        assert_eq!(iter.nth(capacity), None);

        let mut iter = stk.iter();
        assert_eq!(iter.nth(capacity - 1), Some(&0));

        let mut iter = stk.iter();
        assert_eq!(iter.nth(capacity), None);

        stk.push(capacity);
        assert!(stk.capacity() > capacity);

        let mut iter = stk.iter();
        assert_eq!(iter.nth(1), Some(&(capacity - 1)));
        assert_eq!(iter.nth(1), Some(&(capacity - 3)));
        assert_eq!(iter.nth(capacity), None);

        let mut iter = stk.iter();
        assert_eq!(iter.nth(capacity), Some(&0));
        assert_eq!(iter.nth(0), None);

        let mut iter = stk.iter();
        assert_eq!(iter.nth(0), Some(&capacity));
        assert_eq!(iter.nth(0), Some(&(capacity - 1)));
    }

    stk.pop();
    assert_eq!(stk.len(), capacity);
    assert_ne!(stk.capacity(), capacity);

    let mut iter = stk.iter();
    assert_eq!(iter.nth(1), Some(&(capacity - 2)));
    assert_eq!(iter.nth(1), Some(&(capacity - 4)));
    assert_eq!(iter.nth(capacity - 4), None);
}

#[test]
fn stack_iter_last() {
    let stk = Stack::from(&[3, 2, 1]);
    assert_eq!(stk.iter().last(), Some(&3));

    let stk = Stack::from(&[(), (), ()]);
    assert_eq!(stk.iter().last(), Some(&()));

    let stk = Stack::<u8>::from(&[]);
    assert_eq!(stk.iter().last(), None);

    let stk = Stack::<()>::from(&[]);
    assert_eq!(stk.iter().last(), None);
}

#[test]
fn stack_slices() {
    let mut stk = Stack::new();
    let slices = stk.chunks().collect::<Vec<_>>();
    assert_eq!(slices.len(), 0);

    stk.push(0);
    let capacity_1 = stk.capacity();
    for i in 1..capacity_1 {
        stk.push(i);
    }
    assert_eq!(stk.len(), capacity_1);

    let slice = stk.chunks().next().unwrap();
    assert_eq!(slice.len(), capacity_1);

    let slice = stk.chunks().next_back().unwrap();
    assert_eq!(slice.len(), capacity_1);

    let slices = stk.chunks().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);

    for slice in stk.chunks() {
        stk.push(slice[0] + 1);
    }

    let slices = stk.chunks().collect::<Vec<_>>();
    assert_eq!(slices.len(), 2);
    assert_eq!(slices[0][0], capacity_1 - 1);
    assert_eq!(slices[1], [capacity_1]);

    let slices = stk.chunks().rev().collect::<Vec<_>>();
    assert_eq!(slices.len(), 2);
    assert_eq!(slices[0], [capacity_1]);
    assert_eq!(slices[1][0], capacity_1 - 1);

    stk.pop();

    let slices = stk.chunks().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 1);

    let slices = stk.chunks().rev().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 1);

    stk.pop();

    let slices = stk.chunks().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 2);

    let slices = stk.chunks().rev().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 2);
}

#[test]
fn stack_slices_zst() {
    let stk = Stack::new();

    let slices = stk.chunks().collect::<Vec<_>>();
    assert_eq!(slices.len(), 0);

    for _ in 0..1000 {
        stk.push(());
    }
    let slices = stk.chunks().collect::<Vec<_>>();
    assert_eq!(slices[0], [(); 1000]);

    let slices = stk.chunks().rev().collect::<Vec<_>>();
    assert_eq!(slices[0], [(); 1000]);
}

#[test]
fn stack_slices_mut() {
    let mut stk = Stack::from([0, 1, 2]);

    let slice = stk.chunks_mut().next().unwrap();
    assert_eq!(slice, [2, 1, 0]);
    slice[0] = 42;
    assert_eq!(slice, [42, 1, 0]);

    let mut stk = Stack::new();
    let slices = stk.chunks_mut().collect::<Vec<_>>();
    assert_eq!(slices.len(), 0);

    stk.push(0);
    let capacity_1 = stk.capacity();
    for i in 1..capacity_1 {
        stk.push(i);
    }
    assert_eq!(stk.len(), capacity_1);

    let slice = stk.chunks_mut().next().unwrap();
    assert_eq!(slice.len(), capacity_1);

    let slice = stk.chunks_mut().next_back().unwrap();
    assert_eq!(slice.len(), capacity_1);

    let slices = stk.chunks_mut().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);

    stk.push(capacity_1);

    let slices = stk.chunks_mut().collect::<Vec<_>>();
    assert_eq!(slices.len(), 2);
    assert_eq!(slices[0][0], capacity_1 - 1);
    assert_eq!(slices[1], [capacity_1]);

    let slices = stk.chunks_mut().rev().collect::<Vec<_>>();
    assert_eq!(slices.len(), 2);
    assert_eq!(slices[0], [capacity_1]);
    assert_eq!(slices[1][0], capacity_1 - 1);

    stk.pop();

    let slices = stk.chunks_mut().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 1);

    let slices = stk.chunks_mut().rev().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 1);

    stk.pop();

    let slices = stk.chunks_mut().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 2);

    let slices = stk.chunks_mut().rev().collect::<Vec<_>>();
    assert_eq!(slices.len(), 1);
    assert_eq!(slices[0][0], capacity_1 - 2);
}

#[test]
fn stack_partial_eq() {
    let stk = Stack::from(&[3, 2, 1]);
    assert_eq!(stk, [1, 2, 3]);
    assert_eq!(stk, &[1, 2, 3]);
    assert_eq!(stk, &mut [1, 2, 3]);
    assert_eq!([1, 2, 3], stk);
    assert_eq!(&[1, 2, 3], stk);
    assert_eq!(&mut [1, 2, 3], stk);

    assert_eq!(stk, [1, 2, 3].as_slice());
    assert_eq!(stk, [1, 2, 3].as_mut_slice());

    assert_ne!(stk, [1, 2, 5]);
    assert_ne!(stk, &[1, 2, 5]);
    assert_ne!(stk, &mut [1, 2, 5]);
    assert_ne!([1, 2, 5], stk);
    assert_ne!(&[1, 2, 5], stk);
    assert_ne!(&mut [1, 2, 5], stk);

    assert_ne!(stk, [1, 2, 3, 4]);
    assert_ne!(stk, &[1, 2, 3, 4]);
    assert_ne!(stk, &mut [1, 2, 3, 4]);
    assert_ne!([1, 2, 3, 4], stk);
    assert_ne!(&[1, 2, 3, 4], stk);
    assert_ne!(&mut [1, 2, 3, 4], stk);
}