use alloc::vec;
use alloc::vec::Vec;
use core::ops::{Index, Range};
#[derive(Debug)]
pub struct Stack<T: Clone> {
ops: Vec<StackOp<T>>,
cache: Vec<T>,
snapshots: Vec<usize>,
}
impl<T: Clone> Stack<T> {
pub fn new() -> Self {
Stack {
ops: vec![],
cache: vec![],
snapshots: vec![],
}
}
#[allow(dead_code)]
pub fn is_empty(&self) -> bool {
self.cache.is_empty()
}
pub fn peek(&self) -> Option<&T> {
self.cache.last()
}
pub fn push(&mut self, elem: T) {
self.ops.push(StackOp::Push(elem.clone()));
self.cache.push(elem);
}
pub fn pop(&mut self) -> Option<T> {
let popped = self.cache.pop();
if let Some(ref val) = popped {
self.ops.push(StackOp::Pop(val.clone()));
}
popped
}
pub fn len(&self) -> usize {
self.cache.len()
}
pub fn snapshot(&mut self) {
self.snapshots.push(self.ops.len());
}
pub fn clear_snapshot(&mut self) {
self.snapshots.pop();
}
pub fn restore(&mut self) {
match self.snapshots.pop() {
Some(ops_index) => {
self.rewind_to(ops_index);
self.ops.truncate(ops_index);
}
None => {
self.cache.clear();
self.ops.clear();
}
}
}
fn rewind_to(&mut self, index: usize) {
let ops_to_rewind = &self.ops[index..];
for op in ops_to_rewind.iter().rev() {
match *op {
StackOp::Push(_) => {
self.cache.pop();
}
StackOp::Pop(ref elem) => {
self.cache.push(elem.clone());
}
}
}
}
}
impl<T: Clone> Index<Range<usize>> for Stack<T> {
type Output = [T];
fn index(&self, range: Range<usize>) -> &[T] {
self.cache.index(range)
}
}
#[derive(Debug)]
enum StackOp<T> {
Push(T),
Pop(T),
}
#[cfg(test)]
mod test {
use super::Stack;
#[test]
fn snapshot_with_empty() {
let mut stack = Stack::new();
stack.snapshot();
assert!(stack.is_empty());
stack.push(0);
stack.restore();
assert!(stack.is_empty());
}
#[test]
fn snapshot_twice() {
let mut stack = Stack::new();
stack.push(0);
stack.snapshot();
stack.snapshot();
stack.restore();
stack.restore();
assert_eq!(stack[0..stack.len()], [0]);
}
#[test]
fn stack_ops() {
let mut stack = Stack::new();
assert!(stack.is_empty());
assert_eq!(stack.peek(), None);
assert_eq!(stack.pop(), None);
stack.push(0);
assert!(!stack.is_empty());
assert_eq!(stack.peek(), Some(&0));
stack.push(1);
assert!(!stack.is_empty());
assert_eq!(stack.peek(), Some(&1));
assert_eq!(stack.pop(), Some(1));
assert!(!stack.is_empty());
assert_eq!(stack.peek(), Some(&0));
stack.push(2);
assert!(!stack.is_empty());
assert_eq!(stack.peek(), Some(&2));
stack.push(3);
assert!(!stack.is_empty());
assert_eq!(stack.peek(), Some(&3));
stack.snapshot();
assert_eq!(stack.pop(), Some(3));
assert!(!stack.is_empty());
assert_eq!(stack.peek(), Some(&2));
stack.snapshot();
assert_eq!(stack.pop(), Some(2));
assert!(!stack.is_empty());
assert_eq!(stack.peek(), Some(&0));
assert_eq!(stack.pop(), Some(0));
assert!(stack.is_empty());
stack.restore();
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(0));
assert_eq!(stack.pop(), None);
stack.restore();
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(0));
assert_eq!(stack.pop(), None);
}
}