utls 0.12.10

/// Prelude module containing commonly used types and traits
pub mod prelude {
    pub use super::{
        buf::{Buffer, CircularBuffer, PriorityBuffer},
        list::sorted::{DefaultSorts, SortedList},
    };
}
/// Module providing buffer types
pub mod buf {
    use std::{
        error::Error,
        fmt::Display,
        ops::{Index, IndexMut},
    };

    /// Primarily a trait to mark a struct as a buffer
    pub trait Buffer: Sized {
        /// Returns true if the buffer contains no elements
        fn is_empty(&self) -> bool;
        /// Creates a new buffer with the specified capacity.
        ///
        /// # Arguments
        ///
        /// * `capacity` - The fixed size of the buffer
        ///
        /// # Errors
        ///
        /// Returns `BufError::InvalidCapacity` if capacity is 0
        fn new(capacity: usize) -> Result<Self, BufError>;
        /// Clears the buffer, removing all elements
        fn clear(&mut self);
    }

    /// A fixed-size circular buffer implementation.
    ///
    /// This buffer can store a fixed number of elements in a circular fashion,
    /// where new elements overwrite old ones when the buffer is full.
    #[derive(Clone, Debug)]
    pub struct CircularBuffer<T> {
        buffer: Vec<Option<T>>,
        read_pos: usize,
        write_pos: usize,
        size: usize,
    }
    impl<T> CircularBuffer<T> {
        /// Pushes an item to the back of the buffer.
        ///
        /// # Arguments
        ///
        /// * `item` - The item to push
        ///
        /// # Errors
        ///
        /// Returns `BufError::BufFull` if the buffer is full
        pub fn push(&mut self, item: T) -> Result<(), BufError> {
            if self.is_full() {
                return Err(BufError::BufFull(self.size));
            }

            self.buffer[self.write_pos] = Some(item);
            self.write_pos = (self.write_pos + 1) % self.size;
            Ok(())
        }
        /// Removes and returns the first item in the buffer.
        ///
        /// # Returns
        ///
        /// * `Some(T)` - The first item if the buffer is not empty
        /// * `None` - If the buffer is empty
        pub fn pop(&mut self) -> Option<T> {
            if self.is_empty() {
                return None;
            }

            let item = self.buffer[self.read_pos].take();
            self.read_pos = (self.read_pos + 1) % self.size;
            item
        }
        /// Returns a reference to the first item without removing it.
        ///
        /// # Returns
        ///
        /// * `Some(&T)` - Reference to the first item if buffer is not empty
        /// * `None` - If the buffer is empty
        pub fn peek(&self) -> Option<&T> {
            self.buffer.get(self.read_pos).unwrap_or(&None).as_ref()
        }

        /// Checks if the buffer is at full capacity.
        pub fn is_full(&self) -> bool {
            self.available() == self.size
        }

        /// Returns the total capacity of the buffer.
        pub fn capacity(&self) -> usize {
            self.size
        }
        /// Returns the current number of elements in the buffer
        pub fn len(&self) -> usize {
            self.available()
        }
        /// Returns the number of elements currently in the buffer
        pub fn available(&self) -> usize {
            self.buffer.iter().filter(|x| x.is_some()).count() + 1
        }
        /// Returns the amount of free space in the buffer
        pub fn free_space(&self) -> usize {
            self.size - self.available()
        }
        /// Returns an iterator over references to the elements in the buffer.
        pub fn iter(&self) -> impl Iterator<Item = &T> {
            self.buffer.iter().filter_map(|x| x.as_ref())
        }
        /// Returns an iterator over mutable references to elements
        pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
            self.buffer.iter_mut().filter_map(|x| x.as_mut())
        }

