radixt/
map.rs

1use std::ops::RangeBounds;
2
3use crate::iter::{
4    IntoIter, Iter, IterMap, IterMapMut, IterMut, MapK, MapKV, MapKVMut, MapV, MapVMut, Range,
5    RangeMut,
6};
7use crate::node::Node;
8
9#[derive(Debug)]
10pub struct RadixMap<T> {
11    root: Node<T>,
12    size: usize,
13}
14
15impl<T> Default for RadixMap<T> {
16    fn default() -> Self {
17        RadixMap::new()
18    }
19}
20
21impl<T> RadixMap<T> {
22    pub fn new() -> Self {
23        RadixMap {
24            root: Node::new(&[]),
25            size: 0,
26        }
27    }
28
29    /// Returns the number of elements in the map.
30    #[inline(always)]
31    pub fn len(&self) -> usize {
32        self.size
33    }
34
35    /// Returns `true` if the map contains no elements.
36    #[inline(always)]
37    pub fn is_empty(&self) -> bool {
38        self.len() == 0
39    }
40
41    /// Inserts a key-value pair into the map.
42    ///
43    /// If the map did not have this key present, None is returned.
44    ///
45    /// If the map did have this key present, the value is updated, and the old
46    /// value is returned.
47    #[inline(always)]
48    pub fn insert<K: AsRef<[u8]>>(&mut self, key: K, value: T) -> Option<T> {
49        let old = self.root.insert(key.as_ref(), value);
50        self.size += old.is_none() as usize;
51        old
52    }
53
54    /// Removes a key from the map, returning the value at the key if the key
55    /// was previously in the map.
56    #[inline(always)]
57    pub fn remove<K: AsRef<[u8]>>(&mut self, key: K) -> Option<T> {
58        let removed = self.root.remove(key.as_ref());
59        self.size -= removed.is_some() as usize;
60        removed
61    }
62
63    /// Returns a reference to the value corresponding to the key.
64    #[inline(always)]
65    pub fn get<K: AsRef<[u8]>>(&self, key: K) -> Option<&T> {
66        self.root.get(key.as_ref())
67    }
68
69    /// Returns a mutable reference to the value corresponding to the key.
70    #[inline(always)]
71    pub fn get_mut<K: AsRef<[u8]>>(&mut self, key: K) -> Option<&mut T> {
72        self.root.get_mut(key.as_ref())
73    }
74
75    /// Returns `true` if this map contains a value for the specified key.
76    #[inline(always)]
77    pub fn contains_key<K: AsRef<[u8]>>(&self, key: K) -> bool {
78        self.get(key).is_some()
79    }
80
81    /// Gets an iterator over the entries of the map, sorted by key.
82    /// This iterator allocates a boxed slice for each item. If you
83    /// only need to access values consider using [`Self::values()`] instead.
84    #[inline(always)]
85    pub fn iter(&self) -> Iter<T, MapKV<T>> {
86        self.get_iter()
87    }
88
89    /// Gets a mutable iterator over the entries of the map, sorted by key.
90    /// This iterator allocates a boxed slice for each item. If you only
91    /// need to access values consider using [`Self::values_mut()`] instead.
92    #[inline(always)]
93    pub fn iter_mut(&mut self) -> IterMut<T, MapKVMut<T>> {
94        self.get_iter_mut()
95    }
96
97    /// Gets an iterator over the entries of the map matching a given prefix, sorted by key.
98    ///
99    /// This iterator allocates a boxed slice for each item. If you only
100    /// need to access values consider using [`Self::prefix_values()`] instead.
101    #[inline(always)]
102    pub fn prefix_iter<K: AsRef<[u8]>>(&self, prefix: K) -> Iter<T, MapKV<T>> {
103        self.get_prefix_iter(prefix)
104    }
105
106    /// Gets a mutable iterator over the entries of the map matching a given prefix, sorted by key.
107    ///
108    /// This iterator allocates a boxed slice for each item. If you only
109    /// need to access values consider using [`Self::prefix_values_mut()`] instead.
110    #[inline(always)]
111    pub fn prefix_iter_mut<K: AsRef<[u8]>>(&mut self, prefix: K) -> IterMut<T, MapKVMut<T>> {
112        self.get_prefix_iter_mut(prefix)
113    }
114
115    /// Gets an iterator over the values of the map, in order by key.
116    #[inline(always)]
117    pub fn values(&self) -> Iter<T, MapV<T>> {
118        self.get_iter()
119    }
120
121    /// Gets a mutable iterator over the values of the map, in order by key.
122    #[inline(always)]
123    pub fn values_mut(&mut self) -> IterMut<T, MapVMut<T>> {
124        self.get_iter_mut()
125    }
126
127    /// Gets an iterator over the values of the map matching a given prefix, in order by key.
128    #[inline(always)]
129    pub fn prefix_values<K: AsRef<[u8]>>(&self, prefix: K) -> Iter<T, MapV<T>> {
130        self.get_prefix_iter(prefix)
131    }
132
133    /// Gets a mutable iterator over the values of the map matching a given prefix, in order by key.
134    #[inline(always)]
135    pub fn prefix_values_mut<K: AsRef<[u8]>>(&mut self, prefix: K) -> IterMut<T, MapVMut<T>> {
136        self.get_prefix_iter_mut(prefix)
137    }
138
139    /// Gets an iterator over the keys of the map, in order by key.
140    #[inline(always)]
141    pub fn keys(&self) -> Iter<T, MapK<T>> {
142        self.get_iter()
143    }
144
145    /// Gets an iterator over the keys of the map matching a given prefix, in order by key.
146    #[inline(always)]
147    pub fn prefix_keys<K: AsRef<[u8]>>(&self, prefix: K) -> Iter<T, MapK<T>> {
148        self.get_prefix_iter(prefix)
149    }
150
151    /// Constructs an iterator over a sub-range of elements in the map. The simplest
152    /// way is to use the range syntax `min..max`, thus `range(min..max)` will yield elements from min
153    /// (inclusive) to max (exclusive). The range may also be entered as `(Bound<T>, Bound<T>)`.
154    #[inline(always)]
155    pub fn range<K: AsRef<[u8]>, B: RangeBounds<K>>(&self, bounds: B) -> Range<T, K, B> {
156        Range::new(self.get_iter(), bounds)
157    }
158
159    /// Constructs a mutable iterator over a sub-range of elements in the map. The simplest
160    /// way is to use the range syntax `min..max`, thus `range(min..max)` will yield elements from min
161    /// (inclusive) to max (exclusive). The range may also be entered as `(Bound<T>, Bound<T>)`.
162    #[inline(always)]
163    pub fn range_mut<K: AsRef<[u8]>, B: RangeBounds<K>>(&mut self, bounds: B) -> RangeMut<T, K, B> {
164        RangeMut::new(self.get_iter_mut(), bounds)
165    }
166
167    fn get_iter<'a, M: IterMap<'a, T>>(&'a self) -> Iter<'a, T, M> {
168        Iter::new(Some(&self.root), vec![])
169    }
170
171    fn get_iter_mut<'a, M: IterMapMut<'a, T>>(&'a mut self) -> IterMut<'a, T, M> {
172        IterMut::new(Some(&mut self.root), vec![])
173    }
174
175    fn get_prefix_iter<'a, M: IterMap<'a, T>, K: AsRef<[u8]>>(
176        &'a self,
177        prefix: K,
178    ) -> Iter<'a, T, M> {
179        match self.root.find_prefix(prefix.as_ref()) {
180            Some((prefix_len, prefix_node)) => {
181                Iter::new(Some(prefix_node), prefix.as_ref()[..prefix_len].to_vec())
182            }
183            None => Iter::new(None, vec![]),
184        }
185    }
186
187    fn get_prefix_iter_mut<'a, M: IterMapMut<'a, T>, K: AsRef<[u8]>>(
188        &'a mut self,
189        prefix: K,
190    ) -> IterMut<'a, T, M> {
191        match self.root.find_prefix_mut(prefix.as_ref()) {
192            Some((prefix_len, prefix_node)) => {
193                IterMut::new(Some(prefix_node), prefix.as_ref()[..prefix_len].to_vec())
194            }
195            None => IterMut::new(None, vec![]),
196        }
197    }
198
199    #[inline(always)]
200    pub(crate) fn root(&self) -> &Node<T> {
201        &self.root
202    }
203}
204
205impl<T> IntoIterator for RadixMap<T> {
206    type Item = (Box<[u8]>, T);
207    type IntoIter = IntoIter<T>;
208
209    fn into_iter(self) -> Self::IntoIter {
210        IntoIter::new(self.root)
211    }
212}
213
214impl<K: AsRef<[u8]>, T, const N: usize> From<[(K, T); N]> for RadixMap<T> {
215    fn from(items: [(K, T); N]) -> Self {
216        let mut map = RadixMap::new();
217        for (key, value) in items {
218            map.insert(key, value);
219        }
220        map
221    }
222}
223
224impl<K: AsRef<[u8]>, T> FromIterator<(K, T)> for RadixMap<T> {
225    fn from_iter<I: IntoIterator<Item = (K, T)>>(iter: I) -> Self {
226        let mut map = RadixMap::new();
227        for (key, value) in iter {
228            map.insert(key, value);
229        }
230        map
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237
238    use std::rc::Rc;
239
240    fn populated_map() -> RadixMap<u32> {
241        let mut m = RadixMap::new();
242
243        m.insert("cad", 5);
244        m.insert("abc;0", 1);
245        m.insert("c", 4);
246        m.insert("abb;0", 2);
247        m.insert("ab", 3);
248
249        m
250    }
251
252    #[test]
253    fn test_insert_and_get() {
254        let mut m = RadixMap::new();
255
256        m.insert("abc;0", 1);
257        m.insert("abb;0", 2);
258        m.insert("ab", 3);
259        m.insert("c", 4);
260        m.insert("cad", 5);
261
262        assert_eq!(m.len(), 5);
263
264        assert_eq!(m.get("ab").unwrap(), &3);
265        assert_eq!(m.get("abc;0").unwrap(), &1);
266        assert_eq!(m.get("abb;0").unwrap(), &2);
267        assert_eq!(m.get("c").unwrap(), &4);
268        assert_eq!(m.get("cad").unwrap(), &5);
269
270        assert_eq!(m.get("d"), None);
271        assert_eq!(m.get("ac"), None);
272        assert_eq!(m.get("abd"), None);
273        assert_eq!(m.get("abc;"), None);
274        assert_eq!(m.get("abc;1"), None);
275        assert_eq!(m.get(""), None);
276    }
277
278    #[test]
279    fn test_remove() {
280        let mut m = populated_map();
281
282        assert_eq!(m.len(), 5);
283        assert_eq!(m.get("ab").unwrap(), &3);
284        assert_eq!(m.get("abc;0").unwrap(), &1);
285        assert_eq!(m.get("abb;0").unwrap(), &2);
286        assert_eq!(m.get("c").unwrap(), &4);
287        assert_eq!(m.get("cad").unwrap(), &5);
288
289        assert_eq!(m.remove("ab"), Some(3));
290        assert_eq!(m.len(), 4);
291        assert!(m.get("ab").is_none());
292
293        assert_eq!(m.remove("cad"), Some(5));
294        assert_eq!(m.len(), 3);
295        assert!(m.get("cad").is_none());
296
297        assert_eq!(m.remove("cad"), None);
298        assert_eq!(m.remove("foobar"), None);
299
300        assert_eq!(m.get("abc;0").unwrap(), &1);
301        assert_eq!(m.get("abb;0").unwrap(), &2);
302        assert_eq!(m.get("c").unwrap(), &4);
303    }
304
305    #[test]
306    fn test_with_long_keys() {
307        let mut m = RadixMap::new();
308
309        let key_a = vec![0; 260];
310        let mut key_b = key_a.clone();
311        key_b.extend(&[1, 2, 3]);
312        let mut key_c = key_a.clone();
313        key_c.extend(&[4, 5, 6]);
314        let key_d = vec![0; 520];
315        let key_e = vec![1; 512];
316        let key_f = vec![2; 510];
317
318        m.insert(&key_a, 1);
319        m.insert(&key_b, 2);
320        m.insert(&key_c, 3);
321        m.insert(&key_d, 4);
322        m.insert(&key_e, 5);
323        m.insert(&key_f, 6);
324
325        assert_eq!(m.len(), 6);
326        assert_eq!(m.get(&key_a), Some(&1));
327        assert_eq!(m.get(&key_b), Some(&2));
328        assert_eq!(m.get(&key_c), Some(&3));
329        assert_eq!(m.get(&key_d), Some(&4));
330        assert_eq!(m.get(&key_e), Some(&5));
331        assert_eq!(m.get(&key_f), Some(&6));
332
333        // Test remove
334        assert_eq!(m.remove(&key_a), Some(1));
335        assert_eq!(m.len(), 5);
336        assert_eq!(m.get(&key_a), None);
337        assert_eq!(m.get(&key_b), Some(&2));
338        assert_eq!(m.get(&key_c), Some(&3));
339        assert_eq!(m.get(&key_d), Some(&4));
340        assert_eq!(m.get(&key_e), Some(&5));
341        assert_eq!(m.get(&key_f), Some(&6));
342
343        assert_eq!(m.remove(&key_d), Some(4));
344        assert_eq!(m.len(), 4);
345        assert_eq!(m.get(&key_a), None);
346        assert_eq!(m.get(&key_b), Some(&2));
347        assert_eq!(m.get(&key_c), Some(&3));
348        assert_eq!(m.get(&key_d), None);
349        assert_eq!(m.get(&key_e), Some(&5));
350        assert_eq!(m.get(&key_f), Some(&6));
351
352        // Test remove missing
353        assert_eq!(m.remove(&key_d), None);
354        assert_eq!(m.len(), 4);
355        assert_eq!(m.get(&key_a), None);
356        assert_eq!(m.get(&key_b), Some(&2));
357        assert_eq!(m.get(&key_c), Some(&3));
358        assert_eq!(m.get(&key_d), None);
359        assert_eq!(m.get(&key_e), Some(&5));
360        assert_eq!(m.get(&key_f), Some(&6));
361
362        // Test iter
363        assert_eq!(m.iter().count(), 4);
364        assert_eq!(m.prefix_iter(&key_a).count(), 2);
365        assert_eq!(m.prefix_iter(&[0]).count(), 2);
366        assert_eq!(m.prefix_iter(&[1]).count(), 1);
367        assert_eq!(m.prefix_iter(&[2]).count(), 1);
368        assert_eq!(m.prefix_iter(&[3]).count(), 0);
369        assert_eq!(m.prefix_iter(&key_d).count(), 0);
370    }
371
372    #[test]
373    fn test_iter() {
374        let m = populated_map();
375
376        let mut it = m.iter();
377
378        let (k, v) = it.next().unwrap();
379        assert_eq!(k.as_ref(), b"ab");
380        assert_eq!(v, &3);
381        let (k, v) = it.next().unwrap();
382        assert_eq!(k.as_ref(), b"abb;0");
383        assert_eq!(v, &2);
384        let (k, v) = it.next().unwrap();
385        assert_eq!(k.as_ref(), b"abc;0");
386        assert_eq!(v, &1);
387        let (k, v) = it.next().unwrap();
388        assert_eq!(k.as_ref(), b"c");
389        assert_eq!(v, &4);
390        let (k, v) = it.next().unwrap();
391        assert_eq!(k.as_ref(), b"cad");
392        assert_eq!(v, &5);
393
394        assert_eq!(it.next(), None);
395    }
396
397    #[test]
398    fn test_iter_mut() {
399        let mut m = populated_map();
400
401        let mut it = m.iter_mut();
402
403        let (k, v) = it.next().unwrap();
404        assert_eq!(k.as_ref(), b"ab");
405        assert_eq!(v, &mut 3);
406        let (k, v) = it.next().unwrap();
407        assert_eq!(k.as_ref(), b"abb;0");
408        assert_eq!(v, &mut 2);
409        let (k, v) = it.next().unwrap();
410        assert_eq!(k.as_ref(), b"abc;0");
411        assert_eq!(v, &mut 1);
412        let (k, v) = it.next().unwrap();
413        assert_eq!(k.as_ref(), b"c");
414        assert_eq!(v, &mut 4);
415        let (k, v) = it.next().unwrap();
416        assert_eq!(k.as_ref(), b"cad");
417        assert_eq!(v, &mut 5);
418
419        assert_eq!(it.next(), None);
420
421        // Modify second item
422        assert_eq!(m.get("cad"), Some(&5));
423        assert_eq!(m.get("abc;0"), Some(&1));
424        assert_eq!(m.get("c"), Some(&4));
425        assert_eq!(m.get("abb;0"), Some(&2));
426        assert_eq!(m.get("ab"), Some(&3));
427
428        let mut it = m.iter_mut();
429
430        let _ = it.next().unwrap();
431        let (k, v) = it.next().unwrap();
432        assert_eq!(k.as_ref(), b"abb;0");
433        assert_eq!(v, &mut 2);
434        *v = 100;
435
436        for _ in 0..3 {
437            let _ = it.next().unwrap();
438        }
439        assert_eq!(it.next(), None);
440
441        assert_eq!(m.get("cad"), Some(&5));
442        assert_eq!(m.get("abc;0"), Some(&1));
443        assert_eq!(m.get("c"), Some(&4));
444        assert_eq!(m.get("abb;0"), Some(&100));
445        assert_eq!(m.get("ab"), Some(&3));
446    }
447
448    #[test]
449    fn test_prefix_iter() {
450        let m = populated_map();
451
452        let mut it = m.prefix_iter(b"ab");
453        let (k, v) = it.next().unwrap();
454        assert_eq!(k.as_ref(), b"ab");
455        assert_eq!(v, &3);
456        let (k, v) = it.next().unwrap();
457        assert_eq!(k.as_ref(), b"abb;0");
458        assert_eq!(v, &2);
459        let (k, v) = it.next().unwrap();
460        assert_eq!(k.as_ref(), b"abc;0");
461        assert_eq!(v, &1);
462        assert_eq!(it.next(), None);
463
464        let mut it = m.prefix_iter(b"abb");
465        let (k, v) = it.next().unwrap();
466        assert_eq!(k.as_ref(), b"abb;0");
467        assert_eq!(v, &2);
468        assert_eq!(it.next(), None);
469
470        let mut it = m.prefix_iter(b"c");
471        let (k, v) = it.next().unwrap();
472        assert_eq!(k.as_ref(), b"c");
473        assert_eq!(v, &4);
474        let (k, v) = it.next().unwrap();
475        assert_eq!(k.as_ref(), b"cad");
476        assert_eq!(v, &5);
477        assert_eq!(it.next(), None);
478
479        let mut it = m.prefix_iter(b"ca");
480        let (k, v) = it.next().unwrap();
481        assert_eq!(k.as_ref(), b"cad");
482        assert_eq!(v, &5);
483        assert_eq!(it.next(), None);
484
485        let mut it = m.prefix_iter(b"cad");
486        let (k, v) = it.next().unwrap();
487        assert_eq!(k.as_ref(), b"cad");
488        assert_eq!(v, &5);
489        assert_eq!(it.next(), None);
490
491        let mut it = m.prefix_iter(b"cada");
492        assert_eq!(it.next(), None);
493
494        let mut it = m.prefix_iter(b"abd");
495        assert_eq!(it.next(), None);
496    }
497
498    #[test]
499    fn test_prefix_iter_mut() {
500        let mut m = populated_map();
501
502        let mut it = m.prefix_iter_mut(b"ab");
503        let (k, v) = it.next().unwrap();
504        assert_eq!(k.as_ref(), b"ab");
505        assert_eq!(v, &mut 3);
506        let (k, v) = it.next().unwrap();
507        assert_eq!(k.as_ref(), b"abb;0");
508        assert_eq!(v, &mut 2);
509        let (k, v) = it.next().unwrap();
510        assert_eq!(k.as_ref(), b"abc;0");
511        assert_eq!(v, &mut 1);
512        assert_eq!(it.next(), None);
513
514        let mut it = m.prefix_iter_mut(b"abb");
515        let (k, v) = it.next().unwrap();
516        assert_eq!(k.as_ref(), b"abb;0");
517        assert_eq!(v, &mut 2);
518        assert_eq!(it.next(), None);
519
520        let mut it = m.prefix_iter_mut(b"c");
521        let (k, v) = it.next().unwrap();
522        assert_eq!(k.as_ref(), b"c");
523        assert_eq!(v, &mut 4);
524        let (k, v) = it.next().unwrap();
525        assert_eq!(k.as_ref(), b"cad");
526        assert_eq!(v, &mut 5);
527        assert_eq!(it.next(), None);
528
529        let mut it = m.prefix_iter_mut(b"ca");
530        let (k, v) = it.next().unwrap();
531        assert_eq!(k.as_ref(), b"cad");
532        assert_eq!(v, &mut 5);
533        assert_eq!(it.next(), None);
534
535        let mut it = m.prefix_iter_mut(b"cad");
536        let (k, v) = it.next().unwrap();
537        assert_eq!(k.as_ref(), b"cad");
538        assert_eq!(v, &mut 5);
539        assert_eq!(it.next(), None);
540
541        let mut it = m.prefix_iter_mut(b"cada");
542        assert_eq!(it.next(), None);
543
544        let mut it = m.prefix_iter_mut(b"abd");
545        assert_eq!(it.next(), None);
546    }
547
548    #[test]
549    fn test_range() {
550        let mut m = RadixMap::new();
551        m.insert("aa", 1);
552        m.insert("ab", 2);
553        m.insert("ac", 3);
554        m.insert("ad", 4);
555        m.insert("ba", 5);
556        m.insert("bb", 6);
557        m.insert("bc", 7);
558        m.insert("bd", 8);
559
560        assert_eq!(m.range::<&[u8], _>(..).count(), 8);
561        assert_eq!(m.range("a"..).count(), 8);
562        assert_eq!(m.range("a".."b").count(), 4);
563        assert_eq!(m.range("a"..="b").count(), 4);
564        assert_eq!(m.range("a"..="ba").count(), 5);
565        assert_eq!(m.range("ab"..="ba").count(), 4);
566        assert_eq!(m.range("ae"..).count(), 4);
567
568        for ((k1, v1), (k2, v2)) in m.range("a"..).zip(m.iter().take(4)) {
569            assert_eq!(k1.as_ref(), k2.as_ref());
570            assert_eq!(*v1, *v2);
571        }
572
573        for ((k1, v1), (k2, v2)) in m.range("ab"..="ba").zip(m.iter().skip(1).take(4)) {
574            assert_eq!(k1.as_ref(), k2.as_ref());
575            assert_eq!(*v1, *v2);
576        }
577
578        assert_eq!(m.range("b"..).count(), 4);
579        assert_eq!(m.range("b".."b").count(), 0);
580        assert_eq!(m.range("b"..="b").count(), 0);
581        assert_eq!(m.range("b"..="be").count(), 4);
582        assert_eq!(m.range("bb".."bc").count(), 1);
583        assert_eq!(m.range("bb"..="bc").count(), 2);
584
585        for ((k1, v1), (k2, v2)) in m.range("bb"..="bc").zip(m.iter().skip(5).take(2)) {
586            assert_eq!(k1.as_ref(), k2.as_ref());
587            assert_eq!(*v1, *v2);
588        }
589
590        assert_eq!(m.range("be"..).count(), 0);
591        assert_eq!(m.range("c"..).count(), 0);
592    }
593
594    #[test]
595    fn test_range_mut() {
596        let mut m = RadixMap::new();
597        m.insert("aa", 1);
598        m.insert("ab", 2);
599        m.insert("ac", 3);
600        m.insert("ad", 4);
601        m.insert("ba", 5);
602        m.insert("bb", 6);
603        m.insert("bc", 7);
604        m.insert("bd", 8);
605
606        assert_eq!(m.range_mut::<&[u8], _>(..).count(), 8);
607        assert_eq!(m.range_mut("a"..).count(), 8);
608        assert_eq!(m.range_mut("a".."b").count(), 4);
609        assert_eq!(m.range_mut("a"..="b").count(), 4);
610        assert_eq!(m.range_mut("a"..="ba").count(), 5);
611        assert_eq!(m.range_mut("ab"..="ba").count(), 4);
612        assert_eq!(m.range_mut("ae"..).count(), 4);
613
614        for ((k1, v1), (k2, v2)) in m.range("a"..).zip(m.iter().take(4)) {
615            assert_eq!(k1.as_ref(), k2.as_ref());
616            assert_eq!(*v1, *v2);
617        }
618
619        for ((k1, v1), (k2, v2)) in m.range("ab"..="ba").zip(m.iter().skip(1).take(4)) {
620            assert_eq!(k1.as_ref(), k2.as_ref());
621            assert_eq!(*v1, *v2);
622        }
623
624        assert_eq!(m.range_mut("b"..).count(), 4);
625        assert_eq!(m.range_mut("b".."b").count(), 0);
626        assert_eq!(m.range_mut("b"..="b").count(), 0);
627        assert_eq!(m.range_mut("b"..="be").count(), 4);
628        assert_eq!(m.range_mut("bb".."bc").count(), 1);
629        assert_eq!(m.range_mut("bb"..="bc").count(), 2);
630
631        for ((k1, v1), (k2, v2)) in m.range("bb"..="bc").zip(m.iter().skip(5).take(2)) {
632            assert_eq!(k1.as_ref(), k2.as_ref());
633            assert_eq!(*v1, *v2);
634        }
635
636        assert_eq!(m.range_mut("be"..).count(), 0);
637        assert_eq!(m.range_mut("c"..).count(), 0);
638
639        let (_, v) = m.range_mut("bb".."bc").next().unwrap();
640        *v = 66;
641
642        assert_eq!(m.get("bb"), Some(&66));
643    }
644
645    #[test]
646    fn test_from() {
647        let map = RadixMap::<u64>::from([("foo", 1), ("bar", 2), ("baz", 3), ("foo", 4)]);
648
649        assert_eq!(map.len(), 3);
650
651        let mut it = map.iter();
652        assert_eq!(it.next(), Some(("bar".as_bytes().into(), &2)));
653        assert_eq!(it.next(), Some(("baz".as_bytes().into(), &3)));
654        assert_eq!(it.next(), Some(("foo".as_bytes().into(), &4)));
655        assert!(it.next().is_none());
656    }
657
658    #[test]
659    fn test_from_iterator() {
660        let map: RadixMap<u64> = vec![("foo", 1), ("bar", 2), ("baz", 3), ("foo", 4)]
661            .into_iter()
662            .collect();
663
664        assert_eq!(map.len(), 3);
665
666        let mut it = map.iter();
667        assert_eq!(it.next(), Some(("bar".as_bytes().into(), &2)));
668        assert_eq!(it.next(), Some(("baz".as_bytes().into(), &3)));
669        assert_eq!(it.next(), Some(("foo".as_bytes().into(), &4)));
670        assert!(it.next().is_none());
671    }
672
673    #[test]
674    fn test_into_iter() {
675        let m = populated_map();
676        assert_eq!(m.len(), 5);
677
678        let mut it = m.into_iter();
679
680        let (k, v) = it.next().unwrap();
681        assert_eq!(k.as_ref(), b"ab");
682        assert_eq!(v, 3);
683
684        let (k, v) = it.next().unwrap();
685        assert_eq!(k.as_ref(), b"abb;0");
686        assert_eq!(v, 2);
687
688        let (k, v) = it.next().unwrap();
689        assert_eq!(k.as_ref(), b"abc;0");
690        assert_eq!(v, 1);
691
692        let (k, v) = it.next().unwrap();
693        assert_eq!(k.as_ref(), b"c");
694        assert_eq!(v, 4);
695
696        let (k, v) = it.next().unwrap();
697        assert_eq!(k.as_ref(), b"cad");
698        assert_eq!(v, 5);
699
700        assert!(it.next().is_none());
701    }
702
703    #[test]
704    fn test_into_iter_drops_internal_values() {
705        let rc = Rc::new(());
706
707        let mut m = RadixMap::new();
708        m.insert("a", rc.clone());
709        m.insert("aba", rc.clone());
710        m.insert("cat", rc.clone());
711
712        let _: Vec<(Box<[u8]>, Rc<()>)> = m.into_iter().collect();
713        assert_eq!(Rc::strong_count(&rc), 1);
714    }
715
716    #[test]
717    fn test_into_iter_unfinished() {
718        let rc = Rc::new(());
719
720        let mut m = RadixMap::new();
721        m.insert("a", rc.clone());
722        m.insert("aba", rc.clone());
723        m.insert("cat", rc.clone());
724
725        let mut it = m.into_iter();
726        let _ = it.next().unwrap();
727        drop(it);
728
729        assert_eq!(Rc::strong_count(&rc), 1);
730    }
731}
radixt/map.rs

radixt/
map.rs
