#[derive(Debug)]
pub struct MovingMin<T> {
push_stack: Vec<(T, T)>,
pop_stack: Vec<(T, T)>,
}
impl<T: Clone + PartialOrd> Default for MovingMin<T> {
fn default() -> Self {
Self {
push_stack: Vec::new(),
pop_stack: Vec::new(),
}
}
}
impl<T: Clone + PartialOrd> MovingMin<T> {
#[inline]
pub fn new() -> Self {
Self::default()
}
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
Self {
push_stack: Vec::with_capacity(capacity),
pop_stack: Vec::with_capacity(capacity),
}
}
#[inline]
pub fn min(&self) -> Option<&T> {
match (self.push_stack.last(), self.pop_stack.last()) {
(None, None) => None,
(Some((_, min)), None) => Some(min),
(None, Some((_, min))) => Some(min),
(Some((_, a)), Some((_, b))) => Some(if a < b { a } else { b }),
}
}
#[inline]
pub fn push(&mut self, val: T) {
self.push_stack.push(match self.push_stack.last() {
Some((_, min)) => {
if val > *min {
(val, min.clone())
} else {
(val.clone(), val)
}
}
None => (val.clone(), val),
});
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
if self.pop_stack.is_empty() {
match self.push_stack.pop() {
Some((val, _)) => {
self.pop_stack.push((val.clone(), val));
while let Some((val, _)) = self.push_stack.pop() {
let last =
unsafe { self.pop_stack.get_unchecked(self.pop_stack.len() - 1) };
let min = if last.1 < val {
last.1.clone()
} else {
val.clone()
};
self.pop_stack.push((val.clone(), min));
}
}
None => return None,
}
}
self.pop_stack.pop().map(|(val, _)| val)
}
#[inline]
pub fn len(&self) -> usize {
self.push_stack.len() + self.pop_stack.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
#[derive(Debug)]
pub struct MovingMax<T> {
push_stack: Vec<(T, T)>,
pop_stack: Vec<(T, T)>,
}
impl<T: Clone + PartialOrd> Default for MovingMax<T> {
fn default() -> Self {
Self {
push_stack: Vec::new(),
pop_stack: Vec::new(),
}
}
}
impl<T: Clone + PartialOrd> MovingMax<T> {
#[inline]
pub fn new() -> Self {
Self::default()
}
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
Self {
push_stack: Vec::with_capacity(capacity),
pop_stack: Vec::with_capacity(capacity),
}
}
#[inline]
pub fn max(&self) -> Option<&T> {
match (self.push_stack.last(), self.pop_stack.last()) {
(None, None) => None,
(Some((_, max)), None) => Some(max),
(None, Some((_, max))) => Some(max),
(Some((_, a)), Some((_, b))) => Some(if a > b { a } else { b }),
}
}
#[inline]
pub fn push(&mut self, val: T) {
self.push_stack.push(match self.push_stack.last() {
Some((_, max)) => {
if val < *max {
(val, max.clone())
} else {
(val.clone(), val)
}
}
None => (val.clone(), val),
});
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
if self.pop_stack.is_empty() {
match self.push_stack.pop() {
Some((val, _)) => {
self.pop_stack.push((val.clone(), val));
while let Some((val, _)) = self.push_stack.pop() {
let last =
unsafe { self.pop_stack.get_unchecked(self.pop_stack.len() - 1) };
let max = if last.1 > val {
last.1.clone()
} else {
val.clone()
};
self.pop_stack.push((val.clone(), max));
}
}
None => return None,
}
}
self.pop_stack.pop().map(|(val, _)| val)
}
#[inline]
pub fn len(&self) -> usize {
self.push_stack.len() + self.pop_stack.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn moving_min() {
let mut moving_min = MovingMin::<i32>::new();
moving_min.push(1);
assert_eq!(moving_min.min(), Some(&1));
moving_min.push(2);
assert_eq!(moving_min.min(), Some(&1));
moving_min.push(3);
assert_eq!(moving_min.min(), Some(&1));
assert_eq!(moving_min.pop(), Some(1));
assert_eq!(moving_min.min(), Some(&2));
assert_eq!(moving_min.pop(), Some(2));
assert_eq!(moving_min.pop(), Some(3));
assert_eq!(moving_min.pop(), None);
moving_min.push(2);
moving_min.push(1);
moving_min.push(3);
assert_eq!(moving_min.min(), Some(&1));
assert_eq!(moving_min.pop(), Some(2));
assert_eq!(moving_min.min(), Some(&1));
assert_eq!(moving_min.pop(), Some(1));
assert_eq!(moving_min.min(), Some(&3));
assert_eq!(moving_min.pop(), Some(3));
assert_eq!(moving_min.min(), None);
assert_eq!(moving_min.pop(), None);
}
#[test]
fn moving_max() {
let mut moving_max = MovingMax::<i32>::new();
moving_max.push(3);
assert_eq!(moving_max.max(), Some(&3));
moving_max.push(2);
assert_eq!(moving_max.max(), Some(&3));
moving_max.push(1);
assert_eq!(moving_max.max(), Some(&3));
assert_eq!(moving_max.pop(), Some(3));
assert_eq!(moving_max.max(), Some(&2));
assert_eq!(moving_max.pop(), Some(2));
assert_eq!(moving_max.pop(), Some(1));
assert_eq!(moving_max.pop(), None);
moving_max.push(2);
moving_max.push(3);
moving_max.push(1);
assert_eq!(moving_max.max(), Some(&3));
assert_eq!(moving_max.pop(), Some(2));
assert_eq!(moving_max.max(), Some(&3));
assert_eq!(moving_max.pop(), Some(3));
assert_eq!(moving_max.max(), Some(&1));
assert_eq!(moving_max.pop(), Some(1));
assert_eq!(moving_max.max(), None);
assert_eq!(moving_max.pop(), None);
}
}