ds_ext/
lib.rs

1//! This crate repackages standard data structures with additional capabilities,
2//! like fast ordered maps and sets.
3//!
4//! [`OrdHashSet`] uses a [`Vec`] internally for ordering.
5//! [`OrdHashSet`] and [`OrdHashMap`] both implement a `bisect` method
6//! which allows looking up a key by comparison,
7//! potentially avoiding the need for a heap allocation to construct a search key..
8//!
9//! Features:
10//!  - `all`: enables all features
11//!  - `serialize`: enables support for [`serde`](https://docs.rs/serde/).
12//!  - `stream`: enables support for [`destream`](https://docs.rs/destream/).
13//!  - `hash`: enables support for [`async-hash`](https://docs.rs/async-hash/).
14//!
15//!
16//! Example usage:
17//! ```
18//! use ds_ext::*;
19//!
20//! let mut set = OrdHashSet::new();
21//! assert!(set.is_empty());
22//!
23//! set.insert(1);
24//! assert!(set.contains(&1));
25//! assert_eq!(set.len(), 1);
26//!
27//! let mut map = OrdHashMap::from_iter(set.into_iter().map(|i| (i, i)));
28//! assert_eq!(map.len(), 1);
29//!
30//! assert_eq!(map.get(&1), map.bisect(|i| i.partial_cmp(&1)));
31//! ```
32
33#[cfg(feature = "hash")]
34mod hash;
35#[cfg(feature = "serialize")]
36mod serial;
37#[cfg(feature = "stream")]
38mod stream;
39
40pub mod map;
41pub mod queue;
42pub mod set;
43
44pub use map::OrdHashMap;
45pub use queue::LinkedHashMap;
46pub use set::OrdHashSet;
47
48#[cfg(test)]
49mod tests {
50    #[cfg(feature = "serialize")]
51    #[test]
52    fn serde_roundtrip_collections() {
53        use super::*;
54        type MapSetLinked = (
55            OrdHashMap<u32, String>,
56            OrdHashSet<String>,
57            LinkedHashMap<String, u32>,
58        );
59        let mut map = OrdHashMap::new();
60        map.insert(1u32, "one".to_string());
61        map.insert(2, "two".to_string());
62
63        let mut set = OrdHashSet::new();
64        set.insert("a".to_string());
65        set.insert("b".to_string());
66
67        let mut linked = LinkedHashMap::new();
68        linked.insert("k1".to_string(), 10u32);
69        linked.insert("k2".to_string(), 20u32);
70
71        let empty: MapSetLinked = (OrdHashMap::new(), OrdHashSet::new(), LinkedHashMap::new());
72        let single: MapSetLinked = {
73            let mut map = OrdHashMap::new();
74            map.insert(9, "nine".to_string());
75            let mut set = OrdHashSet::new();
76            set.insert("z".to_string());
77            let mut linked = LinkedHashMap::new();
78            linked.insert("only".to_string(), 1u32);
79            (map, set, linked)
80        };
81
82        let encoded = serde_json::to_string(&(map.clone(), set.clone(), linked.clone()))
83            .expect("serialize collections");
84        let decoded: MapSetLinked =
85            serde_json::from_str(&encoded).expect("deserialize collections");
86
87        assert_eq!(decoded.0, map);
88        assert_eq!(decoded.1, set);
89        assert_eq!(decoded.2.len(), linked.len());
90        for (key, value) in linked.iter() {
91            assert_eq!(decoded.2.get(key), Some(value));
92        }
93
94        let empty_encoded = serde_json::to_string(&empty).expect("serialize empty collections");
95        let empty_decoded: MapSetLinked =
96            serde_json::from_str(&empty_encoded).expect("deserialize empty collections");
97        assert!(empty_decoded.0.is_empty());
98        assert!(empty_decoded.1.is_empty());
99        assert!(empty_decoded.2.is_empty());
100
101        let single_encoded = serde_json::to_string(&single).expect("serialize single collections");
102        let single_decoded: MapSetLinked =
103            serde_json::from_str(&single_encoded).expect("deserialize single collections");
104        assert_eq!(single_decoded.0.get(&9).map(|v| v.as_str()), Some("nine"));
105        assert!(single_decoded.1.contains(&"z".to_string()));
106        assert_eq!(single_decoded.2.get(&"only".to_string()), Some(&1));
107    }
108
109    #[cfg(feature = "stream")]
110    #[test]
111    fn stream_roundtrip_collections() {
112        use super::*;
113        type MapSetLinked = (
114            OrdHashMap<u32, String>,
115            OrdHashSet<String>,
116            LinkedHashMap<String, u32>,
117        );
118        let mut map = OrdHashMap::new();
119        map.insert(1u32, "one".to_string());
120        map.insert(2, "two".to_string());
121
122        let mut set = OrdHashSet::new();
123        set.insert("a".to_string());
124        set.insert("b".to_string());
125
126        let mut linked = LinkedHashMap::new();
127        linked.insert("k1".to_string(), 10u32);
128        linked.insert("k2".to_string(), 20u32);
129
130        let empty: MapSetLinked = (OrdHashMap::new(), OrdHashSet::new(), LinkedHashMap::new());
131        let single: MapSetLinked = {
132            let mut map = OrdHashMap::new();
133            map.insert(9, "nine".to_string());
134            let mut set = OrdHashSet::new();
135            set.insert("z".to_string());
136            let mut linked = LinkedHashMap::new();
137            linked.insert("only".to_string(), 1u32);
138            (map, set, linked)
139        };
140
141        let payload = (map.clone(), set.clone(), linked.clone());
142        let stream = tbon::en::encode(&payload).expect("encode tbon payload");
143        let decoded: MapSetLinked =
144            futures::executor::block_on(tbon::de::try_decode((), stream))
145                .expect("decode tbon payload");
146
147        assert_eq!(decoded.0, map);
148        assert_eq!(decoded.1, set);
149        assert_eq!(decoded.2.len(), linked.len());
150        for (key, value) in linked.iter() {
151            assert_eq!(decoded.2.get(key), Some(value));
152        }
153
154        let empty_stream = tbon::en::encode(&empty).expect("encode empty payload");
155        let empty_decoded: MapSetLinked =
156            futures::executor::block_on(tbon::de::try_decode((), empty_stream))
157                .expect("decode empty payload");
158        assert!(empty_decoded.0.is_empty());
159        assert!(empty_decoded.1.is_empty());
160        assert!(empty_decoded.2.is_empty());
161
162        let single_stream = tbon::en::encode(&single).expect("encode single payload");
163        let single_decoded: MapSetLinked =
164            futures::executor::block_on(tbon::de::try_decode((), single_stream))
165                .expect("decode single payload");
166        assert_eq!(single_decoded.0.get(&9).map(|v| v.as_str()), Some("nine"));
167        assert!(single_decoded.1.contains(&"z".to_string()));
168        assert_eq!(single_decoded.2.get(&"only".to_string()), Some(&1));
169    }
170}
ds_ext/lib.rs

ds_ext/
lib.rs