        /// Attempts to extend the buffer with elements from an iterator
        pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) -> Result<(), BufError> {
            for item in iter {
                self.push(item)?;
            }
            Ok(())
        }
        /// Gets a reference to the element at the specified index.
        ///
        /// # Arguments
        ///
        /// * `index` - The index of the element to retrieve
        ///
        /// # Returns
        ///
        /// * `Some(&T)` - Reference to the element if index is valid
        /// * `None` - If index is out of bounds
        pub fn get(&self, index: usize) -> Option<&T> {
            if index >= self.len() {
                return None;
            }
            let actual_index = (self.read_pos + index) % self.size;
            self.buffer[actual_index].as_ref()
        }
        /// Overwrites the oldest element in the buffer with a new item.
        ///
        /// If the buffer is full, the read position is adjusted to maintain
        /// the circular nature of the buffer.
        ///
        /// # Arguments
        ///
        /// * `item` - The item to write
        pub fn overwrite(&mut self, item: T) {
            self.buffer[self.write_pos] = Some(item);
            self.write_pos = (self.write_pos + 1) % self.size;
            if self.is_full() {
                self.read_pos = self.write_pos;
            }
        }
        /// Rotates the buffer left by n positions
        pub fn rotate_left(&mut self, n: usize) {
            if self.is_empty() || n == 0 {
                return;
            }
            self.read_pos = (self.read_pos + n) % self.size;
            self.write_pos = (self.write_pos + n) % self.size;
        }

        /// Rotates the buffer right by n positions
        pub fn rotate_right(&mut self, n: usize) {
            if self.is_empty() || n == 0 {
                return;
            }
            self.read_pos = (self.size + self.read_pos - n) % self.size;
            self.write_pos = (self.size + self.write_pos - n) % self.size;
        }

        /// Removes and returns the element at index while preserving order
        pub fn remove(&mut self, index: usize) -> Option<T> {
            if index >= self.available() {
                return None;
            }

            let actual_index = (self.read_pos + index) % self.size;
            let item = self.buffer[actual_index].take();

            // Shift elements
            for i in actual_index..self.write_pos {
                self.buffer[i] = self.buffer[(i + 1) % self.size].take();
            }

            self.write_pos = (self.size + self.write_pos - 1) % self.size;
            item
        }

        /// Splits the buffer at the specified index
        pub fn split_at(&self, mid: usize) -> Option<(CircularBuffer<T>, CircularBuffer<T>)>
        where
            T: Clone,
        {
            if mid > self.len() {
                return None;
            }

            let mut first = CircularBuffer::new(mid).ok()?;
            let mut second = CircularBuffer::new(self.len() - mid).ok()?;

            for (i, item) in self.iter().enumerate() {
                if i < mid {
                    first.push(item.clone()).ok()?;
                } else {
                    second.push(item.clone()).ok()?;
                }
            }

            Some((first, second))
        }
    }

    impl<T: Clone> CircularBuffer<T> {
        /// Returns two vectors containing the buffer's contents
        /// The first vector contains elements from read_pos to the end
        /// The second vector contains any remaining elements from start to write_pos
        pub fn as_slices(&self) -> (Vec<T>, Vec<T>) {
            if self.is_empty() {
                return (Vec::new(), Vec::new());
            }

            let buf: Vec<T> = self.iter().cloned().collect();

            if self.write_pos <= self.read_pos {
                // Data wraps around
                // First slice: from read_pos to end
                // Second slice: from start to write_pos
                (
                    buf[self.read_pos..].to_vec(),
                    buf[..self.write_pos].to_vec(),
                )
            } else {
                // Data is contiguous
                // First slice: from read_pos to write_pos
                // Second slice: empty
                (buf[self.read_pos..self.write_pos].to_vec(), Vec::new())
            }
        }

        /// Resizes the buffer to a new capacity
        pub fn resize(&mut self, new_capacity: usize) -> Result<(), BufError> {
            if new_capacity == 0 {
                return Err(BufError::InvalidCapacity);
            }

            let mut new_buffer: Vec<Option<T>> =
                Vec::with_capacity(new_capacity).iter().cloned().collect();
            new_buffer.resize_with(new_capacity, || None);

            // Transfer existing elements
            for (i, item) in self.iter().enumerate() {
                if i < new_capacity {
                    new_buffer[i] = Some(item.clone());
                }
            }

            self.buffer = new_buffer;
            self.size = new_capacity;
            self.read_pos = 0;
            self.write_pos = self.len().min(new_capacity);

            Ok(())
        }
    }

    impl<T> Buffer for CircularBuffer<T> {
        fn is_empty(&self) -> bool {
            self.available() == 0
        }
        fn new(capacity: usize) -> Result<Self, BufError> {
            if capacity == 0 {
                return Err(BufError::InvalidCapacity);
            }

            let mut buffer = Vec::with_capacity(capacity);
            buffer.resize_with(capacity, || None);
            Ok(Self {
                buffer,
                read_pos: 0,
                write_pos: 0,
                size: capacity,
            })
        }
        fn clear(&mut self) {
            self.buffer.clear();
            self.read_pos = 0;
            self.write_pos = 0;
        }
    }

    impl<T> IntoIterator for CircularBuffer<T> {
        type Item = T;
        type IntoIter = std::vec::IntoIter<T>;

        fn into_iter(self) -> Self::IntoIter {
            self.buffer
                .into_iter()
                .filter_map(|x| x)
                .collect::<Vec<_>>()
                .into_iter()
        }
    }

    impl<T> FromIterator<T> for CircularBuffer<T> {
        fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
            let iter = iter.into_iter();
            let (lower, _) = iter.size_hint();
            let mut buffer =
                CircularBuffer::new(lower.max(16)).expect("Failed to create buffer from iterator");

            for item in iter {
                buffer.push(item).ok();
            }
            buffer
        }
    }

    impl<T> Index<usize> for CircularBuffer<T> {
        type Output = Option<T>;
        fn index(&self, index: usize) -> &Self::Output {
            &self.buffer[index]
        }
    }

    impl<T> IndexMut<usize> for CircularBuffer<T> {
        fn index_mut(&mut self, index: usize) -> &mut Self::Output {
            &mut self.buffer[index]
        }
    }

    /// A buffer that maintains elements in priority order
    #[derive(Clone, Debug)]
    pub struct PriorityBuffer<T: Clone, P: Ord + Clone> {
        buffer: Vec<(T, P)>,
    }

    impl<T: Clone, P: Ord + Clone> PriorityBuffer<T, P> {
        /// Adds an item with the specified priority to the buffer
        pub fn push(&mut self, item: T, priority: P) -> Result<(), BufError> {
            self.buffer.push((item, priority));
            // Sort buffer contents by priority
            let mut contents: Vec<_> = self.buffer.iter().cloned().collect();
            contents.sort_by(|a, b| b.1.cmp(&a.1));

            self.buffer.clear();
            for item in contents {
                self.buffer.push(item);
            }
            Ok(())
        }

        /// Removes and returns the highest priority item from the buffer
        pub fn pop(&mut self) -> Option<T> {
            self.buffer.pop().map(|(item, _)| item)
        }

        /// Returns a reference to the highest priority item without removing it
        pub fn peek(&self) -> Option<&T> {
            self.buffer.last().map(|(item, _)| item)
        }

        /// Returns the current number of elements in the buffer
        pub fn len(&self) -> usize {
            self.buffer.len()
        }

        /// Returns an iterator over the items in priority order
        pub fn iter(&self) -> impl Iterator<Item = &T> {
            self.buffer.iter().map(|(item, _)| item)
        }

        /// Returns the priority of the next item to be popped
        pub fn peek_priority(&self) -> Option<&P> {
            self.buffer.last().map(|(_, priority)| priority)
        }

        /// Removes all elements with the specified priority
        pub fn remove_priority(&mut self, priority: &P) {
            self.buffer.retain(|(_, p)| p != priority);
        }

        /// Retains all elements with a priority matching the specified condition
        pub fn retain_priority<F: FnMut(&(T, P)) -> bool>(&mut self, f: F) {
            self.buffer.retain(f);
        }
    }

    impl<T: std::clone::Clone, P: std::cmp::Ord + Clone> Buffer for PriorityBuffer<T, P> {
        fn is_empty(&self) -> bool {
            self.buffer.is_empty()
        }
        fn new(capacity: usize) -> Result<Self, BufError> {
            Ok(Self {
                buffer: Vec::with_capacity(capacity),
            })
        }
        fn clear(&mut self) {
            self.buffer.clear();
        }
    }

    /// Error types for buffer operations
    #[derive(Debug)]
    pub enum BufError {
        /// Buffer is full, contains the capacity
        BufFull(usize),
        /// Attempted to create buffer with invalid capacity
        InvalidCapacity,
        /// Other buffer-related errors with description
        Other(String),
    }

    impl Error for BufError {}

    impl Display for BufError {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            match self {
                Self::BufFull(cap) => write!(f, "Buffer is full. Capacity: {}", cap),
                Self::InvalidCapacity => write!(f, "Requested capacity is invalid"),
                Self::Other(message) => write!(f, "An unknown error occurred: {}", message),
            }
        }
    }

    /// A pool of buffers with automatic resource management
    pub struct BufferPool<T: Buffer> {
        buffers: Vec<T>,
        capacity: usize,
    }

    impl<T: Buffer> BufferPool<T> {
        /// Creates a new buffer pool with the specified number of buffers and capacity per buffer
        pub fn new(num_buffers: usize, buffer_capacity: usize) -> Result<Self, BufError> {
            let mut buffers = Vec::with_capacity(num_buffers);
            for _ in 0..num_buffers {
                buffers.push(T::new(buffer_capacity)?);
            }

            Ok(Self {
                buffers,
                capacity: buffer_capacity,
            })
        }

        /// Returns a reference to an available buffer from the pool, if any
        pub fn get_buffer(&mut self) -> Option<&mut T> {
            self.buffers.iter_mut().find(|buf| buf.is_empty())
        }

        /// Returns a buffer to the pool if there is capacity available
        pub fn return_buffer(&mut self, buffer: T) -> Result<(), BufError> {
            if self.buffers.len() < self.capacity {
                self.buffers.push(buffer);
                Ok(())
            }
            else {
                Err(BufError::BufFull(self.capacity))
            }
        }

        /// Returns the number of available buffers in the pool
        pub fn available_buffers(&self) -> usize {
            self.buffers.iter().filter(|buf| buf.is_empty()).count()
        }

        /// Returns the total number of buffers in the pool
        pub fn total_buffers(&self) -> usize {
            self.buffers.len()
        }

        /// Clears all buffers in the pool
        pub fn clear_all(&mut self) {
            for buffer in &mut self.buffers {
                // Assuming Buffer trait had clear method, you might need to add it
                buffer.clear();
            }
        }

        /// Removes and returns a buffer from the pool if available
        pub fn take_buffer(&mut self) -> Option<T> {
            self.buffers.pop()
        }
    }
}

