]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use core::borrow::Borrow; |
1a4d82fc | 2 | use core::cmp::Ordering; |
3dfed10e | 3 | use core::fmt::{self, Debug}; |
1a4d82fc | 4 | use core::hash::{Hash, Hasher}; |
29967ef6 | 5 | use core::iter::{FromIterator, FusedIterator}; |
9cc50fc6 | 6 | use core::marker::PhantomData; |
ba9703b0 | 7 | use core::mem::{self, ManuallyDrop}; |
9fa01778 | 8 | use core::ops::{Index, RangeBounds}; |
3dfed10e | 9 | use core::ptr; |
1a4d82fc | 10 | |
1b1a35ee | 11 | use super::borrow::DormantMutRef; |
29967ef6 | 12 | use super::node::{self, marker, ForceResult::*, Handle, NodeRef}; |
9fa01778 | 13 | use super::search::{self, SearchResult::*}; |
74b04a01 | 14 | use super::unwrap_unchecked; |
9cc50fc6 | 15 | |
29967ef6 XL |
16 | mod entry; |
17 | pub use entry::{Entry, OccupiedEntry, VacantEntry}; | |
9fa01778 | 18 | use Entry::*; |
29967ef6 XL |
19 | |
20 | /// Minimum number of elements in nodes that are not a root. | |
21 | /// We might temporarily have fewer elements during methods. | |
22 | pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT; | |
1a4d82fc | 23 | |
1a4d82fc JJ |
24 | /// A map based on a B-Tree. |
25 | /// | |
26 | /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing | |
27 | /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal | |
28 | /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of | |
29 | /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this | |
30 | /// is done is *very* inefficient for modern computer architectures. In particular, every element | |
31 | /// is stored in its own individually heap-allocated node. This means that every single insertion | |
32 | /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these | |
33 | /// are both notably expensive things to do in practice, we are forced to at very least reconsider | |
34 | /// the BST strategy. | |
35 | /// | |
36 | /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing | |
37 | /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in | |
38 | /// searches. However, this does mean that searches will have to do *more* comparisons on average. | |
39 | /// The precise number of comparisons depends on the node search strategy used. For optimal cache | |
40 | /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search | |
41 | /// the node using binary search. As a compromise, one could also perform a linear search | |
42 | /// that initially only checks every i<sup>th</sup> element for some choice of i. | |
43 | /// | |
44 | /// Currently, our implementation simply performs naive linear search. This provides excellent | |
45 | /// performance on *small* nodes of elements which are cheap to compare. However in the future we | |
46 | /// would like to further explore choosing the optimal search strategy based on the choice of B, | |
47 | /// and possibly other factors. Using linear search, searching for a random element is expected | |
ba9703b0 | 48 | /// to take O(B * log(n)) comparisons, which is generally worse than a BST. In practice, |
85aaf69f | 49 | /// however, performance is excellent. |
c34b1796 AL |
50 | /// |
51 | /// It is a logic error for a key to be modified in such a way that the key's ordering relative to | |
9e0c209e SL |
52 | /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is |
53 | /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. | |
54 | /// | |
3dfed10e XL |
55 | /// [`Cell`]: core::cell::Cell |
56 | /// [`RefCell`]: core::cell::RefCell | |
54a0048b SL |
57 | /// |
58 | /// # Examples | |
59 | /// | |
60 | /// ``` | |
61 | /// use std::collections::BTreeMap; | |
62 | /// | |
63 | /// // type inference lets us omit an explicit type signature (which | |
64 | /// // would be `BTreeMap<&str, &str>` in this example). | |
65 | /// let mut movie_reviews = BTreeMap::new(); | |
66 | /// | |
3157f602 | 67 | /// // review some movies. |
54a0048b SL |
68 | /// movie_reviews.insert("Office Space", "Deals with real issues in the workplace."); |
69 | /// movie_reviews.insert("Pulp Fiction", "Masterpiece."); | |
70 | /// movie_reviews.insert("The Godfather", "Very enjoyable."); | |
0bf4aa26 | 71 | /// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot."); |
54a0048b SL |
72 | /// |
73 | /// // check for a specific one. | |
74 | /// if !movie_reviews.contains_key("Les Misérables") { | |
75 | /// println!("We've got {} reviews, but Les Misérables ain't one.", | |
76 | /// movie_reviews.len()); | |
77 | /// } | |
78 | /// | |
79 | /// // oops, this review has a lot of spelling mistakes, let's delete it. | |
80 | /// movie_reviews.remove("The Blues Brothers"); | |
81 | /// | |
82 | /// // look up the values associated with some keys. | |
83 | /// let to_find = ["Up!", "Office Space"]; | |
416331ca XL |
84 | /// for movie in &to_find { |
85 | /// match movie_reviews.get(movie) { | |
86 | /// Some(review) => println!("{}: {}", movie, review), | |
87 | /// None => println!("{} is unreviewed.", movie) | |
54a0048b SL |
88 | /// } |
89 | /// } | |
90 | /// | |
0731742a XL |
91 | /// // Look up the value for a key (will panic if the key is not found). |
92 | /// println!("Movie review: {}", movie_reviews["Office Space"]); | |
93 | /// | |
54a0048b SL |
94 | /// // iterate over everything. |
95 | /// for (movie, review) in &movie_reviews { | |
96 | /// println!("{}: \"{}\"", movie, review); | |
97 | /// } | |
98 | /// ``` | |
99 | /// | |
1b1a35ee XL |
100 | /// `BTreeMap` also implements an [`Entry API`], which allows for more complex |
101 | /// methods of getting, setting, updating and removing keys and their values: | |
102 | /// | |
103 | /// [`Entry API`]: BTreeMap::entry | |
54a0048b SL |
104 | /// |
105 | /// ``` | |
106 | /// use std::collections::BTreeMap; | |
107 | /// | |
108 | /// // type inference lets us omit an explicit type signature (which | |
109 | /// // would be `BTreeMap<&str, u8>` in this example). | |
110 | /// let mut player_stats = BTreeMap::new(); | |
111 | /// | |
112 | /// fn random_stat_buff() -> u8 { | |
113 | /// // could actually return some random value here - let's just return | |
114 | /// // some fixed value for now | |
115 | /// 42 | |
116 | /// } | |
117 | /// | |
118 | /// // insert a key only if it doesn't already exist | |
119 | /// player_stats.entry("health").or_insert(100); | |
120 | /// | |
121 | /// // insert a key using a function that provides a new value only if it | |
122 | /// // doesn't already exist | |
123 | /// player_stats.entry("defence").or_insert_with(random_stat_buff); | |
124 | /// | |
125 | /// // update a key, guarding against the key possibly not being set | |
126 | /// let stat = player_stats.entry("attack").or_insert(100); | |
127 | /// *stat += random_stat_buff(); | |
128 | /// ``` | |
85aaf69f | 129 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 130 | pub struct BTreeMap<K, V> { |
ba9703b0 | 131 | root: Option<node::Root<K, V>>, |
3157f602 | 132 | length: usize, |
9cc50fc6 SL |
133 | } |
134 | ||
c30ab7b3 | 135 | #[stable(feature = "btree_drop", since = "1.7.0")] |
32a655c1 | 136 | unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> { |
9cc50fc6 SL |
137 | fn drop(&mut self) { |
138 | unsafe { | |
cc61c64b | 139 | drop(ptr::read(self).into_iter()); |
9cc50fc6 SL |
140 | } |
141 | } | |
142 | } | |
143 | ||
c30ab7b3 | 144 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
145 | impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> { |
146 | fn clone(&self) -> BTreeMap<K, V> { | |
8faf50e0 | 147 | fn clone_subtree<'a, K: Clone, V: Clone>( |
dfeec247 | 148 | node: node::NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>, |
8faf50e0 | 149 | ) -> BTreeMap<K, V> |
dfeec247 XL |
150 | where |
151 | K: 'a, | |
152 | V: 'a, | |
8faf50e0 | 153 | { |
9cc50fc6 SL |
154 | match node.force() { |
155 | Leaf(leaf) => { | |
ba9703b0 | 156 | let mut out_tree = BTreeMap { root: Some(node::Root::new_leaf()), length: 0 }; |
9cc50fc6 SL |
157 | |
158 | { | |
3dfed10e XL |
159 | let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped |
160 | let mut out_node = match root.node_as_mut().force() { | |
9cc50fc6 | 161 | Leaf(leaf) => leaf, |
3157f602 | 162 | Internal(_) => unreachable!(), |
9cc50fc6 SL |
163 | }; |
164 | ||
165 | let mut in_edge = leaf.first_edge(); | |
166 | while let Ok(kv) = in_edge.right_kv() { | |
167 | let (k, v) = kv.into_kv(); | |
168 | in_edge = kv.right_edge(); | |
169 | ||
170 | out_node.push(k.clone(), v.clone()); | |
171 | out_tree.length += 1; | |
172 | } | |
173 | } | |
174 | ||
175 | out_tree | |
3157f602 | 176 | } |
9cc50fc6 SL |
177 | Internal(internal) => { |
178 | let mut out_tree = clone_subtree(internal.first_edge().descend()); | |
179 | ||
180 | { | |
3dfed10e XL |
181 | let out_root = BTreeMap::ensure_is_owned(&mut out_tree.root); |
182 | let mut out_node = out_root.push_internal_level(); | |
9cc50fc6 SL |
183 | let mut in_edge = internal.first_edge(); |
184 | while let Ok(kv) = in_edge.right_kv() { | |
185 | let (k, v) = kv.into_kv(); | |
186 | in_edge = kv.right_edge(); | |
187 | ||
188 | let k = (*k).clone(); | |
189 | let v = (*v).clone(); | |
190 | let subtree = clone_subtree(in_edge.descend()); | |
191 | ||
192 | // We can't destructure subtree directly | |
193 | // because BTreeMap implements Drop | |
194 | let (subroot, sublength) = unsafe { | |
ba9703b0 | 195 | let subtree = ManuallyDrop::new(subtree); |
9cc50fc6 SL |
196 | let root = ptr::read(&subtree.root); |
197 | let length = subtree.length; | |
9cc50fc6 SL |
198 | (root, length) |
199 | }; | |
200 | ||
ba9703b0 | 201 | out_node.push(k, v, subroot.unwrap_or_else(node::Root::new_leaf)); |
9cc50fc6 SL |
202 | out_tree.length += 1 + sublength; |
203 | } | |
204 | } | |
205 | ||
206 | out_tree | |
207 | } | |
208 | } | |
209 | } | |
210 | ||
416331ca | 211 | if self.is_empty() { |
8faf50e0 XL |
212 | // Ideally we'd call `BTreeMap::new` here, but that has the `K: |
213 | // Ord` constraint, which this method lacks. | |
ba9703b0 | 214 | BTreeMap { root: None, length: 0 } |
8faf50e0 | 215 | } else { |
3dfed10e | 216 | clone_subtree(self.root.as_ref().unwrap().node_as_ref()) // unwrap succeeds because not empty |
8faf50e0 | 217 | } |
9cc50fc6 | 218 | } |
1a4d82fc JJ |
219 | } |
220 | ||
9cc50fc6 | 221 | impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()> |
dfeec247 XL |
222 | where |
223 | K: Borrow<Q> + Ord, | |
224 | Q: Ord, | |
9cc50fc6 SL |
225 | { |
226 | type Key = K; | |
227 | ||
228 | fn get(&self, key: &Q) -> Option<&K> { | |
3dfed10e XL |
229 | let root_node = self.root.as_ref()?.node_as_ref(); |
230 | match search::search_tree(root_node, key) { | |
9cc50fc6 | 231 | Found(handle) => Some(handle.into_kv().0), |
3157f602 | 232 | GoDown(_) => None, |
9cc50fc6 SL |
233 | } |
234 | } | |
235 | ||
236 | fn take(&mut self, key: &Q) -> Option<K> { | |
1b1a35ee XL |
237 | let (map, dormant_map) = DormantMutRef::new(self); |
238 | let root_node = map.root.as_mut()?.node_as_mut(); | |
3dfed10e | 239 | match search::search_tree(root_node, key) { |
1b1a35ee XL |
240 | Found(handle) => { |
241 | Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_kv().0) | |
242 | } | |
3157f602 | 243 | GoDown(_) => None, |
9cc50fc6 SL |
244 | } |
245 | } | |
246 | ||
247 | fn replace(&mut self, key: K) -> Option<K> { | |
1b1a35ee XL |
248 | let (map, dormant_map) = DormantMutRef::new(self); |
249 | let root_node = Self::ensure_is_owned(&mut map.root).node_as_mut(); | |
250 | match search::search_tree::<marker::Mut<'_>, K, (), K>(root_node, &key) { | |
3dfed10e | 251 | Found(handle) => Some(mem::replace(handle.into_key_mut(), key)), |
9cc50fc6 | 252 | GoDown(handle) => { |
1b1a35ee | 253 | VacantEntry { key, handle, dormant_map, _marker: PhantomData }.insert(()); |
9cc50fc6 SL |
254 | None |
255 | } | |
256 | } | |
257 | } | |
1a4d82fc JJ |
258 | } |
259 | ||
cc61c64b XL |
260 | /// An iterator over the entries of a `BTreeMap`. |
261 | /// | |
262 | /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its | |
263 | /// documentation for more. | |
264 | /// | |
3dfed10e | 265 | /// [`iter`]: BTreeMap::iter |
85aaf69f | 266 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 267 | pub struct Iter<'a, K: 'a, V: 'a> { |
9cc50fc6 | 268 | range: Range<'a, K, V>, |
3157f602 | 269 | length: usize, |
1a4d82fc JJ |
270 | } |
271 | ||
8bb4bdeb | 272 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
273 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { |
274 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
8bb4bdeb XL |
275 | f.debug_list().entries(self.clone()).finish() |
276 | } | |
277 | } | |
278 | ||
cc61c64b XL |
279 | /// A mutable iterator over the entries of a `BTreeMap`. |
280 | /// | |
281 | /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its | |
282 | /// documentation for more. | |
283 | /// | |
3dfed10e | 284 | /// [`iter_mut`]: BTreeMap::iter_mut |
85aaf69f | 285 | #[stable(feature = "rust1", since = "1.0.0")] |
8bb4bdeb | 286 | #[derive(Debug)] |
1a4d82fc | 287 | pub struct IterMut<'a, K: 'a, V: 'a> { |
9cc50fc6 | 288 | range: RangeMut<'a, K, V>, |
3157f602 | 289 | length: usize, |
1a4d82fc JJ |
290 | } |
291 | ||
cc61c64b XL |
292 | /// An owning iterator over the entries of a `BTreeMap`. |
293 | /// | |
dfeec247 | 294 | /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`] |
cc61c64b XL |
295 | /// (provided by the `IntoIterator` trait). See its documentation for more. |
296 | /// | |
3dfed10e | 297 | /// [`into_iter`]: IntoIterator::into_iter |
85aaf69f | 298 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 299 | pub struct IntoIter<K, V> { |
ba9703b0 XL |
300 | front: Option<Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>>, |
301 | back: Option<Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>>, | |
3157f602 | 302 | length: usize, |
1a4d82fc JJ |
303 | } |
304 | ||
1b1a35ee XL |
305 | impl<K, V> IntoIter<K, V> { |
306 | /// Returns an iterator of references over the remaining items. | |
307 | #[inline] | |
308 | pub(super) fn iter(&self) -> Iter<'_, K, V> { | |
ba9703b0 XL |
309 | let range = Range { |
310 | front: self.front.as_ref().map(|f| f.reborrow()), | |
311 | back: self.back.as_ref().map(|b| b.reborrow()), | |
312 | }; | |
1b1a35ee XL |
313 | |
314 | Iter { range: range, length: self.length } | |
315 | } | |
316 | } | |
317 | ||
318 | #[stable(feature = "collection_debug", since = "1.17.0")] | |
319 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> { | |
320 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
321 | f.debug_list().entries(self.iter()).finish() | |
8bb4bdeb XL |
322 | } |
323 | } | |
324 | ||
cc61c64b XL |
325 | /// An iterator over the keys of a `BTreeMap`. |
326 | /// | |
327 | /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its | |
328 | /// documentation for more. | |
329 | /// | |
3dfed10e | 330 | /// [`keys`]: BTreeMap::keys |
85aaf69f | 331 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 332 | pub struct Keys<'a, K: 'a, V: 'a> { |
9cc50fc6 | 333 | inner: Iter<'a, K, V>, |
1a4d82fc JJ |
334 | } |
335 | ||
8bb4bdeb | 336 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
337 | impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> { |
338 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
041b39d2 | 339 | f.debug_list().entries(self.clone()).finish() |
8bb4bdeb XL |
340 | } |
341 | } | |
342 | ||
cc61c64b XL |
343 | /// An iterator over the values of a `BTreeMap`. |
344 | /// | |
345 | /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its | |
346 | /// documentation for more. | |
347 | /// | |
3dfed10e | 348 | /// [`values`]: BTreeMap::values |
85aaf69f | 349 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 350 | pub struct Values<'a, K: 'a, V: 'a> { |
9cc50fc6 | 351 | inner: Iter<'a, K, V>, |
85aaf69f SL |
352 | } |
353 | ||
8bb4bdeb | 354 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
355 | impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> { |
356 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
041b39d2 | 357 | f.debug_list().entries(self.clone()).finish() |
8bb4bdeb XL |
358 | } |
359 | } | |
360 | ||
cc61c64b XL |
361 | /// A mutable iterator over the values of a `BTreeMap`. |
362 | /// | |
363 | /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its | |
364 | /// documentation for more. | |
365 | /// | |
3dfed10e | 366 | /// [`values_mut`]: BTreeMap::values_mut |
a7813a04 | 367 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
54a0048b SL |
368 | pub struct ValuesMut<'a, K: 'a, V: 'a> { |
369 | inner: IterMut<'a, K, V>, | |
370 | } | |
371 | ||
1b1a35ee XL |
372 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
373 | impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> { | |
374 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
375 | f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish() | |
376 | } | |
377 | } | |
378 | ||
3dfed10e XL |
379 | /// An owning iterator over the keys of a `BTreeMap`. |
380 | /// | |
381 | /// This `struct` is created by the [`into_keys`] method on [`BTreeMap`]. | |
382 | /// See its documentation for more. | |
383 | /// | |
384 | /// [`into_keys`]: BTreeMap::into_keys | |
385 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
3dfed10e XL |
386 | pub struct IntoKeys<K, V> { |
387 | inner: IntoIter<K, V>, | |
388 | } | |
389 | ||
1b1a35ee XL |
390 | #[unstable(feature = "map_into_keys_values", issue = "75294")] |
391 | impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> { | |
392 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
393 | f.debug_list().entries(self.inner.iter().map(|(key, _)| key)).finish() | |
394 | } | |
395 | } | |
396 | ||
3dfed10e XL |
397 | /// An owning iterator over the values of a `BTreeMap`. |
398 | /// | |
399 | /// This `struct` is created by the [`into_values`] method on [`BTreeMap`]. | |
400 | /// See its documentation for more. | |
401 | /// | |
402 | /// [`into_values`]: BTreeMap::into_values | |
403 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
3dfed10e XL |
404 | pub struct IntoValues<K, V> { |
405 | inner: IntoIter<K, V>, | |
406 | } | |
407 | ||
1b1a35ee XL |
408 | #[unstable(feature = "map_into_keys_values", issue = "75294")] |
409 | impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> { | |
410 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
411 | f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish() | |
412 | } | |
413 | } | |
414 | ||
cc61c64b XL |
415 | /// An iterator over a sub-range of entries in a `BTreeMap`. |
416 | /// | |
417 | /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its | |
418 | /// documentation for more. | |
419 | /// | |
3dfed10e | 420 | /// [`range`]: BTreeMap::range |
8bb4bdeb | 421 | #[stable(feature = "btree_range", since = "1.17.0")] |
85aaf69f | 422 | pub struct Range<'a, K: 'a, V: 'a> { |
ba9703b0 XL |
423 | front: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>>, |
424 | back: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>>, | |
85aaf69f SL |
425 | } |
426 | ||
8bb4bdeb | 427 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
428 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> { |
429 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
8bb4bdeb XL |
430 | f.debug_list().entries(self.clone()).finish() |
431 | } | |
432 | } | |
433 | ||
cc61c64b XL |
434 | /// A mutable iterator over a sub-range of entries in a `BTreeMap`. |
435 | /// | |
436 | /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its | |
437 | /// documentation for more. | |
438 | /// | |
3dfed10e | 439 | /// [`range_mut`]: BTreeMap::range_mut |
8bb4bdeb | 440 | #[stable(feature = "btree_range", since = "1.17.0")] |
85aaf69f | 441 | pub struct RangeMut<'a, K: 'a, V: 'a> { |
1b1a35ee XL |
442 | front: Option<Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge>>, |
443 | back: Option<Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge>>, | |
9cc50fc6 SL |
444 | |
445 | // Be invariant in `K` and `V` | |
446 | _marker: PhantomData<&'a mut (K, V)>, | |
1a4d82fc JJ |
447 | } |
448 | ||
8bb4bdeb | 449 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
450 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> { |
451 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
ba9703b0 XL |
452 | let range = Range { |
453 | front: self.front.as_ref().map(|f| f.reborrow()), | |
454 | back: self.back.as_ref().map(|b| b.reborrow()), | |
455 | }; | |
8bb4bdeb XL |
456 | f.debug_list().entries(range).finish() |
457 | } | |
458 | } | |
459 | ||
1a4d82fc | 460 | impl<K: Ord, V> BTreeMap<K, V> { |
f035d41b XL |
461 | /// Makes a new empty BTreeMap. |
462 | /// | |
463 | /// Does not allocate anything on its own. | |
54a0048b SL |
464 | /// |
465 | /// # Examples | |
466 | /// | |
467 | /// Basic usage: | |
468 | /// | |
469 | /// ``` | |
470 | /// use std::collections::BTreeMap; | |
471 | /// | |
472 | /// let mut map = BTreeMap::new(); | |
473 | /// | |
474 | /// // entries can now be inserted into the empty map | |
475 | /// map.insert(1, "a"); | |
476 | /// ``` | |
85aaf69f | 477 | #[stable(feature = "rust1", since = "1.0.0")] |
f9f354fc XL |
478 | #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] |
479 | pub const fn new() -> BTreeMap<K, V> { | |
ba9703b0 | 480 | BTreeMap { root: None, length: 0 } |
1a4d82fc JJ |
481 | } |
482 | ||
dfeec247 | 483 | /// Clears the map, removing all elements. |
1a4d82fc JJ |
484 | /// |
485 | /// # Examples | |
486 | /// | |
54a0048b SL |
487 | /// Basic usage: |
488 | /// | |
1a4d82fc JJ |
489 | /// ``` |
490 | /// use std::collections::BTreeMap; | |
491 | /// | |
492 | /// let mut a = BTreeMap::new(); | |
85aaf69f | 493 | /// a.insert(1, "a"); |
1a4d82fc JJ |
494 | /// a.clear(); |
495 | /// assert!(a.is_empty()); | |
496 | /// ``` | |
85aaf69f | 497 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 498 | pub fn clear(&mut self) { |
9cc50fc6 | 499 | *self = BTreeMap::new(); |
1a4d82fc JJ |
500 | } |
501 | ||
1a4d82fc JJ |
502 | /// Returns a reference to the value corresponding to the key. |
503 | /// | |
504 | /// The key may be any borrowed form of the map's key type, but the ordering | |
505 | /// on the borrowed form *must* match the ordering on the key type. | |
506 | /// | |
507 | /// # Examples | |
508 | /// | |
54a0048b SL |
509 | /// Basic usage: |
510 | /// | |
1a4d82fc JJ |
511 | /// ``` |
512 | /// use std::collections::BTreeMap; | |
513 | /// | |
514 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 515 | /// map.insert(1, "a"); |
1a4d82fc JJ |
516 | /// assert_eq!(map.get(&1), Some(&"a")); |
517 | /// assert_eq!(map.get(&2), None); | |
518 | /// ``` | |
85aaf69f | 519 | #[stable(feature = "rust1", since = "1.0.0")] |
3157f602 | 520 | pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> |
dfeec247 XL |
521 | where |
522 | K: Borrow<Q>, | |
523 | Q: Ord, | |
3157f602 | 524 | { |
3dfed10e XL |
525 | let root_node = self.root.as_ref()?.node_as_ref(); |
526 | match search::search_tree(root_node, key) { | |
9cc50fc6 | 527 | Found(handle) => Some(handle.into_kv().1), |
3157f602 | 528 | GoDown(_) => None, |
1a4d82fc JJ |
529 | } |
530 | } | |
531 | ||
0531ce1d XL |
532 | /// Returns the key-value pair corresponding to the supplied key. |
533 | /// | |
534 | /// The supplied key may be any borrowed form of the map's key type, but the ordering | |
535 | /// on the borrowed form *must* match the ordering on the key type. | |
536 | /// | |
537 | /// # Examples | |
538 | /// | |
539 | /// ``` | |
0531ce1d XL |
540 | /// use std::collections::BTreeMap; |
541 | /// | |
542 | /// let mut map = BTreeMap::new(); | |
543 | /// map.insert(1, "a"); | |
544 | /// assert_eq!(map.get_key_value(&1), Some((&1, &"a"))); | |
545 | /// assert_eq!(map.get_key_value(&2), None); | |
546 | /// ``` | |
e74abb32 | 547 | #[stable(feature = "map_get_key_value", since = "1.40.0")] |
0531ce1d | 548 | pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)> |
dfeec247 XL |
549 | where |
550 | K: Borrow<Q>, | |
551 | Q: Ord, | |
0531ce1d | 552 | { |
3dfed10e XL |
553 | let root_node = self.root.as_ref()?.node_as_ref(); |
554 | match search::search_tree(root_node, k) { | |
0531ce1d XL |
555 | Found(handle) => Some(handle.into_kv()), |
556 | GoDown(_) => None, | |
557 | } | |
558 | } | |
559 | ||
60c5eb7d XL |
560 | /// Returns the first key-value pair in the map. |
561 | /// The key in this pair is the minimum key in the map. | |
562 | /// | |
563 | /// # Examples | |
564 | /// | |
565 | /// Basic usage: | |
566 | /// | |
567 | /// ``` | |
568 | /// #![feature(map_first_last)] | |
569 | /// use std::collections::BTreeMap; | |
570 | /// | |
571 | /// let mut map = BTreeMap::new(); | |
572 | /// assert_eq!(map.first_key_value(), None); | |
573 | /// map.insert(1, "b"); | |
574 | /// map.insert(2, "a"); | |
575 | /// assert_eq!(map.first_key_value(), Some((&1, &"b"))); | |
576 | /// ``` | |
577 | #[unstable(feature = "map_first_last", issue = "62924")] | |
ba9703b0 | 578 | pub fn first_key_value(&self) -> Option<(&K, &V)> { |
3dfed10e XL |
579 | let root_node = self.root.as_ref()?.node_as_ref(); |
580 | root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv) | |
60c5eb7d XL |
581 | } |
582 | ||
583 | /// Returns the first entry in the map for in-place manipulation. | |
584 | /// The key of this entry is the minimum key in the map. | |
585 | /// | |
586 | /// # Examples | |
587 | /// | |
ba9703b0 XL |
588 | /// ``` |
589 | /// #![feature(map_first_last)] | |
590 | /// use std::collections::BTreeMap; | |
591 | /// | |
592 | /// let mut map = BTreeMap::new(); | |
593 | /// map.insert(1, "a"); | |
594 | /// map.insert(2, "b"); | |
595 | /// if let Some(mut entry) = map.first_entry() { | |
596 | /// if *entry.key() > 0 { | |
597 | /// entry.insert("first"); | |
598 | /// } | |
599 | /// } | |
600 | /// assert_eq!(*map.get(&1).unwrap(), "first"); | |
601 | /// assert_eq!(*map.get(&2).unwrap(), "b"); | |
602 | /// ``` | |
603 | #[unstable(feature = "map_first_last", issue = "62924")] | |
604 | pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> { | |
1b1a35ee XL |
605 | let (map, dormant_map) = DormantMutRef::new(self); |
606 | let root_node = map.root.as_mut()?.node_as_mut(); | |
3dfed10e | 607 | let kv = root_node.first_leaf_edge().right_kv().ok()?; |
1b1a35ee | 608 | Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData }) |
ba9703b0 XL |
609 | } |
610 | ||
611 | /// Removes and returns the first element in the map. | |
612 | /// The key of this element is the minimum key that was in the map. | |
613 | /// | |
614 | /// # Examples | |
615 | /// | |
616 | /// Draining elements in ascending order, while keeping a usable map each iteration. | |
60c5eb7d XL |
617 | /// |
618 | /// ``` | |
619 | /// #![feature(map_first_last)] | |
620 | /// use std::collections::BTreeMap; | |
621 | /// | |
622 | /// let mut map = BTreeMap::new(); | |
623 | /// map.insert(1, "a"); | |
624 | /// map.insert(2, "b"); | |
ba9703b0 XL |
625 | /// while let Some((key, _val)) = map.pop_first() { |
626 | /// assert!(map.iter().all(|(k, _v)| *k > key)); | |
60c5eb7d | 627 | /// } |
ba9703b0 | 628 | /// assert!(map.is_empty()); |
60c5eb7d XL |
629 | /// ``` |
630 | #[unstable(feature = "map_first_last", issue = "62924")] | |
ba9703b0 XL |
631 | pub fn pop_first(&mut self) -> Option<(K, V)> { |
632 | self.first_entry().map(|entry| entry.remove_entry()) | |
60c5eb7d XL |
633 | } |
634 | ||
635 | /// Returns the last key-value pair in the map. | |
636 | /// The key in this pair is the maximum key in the map. | |
637 | /// | |
638 | /// # Examples | |
639 | /// | |
640 | /// Basic usage: | |
641 | /// | |
642 | /// ``` | |
643 | /// #![feature(map_first_last)] | |
644 | /// use std::collections::BTreeMap; | |
645 | /// | |
646 | /// let mut map = BTreeMap::new(); | |
647 | /// map.insert(1, "b"); | |
648 | /// map.insert(2, "a"); | |
649 | /// assert_eq!(map.last_key_value(), Some((&2, &"a"))); | |
650 | /// ``` | |
651 | #[unstable(feature = "map_first_last", issue = "62924")] | |
ba9703b0 | 652 | pub fn last_key_value(&self) -> Option<(&K, &V)> { |
3dfed10e XL |
653 | let root_node = self.root.as_ref()?.node_as_ref(); |
654 | root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv) | |
60c5eb7d XL |
655 | } |
656 | ||
657 | /// Returns the last entry in the map for in-place manipulation. | |
658 | /// The key of this entry is the maximum key in the map. | |
659 | /// | |
660 | /// # Examples | |
661 | /// | |
ba9703b0 XL |
662 | /// ``` |
663 | /// #![feature(map_first_last)] | |
664 | /// use std::collections::BTreeMap; | |
665 | /// | |
666 | /// let mut map = BTreeMap::new(); | |
667 | /// map.insert(1, "a"); | |
668 | /// map.insert(2, "b"); | |
669 | /// if let Some(mut entry) = map.last_entry() { | |
670 | /// if *entry.key() > 0 { | |
671 | /// entry.insert("last"); | |
672 | /// } | |
673 | /// } | |
674 | /// assert_eq!(*map.get(&1).unwrap(), "a"); | |
675 | /// assert_eq!(*map.get(&2).unwrap(), "last"); | |
676 | /// ``` | |
677 | #[unstable(feature = "map_first_last", issue = "62924")] | |
678 | pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> { | |
1b1a35ee XL |
679 | let (map, dormant_map) = DormantMutRef::new(self); |
680 | let root_node = map.root.as_mut()?.node_as_mut(); | |
3dfed10e | 681 | let kv = root_node.last_leaf_edge().left_kv().ok()?; |
1b1a35ee | 682 | Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData }) |
ba9703b0 XL |
683 | } |
684 | ||
685 | /// Removes and returns the last element in the map. | |
686 | /// The key of this element is the maximum key that was in the map. | |
687 | /// | |
688 | /// # Examples | |
689 | /// | |
690 | /// Draining elements in descending order, while keeping a usable map each iteration. | |
60c5eb7d XL |
691 | /// |
692 | /// ``` | |
693 | /// #![feature(map_first_last)] | |
694 | /// use std::collections::BTreeMap; | |
695 | /// | |
696 | /// let mut map = BTreeMap::new(); | |
697 | /// map.insert(1, "a"); | |
698 | /// map.insert(2, "b"); | |
ba9703b0 XL |
699 | /// while let Some((key, _val)) = map.pop_last() { |
700 | /// assert!(map.iter().all(|(k, _v)| *k < key)); | |
60c5eb7d | 701 | /// } |
ba9703b0 | 702 | /// assert!(map.is_empty()); |
60c5eb7d XL |
703 | /// ``` |
704 | #[unstable(feature = "map_first_last", issue = "62924")] | |
ba9703b0 XL |
705 | pub fn pop_last(&mut self) -> Option<(K, V)> { |
706 | self.last_entry().map(|entry| entry.remove_entry()) | |
60c5eb7d XL |
707 | } |
708 | ||
cc61c64b | 709 | /// Returns `true` if the map contains a value for the specified key. |
1a4d82fc JJ |
710 | /// |
711 | /// The key may be any borrowed form of the map's key type, but the ordering | |
712 | /// on the borrowed form *must* match the ordering on the key type. | |
713 | /// | |
714 | /// # Examples | |
715 | /// | |
54a0048b SL |
716 | /// Basic usage: |
717 | /// | |
1a4d82fc JJ |
718 | /// ``` |
719 | /// use std::collections::BTreeMap; | |
720 | /// | |
721 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 722 | /// map.insert(1, "a"); |
1a4d82fc JJ |
723 | /// assert_eq!(map.contains_key(&1), true); |
724 | /// assert_eq!(map.contains_key(&2), false); | |
725 | /// ``` | |
85aaf69f | 726 | #[stable(feature = "rust1", since = "1.0.0")] |
3157f602 | 727 | pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool |
dfeec247 XL |
728 | where |
729 | K: Borrow<Q>, | |
730 | Q: Ord, | |
3157f602 | 731 | { |
1a4d82fc JJ |
732 | self.get(key).is_some() |
733 | } | |
734 | ||
735 | /// Returns a mutable reference to the value corresponding to the key. | |
736 | /// | |
737 | /// The key may be any borrowed form of the map's key type, but the ordering | |
738 | /// on the borrowed form *must* match the ordering on the key type. | |
739 | /// | |
740 | /// # Examples | |
741 | /// | |
54a0048b SL |
742 | /// Basic usage: |
743 | /// | |
1a4d82fc JJ |
744 | /// ``` |
745 | /// use std::collections::BTreeMap; | |
746 | /// | |
747 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 748 | /// map.insert(1, "a"); |
9346a6ac AL |
749 | /// if let Some(x) = map.get_mut(&1) { |
750 | /// *x = "b"; | |
1a4d82fc | 751 | /// } |
c34b1796 | 752 | /// assert_eq!(map[&1], "b"); |
1a4d82fc JJ |
753 | /// ``` |
754 | // See `get` for implementation notes, this is basically a copy-paste with mut's added | |
85aaf69f | 755 | #[stable(feature = "rust1", since = "1.0.0")] |
3157f602 | 756 | pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> |
dfeec247 XL |
757 | where |
758 | K: Borrow<Q>, | |
759 | Q: Ord, | |
3157f602 | 760 | { |
3dfed10e XL |
761 | let root_node = self.root.as_mut()?.node_as_mut(); |
762 | match search::search_tree(root_node, key) { | |
763 | Found(handle) => Some(handle.into_val_mut()), | |
3157f602 | 764 | GoDown(_) => None, |
1a4d82fc JJ |
765 | } |
766 | } | |
767 | ||
b039eaaf SL |
768 | /// Inserts a key-value pair into the map. |
769 | /// | |
770 | /// If the map did not have this key present, `None` is returned. | |
771 | /// | |
7453a54e SL |
772 | /// If the map did have this key present, the value is updated, and the old |
773 | /// value is returned. The key is not updated, though; this matters for | |
774 | /// types that can be `==` without being identical. See the [module-level | |
775 | /// documentation] for more. | |
b039eaaf SL |
776 | /// |
777 | /// [module-level documentation]: index.html#insert-and-complex-keys | |
1a4d82fc JJ |
778 | /// |
779 | /// # Examples | |
780 | /// | |
54a0048b SL |
781 | /// Basic usage: |
782 | /// | |
1a4d82fc JJ |
783 | /// ``` |
784 | /// use std::collections::BTreeMap; | |
785 | /// | |
786 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 787 | /// assert_eq!(map.insert(37, "a"), None); |
1a4d82fc JJ |
788 | /// assert_eq!(map.is_empty(), false); |
789 | /// | |
790 | /// map.insert(37, "b"); | |
791 | /// assert_eq!(map.insert(37, "c"), Some("b")); | |
c34b1796 | 792 | /// assert_eq!(map[&37], "c"); |
1a4d82fc | 793 | /// ``` |
85aaf69f | 794 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
795 | pub fn insert(&mut self, key: K, value: V) -> Option<V> { |
796 | match self.entry(key) { | |
797 | Occupied(mut entry) => Some(entry.insert(value)), | |
798 | Vacant(entry) => { | |
799 | entry.insert(value); | |
800 | None | |
1a4d82fc JJ |
801 | } |
802 | } | |
803 | } | |
804 | ||
1a4d82fc JJ |
805 | /// Removes a key from the map, returning the value at the key if the key |
806 | /// was previously in the map. | |
807 | /// | |
808 | /// The key may be any borrowed form of the map's key type, but the ordering | |
809 | /// on the borrowed form *must* match the ordering on the key type. | |
810 | /// | |
811 | /// # Examples | |
812 | /// | |
54a0048b SL |
813 | /// Basic usage: |
814 | /// | |
1a4d82fc JJ |
815 | /// ``` |
816 | /// use std::collections::BTreeMap; | |
817 | /// | |
818 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 819 | /// map.insert(1, "a"); |
1a4d82fc JJ |
820 | /// assert_eq!(map.remove(&1), Some("a")); |
821 | /// assert_eq!(map.remove(&1), None); | |
822 | /// ``` | |
85aaf69f | 823 | #[stable(feature = "rust1", since = "1.0.0")] |
3157f602 | 824 | pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> |
74b04a01 XL |
825 | where |
826 | K: Borrow<Q>, | |
827 | Q: Ord, | |
828 | { | |
829 | self.remove_entry(key).map(|(_, v)| v) | |
830 | } | |
831 | ||
832 | /// Removes a key from the map, returning the stored key and value if the key | |
833 | /// was previously in the map. | |
834 | /// | |
835 | /// The key may be any borrowed form of the map's key type, but the ordering | |
836 | /// on the borrowed form *must* match the ordering on the key type. | |
837 | /// | |
838 | /// # Examples | |
839 | /// | |
840 | /// Basic usage: | |
841 | /// | |
842 | /// ``` | |
74b04a01 XL |
843 | /// use std::collections::BTreeMap; |
844 | /// | |
845 | /// let mut map = BTreeMap::new(); | |
846 | /// map.insert(1, "a"); | |
847 | /// assert_eq!(map.remove_entry(&1), Some((1, "a"))); | |
848 | /// assert_eq!(map.remove_entry(&1), None); | |
849 | /// ``` | |
f9f354fc | 850 | #[stable(feature = "btreemap_remove_entry", since = "1.45.0")] |
74b04a01 | 851 | pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> |
dfeec247 XL |
852 | where |
853 | K: Borrow<Q>, | |
854 | Q: Ord, | |
3157f602 | 855 | { |
1b1a35ee XL |
856 | let (map, dormant_map) = DormantMutRef::new(self); |
857 | let root_node = map.root.as_mut()?.node_as_mut(); | |
3dfed10e | 858 | match search::search_tree(root_node, key) { |
1b1a35ee XL |
859 | Found(handle) => { |
860 | Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_entry()) | |
861 | } | |
3157f602 | 862 | GoDown(_) => None, |
1a4d82fc JJ |
863 | } |
864 | } | |
85aaf69f | 865 | |
a7813a04 XL |
866 | /// Moves all elements from `other` into `Self`, leaving `other` empty. |
867 | /// | |
868 | /// # Examples | |
869 | /// | |
870 | /// ``` | |
a7813a04 XL |
871 | /// use std::collections::BTreeMap; |
872 | /// | |
873 | /// let mut a = BTreeMap::new(); | |
874 | /// a.insert(1, "a"); | |
875 | /// a.insert(2, "b"); | |
876 | /// a.insert(3, "c"); | |
877 | /// | |
878 | /// let mut b = BTreeMap::new(); | |
879 | /// b.insert(3, "d"); | |
880 | /// b.insert(4, "e"); | |
881 | /// b.insert(5, "f"); | |
882 | /// | |
883 | /// a.append(&mut b); | |
884 | /// | |
885 | /// assert_eq!(a.len(), 5); | |
886 | /// assert_eq!(b.len(), 0); | |
887 | /// | |
888 | /// assert_eq!(a[&1], "a"); | |
889 | /// assert_eq!(a[&2], "b"); | |
890 | /// assert_eq!(a[&3], "d"); | |
891 | /// assert_eq!(a[&4], "e"); | |
892 | /// assert_eq!(a[&5], "f"); | |
893 | /// ``` | |
3157f602 | 894 | #[stable(feature = "btree_append", since = "1.11.0")] |
a7813a04 XL |
895 | pub fn append(&mut self, other: &mut Self) { |
896 | // Do we have to append anything at all? | |
416331ca | 897 | if other.is_empty() { |
a7813a04 XL |
898 | return; |
899 | } | |
900 | ||
901 | // We can just swap `self` and `other` if `self` is empty. | |
416331ca | 902 | if self.is_empty() { |
a7813a04 XL |
903 | mem::swap(self, other); |
904 | return; | |
905 | } | |
906 | ||
416331ca XL |
907 | let self_iter = mem::take(self).into_iter(); |
908 | let other_iter = mem::take(other).into_iter(); | |
29967ef6 XL |
909 | let root = BTreeMap::ensure_is_owned(&mut self.root); |
910 | root.append_from_sorted_iters(self_iter, other_iter, &mut self.length) | |
a7813a04 XL |
911 | } |
912 | ||
32a655c1 SL |
913 | /// Constructs a double-ended iterator over a sub-range of elements in the map. |
914 | /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will | |
915 | /// yield elements from min (inclusive) to max (exclusive). | |
916 | /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example | |
917 | /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive | |
918 | /// range from 4 to 10. | |
9346a6ac | 919 | /// |
8bb4bdeb XL |
920 | /// # Panics |
921 | /// | |
922 | /// Panics if range `start > end`. | |
923 | /// Panics if range `start == end` and both bounds are `Excluded`. | |
924 | /// | |
9346a6ac AL |
925 | /// # Examples |
926 | /// | |
54a0048b SL |
927 | /// Basic usage: |
928 | /// | |
9346a6ac AL |
929 | /// ``` |
930 | /// use std::collections::BTreeMap; | |
0531ce1d | 931 | /// use std::ops::Bound::Included; |
9346a6ac AL |
932 | /// |
933 | /// let mut map = BTreeMap::new(); | |
9cc50fc6 SL |
934 | /// map.insert(3, "a"); |
935 | /// map.insert(5, "b"); | |
936 | /// map.insert(8, "c"); | |
32a655c1 | 937 | /// for (&key, &value) in map.range((Included(&4), Included(&8))) { |
9346a6ac AL |
938 | /// println!("{}: {}", key, value); |
939 | /// } | |
32a655c1 | 940 | /// assert_eq!(Some((&5, &"b")), map.range(4..).next()); |
9346a6ac | 941 | /// ``` |
8bb4bdeb | 942 | #[stable(feature = "btree_range", since = "1.17.0")] |
9fa01778 | 943 | pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V> |
dfeec247 XL |
944 | where |
945 | T: Ord, | |
946 | K: Borrow<T>, | |
947 | R: RangeBounds<T>, | |
9cc50fc6 | 948 | { |
ba9703b0 | 949 | if let Some(root) = &self.root { |
1b1a35ee | 950 | let (f, b) = root.node_as_ref().range_search(range); |
9cc50fc6 | 951 | |
ba9703b0 XL |
952 | Range { front: Some(f), back: Some(b) } |
953 | } else { | |
954 | Range { front: None, back: None } | |
955 | } | |
9cc50fc6 SL |
956 | } |
957 | ||
32a655c1 SL |
958 | /// Constructs a mutable double-ended iterator over a sub-range of elements in the map. |
959 | /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will | |
960 | /// yield elements from min (inclusive) to max (exclusive). | |
961 | /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example | |
962 | /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive | |
963 | /// range from 4 to 10. | |
9cc50fc6 | 964 | /// |
8bb4bdeb XL |
965 | /// # Panics |
966 | /// | |
967 | /// Panics if range `start > end`. | |
968 | /// Panics if range `start == end` and both bounds are `Excluded`. | |
969 | /// | |
9cc50fc6 SL |
970 | /// # Examples |
971 | /// | |
54a0048b SL |
972 | /// Basic usage: |
973 | /// | |
9cc50fc6 | 974 | /// ``` |
9cc50fc6 | 975 | /// use std::collections::BTreeMap; |
9cc50fc6 | 976 | /// |
a1dfa0c6 XL |
977 | /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"] |
978 | /// .iter() | |
979 | /// .map(|&s| (s, 0)) | |
980 | /// .collect(); | |
32a655c1 | 981 | /// for (_, balance) in map.range_mut("B".."Cheryl") { |
9cc50fc6 SL |
982 | /// *balance += 100; |
983 | /// } | |
984 | /// for (name, balance) in &map { | |
985 | /// println!("{} => {}", name, balance); | |
986 | /// } | |
987 | /// ``` | |
8bb4bdeb | 988 | #[stable(feature = "btree_range", since = "1.17.0")] |
9fa01778 | 989 | pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V> |
dfeec247 XL |
990 | where |
991 | T: Ord, | |
992 | K: Borrow<T>, | |
993 | R: RangeBounds<T>, | |
9cc50fc6 | 994 | { |
ba9703b0 | 995 | if let Some(root) = &mut self.root { |
1b1a35ee | 996 | let (f, b) = root.node_as_valmut().range_search(range); |
9cc50fc6 | 997 | |
ba9703b0 XL |
998 | RangeMut { front: Some(f), back: Some(b), _marker: PhantomData } |
999 | } else { | |
1000 | RangeMut { front: None, back: None, _marker: PhantomData } | |
1001 | } | |
9cc50fc6 SL |
1002 | } |
1003 | ||
1004 | /// Gets the given key's corresponding entry in the map for in-place manipulation. | |
1005 | /// | |
1006 | /// # Examples | |
1007 | /// | |
54a0048b SL |
1008 | /// Basic usage: |
1009 | /// | |
9cc50fc6 SL |
1010 | /// ``` |
1011 | /// use std::collections::BTreeMap; | |
1012 | /// | |
1013 | /// let mut count: BTreeMap<&str, usize> = BTreeMap::new(); | |
1014 | /// | |
1015 | /// // count the number of occurrences of letters in the vec | |
1016 | /// for x in vec!["a","b","a","c","a","b"] { | |
1017 | /// *count.entry(x).or_insert(0) += 1; | |
1018 | /// } | |
1019 | /// | |
1020 | /// assert_eq!(count["a"], 3); | |
1021 | /// ``` | |
1022 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1023 | pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { |
94b46f34 | 1024 | // FIXME(@porglezomp) Avoid allocating if we don't insert |
1b1a35ee XL |
1025 | let (map, dormant_map) = DormantMutRef::new(self); |
1026 | let root_node = Self::ensure_is_owned(&mut map.root).node_as_mut(); | |
1027 | match search::search_tree(root_node, &key) { | |
1028 | Found(handle) => Occupied(OccupiedEntry { handle, dormant_map, _marker: PhantomData }), | |
3157f602 | 1029 | GoDown(handle) => { |
1b1a35ee | 1030 | Vacant(VacantEntry { key, handle, dormant_map, _marker: PhantomData }) |
3157f602 | 1031 | } |
9346a6ac | 1032 | } |
85aaf69f | 1033 | } |
a7813a04 | 1034 | |
3157f602 XL |
1035 | /// Splits the collection into two at the given key. Returns everything after the given key, |
1036 | /// including the key. | |
1037 | /// | |
1038 | /// # Examples | |
1039 | /// | |
1040 | /// Basic usage: | |
1041 | /// | |
1042 | /// ``` | |
1043 | /// use std::collections::BTreeMap; | |
1044 | /// | |
1045 | /// let mut a = BTreeMap::new(); | |
1046 | /// a.insert(1, "a"); | |
1047 | /// a.insert(2, "b"); | |
1048 | /// a.insert(3, "c"); | |
1049 | /// a.insert(17, "d"); | |
1050 | /// a.insert(41, "e"); | |
1051 | /// | |
1052 | /// let b = a.split_off(&3); | |
1053 | /// | |
1054 | /// assert_eq!(a.len(), 2); | |
1055 | /// assert_eq!(b.len(), 3); | |
1056 | /// | |
1057 | /// assert_eq!(a[&1], "a"); | |
1058 | /// assert_eq!(a[&2], "b"); | |
1059 | /// | |
1060 | /// assert_eq!(b[&3], "c"); | |
1061 | /// assert_eq!(b[&17], "d"); | |
1062 | /// assert_eq!(b[&41], "e"); | |
1063 | /// ``` | |
1064 | #[stable(feature = "btree_split_off", since = "1.11.0")] | |
1065 | pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self | |
dfeec247 XL |
1066 | where |
1067 | K: Borrow<Q>, | |
3157f602 XL |
1068 | { |
1069 | if self.is_empty() { | |
1070 | return Self::new(); | |
1071 | } | |
1072 | ||
1073 | let total_num = self.len(); | |
3dfed10e | 1074 | let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty |
3157f602 XL |
1075 | |
1076 | let mut right = Self::new(); | |
3dfed10e | 1077 | let right_root = Self::ensure_is_owned(&mut right.root); |
3157f602 | 1078 | |
29967ef6 | 1079 | left_root.split_off(right_root, key); |
3157f602 | 1080 | |
3dfed10e XL |
1081 | if left_root.height() < right_root.height() { |
1082 | self.length = left_root.node_as_ref().calc_length(); | |
3157f602 XL |
1083 | right.length = total_num - self.len(); |
1084 | } else { | |
3dfed10e | 1085 | right.length = right_root.node_as_ref().calc_length(); |
3157f602 XL |
1086 | self.length = total_num - right.len(); |
1087 | } | |
1088 | ||
1089 | right | |
1090 | } | |
1091 | ||
ba9703b0 XL |
1092 | /// Creates an iterator which uses a closure to determine if an element should be removed. |
1093 | /// | |
1094 | /// If the closure returns true, the element is removed from the map and yielded. | |
1095 | /// If the closure returns false, or panics, the element remains in the map and will not be | |
1096 | /// yielded. | |
1097 | /// | |
1098 | /// Note that `drain_filter` lets you mutate every value in the filter closure, regardless of | |
1099 | /// whether you choose to keep or remove it. | |
1100 | /// | |
1101 | /// If the iterator is only partially consumed or not consumed at all, each of the remaining | |
1102 | /// elements will still be subjected to the closure and removed and dropped if it returns true. | |
1103 | /// | |
1104 | /// It is unspecified how many more elements will be subjected to the closure | |
1105 | /// if a panic occurs in the closure, or a panic occurs while dropping an element, | |
1106 | /// or if the `DrainFilter` value is leaked. | |
1107 | /// | |
1108 | /// # Examples | |
1109 | /// | |
1110 | /// Splitting a map into even and odd keys, reusing the original map: | |
1111 | /// | |
1112 | /// ``` | |
1113 | /// #![feature(btree_drain_filter)] | |
1114 | /// use std::collections::BTreeMap; | |
1115 | /// | |
1116 | /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect(); | |
1117 | /// let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect(); | |
1118 | /// let odds = map; | |
1119 | /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), vec![0, 2, 4, 6]); | |
1120 | /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), vec![1, 3, 5, 7]); | |
1121 | /// ``` | |
1122 | #[unstable(feature = "btree_drain_filter", issue = "70530")] | |
1123 | pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F> | |
1124 | where | |
1125 | F: FnMut(&K, &mut V) -> bool, | |
1126 | { | |
1127 | DrainFilter { pred, inner: self.drain_filter_inner() } | |
1128 | } | |
3dfed10e | 1129 | |
ba9703b0 | 1130 | pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> { |
1b1a35ee XL |
1131 | if let Some(root) = self.root.as_mut() { |
1132 | let (root, dormant_root) = DormantMutRef::new(root); | |
1133 | let front = root.node_as_mut().first_leaf_edge(); | |
1134 | DrainFilterInner { | |
1135 | length: &mut self.length, | |
1136 | dormant_root: Some(dormant_root), | |
1137 | cur_leaf_edge: Some(front), | |
1138 | } | |
1139 | } else { | |
1140 | DrainFilterInner { length: &mut self.length, dormant_root: None, cur_leaf_edge: None } | |
1141 | } | |
ba9703b0 XL |
1142 | } |
1143 | ||
3dfed10e XL |
1144 | /// Creates a consuming iterator visiting all the keys, in sorted order. |
1145 | /// The map cannot be used after calling this. | |
1146 | /// The iterator element type is `K`. | |
1147 | /// | |
1148 | /// # Examples | |
1149 | /// | |
1150 | /// ``` | |
1151 | /// #![feature(map_into_keys_values)] | |
1152 | /// use std::collections::BTreeMap; | |
1153 | /// | |
1154 | /// let mut a = BTreeMap::new(); | |
1155 | /// a.insert(2, "b"); | |
1156 | /// a.insert(1, "a"); | |
1157 | /// | |
1158 | /// let keys: Vec<i32> = a.into_keys().collect(); | |
1159 | /// assert_eq!(keys, [1, 2]); | |
1160 | /// ``` | |
1161 | #[inline] | |
1162 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1163 | pub fn into_keys(self) -> IntoKeys<K, V> { | |
1164 | IntoKeys { inner: self.into_iter() } | |
3157f602 XL |
1165 | } |
1166 | ||
3dfed10e XL |
1167 | /// Creates a consuming iterator visiting all the values, in order by key. |
1168 | /// The map cannot be used after calling this. | |
1169 | /// The iterator element type is `V`. | |
1170 | /// | |
1171 | /// # Examples | |
1172 | /// | |
1173 | /// ``` | |
1174 | /// #![feature(map_into_keys_values)] | |
1175 | /// use std::collections::BTreeMap; | |
1176 | /// | |
1177 | /// let mut a = BTreeMap::new(); | |
1178 | /// a.insert(1, "hello"); | |
1179 | /// a.insert(2, "goodbye"); | |
1180 | /// | |
1181 | /// let values: Vec<&str> = a.into_values().collect(); | |
1182 | /// assert_eq!(values, ["hello", "goodbye"]); | |
1183 | /// ``` | |
1184 | #[inline] | |
1185 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1186 | pub fn into_values(self) -> IntoValues<K, V> { | |
1187 | IntoValues { inner: self.into_iter() } | |
3157f602 | 1188 | } |
85aaf69f SL |
1189 | } |
1190 | ||
c30ab7b3 | 1191 | #[stable(feature = "rust1", since = "1.0.0")] |
3dfed10e | 1192 | impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> { |
85aaf69f SL |
1193 | type Item = (&'a K, &'a V); |
1194 | type IntoIter = Iter<'a, K, V>; | |
1195 | ||
1196 | fn into_iter(self) -> Iter<'a, K, V> { | |
1197 | self.iter() | |
1198 | } | |
1199 | } | |
1200 | ||
c30ab7b3 | 1201 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1202 | impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> { |
1203 | type Item = (&'a K, &'a V); | |
85aaf69f | 1204 | |
9cc50fc6 SL |
1205 | fn next(&mut self) -> Option<(&'a K, &'a V)> { |
1206 | if self.length == 0 { | |
1207 | None | |
1208 | } else { | |
1209 | self.length -= 1; | |
1210 | unsafe { Some(self.range.next_unchecked()) } | |
1211 | } | |
85aaf69f | 1212 | } |
85aaf69f | 1213 | |
9cc50fc6 SL |
1214 | fn size_hint(&self) -> (usize, Option<usize>) { |
1215 | (self.length, Some(self.length)) | |
1216 | } | |
416331ca XL |
1217 | |
1218 | fn last(mut self) -> Option<(&'a K, &'a V)> { | |
1219 | self.next_back() | |
1220 | } | |
f035d41b XL |
1221 | |
1222 | fn min(mut self) -> Option<(&'a K, &'a V)> { | |
1223 | self.next() | |
1224 | } | |
1225 | ||
1226 | fn max(mut self) -> Option<(&'a K, &'a V)> { | |
1227 | self.next_back() | |
1228 | } | |
1a4d82fc JJ |
1229 | } |
1230 | ||
0531ce1d | 1231 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1232 | impl<K, V> FusedIterator for Iter<'_, K, V> {} |
9e0c209e | 1233 | |
c30ab7b3 | 1234 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1235 | impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> { |
1236 | fn next_back(&mut self) -> Option<(&'a K, &'a V)> { | |
1237 | if self.length == 0 { | |
1238 | None | |
1239 | } else { | |
1240 | self.length -= 1; | |
1241 | unsafe { Some(self.range.next_back_unchecked()) } | |
85aaf69f SL |
1242 | } |
1243 | } | |
9cc50fc6 | 1244 | } |
85aaf69f | 1245 | |
c30ab7b3 | 1246 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1247 | impl<K, V> ExactSizeIterator for Iter<'_, K, V> { |
3157f602 XL |
1248 | fn len(&self) -> usize { |
1249 | self.length | |
1250 | } | |
9cc50fc6 | 1251 | } |
1a4d82fc | 1252 | |
c30ab7b3 | 1253 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 XL |
1254 | impl<K, V> Clone for Iter<'_, K, V> { |
1255 | fn clone(&self) -> Self { | |
dfeec247 | 1256 | Iter { range: self.range.clone(), length: self.length } |
1a4d82fc | 1257 | } |
9cc50fc6 | 1258 | } |
1a4d82fc | 1259 | |
c30ab7b3 | 1260 | #[stable(feature = "rust1", since = "1.0.0")] |
3dfed10e | 1261 | impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> { |
9cc50fc6 SL |
1262 | type Item = (&'a K, &'a mut V); |
1263 | type IntoIter = IterMut<'a, K, V>; | |
1264 | ||
1265 | fn into_iter(self) -> IterMut<'a, K, V> { | |
1266 | self.iter_mut() | |
1a4d82fc | 1267 | } |
9cc50fc6 | 1268 | } |
1a4d82fc | 1269 | |
c30ab7b3 | 1270 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1271 | impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> { |
1272 | type Item = (&'a K, &'a mut V); | |
1a4d82fc | 1273 | |
9cc50fc6 SL |
1274 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { |
1275 | if self.length == 0 { | |
1276 | None | |
1277 | } else { | |
1278 | self.length -= 1; | |
74b04a01 XL |
1279 | let (k, v) = unsafe { self.range.next_unchecked() }; |
1280 | Some((k, v)) // coerce k from `&mut K` to `&K` | |
9cc50fc6 | 1281 | } |
1a4d82fc JJ |
1282 | } |
1283 | ||
9cc50fc6 SL |
1284 | fn size_hint(&self) -> (usize, Option<usize>) { |
1285 | (self.length, Some(self.length)) | |
1a4d82fc | 1286 | } |
416331ca XL |
1287 | |
1288 | fn last(mut self) -> Option<(&'a K, &'a mut V)> { | |
1289 | self.next_back() | |
1290 | } | |
f035d41b XL |
1291 | |
1292 | fn min(mut self) -> Option<(&'a K, &'a mut V)> { | |
1293 | self.next() | |
1294 | } | |
1295 | ||
1296 | fn max(mut self) -> Option<(&'a K, &'a mut V)> { | |
1297 | self.next_back() | |
1298 | } | |
9cc50fc6 | 1299 | } |
1a4d82fc | 1300 | |
c30ab7b3 | 1301 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1302 | impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> { |
1303 | fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { | |
1304 | if self.length == 0 { | |
1305 | None | |
1306 | } else { | |
1307 | self.length -= 1; | |
74b04a01 XL |
1308 | let (k, v) = unsafe { self.range.next_back_unchecked() }; |
1309 | Some((k, v)) // coerce k from `&mut K` to `&K` | |
9cc50fc6 | 1310 | } |
1a4d82fc | 1311 | } |
9cc50fc6 | 1312 | } |
1a4d82fc | 1313 | |
c30ab7b3 | 1314 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1315 | impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { |
3157f602 XL |
1316 | fn len(&self) -> usize { |
1317 | self.length | |
1318 | } | |
9cc50fc6 | 1319 | } |
1a4d82fc | 1320 | |
0531ce1d | 1321 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1322 | impl<K, V> FusedIterator for IterMut<'_, K, V> {} |
9e0c209e | 1323 | |
1b1a35ee XL |
1324 | impl<'a, K, V> IterMut<'a, K, V> { |
1325 | /// Returns an iterator of references over the remaining items. | |
1326 | #[inline] | |
1327 | pub(super) fn iter(&self) -> Iter<'_, K, V> { | |
1328 | Iter { range: self.range.iter(), length: self.length } | |
1329 | } | |
1330 | } | |
1331 | ||
c30ab7b3 | 1332 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1333 | impl<K, V> IntoIterator for BTreeMap<K, V> { |
1334 | type Item = (K, V); | |
1335 | type IntoIter = IntoIter<K, V>; | |
1a4d82fc | 1336 | |
9cc50fc6 | 1337 | fn into_iter(self) -> IntoIter<K, V> { |
ba9703b0 | 1338 | let mut me = ManuallyDrop::new(self); |
f9f354fc | 1339 | if let Some(root) = me.root.take() { |
1b1a35ee | 1340 | let (f, b) = root.into_ref().full_range(); |
f9f354fc XL |
1341 | |
1342 | IntoIter { front: Some(f), back: Some(b), length: me.length } | |
ba9703b0 XL |
1343 | } else { |
1344 | IntoIter { front: None, back: None, length: 0 } | |
1345 | } | |
1a4d82fc | 1346 | } |
9cc50fc6 | 1347 | } |
1a4d82fc | 1348 | |
c30ab7b3 | 1349 | #[stable(feature = "btree_drop", since = "1.7.0")] |
9cc50fc6 SL |
1350 | impl<K, V> Drop for IntoIter<K, V> { |
1351 | fn drop(&mut self) { | |
74b04a01 XL |
1352 | struct DropGuard<'a, K, V>(&'a mut IntoIter<K, V>); |
1353 | ||
1354 | impl<'a, K, V> Drop for DropGuard<'a, K, V> { | |
1355 | fn drop(&mut self) { | |
1356 | // Continue the same loop we perform below. This only runs when unwinding, so we | |
1357 | // don't have to care about panics this time (they'll abort). | |
1358 | while let Some(_) = self.0.next() {} | |
1359 | ||
74b04a01 | 1360 | unsafe { |
ba9703b0 XL |
1361 | let mut node = |
1362 | unwrap_unchecked(ptr::read(&self.0.front)).into_node().forget_type(); | |
74b04a01 XL |
1363 | while let Some(parent) = node.deallocate_and_ascend() { |
1364 | node = parent.into_node().forget_type(); | |
1365 | } | |
1366 | } | |
1367 | } | |
1368 | } | |
1369 | ||
1370 | while let Some(pair) = self.next() { | |
1371 | let guard = DropGuard(self); | |
1372 | drop(pair); | |
1373 | mem::forget(guard); | |
1374 | } | |
1375 | ||
9cc50fc6 | 1376 | unsafe { |
ba9703b0 XL |
1377 | if let Some(front) = ptr::read(&self.front) { |
1378 | let mut node = front.into_node().forget_type(); | |
1379 | // Most of the nodes have been deallocated while traversing | |
1380 | // but one pile from a leaf up to the root is left standing. | |
1381 | while let Some(parent) = node.deallocate_and_ascend() { | |
1382 | node = parent.into_node().forget_type(); | |
1383 | } | |
1a4d82fc JJ |
1384 | } |
1385 | } | |
1386 | } | |
9cc50fc6 | 1387 | } |
1a4d82fc | 1388 | |
c30ab7b3 | 1389 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1390 | impl<K, V> Iterator for IntoIter<K, V> { |
1391 | type Item = (K, V); | |
1a4d82fc | 1392 | |
9cc50fc6 SL |
1393 | fn next(&mut self) -> Option<(K, V)> { |
1394 | if self.length == 0 { | |
74b04a01 | 1395 | None |
9cc50fc6 SL |
1396 | } else { |
1397 | self.length -= 1; | |
ba9703b0 | 1398 | Some(unsafe { self.front.as_mut().unwrap().next_unchecked() }) |
1a4d82fc JJ |
1399 | } |
1400 | } | |
1401 | ||
9cc50fc6 SL |
1402 | fn size_hint(&self) -> (usize, Option<usize>) { |
1403 | (self.length, Some(self.length)) | |
1404 | } | |
1405 | } | |
1406 | ||
c30ab7b3 | 1407 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1408 | impl<K, V> DoubleEndedIterator for IntoIter<K, V> { |
1409 | fn next_back(&mut self) -> Option<(K, V)> { | |
1410 | if self.length == 0 { | |
74b04a01 | 1411 | None |
9cc50fc6 SL |
1412 | } else { |
1413 | self.length -= 1; | |
ba9703b0 | 1414 | Some(unsafe { self.back.as_mut().unwrap().next_back_unchecked() }) |
1a4d82fc JJ |
1415 | } |
1416 | } | |
1417 | } | |
1418 | ||
c30ab7b3 | 1419 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 | 1420 | impl<K, V> ExactSizeIterator for IntoIter<K, V> { |
3157f602 XL |
1421 | fn len(&self) -> usize { |
1422 | self.length | |
1423 | } | |
1a4d82fc JJ |
1424 | } |
1425 | ||
0531ce1d | 1426 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
1427 | impl<K, V> FusedIterator for IntoIter<K, V> {} |
1428 | ||
c30ab7b3 | 1429 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1430 | impl<'a, K, V> Iterator for Keys<'a, K, V> { |
1431 | type Item = &'a K; | |
1432 | ||
1433 | fn next(&mut self) -> Option<&'a K> { | |
1434 | self.inner.next().map(|(k, _)| k) | |
1a4d82fc | 1435 | } |
1a4d82fc | 1436 | |
9cc50fc6 SL |
1437 | fn size_hint(&self) -> (usize, Option<usize>) { |
1438 | self.inner.size_hint() | |
62682a34 | 1439 | } |
416331ca XL |
1440 | |
1441 | fn last(mut self) -> Option<&'a K> { | |
1442 | self.next_back() | |
1443 | } | |
f035d41b XL |
1444 | |
1445 | fn min(mut self) -> Option<&'a K> { | |
1446 | self.next() | |
1447 | } | |
1448 | ||
1449 | fn max(mut self) -> Option<&'a K> { | |
1450 | self.next_back() | |
1451 | } | |
62682a34 SL |
1452 | } |
1453 | ||
c30ab7b3 | 1454 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1455 | impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { |
1456 | fn next_back(&mut self) -> Option<&'a K> { | |
1457 | self.inner.next_back().map(|(k, _)| k) | |
1a4d82fc JJ |
1458 | } |
1459 | } | |
1460 | ||
c30ab7b3 | 1461 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1462 | impl<K, V> ExactSizeIterator for Keys<'_, K, V> { |
9cc50fc6 SL |
1463 | fn len(&self) -> usize { |
1464 | self.inner.len() | |
1a4d82fc JJ |
1465 | } |
1466 | } | |
1467 | ||
0531ce1d | 1468 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1469 | impl<K, V> FusedIterator for Keys<'_, K, V> {} |
9e0c209e | 1470 | |
c30ab7b3 | 1471 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 XL |
1472 | impl<K, V> Clone for Keys<'_, K, V> { |
1473 | fn clone(&self) -> Self { | |
3157f602 | 1474 | Keys { inner: self.inner.clone() } |
1a4d82fc JJ |
1475 | } |
1476 | } | |
1477 | ||
c30ab7b3 | 1478 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1479 | impl<'a, K, V> Iterator for Values<'a, K, V> { |
1480 | type Item = &'a V; | |
1a4d82fc | 1481 | |
9cc50fc6 SL |
1482 | fn next(&mut self) -> Option<&'a V> { |
1483 | self.inner.next().map(|(_, v)| v) | |
1a4d82fc | 1484 | } |
1a4d82fc | 1485 | |
9cc50fc6 SL |
1486 | fn size_hint(&self) -> (usize, Option<usize>) { |
1487 | self.inner.size_hint() | |
1a4d82fc | 1488 | } |
416331ca XL |
1489 | |
1490 | fn last(mut self) -> Option<&'a V> { | |
1491 | self.next_back() | |
1492 | } | |
1a4d82fc JJ |
1493 | } |
1494 | ||
c30ab7b3 | 1495 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1496 | impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { |
1497 | fn next_back(&mut self) -> Option<&'a V> { | |
1498 | self.inner.next_back().map(|(_, v)| v) | |
1a4d82fc JJ |
1499 | } |
1500 | } | |
1501 | ||
c30ab7b3 | 1502 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1503 | impl<K, V> ExactSizeIterator for Values<'_, K, V> { |
9cc50fc6 SL |
1504 | fn len(&self) -> usize { |
1505 | self.inner.len() | |
1a4d82fc JJ |
1506 | } |
1507 | } | |
1508 | ||
0531ce1d | 1509 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1510 | impl<K, V> FusedIterator for Values<'_, K, V> {} |
9e0c209e | 1511 | |
c30ab7b3 | 1512 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 XL |
1513 | impl<K, V> Clone for Values<'_, K, V> { |
1514 | fn clone(&self) -> Self { | |
3157f602 | 1515 | Values { inner: self.inner.clone() } |
1a4d82fc JJ |
1516 | } |
1517 | } | |
1518 | ||
ba9703b0 XL |
1519 | /// An iterator produced by calling `drain_filter` on BTreeMap. |
1520 | #[unstable(feature = "btree_drain_filter", issue = "70530")] | |
1521 | pub struct DrainFilter<'a, K, V, F> | |
1522 | where | |
1523 | K: 'a, | |
1524 | V: 'a, | |
1525 | F: 'a + FnMut(&K, &mut V) -> bool, | |
1526 | { | |
1527 | pred: F, | |
1528 | inner: DrainFilterInner<'a, K, V>, | |
1529 | } | |
3dfed10e XL |
1530 | /// Most of the implementation of DrainFilter, independent of the type |
1531 | /// of the predicate, thus also serving for BTreeSet::DrainFilter. | |
ba9703b0 | 1532 | pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> { |
29967ef6 | 1533 | /// Reference to the length field in the borrowed map, updated live. |
ba9703b0 | 1534 | length: &'a mut usize, |
29967ef6 XL |
1535 | /// Burried reference to the root field in the borrowed map. |
1536 | /// Wrapped in `Option` to allow drop handler to `take` it. | |
1b1a35ee | 1537 | dormant_root: Option<DormantMutRef<'a, node::Root<K, V>>>, |
29967ef6 XL |
1538 | /// Contains a leaf edge preceding the next element to be returned, or the last leaf edge. |
1539 | /// Empty if the map has no root, if iteration went beyond the last leaf edge, | |
1540 | /// or if a panic occurred in the predicate. | |
ba9703b0 XL |
1541 | cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>, |
1542 | } | |
1543 | ||
1544 | #[unstable(feature = "btree_drain_filter", issue = "70530")] | |
1545 | impl<K, V, F> Drop for DrainFilter<'_, K, V, F> | |
1546 | where | |
1547 | F: FnMut(&K, &mut V) -> bool, | |
1548 | { | |
1549 | fn drop(&mut self) { | |
1550 | self.for_each(drop); | |
1551 | } | |
1552 | } | |
1553 | ||
1554 | #[unstable(feature = "btree_drain_filter", issue = "70530")] | |
1555 | impl<K, V, F> fmt::Debug for DrainFilter<'_, K, V, F> | |
1556 | where | |
1557 | K: fmt::Debug, | |
1558 | V: fmt::Debug, | |
1559 | F: FnMut(&K, &mut V) -> bool, | |
1560 | { | |
1561 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1562 | f.debug_tuple("DrainFilter").field(&self.inner.peek()).finish() | |
1563 | } | |
1564 | } | |
1565 | ||
1566 | #[unstable(feature = "btree_drain_filter", issue = "70530")] | |
1567 | impl<K, V, F> Iterator for DrainFilter<'_, K, V, F> | |
1568 | where | |
1569 | F: FnMut(&K, &mut V) -> bool, | |
1570 | { | |
1571 | type Item = (K, V); | |
1572 | ||
1573 | fn next(&mut self) -> Option<(K, V)> { | |
1574 | self.inner.next(&mut self.pred) | |
1575 | } | |
1576 | ||
1577 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1578 | self.inner.size_hint() | |
1579 | } | |
1580 | } | |
1581 | ||
1582 | impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> { | |
1583 | /// Allow Debug implementations to predict the next element. | |
1584 | pub(super) fn peek(&self) -> Option<(&K, &V)> { | |
1585 | let edge = self.cur_leaf_edge.as_ref()?; | |
1b1a35ee | 1586 | edge.reborrow().next_kv().ok().map(Handle::into_kv) |
ba9703b0 XL |
1587 | } |
1588 | ||
ba9703b0 XL |
1589 | /// Implementation of a typical `DrainFilter::next` method, given the predicate. |
1590 | pub(super) fn next<F>(&mut self, pred: &mut F) -> Option<(K, V)> | |
1591 | where | |
1592 | F: FnMut(&K, &mut V) -> bool, | |
1593 | { | |
3dfed10e | 1594 | while let Ok(mut kv) = self.cur_leaf_edge.take()?.next_kv() { |
ba9703b0 XL |
1595 | let (k, v) = kv.kv_mut(); |
1596 | if pred(k, v) { | |
1597 | *self.length -= 1; | |
1b1a35ee XL |
1598 | let (kv, pos) = kv.remove_kv_tracking(|| { |
1599 | // SAFETY: we will touch the root in a way that will not | |
1600 | // invalidate the position returned. | |
1601 | let root = unsafe { self.dormant_root.take().unwrap().awaken() }; | |
1602 | root.pop_internal_level(); | |
1603 | self.dormant_root = Some(DormantMutRef::new(root).1); | |
1604 | }); | |
3dfed10e XL |
1605 | self.cur_leaf_edge = Some(pos); |
1606 | return Some(kv); | |
ba9703b0 XL |
1607 | } |
1608 | self.cur_leaf_edge = Some(kv.next_leaf_edge()); | |
1609 | } | |
1610 | None | |
1611 | } | |
1612 | ||
1613 | /// Implementation of a typical `DrainFilter::size_hint` method. | |
1614 | pub(super) fn size_hint(&self) -> (usize, Option<usize>) { | |
29967ef6 XL |
1615 | // In most of the btree iterators, `self.length` is the number of elements |
1616 | // yet to be visited. Here, it includes elements that were visited and that | |
1617 | // the predicate decided not to drain. Making this upper bound more accurate | |
1618 | // requires maintaining an extra field and is not worth while. | |
ba9703b0 XL |
1619 | (0, Some(*self.length)) |
1620 | } | |
1621 | } | |
1622 | ||
1623 | #[unstable(feature = "btree_drain_filter", issue = "70530")] | |
1624 | impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {} | |
1625 | ||
cc61c64b | 1626 | #[stable(feature = "btree_range", since = "1.17.0")] |
9cc50fc6 SL |
1627 | impl<'a, K, V> Iterator for Range<'a, K, V> { |
1628 | type Item = (&'a K, &'a V); | |
1a4d82fc | 1629 | |
9cc50fc6 | 1630 | fn next(&mut self) -> Option<(&'a K, &'a V)> { |
74b04a01 | 1631 | if self.is_empty() { None } else { unsafe { Some(self.next_unchecked()) } } |
1a4d82fc | 1632 | } |
416331ca XL |
1633 | |
1634 | fn last(mut self) -> Option<(&'a K, &'a V)> { | |
1635 | self.next_back() | |
1636 | } | |
f035d41b XL |
1637 | |
1638 | fn min(mut self) -> Option<(&'a K, &'a V)> { | |
1639 | self.next() | |
1640 | } | |
1641 | ||
1642 | fn max(mut self) -> Option<(&'a K, &'a V)> { | |
1643 | self.next_back() | |
1644 | } | |
1a4d82fc JJ |
1645 | } |
1646 | ||
a7813a04 | 1647 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
54a0048b SL |
1648 | impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { |
1649 | type Item = &'a mut V; | |
1650 | ||
1651 | fn next(&mut self) -> Option<&'a mut V> { | |
1652 | self.inner.next().map(|(_, v)| v) | |
1653 | } | |
1654 | ||
1655 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1656 | self.inner.size_hint() | |
1657 | } | |
416331ca XL |
1658 | |
1659 | fn last(mut self) -> Option<&'a mut V> { | |
1660 | self.next_back() | |
1661 | } | |
54a0048b SL |
1662 | } |
1663 | ||
a7813a04 | 1664 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
54a0048b SL |
1665 | impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> { |
1666 | fn next_back(&mut self) -> Option<&'a mut V> { | |
1667 | self.inner.next_back().map(|(_, v)| v) | |
1668 | } | |
1669 | } | |
1670 | ||
a7813a04 | 1671 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
9fa01778 | 1672 | impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { |
54a0048b SL |
1673 | fn len(&self) -> usize { |
1674 | self.inner.len() | |
1675 | } | |
1676 | } | |
1677 | ||
0531ce1d | 1678 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1679 | impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} |
9e0c209e | 1680 | |
9cc50fc6 | 1681 | impl<'a, K, V> Range<'a, K, V> { |
74b04a01 XL |
1682 | fn is_empty(&self) -> bool { |
1683 | self.front == self.back | |
1684 | } | |
1a4d82fc | 1685 | |
74b04a01 | 1686 | unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) { |
f035d41b | 1687 | unsafe { unwrap_unchecked(self.front.as_mut()).next_unchecked() } |
1a4d82fc | 1688 | } |
9cc50fc6 | 1689 | } |
1a4d82fc | 1690 | |
3dfed10e XL |
1691 | #[unstable(feature = "map_into_keys_values", issue = "75294")] |
1692 | impl<K, V> Iterator for IntoKeys<K, V> { | |
1693 | type Item = K; | |
1694 | ||
1695 | fn next(&mut self) -> Option<K> { | |
1696 | self.inner.next().map(|(k, _)| k) | |
1697 | } | |
1698 | ||
1699 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1700 | self.inner.size_hint() | |
1701 | } | |
1702 | ||
1703 | fn last(mut self) -> Option<K> { | |
1704 | self.next_back() | |
1705 | } | |
1706 | ||
1707 | fn min(mut self) -> Option<K> { | |
1708 | self.next() | |
1709 | } | |
1710 | ||
1711 | fn max(mut self) -> Option<K> { | |
1712 | self.next_back() | |
1713 | } | |
1714 | } | |
1715 | ||
1716 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1717 | impl<K, V> DoubleEndedIterator for IntoKeys<K, V> { | |
1718 | fn next_back(&mut self) -> Option<K> { | |
1719 | self.inner.next_back().map(|(k, _)| k) | |
1720 | } | |
1721 | } | |
1722 | ||
1723 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1724 | impl<K, V> ExactSizeIterator for IntoKeys<K, V> { | |
1725 | fn len(&self) -> usize { | |
1726 | self.inner.len() | |
1727 | } | |
1728 | } | |
1729 | ||
1730 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1731 | impl<K, V> FusedIterator for IntoKeys<K, V> {} | |
1732 | ||
1733 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1734 | impl<K, V> Iterator for IntoValues<K, V> { | |
1735 | type Item = V; | |
1736 | ||
1737 | fn next(&mut self) -> Option<V> { | |
1738 | self.inner.next().map(|(_, v)| v) | |
1739 | } | |
1740 | ||
1741 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1742 | self.inner.size_hint() | |
1743 | } | |
1744 | ||
1745 | fn last(mut self) -> Option<V> { | |
1746 | self.next_back() | |
1747 | } | |
1748 | } | |
1749 | ||
1750 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1751 | impl<K, V> DoubleEndedIterator for IntoValues<K, V> { | |
1752 | fn next_back(&mut self) -> Option<V> { | |
1753 | self.inner.next_back().map(|(_, v)| v) | |
1754 | } | |
1755 | } | |
1756 | ||
1757 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1758 | impl<K, V> ExactSizeIterator for IntoValues<K, V> { | |
1759 | fn len(&self) -> usize { | |
1760 | self.inner.len() | |
1761 | } | |
1762 | } | |
1763 | ||
1764 | #[unstable(feature = "map_into_keys_values", issue = "75294")] | |
1765 | impl<K, V> FusedIterator for IntoValues<K, V> {} | |
1766 | ||
cc61c64b | 1767 | #[stable(feature = "btree_range", since = "1.17.0")] |
9cc50fc6 SL |
1768 | impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { |
1769 | fn next_back(&mut self) -> Option<(&'a K, &'a V)> { | |
74b04a01 | 1770 | if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) } |
1a4d82fc JJ |
1771 | } |
1772 | } | |
1773 | ||
9cc50fc6 SL |
1774 | impl<'a, K, V> Range<'a, K, V> { |
1775 | unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) { | |
f035d41b | 1776 | unsafe { unwrap_unchecked(self.back.as_mut()).next_back_unchecked() } |
1a4d82fc JJ |
1777 | } |
1778 | } | |
1779 | ||
0531ce1d | 1780 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1781 | impl<K, V> FusedIterator for Range<'_, K, V> {} |
9e0c209e | 1782 | |
cc61c64b | 1783 | #[stable(feature = "btree_range", since = "1.17.0")] |
9fa01778 XL |
1784 | impl<K, V> Clone for Range<'_, K, V> { |
1785 | fn clone(&self) -> Self { | |
dfeec247 | 1786 | Range { front: self.front, back: self.back } |
92a42be0 | 1787 | } |
1a4d82fc | 1788 | } |
1a4d82fc | 1789 | |
cc61c64b | 1790 | #[stable(feature = "btree_range", since = "1.17.0")] |
9cc50fc6 | 1791 | impl<'a, K, V> Iterator for RangeMut<'a, K, V> { |
1a4d82fc JJ |
1792 | type Item = (&'a K, &'a mut V); |
1793 | ||
92a42be0 | 1794 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { |
74b04a01 XL |
1795 | if self.is_empty() { |
1796 | None | |
1797 | } else { | |
1798 | let (k, v) = unsafe { self.next_unchecked() }; | |
1799 | Some((k, v)) // coerce k from `&mut K` to `&K` | |
1800 | } | |
92a42be0 | 1801 | } |
416331ca XL |
1802 | |
1803 | fn last(mut self) -> Option<(&'a K, &'a mut V)> { | |
1804 | self.next_back() | |
1805 | } | |
f035d41b XL |
1806 | |
1807 | fn min(mut self) -> Option<(&'a K, &'a mut V)> { | |
1808 | self.next() | |
1809 | } | |
1810 | ||
1811 | fn max(mut self) -> Option<(&'a K, &'a mut V)> { | |
1812 | self.next_back() | |
1813 | } | |
1a4d82fc | 1814 | } |
1a4d82fc | 1815 | |
9cc50fc6 | 1816 | impl<'a, K, V> RangeMut<'a, K, V> { |
74b04a01 XL |
1817 | fn is_empty(&self) -> bool { |
1818 | self.front == self.back | |
1819 | } | |
1a4d82fc | 1820 | |
1b1a35ee | 1821 | unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) { |
f035d41b | 1822 | unsafe { unwrap_unchecked(self.front.as_mut()).next_unchecked() } |
92a42be0 | 1823 | } |
1b1a35ee XL |
1824 | |
1825 | /// Returns an iterator of references over the remaining items. | |
1826 | #[inline] | |
1827 | pub(super) fn iter(&self) -> Range<'_, K, V> { | |
1828 | Range { | |
1829 | front: self.front.as_ref().map(|f| f.reborrow()), | |
1830 | back: self.back.as_ref().map(|b| b.reborrow()), | |
1831 | } | |
1832 | } | |
c34b1796 | 1833 | } |
1a4d82fc | 1834 | |
cc61c64b | 1835 | #[stable(feature = "btree_range", since = "1.17.0")] |
9cc50fc6 SL |
1836 | impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> { |
1837 | fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { | |
74b04a01 XL |
1838 | if self.is_empty() { |
1839 | None | |
1840 | } else { | |
1841 | let (k, v) = unsafe { self.next_back_unchecked() }; | |
1842 | Some((k, v)) // coerce k from `&mut K` to `&K` | |
1843 | } | |
92a42be0 | 1844 | } |
1a4d82fc | 1845 | } |
1a4d82fc | 1846 | |
0531ce1d | 1847 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1848 | impl<K, V> FusedIterator for RangeMut<'_, K, V> {} |
9e0c209e | 1849 | |
9cc50fc6 | 1850 | impl<'a, K, V> RangeMut<'a, K, V> { |
1b1a35ee | 1851 | unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) { |
f035d41b | 1852 | unsafe { unwrap_unchecked(self.back.as_mut()).next_back_unchecked() } |
92a42be0 | 1853 | } |
1a4d82fc | 1854 | } |
9cc50fc6 | 1855 | |
c30ab7b3 | 1856 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 | 1857 | impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { |
3157f602 | 1858 | fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> { |
9cc50fc6 SL |
1859 | let mut map = BTreeMap::new(); |
1860 | map.extend(iter); | |
1861 | map | |
92a42be0 | 1862 | } |
1a4d82fc | 1863 | } |
1a4d82fc | 1864 | |
c30ab7b3 | 1865 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1866 | impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> { |
1867 | #[inline] | |
3157f602 | 1868 | fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { |
532ac7d7 | 1869 | iter.into_iter().for_each(move |(k, v)| { |
9cc50fc6 | 1870 | self.insert(k, v); |
532ac7d7 | 1871 | }); |
92a42be0 | 1872 | } |
f9f354fc XL |
1873 | |
1874 | #[inline] | |
1875 | fn extend_one(&mut self, (k, v): (K, V)) { | |
1876 | self.insert(k, v); | |
1877 | } | |
c34b1796 | 1878 | } |
85aaf69f | 1879 | |
c30ab7b3 | 1880 | #[stable(feature = "extend_ref", since = "1.2.0")] |
9cc50fc6 | 1881 | impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> { |
3157f602 | 1882 | fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) { |
9cc50fc6 | 1883 | self.extend(iter.into_iter().map(|(&key, &value)| (key, value))); |
92a42be0 | 1884 | } |
f9f354fc XL |
1885 | |
1886 | #[inline] | |
1887 | fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) { | |
1888 | self.insert(k, v); | |
1889 | } | |
85aaf69f | 1890 | } |
9cc50fc6 | 1891 | |
c30ab7b3 | 1892 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1893 | impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> { |
1894 | fn hash<H: Hasher>(&self, state: &mut H) { | |
1895 | for elt in self { | |
1896 | elt.hash(state); | |
1897 | } | |
92a42be0 | 1898 | } |
85aaf69f SL |
1899 | } |
1900 | ||
c30ab7b3 | 1901 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 | 1902 | impl<K: Ord, V> Default for BTreeMap<K, V> { |
9e0c209e | 1903 | /// Creates an empty `BTreeMap<K, V>`. |
9cc50fc6 SL |
1904 | fn default() -> BTreeMap<K, V> { |
1905 | BTreeMap::new() | |
92a42be0 | 1906 | } |
85aaf69f | 1907 | } |
9cc50fc6 | 1908 | |
c30ab7b3 | 1909 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1910 | impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> { |
1911 | fn eq(&self, other: &BTreeMap<K, V>) -> bool { | |
3157f602 | 1912 | self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b) |
92a42be0 | 1913 | } |
85aaf69f SL |
1914 | } |
1915 | ||
c30ab7b3 | 1916 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 | 1917 | impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {} |
c34b1796 | 1918 | |
c30ab7b3 | 1919 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1920 | impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> { |
1921 | #[inline] | |
1922 | fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> { | |
1923 | self.iter().partial_cmp(other.iter()) | |
c34b1796 | 1924 | } |
1a4d82fc JJ |
1925 | } |
1926 | ||
c30ab7b3 | 1927 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 SL |
1928 | impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> { |
1929 | #[inline] | |
1930 | fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering { | |
1931 | self.iter().cmp(other.iter()) | |
1a4d82fc JJ |
1932 | } |
1933 | } | |
1934 | ||
c30ab7b3 | 1935 | #[stable(feature = "rust1", since = "1.0.0")] |
9cc50fc6 | 1936 | impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> { |
9fa01778 | 1937 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
9cc50fc6 | 1938 | f.debug_map().entries(self.iter()).finish() |
1a4d82fc | 1939 | } |
9cc50fc6 | 1940 | } |
1a4d82fc | 1941 | |
c30ab7b3 | 1942 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1943 | impl<K: Ord, Q: ?Sized, V> Index<&Q> for BTreeMap<K, V> |
dfeec247 XL |
1944 | where |
1945 | K: Borrow<Q>, | |
1946 | Q: Ord, | |
9cc50fc6 SL |
1947 | { |
1948 | type Output = V; | |
1a4d82fc | 1949 | |
2c00a5a8 XL |
1950 | /// Returns a reference to the value corresponding to the supplied key. |
1951 | /// | |
1952 | /// # Panics | |
1953 | /// | |
1954 | /// Panics if the key is not present in the `BTreeMap`. | |
9cc50fc6 SL |
1955 | #[inline] |
1956 | fn index(&self, key: &Q) -> &V { | |
1957 | self.get(key).expect("no entry found for key") | |
1a4d82fc | 1958 | } |
9cc50fc6 | 1959 | } |
1a4d82fc | 1960 | |
1a4d82fc | 1961 | impl<K, V> BTreeMap<K, V> { |
7453a54e | 1962 | /// Gets an iterator over the entries of the map, sorted by key. |
1a4d82fc | 1963 | /// |
c34b1796 | 1964 | /// # Examples |
1a4d82fc | 1965 | /// |
54a0048b SL |
1966 | /// Basic usage: |
1967 | /// | |
1a4d82fc JJ |
1968 | /// ``` |
1969 | /// use std::collections::BTreeMap; | |
1970 | /// | |
1971 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 1972 | /// map.insert(3, "c"); |
7453a54e SL |
1973 | /// map.insert(2, "b"); |
1974 | /// map.insert(1, "a"); | |
1a4d82fc JJ |
1975 | /// |
1976 | /// for (key, value) in map.iter() { | |
1977 | /// println!("{}: {}", key, value); | |
1978 | /// } | |
1979 | /// | |
1980 | /// let (first_key, first_value) = map.iter().next().unwrap(); | |
85aaf69f | 1981 | /// assert_eq!((*first_key, *first_value), (1, "a")); |
1a4d82fc | 1982 | /// ``` |
85aaf69f | 1983 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1984 | pub fn iter(&self) -> Iter<'_, K, V> { |
f9f354fc | 1985 | if let Some(root) = &self.root { |
1b1a35ee | 1986 | let (f, b) = root.node_as_ref().full_range(); |
f9f354fc XL |
1987 | |
1988 | Iter { range: Range { front: Some(f), back: Some(b) }, length: self.length } | |
1989 | } else { | |
1990 | Iter { range: Range { front: None, back: None }, length: 0 } | |
1a4d82fc JJ |
1991 | } |
1992 | } | |
1993 | ||
7453a54e | 1994 | /// Gets a mutable iterator over the entries of the map, sorted by key. |
1a4d82fc JJ |
1995 | /// |
1996 | /// # Examples | |
1997 | /// | |
54a0048b SL |
1998 | /// Basic usage: |
1999 | /// | |
1a4d82fc JJ |
2000 | /// ``` |
2001 | /// use std::collections::BTreeMap; | |
2002 | /// | |
2003 | /// let mut map = BTreeMap::new(); | |
85aaf69f SL |
2004 | /// map.insert("a", 1); |
2005 | /// map.insert("b", 2); | |
2006 | /// map.insert("c", 3); | |
1a4d82fc JJ |
2007 | /// |
2008 | /// // add 10 to the value if the key isn't "a" | |
2009 | /// for (key, value) in map.iter_mut() { | |
2010 | /// if key != &"a" { | |
2011 | /// *value += 10; | |
2012 | /// } | |
2013 | /// } | |
2014 | /// ``` | |
85aaf69f | 2015 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 2016 | pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { |
f9f354fc | 2017 | if let Some(root) = &mut self.root { |
1b1a35ee | 2018 | let (f, b) = root.node_as_valmut().full_range(); |
f9f354fc XL |
2019 | |
2020 | IterMut { | |
2021 | range: RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }, | |
2022 | length: self.length, | |
2023 | } | |
2024 | } else { | |
2025 | IterMut { range: RangeMut { front: None, back: None, _marker: PhantomData }, length: 0 } | |
1a4d82fc JJ |
2026 | } |
2027 | } | |
2028 | ||
7453a54e | 2029 | /// Gets an iterator over the keys of the map, in sorted order. |
1a4d82fc JJ |
2030 | /// |
2031 | /// # Examples | |
2032 | /// | |
54a0048b SL |
2033 | /// Basic usage: |
2034 | /// | |
1a4d82fc JJ |
2035 | /// ``` |
2036 | /// use std::collections::BTreeMap; | |
2037 | /// | |
2038 | /// let mut a = BTreeMap::new(); | |
85aaf69f | 2039 | /// a.insert(2, "b"); |
7453a54e | 2040 | /// a.insert(1, "a"); |
1a4d82fc | 2041 | /// |
62682a34 | 2042 | /// let keys: Vec<_> = a.keys().cloned().collect(); |
c34b1796 | 2043 | /// assert_eq!(keys, [1, 2]); |
1a4d82fc | 2044 | /// ``` |
85aaf69f | 2045 | #[stable(feature = "rust1", since = "1.0.0")] |
416331ca | 2046 | pub fn keys(&self) -> Keys<'_, K, V> { |
9cc50fc6 | 2047 | Keys { inner: self.iter() } |
1a4d82fc JJ |
2048 | } |
2049 | ||
7453a54e | 2050 | /// Gets an iterator over the values of the map, in order by key. |
1a4d82fc JJ |
2051 | /// |
2052 | /// # Examples | |
2053 | /// | |
54a0048b SL |
2054 | /// Basic usage: |
2055 | /// | |
1a4d82fc JJ |
2056 | /// ``` |
2057 | /// use std::collections::BTreeMap; | |
2058 | /// | |
2059 | /// let mut a = BTreeMap::new(); | |
7453a54e SL |
2060 | /// a.insert(1, "hello"); |
2061 | /// a.insert(2, "goodbye"); | |
1a4d82fc JJ |
2062 | /// |
2063 | /// let values: Vec<&str> = a.values().cloned().collect(); | |
7453a54e | 2064 | /// assert_eq!(values, ["hello", "goodbye"]); |
1a4d82fc | 2065 | /// ``` |
85aaf69f | 2066 | #[stable(feature = "rust1", since = "1.0.0")] |
416331ca | 2067 | pub fn values(&self) -> Values<'_, K, V> { |
9cc50fc6 | 2068 | Values { inner: self.iter() } |
1a4d82fc JJ |
2069 | } |
2070 | ||
54a0048b SL |
2071 | /// Gets a mutable iterator over the values of the map, in order by key. |
2072 | /// | |
2073 | /// # Examples | |
2074 | /// | |
2075 | /// Basic usage: | |
2076 | /// | |
2077 | /// ``` | |
54a0048b SL |
2078 | /// use std::collections::BTreeMap; |
2079 | /// | |
2080 | /// let mut a = BTreeMap::new(); | |
2081 | /// a.insert(1, String::from("hello")); | |
2082 | /// a.insert(2, String::from("goodbye")); | |
2083 | /// | |
2084 | /// for value in a.values_mut() { | |
2085 | /// value.push_str("!"); | |
2086 | /// } | |
2087 | /// | |
2088 | /// let values: Vec<String> = a.values().cloned().collect(); | |
2089 | /// assert_eq!(values, [String::from("hello!"), | |
2090 | /// String::from("goodbye!")]); | |
2091 | /// ``` | |
a7813a04 | 2092 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
9fa01778 | 2093 | pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { |
54a0048b SL |
2094 | ValuesMut { inner: self.iter_mut() } |
2095 | } | |
2096 | ||
9346a6ac | 2097 | /// Returns the number of elements in the map. |
1a4d82fc JJ |
2098 | /// |
2099 | /// # Examples | |
2100 | /// | |
54a0048b SL |
2101 | /// Basic usage: |
2102 | /// | |
1a4d82fc JJ |
2103 | /// ``` |
2104 | /// use std::collections::BTreeMap; | |
2105 | /// | |
2106 | /// let mut a = BTreeMap::new(); | |
2107 | /// assert_eq!(a.len(), 0); | |
85aaf69f | 2108 | /// a.insert(1, "a"); |
1a4d82fc JJ |
2109 | /// assert_eq!(a.len(), 1); |
2110 | /// ``` | |
85aaf69f | 2111 | #[stable(feature = "rust1", since = "1.0.0")] |
29967ef6 XL |
2112 | #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] |
2113 | pub const fn len(&self) -> usize { | |
92a42be0 SL |
2114 | self.length |
2115 | } | |
1a4d82fc | 2116 | |
cc61c64b | 2117 | /// Returns `true` if the map contains no elements. |
1a4d82fc JJ |
2118 | /// |
2119 | /// # Examples | |
2120 | /// | |
54a0048b SL |
2121 | /// Basic usage: |
2122 | /// | |
1a4d82fc JJ |
2123 | /// ``` |
2124 | /// use std::collections::BTreeMap; | |
2125 | /// | |
2126 | /// let mut a = BTreeMap::new(); | |
2127 | /// assert!(a.is_empty()); | |
85aaf69f | 2128 | /// a.insert(1, "a"); |
1a4d82fc JJ |
2129 | /// assert!(!a.is_empty()); |
2130 | /// ``` | |
85aaf69f | 2131 | #[stable(feature = "rust1", since = "1.0.0")] |
29967ef6 XL |
2132 | #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] |
2133 | pub const fn is_empty(&self) -> bool { | |
92a42be0 SL |
2134 | self.len() == 0 |
2135 | } | |
ba9703b0 XL |
2136 | |
2137 | /// If the root node is the empty (non-allocated) root node, allocate our | |
3dfed10e XL |
2138 | /// own node. Is an associated function to avoid borrowing the entire BTreeMap. |
2139 | fn ensure_is_owned(root: &mut Option<node::Root<K, V>>) -> &mut node::Root<K, V> { | |
2140 | root.get_or_insert_with(node::Root::new_leaf) | |
ba9703b0 | 2141 | } |
1a4d82fc JJ |
2142 | } |
2143 | ||
3dfed10e XL |
2144 | #[cfg(test)] |
2145 | mod tests; |