registorder_map/
lib.rs

1#[cfg(feature = "serde")]
2use serde::de::{Deserialize, Deserializer, MapAccess, Visitor};
3#[cfg(feature = "serde")]
4use serde::ser::{Serialize, SerializeMap, Serializer};
5#[cfg(feature = "serde")]
6use std::marker::PhantomData;
7
8#[derive(Clone)]
9struct Entry<K, V> {
10    key: K,
11    val: V,
12}
13
14/// An `RegistOrderMap` is like a `std::collections::HashMap`,
15/// but it is sorted according to the key in descending order.
16/// The `RegistOrderMap` is a `HashMap` with guaranteed registration order.
17/// I have only implemented the minimum required methods, so please request them if you have any requests.
18#[derive(Clone)]
19pub struct RegistOrderMap<K, V> {
20    entries: Vec<Entry<K, V>>,
21}
22
23impl<K, V> RegistOrderMap<K, V> {
24    /// Creates an empty RegistOrderMap.
25    pub fn new() -> Self {
26        Default::default()
27    }
28    fn find(&self, k: &K) -> Option<usize>
29    where
30        K: Eq,
31    {
32        self.entries.iter().position(|e| e.key == *k)
33    }
34    /// Returns a ref2erence to the value corresponding to the key.
35    pub fn get(&self, k: &K) -> Option<&V>
36    where
37        K: Eq,
38    {
39        match self.find(k) {
40            Some(i) => Some(&self.entries[i].val),
41            None => None,
42        }
43    }
44    /// Inserts a key-value pair into the map.
45    pub fn insert(&mut self, k: K, v: V)
46    where
47        K: Eq,
48    {
49        match self.find(&k) {
50            None => self.entries.push(Entry { key: k, val: v }),
51            Some(i) => self.entries[i].val = v,
52        }
53    }
54    /// Returns true if the map contains no elements.
55    #[inline]
56    pub fn is_empty(&self) -> bool {
57        self.entries.is_empty()
58    }
59    /// An iterator visiting all key-value pairs in arbitrary order. The iterator element type is `(&'a K, &'a V)`.
60    #[inline]
61    pub fn iter(&self) -> Iter<'_, K, V> {
62        Iter {
63            inner: self.entries.iter(),
64        }
65    }
66    /// Returns the number of elements in the map.
67    #[inline]
68    pub fn len(&self) -> usize {
69        self.entries.len()
70    }
71    /// Creates an empty `RegistOrderMap` with at least the specified capacity.
72    #[inline]
73    pub fn with_capacity(capacity: usize) -> Self {
74        Self {
75            entries: Vec::with_capacity(capacity),
76        }
77    }
78}
79
80impl<K, V> Default for RegistOrderMap<K, V> {
81    fn default() -> Self {
82        Self {
83            entries: Vec::new(),
84        }
85    }
86}
87
88impl<K, V, const N: usize> From<[(K, V); N]> for RegistOrderMap<K, V>
89where
90    K: Eq + Copy,
91    V: Copy,
92{
93    fn from(arr: [(K, V); N]) -> Self {
94        Self {
95            entries: arr.iter().map(|e| Entry { key: e.0, val: e.1 }).collect(),
96        }
97    }
98}
99
100impl<K: std::fmt::Debug, V: std::fmt::Debug> std::fmt::Debug for Entry<K, V> {
101    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
102        f.debug_struct("Entry")
103            .field("key", &self.key)
104            .field("val", &self.val)
105            .finish()
106    }
107}
108
109impl<K: std::fmt::Debug, V: std::fmt::Debug> std::fmt::Debug for RegistOrderMap<K, V> {
110    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
111        f.debug_list()
112            .entries(self.entries.iter())
113            .finish()
114    }
115}
116
117pub struct Iter<'a, K: 'a, V: 'a> {
118    inner: std::slice::Iter<'a, Entry<K, V>>,
119}
120
121impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V>
122where
123    K: Eq,
124{
125    type Item = (&'a K, &'a V);
126
127    fn next(&mut self) -> Option<Self::Item> {
128        match self.inner.next() {
129            None => None,
130            Some(entry) => Some((&entry.key, &entry.val)),
131        }
132    }
133}
134
135#[cfg(feature = "serde")]
136impl<K, V> Serialize for RegistOrderMap<K, V>
137where
138    K: Serialize + Eq,
139    V: Serialize,
140{
141    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
142    where
143        S: Serializer,
144    {
145        let mut map = serializer.serialize_map(Some(self.len()))?;
146        for (k, v) in self.iter() {
147            map.serialize_entry(k, v)?;
148        }
149        map.end()
150    }
151}
152
153#[cfg(feature = "serde")]
154struct RegistOrderMapVisitor<K, V> {
155    marker: PhantomData<fn() -> RegistOrderMap<K, V>>,
156}
157
158#[cfg(feature = "serde")]
159impl<K, V> RegistOrderMapVisitor<K, V> {
160    fn new() -> Self {
161        Self {
162            marker: PhantomData,
163        }
164    }
165}
166
167#[cfg(feature = "serde")]
168impl<'de, K, V> Visitor<'de> for RegistOrderMapVisitor<K, V>
169where
170    K: Deserialize<'de> + Eq,
171    V: Deserialize<'de>,
172{
173    type Value = RegistOrderMap<K, V>;
174
175    fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
176        formatter.write_str("a very special map")
177    }
178
179    fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
180    where
181        M: MapAccess<'de>,
182    {
183        let mut map = RegistOrderMap::with_capacity(access.size_hint().unwrap_or(0));
184
185        while let Some((key, value)) = access.next_entry()? {
186            map.insert(key, value);
187        }
188
189        Ok(map)
190    }
191}
192
193#[cfg(feature = "serde")]
194impl<'de, K, V> Deserialize<'de> for RegistOrderMap<K, V>
195where
196    K: Deserialize<'de> + Eq,
197    V: Deserialize<'de>,
198{
199    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
200    where
201        D: Deserializer<'de>,
202    {
203        // Instantiate our Visitor and ask the Deserializer to drive
204        // it over the input data, resulting in an instance of MyMap.
205        deserializer.deserialize_map(RegistOrderMapVisitor::new())
206    }
207
208}
209
210#[cfg(test)]
211mod tests {
212    use super::*;
213    #[cfg(feature = "serde")]
214    use serde_json;
215
216    #[test]
217    fn test_insert() {
218        let key1 = "key1".to_string();
219        let key2 = "key2".to_string();
220        let mut map = RegistOrderMap::new();
221        map.insert(key2.clone(), 20);
222        assert_eq!(map.get(&key1), None);
223        assert_eq!(map.get(&key2), Some(&20));
224        map.insert(key1.clone(), 10);
225        assert_eq!(map.get(&key1), Some(&10));
226        assert_eq!(map.get(&key2), Some(&20));
227    }
228
229    #[test]
230    fn test_iter() {
231        let key1 = "key1".to_string();
232        let key2 = "key2".to_string();
233        let mut map = RegistOrderMap::new();
234        map.insert(key2.clone(), 20);
235        map.insert(key1.clone(), 10);
236        let mut iter = map.iter();
237        assert_eq!(iter.next(), Some((&key2, &20)));
238        assert_eq!(iter.next(), Some((&key1, &10)));
239    }
240
241    #[test]
242    fn test_from() {
243        let map = RegistOrderMap::from([("key2", 20), ("key1", 10)]);
244        let mut iter = map.iter();
245        assert_eq!(iter.next(), Some((&"key2", &20)));
246        assert_eq!(iter.next(), Some((&"key1", &10)));
247    }
248
249    #[test]
250    fn test_debug() {
251        let key1 = "key1".to_string();
252        let key2 = "key2".to_string();
253        let mut map = RegistOrderMap::new();
254        map.insert(key2.clone(), 20);
255        map.insert(key1.clone(), 10);
256        assert_eq!(
257            format!("{:?}", map),
258            r#"[Entry { key: "key2", val: 20 }, Entry { key: "key1", val: 10 }]"#
259        );
260    }
261
262    #[cfg(feature = "serde")]
263    #[test]
264    fn test_serialize() {
265        let key1 = "key1".to_string();
266        let key2 = "key2".to_string();
267        let mut map = RegistOrderMap::new();
268        map.insert(key2.clone(), 20);
269        map.insert(key1.clone(), 10);
270        let json_str: &str = &serde_json::to_string(&map).unwrap();
271        assert_eq!(json_str, r#"{"key2":20,"key1":10}"#);
272    }
273
274    #[cfg(feature = "serde")]
275    #[test]
276    fn test_deserialize() {
277        let key1 = "key1".to_string();
278        let key2 = "key2".to_string();
279        let json_str = r#"{"key2":20,"key1":10}"#;
280        let map: RegistOrderMap<String, i64> = serde_json::from_str(json_str).unwrap();
281        let mut iter = map.iter();
282        assert_eq!(iter.next(), Some((&key2, &20)));
283        assert_eq!(iter.next(), Some((&key1, &10)));
284    }
285}
registorder_map/lib.rs

registorder_map/
lib.rs
