opening_hours_syntax/
sorted_vec.rs

1use alloc::vec::Vec;
2use core::borrow::Borrow;
3use core::cmp::Ordering;
4use core::convert::From;
5use core::ops::Deref;
6
7/// A wrapper arround a [`Vec`] that is always sorted and with values repeating
8/// at most once.
9///
10/// ```
11/// use opening_hours_syntax::sorted_vec::UniqueSortedVec;
12///
13/// let sorted: UniqueSortedVec<_> = vec![2, 1, 3, 5, 3].into();
14/// assert_eq!(sorted.as_slice(), &[1, 2, 3, 5]);
15/// ```
16#[repr(transparent)]
17#[derive(Clone, Debug, Default, Hash, Eq, PartialEq, PartialOrd, Ord)]
18pub struct UniqueSortedVec<T>(Vec<T>);
19
20impl<T> UniqueSortedVec<T> {
21    /// Create a new empty instance.
22    #[inline]
23    pub const fn new() -> Self {
24        Self(Vec::new())
25    }
26}
27
28impl<T: Ord> UniqueSortedVec<T> {
29    /// Build a new [`UniqueSortedVec`] with borrowed content. The order is
30    /// assumed to be equivalent for borrowed content.
31    ///
32    /// ```
33    /// use opening_hours_syntax::sorted_vec::UniqueSortedVec;
34    ///
35    /// let sorted: UniqueSortedVec<_> = vec!["Hello".to_string(), "Anaïs".to_string()].into();
36    /// let sorted_ref: UniqueSortedVec<&str> = sorted.to_ref();
37    /// assert_eq!(sorted_ref.as_slice(), &["Anaïs", "Hello"]);
38    /// ```
39    #[inline]
40    pub fn to_ref<U: Ord + ?Sized>(&self) -> UniqueSortedVec<&U>
41    where
42        T: Borrow<U>,
43    {
44        UniqueSortedVec(self.0.iter().map(Borrow::borrow).collect())
45    }
46
47    /// Merge values of two [`UniqueSortedVec`] while preserving the invariants.
48    ///
49    /// ```
50    /// use opening_hours_syntax::sorted_vec::UniqueSortedVec;
51    ///
52    /// let sorted_1: UniqueSortedVec<_> = vec![1, 2, 3].into();
53    /// let sorted_2: UniqueSortedVec<_> = vec![0, 3, 4].into();
54    /// assert_eq!(sorted_1.union(sorted_2).as_slice(), &[0, 1, 2, 3, 4]);
55    /// ```
56    #[inline]
57    pub fn union(mut self, mut other: Self) -> Self {
58        match (self.as_slice(), other.as_slice()) {
59            (_, []) => self,
60            ([], _) => other,
61            ([.., tail_x], [head_y, ..]) if tail_x < head_y => {
62                self.0.extend(other.0);
63                self
64            }
65            ([head_x, ..], [.., tail_y]) if tail_y < head_x => {
66                other.0.extend(self.0);
67                other
68            }
69            ([.., tail_x], [.., tail_y]) => {
70                let last = match tail_x.cmp(tail_y) {
71                    Ordering::Greater => self.0.pop().unwrap(), // move `tail_x` out
72                    Ordering::Less => other.0.pop().unwrap(),   // move `tail_y` out
73                    Ordering::Equal => {
74                        other.0.pop().unwrap(); // move `tail_x` out
75                        self.0.pop().unwrap() // move `tail_y` out
76                    }
77                };
78
79                let mut new_head = self.union(other);
80                new_head.0.push(last);
81                new_head
82            }
83        }
84    }
85
86    /// Returns true if the slice contains an element with the given value.
87    ///
88    /// ```
89    /// use opening_hours_syntax::sorted_vec::UniqueSortedVec;
90    ///
91    /// let sorted: UniqueSortedVec<_> = vec![10, 40, 30].into();
92    /// assert!(sorted.contains(&30));
93    /// assert!(!sorted.contains(&50));
94    /// ```
95    #[inline]
96    pub fn contains(&self, x: &T) -> bool {
97        self.0.binary_search(x).is_ok()
98    }
99
100    /// Search for the given value in the slice return a reference to it or the
101    /// next greater value if it is not found.
102    ///
103    /// ```
104    /// use opening_hours_syntax::sorted_vec::UniqueSortedVec;
105    ///
106    /// let sorted: UniqueSortedVec<_> = vec![10, 40, 30].into();
107    /// assert_eq!(sorted.find_first_following(&30), Some(&30));
108    /// assert_eq!(sorted.find_first_following(&31), Some(&40));
109    /// assert_eq!(sorted.find_first_following(&50), None);
110    /// ```
111    #[inline]
112    pub fn find_first_following(&self, x: &T) -> Option<&T> {
113        let (Ok(i) | Err(i)) = self.0.binary_search(x);
114        self.0.get(i)
115    }
116}
117
118impl<T: Ord> From<Vec<T>> for UniqueSortedVec<T> {
119    #[inline]
120    fn from(mut vec: Vec<T>) -> Self {
121        vec.sort_unstable();
122        vec.dedup();
123        Self(vec)
124    }
125}
126
127impl<T: Ord> From<UniqueSortedVec<T>> for Vec<T> {
128    #[inline]
129    fn from(val: UniqueSortedVec<T>) -> Self {
130        val.0
131    }
132}
133
134impl<T: Ord> Deref for UniqueSortedVec<T> {
135    type Target = Vec<T>;
136
137    #[inline]
138    fn deref(&self) -> &Self::Target {
139        &self.0
140    }
141}
opening_hours_syntax/sorted_vec.rs

opening_hours_syntax/
sorted_vec.rs
