queue_model/

lib.rs

//! Abstraction of the concept of a queue.

#![no_std]
#![warn(missing_docs)]

use core::{
    cmp::max,
    mem::{replace, MaybeUninit},
};

use cfg_if::cfg_if;
use safe_modular_arithmetic::StaticModular;

/// Trait which queue implementations must conform to.
pub trait QueueModel {
    /// The type of items in the queue.
    type Item;

    /// Attempts to enqueue an item; returns whether or not it was successful.
    fn enqueue(&mut self, item: Self::Item) -> bool;

    /// Attempts to dequeue an item; returns `None` if there are no items
    /// available.
    fn dequeue(&mut self) -> Option<Self::Item>;

    /// Checks if the queue is empty.
    fn is_empty(&self) -> bool;
}

/// A statically-sized queue which is implemented as a ring buffer.
pub struct StaticRingQueue<T, const N: usize> {
    length: usize,
    offset: StaticModular<usize, N>,
    buffer: [MaybeUninit<T>; N],
}

impl<T, const N: usize> StaticRingQueue<T, N> {
    /// Creates a new queue.
    #[inline]
    pub fn new() -> Self {
        Self {
            length: 0,
            offset: 0.into(),
            buffer: unsafe { MaybeUninit::uninit().assume_init() },
        }
    }
}

impl<T, const N: usize> Default for StaticRingQueue<T, N> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T, const N: usize> QueueModel for StaticRingQueue<T, N> {
    type Item = T;

    fn enqueue(&mut self, item: Self::Item) -> bool {
        if self.length == N {
            false
        } else {
            self.buffer[self.offset + self.length.into()] = MaybeUninit::new(item);
            self.length += 1;
            true
        }
    }

    fn dequeue(&mut self) -> Option<Self::Item> {
        if self.length == 0 {
            None
        } else {
            let item = replace(&mut self.buffer[self.offset], MaybeUninit::uninit());
            self.offset = self.offset + 1.into();
            self.length -= 1;
            Some(unsafe { item.assume_init() })
        }
    }

    fn is_empty(&self) -> bool {
        self.length == 0
    }
}

/// A statically-sized queue which is implemented as a max-heap.
pub struct StaticPriorityQueue<T: Ord, const N: usize> {
    length: usize,
    buffer: [MaybeUninit<T>; N],
}

impl<T: Ord, const N: usize> StaticPriorityQueue<T, N> {
    /// Creates a new queue.
    #[inline]
    pub fn new() -> Self {
        Self {
            length: 0,
            buffer: unsafe { MaybeUninit::uninit().assume_init() },
        }
    }
}

impl<T: Ord, const N: usize> Default for StaticPriorityQueue<T, N> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Ord, const N: usize> QueueModel for StaticPriorityQueue<T, N> {
    type Item = T;

    fn enqueue(&mut self, item: Self::Item) -> bool {
        if self.length == N {
            false
        } else {
            up_heap(&mut self.buffer[0..=self.length], self.length, item);
            self.length += 1;
            true
        }
    }

    fn dequeue(&mut self) -> Option<Self::Item> {
        if self.length == 0 {
            None
        } else {
            self.length -= 1;
            let last = replace(&mut self.buffer[self.length], MaybeUninit::uninit());
            let item = down_heap(&mut self.buffer[0..self.length], 0, unsafe {
                last.assume_init()
            });
            Some(unsafe { item.assume_init() })
        }
    }

    fn is_empty(&self) -> bool {
        self.length == 0
    }
}

cfg_if! {
    if #[cfg(feature = "alloc")] {
        extern crate alloc;
        use alloc::collections::{BinaryHeap, VecDeque};

        impl<T> QueueModel for VecDeque<T> {
            type Item = T;

            #[inline]
            fn enqueue(&mut self, item: Self::Item) -> bool {
                self.push_back(item);
                true
            }

            #[inline]
            fn dequeue(&mut self) -> Option<Self::Item> {
                self.pop_front()
            }

            #[inline]
            fn is_empty(&self) -> bool {
                Self::is_empty(&self)
            }
        }

        impl<T: Ord> QueueModel for BinaryHeap<T> {
            type Item = T;

            #[inline]
            fn enqueue(&mut self, item: Self::Item) -> bool {
                self.push(item);
                true
            }

            #[inline]
            fn dequeue(&mut self) -> Option<Self::Item> {
                self.pop()
            }

            #[inline]
            fn is_empty(&self) -> bool {
                Self::is_empty(&self)
            }
        }
    }
}

fn up_heap<T: Ord>(buffer: &mut [MaybeUninit<T>], index: usize, item: T) -> MaybeUninit<T> {
    let next = if index == 0 {
        MaybeUninit::new(item)
    } else {
        let parent = (index - 1) / 2;
        if unsafe { &*(&buffer[parent] as *const _ as *const T) } < &item {
            up_heap(buffer, parent, item)
        } else {
            MaybeUninit::new(item)
        }
    };
    replace(&mut buffer[index], next)
}

fn down_heap<T: Ord>(buffer: &mut [MaybeUninit<T>], index: usize, item: T) -> MaybeUninit<T> {
    if index >= buffer.len() {
        return MaybeUninit::new(item);
    }

    let child = [index * 2 + 1, index * 2 + 2]
        .iter()
        .filter_map(|i| {
            buffer
                .get_mut(*i)
                .map(|v| (unsafe { &*(v as *const _ as *const T) }, *i))
        })
        .fold(None, |acc, cur| {
            if let Some(acc) = acc {
                Some(max(acc, cur))
            } else if *cur.0 > item {
                Some(cur)
            } else {
                None
            }
        });
    let next = if let Some((_, i)) = child {
        down_heap(buffer, i, item)
    } else {
        MaybeUninit::new(item)
    };
    replace(&mut buffer[index], next)
}