id_cache/
lib.rs

1///! A crate providing a simple data structure for caching id values.
2///!
3///! See the documentation for the [`IdCache<I, T>`] type for more information.
4use id_collections::{Count, Id, IdVec};
5use std::{borrow::Borrow, collections::HashMap, fmt::Debug, hash::Hash, ops::Index};
6
7/// A cache which generates sequentially-assigned ids for unique values.
8///
9/// # Example
10///
11/// ```
12/// use id_collections::id_type;
13/// use id_cache::IdCache;
14///
15/// #[id_type]
16/// struct WordId(u32);
17///
18/// let mut word_cache: IdCache<WordId, &str> = IdCache::new();
19///
20/// let foo_id = word_cache.make_id("foo");
21/// let bar_id = word_cache.make_id("bar");
22///
23/// assert_eq!(word_cache[foo_id], "foo");
24/// assert_eq!(word_cache[bar_id], "bar");
25///
26/// // ids for repeated values are reused:
27/// assert_eq!(word_cache.make_id("foo"), foo_id);
28/// ```
29///
30/// # Serde Support
31///
32/// When the `serde` Cargo feature is enabled, the `IdCache<I, T>` type can be serialized and
33/// deserialized using [Serde](https://serde.rs). An `IdCache<I, T>` is serialized as a sequence
34/// consisting of the unique values in the cache, ordered by id:
35///
36/// ```
37/// # #[cfg(feature = "serde")]
38/// # {
39/// use id_collections::id_type;
40/// use id_cache::IdCache;
41///
42/// #[id_type]
43/// struct WordId(u32);
44///
45/// let mut word_cache: IdCache<WordId, &str> = IdCache::new();
46/// word_cache.make_id("foo");
47/// word_cache.make_id("bar");
48///
49/// let serialized = serde_json::to_string(&word_cache).unwrap();
50/// assert_eq!(&serialized, r#"["foo","bar"]"#);
51/// # }
52/// ```
53#[derive(Clone)]
54#[cfg_attr(feature = "serde", derive(serde::Serialize))]
55#[cfg_attr(feature = "serde", serde(transparent))]
56pub struct IdCache<I: Id, T> {
57    #[cfg_attr(feature = "serde", serde(bound(serialize = "T: serde::Serialize")))]
58    id_to_value: IdVec<I, T>,
59    #[cfg_attr(feature = "serde", serde(skip))]
60    value_to_id: HashMap<T, I>,
61}
62
63#[cfg(feature = "serde")]
64impl<'de, I: Id, T: Eq + Hash + Clone + serde::Deserialize<'de>> serde::Deserialize<'de>
65    for IdCache<I, T>
66{
67    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
68    where
69        D: serde::Deserializer<'de>,
70    {
71        let id_to_value = IdVec::<I, T>::deserialize(deserializer)?;
72
73        let mut value_to_id = HashMap::new();
74        for (id, value) in &id_to_value {
75            let existing = value_to_id.insert(value.clone(), id);
76            if existing.is_some() {
77                use serde::de::Error;
78                return Err(D::Error::custom("duplicate value in IdCache"));
79            }
80        }
81
82        Ok(IdCache {
83            id_to_value,
84            value_to_id,
85        })
86    }
87}
88
89#[cfg(feature = "serde")]
90mod serde_test {
91    #[test]
92    fn test_round_trip() {
93        use crate::IdCache;
94        use id_collections::id_type;
95
96        #[id_type]
97        struct TestId(u32);
98
99        let mut cache: IdCache<u32, String> = IdCache::new();
100        cache.make_id("foo".to_owned());
101        cache.make_id("bar".to_owned());
102
103        let serialized = serde_json::to_string(&cache).unwrap();
104        assert_eq!(serialized, r#"["foo","bar"]"#);
105
106        let deserialized = serde_json::from_str::<IdCache<u32, String>>(&serialized).unwrap();
107        assert_eq!(&deserialized, &cache);
108    }
109
110    #[test]
111    fn test_duplicate_err() {
112        use crate::IdCache;
113
114        let result = serde_json::from_str::<IdCache<u32, String>>(r#"["foo","foo"]"#);
115        assert!(result.is_err());
116    }
117}
118
119impl<I: Id, T> Default for IdCache<I, T> {
120    fn default() -> Self {
121        Self::new()
122    }
123}
124
125impl<I: Id + Debug, T: Debug> Debug for IdCache<I, T> {
126    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
127        self.id_to_value.fmt(f)
128    }
129}
130
131impl<I: Id, T: PartialEq> PartialEq for IdCache<I, T> {
132    fn eq(&self, other: &Self) -> bool {
133        self.id_to_value == other.id_to_value
134    }
135}
136
137impl<I: Id, T: Eq> Eq for IdCache<I, T> {}
138
139impl<I: Id, T> IdCache<I, T> {
140    /// Constructs a new, empty `IdCache<I, T>`.
141    ///
142    /// # Examples
143    ///
144    /// ```
145    /// # use id_cache::IdCache;
146    /// let cache: IdCache<u32, &str> = IdCache::new();
147    /// assert!(cache.is_empty());
148    /// ```
149    pub fn new() -> Self {
150        IdCache {
151            id_to_value: IdVec::new(),
152            value_to_id: HashMap::new(),
153        }
154    }
155
156    /// Constructs a new, empty `IdCache<I, T>` with space to hold at least `capacity` unique
157    /// values.
158    ///
159    /// # Examples
160    ///
161    /// ```
162    /// # use id_cache::IdCache;
163    /// let mut cache: IdCache<u32, &str> = IdCache::with_capacity(100);
164    /// assert!(cache.is_empty());
165    /// ```
166    pub fn with_capacity(capacity: usize) -> Self {
167        IdCache {
168            id_to_value: IdVec::with_capacity(capacity),
169            value_to_id: HashMap::with_capacity(capacity),
170        }
171    }
172
173    /// Returns the total number of ids that have been assigned to unique values in the
174    /// `IdCache<I, T>`.
175    ///
176    /// # Examples
177    ///
178    /// ```
179    /// # use id_cache::IdCache;
180    /// let mut cache: IdCache<u32, &str> = IdCache::new();
181    /// assert!(cache.count().is_empty());
182    /// cache.make_id("foo");
183    /// cache.make_id("bar");
184    /// assert_eq!(cache.count().to_value(), 2);
185    /// cache.make_id("foo"); // value already present, so does not assign a new id
186    /// assert_eq!(cache.count().to_value(), 2);
187    /// ```
188    pub fn count(&self) -> Count<I> {
189        self.id_to_value.count()
190    }
191
192    /// Returns the total number of unique values in the `IdCache<I, T>`.
193    ///
194    /// # Examples
195    ///
196    /// ```
197    /// # use id_cache::IdCache;
198    /// let mut cache: IdCache<u32, &str> = IdCache::new();
199    /// assert_eq!(cache.len(), 0);
200    /// cache.make_id("foo");
201    /// cache.make_id("bar");
202    /// assert_eq!(cache.len(), 2);
203    /// cache.make_id("foo"); // value already present, so does not increase the len
204    /// assert_eq!(cache.len(), 2);
205    /// ```
206    pub fn len(&self) -> usize {
207        self.id_to_value.len()
208    }
209
210    /// Returns `true` if the `IdCache<I, T>` contains no values.
211    ///
212    /// # Examples
213    ///
214    /// ```
215    /// # use id_cache::IdCache;
216    /// let mut cache: IdCache<u32, &str> = IdCache::new();
217    /// assert!(cache.is_empty());
218    /// cache.make_id("foo");
219    /// assert!(!cache.is_empty());
220    /// ```
221    pub fn is_empty(&self) -> bool {
222        self.id_to_value.is_empty()
223    }
224
225    /// Ensures `value` has an id in the `IdCache<I, T>`, and returns that id.
226    ///
227    /// If `value` is already present in the `IdCache<I, T>`, then `make_id` returns its existing
228    /// id. Otherwise, `make_id` returns a new sequentally-assigned id.
229    ///
230    /// # Panics
231    ///
232    /// Panics if the number of ids in the `IdCache<I, T>` overflows `I`.
233    ///
234    /// # Examples
235    ///
236    /// ```
237    /// # use id_cache::IdCache;
238    /// let mut cache: IdCache<u32, &str> = IdCache::new();
239    /// assert_eq!(cache.make_id("foo"), 0);
240    /// assert_eq!(cache.make_id("bar"), 1);
241    /// assert_eq!(cache.make_id("foo"), 0);
242    /// ```
243    pub fn make_id(&mut self, value: T) -> I
244    where
245        T: Eq + Hash + Clone,
246    {
247        *self
248            .value_to_id
249            .entry(value)
250            .or_insert_with_key(|value| self.id_to_value.push(value.clone()))
251    }
252
253    /// Returns the id of a value in the `IdCache<I, T>`, or `None` if the value is not present.
254    ///
255    /// # Examples
256    ///
257    /// ```
258    /// # use id_cache::IdCache;
259    /// let mut cache: IdCache<u32, &str> = IdCache::new();
260    /// let foo_id = cache.make_id("foo");
261    /// assert_eq!(cache.get_id(&"foo"), Some(foo_id));
262    /// assert_eq!(cache.get_id(&"bar"), None);
263    /// ```
264    pub fn get_id<U>(&self, value: &U) -> Option<I>
265    where
266        T: Borrow<U> + Eq + Hash,
267        U: Eq + Hash,
268    {
269        self.value_to_id.get(value).cloned()
270    }
271
272    /// Returns a reference to the value in the `IdCache<I, T>` associated with a given `id`, or
273    /// `None` if the id has not been assigned.
274    ///
275    /// # Examples
276    ///
277    /// ```
278    /// # use id_cache::IdCache;
279    /// let mut cache: IdCache<u32, &str> = IdCache::new();
280    /// let foo_id = cache.make_id("foo");
281    /// assert_eq!(foo_id, 0);
282    /// assert_eq!(cache.get_value(foo_id), Some(&"foo"));
283    /// assert_eq!(cache.get_value(1), None);
284    /// ```
285    pub fn get_value(&self, id: I) -> Option<&T> {
286        self.id_to_value.get(id)
287    }
288}
289
290impl<I: Id, T, J: Borrow<I>> Index<J> for IdCache<I, T> {
291    type Output = T;
292
293    /// Returns a reference to the value in the `IdCache<I, T>` associated with a given `id`.
294    ///
295    /// # Panics
296    ///
297    /// Panics if `id` has not been assigned.
298    ///
299    /// # Examples
300    ///
301    /// ```
302    /// # use id_cache::IdCache;
303    /// let mut cache: IdCache<u32, &str> = IdCache::new();
304    /// let foo_id = cache.make_id("foo");
305    /// assert_eq!(cache[foo_id], "foo");
306    /// ```
307    #[inline]
308    fn index(&self, id: J) -> &Self::Output {
309        let id = *id.borrow();
310        &self.id_to_value[id]
311    }
312}
id_cache/lib.rs

id_cache/
lib.rs
