sigma_bounded/
btree_map.rs

1//! Defines [`BTreeMap`] and associated types.
2
3#[cfg(feature = "alloc")]
4extern crate alloc;
5
6use crate::error::Result;
7
8#[cfg(not(feature = "alloc"))]
9use crate::error::Error;
10
11#[cfg(feature = "alloc")]
12type Inner<K, V, const N: usize> = alloc::collections::BTreeMap<K, V>;
13#[cfg(not(feature = "alloc"))]
14type Inner<K, V, const N: usize> = heapless::LinearMap<K, V, N>;
15
16/// An ordered map based on a B-Tree (with `alloc`) or a linear map (with `heapless`).
17///
18/// When `heapless` feature is enabled, this is a wrapper around `heapless::LinearMap<K, V, N>`.
19///
20/// Note: With heapless, iteration order is insertion order, not key order.
21#[allow(dead_code)]
22pub struct BTreeMap<K, V, const N: usize>(Inner<K, V, N>);
23
24impl<K, V, const N: usize> Clone for BTreeMap<K, V, N>
25where
26    K: Clone + Eq,
27    V: Clone,
28{
29    fn clone(&self) -> Self {
30        Self(self.0.clone())
31    }
32}
33
34impl<K, V, const N: usize> core::fmt::Debug for BTreeMap<K, V, N>
35where
36    K: core::fmt::Debug + Eq,
37    V: core::fmt::Debug,
38{
39    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
40        f.debug_tuple("BTreeMap").field(&self.0).finish()
41    }
42}
43
44#[allow(dead_code)]
45impl<K, V, const N: usize> BTreeMap<K, V, N>
46where
47    K: Ord + Eq,
48{
49    /// Constructs a new, empty map.
50    #[inline]
51    pub fn new() -> Self {
52        Self::default()
53    }
54
55    /// Returns a reference to the value corresponding to the key.
56    #[inline]
57    pub fn get(&self, key: &K) -> Option<&V> {
58        self.0.get(key)
59    }
60
61    /// Returns `true` if the map contains a value for the specified key.
62    #[inline]
63    pub fn contains_key(&self, key: &K) -> bool {
64        #[cfg(feature = "alloc")]
65        {
66            self.0.contains_key(key)
67        }
68        #[cfg(not(feature = "alloc"))]
69        {
70            self.0.get(key).is_some()
71        }
72    }
73
74    /// Inserts a key-value pair into the map.
75    ///
76    /// If the map did not have this key present, `Ok(None)` is returned.
77    /// If the map did have this key present, the value is updated, and `Ok(Some(old_value))` is returned.
78    /// Returns `Err` if the map is at capacity (heapless only).
79    #[inline]
80    pub fn insert(&mut self, key: K, value: V) -> Result<Option<V>> {
81        #[cfg(feature = "alloc")]
82        {
83            Ok(self.0.insert(key, value))
84        }
85        #[cfg(not(feature = "alloc"))]
86        {
87            self.0.insert(key, value).map_err(|_| Error::CapacityExceeded)
88        }
89    }
90
91    /// Removes a key from the map, returning the value at the key if the key was previously in the map.
92    #[inline]
93    pub fn remove(&mut self, key: &K) -> Option<V> {
94        self.0.remove(key)
95    }
96}
97
98#[allow(dead_code)]
99impl<K, V, const N: usize> BTreeMap<K, V, N>
100where
101    K: Eq,
102{
103    /// Returns the number of elements in the map.
104    #[inline]
105    pub fn len(&self) -> usize {
106        self.0.len()
107    }
108
109    /// Returns `true` if the map contains no elements.
110    #[inline]
111    pub fn is_empty(&self) -> bool {
112        self.0.is_empty()
113    }
114
115    /// Clears the map, removing all elements.
116    #[inline]
117    pub fn clear(&mut self) {
118        self.0.clear();
119    }
120
121    /// Returns an iterator over the map's key-value pairs.
122    #[inline]
123    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
124        self.0.iter()
125    }
126
127    /// Returns an iterator over the map's keys.
128    #[inline]
129    pub fn keys(&self) -> impl Iterator<Item = &K> {
130        #[cfg(feature = "alloc")]
131        {
132            self.0.keys()
133        }
134        #[cfg(not(feature = "alloc"))]
135        {
136            self.0.iter().map(|(k, _)| k)
137        }
138    }
139
140    /// Returns an iterator over the map's values.
141    #[inline]
142    pub fn values(&self) -> impl Iterator<Item = &V> {
143        #[cfg(feature = "alloc")]
144        {
145            self.0.values()
146        }
147        #[cfg(not(feature = "alloc"))]
148        {
149            self.0.iter().map(|(_, v)| v)
150        }
151    }
152}
153
154impl<K, V, const N: usize> Default for BTreeMap<K, V, N>
155where
156    K: Ord + Eq,
157{
158    #[inline]
159    fn default() -> Self {
160        #[cfg(feature = "alloc")]
161        {
162            Self(Inner::new())
163        }
164        #[cfg(not(feature = "alloc"))]
165        {
166            Self(Inner::new())
167        }
168    }
169}
170
171impl<K, V, const N: usize> PartialEq for BTreeMap<K, V, N>
172where
173    K: Ord + Eq,
174    V: PartialEq,
175{
176    #[inline]
177    fn eq(&self, other: &Self) -> bool {
178        #[cfg(feature = "alloc")]
179        {
180            self.0 == other.0
181        }
182        #[cfg(not(feature = "alloc"))]
183        {
184            if self.len() != other.len() {
185                return false;
186            }
187            self.iter().all(|(k, v)| other.get(k) == Some(v))
188        }
189    }
190}
191
192impl<K, V, const N: usize> Eq for BTreeMap<K, V, N>
193where
194    K: Ord + Eq,
195    V: Eq,
196{
197}
sigma_bounded/btree_map.rs

sigma_bounded/
btree_map.rs
