vec_btree_map/
lib.rs

1#![no_std]
2extern crate alloc;
3
4mod deref;
5mod index;
6mod iter;
7#[cfg(feature = "serde")]
8mod serde;
9#[cfg(test)]
10mod tests;
11
12use alloc::vec::Vec;
13use core::borrow::Borrow;
14use core::fmt::{self, Debug, Formatter};
15use core::mem;
16
17pub use iter::{Iter, IterMut, Keys, Values, ValuesMut};
18
19#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
20pub struct VecBTreeMap<K, V> {
21    base: Vec<(K, V)>,
22}
23
24impl<K, V> Default for VecBTreeMap<K, V> {
25    fn default() -> Self {
26        Self::new()
27    }
28}
29
30impl<K, V> VecBTreeMap<K, V> {
31    /// Constructs a new, empty `VecBTreeMap<K, V>`.
32    ///
33    /// The map is initially created with a capacity of 0, so it will not allocate until it is first inserted into.
34    ///
35    /// # Examples
36    ///
37    /// ```
38    /// # #![allow(unused_mut)]
39    /// use vec_btree_map::VecBTreeMap;
40    ///
41    /// let mut map: VecBTreeMap<String, f64> = VecBTreeMap::new();
42    /// ```
43    #[inline]
44    #[must_use]
45    pub const fn new() -> Self {
46        Self { base: Vec::new() }
47    }
48
49    /// Constructs a new, empty `VecBTreeMap<K, V>` with at least the specified capacity.
50    ///
51    /// The map will be able to hold at least `capacity` elements without
52    /// reallocating. This method is allowed to allocate for more elements than
53    /// `capacity`. If `capacity` is 0, the map will not allocate.
54    ///
55    /// It is important to note that although the returned map has the
56    /// minimum *capacity* specified, the map will have a zero *length*. For
57    /// an explanation of the difference between length and capacity, see
58    /// *[Capacity and reallocation]*.
59    ///
60    /// If it is important to know the exact allocated capacity of a `VecBTreeMap<K, V>`,
61    /// always use the [`capacity`] method after construction.
62    ///
63    /// [Capacity and reallocation]: Vec#capacity-and-reallocation
64    /// [`capacity`]: Vec::capacity
65    ///
66    /// # Panics
67    ///
68    /// Panics if the new capacity exceeds `isize::MAX` bytes.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// use vec_btree_map::VecBTreeMap;
74    ///
75    /// let mut map = VecBTreeMap::with_capacity(10);
76    ///
77    /// // The map contains no items, even though it has capacity for more
78    /// assert_eq!(map.len(), 0);
79    /// assert!(map.capacity() >= 10);
80    ///
81    /// // These are all done without reallocating...
82    /// for i in 0..10 {
83    ///     map.insert(i, i);
84    /// }
85    /// assert_eq!(map.len(), 10);
86    /// assert!(map.capacity() >= 10);
87    ///
88    /// // ...but this may make the map reallocate
89    /// map.insert(11, 0);
90    /// assert_eq!(map.len(), 11);
91    /// assert!(map.capacity() >= 11);
92    /// ```
93    ///     
94    #[inline]
95    #[must_use]
96    pub fn with_capacity(capacity: usize) -> Self {
97        Self {
98            base: Vec::with_capacity(capacity),
99        }
100    }
101
102    /// An iterator yielding all key-value paris from start to end.
103    /// The iterator element type is `(&K, &V)`.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    /// use vec_btree_map::VecBTreeMap;
109    ///
110    /// let mut map = VecBTreeMap::with_capacity(3);
111    /// map.insert("a", 1);
112    /// map.insert("b", 2);
113    /// map.insert("c", 3);
114    ///
115    /// let mut iter = map.iter();
116    ///
117    /// for (key, value) in iter {
118    ///     println!("{key}: {value}");
119    /// }
120    /// ```
121    #[inline]
122    pub fn iter(&self) -> Iter<'_, K, V> {
123        Iter::new(self.base.iter())
124    }
125
126    /// An iterator yielding all key-value pairs from start to end, with mutable references to the values.
127    /// The iterator element type is (&K, &mut V).
128    ///
129    /// # Examples
130    ///
131    /// ```
132    /// use vec_btree_map::VecBTreeMap;
133    ///
134    /// let mut map = VecBTreeMap::with_capacity(3);
135    /// map.insert("a", 1);
136    /// map.insert("b", 2);
137    /// map.insert("c", 3);
138    ///
139    /// // Update all values
140    /// for (_, value) in map.iter_mut() {
141    ///     *value *= 2;
142    /// }
143    ///
144    /// for (key, value) in map.iter() {
145    ///     println!("{key}: {value}");
146    /// }
147    /// ```
148    #[inline]
149    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
150        IterMut::new(self.base.iter_mut())
151    }
152
153    /// An iterator yielding all keys from start to end.
154    /// The iterator element type is `&K`.
155    ///
156    /// # Examples
157    ///
158    /// ```
159    /// use vec_btree_map::VecBTreeMap;
160    ///
161    /// let mut map = VecBTreeMap::with_capacity(3);
162    /// map.insert("a", 1);
163    /// map.insert("b", 2);
164    /// map.insert("c", 3);
165    ///
166    /// let mut keys = map.keys();
167    ///
168    /// assert_eq!(keys.next(), Some(&"a"));
169    /// assert_eq!(keys.next(), Some(&"b"));
170    /// assert_eq!(keys.next(), Some(&"c"));
171    /// assert_eq!(keys.next(), None);
172    /// ```
173    #[inline]
174    pub fn keys(&self) -> Keys<'_, K, V> {
175        Keys::new(self.base.iter())
176    }
177
178    /// An iterator yielding all values from start to end.
179    /// The iterator element type is `&V`.
180    ///
181    /// # Examples
182    ///
183    /// ```
184    /// use vec_btree_map::VecBTreeMap;
185    ///
186    /// let mut map = VecBTreeMap::with_capacity(3);
187    /// map.insert("a", 1);
188    /// map.insert("b", 2);
189    /// map.insert("c", 3);
190    ///
191    ///let mut keys = map.values();
192    ///
193    /// assert_eq!(keys.next(), Some(&1));
194    /// assert_eq!(keys.next(), Some(&2));
195    /// assert_eq!(keys.next(), Some(&3));
196    /// assert_eq!(keys.next(), None);
197    /// ```
198    #[inline]
199    pub fn values(&self) -> Values<'_, K, V> {
200        Values::new(self.base.iter())
201    }
202
203    /// An iterator yielding all values mutably from start to end.
204    /// The iterator element type is `&V`.
205    ///
206    /// # Examples
207    ///
208    /// ```
209    /// use vec_btree_map::VecBTreeMap;
210    ///
211    /// let mut map = VecBTreeMap::with_capacity(3);
212    /// map.insert("a", 1);
213    /// map.insert("b", 2);
214    /// map.insert("c", 3);
215    ///
216    /// for val in map.values_mut() {
217    ///     *val *= *val;
218    /// }
219    ///
220    ///let mut keys = map.values();
221    ///
222    /// assert_eq!(keys.next(), Some(&1));
223    /// assert_eq!(keys.next(), Some(&4));
224    /// assert_eq!(keys.next(), Some(&9));
225    /// assert_eq!(keys.next(), None);
226    /// ```
227    #[inline]
228    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
229        ValuesMut::new(self.base.iter_mut())
230    }
231}
232
233impl<K, V> VecBTreeMap<K, V>
234where
235    K: Ord,
236{
237    /// Binary searches this map for a given key.
238    ///
239    /// If the key is found then [`Result::Ok`] is returned, containing the
240    /// index of the matching key.
241    /// If the key is not found then [`Result::Err`] is returned, containing
242    /// the index where a matching key-value pair could be inserted while maintaining
243    /// sorted order.
244    ///
245    /// # Examples
246    ///
247    /// Looks up a series of four elements.
248    /// The first is found, the second and third are not.
249    ///
250    /// ```
251    /// use vec_btree_map::VecBTreeMap;
252    ///
253    /// let mut map = VecBTreeMap::with_capacity(3);
254    /// map.insert("a", 1);
255    /// map.insert("c", 2);
256    /// map.insert("d", 3);
257    ///
258    /// assert_eq!(map.binary_search("a"), Ok(0));
259    /// assert_eq!(map.binary_search("b"), Err(1));
260    /// assert_eq!(map.binary_search("e"), Err(3));
261    /// ```
262    #[inline]
263    pub fn binary_search<Q>(&self, k: &Q) -> Result<usize, usize>
264    where
265        Q: Ord + ?Sized,
266        K: Borrow<Q>,
267    {
268        self.base.binary_search_by(|e| e.0.borrow().cmp(k))
269    }
270
271    /// Appends a key-value pair to the back of the map.
272    ///
273    /// If the map woudn't be sorted anymore by appending
274    /// the key-value pair to the back of the map, [`Some`]`(K, V)` is returned.
275    /// Otherwise [`None`] is returned.
276    ///
277    /// # Panics
278    ///
279    /// Panics if the new capacity exceeds `isize::MAX` bytes.
280    #[inline]
281    pub fn push(&mut self, k: K, v: V) -> Option<(K, V)> {
282        let last = self.len().saturating_sub(1);
283        if let Some((key, _)) = self.get(last)
284            && key >= &k
285        {
286            return Some((k, v));
287        }
288        self.base.push((k, v));
289        None
290    }
291
292    /// Inserts a key-value pair into the map.
293    ///
294    /// If the map did not have this key present, [`None`] is returned.
295    ///
296    /// If the map did have this key present, the value is updated, and the old
297    /// value is returned. The key is not updated.
298    ///
299    /// # Panics
300    ///
301    /// Panics if the new capacity exceeds `isize::MAX` bytes.
302    ///
303    /// # Examples
304    ///
305    /// ```
306    /// use vec_btree_map::VecBTreeMap;
307    ///
308    /// let mut map = VecBTreeMap::new();
309    ///
310    /// assert_eq!(map.is_empty(), true);
311    /// assert_eq!(map.insert("a", 1), None);
312    /// assert_eq!(map.is_empty(), false);
313    ///
314    /// map.insert("a", 2);
315    /// assert_eq!(map.insert("a", 3), Some(2));
316    /// assert_eq!(map[0], 3);
317    /// ```
318    #[inline]
319    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
320        match self.binary_search(&k) {
321            Ok(i) => Some(mem::replace(&mut self.base[i].1, v)),
322            Err(i) => {
323                self.base.insert(i, (k, v));
324                None
325            }
326        }
327    }
328
329    /// Removes a key from the map, returning the value at the key if the key
330    /// was previously in the map.
331    ///
332    /// The key may be any borrowed form of the map's key type, but
333    /// [`Ord`] on the borrowed form *must* match those for
334    /// the key type.
335    ///
336    /// # Examples
337    ///
338    /// ```
339    /// use vec_btree_map::VecBTreeMap;
340    ///
341    /// let mut map = VecBTreeMap::new();
342    /// map.insert("a", 1);
343    /// assert_eq!(map.remove("a"), Some(1));
344    /// assert_eq!(map.remove("a"), None);
345    /// ```
346    #[inline]
347    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
348    where
349        Q: Ord + ?Sized,
350        K: Borrow<Q>,
351    {
352        self.binary_search(k).map(|i| self.base.remove(i).1).ok()
353    }
354
355    /// Removes the last key-value pair from the map and returns it, or [`None`] if it
356    /// is empty.
357    ///
358    /// # Examples
359    ///
360    /// ```
361    /// use vec_btree_map::VecBTreeMap;
362    ///
363    /// let mut map = VecBTreeMap::new();
364    /// map.insert("a", 1);
365    /// assert_eq!(map.pop(), Some(("a", 1)));
366    /// assert_eq!(map.pop(), None);
367    /// ```
368    #[inline]
369    pub fn pop(&mut self) -> Option<(K, V)> {
370        self.base.pop()
371    }
372
373    /// Clears the map, removing all key-value pairs. Keeps the allocated memory
374    /// for reuse.
375    ///
376    /// # Examples
377    ///
378    /// ```
379    /// use vec_btree_map::VecBTreeMap;
380    ///
381    /// let mut a = VecBTreeMap::new();
382    /// a.insert(1, "a");
383    /// a.clear();
384    /// assert!(a.is_empty());
385    /// ```
386    #[inline]
387    pub fn clear(&mut self) {
388        self.base.clear()
389    }
390}
391
392impl<K: Clone, V: Clone> Clone for VecBTreeMap<K, V> {
393    #[inline]
394    fn clone(&self) -> Self {
395        Self {
396            base: self.base.clone(),
397        }
398    }
399}
400
401impl<K: Debug, V: Debug> Debug for VecBTreeMap<K, V> {
402    #[inline]
403    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
404        f.debug_map().entries(self.iter()).finish()
405    }
406}
vec_btree_map/lib.rs

vec_btree_map/
lib.rs