/// Module providing various list type containers
pub mod list {
    /// Module for sorting containers
    pub mod sorted {
        use std::{
            ops::{Index, IndexMut},
            random,
        };

        /// A list that maintains its elements in sorted order according to a provided sorting function
        pub struct SortedList<T> {
            /// The value contained within
            pub list: Vec<T>,
            sort: Box<dyn Fn(&[T]) -> Vec<T>>,
        }

        impl<T> SortedList<T> {
            /// Creates a new SortedList with the specified sorting function
            pub fn new(sort_function: impl Fn(&[T]) -> Vec<T> + 'static) -> Self {
                Self {
                    list: Vec::new(),
                    sort: Box::new(sort_function),
                }
            }
            /// Adds an item to the list and sorts it according to the sorting function
            pub fn push(&mut self, item: T) {
                self.list.push(item);
                self.list = (self.sort)(&self.list);
            }
            /// Removes and returns the last element from the list, then re-sorts
            pub fn pop(&mut self) -> Option<T> {
                let out = self.list.pop();
                self.list = (self.sort)(&self.list);
                out
            }
            /// Adds an item to the list without sorting
            pub fn push_no_sort(&mut self, item: T) {
                self.list.push(item);
            }
            /// Removes and returns the last element from the list without sorting
            pub fn pop_no_sort(&mut self) -> Option<T> {
                self.list.pop()
            }
            /// Manually triggers a sort of the list
            pub fn man_sort(&mut self) {
                self.list = (self.sort)(&self.list);
            }
            /// Returns a reference to the element at the specified index
            pub fn get(&self, index: usize) -> Option<&T> {
                self.list.get(index)
            }
            /// Changes the sorting function used by the list
            pub fn set_sort(&mut self, sort_function: impl Fn(&[T]) -> Vec<T> + 'static) {
                self.sort = Box::new(sort_function);
            }
            /// Returns the current number of elements in the list
            pub fn len(&self) -> usize {
                self.list.len()
            }

