ufotofu 0.10.1

use core::{cmp::min, fmt};

use alloc::collections::VecDeque;

use crate::queues::{BoundedQueue, Queue};

/// A queue whose internal storage grows and shrinks dynamically within predifined bounds.
pub struct Elastic<T> {
    /// The lower bound on the capacity of the queue
    minimum_capacity: usize,
    /// The upper bound on the capacity of the queue
    maximum_capacity: usize,
    /// Buffered items
    pub(super) buffer: VecDeque<T>,
    /// Number of items in the queue
    amount: usize,
    /// The function we use to initialise buffer slots, or to reset them after having produced an item.
    initialise_memory: fn() -> T,
}

impl<T> Elastic<T> {
    /// Creates a new elastic queue.
    ///
    /// The `initialise_memory` function is used internally to ensure that all queue slots contain valid memory at all times. The specific choice of `T` returned by that funciton does not affect the observable semantics of the queue at all.
    ///
    /// # Panics
    ///
    /// Panics if `minimum_capacity > maximum_capacity`.
    pub(crate) fn new(
        minimum_capacity: usize,
        maximum_capacity: usize,
        initialise_memory: fn() -> T,
    ) -> Self {
        debug_assert!(
            minimum_capacity != 0,
            "The minimum capacity of an elastic queue must be greater than 0."
        );
        assert!(minimum_capacity <= maximum_capacity, "The maximum capacity of an elastic queue must be at least as large as its minimum capacity, but got minimum = {minimum_capacity}, maximum = {maximum_capacity}");

        Self {
            minimum_capacity,
            maximum_capacity,
            buffer: VecDeque::with_capacity(minimum_capacity),
            amount: 0,
            initialise_memory,
        }
    }

    /// Returns a slice containing the next items that should be read.
    fn readable_slice(&mut self) -> &[T] {
        let (fst, snd) = self.buffer.as_slices();

        if fst.is_empty() {
            &snd[..min(snd.len(), self.amount)]
        } else {
            &fst[..min(fst.len(), self.amount)]
        }
    }

    /// Returns a slice containing the next slots that should be written to.
    fn writeable_slice(&mut self) -> &mut [T] {
        let (fst, snd) = self.buffer.as_mut_slices();

        let fst_len = fst.len();
        if fst_len > self.amount {
            &mut fst[self.amount..]
        } else {
            let snd_len = snd.len();
            &mut snd[min(snd_len, self.amount - fst_len)..]
        }
    }

    /// Expands the capacity of the queue within bounds, if it is currently full.
    ///
    /// Returns `true` if the queue has room for additional items once the function returns.
    fn try_capacity(&mut self) -> bool {
        let expandable = self.buffer.len() < self.maximum_capacity;
        let full = self.buffer.len() == self.amount;

        if full && expandable {
            let new_len = (self.buffer.capacity() * 2).min(self.maximum_capacity);
            self.buffer.resize_with(new_len, self.initialise_memory);

            // We successfully made room for new items
            true
        } else {
            // We only have room for new items if we already had enough
            !full
        }
    }

    /// Shrinks the capacity of the queue if it is under half-full.
    fn shrink_if_possible(&mut self) {
        if self.amount < self.buffer.capacity() / 2 {
            self.buffer
                .shrink_to((self.buffer.capacity() / 2).max(self.minimum_capacity));
        }
    }
}

impl<T> Queue for Elastic<T> {
    type Item = T;

    fn len(&self) -> usize {
        self.amount
    }

    fn is_full(&self) -> bool {
        self.amount == self.maximum_capacity
    }

    fn max_capacity(&self) -> Option<usize> {
        Some(self.maximum_capacity)
    }

    fn enqueue(&mut self, item: T) -> Option<T> {
        if self.try_capacity() {
            self.buffer[self.amount] = item;
            self.amount += 1;
            None
        } else {
            Some(item)
        }
    }

    async fn expose_slots<F, R>(&mut self, f: F) -> R
    where
        F: AsyncFnOnce(&mut [T]) -> (usize, R),
    {
        self.try_capacity();
        let (amount, returned) = f(self.writeable_slice()).await;
        self.amount += amount;
        returned
    }

    fn dequeue(&mut self) -> Option<T> {
        if self.amount == 0 {
            None
        } else {
            let tmp = self.buffer.pop_front();
            self.amount -= 1;
            self.shrink_if_possible();
            Some(tmp.expect("amount == 0 if queue is empty"))
        }
    }

