use std::cmp::{self, Ordering};
use std::collections::vec_deque::{Drain, IntoIter, Iter, IterMut, VecDeque};
use std::hash::{Hash, Hasher};
use std::ops::{Index, IndexMut, RangeBounds};
#[derive(Clone, Debug)]
pub struct FixedLifoDeque<T> {
storage: VecDeque<T>,
limit: usize,
}
impl<T> FixedLifoDeque<T> {
#[inline]
pub fn new() -> Self {
FixedLifoDeque::with_limit(0)
}
pub fn with_limit(n: usize) -> Self {
FixedLifoDeque { storage: VecDeque::with_capacity(n), limit: n }
}
pub fn reset_limit(&mut self, n: usize) {
if n < self.limit {
let overflow = self.limit - n;
self.drop_excess_for_inserting(overflow);
}
self.limit = n;
self.storage.reserve_exact(n);
self.storage.shrink_to_fit();
debug_assert!(self.storage.len() <= self.limit);
}
#[inline]
pub fn limit(&self) -> usize {
self.limit
}
#[inline]
pub fn get(&self, index: usize) -> Option<&T> {
self.storage.get(index)
}
#[inline]
pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
self.storage.get_mut(index)
}
#[inline]
pub fn swap(&mut self, i: usize, j: usize) {
self.storage.swap(i, j);
}
#[inline]
pub fn capacity(&self) -> usize {
self.limit
}
#[inline]
pub fn iter(&self) -> Iter<T> {
self.storage.iter()
}
#[inline]
pub fn iter_mut(&mut self) -> IterMut<T> {
self.storage.iter_mut()
}
#[inline]
pub fn as_slices(&self) -> (&[T], &[T]) {
self.storage.as_slices()
}
#[inline]
pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
self.storage.as_mut_slices()
}
#[inline]
pub fn len(&self) -> usize {
self.storage.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.storage.is_empty()
}
#[inline]
pub fn drain<R>(&mut self, range: R) -> Drain<T>
where
R: RangeBounds<usize>,
{
self.storage.drain(range)
}
#[inline]
pub fn clear(&mut self) {
self.storage.clear();
}
#[inline]
pub fn contains(&self, x: &T) -> bool
where
T: PartialEq<T>,
{
self.storage.contains(x)
}
#[inline]
pub fn front(&self) -> Option<&T> {
self.storage.front()
}
#[inline]
pub fn front_mut(&mut self) -> Option<&mut T> {
self.storage.front_mut()
}
#[inline]
pub fn back(&self) -> Option<&T> {
self.storage.back()
}
#[inline]
pub fn back_mut(&mut self) -> Option<&mut T> {
self.storage.back_mut()
}
#[inline]
fn drop_excess_for_inserting(&mut self, n_to_be_inserted: usize) {
if self.storage.len() + n_to_be_inserted > self.limit {
let overflow =
self.storage.len().min(self.storage.len() + n_to_be_inserted - self.limit);
self.storage.drain(..overflow);
}
}
#[inline]
pub fn pop_front(&mut self) -> Option<T> {
self.storage.pop_front()
}
pub fn push_back(&mut self, value: T) {
self.drop_excess_for_inserting(1);
self.storage.push_back(value);
self.drop_excess_for_inserting(0);
}
#[inline]
pub fn pop_back(&mut self) -> Option<T> {
self.storage.pop_back()
}
#[inline]
pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
self.storage.swap_remove_back(index)
}
#[inline]
pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
self.storage.swap_remove_front(index)
}
#[inline]
pub fn remove(&mut self, index: usize) -> Option<T> {
self.storage.remove(index)
}
pub fn split_off(&mut self, at: usize) -> FixedLifoDeque<T> {
FixedLifoDeque { storage: self.storage.split_off(at), limit: self.limit }
}
pub fn append(&mut self, other: &mut VecDeque<T>) {
self.drop_excess_for_inserting(other.len());
self.storage.append(other);
self.drop_excess_for_inserting(0);
}
#[inline]
pub fn retain<F>(&mut self, f: F)
where
F: FnMut(&T) -> bool,
{
self.storage.retain(f);
}
}
impl<T: Clone> FixedLifoDeque<T> {
pub fn resize(&mut self, new_len: usize, value: T) {
if new_len < self.len() {
let to_drop = self.len() - new_len;
self.storage.drain(..to_drop);
} else {
self.storage.resize(cmp::min(self.limit, new_len), value);
}
}
}
impl<A: PartialEq> PartialEq for FixedLifoDeque<A> {
#[inline]
fn eq(&self, other: &FixedLifoDeque<A>) -> bool {
self.storage == other.storage
}
}
impl<A: Eq> Eq for FixedLifoDeque<A> {}
impl<A: PartialOrd> PartialOrd for FixedLifoDeque<A> {
#[inline]
fn partial_cmp(&self, other: &FixedLifoDeque<A>) -> Option<Ordering> {
self.storage.partial_cmp(&other.storage)
}
}
impl<A: Ord> Ord for FixedLifoDeque<A> {
#[inline]
fn cmp(&self, other: &FixedLifoDeque<A>) -> Ordering {
self.storage.cmp(&other.storage)
}
}
impl<A: Hash> Hash for FixedLifoDeque<A> {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
self.storage.hash(state);
}
}
impl<A> Index<usize> for FixedLifoDeque<A> {
type Output = A;
#[inline]
fn index(&self, index: usize) -> &A {
&self.storage[index]
}
}
impl<A> IndexMut<usize> for FixedLifoDeque<A> {
#[inline]
fn index_mut(&mut self, index: usize) -> &mut A {
&mut self.storage[index]
}
}
impl<T> IntoIterator for FixedLifoDeque<T> {
type Item = T;
type IntoIter = IntoIter<T>;
#[inline]
fn into_iter(self) -> IntoIter<T> {
self.storage.into_iter()
}
}
impl<'a, T> IntoIterator for &'a FixedLifoDeque<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
#[inline]
fn into_iter(self) -> Iter<'a, T> {
self.storage.iter()
}
}
impl<'a, T> IntoIterator for &'a mut FixedLifoDeque<T> {
type Item = &'a mut T;
type IntoIter = IterMut<'a, T>;
#[inline]
fn into_iter(self) -> IterMut<'a, T> {
self.storage.iter_mut()
}
}
impl<A> Extend<A> for FixedLifoDeque<A> {
fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
for elt in iter {
self.push_back(elt);
}
}
}
impl<'a, T: 'a + Copy> Extend<&'a T> for FixedLifoDeque<T> {
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.extend(iter.into_iter().cloned());
}
}
#[cfg(test)]
mod tests {
use super::*;
#[cfg(feature = "benchmarks")]
use test::Bencher;
#[test]
fn test_basic_insertions() {
let mut tester = FixedLifoDeque::with_limit(3);
assert_eq!(tester.len(), 0);
assert_eq!(tester.capacity(), 3);
assert_eq!(tester.front(), None);
assert_eq!(tester.back(), None);
tester.push_back(1);
assert_eq!(tester.len(), 1);
assert_eq!(tester.front(), Some(1).as_ref());
assert_eq!(tester.back(), Some(1).as_ref());
tester.push_back(2);
assert_eq!(tester.len(), 2);
assert_eq!(tester.front(), Some(1).as_ref());
assert_eq!(tester.back(), Some(2).as_ref());
tester.push_back(3);
tester.push_back(4);
assert_eq!(tester.len(), 3);
assert_eq!(tester.front(), Some(2).as_ref());
assert_eq!(tester.back(), Some(4).as_ref());
assert_eq!(tester[0], 2);
assert_eq!(tester[1], 3);
assert_eq!(tester[2], 4);
}
#[cfg(feature = "benchmarks")]
#[bench]
fn bench_push_back(b: &mut Bencher) {
let mut q = FixedLifoDeque::with_limit(10);
b.iter(|| q.push_back(5));
}
#[cfg(feature = "benchmarks")]
#[bench]
fn bench_deletion_from_empty(b: &mut Bencher) {
let mut q = FixedLifoDeque::<u32>::with_limit(10000);
b.iter(|| q.pop_front());
}
#[cfg(feature = "benchmarks")]
#[bench]
fn bench_deletion_from_non_empty(b: &mut Bencher) {
let mut q = FixedLifoDeque::with_limit(1000000);
for i in 0..q.limit() {
q.push_back(i);
}
b.iter(|| q.pop_front());
}
}