            /// Returns true if the list contains no elements
            pub fn is_empty(&self) -> bool {
                self.list.is_empty()
            }

            /// Returns an iterator over the sorted elements
            pub fn iter(&self) -> impl Iterator<Item = &T> {
                self.list.iter()
            }

            /// Removes all elements from the list
            pub fn clear(&mut self) {
                self.list.clear();
            }

            /// Extends the list with elements from an iterator
            pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
                for item in iter {
                    self.push(item);
                }
            }
        }

        impl<T> Index<usize> for SortedList<T> {
            type Output = T;
            fn index(&self, index: usize) -> &Self::Output {
                &self.list[index]
            }
        }

        impl<T> IndexMut<usize> for SortedList<T> {
            fn index_mut(&mut self, index: usize) -> &mut Self::Output {
                &mut self.list[index]
            }
        }
        /// Provides common sorting functions for use with SortedList
        pub struct DefaultSorts;

        impl DefaultSorts {
            /// Returns a sorting function that sorts elements in descending order
            pub fn descending<T: Ord + Clone>() -> impl Fn(&[T]) -> Vec<T> {
                |slice: &[T]| {
                    let mut vec = slice.to_vec();
                    vec.sort_by(|a, b| b.cmp(a));
                    vec
                }
            }
            /// Returns a sorting function that sorts elements in ascending order
            pub fn ascending<T: Ord + Clone>() -> impl Fn(&[T]) -> Vec<T> {
                |slice: &[T]| {
                    let mut vec = slice.to_vec();
                    vec.sort_by(|a, b| a.cmp(b));
                    vec
                }
            }
            /// Returns a sorting function that randomly shuffles elements
            pub fn random<T: Ord + Clone>() -> impl Fn(&[T]) -> Vec<T> {
                move |slice: &[T]| {
                    let mut vec = slice.to_vec();
                    vec.sort_by(|a, b| {
                        // Get the memory addresses of elements and use them as a source of randomness
                        let addr_a = (a as *const T) as usize;
                        let addr_b = (b as *const T) as usize;

                        // XOR with some prime numbers to distribute values better
                        let mut hash_a = addr_a.wrapping_mul(2654435761);
                        let mut hash_b = addr_b.wrapping_mul(2654435761);

                        hash_a = hash_a
                            .checked_add(random::random::<usize>())
                            .unwrap_or(hash_a);
                        hash_b = hash_b
                            .checked_add(random::random::<usize>())
                            .unwrap_or(hash_b);

                        // Use the difference to determine ordering. Doesn't match < to Less, etc. to increase 'randomness'
                        if hash_a < hash_b {
                            std::cmp::Ordering::Equal
                        } else if hash_a > hash_b {
                            std::cmp::Ordering::Less
                        } else {
                            std::cmp::Ordering::Greater
                        }
                    });
                    vec
                }
            }
        }
    }
}