use std::default::Default;
use std::slice;
#[derive(Debug, Clone)]
pub struct DStack<I> {
stacks: Vec<I>,
left_head: Option<usize>,
right_head: usize,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum StackVal<I> {
Enter(I),
Exit(I),
}
impl<I: Default> Default for StackVal<I> {
fn default() -> Self {
Self::Enter(I::default())
}
}
impl<I> DStack<I>
where
I: Clone,
{
pub fn with_capacity(n: usize) -> Self
where
I: Default,
{
assert!(n > 1);
Self {
stacks: vec![I::default(); n],
left_head: None,
right_head: n,
}
}
pub fn capacity(&self) -> usize {
self.stacks.len()
}
pub fn is_left_empty(&self) -> bool {
self.left_head.is_none()
}
pub fn is_right_empty(&self) -> bool {
self.right_head == self.capacity()
}
pub fn push_left(&mut self, value: I) {
let head = self.left_head.map_or(0, |x| x + 1);
assert!(head < self.right_head);
self.stacks[head] = value;
self.left_head = Some(head);
}
pub fn push_right(&mut self, value: I) {
self.right_head -= 1;
if let Some(left_head) = self.left_head {
assert!(self.right_head > left_head);
}
self.stacks[self.right_head] = value;
}
pub fn pop_left(&mut self) -> Option<I> {
match self.left_head {
Some(left_head) => {
let res = self.stacks[left_head].clone();
self.left_head = if left_head > 0 {
Some(left_head - 1)
} else {
None
};
Some(res)
}
None => None,
}
}
pub fn pop_right(&mut self) -> Option<I> {
if self.right_head >= self.stacks.len() {
None
} else {
let res = self.stacks[self.right_head].clone();
self.right_head += 1;
Some(res)
}
}
pub fn len_right(&self) -> usize {
let n = self.stacks.len();
n - self.right_head
}
pub fn clear_right(&mut self) {
self.right_head = self.stacks.len();
}
pub fn clear_left(&mut self) {
self.left_head = None;
}
pub fn iter_right(&self) -> slice::Iter<I> {
self.stacks[self.right_head..].iter()
}
pub fn push_left_on_right(&mut self) {
while let Some(val) = self.pop_left() {
self.push_right(val);
}
}
pub fn push_right_on_left(&mut self) {
while let Some(val) = self.pop_right() {
self.push_left(val);
}
}
}
pub fn extract_stack_val<I>(stack_val: &StackVal<I>) -> &I {
match stack_val {
StackVal::Enter(i) | StackVal::Exit(i) => i,
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_stack_val_default() {
let val = StackVal::<usize>::default();
assert_eq!(val, StackVal::<usize>::Enter(0));
}
#[test]
#[should_panic]
fn test_create_stack_with_not_enough_capacity() {
let _stack = DStack::<i32>::with_capacity(1);
}
#[test]
fn test_create_empty_stack() {
const CAPACITY: usize = 10;
let stack = DStack::<i32>::with_capacity(CAPACITY);
assert_eq!(stack.stacks.len(), CAPACITY);
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, CAPACITY);
}
#[test]
fn test_capacity() {
const CAPACITY: usize = 10;
let stack = DStack::<i32>::with_capacity(CAPACITY);
assert_eq!(stack.capacity(), CAPACITY);
}
#[test]
fn test_is_left_empty_with_empty_stack() {
let stack = DStack::<i32>::with_capacity(10);
assert!(stack.is_left_empty());
}
#[test]
fn test_is_left_empty_with_non_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
stack.push_left(3);
assert!(!stack.is_left_empty());
}
#[test]
fn test_is_left_empty_with_right_non_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
stack.push_right(3);
assert!(stack.is_left_empty());
}
#[test]
fn test_is_right_empty_with_empty_stack() {
let stack = DStack::<i32>::with_capacity(10);
assert!(stack.is_right_empty());
}
#[test]
fn test_is_right_empty_with_non_empty_stack() {
let mut stack = DStack::with_capacity(10);
stack.push_right(3);
assert!(!stack.is_right_empty());
}
#[test]
fn test_is_right_empty_with_left_non_empty_stack() {
let mut stack = DStack::with_capacity(10);
stack.push_left(3);
assert!(stack.is_right_empty());
}
#[test]
fn test_push_left_stack() {
let mut stack = DStack::with_capacity(3);
stack.push_left(1);
stack.push_left(2);
stack.push_left(3);
assert_eq!(stack.stacks[0], 1);
assert_eq!(stack.stacks[1], 2);
assert_eq!(stack.stacks[2], 3);
assert_eq!(stack.left_head, Some(2));
assert_eq!(stack.right_head, 3);
}
#[test]
#[should_panic]
fn test_push_left_more_item_that_capacity_stack() {
let mut stack = DStack::with_capacity(2);
stack.push_left(1);
stack.push_left(2);
stack.push_left(3);
}
#[test]
fn test_push_right_stack() {
let mut stack = DStack::with_capacity(3);
stack.push_right(1);
stack.push_right(2);
stack.push_right(3);
assert_eq!(stack.stacks[0], 3);
assert_eq!(stack.stacks[1], 2);
assert_eq!(stack.stacks[2], 1);
assert_eq!(stack.right_head, 0);
assert_eq!(stack.left_head, None);
}
#[test]
#[should_panic]
fn test_push_right_more_item_that_capacity_stack() {
let mut stack = DStack::with_capacity(2);
stack.push_right(1);
stack.push_right(2);
stack.push_right(3);
}
#[test]
fn test_push_left_without_exceeding_right_head_stack() {
let mut stack = DStack::with_capacity(3);
stack.push_left(1);
stack.push_right(3);
stack.push_left(2);
assert_eq!(stack.stacks[0], 1);
assert_eq!(stack.stacks[1], 2);
assert_eq!(stack.stacks[2], 3);
assert_eq!(stack.left_head, Some(1));
assert_eq!(stack.right_head, 2);
}
#[test]
#[should_panic]
fn test_push_left_exceeding_right_head_stack() {
let mut stack = DStack::with_capacity(3);
stack.push_right(3);
stack.push_left(1);
stack.push_right(2);
stack.push_left(10);
}
#[test]
fn test_push_right_without_exceeding_left_head_stack() {
let mut stack = DStack::with_capacity(3);
stack.push_right(3);
stack.push_left(1);
stack.push_right(2);
assert_eq!(stack.stacks[0], 1);
assert_eq!(stack.stacks[1], 2);
assert_eq!(stack.stacks[2], 3);
assert_eq!(stack.left_head, Some(0));
assert_eq!(stack.right_head, 1);
}
#[test]
#[should_panic]
fn test_push_right_exceeding_left_head_stack() {
let mut stack = DStack::with_capacity(3);
stack.push_left(3);
stack.push_right(1);
stack.push_left(2);
stack.push_right(10);
}
#[test]
fn test_pop_left_on_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
let res = stack.pop_left();
assert!(matches!(res, None));
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, 10);
}
#[test]
fn test_pop_left_on_non_empty_stack() {
let mut stack = DStack::with_capacity(10);
stack.push_left(144);
let res = stack.pop_left();
assert_eq!(res, Some(144));
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, 10);
}
#[test]
fn test_pop_right_on_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
let res = stack.pop_right();
assert!(matches!(res, None));
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, 10);
}
#[test]
fn test_pop_right_on_non_empty_stack() {
let mut stack = DStack::with_capacity(10);
stack.push_right(144);
let res = stack.pop_right();
assert_eq!(res, Some(144));
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, 10);
}
#[test]
fn test_len_right_on_empty_stack() {
let stack = DStack::<i32>::with_capacity(10);
assert_eq!(stack.len_right(), 0);
}
#[test]
fn test_len_right_on_full_stack() {
let mut stack = DStack::<i32>::with_capacity(3);
stack.push_right(1);
stack.push_right(2);
stack.push_left(3);
assert_eq!(stack.len_right(), 2);
}
#[test]
fn test_clear_right_on_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
stack.clear_right();
assert_eq!(stack.right_head, 10);
assert_eq!(stack.left_head, None);
}
#[test]
fn test_clear_right_on_full_stack() {
let mut stack = DStack::<i32>::with_capacity(3);
stack.push_right(1);
stack.push_right(2);
stack.push_left(3);
stack.clear_right();
assert_eq!(stack.right_head, 3);
assert_eq!(stack.left_head, Some(0));
}
#[test]
fn test_clear_left_on_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
stack.clear_left();
assert_eq!(stack.right_head, 10);
assert_eq!(stack.left_head, None);
}
#[test]
fn test_clear_left_on_full_stack() {
let mut stack = DStack::<i32>::with_capacity(3);
stack.push_left(1);
stack.push_left(2);
stack.push_right(3);
stack.clear_left();
assert_eq!(stack.right_head, 2);
assert_eq!(stack.left_head, None);
}
#[test]
fn test_iter_right_on_empty_stack() {
let stack = DStack::<i32>::with_capacity(3);
let mut it = stack.iter_right();
assert_eq!(it.next(), None);
}
#[test]
fn test_iter_right_on_full_stack() {
let mut stack = DStack::<i32>::with_capacity(3);
stack.push_left(1);
stack.push_left(2);
stack.push_right(3);
let mut it = stack.iter_right();
assert!(matches!(it.next(), Some(3)));
assert_eq!(it.next(), None);
}
#[test]
fn test_push_left_on_right_with_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
stack.push_left_on_right();
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, 10);
}
#[test]
fn test_push_left_on_right_stack() {
let mut stack = DStack::with_capacity(10);
stack.push_left(1);
stack.push_left(2);
stack.push_left(3);
stack.push_left_on_right();
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, 7);
}
#[test]
fn test_push_right_on_left_with_empty_stack() {
let mut stack = DStack::<i32>::with_capacity(10);
stack.push_right_on_left();
assert_eq!(stack.left_head, None);
assert_eq!(stack.right_head, 10);
}
#[test]
fn test_push_right_on_left_stack() {
let mut stack = DStack::with_capacity(10);
stack.push_right(1);
stack.push_right(2);
stack.push_right(3);
stack.push_right_on_left();
assert_eq!(stack.left_head, Some(2));
assert_eq!(stack.right_head, 10);
}
}