use core::fmt;
use core::iter::FusedIterator;
use core::marker::PhantomData;
use core::mem::MaybeUninit;
use core::{ptr, slice};
pub struct Deque<T, const N: usize> {
buffer: [MaybeUninit<T>; N],
front: usize,
back: usize,
full: bool,
}
impl<T, const N: usize> Deque<T, N> {
const INIT: MaybeUninit<T> = MaybeUninit::uninit();
pub const fn new() -> Self {
crate::sealed::greater_than_0::<N>();
Self {
buffer: [Self::INIT; N],
front: 0,
back: 0,
full: false,
}
}
fn increment(i: usize) -> usize {
if i + 1 == N {
0
} else {
i + 1
}
}
fn decrement(i: usize) -> usize {
if i == 0 {
N - 1
} else {
i - 1
}
}
pub const fn capacity(&self) -> usize {
N
}
pub const fn len(&self) -> usize {
if self.full {
N
} else if self.back < self.front {
self.back + N - self.front
} else {
self.back - self.front
}
}
pub fn clear(&mut self) {
unsafe { self.drop_contents() }
self.front = 0;
self.back = 0;
self.full = false;
}
unsafe fn drop_contents(&mut self) {
let (a, b) = self.as_mut_slices();
ptr::drop_in_place(a);
ptr::drop_in_place(b);
}
pub fn is_empty(&self) -> bool {
self.front == self.back && !self.full
}
pub fn is_full(&self) -> bool {
self.full
}
pub fn as_slices(&self) -> (&[T], &[T]) {
unsafe {
if self.is_empty() {
(&[], &[])
} else if self.back <= self.front {
(
slice::from_raw_parts(
self.buffer.as_ptr().add(self.front) as *const T,
N - self.front,
),
slice::from_raw_parts(self.buffer.as_ptr() as *const T, self.back),
)
} else {
(
slice::from_raw_parts(
self.buffer.as_ptr().add(self.front) as *const T,
self.back - self.front,
),
&[],
)
}
}
}
pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
let ptr = self.buffer.as_mut_ptr();
unsafe {
if self.is_empty() {
(&mut [], &mut [])
} else if self.back <= self.front {
(
slice::from_raw_parts_mut(ptr.add(self.front) as *mut T, N - self.front),
slice::from_raw_parts_mut(ptr as *mut T, self.back),
)
} else {
(
slice::from_raw_parts_mut(
ptr.add(self.front) as *mut T,
self.back - self.front,
),
&mut [],
)
}
}
}
pub fn front(&self) -> Option<&T> {
if self.is_empty() {
None
} else {
Some(unsafe { &*self.buffer.get_unchecked(self.front).as_ptr() })
}
}
pub fn front_mut(&mut self) -> Option<&mut T> {
if self.is_empty() {
None
} else {
Some(unsafe { &mut *self.buffer.get_unchecked_mut(self.front).as_mut_ptr() })
}
}
pub fn back(&self) -> Option<&T> {
if self.is_empty() {
None
} else {
let index = Self::decrement(self.back);
Some(unsafe { &*self.buffer.get_unchecked(index).as_ptr() })
}
}
pub fn back_mut(&mut self) -> Option<&mut T> {
if self.is_empty() {
None
} else {
let index = Self::decrement(self.back);
Some(unsafe { &mut *self.buffer.get_unchecked_mut(index).as_mut_ptr() })
}
}
pub fn pop_front(&mut self) -> Option<T> {
if self.is_empty() {
None
} else {
Some(unsafe { self.pop_front_unchecked() })
}
}
pub fn pop_back(&mut self) -> Option<T> {
if self.is_empty() {
None
} else {
Some(unsafe { self.pop_back_unchecked() })
}
}
pub fn push_front(&mut self, item: T) -> Result<(), T> {
if self.is_full() {
Err(item)
} else {
unsafe { self.push_front_unchecked(item) }
Ok(())
}
}
pub fn push_back(&mut self, item: T) -> Result<(), T> {
if self.is_full() {
Err(item)
} else {
unsafe { self.push_back_unchecked(item) }
Ok(())
}
}
pub unsafe fn pop_front_unchecked(&mut self) -> T {
debug_assert!(!self.is_empty());
let index = self.front;
self.full = false;
self.front = Self::increment(self.front);
(self.buffer.get_unchecked_mut(index).as_ptr() as *const T).read()
}
pub unsafe fn pop_back_unchecked(&mut self) -> T {
debug_assert!(!self.is_empty());
self.full = false;
self.back = Self::decrement(self.back);
(self.buffer.get_unchecked_mut(self.back).as_ptr() as *const T).read()
}
pub unsafe fn push_front_unchecked(&mut self, item: T) {
debug_assert!(!self.is_full());
let index = Self::decrement(self.front);
*self.buffer.get_unchecked_mut(index) = MaybeUninit::new(item);
self.front = index;
if self.front == self.back {
self.full = true;
}
}
pub unsafe fn push_back_unchecked(&mut self, item: T) {
debug_assert!(!self.is_full());
*self.buffer.get_unchecked_mut(self.back) = MaybeUninit::new(item);
self.back = Self::increment(self.back);
if self.front == self.back {
self.full = true;
}
}
pub fn iter(&self) -> Iter<'_, T, N> {
let done = self.is_empty();
Iter {
_phantom: PhantomData,
buffer: &self.buffer as *const MaybeUninit<T>,
front: self.front,
back: self.back,
done,
}
}
pub fn iter_mut(&mut self) -> IterMut<'_, T, N> {
let done = self.is_empty();
IterMut {
_phantom: PhantomData,
buffer: &mut self.buffer as *mut _ as *mut MaybeUninit<T>,
front: self.front,
back: self.back,
done,
}
}
}
impl<T, const N: usize> Default for Deque<T, N> {
fn default() -> Self {
Self::new()
}
}
impl<T, const N: usize> Drop for Deque<T, N> {
fn drop(&mut self) {
unsafe { self.drop_contents() }
}
}
impl<T: fmt::Debug, const N: usize> fmt::Debug for Deque<T, N> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self).finish()
}
}
#[derive(Clone)]
pub struct IntoIter<T, const N: usize> {
deque: Deque<T, N>,
}
impl<T, const N: usize> Iterator for IntoIter<T, N> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.deque.pop_front()
}
}
impl<T, const N: usize> IntoIterator for Deque<T, N> {
type Item = T;
type IntoIter = IntoIter<T, N>;
fn into_iter(self) -> Self::IntoIter {
IntoIter { deque: self }
}
}
#[derive(Clone)]
pub struct Iter<'a, T, const N: usize> {
buffer: *const MaybeUninit<T>,
_phantom: PhantomData<&'a T>,
front: usize,
back: usize,
done: bool,
}
impl<'a, T, const N: usize> Iterator for Iter<'a, T, N> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.done {
None
} else {
let index = self.front;
self.front = Deque::<T, N>::increment(self.front);
if self.front == self.back {
self.done = true;
}
Some(unsafe { &*(self.buffer.add(index) as *const T) })
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = if self.done {
0
} else if self.back <= self.front {
self.back + N - self.front
} else {
self.back - self.front
};
(len, Some(len))
}
}
impl<'a, T, const N: usize> DoubleEndedIterator for Iter<'a, T, N> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.done {
None
} else {
self.back = Deque::<T, N>::decrement(self.back);
if self.front == self.back {
self.done = true;
}
Some(unsafe { &*(self.buffer.add(self.back) as *const T) })
}
}
}
impl<'a, T, const N: usize> ExactSizeIterator for Iter<'a, T, N> {}
impl<'a, T, const N: usize> FusedIterator for Iter<'a, T, N> {}
pub struct IterMut<'a, T, const N: usize> {
buffer: *mut MaybeUninit<T>,
_phantom: PhantomData<&'a mut T>,
front: usize,
back: usize,
done: bool,
}
impl<'a, T, const N: usize> Iterator for IterMut<'a, T, N> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
if self.done {
None
} else {
let index = self.front;
self.front = Deque::<T, N>::increment(self.front);
if self.front == self.back {
self.done = true;
}
Some(unsafe { &mut *(self.buffer.add(index) as *mut T) })
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = if self.done {
0
} else if self.back <= self.front {
self.back + N - self.front
} else {
self.back - self.front
};
(len, Some(len))
}
}
impl<'a, T, const N: usize> DoubleEndedIterator for IterMut<'a, T, N> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.done {
None
} else {
self.back = Deque::<T, N>::decrement(self.back);
if self.front == self.back {
self.done = true;
}
Some(unsafe { &mut *(self.buffer.add(self.back) as *mut T) })
}
}
}
impl<'a, T, const N: usize> ExactSizeIterator for IterMut<'a, T, N> {}
impl<'a, T, const N: usize> FusedIterator for IterMut<'a, T, N> {}
impl<'a, T, const N: usize> IntoIterator for &'a Deque<T, N> {
type Item = &'a T;
type IntoIter = Iter<'a, T, N>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, T, const N: usize> IntoIterator for &'a mut Deque<T, N> {
type Item = &'a mut T;
type IntoIter = IterMut<'a, T, N>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<T, const N: usize> Clone for Deque<T, N>
where
T: Clone,
{
fn clone(&self) -> Self {
let mut res = Deque::new();
for i in self {
unsafe { res.push_back_unchecked(i.clone()) }
}
res
}
}
#[cfg(test)]
mod tests {
use crate::Deque;
#[test]
fn static_new() {
static mut _V: Deque<i32, 4> = Deque::new();
}
#[test]
fn stack_new() {
let mut _v: Deque<i32, 4> = Deque::new();
}
#[test]
fn drop() {
droppable!();
{
let mut v: Deque<Droppable, 2> = Deque::new();
v.push_back(Droppable::new()).ok().unwrap();
v.push_back(Droppable::new()).ok().unwrap();
v.pop_front().unwrap();
}
assert_eq!(Droppable::count(), 0);
{
let mut v: Deque<Droppable, 2> = Deque::new();
v.push_back(Droppable::new()).ok().unwrap();
v.push_back(Droppable::new()).ok().unwrap();
}
assert_eq!(Droppable::count(), 0);
{
let mut v: Deque<Droppable, 2> = Deque::new();
v.push_front(Droppable::new()).ok().unwrap();
v.push_front(Droppable::new()).ok().unwrap();
}
assert_eq!(Droppable::count(), 0);
}
#[test]
fn full() {
let mut v: Deque<i32, 4> = Deque::new();
v.push_back(0).unwrap();
v.push_front(1).unwrap();
v.push_back(2).unwrap();
v.push_back(3).unwrap();
assert!(v.push_front(4).is_err());
assert!(v.push_back(4).is_err());
assert!(v.is_full());
}
#[test]
fn empty() {
let mut v: Deque<i32, 4> = Deque::new();
assert!(v.is_empty());
v.push_back(0).unwrap();
assert!(!v.is_empty());
v.push_front(1).unwrap();
assert!(!v.is_empty());
v.pop_front().unwrap();
v.pop_front().unwrap();
assert!(v.pop_front().is_none());
assert!(v.pop_back().is_none());
assert!(v.is_empty());
}
#[test]
fn front_back() {
let mut v: Deque<i32, 4> = Deque::new();
assert_eq!(v.front(), None);
assert_eq!(v.front_mut(), None);
assert_eq!(v.back(), None);
assert_eq!(v.back_mut(), None);
v.push_back(4).unwrap();
assert_eq!(v.front(), Some(&4));
assert_eq!(v.front_mut(), Some(&mut 4));
assert_eq!(v.back(), Some(&4));
assert_eq!(v.back_mut(), Some(&mut 4));
v.push_front(3).unwrap();
assert_eq!(v.front(), Some(&3));
assert_eq!(v.front_mut(), Some(&mut 3));
assert_eq!(v.back(), Some(&4));
assert_eq!(v.back_mut(), Some(&mut 4));
v.pop_back().unwrap();
assert_eq!(v.front(), Some(&3));
assert_eq!(v.front_mut(), Some(&mut 3));
assert_eq!(v.back(), Some(&3));
assert_eq!(v.back_mut(), Some(&mut 3));
v.pop_front().unwrap();
assert_eq!(v.front(), None);
assert_eq!(v.front_mut(), None);
assert_eq!(v.back(), None);
assert_eq!(v.back_mut(), None);
}
#[test]
fn iter() {
let mut v: Deque<i32, 4> = Deque::new();
v.push_back(0).unwrap();
v.push_back(1).unwrap();
v.push_front(2).unwrap();
v.push_front(3).unwrap();
v.pop_back().unwrap();
v.push_front(4).unwrap();
let mut items = v.iter();
assert_eq!(items.next(), Some(&4));
assert_eq!(items.next(), Some(&3));
assert_eq!(items.next(), Some(&2));
assert_eq!(items.next(), Some(&0));
assert_eq!(items.next(), None);
}
#[test]
fn iter_mut() {
let mut v: Deque<i32, 4> = Deque::new();
v.push_back(0).unwrap();
v.push_back(1).unwrap();
v.push_front(2).unwrap();
v.push_front(3).unwrap();
v.pop_back().unwrap();
v.push_front(4).unwrap();
let mut items = v.iter_mut();
assert_eq!(items.next(), Some(&mut 4));
assert_eq!(items.next(), Some(&mut 3));
assert_eq!(items.next(), Some(&mut 2));
assert_eq!(items.next(), Some(&mut 0));
assert_eq!(items.next(), None);
}
#[test]
fn iter_move() {
let mut v: Deque<i32, 4> = Deque::new();
v.push_back(0).unwrap();
v.push_back(1).unwrap();
v.push_back(2).unwrap();
v.push_back(3).unwrap();
let mut items = v.into_iter();
assert_eq!(items.next(), Some(0));
assert_eq!(items.next(), Some(1));
assert_eq!(items.next(), Some(2));
assert_eq!(items.next(), Some(3));
assert_eq!(items.next(), None);
}
#[test]
fn iter_move_drop() {
droppable!();
{
let mut deque: Deque<Droppable, 2> = Deque::new();
deque.push_back(Droppable::new()).ok().unwrap();
deque.push_back(Droppable::new()).ok().unwrap();
let mut items = deque.into_iter();
let _ = items.next();
let _ = items.next();
}
assert_eq!(Droppable::count(), 0);
{
let mut deque: Deque<Droppable, 2> = Deque::new();
deque.push_back(Droppable::new()).ok().unwrap();
deque.push_back(Droppable::new()).ok().unwrap();
let _items = deque.into_iter();
}
assert_eq!(Droppable::count(), 0);
{
let mut deque: Deque<Droppable, 2> = Deque::new();
deque.push_back(Droppable::new()).ok().unwrap();
deque.push_back(Droppable::new()).ok().unwrap();
let mut items = deque.into_iter();
let _ = items.next(); }
assert_eq!(Droppable::count(), 0);
}
#[test]
fn push_and_pop() {
let mut q: Deque<i32, 4> = Deque::new();
assert_eq!(q.len(), 0);
assert_eq!(q.pop_front(), None);
assert_eq!(q.pop_back(), None);
assert_eq!(q.len(), 0);
q.push_back(0).unwrap();
assert_eq!(q.len(), 1);
assert_eq!(q.pop_back(), Some(0));
assert_eq!(q.len(), 0);
q.push_back(0).unwrap();
q.push_back(1).unwrap();
q.push_front(2).unwrap();
q.push_front(3).unwrap();
assert_eq!(q.len(), 4);
assert_eq!(q.pop_front(), Some(3));
assert_eq!(q.len(), 3);
assert_eq!(q.pop_front(), Some(2));
assert_eq!(q.len(), 2);
assert_eq!(q.pop_back(), Some(1));
assert_eq!(q.len(), 1);
assert_eq!(q.pop_front(), Some(0));
assert_eq!(q.len(), 0);
assert_eq!(q.pop_front(), None);
assert_eq!(q.pop_back(), None);
assert_eq!(q.len(), 0);
}
#[test]
fn as_slices() {
let mut q: Deque<i32, 4> = Deque::new();
assert_eq!(q.len(), 0);
q.push_back(0).unwrap();
q.push_back(1).unwrap();
q.push_back(2).unwrap();
q.push_back(3).unwrap();
assert_eq!(q.as_slices(), (&[0, 1, 2, 3][..], &[][..]));
q.pop_front().unwrap();
assert_eq!(q.as_slices(), (&[1, 2, 3][..], &[][..]));
q.push_back(4).unwrap();
assert_eq!(q.as_slices(), (&[1, 2, 3][..], &[4][..]));
}
#[test]
fn clear() {
let mut q: Deque<i32, 4> = Deque::new();
assert_eq!(q.len(), 0);
q.push_back(0).unwrap();
q.push_back(1).unwrap();
q.push_back(2).unwrap();
q.push_back(3).unwrap();
assert_eq!(q.len(), 4);
q.clear();
assert_eq!(q.len(), 0);
q.push_back(0).unwrap();
assert_eq!(q.len(), 1);
}
}