opening_hours_syntax/
sorted_vec.rs

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

opening_hours_syntax/
sorted_vec.rs
