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

vec_btree_map/
lib.rs
