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
88                .insert(key, value)
89                .map_err(|_| Error::CapacityExceeded)
90        }
91    }
92
93    /// Removes a key from the map, returning the value at the key if the key was previously in the map.
94    #[inline]
95    pub fn remove(&mut self, key: &K) -> Option<V> {
96        self.0.remove(key)
97    }
98}
99
100#[allow(dead_code)]
101impl<K, V, const N: usize> BTreeMap<K, V, N>
102where
103    K: Eq,
104{
105    /// Returns the number of elements in the map.
106    #[inline]
107    pub fn len(&self) -> usize {
108        self.0.len()
109    }
110
111    /// Returns `true` if the map contains no elements.
112    #[inline]
113    pub fn is_empty(&self) -> bool {
114        self.0.is_empty()
115    }
116
117    /// Clears the map, removing all elements.
118    #[inline]
119    pub fn clear(&mut self) {
120        self.0.clear();
121    }
122
123    /// Returns an iterator over the map's key-value pairs.
124    #[inline]
125    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
126        self.0.iter()
127    }
128
129    /// Returns an iterator over the map's keys.
130    #[inline]
131    pub fn keys(&self) -> impl Iterator<Item = &K> {
132        #[cfg(feature = "alloc")]
133        {
134            self.0.keys()
135        }
136        #[cfg(not(feature = "alloc"))]
137        {
138            self.0.iter().map(|(k, _)| k)
139        }
140    }
141
142    /// Returns an iterator over the map's values.
143    #[inline]
144    pub fn values(&self) -> impl Iterator<Item = &V> {
145        #[cfg(feature = "alloc")]
146        {
147            self.0.values()
148        }
149        #[cfg(not(feature = "alloc"))]
150        {
151            self.0.iter().map(|(_, v)| v)
152        }
153    }
154}
155
156impl<K, V, const N: usize> Default for BTreeMap<K, V, N>
157where
158    K: Ord + Eq,
159{
160    #[inline]
161    fn default() -> Self {
162        #[cfg(feature = "alloc")]
163        {
164            Self(Inner::new())
165        }
166        #[cfg(not(feature = "alloc"))]
167        {
168            Self(Inner::new())
169        }
170    }
171}
172
173impl<K, V, const N: usize> PartialEq for BTreeMap<K, V, N>
174where
175    K: Ord + Eq,
176    V: PartialEq,
177{
178    #[inline]
179    fn eq(&self, other: &Self) -> bool {
180        #[cfg(feature = "alloc")]
181        {
182            self.0 == other.0
183        }
184        #[cfg(not(feature = "alloc"))]
185        {
186            if self.len() != other.len() {
187                return false;
188            }
189            self.iter().all(|(k, v)| other.get(k) == Some(v))
190        }
191    }
192}
193
194impl<K, V, const N: usize> Eq for BTreeMap<K, V, N>
195where
196    K: Ord + Eq,
197    V: Eq,
198{
199}
sigma_bounded/btree_map.rs

sigma_bounded/
btree_map.rs
