1use std::borrow::Borrow;
6use std::cmp::Ordering;
7use std::fmt::Debug;
8use std::marker::PhantomData;
9use std::{iter, slice};
10
11#[derive(Eq, PartialEq, PartialOrd, Ord, Hash, Clone, Default)]
16pub struct SortedVecMap<K, V> {
17 vec: Vec<(K, V)>,
18}
19
20impl<K, V> SortedVecMap<K, V> {
21 pub fn new() -> Self {
23 Self { vec: Vec::new() }
24 }
25
26 pub fn is_empty(&self) -> bool {
28 self.vec.is_empty()
29 }
30
31 pub fn get<Q>(&self, key: &Q) -> Option<&V>
33 where
34 K: Borrow<Q> + Ord,
35 Q: Ord + ?Sized,
36 {
37 if let Ok(index) = self.index_of(key) {
38 Some(&self.vec[index].1)
39 } else {
40 None
41 }
42 }
43
44 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
46 where
47 K: Borrow<Q> + Ord,
48 Q: Ord + ?Sized,
49 {
50 if let Ok(index) = self.index_of(key) {
51 Some(&mut self.vec[index].1)
52 } else {
53 None
54 }
55 }
56
57 pub fn insert(&mut self, key: K, value: V) -> Option<V>
61 where
62 K: Ord,
63 {
64 match self.index_of(&key) {
65 Ok(index) => {
66 let old = std::mem::replace(&mut self.vec[index], (key, value));
67 Some(old.1)
68 }
69 Err(index) => {
70 self.vec.insert(index, (key, value));
71 None
72 }
73 }
74 }
75
76 pub fn iter(&self) -> Iter<'_, K, V> {
78 self.vec.iter().map(|entry| (&entry.0, &entry.1))
79 }
80
81 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
83 self.vec.iter_mut().map(|entry| (&entry.0, &mut entry.1))
84 }
85
86 pub fn keys(&self) -> Keys<'_, K, V> {
88 self.vec.iter().map(|e| &e.0)
89 }
90
91 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
93 self.vec.iter_mut().map(|e| &mut e.1)
94 }
95
96 fn index_of<Q>(&self, key: &Q) -> Result<usize, usize>
102 where
103 K: Borrow<Q> + Ord,
104 Q: Ord + ?Sized,
105 {
106 self.vec.binary_search_by(|probe| probe.0.borrow().cmp(key))
107 }
108}
109
110impl<K: Debug, V: Debug> Debug for SortedVecMap<K, V> {
111 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
112 f.debug_map().entries(self.iter()).finish()
113 }
114}
115
116pub type Iter<'a, K, V> = iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> (&K, &V)>;
117pub type IterMut<'a, K, V> = iter::Map<slice::IterMut<'a, (K, V)>, fn(&mut (K, V)) -> (&K, &mut V)>;
118pub type Keys<'a, K, V> = iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> &K>;
119pub type ValuesMut<'a, K, V> = iter::Map<slice::IterMut<'a, (K, V)>, fn(&mut (K, V)) -> &mut V>;
120
121impl<K: Ord, V> FromIterator<(K, V)> for SortedVecMap<K, V> {
122 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
123 let mut vec = Vec::from_iter(iter);
124 vec.shrink_to_fit();
125 vec.sort_by(sort_comparator);
126 vec.dedup_by(dedup_comparator);
127 Self { vec }
128 }
129}
130
131impl<'de, K, V> serde::Deserialize<'de> for SortedVecMap<K, V>
132where
133 K: Ord + serde::Deserialize<'de>,
134 V: serde::Deserialize<'de>,
135{
136 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
137 where
138 D: serde::Deserializer<'de>,
139 {
140 struct Visitor<K, V> {
141 _map_type: PhantomData<SortedVecMap<K, V>>,
142 }
143 impl<'de, K, V> serde::de::Visitor<'de> for Visitor<K, V>
144 where
145 K: Ord + serde::Deserialize<'de>,
146 V: serde::Deserialize<'de>,
147 {
148 type Value = SortedVecMap<K, V>;
149 fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
150 formatter.write_str("a map")
151 }
152 fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
153 where
154 A: serde::de::MapAccess<'de>,
155 {
156 let mut vec: Vec<(K, V)> = match map.size_hint() {
157 Some(hint) => Vec::with_capacity(hint),
158 None => Vec::new(),
159 };
160 let mut is_sorted_and_deduped = true;
161 while let Some(entry) = map.next_entry()? {
162 if is_sorted_and_deduped {
163 if let Some(back) = vec.last() {
164 is_sorted_and_deduped = back.0.cmp(&entry.0) == Ordering::Less;
165 }
166 }
167 vec.push(entry);
168 }
169 if !is_sorted_and_deduped {
170 vec.sort_by(sort_comparator);
171 vec.dedup_by(dedup_comparator);
172 }
173 vec.shrink_to_fit();
174 Ok(SortedVecMap { vec })
175 }
176 }
177 deserializer.deserialize_map(Visitor { _map_type: PhantomData })
178 }
179}
180
181impl<K: serde::Serialize, V: serde::Serialize> serde::Serialize for SortedVecMap<K, V> {
182 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
183 where
184 S: serde::Serializer,
185 {
186 serializer.collect_map(self.iter())
187 }
188}
189
190fn sort_comparator<K: Ord, V>(a: &(K, V), b: &(K, V)) -> Ordering {
191 a.0.cmp(&b.0)
192}
193
194fn dedup_comparator<K: Ord, V>(a: &mut (K, V), b: &mut (K, V)) -> bool {
195 a.0 == b.0
196}
197
198#[cfg(test)]
199mod tests {
200 use super::*;
201 use std::collections::BTreeMap;
202
203 #[test]
204 fn test_get() {
205 let mut map = SortedVecMap::new();
206 assert!(map.get(&1).is_none());
207
208 map.insert(1, 21);
209 assert_eq!(map.get(&1), Some(&21));
210
211 map.insert(0, 20);
212 assert_eq!(map.get(&0), Some(&20));
213 assert_eq!(map.get(&1), Some(&21));
214
215 map.insert(2, 22);
216 assert_eq!(map.get(&0), Some(&20));
217 assert_eq!(map.get(&1), Some(&21));
218 assert_eq!(map.get(&2), Some(&22));
219 }
220
221 #[test]
222 fn test_insert() {
223 let mut map = SortedVecMap::new();
224 for (k, v) in [(50, 50), (47, 47), (48, 48), (51, 51), (49, 49)] {
225 assert!(map.insert(k, v).is_none());
226 }
227 assert_eq!(map.insert(48, 88), Some(48));
228 assert_eq!(map.vec.as_slice(), &[(47, 47), (48, 88), (49, 49), (50, 50), (51, 51)])
229 }
230
231 #[test]
232 fn test_serialize_deserialize() {
233 let map: SortedVecMap<i32, i32> =
234 [(56, 56), (47, 47), (53, 53), (51, 51), (49, 49)].into_iter().collect();
235 let serialized = bincode::serialize(&map).unwrap();
236 let deserialized: SortedVecMap<i32, i32> = bincode::deserialize(&serialized).unwrap();
237 assert_eq!(map, deserialized);
238 }
239
240 #[test]
241 fn test_deserialize_from_btree_map() {
242 let map: BTreeMap<i32, i32> = [(56, 56), (47, 47), (53, 53), (51, 51), (49, 49)].into();
243 let serialized = bincode::serialize(&map).unwrap();
244 let deserialized: SortedVecMap<i32, i32> = bincode::deserialize(&serialized).unwrap();
245
246 let map_entries: Vec<(i32, i32)> = map.into_iter().collect();
247 assert_eq!(map_entries, deserialized.vec);
248 }
249}