radiate_utils/buff/
sorted.rs

1#[cfg(feature = "serde")]
2use serde::{Deserialize, Serialize};
3use smallvec::SmallVec;
4use std::{fmt::Debug, ops::Deref};
5
6pub type InnerBuff<T> = SmallVec<[T; 8]>;
7
8#[derive(Clone, PartialEq, Eq)]
9#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
10#[repr(transparent)]
11pub struct SortedBuffer<T> {
12    inner: InnerBuff<T>,
13}
14
15impl<T> SortedBuffer<T> {
16    pub fn new() -> Self {
17        SortedBuffer {
18            inner: InnerBuff::<T>::new(),
19        }
20    }
21
22    #[inline]
23    pub fn len(&self) -> usize {
24        self.inner.len()
25    }
26
27    #[inline]
28    pub fn is_empty(&self) -> bool {
29        self.inner.is_empty()
30    }
31
32    #[inline]
33    pub fn as_slice(&self) -> &[T] {
34        &self.inner
35    }
36
37    #[inline]
38    pub fn as_mut_slice(&mut self) -> &mut [T] {
39        &mut self.inner
40    }
41
42    #[inline]
43    pub fn contains(&self, value: &T) -> bool
44    where
45        T: Ord,
46    {
47        self.inner.binary_search(value).is_ok()
48    }
49
50    #[inline]
51    pub fn iter(&self) -> std::slice::Iter<'_, T> {
52        self.inner.iter()
53    }
54
55    #[inline]
56    pub fn insert_sorted_unique(v: &mut SortedBuffer<T>, value: T)
57    where
58        T: Ord,
59    {
60        match v.inner.binary_search(&value) {
61            Ok(_) => {}
62            Err(pos) => v.inner.insert(pos, value),
63        }
64    }
65
66    #[inline]
67    pub fn remove_sorted(v: &mut SortedBuffer<T>, value: &T)
68    where
69        T: Ord,
70    {
71        if let Ok(pos) = v.inner.binary_search(value) {
72            v.inner.remove(pos);
73        }
74    }
75
76    #[inline]
77    pub fn set_sorted_unique(dst: &mut SortedBuffer<T>, src: impl IntoIterator<Item = T>)
78    where
79        T: Ord,
80    {
81        dst.inner.clear();
82        dst.inner.extend(src);
83        dst.inner.sort_unstable();
84        dst.inner.dedup();
85    }
86}
87
88impl<T: Default> Default for SortedBuffer<T> {
89    fn default() -> Self {
90        SortedBuffer::new()
91    }
92}
93
94impl<T> Deref for SortedBuffer<T> {
95    type Target = [T];
96
97    fn deref(&self) -> &Self::Target {
98        &self.inner
99    }
100}
101
102impl<T> FromIterator<T> for SortedBuffer<T>
103where
104    T: Ord,
105{
106    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
107        let mut buffer = SortedBuffer::<T>::new();
108        SortedBuffer::set_sorted_unique(&mut buffer, iter);
109        buffer
110    }
111}
112
113impl<T, I> From<I> for SortedBuffer<T>
114where
115    I: IntoIterator<Item = T>,
116    T: Ord,
117{
118    fn from(iter: I) -> Self {
119        let mut buffer = SortedBuffer::<T>::new();
120        SortedBuffer::set_sorted_unique(&mut buffer, iter);
121        buffer
122    }
123}
124
125impl<T> Debug for SortedBuffer<T>
126where
127    T: Debug,
128{
129    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
130        write!(f, "{:?}", self.inner.as_slice())?;
131        Ok(())
132    }
133}
134
135#[cfg(test)]
136mod tests {
137    use super::*;
138
139    #[test]
140    fn test_sorted_buffer_insert_remove() {
141        let mut buffer = SortedBuffer::new();
142        SortedBuffer::insert_sorted_unique(&mut buffer, 5);
143        SortedBuffer::insert_sorted_unique(&mut buffer, 3);
144        SortedBuffer::insert_sorted_unique(&mut buffer, 8);
145        SortedBuffer::insert_sorted_unique(&mut buffer, 5); // Duplicate, should not be added
146
147        assert_eq!(&*buffer, &[3, 5, 8]);
148
149        SortedBuffer::remove_sorted(&mut buffer, &5);
150        assert_eq!(&*buffer, &[3, 8]);
151
152        SortedBuffer::remove_sorted(&mut buffer, &10); // Not present, should do nothing
153        assert_eq!(&*buffer, &[3, 8]);
154    }
155
156    #[test]
157    fn test_sorted_buffer_from_iter() {
158        let vec = vec![4, 2, 7, 2, 5];
159        let buffer: SortedBuffer<i32> = vec.into_iter().collect();
160        assert_eq!(&*buffer, &[2, 4, 5, 7]);
161    }
162}
radiate_utils/buff/sorted.rs

radiate_utils/buff/
sorted.rs
