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> Deref for SortedBuffer<T> {
89    type Target = [T];
90
91    fn deref(&self) -> &Self::Target {
92        &self.inner
93    }
94}
95
96impl<T> FromIterator<T> for SortedBuffer<T>
97where
98    T: Ord,
99{
100    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
101        let mut buffer = SortedBuffer::<T>::new();
102        SortedBuffer::set_sorted_unique(&mut buffer, iter);
103        buffer
104    }
105}
106
107impl<T, I> From<I> for SortedBuffer<T>
108where
109    I: IntoIterator<Item = T>,
110    T: Ord,
111{
112    fn from(iter: I) -> Self {
113        let mut buffer = SortedBuffer::<T>::new();
114        SortedBuffer::set_sorted_unique(&mut buffer, iter);
115        buffer
116    }
117}
118
119impl<T> Debug for SortedBuffer<T>
120where
121    T: Debug,
122{
123    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
124        write!(f, "{:?}", self.inner.as_slice())?;
125        return Ok(());
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132
133    #[test]
134    fn test_sorted_buffer_insert_remove() {
135        let mut buffer = SortedBuffer::new();
136        SortedBuffer::insert_sorted_unique(&mut buffer, 5);
137        SortedBuffer::insert_sorted_unique(&mut buffer, 3);
138        SortedBuffer::insert_sorted_unique(&mut buffer, 8);
139        SortedBuffer::insert_sorted_unique(&mut buffer, 5); // Duplicate, should not be added
140
141        assert_eq!(&*buffer, &[3, 5, 8]);
142
143        SortedBuffer::remove_sorted(&mut buffer, &5);
144        assert_eq!(&*buffer, &[3, 8]);
145
146        SortedBuffer::remove_sorted(&mut buffer, &10); // Not present, should do nothing
147        assert_eq!(&*buffer, &[3, 8]);
148    }
149
150    #[test]
151    fn test_sorted_buffer_from_iter() {
152        let vec = vec![4, 2, 7, 2, 5];
153        let buffer: SortedBuffer<i32> = vec.into_iter().collect();
154        assert_eq!(&*buffer, &[2, 4, 5, 7]);
155    }
156}
radiate_utils/buff/sorted.rs

radiate_utils/buff/
sorted.rs