    async fn expose_items<F, R>(&mut self, f: F) -> R
    where
        F: AsyncFnOnce(&[T]) -> (usize, R),
    {
        let (amount, returned) = f(self.readable_slice()).await;
        self.amount -= amount;

        // TODO use truncate_front once stabilised: https://github.com/rust-lang/rust/issues/140667
        let rotate_by = amount;
        self.buffer.rotate_left(rotate_by);
        self.buffer.truncate(self.amount);
        self.shrink_if_possible();

        returned
    }
}

impl<T: fmt::Debug> fmt::Debug for Elastic<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Elastic")
            .field("minimum_capacity", &self.minimum_capacity)
            .field("maximum_capacity", &self.maximum_capacity)
            .field("len", &self.amount)
            .field("data", &DataDebugger(self))
            .finish()
    }
}

impl<T> BoundedQueue for Elastic<T> {}

struct DataDebugger<'q, T>(&'q Elastic<T>);

impl<T: fmt::Debug> fmt::Debug for DataDebugger<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut list = f.debug_list();

        for item in self.0.buffer.iter().take(self.0.amount) {
            list.entry(item);
        }

        list.finish()
    }
}

#[cfg(test)]
mod tests {
    extern crate alloc;
    use super::*;
    use crate::queues::QueueExt;
    use alloc::format;

    #[test]
    fn enqueues_and_dequeues_with_correct_amount() {
        let mut queue: Elastic<u8> = Elastic::new(1, 5, Default::default);
        assert_eq!(queue.enqueue(2), None);
        assert_eq!(queue.enqueue(3), None);
        assert_eq!(queue.enqueue(5), None);
        assert_eq!(queue.enqueue(7), None);
        assert_eq!(queue.len(), 4);

        assert_eq!(queue.enqueue(11), None);
        assert_eq!(queue.len(), 5);
        assert_eq!(queue.enqueue(13), Some(13));

        assert_eq!(queue.dequeue(), Some(2));
        assert_eq!(queue.len(), 4);

        assert_eq!(queue.enqueue(13), None);
    }

    #[test]
    fn returns_none_on_dequeue_when_queue_is_empty() {
        let mut queue: Elastic<u8> = Elastic::new(1, 5, Default::default);

        queue.enqueue(2);
        queue.dequeue();

        assert!(queue.dequeue().is_none());
    }

    #[test]
    fn bulk_enqueues_and_dequeues_with_correct_amount() {
        pollster::block_on(async {
            let mut queue: Elastic<u8> = Elastic::new(1, 7, Default::default);
            let mut buf = [0; 8];
            let enqueue_amount = queue.bulk_enqueue(b"ufotofu").await;
            let dequeue_amount = queue.bulk_dequeue(&mut buf).await;
            assert_eq!(enqueue_amount, dequeue_amount);
        })
    }

    #[test]
    fn test_debug_impl() {
        let mut queue: Elastic<u8> = Elastic::new(1, 8, Default::default);
        assert_eq!(queue.enqueue(2), None);
        assert_eq!(queue.enqueue(3), None);
        assert_eq!(queue.enqueue(5), None);
        assert_eq!(
            format!("{queue:?}"),
            "Elastic { minimum_capacity: 1, maximum_capacity: 8, len: 3, data: [2, 3, 5] }"
        );

        assert_eq!(queue.dequeue(), Some(2));
        assert_eq!(
            format!("{queue:?}"),
            "Elastic { minimum_capacity: 1, maximum_capacity: 8, len: 2, data: [3, 5] }"
        );

        assert_eq!(queue.dequeue(), Some(3));
        assert_eq!(
            format!("{queue:?}"),
            "Elastic { minimum_capacity: 1, maximum_capacity: 8, len: 1, data: [5] }"
        );

        assert_eq!(queue.enqueue(7), None);
        assert_eq!(
            format!("{queue:?}"),
            "Elastic { minimum_capacity: 1, maximum_capacity: 8, len: 2, data: [5, 7] }"
        );

        assert_eq!(queue.enqueue(11), None);
        assert_eq!(queue.enqueue(13), None);
        assert_eq!(queue.enqueue(17), None);
        assert_eq!(
            format!("{queue:?}"),
            "Elastic { minimum_capacity: 1, maximum_capacity: 8, len: 5, data: [5, 7, 11, 13, 17] }"
        );
    }
}