1 | use core::borrow::Borrow; |
---|---|
2 | use core::cmp::Ordering; |
3 | use core::error::Error; |
4 | use core::fmt::{self, Debug}; |
5 | use core::hash::{Hash, Hasher}; |
6 | use core::iter::FusedIterator; |
7 | use core::marker::PhantomData; |
8 | use core::mem::{self, ManuallyDrop}; |
9 | use core::ops::{Bound, Index, RangeBounds}; |
10 | use core::ptr; |
11 | |
12 | use super::borrow::DormantMutRef; |
13 | use super::dedup_sorted_iter::DedupSortedIter; |
14 | use super::navigate::{LazyLeafRange, LeafRange}; |
15 | use super::node::ForceResult::*; |
16 | use super::node::{self, Handle, NodeRef, Root, marker}; |
17 | use super::search::SearchBound; |
18 | use super::search::SearchResult::*; |
19 | use super::set_val::SetValZST; |
20 | use crate::alloc::{Allocator, Global}; |
21 | use crate::vec::Vec; |
22 | |
23 | mod entry; |
24 | |
25 | use Entry::*; |
26 | #[stable(feature = "rust1", since = "1.0.0")] |
27 | pub use entry::{Entry, OccupiedEntry, OccupiedError, VacantEntry}; |
28 | |
29 | /// Minimum number of elements in a node that is not a root. |
30 | /// We might temporarily have fewer elements during methods. |
31 | pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT; |
32 | |
33 | // A tree in a `BTreeMap` is a tree in the `node` module with additional invariants: |
34 | // - Keys must appear in ascending order (according to the key's type). |
35 | // - Every non-leaf node contains at least 1 element (has at least 2 children). |
36 | // - Every non-root node contains at least MIN_LEN elements. |
37 | // |
38 | // An empty map is represented either by the absence of a root node or by a |
39 | // root node that is an empty leaf. |
40 | |
41 | /// An ordered map based on a [B-Tree]. |
42 | /// |
43 | /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing |
44 | /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal |
45 | /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of |
46 | /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this |
47 | /// is done is *very* inefficient for modern computer architectures. In particular, every element |
48 | /// is stored in its own individually heap-allocated node. This means that every single insertion |
49 | /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these |
50 | /// are both notably expensive things to do in practice, we are forced to, at the very least, |
51 | /// reconsider the BST strategy. |
52 | /// |
53 | /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing |
54 | /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in |
55 | /// searches. However, this does mean that searches will have to do *more* comparisons on average. |
56 | /// The precise number of comparisons depends on the node search strategy used. For optimal cache |
57 | /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search |
58 | /// the node using binary search. As a compromise, one could also perform a linear search |
59 | /// that initially only checks every i<sup>th</sup> element for some choice of i. |
60 | /// |
61 | /// Currently, our implementation simply performs naive linear search. This provides excellent |
62 | /// performance on *small* nodes of elements which are cheap to compare. However in the future we |
63 | /// would like to further explore choosing the optimal search strategy based on the choice of B, |
64 | /// and possibly other factors. Using linear search, searching for a random element is expected |
65 | /// to take B * log(n) comparisons, which is generally worse than a BST. In practice, |
66 | /// however, performance is excellent. |
67 | /// |
68 | /// It is a logic error for a key to be modified in such a way that the key's ordering relative to |
69 | /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is |
70 | /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. |
71 | /// The behavior resulting from such a logic error is not specified, but will be encapsulated to the |
72 | /// `BTreeMap` that observed the logic error and not result in undefined behavior. This could |
73 | /// include panics, incorrect results, aborts, memory leaks, and non-termination. |
74 | /// |
75 | /// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::into_iter`], [`BTreeMap::values`], or |
76 | /// [`BTreeMap::keys`] produce their items in order by key, and take worst-case logarithmic and |
77 | /// amortized constant time per item returned. |
78 | /// |
79 | /// [B-Tree]: https://en.wikipedia.org/wiki/B-tree |
80 | /// [`Cell`]: core::cell::Cell |
81 | /// [`RefCell`]: core::cell::RefCell |
82 | /// |
83 | /// # Examples |
84 | /// |
85 | /// ``` |
86 | /// use std::collections::BTreeMap; |
87 | /// |
88 | /// // type inference lets us omit an explicit type signature (which |
89 | /// // would be `BTreeMap<&str, &str>` in this example). |
90 | /// let mut movie_reviews = BTreeMap::new(); |
91 | /// |
92 | /// // review some movies. |
93 | /// movie_reviews.insert("Office Space", "Deals with real issues in the workplace."); |
94 | /// movie_reviews.insert("Pulp Fiction", "Masterpiece."); |
95 | /// movie_reviews.insert("The Godfather", "Very enjoyable."); |
96 | /// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot."); |
97 | /// |
98 | /// // check for a specific one. |
99 | /// if !movie_reviews.contains_key("Les Misérables") { |
100 | /// println!("We've got {} reviews, but Les Misérables ain't one.", |
101 | /// movie_reviews.len()); |
102 | /// } |
103 | /// |
104 | /// // oops, this review has a lot of spelling mistakes, let's delete it. |
105 | /// movie_reviews.remove("The Blues Brothers"); |
106 | /// |
107 | /// // look up the values associated with some keys. |
108 | /// let to_find = ["Up!", "Office Space"]; |
109 | /// for movie in &to_find { |
110 | /// match movie_reviews.get(movie) { |
111 | /// Some(review) => println!("{movie}: {review}"), |
112 | /// None => println!("{movie} is unreviewed.") |
113 | /// } |
114 | /// } |
115 | /// |
116 | /// // Look up the value for a key (will panic if the key is not found). |
117 | /// println!("Movie review: {}", movie_reviews[ "Office Space"]); |
118 | /// |
119 | /// // iterate over everything. |
120 | /// for (movie, review) in &movie_reviews { |
121 | /// println!("{movie}:\" {review}\" "); |
122 | /// } |
123 | /// ``` |
124 | /// |
125 | /// A `BTreeMap` with a known list of items can be initialized from an array: |
126 | /// |
127 | /// ``` |
128 | /// use std::collections::BTreeMap; |
129 | /// |
130 | /// let solar_distance = BTreeMap::from([ |
131 | /// ("Mercury", 0.4), |
132 | /// ("Venus", 0.7), |
133 | /// ("Earth", 1.0), |
134 | /// ("Mars", 1.5), |
135 | /// ]); |
136 | /// ``` |
137 | /// |
138 | /// `BTreeMap` implements an [`Entry API`], which allows for complex |
139 | /// methods of getting, setting, updating and removing keys and their values: |
140 | /// |
141 | /// [`Entry API`]: BTreeMap::entry |
142 | /// |
143 | /// ``` |
144 | /// use std::collections::BTreeMap; |
145 | /// |
146 | /// // type inference lets us omit an explicit type signature (which |
147 | /// // would be `BTreeMap<&str, u8>` in this example). |
148 | /// let mut player_stats = BTreeMap::new(); |
149 | /// |
150 | /// fn random_stat_buff() -> u8 { |
151 | /// // could actually return some random value here - let's just return |
152 | /// // some fixed value for now |
153 | /// 42 |
154 | /// } |
155 | /// |
156 | /// // insert a key only if it doesn't already exist |
157 | /// player_stats.entry("health").or_insert(100); |
158 | /// |
159 | /// // insert a key using a function that provides a new value only if it |
160 | /// // doesn't already exist |
161 | /// player_stats.entry("defence").or_insert_with(random_stat_buff); |
162 | /// |
163 | /// // update a key, guarding against the key possibly not being set |
164 | /// let stat = player_stats.entry("attack").or_insert(100); |
165 | /// *stat += random_stat_buff(); |
166 | /// |
167 | /// // modify an entry before an insert with in-place mutation |
168 | /// player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100); |
169 | /// ``` |
170 | #[stable(feature = "rust1", since = "1.0.0")] |
171 | #[cfg_attr(not(test), rustc_diagnostic_item = "BTreeMap")] |
172 | #[rustc_insignificant_dtor] |
173 | pub struct BTreeMap< |
174 | K, |
175 | V, |
176 | #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global, |
177 | > { |
178 | root: Option<Root<K, V>>, |
179 | length: usize, |
180 | /// `ManuallyDrop` to control drop order (needs to be dropped after all the nodes). |
181 | pub(super) alloc: ManuallyDrop<A>, |
182 | // For dropck; the `Box` avoids making the `Unpin` impl more strict than before |
183 | _marker: PhantomData<crate::boxed::Box<(K, V), A>>, |
184 | } |
185 | |
186 | #[stable(feature = "btree_drop", since = "1.7.0")] |
187 | unsafe impl<#[may_dangle] K, #[ may_dangle] V, A: Allocator + Clone> Drop for BTreeMap<K, V, A> { |
188 | fn drop(&mut self) { |
189 | drop(unsafe { ptr::read(self) }.into_iter()) |
190 | } |
191 | } |
192 | |
193 | // FIXME: This implementation is "wrong", but changing it would be a breaking change. |
194 | // (The bounds of the automatic `UnwindSafe` implementation have been like this since Rust 1.50.) |
195 | // Maybe we can fix it nonetheless with a crater run, or if the `UnwindSafe` |
196 | // traits are deprecated, or disarmed (no longer causing hard errors) in the future. |
197 | #[stable(feature = "btree_unwindsafe", since = "1.64.0")] |
198 | impl<K, V, A: Allocator + Clone> core::panic::UnwindSafe for BTreeMap<K, V, A> |
199 | where |
200 | A: core::panic::UnwindSafe, |
201 | K: core::panic::RefUnwindSafe, |
202 | V: core::panic::RefUnwindSafe, |
203 | { |
204 | } |
205 | |
206 | #[stable(feature = "rust1", since = "1.0.0")] |
207 | impl<K: Clone, V: Clone, A: Allocator + Clone> Clone for BTreeMap<K, V, A> { |
208 | fn clone(&self) -> BTreeMap<K, V, A> { |
209 | fn clone_subtree<'a, K: Clone, V: Clone, A: Allocator + Clone>( |
210 | node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>, |
211 | alloc: A, |
212 | ) -> BTreeMap<K, V, A> |
213 | where |
214 | K: 'a, |
215 | V: 'a, |
216 | { |
217 | match node.force() { |
218 | Leaf(leaf) => { |
219 | let mut out_tree = BTreeMap { |
220 | root: Some(Root::new(alloc.clone())), |
221 | length: 0, |
222 | alloc: ManuallyDrop::new(alloc), |
223 | _marker: PhantomData, |
224 | }; |
225 | |
226 | { |
227 | let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped |
228 | let mut out_node = match root.borrow_mut().force() { |
229 | Leaf(leaf) => leaf, |
230 | Internal(_) => unreachable!(), |
231 | }; |
232 | |
233 | let mut in_edge = leaf.first_edge(); |
234 | while let Ok(kv) = in_edge.right_kv() { |
235 | let (k, v) = kv.into_kv(); |
236 | in_edge = kv.right_edge(); |
237 | |
238 | out_node.push(k.clone(), v.clone()); |
239 | out_tree.length += 1; |
240 | } |
241 | } |
242 | |
243 | out_tree |
244 | } |
245 | Internal(internal) => { |
246 | let mut out_tree = |
247 | clone_subtree(internal.first_edge().descend(), alloc.clone()); |
248 | |
249 | { |
250 | let out_root = out_tree.root.as_mut().unwrap(); |
251 | let mut out_node = out_root.push_internal_level(alloc.clone()); |
252 | let mut in_edge = internal.first_edge(); |
253 | while let Ok(kv) = in_edge.right_kv() { |
254 | let (k, v) = kv.into_kv(); |
255 | in_edge = kv.right_edge(); |
256 | |
257 | let k = (*k).clone(); |
258 | let v = (*v).clone(); |
259 | let subtree = clone_subtree(in_edge.descend(), alloc.clone()); |
260 | |
261 | // We can't destructure subtree directly |
262 | // because BTreeMap implements Drop |
263 | let (subroot, sublength) = unsafe { |
264 | let subtree = ManuallyDrop::new(subtree); |
265 | let root = ptr::read(&subtree.root); |
266 | let length = subtree.length; |
267 | (root, length) |
268 | }; |
269 | |
270 | out_node.push( |
271 | k, |
272 | v, |
273 | subroot.unwrap_or_else(|| Root::new(alloc.clone())), |
274 | ); |
275 | out_tree.length += 1 + sublength; |
276 | } |
277 | } |
278 | |
279 | out_tree |
280 | } |
281 | } |
282 | } |
283 | |
284 | if self.is_empty() { |
285 | BTreeMap::new_in((*self.alloc).clone()) |
286 | } else { |
287 | clone_subtree(self.root.as_ref().unwrap().reborrow(), (*self.alloc).clone()) // unwrap succeeds because not empty |
288 | } |
289 | } |
290 | } |
291 | |
292 | // Internal functionality for `BTreeSet`. |
293 | impl<K, A: Allocator + Clone> BTreeMap<K, SetValZST, A> { |
294 | pub(super) fn replace(&mut self, key: K) -> Option<K> |
295 | where |
296 | K: Ord, |
297 | { |
298 | let (map, dormant_map) = DormantMutRef::new(self); |
299 | let root_node = |
300 | map.root.get_or_insert_with(|| Root::new((*map.alloc).clone())).borrow_mut(); |
301 | match root_node.search_tree::<K>(&key) { |
302 | Found(mut kv) => Some(mem::replace(kv.key_mut(), key)), |
303 | GoDown(handle) => { |
304 | VacantEntry { |
305 | key, |
306 | handle: Some(handle), |
307 | dormant_map, |
308 | alloc: (*map.alloc).clone(), |
309 | _marker: PhantomData, |
310 | } |
311 | .insert(SetValZST); |
312 | None |
313 | } |
314 | } |
315 | } |
316 | |
317 | pub(super) fn get_or_insert_with<Q: ?Sized, F>(&mut self, q: &Q, f: F) -> &K |
318 | where |
319 | K: Borrow<Q> + Ord, |
320 | Q: Ord, |
321 | F: FnOnce(&Q) -> K, |
322 | { |
323 | let (map, dormant_map) = DormantMutRef::new(self); |
324 | let root_node = |
325 | map.root.get_or_insert_with(|| Root::new((*map.alloc).clone())).borrow_mut(); |
326 | match root_node.search_tree(q) { |
327 | Found(handle) => handle.into_kv_mut().0, |
328 | GoDown(handle) => { |
329 | let key = f(q); |
330 | assert!(*key.borrow() == *q, "new value is not equal"); |
331 | VacantEntry { |
332 | key, |
333 | handle: Some(handle), |
334 | dormant_map, |
335 | alloc: (*map.alloc).clone(), |
336 | _marker: PhantomData, |
337 | } |
338 | .insert_entry(SetValZST) |
339 | .into_key() |
340 | } |
341 | } |
342 | } |
343 | } |
344 | |
345 | /// An iterator over the entries of a `BTreeMap`. |
346 | /// |
347 | /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its |
348 | /// documentation for more. |
349 | /// |
350 | /// [`iter`]: BTreeMap::iter |
351 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
352 | #[stable(feature = "rust1", since = "1.0.0")] |
353 | pub struct Iter<'a, K: 'a, V: 'a> { |
354 | range: LazyLeafRange<marker::Immut<'a>, K, V>, |
355 | length: usize, |
356 | } |
357 | |
358 | #[stable(feature = "collection_debug", since = "1.17.0")] |
359 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { |
360 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
361 | f.debug_list().entries(self.clone()).finish() |
362 | } |
363 | } |
364 | |
365 | #[stable(feature = "default_iters", since = "1.70.0")] |
366 | impl<'a, K: 'a, V: 'a> Default for Iter<'a, K, V> { |
367 | /// Creates an empty `btree_map::Iter`. |
368 | /// |
369 | /// ``` |
370 | /// # use std::collections::btree_map; |
371 | /// let iter: btree_map::Iter<'_, u8, u8> = Default::default(); |
372 | /// assert_eq!(iter.len(), 0); |
373 | /// ``` |
374 | fn default() -> Self { |
375 | Iter { range: Default::default(), length: 0 } |
376 | } |
377 | } |
378 | |
379 | /// A mutable iterator over the entries of a `BTreeMap`. |
380 | /// |
381 | /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its |
382 | /// documentation for more. |
383 | /// |
384 | /// [`iter_mut`]: BTreeMap::iter_mut |
385 | #[stable(feature = "rust1", since = "1.0.0")] |
386 | pub struct IterMut<'a, K: 'a, V: 'a> { |
387 | range: LazyLeafRange<marker::ValMut<'a>, K, V>, |
388 | length: usize, |
389 | |
390 | // Be invariant in `K` and `V` |
391 | _marker: PhantomData<&'a mut (K, V)>, |
392 | } |
393 | |
394 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
395 | #[stable(feature = "collection_debug", since = "1.17.0")] |
396 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> { |
397 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
398 | let range: Iter<'_, K, V> = Iter { range: self.range.reborrow(), length: self.length }; |
399 | f.debug_list().entries(range).finish() |
400 | } |
401 | } |
402 | |
403 | #[stable(feature = "default_iters", since = "1.70.0")] |
404 | impl<'a, K: 'a, V: 'a> Default for IterMut<'a, K, V> { |
405 | /// Creates an empty `btree_map::IterMut`. |
406 | /// |
407 | /// ``` |
408 | /// # use std::collections::btree_map; |
409 | /// let iter: btree_map::IterMut<'_, u8, u8> = Default::default(); |
410 | /// assert_eq!(iter.len(), 0); |
411 | /// ``` |
412 | fn default() -> Self { |
413 | IterMut { range: Default::default(), length: 0, _marker: PhantomData {} } |
414 | } |
415 | } |
416 | |
417 | /// An owning iterator over the entries of a `BTreeMap`, sorted by key. |
418 | /// |
419 | /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`] |
420 | /// (provided by the [`IntoIterator`] trait). See its documentation for more. |
421 | /// |
422 | /// [`into_iter`]: IntoIterator::into_iter |
423 | #[stable(feature = "rust1", since = "1.0.0")] |
424 | #[rustc_insignificant_dtor] |
425 | pub struct IntoIter< |
426 | K, |
427 | V, |
428 | #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global, |
429 | > { |
430 | range: LazyLeafRange<marker::Dying, K, V>, |
431 | length: usize, |
432 | /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`. |
433 | alloc: A, |
434 | } |
435 | |
436 | impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> { |
437 | /// Returns an iterator of references over the remaining items. |
438 | #[inline] |
439 | pub(super) fn iter(&self) -> Iter<'_, K, V> { |
440 | Iter { range: self.range.reborrow(), length: self.length } |
441 | } |
442 | } |
443 | |
444 | #[stable(feature = "collection_debug", since = "1.17.0")] |
445 | impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for IntoIter<K, V, A> { |
446 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
447 | f.debug_list().entries(self.iter()).finish() |
448 | } |
449 | } |
450 | |
451 | #[stable(feature = "default_iters", since = "1.70.0")] |
452 | impl<K, V, A> Default for IntoIter<K, V, A> |
453 | where |
454 | A: Allocator + Default + Clone, |
455 | { |
456 | /// Creates an empty `btree_map::IntoIter`. |
457 | /// |
458 | /// ``` |
459 | /// # use std::collections::btree_map; |
460 | /// let iter: btree_map::IntoIter<u8, u8> = Default::default(); |
461 | /// assert_eq!(iter.len(), 0); |
462 | /// ``` |
463 | fn default() -> Self { |
464 | IntoIter { range: Default::default(), length: 0, alloc: Default::default() } |
465 | } |
466 | } |
467 | |
468 | /// An iterator over the keys of a `BTreeMap`. |
469 | /// |
470 | /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its |
471 | /// documentation for more. |
472 | /// |
473 | /// [`keys`]: BTreeMap::keys |
474 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
475 | #[stable(feature = "rust1", since = "1.0.0")] |
476 | pub struct Keys<'a, K, V> { |
477 | inner: Iter<'a, K, V>, |
478 | } |
479 | |
480 | #[stable(feature = "collection_debug", since = "1.17.0")] |
481 | impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> { |
482 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
483 | f.debug_list().entries(self.clone()).finish() |
484 | } |
485 | } |
486 | |
487 | /// An iterator over the values of a `BTreeMap`. |
488 | /// |
489 | /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its |
490 | /// documentation for more. |
491 | /// |
492 | /// [`values`]: BTreeMap::values |
493 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
494 | #[stable(feature = "rust1", since = "1.0.0")] |
495 | pub struct Values<'a, K, V> { |
496 | inner: Iter<'a, K, V>, |
497 | } |
498 | |
499 | #[stable(feature = "collection_debug", since = "1.17.0")] |
500 | impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> { |
501 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
502 | f.debug_list().entries(self.clone()).finish() |
503 | } |
504 | } |
505 | |
506 | /// A mutable iterator over the values of a `BTreeMap`. |
507 | /// |
508 | /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its |
509 | /// documentation for more. |
510 | /// |
511 | /// [`values_mut`]: BTreeMap::values_mut |
512 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
513 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
514 | pub struct ValuesMut<'a, K, V> { |
515 | inner: IterMut<'a, K, V>, |
516 | } |
517 | |
518 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
519 | impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> { |
520 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
521 | f.debug_list().entries(self.inner.iter().map(|(_, val: &V)| val)).finish() |
522 | } |
523 | } |
524 | |
525 | /// An owning iterator over the keys of a `BTreeMap`. |
526 | /// |
527 | /// This `struct` is created by the [`into_keys`] method on [`BTreeMap`]. |
528 | /// See its documentation for more. |
529 | /// |
530 | /// [`into_keys`]: BTreeMap::into_keys |
531 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
532 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
533 | pub struct IntoKeys<K, V, A: Allocator + Clone = Global> { |
534 | inner: IntoIter<K, V, A>, |
535 | } |
536 | |
537 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
538 | impl<K: fmt::Debug, V, A: Allocator + Clone> fmt::Debug for IntoKeys<K, V, A> { |
539 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
540 | f.debug_list().entries(self.inner.iter().map(|(key: &K, _)| key)).finish() |
541 | } |
542 | } |
543 | |
544 | /// An owning iterator over the values of a `BTreeMap`. |
545 | /// |
546 | /// This `struct` is created by the [`into_values`] method on [`BTreeMap`]. |
547 | /// See its documentation for more. |
548 | /// |
549 | /// [`into_values`]: BTreeMap::into_values |
550 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
551 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
552 | pub struct IntoValues< |
553 | K, |
554 | V, |
555 | #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global, |
556 | > { |
557 | inner: IntoIter<K, V, A>, |
558 | } |
559 | |
560 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
561 | impl<K, V: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoValues<K, V, A> { |
562 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
563 | f.debug_list().entries(self.inner.iter().map(|(_, val: &V)| val)).finish() |
564 | } |
565 | } |
566 | |
567 | /// An iterator over a sub-range of entries in a `BTreeMap`. |
568 | /// |
569 | /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its |
570 | /// documentation for more. |
571 | /// |
572 | /// [`range`]: BTreeMap::range |
573 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
574 | #[stable(feature = "btree_range", since = "1.17.0")] |
575 | pub struct Range<'a, K: 'a, V: 'a> { |
576 | inner: LeafRange<marker::Immut<'a>, K, V>, |
577 | } |
578 | |
579 | #[stable(feature = "collection_debug", since = "1.17.0")] |
580 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> { |
581 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
582 | f.debug_list().entries(self.clone()).finish() |
583 | } |
584 | } |
585 | |
586 | /// A mutable iterator over a sub-range of entries in a `BTreeMap`. |
587 | /// |
588 | /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its |
589 | /// documentation for more. |
590 | /// |
591 | /// [`range_mut`]: BTreeMap::range_mut |
592 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
593 | #[stable(feature = "btree_range", since = "1.17.0")] |
594 | pub struct RangeMut<'a, K: 'a, V: 'a> { |
595 | inner: LeafRange<marker::ValMut<'a>, K, V>, |
596 | |
597 | // Be invariant in `K` and `V` |
598 | _marker: PhantomData<&'a mut (K, V)>, |
599 | } |
600 | |
601 | #[stable(feature = "collection_debug", since = "1.17.0")] |
602 | impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> { |
603 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
604 | let range: Range<'_, K, V> = Range { inner: self.inner.reborrow() }; |
605 | f.debug_list().entries(range).finish() |
606 | } |
607 | } |
608 | |
609 | impl<K, V> BTreeMap<K, V> { |
610 | /// Makes a new, empty `BTreeMap`. |
611 | /// |
612 | /// Does not allocate anything on its own. |
613 | /// |
614 | /// # Examples |
615 | /// |
616 | /// ``` |
617 | /// use std::collections::BTreeMap; |
618 | /// |
619 | /// let mut map = BTreeMap::new(); |
620 | /// |
621 | /// // entries can now be inserted into the empty map |
622 | /// map.insert(1, "a"); |
623 | /// ``` |
624 | #[stable(feature = "rust1", since = "1.0.0")] |
625 | #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")] |
626 | #[inline] |
627 | #[must_use] |
628 | pub const fn new() -> BTreeMap<K, V> { |
629 | BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global), _marker: PhantomData } |
630 | } |
631 | } |
632 | |
633 | impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { |
634 | /// Clears the map, removing all elements. |
635 | /// |
636 | /// # Examples |
637 | /// |
638 | /// ``` |
639 | /// use std::collections::BTreeMap; |
640 | /// |
641 | /// let mut a = BTreeMap::new(); |
642 | /// a.insert(1, "a"); |
643 | /// a.clear(); |
644 | /// assert!(a.is_empty()); |
645 | /// ``` |
646 | #[stable(feature = "rust1", since = "1.0.0")] |
647 | pub fn clear(&mut self) { |
648 | // avoid moving the allocator |
649 | drop(BTreeMap { |
650 | root: mem::replace(&mut self.root, None), |
651 | length: mem::replace(&mut self.length, 0), |
652 | alloc: self.alloc.clone(), |
653 | _marker: PhantomData, |
654 | }); |
655 | } |
656 | |
657 | /// Makes a new empty BTreeMap with a reasonable choice for B. |
658 | /// |
659 | /// # Examples |
660 | /// |
661 | /// ``` |
662 | /// # #![feature(allocator_api)] |
663 | /// # #![feature(btreemap_alloc)] |
664 | /// use std::collections::BTreeMap; |
665 | /// use std::alloc::Global; |
666 | /// |
667 | /// let mut map = BTreeMap::new_in(Global); |
668 | /// |
669 | /// // entries can now be inserted into the empty map |
670 | /// map.insert(1, "a"); |
671 | /// ``` |
672 | #[unstable(feature = "btreemap_alloc", issue = "32838")] |
673 | pub const fn new_in(alloc: A) -> BTreeMap<K, V, A> { |
674 | BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(alloc), _marker: PhantomData } |
675 | } |
676 | } |
677 | |
678 | impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { |
679 | /// Returns a reference to the value corresponding to the key. |
680 | /// |
681 | /// The key may be any borrowed form of the map's key type, but the ordering |
682 | /// on the borrowed form *must* match the ordering on the key type. |
683 | /// |
684 | /// # Examples |
685 | /// |
686 | /// ``` |
687 | /// use std::collections::BTreeMap; |
688 | /// |
689 | /// let mut map = BTreeMap::new(); |
690 | /// map.insert(1, "a"); |
691 | /// assert_eq!(map.get(&1), Some(&"a")); |
692 | /// assert_eq!(map.get(&2), None); |
693 | /// ``` |
694 | #[stable(feature = "rust1", since = "1.0.0")] |
695 | pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> |
696 | where |
697 | K: Borrow<Q> + Ord, |
698 | Q: Ord, |
699 | { |
700 | let root_node = self.root.as_ref()?.reborrow(); |
701 | match root_node.search_tree(key) { |
702 | Found(handle) => Some(handle.into_kv().1), |
703 | GoDown(_) => None, |
704 | } |
705 | } |
706 | |
707 | /// Returns the key-value pair corresponding to the supplied key. This is |
708 | /// potentially useful: |
709 | /// - for key types where non-identical keys can be considered equal; |
710 | /// - for getting the `&K` stored key value from a borrowed `&Q` lookup key; or |
711 | /// - for getting a reference to a key with the same lifetime as the collection. |
712 | /// |
713 | /// The supplied key may be any borrowed form of the map's key type, but the ordering |
714 | /// on the borrowed form *must* match the ordering on the key type. |
715 | /// |
716 | /// # Examples |
717 | /// |
718 | /// ``` |
719 | /// use std::cmp::Ordering; |
720 | /// use std::collections::BTreeMap; |
721 | /// |
722 | /// #[derive(Clone, Copy, Debug)] |
723 | /// struct S { |
724 | /// id: u32, |
725 | /// # #[allow(unused)] // prevents a "field `name` is never read" error |
726 | /// name: &'static str, // ignored by equality and ordering operations |
727 | /// } |
728 | /// |
729 | /// impl PartialEq for S { |
730 | /// fn eq(&self, other: &S) -> bool { |
731 | /// self.id == other.id |
732 | /// } |
733 | /// } |
734 | /// |
735 | /// impl Eq for S {} |
736 | /// |
737 | /// impl PartialOrd for S { |
738 | /// fn partial_cmp(&self, other: &S) -> Option<Ordering> { |
739 | /// self.id.partial_cmp(&other.id) |
740 | /// } |
741 | /// } |
742 | /// |
743 | /// impl Ord for S { |
744 | /// fn cmp(&self, other: &S) -> Ordering { |
745 | /// self.id.cmp(&other.id) |
746 | /// } |
747 | /// } |
748 | /// |
749 | /// let j_a = S { id: 1, name: "Jessica"}; |
750 | /// let j_b = S { id: 1, name: "Jess"}; |
751 | /// let p = S { id: 2, name: "Paul"}; |
752 | /// assert_eq!(j_a, j_b); |
753 | /// |
754 | /// let mut map = BTreeMap::new(); |
755 | /// map.insert(j_a, "Paris"); |
756 | /// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris"))); |
757 | /// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case |
758 | /// assert_eq!(map.get_key_value(&p), None); |
759 | /// ``` |
760 | #[stable(feature = "map_get_key_value", since = "1.40.0")] |
761 | pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)> |
762 | where |
763 | K: Borrow<Q> + Ord, |
764 | Q: Ord, |
765 | { |
766 | let root_node = self.root.as_ref()?.reborrow(); |
767 | match root_node.search_tree(k) { |
768 | Found(handle) => Some(handle.into_kv()), |
769 | GoDown(_) => None, |
770 | } |
771 | } |
772 | |
773 | /// Returns the first key-value pair in the map. |
774 | /// The key in this pair is the minimum key in the map. |
775 | /// |
776 | /// # Examples |
777 | /// |
778 | /// ``` |
779 | /// use std::collections::BTreeMap; |
780 | /// |
781 | /// let mut map = BTreeMap::new(); |
782 | /// assert_eq!(map.first_key_value(), None); |
783 | /// map.insert(1, "b"); |
784 | /// map.insert(2, "a"); |
785 | /// assert_eq!(map.first_key_value(), Some((&1, &"b"))); |
786 | /// ``` |
787 | #[stable(feature = "map_first_last", since = "1.66.0")] |
788 | pub fn first_key_value(&self) -> Option<(&K, &V)> |
789 | where |
790 | K: Ord, |
791 | { |
792 | let root_node = self.root.as_ref()?.reborrow(); |
793 | root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv) |
794 | } |
795 | |
796 | /// Returns the first entry in the map for in-place manipulation. |
797 | /// The key of this entry is the minimum key in the map. |
798 | /// |
799 | /// # Examples |
800 | /// |
801 | /// ``` |
802 | /// use std::collections::BTreeMap; |
803 | /// |
804 | /// let mut map = BTreeMap::new(); |
805 | /// map.insert(1, "a"); |
806 | /// map.insert(2, "b"); |
807 | /// if let Some(mut entry) = map.first_entry() { |
808 | /// if *entry.key() > 0 { |
809 | /// entry.insert("first"); |
810 | /// } |
811 | /// } |
812 | /// assert_eq!(*map.get(&1).unwrap(), "first"); |
813 | /// assert_eq!(*map.get(&2).unwrap(), "b"); |
814 | /// ``` |
815 | #[stable(feature = "map_first_last", since = "1.66.0")] |
816 | pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>> |
817 | where |
818 | K: Ord, |
819 | { |
820 | let (map, dormant_map) = DormantMutRef::new(self); |
821 | let root_node = map.root.as_mut()?.borrow_mut(); |
822 | let kv = root_node.first_leaf_edge().right_kv().ok()?; |
823 | Some(OccupiedEntry { |
824 | handle: kv.forget_node_type(), |
825 | dormant_map, |
826 | alloc: (*map.alloc).clone(), |
827 | _marker: PhantomData, |
828 | }) |
829 | } |
830 | |
831 | /// Removes and returns the first element in the map. |
832 | /// The key of this element is the minimum key that was in the map. |
833 | /// |
834 | /// # Examples |
835 | /// |
836 | /// Draining elements in ascending order, while keeping a usable map each iteration. |
837 | /// |
838 | /// ``` |
839 | /// use std::collections::BTreeMap; |
840 | /// |
841 | /// let mut map = BTreeMap::new(); |
842 | /// map.insert(1, "a"); |
843 | /// map.insert(2, "b"); |
844 | /// while let Some((key, _val)) = map.pop_first() { |
845 | /// assert!(map.iter().all(|(k, _v)| *k > key)); |
846 | /// } |
847 | /// assert!(map.is_empty()); |
848 | /// ``` |
849 | #[stable(feature = "map_first_last", since = "1.66.0")] |
850 | pub fn pop_first(&mut self) -> Option<(K, V)> |
851 | where |
852 | K: Ord, |
853 | { |
854 | self.first_entry().map(|entry| entry.remove_entry()) |
855 | } |
856 | |
857 | /// Returns the last key-value pair in the map. |
858 | /// The key in this pair is the maximum key in the map. |
859 | /// |
860 | /// # Examples |
861 | /// |
862 | /// ``` |
863 | /// use std::collections::BTreeMap; |
864 | /// |
865 | /// let mut map = BTreeMap::new(); |
866 | /// map.insert(1, "b"); |
867 | /// map.insert(2, "a"); |
868 | /// assert_eq!(map.last_key_value(), Some((&2, &"a"))); |
869 | /// ``` |
870 | #[stable(feature = "map_first_last", since = "1.66.0")] |
871 | pub fn last_key_value(&self) -> Option<(&K, &V)> |
872 | where |
873 | K: Ord, |
874 | { |
875 | let root_node = self.root.as_ref()?.reborrow(); |
876 | root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv) |
877 | } |
878 | |
879 | /// Returns the last entry in the map for in-place manipulation. |
880 | /// The key of this entry is the maximum key in the map. |
881 | /// |
882 | /// # Examples |
883 | /// |
884 | /// ``` |
885 | /// use std::collections::BTreeMap; |
886 | /// |
887 | /// let mut map = BTreeMap::new(); |
888 | /// map.insert(1, "a"); |
889 | /// map.insert(2, "b"); |
890 | /// if let Some(mut entry) = map.last_entry() { |
891 | /// if *entry.key() > 0 { |
892 | /// entry.insert("last"); |
893 | /// } |
894 | /// } |
895 | /// assert_eq!(*map.get(&1).unwrap(), "a"); |
896 | /// assert_eq!(*map.get(&2).unwrap(), "last"); |
897 | /// ``` |
898 | #[stable(feature = "map_first_last", since = "1.66.0")] |
899 | pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>> |
900 | where |
901 | K: Ord, |
902 | { |
903 | let (map, dormant_map) = DormantMutRef::new(self); |
904 | let root_node = map.root.as_mut()?.borrow_mut(); |
905 | let kv = root_node.last_leaf_edge().left_kv().ok()?; |
906 | Some(OccupiedEntry { |
907 | handle: kv.forget_node_type(), |
908 | dormant_map, |
909 | alloc: (*map.alloc).clone(), |
910 | _marker: PhantomData, |
911 | }) |
912 | } |
913 | |
914 | /// Removes and returns the last element in the map. |
915 | /// The key of this element is the maximum key that was in the map. |
916 | /// |
917 | /// # Examples |
918 | /// |
919 | /// Draining elements in descending order, while keeping a usable map each iteration. |
920 | /// |
921 | /// ``` |
922 | /// use std::collections::BTreeMap; |
923 | /// |
924 | /// let mut map = BTreeMap::new(); |
925 | /// map.insert(1, "a"); |
926 | /// map.insert(2, "b"); |
927 | /// while let Some((key, _val)) = map.pop_last() { |
928 | /// assert!(map.iter().all(|(k, _v)| *k < key)); |
929 | /// } |
930 | /// assert!(map.is_empty()); |
931 | /// ``` |
932 | #[stable(feature = "map_first_last", since = "1.66.0")] |
933 | pub fn pop_last(&mut self) -> Option<(K, V)> |
934 | where |
935 | K: Ord, |
936 | { |
937 | self.last_entry().map(|entry| entry.remove_entry()) |
938 | } |
939 | |
940 | /// Returns `true` if the map contains a value for the specified key. |
941 | /// |
942 | /// The key may be any borrowed form of the map's key type, but the ordering |
943 | /// on the borrowed form *must* match the ordering on the key type. |
944 | /// |
945 | /// # Examples |
946 | /// |
947 | /// ``` |
948 | /// use std::collections::BTreeMap; |
949 | /// |
950 | /// let mut map = BTreeMap::new(); |
951 | /// map.insert(1, "a"); |
952 | /// assert_eq!(map.contains_key(&1), true); |
953 | /// assert_eq!(map.contains_key(&2), false); |
954 | /// ``` |
955 | #[stable(feature = "rust1", since = "1.0.0")] |
956 | #[cfg_attr(not(test), rustc_diagnostic_item = "btreemap_contains_key")] |
957 | pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool |
958 | where |
959 | K: Borrow<Q> + Ord, |
960 | Q: Ord, |
961 | { |
962 | self.get(key).is_some() |
963 | } |
964 | |
965 | /// Returns a mutable reference to the value corresponding to the key. |
966 | /// |
967 | /// The key may be any borrowed form of the map's key type, but the ordering |
968 | /// on the borrowed form *must* match the ordering on the key type. |
969 | /// |
970 | /// # Examples |
971 | /// |
972 | /// ``` |
973 | /// use std::collections::BTreeMap; |
974 | /// |
975 | /// let mut map = BTreeMap::new(); |
976 | /// map.insert(1, "a"); |
977 | /// if let Some(x) = map.get_mut(&1) { |
978 | /// *x = "b"; |
979 | /// } |
980 | /// assert_eq!(map[&1], "b"); |
981 | /// ``` |
982 | // See `get` for implementation notes, this is basically a copy-paste with mut's added |
983 | #[stable(feature = "rust1", since = "1.0.0")] |
984 | pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> |
985 | where |
986 | K: Borrow<Q> + Ord, |
987 | Q: Ord, |
988 | { |
989 | let root_node = self.root.as_mut()?.borrow_mut(); |
990 | match root_node.search_tree(key) { |
991 | Found(handle) => Some(handle.into_val_mut()), |
992 | GoDown(_) => None, |
993 | } |
994 | } |
995 | |
996 | /// Inserts a key-value pair into the map. |
997 | /// |
998 | /// If the map did not have this key present, `None` is returned. |
999 | /// |
1000 | /// If the map did have this key present, the value is updated, and the old |
1001 | /// value is returned. The key is not updated, though; this matters for |
1002 | /// types that can be `==` without being identical. See the [module-level |
1003 | /// documentation] for more. |
1004 | /// |
1005 | /// [module-level documentation]: index.html#insert-and-complex-keys |
1006 | /// |
1007 | /// # Examples |
1008 | /// |
1009 | /// ``` |
1010 | /// use std::collections::BTreeMap; |
1011 | /// |
1012 | /// let mut map = BTreeMap::new(); |
1013 | /// assert_eq!(map.insert(37, "a"), None); |
1014 | /// assert_eq!(map.is_empty(), false); |
1015 | /// |
1016 | /// map.insert(37, "b"); |
1017 | /// assert_eq!(map.insert(37, "c"), Some( "b")); |
1018 | /// assert_eq!(map[&37], "c"); |
1019 | /// ``` |
1020 | #[stable(feature = "rust1", since = "1.0.0")] |
1021 | #[rustc_confusables( "push", "put", "set")] |
1022 | #[cfg_attr(not(test), rustc_diagnostic_item = "btreemap_insert")] |
1023 | pub fn insert(&mut self, key: K, value: V) -> Option<V> |
1024 | where |
1025 | K: Ord, |
1026 | { |
1027 | match self.entry(key) { |
1028 | Occupied(mut entry) => Some(entry.insert(value)), |
1029 | Vacant(entry) => { |
1030 | entry.insert(value); |
1031 | None |
1032 | } |
1033 | } |
1034 | } |
1035 | |
1036 | /// Tries to insert a key-value pair into the map, and returns |
1037 | /// a mutable reference to the value in the entry. |
1038 | /// |
1039 | /// If the map already had this key present, nothing is updated, and |
1040 | /// an error containing the occupied entry and the value is returned. |
1041 | /// |
1042 | /// # Examples |
1043 | /// |
1044 | /// ``` |
1045 | /// #![feature(map_try_insert)] |
1046 | /// |
1047 | /// use std::collections::BTreeMap; |
1048 | /// |
1049 | /// let mut map = BTreeMap::new(); |
1050 | /// assert_eq!(map.try_insert(37, "a").unwrap(), & "a"); |
1051 | /// |
1052 | /// let err = map.try_insert(37, "b").unwrap_err(); |
1053 | /// assert_eq!(err.entry.key(), &37); |
1054 | /// assert_eq!(err.entry.get(), &"a"); |
1055 | /// assert_eq!(err.value, "b"); |
1056 | /// ``` |
1057 | #[unstable(feature = "map_try_insert", issue = "82766")] |
1058 | pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V, A>> |
1059 | where |
1060 | K: Ord, |
1061 | { |
1062 | match self.entry(key) { |
1063 | Occupied(entry) => Err(OccupiedError { entry, value }), |
1064 | Vacant(entry) => Ok(entry.insert(value)), |
1065 | } |
1066 | } |
1067 | |
1068 | /// Removes a key from the map, returning the value at the key if the key |
1069 | /// was previously in the map. |
1070 | /// |
1071 | /// The key may be any borrowed form of the map's key type, but the ordering |
1072 | /// on the borrowed form *must* match the ordering on the key type. |
1073 | /// |
1074 | /// # Examples |
1075 | /// |
1076 | /// ``` |
1077 | /// use std::collections::BTreeMap; |
1078 | /// |
1079 | /// let mut map = BTreeMap::new(); |
1080 | /// map.insert(1, "a"); |
1081 | /// assert_eq!(map.remove(&1), Some("a")); |
1082 | /// assert_eq!(map.remove(&1), None); |
1083 | /// ``` |
1084 | #[stable(feature = "rust1", since = "1.0.0")] |
1085 | #[rustc_confusables( "delete", "take")] |
1086 | pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> |
1087 | where |
1088 | K: Borrow<Q> + Ord, |
1089 | Q: Ord, |
1090 | { |
1091 | self.remove_entry(key).map(|(_, v)| v) |
1092 | } |
1093 | |
1094 | /// Removes a key from the map, returning the stored key and value if the key |
1095 | /// was previously in the map. |
1096 | /// |
1097 | /// The key may be any borrowed form of the map's key type, but the ordering |
1098 | /// on the borrowed form *must* match the ordering on the key type. |
1099 | /// |
1100 | /// # Examples |
1101 | /// |
1102 | /// ``` |
1103 | /// use std::collections::BTreeMap; |
1104 | /// |
1105 | /// let mut map = BTreeMap::new(); |
1106 | /// map.insert(1, "a"); |
1107 | /// assert_eq!(map.remove_entry(&1), Some((1, "a"))); |
1108 | /// assert_eq!(map.remove_entry(&1), None); |
1109 | /// ``` |
1110 | #[stable(feature = "btreemap_remove_entry", since = "1.45.0")] |
1111 | pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> |
1112 | where |
1113 | K: Borrow<Q> + Ord, |
1114 | Q: Ord, |
1115 | { |
1116 | let (map, dormant_map) = DormantMutRef::new(self); |
1117 | let root_node = map.root.as_mut()?.borrow_mut(); |
1118 | match root_node.search_tree(key) { |
1119 | Found(handle) => Some( |
1120 | OccupiedEntry { |
1121 | handle, |
1122 | dormant_map, |
1123 | alloc: (*map.alloc).clone(), |
1124 | _marker: PhantomData, |
1125 | } |
1126 | .remove_entry(), |
1127 | ), |
1128 | GoDown(_) => None, |
1129 | } |
1130 | } |
1131 | |
1132 | /// Retains only the elements specified by the predicate. |
1133 | /// |
1134 | /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`. |
1135 | /// The elements are visited in ascending key order. |
1136 | /// |
1137 | /// # Examples |
1138 | /// |
1139 | /// ``` |
1140 | /// use std::collections::BTreeMap; |
1141 | /// |
1142 | /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect(); |
1143 | /// // Keep only the elements with even-numbered keys. |
1144 | /// map.retain(|&k, _| k % 2 == 0); |
1145 | /// assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)])); |
1146 | /// ``` |
1147 | #[inline] |
1148 | #[stable(feature = "btree_retain", since = "1.53.0")] |
1149 | pub fn retain<F>(&mut self, mut f: F) |
1150 | where |
1151 | K: Ord, |
1152 | F: FnMut(&K, &mut V) -> bool, |
1153 | { |
1154 | self.extract_if(.., |k, v| !f(k, v)).for_each(drop); |
1155 | } |
1156 | |
1157 | /// Moves all elements from `other` into `self`, leaving `other` empty. |
1158 | /// |
1159 | /// If a key from `other` is already present in `self`, the respective |
1160 | /// value from `self` will be overwritten with the respective value from `other`. |
1161 | /// |
1162 | /// # Examples |
1163 | /// |
1164 | /// ``` |
1165 | /// use std::collections::BTreeMap; |
1166 | /// |
1167 | /// let mut a = BTreeMap::new(); |
1168 | /// a.insert(1, "a"); |
1169 | /// a.insert(2, "b"); |
1170 | /// a.insert(3, "c"); // Note: Key (3) also present in b. |
1171 | /// |
1172 | /// let mut b = BTreeMap::new(); |
1173 | /// b.insert(3, "d"); // Note: Key (3) also present in a. |
1174 | /// b.insert(4, "e"); |
1175 | /// b.insert(5, "f"); |
1176 | /// |
1177 | /// a.append(&mut b); |
1178 | /// |
1179 | /// assert_eq!(a.len(), 5); |
1180 | /// assert_eq!(b.len(), 0); |
1181 | /// |
1182 | /// assert_eq!(a[&1], "a"); |
1183 | /// assert_eq!(a[&2], "b"); |
1184 | /// assert_eq!(a[&3], "d"); // Note: "c" has been overwritten. |
1185 | /// assert_eq!(a[&4], "e"); |
1186 | /// assert_eq!(a[&5], "f"); |
1187 | /// ``` |
1188 | #[stable(feature = "btree_append", since = "1.11.0")] |
1189 | pub fn append(&mut self, other: &mut Self) |
1190 | where |
1191 | K: Ord, |
1192 | A: Clone, |
1193 | { |
1194 | // Do we have to append anything at all? |
1195 | if other.is_empty() { |
1196 | return; |
1197 | } |
1198 | |
1199 | // We can just swap `self` and `other` if `self` is empty. |
1200 | if self.is_empty() { |
1201 | mem::swap(self, other); |
1202 | return; |
1203 | } |
1204 | |
1205 | let self_iter = mem::replace(self, Self::new_in((*self.alloc).clone())).into_iter(); |
1206 | let other_iter = mem::replace(other, Self::new_in((*self.alloc).clone())).into_iter(); |
1207 | let root = self.root.get_or_insert_with(|| Root::new((*self.alloc).clone())); |
1208 | root.append_from_sorted_iters( |
1209 | self_iter, |
1210 | other_iter, |
1211 | &mut self.length, |
1212 | (*self.alloc).clone(), |
1213 | ) |
1214 | } |
1215 | |
1216 | /// Constructs a double-ended iterator over a sub-range of elements in the map. |
1217 | /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will |
1218 | /// yield elements from min (inclusive) to max (exclusive). |
1219 | /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example |
1220 | /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive |
1221 | /// range from 4 to 10. |
1222 | /// |
1223 | /// # Panics |
1224 | /// |
1225 | /// Panics if range `start > end`. |
1226 | /// Panics if range `start == end` and both bounds are `Excluded`. |
1227 | /// |
1228 | /// # Examples |
1229 | /// |
1230 | /// ``` |
1231 | /// use std::collections::BTreeMap; |
1232 | /// use std::ops::Bound::Included; |
1233 | /// |
1234 | /// let mut map = BTreeMap::new(); |
1235 | /// map.insert(3, "a"); |
1236 | /// map.insert(5, "b"); |
1237 | /// map.insert(8, "c"); |
1238 | /// for (&key, &value) in map.range((Included(&4), Included(&8))) { |
1239 | /// println!("{key}: {value}"); |
1240 | /// } |
1241 | /// assert_eq!(Some((&5, &"b")), map.range(4..).next()); |
1242 | /// ``` |
1243 | #[stable(feature = "btree_range", since = "1.17.0")] |
1244 | pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V> |
1245 | where |
1246 | T: Ord, |
1247 | K: Borrow<T> + Ord, |
1248 | R: RangeBounds<T>, |
1249 | { |
1250 | if let Some(root) = &self.root { |
1251 | Range { inner: root.reborrow().range_search(range) } |
1252 | } else { |
1253 | Range { inner: LeafRange::none() } |
1254 | } |
1255 | } |
1256 | |
1257 | /// Constructs a mutable double-ended iterator over a sub-range of elements in the map. |
1258 | /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will |
1259 | /// yield elements from min (inclusive) to max (exclusive). |
1260 | /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example |
1261 | /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive |
1262 | /// range from 4 to 10. |
1263 | /// |
1264 | /// # Panics |
1265 | /// |
1266 | /// Panics if range `start > end`. |
1267 | /// Panics if range `start == end` and both bounds are `Excluded`. |
1268 | /// |
1269 | /// # Examples |
1270 | /// |
1271 | /// ``` |
1272 | /// use std::collections::BTreeMap; |
1273 | /// |
1274 | /// let mut map: BTreeMap<&str, i32> = |
1275 | /// [("Alice", 0), ( "Bob", 0), ( "Carol", 0), ( "Cheryl", 0)].into(); |
1276 | /// for (_, balance) in map.range_mut("B".. "Cheryl") { |
1277 | /// *balance += 100; |
1278 | /// } |
1279 | /// for (name, balance) in &map { |
1280 | /// println!("{name} => {balance}"); |
1281 | /// } |
1282 | /// ``` |
1283 | #[stable(feature = "btree_range", since = "1.17.0")] |
1284 | pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V> |
1285 | where |
1286 | T: Ord, |
1287 | K: Borrow<T> + Ord, |
1288 | R: RangeBounds<T>, |
1289 | { |
1290 | if let Some(root) = &mut self.root { |
1291 | RangeMut { inner: root.borrow_valmut().range_search(range), _marker: PhantomData } |
1292 | } else { |
1293 | RangeMut { inner: LeafRange::none(), _marker: PhantomData } |
1294 | } |
1295 | } |
1296 | |
1297 | /// Gets the given key's corresponding entry in the map for in-place manipulation. |
1298 | /// |
1299 | /// # Examples |
1300 | /// |
1301 | /// ``` |
1302 | /// use std::collections::BTreeMap; |
1303 | /// |
1304 | /// let mut count: BTreeMap<&str, usize> = BTreeMap::new(); |
1305 | /// |
1306 | /// // count the number of occurrences of letters in the vec |
1307 | /// for x in ["a", "b", "a", "c", "a", "b"] { |
1308 | /// count.entry(x).and_modify(|curr| *curr += 1).or_insert(1); |
1309 | /// } |
1310 | /// |
1311 | /// assert_eq!(count["a"], 3); |
1312 | /// assert_eq!(count["b"], 2); |
1313 | /// assert_eq!(count["c"], 1); |
1314 | /// ``` |
1315 | #[stable(feature = "rust1", since = "1.0.0")] |
1316 | pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A> |
1317 | where |
1318 | K: Ord, |
1319 | { |
1320 | let (map, dormant_map) = DormantMutRef::new(self); |
1321 | match map.root { |
1322 | None => Vacant(VacantEntry { |
1323 | key, |
1324 | handle: None, |
1325 | dormant_map, |
1326 | alloc: (*map.alloc).clone(), |
1327 | _marker: PhantomData, |
1328 | }), |
1329 | Some(ref mut root) => match root.borrow_mut().search_tree(&key) { |
1330 | Found(handle) => Occupied(OccupiedEntry { |
1331 | handle, |
1332 | dormant_map, |
1333 | alloc: (*map.alloc).clone(), |
1334 | _marker: PhantomData, |
1335 | }), |
1336 | GoDown(handle) => Vacant(VacantEntry { |
1337 | key, |
1338 | handle: Some(handle), |
1339 | dormant_map, |
1340 | alloc: (*map.alloc).clone(), |
1341 | _marker: PhantomData, |
1342 | }), |
1343 | }, |
1344 | } |
1345 | } |
1346 | |
1347 | /// Splits the collection into two at the given key. Returns everything after the given key, |
1348 | /// including the key. |
1349 | /// |
1350 | /// # Examples |
1351 | /// |
1352 | /// ``` |
1353 | /// use std::collections::BTreeMap; |
1354 | /// |
1355 | /// let mut a = BTreeMap::new(); |
1356 | /// a.insert(1, "a"); |
1357 | /// a.insert(2, "b"); |
1358 | /// a.insert(3, "c"); |
1359 | /// a.insert(17, "d"); |
1360 | /// a.insert(41, "e"); |
1361 | /// |
1362 | /// let b = a.split_off(&3); |
1363 | /// |
1364 | /// assert_eq!(a.len(), 2); |
1365 | /// assert_eq!(b.len(), 3); |
1366 | /// |
1367 | /// assert_eq!(a[&1], "a"); |
1368 | /// assert_eq!(a[&2], "b"); |
1369 | /// |
1370 | /// assert_eq!(b[&3], "c"); |
1371 | /// assert_eq!(b[&17], "d"); |
1372 | /// assert_eq!(b[&41], "e"); |
1373 | /// ``` |
1374 | #[stable(feature = "btree_split_off", since = "1.11.0")] |
1375 | pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self |
1376 | where |
1377 | K: Borrow<Q> + Ord, |
1378 | A: Clone, |
1379 | { |
1380 | if self.is_empty() { |
1381 | return Self::new_in((*self.alloc).clone()); |
1382 | } |
1383 | |
1384 | let total_num = self.len(); |
1385 | let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty |
1386 | |
1387 | let right_root = left_root.split_off(key, (*self.alloc).clone()); |
1388 | |
1389 | let (new_left_len, right_len) = Root::calc_split_length(total_num, &left_root, &right_root); |
1390 | self.length = new_left_len; |
1391 | |
1392 | BTreeMap { |
1393 | root: Some(right_root), |
1394 | length: right_len, |
1395 | alloc: self.alloc.clone(), |
1396 | _marker: PhantomData, |
1397 | } |
1398 | } |
1399 | |
1400 | /// Creates an iterator that visits elements (key-value pairs) in the specified range in |
1401 | /// ascending key order and uses a closure to determine if an element |
1402 | /// should be removed. |
1403 | /// |
1404 | /// If the closure returns `true`, the element is removed from the map and |
1405 | /// yielded. If the closure returns `false`, or panics, the element remains |
1406 | /// in the map and will not be yielded. |
1407 | /// |
1408 | /// The iterator also lets you mutate the value of each element in the |
1409 | /// closure, regardless of whether you choose to keep or remove it. |
1410 | /// |
1411 | /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating |
1412 | /// or the iteration short-circuits, then the remaining elements will be retained. |
1413 | /// Use [`retain`] with a negated predicate if you do not need the returned iterator. |
1414 | /// |
1415 | /// [`retain`]: BTreeMap::retain |
1416 | /// |
1417 | /// # Examples |
1418 | /// |
1419 | /// ``` |
1420 | /// #![feature(btree_extract_if)] |
1421 | /// use std::collections::BTreeMap; |
1422 | /// |
1423 | /// // Splitting a map into even and odd keys, reusing the original map: |
1424 | /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect(); |
1425 | /// let evens: BTreeMap<_, _> = map.extract_if(.., |k, _v| k % 2 == 0).collect(); |
1426 | /// let odds = map; |
1427 | /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]); |
1428 | /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]); |
1429 | /// |
1430 | /// // Splitting a map into low and high halves, reusing the original map: |
1431 | /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect(); |
1432 | /// let low: BTreeMap<_, _> = map.extract_if(0..4, |_k, _v| true).collect(); |
1433 | /// let high = map; |
1434 | /// assert_eq!(low.keys().copied().collect::<Vec<_>>(), [0, 1, 2, 3]); |
1435 | /// assert_eq!(high.keys().copied().collect::<Vec<_>>(), [4, 5, 6, 7]); |
1436 | /// ``` |
1437 | #[unstable(feature = "btree_extract_if", issue = "70530")] |
1438 | pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, K, V, R, F, A> |
1439 | where |
1440 | K: Ord, |
1441 | R: RangeBounds<K>, |
1442 | F: FnMut(&K, &mut V) -> bool, |
1443 | { |
1444 | let (inner, alloc) = self.extract_if_inner(range); |
1445 | ExtractIf { pred, inner, alloc } |
1446 | } |
1447 | |
1448 | pub(super) fn extract_if_inner<R>(&mut self, range: R) -> (ExtractIfInner<'_, K, V, R>, A) |
1449 | where |
1450 | K: Ord, |
1451 | R: RangeBounds<K>, |
1452 | { |
1453 | if let Some(root) = self.root.as_mut() { |
1454 | let (root, dormant_root) = DormantMutRef::new(root); |
1455 | let first = root.borrow_mut().lower_bound(SearchBound::from_range(range.start_bound())); |
1456 | ( |
1457 | ExtractIfInner { |
1458 | length: &mut self.length, |
1459 | dormant_root: Some(dormant_root), |
1460 | cur_leaf_edge: Some(first), |
1461 | range, |
1462 | }, |
1463 | (*self.alloc).clone(), |
1464 | ) |
1465 | } else { |
1466 | ( |
1467 | ExtractIfInner { |
1468 | length: &mut self.length, |
1469 | dormant_root: None, |
1470 | cur_leaf_edge: None, |
1471 | range, |
1472 | }, |
1473 | (*self.alloc).clone(), |
1474 | ) |
1475 | } |
1476 | } |
1477 | |
1478 | /// Creates a consuming iterator visiting all the keys, in sorted order. |
1479 | /// The map cannot be used after calling this. |
1480 | /// The iterator element type is `K`. |
1481 | /// |
1482 | /// # Examples |
1483 | /// |
1484 | /// ``` |
1485 | /// use std::collections::BTreeMap; |
1486 | /// |
1487 | /// let mut a = BTreeMap::new(); |
1488 | /// a.insert(2, "b"); |
1489 | /// a.insert(1, "a"); |
1490 | /// |
1491 | /// let keys: Vec<i32> = a.into_keys().collect(); |
1492 | /// assert_eq!(keys, [1, 2]); |
1493 | /// ``` |
1494 | #[inline] |
1495 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
1496 | pub fn into_keys(self) -> IntoKeys<K, V, A> { |
1497 | IntoKeys { inner: self.into_iter() } |
1498 | } |
1499 | |
1500 | /// Creates a consuming iterator visiting all the values, in order by key. |
1501 | /// The map cannot be used after calling this. |
1502 | /// The iterator element type is `V`. |
1503 | /// |
1504 | /// # Examples |
1505 | /// |
1506 | /// ``` |
1507 | /// use std::collections::BTreeMap; |
1508 | /// |
1509 | /// let mut a = BTreeMap::new(); |
1510 | /// a.insert(1, "hello"); |
1511 | /// a.insert(2, "goodbye"); |
1512 | /// |
1513 | /// let values: Vec<&str> = a.into_values().collect(); |
1514 | /// assert_eq!(values, ["hello", "goodbye"]); |
1515 | /// ``` |
1516 | #[inline] |
1517 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
1518 | pub fn into_values(self) -> IntoValues<K, V, A> { |
1519 | IntoValues { inner: self.into_iter() } |
1520 | } |
1521 | |
1522 | /// Makes a `BTreeMap` from a sorted iterator. |
1523 | pub(crate) fn bulk_build_from_sorted_iter<I>(iter: I, alloc: A) -> Self |
1524 | where |
1525 | K: Ord, |
1526 | I: IntoIterator<Item = (K, V)>, |
1527 | { |
1528 | let mut root = Root::new(alloc.clone()); |
1529 | let mut length = 0; |
1530 | root.bulk_push(DedupSortedIter::new(iter.into_iter()), &mut length, alloc.clone()); |
1531 | BTreeMap { root: Some(root), length, alloc: ManuallyDrop::new(alloc), _marker: PhantomData } |
1532 | } |
1533 | } |
1534 | |
1535 | #[stable(feature = "rust1", since = "1.0.0")] |
1536 | impl<'a, K, V, A: Allocator + Clone> IntoIterator for &'a BTreeMap<K, V, A> { |
1537 | type Item = (&'a K, &'a V); |
1538 | type IntoIter = Iter<'a, K, V>; |
1539 | |
1540 | fn into_iter(self) -> Iter<'a, K, V> { |
1541 | self.iter() |
1542 | } |
1543 | } |
1544 | |
1545 | #[stable(feature = "rust1", since = "1.0.0")] |
1546 | impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> { |
1547 | type Item = (&'a K, &'a V); |
1548 | |
1549 | fn next(&mut self) -> Option<(&'a K, &'a V)> { |
1550 | if self.length == 0 { |
1551 | None |
1552 | } else { |
1553 | self.length -= 1; |
1554 | Some(unsafe { self.range.next_unchecked() }) |
1555 | } |
1556 | } |
1557 | |
1558 | fn size_hint(&self) -> (usize, Option<usize>) { |
1559 | (self.length, Some(self.length)) |
1560 | } |
1561 | |
1562 | fn last(mut self) -> Option<(&'a K, &'a V)> { |
1563 | self.next_back() |
1564 | } |
1565 | |
1566 | fn min(mut self) -> Option<(&'a K, &'a V)> |
1567 | where |
1568 | (&'a K, &'a V): Ord, |
1569 | { |
1570 | self.next() |
1571 | } |
1572 | |
1573 | fn max(mut self) -> Option<(&'a K, &'a V)> |
1574 | where |
1575 | (&'a K, &'a V): Ord, |
1576 | { |
1577 | self.next_back() |
1578 | } |
1579 | } |
1580 | |
1581 | #[stable(feature = "fused", since = "1.26.0")] |
1582 | impl<K, V> FusedIterator for Iter<'_, K, V> {} |
1583 | |
1584 | #[stable(feature = "rust1", since = "1.0.0")] |
1585 | impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> { |
1586 | fn next_back(&mut self) -> Option<(&'a K, &'a V)> { |
1587 | if self.length == 0 { |
1588 | None |
1589 | } else { |
1590 | self.length -= 1; |
1591 | Some(unsafe { self.range.next_back_unchecked() }) |
1592 | } |
1593 | } |
1594 | } |
1595 | |
1596 | #[stable(feature = "rust1", since = "1.0.0")] |
1597 | impl<K, V> ExactSizeIterator for Iter<'_, K, V> { |
1598 | fn len(&self) -> usize { |
1599 | self.length |
1600 | } |
1601 | } |
1602 | |
1603 | #[stable(feature = "rust1", since = "1.0.0")] |
1604 | impl<K, V> Clone for Iter<'_, K, V> { |
1605 | fn clone(&self) -> Self { |
1606 | Iter { range: self.range.clone(), length: self.length } |
1607 | } |
1608 | } |
1609 | |
1610 | #[stable(feature = "rust1", since = "1.0.0")] |
1611 | impl<'a, K, V, A: Allocator + Clone> IntoIterator for &'a mut BTreeMap<K, V, A> { |
1612 | type Item = (&'a K, &'a mut V); |
1613 | type IntoIter = IterMut<'a, K, V>; |
1614 | |
1615 | fn into_iter(self) -> IterMut<'a, K, V> { |
1616 | self.iter_mut() |
1617 | } |
1618 | } |
1619 | |
1620 | #[stable(feature = "rust1", since = "1.0.0")] |
1621 | impl<'a, K, V> Iterator for IterMut<'a, K, V> { |
1622 | type Item = (&'a K, &'a mut V); |
1623 | |
1624 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { |
1625 | if self.length == 0 { |
1626 | None |
1627 | } else { |
1628 | self.length -= 1; |
1629 | Some(unsafe { self.range.next_unchecked() }) |
1630 | } |
1631 | } |
1632 | |
1633 | fn size_hint(&self) -> (usize, Option<usize>) { |
1634 | (self.length, Some(self.length)) |
1635 | } |
1636 | |
1637 | fn last(mut self) -> Option<(&'a K, &'a mut V)> { |
1638 | self.next_back() |
1639 | } |
1640 | |
1641 | fn min(mut self) -> Option<(&'a K, &'a mut V)> |
1642 | where |
1643 | (&'a K, &'a mut V): Ord, |
1644 | { |
1645 | self.next() |
1646 | } |
1647 | |
1648 | fn max(mut self) -> Option<(&'a K, &'a mut V)> |
1649 | where |
1650 | (&'a K, &'a mut V): Ord, |
1651 | { |
1652 | self.next_back() |
1653 | } |
1654 | } |
1655 | |
1656 | #[stable(feature = "rust1", since = "1.0.0")] |
1657 | impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> { |
1658 | fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { |
1659 | if self.length == 0 { |
1660 | None |
1661 | } else { |
1662 | self.length -= 1; |
1663 | Some(unsafe { self.range.next_back_unchecked() }) |
1664 | } |
1665 | } |
1666 | } |
1667 | |
1668 | #[stable(feature = "rust1", since = "1.0.0")] |
1669 | impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { |
1670 | fn len(&self) -> usize { |
1671 | self.length |
1672 | } |
1673 | } |
1674 | |
1675 | #[stable(feature = "fused", since = "1.26.0")] |
1676 | impl<K, V> FusedIterator for IterMut<'_, K, V> {} |
1677 | |
1678 | impl<'a, K, V> IterMut<'a, K, V> { |
1679 | /// Returns an iterator of references over the remaining items. |
1680 | #[inline] |
1681 | pub(super) fn iter(&self) -> Iter<'_, K, V> { |
1682 | Iter { range: self.range.reborrow(), length: self.length } |
1683 | } |
1684 | } |
1685 | |
1686 | #[stable(feature = "rust1", since = "1.0.0")] |
1687 | impl<K, V, A: Allocator + Clone> IntoIterator for BTreeMap<K, V, A> { |
1688 | type Item = (K, V); |
1689 | type IntoIter = IntoIter<K, V, A>; |
1690 | |
1691 | /// Gets an owning iterator over the entries of the map, sorted by key. |
1692 | fn into_iter(self) -> IntoIter<K, V, A> { |
1693 | let mut me: ManuallyDrop |
1694 | if let Some(root: NodeRef |
1695 | let full_range: LazyLeafRange |
1696 | |
1697 | IntoIter { |
1698 | range: full_range, |
1699 | length: me.length, |
1700 | alloc: unsafe { ManuallyDrop::take(&mut me.alloc) }, |
1701 | } |
1702 | } else { |
1703 | IntoIter { |
1704 | range: LazyLeafRange::none(), |
1705 | length: 0, |
1706 | alloc: unsafe { ManuallyDrop::take(&mut me.alloc) }, |
1707 | } |
1708 | } |
1709 | } |
1710 | } |
1711 | |
1712 | #[stable(feature = "btree_drop", since = "1.7.0")] |
1713 | impl<K, V, A: Allocator + Clone> Drop for IntoIter<K, V, A> { |
1714 | fn drop(&mut self) { |
1715 | struct DropGuard<'a, K, V, A: Allocator + Clone>(&'a mut IntoIter<K, V, A>); |
1716 | |
1717 | impl<'a, K, V, A: Allocator + Clone> Drop for DropGuard<'a, K, V, A> { |
1718 | fn drop(&mut self) { |
1719 | // Continue the same loop we perform below. This only runs when unwinding, so we |
1720 | // don't have to care about panics this time (they'll abort). |
1721 | while let Some(kv: Handle |
1722 | // SAFETY: we consume the dying handle immediately. |
1723 | unsafe { kv.drop_key_val() }; |
1724 | } |
1725 | } |
1726 | } |
1727 | |
1728 | while let Some(kv: Handle |
1729 | let guard: DropGuard<'_, K, V, A> = DropGuard(self); |
1730 | // SAFETY: we don't touch the tree before consuming the dying handle. |
1731 | unsafe { kv.drop_key_val() }; |
1732 | mem::forget(guard); |
1733 | } |
1734 | } |
1735 | } |
1736 | |
1737 | impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> { |
1738 | /// Core of a `next` method returning a dying KV handle, |
1739 | /// invalidated by further calls to this function and some others. |
1740 | fn dying_next( |
1741 | &mut self, |
1742 | ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> { |
1743 | if self.length == 0 { |
1744 | self.range.deallocating_end(self.alloc.clone()); |
1745 | None |
1746 | } else { |
1747 | self.length -= 1; |
1748 | Some(unsafe { self.range.deallocating_next_unchecked(self.alloc.clone()) }) |
1749 | } |
1750 | } |
1751 | |
1752 | /// Core of a `next_back` method returning a dying KV handle, |
1753 | /// invalidated by further calls to this function and some others. |
1754 | fn dying_next_back( |
1755 | &mut self, |
1756 | ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> { |
1757 | if self.length == 0 { |
1758 | self.range.deallocating_end(self.alloc.clone()); |
1759 | None |
1760 | } else { |
1761 | self.length -= 1; |
1762 | Some(unsafe { self.range.deallocating_next_back_unchecked(self.alloc.clone()) }) |
1763 | } |
1764 | } |
1765 | } |
1766 | |
1767 | #[stable(feature = "rust1", since = "1.0.0")] |
1768 | impl<K, V, A: Allocator + Clone> Iterator for IntoIter<K, V, A> { |
1769 | type Item = (K, V); |
1770 | |
1771 | fn next(&mut self) -> Option<(K, V)> { |
1772 | // SAFETY: we consume the dying handle immediately. |
1773 | self.dying_next().map(unsafe { |kv: Handle |
1774 | } |
1775 | |
1776 | fn size_hint(&self) -> (usize, Option<usize>) { |
1777 | (self.length, Some(self.length)) |
1778 | } |
1779 | } |
1780 | |
1781 | #[stable(feature = "rust1", since = "1.0.0")] |
1782 | impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoIter<K, V, A> { |
1783 | fn next_back(&mut self) -> Option<(K, V)> { |
1784 | // SAFETY: we consume the dying handle immediately. |
1785 | self.dying_next_back().map(unsafe { |kv: Handle |
1786 | } |
1787 | } |
1788 | |
1789 | #[stable(feature = "rust1", since = "1.0.0")] |
1790 | impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, V, A> { |
1791 | fn len(&self) -> usize { |
1792 | self.length |
1793 | } |
1794 | } |
1795 | |
1796 | #[stable(feature = "fused", since = "1.26.0")] |
1797 | impl<K, V, A: Allocator + Clone> FusedIterator for IntoIter<K, V, A> {} |
1798 | |
1799 | #[stable(feature = "rust1", since = "1.0.0")] |
1800 | impl<'a, K, V> Iterator for Keys<'a, K, V> { |
1801 | type Item = &'a K; |
1802 | |
1803 | fn next(&mut self) -> Option<&'a K> { |
1804 | self.inner.next().map(|(k, _)| k) |
1805 | } |
1806 | |
1807 | fn size_hint(&self) -> (usize, Option<usize>) { |
1808 | self.inner.size_hint() |
1809 | } |
1810 | |
1811 | fn last(mut self) -> Option<&'a K> { |
1812 | self.next_back() |
1813 | } |
1814 | |
1815 | fn min(mut self) -> Option<&'a K> |
1816 | where |
1817 | &'a K: Ord, |
1818 | { |
1819 | self.next() |
1820 | } |
1821 | |
1822 | fn max(mut self) -> Option<&'a K> |
1823 | where |
1824 | &'a K: Ord, |
1825 | { |
1826 | self.next_back() |
1827 | } |
1828 | } |
1829 | |
1830 | #[stable(feature = "rust1", since = "1.0.0")] |
1831 | impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { |
1832 | fn next_back(&mut self) -> Option<&'a K> { |
1833 | self.inner.next_back().map(|(k: &'a K, _)| k) |
1834 | } |
1835 | } |
1836 | |
1837 | #[stable(feature = "rust1", since = "1.0.0")] |
1838 | impl<K, V> ExactSizeIterator for Keys<'_, K, V> { |
1839 | fn len(&self) -> usize { |
1840 | self.inner.len() |
1841 | } |
1842 | } |
1843 | |
1844 | #[stable(feature = "fused", since = "1.26.0")] |
1845 | impl<K, V> FusedIterator for Keys<'_, K, V> {} |
1846 | |
1847 | #[stable(feature = "rust1", since = "1.0.0")] |
1848 | impl<K, V> Clone for Keys<'_, K, V> { |
1849 | fn clone(&self) -> Self { |
1850 | Keys { inner: self.inner.clone() } |
1851 | } |
1852 | } |
1853 | |
1854 | #[stable(feature = "default_iters", since = "1.70.0")] |
1855 | impl<K, V> Default for Keys<'_, K, V> { |
1856 | /// Creates an empty `btree_map::Keys`. |
1857 | /// |
1858 | /// ``` |
1859 | /// # use std::collections::btree_map; |
1860 | /// let iter: btree_map::Keys<'_, u8, u8> = Default::default(); |
1861 | /// assert_eq!(iter.len(), 0); |
1862 | /// ``` |
1863 | fn default() -> Self { |
1864 | Keys { inner: Default::default() } |
1865 | } |
1866 | } |
1867 | |
1868 | #[stable(feature = "rust1", since = "1.0.0")] |
1869 | impl<'a, K, V> Iterator for Values<'a, K, V> { |
1870 | type Item = &'a V; |
1871 | |
1872 | fn next(&mut self) -> Option<&'a V> { |
1873 | self.inner.next().map(|(_, v: &'a V)| v) |
1874 | } |
1875 | |
1876 | fn size_hint(&self) -> (usize, Option<usize>) { |
1877 | self.inner.size_hint() |
1878 | } |
1879 | |
1880 | fn last(mut self) -> Option<&'a V> { |
1881 | self.next_back() |
1882 | } |
1883 | } |
1884 | |
1885 | #[stable(feature = "rust1", since = "1.0.0")] |
1886 | impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { |
1887 | fn next_back(&mut self) -> Option<&'a V> { |
1888 | self.inner.next_back().map(|(_, v: &'a V)| v) |
1889 | } |
1890 | } |
1891 | |
1892 | #[stable(feature = "rust1", since = "1.0.0")] |
1893 | impl<K, V> ExactSizeIterator for Values<'_, K, V> { |
1894 | fn len(&self) -> usize { |
1895 | self.inner.len() |
1896 | } |
1897 | } |
1898 | |
1899 | #[stable(feature = "fused", since = "1.26.0")] |
1900 | impl<K, V> FusedIterator for Values<'_, K, V> {} |
1901 | |
1902 | #[stable(feature = "rust1", since = "1.0.0")] |
1903 | impl<K, V> Clone for Values<'_, K, V> { |
1904 | fn clone(&self) -> Self { |
1905 | Values { inner: self.inner.clone() } |
1906 | } |
1907 | } |
1908 | |
1909 | #[stable(feature = "default_iters", since = "1.70.0")] |
1910 | impl<K, V> Default for Values<'_, K, V> { |
1911 | /// Creates an empty `btree_map::Values`. |
1912 | /// |
1913 | /// ``` |
1914 | /// # use std::collections::btree_map; |
1915 | /// let iter: btree_map::Values<'_, u8, u8> = Default::default(); |
1916 | /// assert_eq!(iter.len(), 0); |
1917 | /// ``` |
1918 | fn default() -> Self { |
1919 | Values { inner: Default::default() } |
1920 | } |
1921 | } |
1922 | |
1923 | /// An iterator produced by calling `extract_if` on BTreeMap. |
1924 | #[unstable(feature = "btree_extract_if", issue = "70530")] |
1925 | #[must_use= "iterators are lazy and do nothing unless consumed"] |
1926 | pub struct ExtractIf< |
1927 | 'a, |
1928 | K, |
1929 | V, |
1930 | R, |
1931 | F, |
1932 | #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global, |
1933 | > { |
1934 | pred: F, |
1935 | inner: ExtractIfInner<'a, K, V, R>, |
1936 | /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`. |
1937 | alloc: A, |
1938 | } |
1939 | |
1940 | /// Most of the implementation of ExtractIf are generic over the type |
1941 | /// of the predicate, thus also serving for BTreeSet::ExtractIf. |
1942 | pub(super) struct ExtractIfInner<'a, K, V, R> { |
1943 | /// Reference to the length field in the borrowed map, updated live. |
1944 | length: &'a mut usize, |
1945 | /// Buried reference to the root field in the borrowed map. |
1946 | /// Wrapped in `Option` to allow drop handler to `take` it. |
1947 | dormant_root: Option<DormantMutRef<'a, Root<K, V>>>, |
1948 | /// Contains a leaf edge preceding the next element to be returned, or the last leaf edge. |
1949 | /// Empty if the map has no root, if iteration went beyond the last leaf edge, |
1950 | /// or if a panic occurred in the predicate. |
1951 | cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>, |
1952 | /// Range over which iteration was requested. We don't need the left side, but we |
1953 | /// can't extract the right side without requiring K: Clone. |
1954 | range: R, |
1955 | } |
1956 | |
1957 | #[unstable(feature = "btree_extract_if", issue = "70530")] |
1958 | impl<K, V, R, F, A> fmt::Debug for ExtractIf<'_, K, V, R, F, A> |
1959 | where |
1960 | K: fmt::Debug, |
1961 | V: fmt::Debug, |
1962 | A: Allocator + Clone, |
1963 | { |
1964 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1965 | f.debug_struct("ExtractIf").field(name: "peek", &self.inner.peek()).finish_non_exhaustive() |
1966 | } |
1967 | } |
1968 | |
1969 | #[unstable(feature = "btree_extract_if", issue = "70530")] |
1970 | impl<K, V, R, F, A: Allocator + Clone> Iterator for ExtractIf<'_, K, V, R, F, A> |
1971 | where |
1972 | K: PartialOrd, |
1973 | R: RangeBounds<K>, |
1974 | F: FnMut(&K, &mut V) -> bool, |
1975 | { |
1976 | type Item = (K, V); |
1977 | |
1978 | fn next(&mut self) -> Option<(K, V)> { |
1979 | self.inner.next(&mut self.pred, self.alloc.clone()) |
1980 | } |
1981 | |
1982 | fn size_hint(&self) -> (usize, Option<usize>) { |
1983 | self.inner.size_hint() |
1984 | } |
1985 | } |
1986 | |
1987 | impl<'a, K, V, R> ExtractIfInner<'a, K, V, R> { |
1988 | /// Allow Debug implementations to predict the next element. |
1989 | pub(super) fn peek(&self) -> Option<(&K, &V)> { |
1990 | let edge = self.cur_leaf_edge.as_ref()?; |
1991 | edge.reborrow().next_kv().ok().map(Handle::into_kv) |
1992 | } |
1993 | |
1994 | /// Implementation of a typical `ExtractIf::next` method, given the predicate. |
1995 | pub(super) fn next<F, A: Allocator + Clone>(&mut self, pred: &mut F, alloc: A) -> Option<(K, V)> |
1996 | where |
1997 | K: PartialOrd, |
1998 | R: RangeBounds<K>, |
1999 | F: FnMut(&K, &mut V) -> bool, |
2000 | { |
2001 | while let Ok(mut kv) = self.cur_leaf_edge.take()?.next_kv() { |
2002 | let (k, v) = kv.kv_mut(); |
2003 | |
2004 | // On creation, we navigated directly to the left bound, so we need only check the |
2005 | // right bound here to decide whether to stop. |
2006 | match self.range.end_bound() { |
2007 | Bound::Included(ref end) if (*k).le(end) => (), |
2008 | Bound::Excluded(ref end) if (*k).lt(end) => (), |
2009 | Bound::Unbounded => (), |
2010 | _ => return None, |
2011 | } |
2012 | |
2013 | if pred(k, v) { |
2014 | *self.length -= 1; |
2015 | let (kv, pos) = kv.remove_kv_tracking( |
2016 | || { |
2017 | // SAFETY: we will touch the root in a way that will not |
2018 | // invalidate the position returned. |
2019 | let root = unsafe { self.dormant_root.take().unwrap().awaken() }; |
2020 | root.pop_internal_level(alloc.clone()); |
2021 | self.dormant_root = Some(DormantMutRef::new(root).1); |
2022 | }, |
2023 | alloc.clone(), |
2024 | ); |
2025 | self.cur_leaf_edge = Some(pos); |
2026 | return Some(kv); |
2027 | } |
2028 | self.cur_leaf_edge = Some(kv.next_leaf_edge()); |
2029 | } |
2030 | None |
2031 | } |
2032 | |
2033 | /// Implementation of a typical `ExtractIf::size_hint` method. |
2034 | pub(super) fn size_hint(&self) -> (usize, Option<usize>) { |
2035 | // In most of the btree iterators, `self.length` is the number of elements |
2036 | // yet to be visited. Here, it includes elements that were visited and that |
2037 | // the predicate decided not to drain. Making this upper bound more tight |
2038 | // during iteration would require an extra field. |
2039 | (0, Some(*self.length)) |
2040 | } |
2041 | } |
2042 | |
2043 | #[unstable(feature = "btree_extract_if", issue = "70530")] |
2044 | impl<K, V, R, F> FusedIterator for ExtractIf<'_, K, V, R, F> |
2045 | where |
2046 | K: PartialOrd, |
2047 | R: RangeBounds<K>, |
2048 | F: FnMut(&K, &mut V) -> bool, |
2049 | { |
2050 | } |
2051 | |
2052 | #[stable(feature = "btree_range", since = "1.17.0")] |
2053 | impl<'a, K, V> Iterator for Range<'a, K, V> { |
2054 | type Item = (&'a K, &'a V); |
2055 | |
2056 | fn next(&mut self) -> Option<(&'a K, &'a V)> { |
2057 | self.inner.next_checked() |
2058 | } |
2059 | |
2060 | fn last(mut self) -> Option<(&'a K, &'a V)> { |
2061 | self.next_back() |
2062 | } |
2063 | |
2064 | fn min(mut self) -> Option<(&'a K, &'a V)> |
2065 | where |
2066 | (&'a K, &'a V): Ord, |
2067 | { |
2068 | self.next() |
2069 | } |
2070 | |
2071 | fn max(mut self) -> Option<(&'a K, &'a V)> |
2072 | where |
2073 | (&'a K, &'a V): Ord, |
2074 | { |
2075 | self.next_back() |
2076 | } |
2077 | } |
2078 | |
2079 | #[stable(feature = "default_iters", since = "1.70.0")] |
2080 | impl<K, V> Default for Range<'_, K, V> { |
2081 | /// Creates an empty `btree_map::Range`. |
2082 | /// |
2083 | /// ``` |
2084 | /// # use std::collections::btree_map; |
2085 | /// let iter: btree_map::Range<'_, u8, u8> = Default::default(); |
2086 | /// assert_eq!(iter.count(), 0); |
2087 | /// ``` |
2088 | fn default() -> Self { |
2089 | Range { inner: Default::default() } |
2090 | } |
2091 | } |
2092 | |
2093 | #[stable(feature = "default_iters_sequel", since = "1.82.0")] |
2094 | impl<K, V> Default for RangeMut<'_, K, V> { |
2095 | /// Creates an empty `btree_map::RangeMut`. |
2096 | /// |
2097 | /// ``` |
2098 | /// # use std::collections::btree_map; |
2099 | /// let iter: btree_map::RangeMut<'_, u8, u8> = Default::default(); |
2100 | /// assert_eq!(iter.count(), 0); |
2101 | /// ``` |
2102 | fn default() -> Self { |
2103 | RangeMut { inner: Default::default(), _marker: PhantomData } |
2104 | } |
2105 | } |
2106 | |
2107 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
2108 | impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { |
2109 | type Item = &'a mut V; |
2110 | |
2111 | fn next(&mut self) -> Option<&'a mut V> { |
2112 | self.inner.next().map(|(_, v: &'a mut V)| v) |
2113 | } |
2114 | |
2115 | fn size_hint(&self) -> (usize, Option<usize>) { |
2116 | self.inner.size_hint() |
2117 | } |
2118 | |
2119 | fn last(mut self) -> Option<&'a mut V> { |
2120 | self.next_back() |
2121 | } |
2122 | } |
2123 | |
2124 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
2125 | impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> { |
2126 | fn next_back(&mut self) -> Option<&'a mut V> { |
2127 | self.inner.next_back().map(|(_, v: &'a mut V)| v) |
2128 | } |
2129 | } |
2130 | |
2131 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
2132 | impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { |
2133 | fn len(&self) -> usize { |
2134 | self.inner.len() |
2135 | } |
2136 | } |
2137 | |
2138 | #[stable(feature = "fused", since = "1.26.0")] |
2139 | impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} |
2140 | |
2141 | #[stable(feature = "default_iters_sequel", since = "1.82.0")] |
2142 | impl<K, V> Default for ValuesMut<'_, K, V> { |
2143 | /// Creates an empty `btree_map::ValuesMut`. |
2144 | /// |
2145 | /// ``` |
2146 | /// # use std::collections::btree_map; |
2147 | /// let iter: btree_map::ValuesMut<'_, u8, u8> = Default::default(); |
2148 | /// assert_eq!(iter.count(), 0); |
2149 | /// ``` |
2150 | fn default() -> Self { |
2151 | ValuesMut { inner: Default::default() } |
2152 | } |
2153 | } |
2154 | |
2155 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2156 | impl<K, V, A: Allocator + Clone> Iterator for IntoKeys<K, V, A> { |
2157 | type Item = K; |
2158 | |
2159 | fn next(&mut self) -> Option<K> { |
2160 | self.inner.next().map(|(k, _)| k) |
2161 | } |
2162 | |
2163 | fn size_hint(&self) -> (usize, Option<usize>) { |
2164 | self.inner.size_hint() |
2165 | } |
2166 | |
2167 | fn last(mut self) -> Option<K> { |
2168 | self.next_back() |
2169 | } |
2170 | |
2171 | fn min(mut self) -> Option<K> |
2172 | where |
2173 | K: Ord, |
2174 | { |
2175 | self.next() |
2176 | } |
2177 | |
2178 | fn max(mut self) -> Option<K> |
2179 | where |
2180 | K: Ord, |
2181 | { |
2182 | self.next_back() |
2183 | } |
2184 | } |
2185 | |
2186 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2187 | impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoKeys<K, V, A> { |
2188 | fn next_back(&mut self) -> Option<K> { |
2189 | self.inner.next_back().map(|(k: K, _)| k) |
2190 | } |
2191 | } |
2192 | |
2193 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2194 | impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoKeys<K, V, A> { |
2195 | fn len(&self) -> usize { |
2196 | self.inner.len() |
2197 | } |
2198 | } |
2199 | |
2200 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2201 | impl<K, V, A: Allocator + Clone> FusedIterator for IntoKeys<K, V, A> {} |
2202 | |
2203 | #[stable(feature = "default_iters", since = "1.70.0")] |
2204 | impl<K, V, A> Default for IntoKeys<K, V, A> |
2205 | where |
2206 | A: Allocator + Default + Clone, |
2207 | { |
2208 | /// Creates an empty `btree_map::IntoKeys`. |
2209 | /// |
2210 | /// ``` |
2211 | /// # use std::collections::btree_map; |
2212 | /// let iter: btree_map::IntoKeys<u8, u8> = Default::default(); |
2213 | /// assert_eq!(iter.len(), 0); |
2214 | /// ``` |
2215 | fn default() -> Self { |
2216 | IntoKeys { inner: Default::default() } |
2217 | } |
2218 | } |
2219 | |
2220 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2221 | impl<K, V, A: Allocator + Clone> Iterator for IntoValues<K, V, A> { |
2222 | type Item = V; |
2223 | |
2224 | fn next(&mut self) -> Option<V> { |
2225 | self.inner.next().map(|(_, v: V)| v) |
2226 | } |
2227 | |
2228 | fn size_hint(&self) -> (usize, Option<usize>) { |
2229 | self.inner.size_hint() |
2230 | } |
2231 | |
2232 | fn last(mut self) -> Option<V> { |
2233 | self.next_back() |
2234 | } |
2235 | } |
2236 | |
2237 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2238 | impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoValues<K, V, A> { |
2239 | fn next_back(&mut self) -> Option<V> { |
2240 | self.inner.next_back().map(|(_, v: V)| v) |
2241 | } |
2242 | } |
2243 | |
2244 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2245 | impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoValues<K, V, A> { |
2246 | fn len(&self) -> usize { |
2247 | self.inner.len() |
2248 | } |
2249 | } |
2250 | |
2251 | #[stable(feature = "map_into_keys_values", since = "1.54.0")] |
2252 | impl<K, V, A: Allocator + Clone> FusedIterator for IntoValues<K, V, A> {} |
2253 | |
2254 | #[stable(feature = "default_iters", since = "1.70.0")] |
2255 | impl<K, V, A> Default for IntoValues<K, V, A> |
2256 | where |
2257 | A: Allocator + Default + Clone, |
2258 | { |
2259 | /// Creates an empty `btree_map::IntoValues`. |
2260 | /// |
2261 | /// ``` |
2262 | /// # use std::collections::btree_map; |
2263 | /// let iter: btree_map::IntoValues<u8, u8> = Default::default(); |
2264 | /// assert_eq!(iter.len(), 0); |
2265 | /// ``` |
2266 | fn default() -> Self { |
2267 | IntoValues { inner: Default::default() } |
2268 | } |
2269 | } |
2270 | |
2271 | #[stable(feature = "btree_range", since = "1.17.0")] |
2272 | impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { |
2273 | fn next_back(&mut self) -> Option<(&'a K, &'a V)> { |
2274 | self.inner.next_back_checked() |
2275 | } |
2276 | } |
2277 | |
2278 | #[stable(feature = "fused", since = "1.26.0")] |
2279 | impl<K, V> FusedIterator for Range<'_, K, V> {} |
2280 | |
2281 | #[stable(feature = "btree_range", since = "1.17.0")] |
2282 | impl<K, V> Clone for Range<'_, K, V> { |
2283 | fn clone(&self) -> Self { |
2284 | Range { inner: self.inner.clone() } |
2285 | } |
2286 | } |
2287 | |
2288 | #[stable(feature = "btree_range", since = "1.17.0")] |
2289 | impl<'a, K, V> Iterator for RangeMut<'a, K, V> { |
2290 | type Item = (&'a K, &'a mut V); |
2291 | |
2292 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { |
2293 | self.inner.next_checked() |
2294 | } |
2295 | |
2296 | fn last(mut self) -> Option<(&'a K, &'a mut V)> { |
2297 | self.next_back() |
2298 | } |
2299 | |
2300 | fn min(mut self) -> Option<(&'a K, &'a mut V)> |
2301 | where |
2302 | (&'a K, &'a mut V): Ord, |
2303 | { |
2304 | self.next() |
2305 | } |
2306 | |
2307 | fn max(mut self) -> Option<(&'a K, &'a mut V)> |
2308 | where |
2309 | (&'a K, &'a mut V): Ord, |
2310 | { |
2311 | self.next_back() |
2312 | } |
2313 | } |
2314 | |
2315 | #[stable(feature = "btree_range", since = "1.17.0")] |
2316 | impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> { |
2317 | fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { |
2318 | self.inner.next_back_checked() |
2319 | } |
2320 | } |
2321 | |
2322 | #[stable(feature = "fused", since = "1.26.0")] |
2323 | impl<K, V> FusedIterator for RangeMut<'_, K, V> {} |
2324 | |
2325 | #[stable(feature = "rust1", since = "1.0.0")] |
2326 | impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { |
2327 | /// Constructs a `BTreeMap<K, V>` from an iterator of key-value pairs. |
2328 | /// |
2329 | /// If the iterator produces any pairs with equal keys, |
2330 | /// all but one of the corresponding values will be dropped. |
2331 | fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> { |
2332 | let mut inputs: Vec<_> = iter.into_iter().collect(); |
2333 | |
2334 | if inputs.is_empty() { |
2335 | return BTreeMap::new(); |
2336 | } |
2337 | |
2338 | // use stable sort to preserve the insertion order. |
2339 | inputs.sort_by(|a: &(K, V), b: &(K, V)| a.0.cmp(&b.0)); |
2340 | BTreeMap::bulk_build_from_sorted_iter(iter:inputs, alloc:Global) |
2341 | } |
2342 | } |
2343 | |
2344 | #[stable(feature = "rust1", since = "1.0.0")] |
2345 | impl<K: Ord, V, A: Allocator + Clone> Extend<(K, V)> for BTreeMap<K, V, A> { |
2346 | #[inline] |
2347 | fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { |
2348 | iter.into_iter().for_each(move |(k: K, v: V)| { |
2349 | self.insert(key:k, value:v); |
2350 | }); |
2351 | } |
2352 | |
2353 | #[inline] |
2354 | fn extend_one(&mut self, (k: K, v: V): (K, V)) { |
2355 | self.insert(key:k, value:v); |
2356 | } |
2357 | } |
2358 | |
2359 | #[stable(feature = "extend_ref", since = "1.2.0")] |
2360 | impl<'a, K: Ord + Copy, V: Copy, A: Allocator + Clone> Extend<(&'a K, &'a V)> |
2361 | for BTreeMap<K, V, A> |
2362 | { |
2363 | fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) { |
2364 | self.extend(iter.into_iter().map(|(&key: K, &value: V)| (key, value))); |
2365 | } |
2366 | |
2367 | #[inline] |
2368 | fn extend_one(&mut self, (&k: K, &v: V): (&'a K, &'a V)) { |
2369 | self.insert(key:k, value:v); |
2370 | } |
2371 | } |
2372 | |
2373 | #[stable(feature = "rust1", since = "1.0.0")] |
2374 | impl<K: Hash, V: Hash, A: Allocator + Clone> Hash for BTreeMap<K, V, A> { |
2375 | fn hash<H: Hasher>(&self, state: &mut H) { |
2376 | state.write_length_prefix(self.len()); |
2377 | for elt: (&K, &V) in self { |
2378 | elt.hash(state); |
2379 | } |
2380 | } |
2381 | } |
2382 | |
2383 | #[stable(feature = "rust1", since = "1.0.0")] |
2384 | impl<K, V> Default for BTreeMap<K, V> { |
2385 | /// Creates an empty `BTreeMap`. |
2386 | fn default() -> BTreeMap<K, V> { |
2387 | BTreeMap::new() |
2388 | } |
2389 | } |
2390 | |
2391 | #[stable(feature = "rust1", since = "1.0.0")] |
2392 | impl<K: PartialEq, V: PartialEq, A: Allocator + Clone> PartialEq for BTreeMap<K, V, A> { |
2393 | fn eq(&self, other: &BTreeMap<K, V, A>) -> bool { |
2394 | self.len() == other.len() && self.iter().zip(other).all(|(a: (&K, &V), b: (&K, &V))| a == b) |
2395 | } |
2396 | } |
2397 | |
2398 | #[stable(feature = "rust1", since = "1.0.0")] |
2399 | impl<K: Eq, V: Eq, A: Allocator + Clone> Eq for BTreeMap<K, V, A> {} |
2400 | |
2401 | #[stable(feature = "rust1", since = "1.0.0")] |
2402 | impl<K: PartialOrd, V: PartialOrd, A: Allocator + Clone> PartialOrd for BTreeMap<K, V, A> { |
2403 | #[inline] |
2404 | fn partial_cmp(&self, other: &BTreeMap<K, V, A>) -> Option<Ordering> { |
2405 | self.iter().partial_cmp(other.iter()) |
2406 | } |
2407 | } |
2408 | |
2409 | #[stable(feature = "rust1", since = "1.0.0")] |
2410 | impl<K: Ord, V: Ord, A: Allocator + Clone> Ord for BTreeMap<K, V, A> { |
2411 | #[inline] |
2412 | fn cmp(&self, other: &BTreeMap<K, V, A>) -> Ordering { |
2413 | self.iter().cmp(other.iter()) |
2414 | } |
2415 | } |
2416 | |
2417 | #[stable(feature = "rust1", since = "1.0.0")] |
2418 | impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for BTreeMap<K, V, A> { |
2419 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2420 | f.debug_map().entries(self.iter()).finish() |
2421 | } |
2422 | } |
2423 | |
2424 | #[stable(feature = "rust1", since = "1.0.0")] |
2425 | impl<K, Q: ?Sized, V, A: Allocator + Clone> Index<&Q> for BTreeMap<K, V, A> |
2426 | where |
2427 | K: Borrow<Q> + Ord, |
2428 | Q: Ord, |
2429 | { |
2430 | type Output = V; |
2431 | |
2432 | /// Returns a reference to the value corresponding to the supplied key. |
2433 | /// |
2434 | /// # Panics |
2435 | /// |
2436 | /// Panics if the key is not present in the `BTreeMap`. |
2437 | #[inline] |
2438 | fn index(&self, key: &Q) -> &V { |
2439 | self.get(key).expect(msg:"no entry found for key") |
2440 | } |
2441 | } |
2442 | |
2443 | #[stable(feature = "std_collections_from_array", since = "1.56.0")] |
2444 | impl<K: Ord, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V> { |
2445 | /// Converts a `[(K, V); N]` into a `BTreeMap<K, V>`. |
2446 | /// |
2447 | /// If any entries in the array have equal keys, |
2448 | /// all but one of the corresponding values will be dropped. |
2449 | /// |
2450 | /// ``` |
2451 | /// use std::collections::BTreeMap; |
2452 | /// |
2453 | /// let map1 = BTreeMap::from([(1, 2), (3, 4)]); |
2454 | /// let map2: BTreeMap<_, _> = [(1, 2), (3, 4)].into(); |
2455 | /// assert_eq!(map1, map2); |
2456 | /// ``` |
2457 | fn from(mut arr: [(K, V); N]) -> Self { |
2458 | if N == 0 { |
2459 | return BTreeMap::new(); |
2460 | } |
2461 | |
2462 | // use stable sort to preserve the insertion order. |
2463 | arr.sort_by(|a: &(K, V), b: &(K, V)| a.0.cmp(&b.0)); |
2464 | BTreeMap::bulk_build_from_sorted_iter(iter:arr, alloc:Global) |
2465 | } |
2466 | } |
2467 | |
2468 | impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { |
2469 | /// Gets an iterator over the entries of the map, sorted by key. |
2470 | /// |
2471 | /// # Examples |
2472 | /// |
2473 | /// ``` |
2474 | /// use std::collections::BTreeMap; |
2475 | /// |
2476 | /// let mut map = BTreeMap::new(); |
2477 | /// map.insert(3, "c"); |
2478 | /// map.insert(2, "b"); |
2479 | /// map.insert(1, "a"); |
2480 | /// |
2481 | /// for (key, value) in map.iter() { |
2482 | /// println!("{key}: {value}"); |
2483 | /// } |
2484 | /// |
2485 | /// let (first_key, first_value) = map.iter().next().unwrap(); |
2486 | /// assert_eq!((*first_key, *first_value), (1, "a")); |
2487 | /// ``` |
2488 | #[stable(feature = "rust1", since = "1.0.0")] |
2489 | pub fn iter(&self) -> Iter<'_, K, V> { |
2490 | if let Some(root) = &self.root { |
2491 | let full_range = root.reborrow().full_range(); |
2492 | |
2493 | Iter { range: full_range, length: self.length } |
2494 | } else { |
2495 | Iter { range: LazyLeafRange::none(), length: 0 } |
2496 | } |
2497 | } |
2498 | |
2499 | /// Gets a mutable iterator over the entries of the map, sorted by key. |
2500 | /// |
2501 | /// # Examples |
2502 | /// |
2503 | /// ``` |
2504 | /// use std::collections::BTreeMap; |
2505 | /// |
2506 | /// let mut map = BTreeMap::from([ |
2507 | /// ("a", 1), |
2508 | /// ("b", 2), |
2509 | /// ("c", 3), |
2510 | /// ]); |
2511 | /// |
2512 | /// // add 10 to the value if the key isn't "a" |
2513 | /// for (key, value) in map.iter_mut() { |
2514 | /// if key != &"a"{ |
2515 | /// *value += 10; |
2516 | /// } |
2517 | /// } |
2518 | /// ``` |
2519 | #[stable(feature = "rust1", since = "1.0.0")] |
2520 | pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { |
2521 | if let Some(root) = &mut self.root { |
2522 | let full_range = root.borrow_valmut().full_range(); |
2523 | |
2524 | IterMut { range: full_range, length: self.length, _marker: PhantomData } |
2525 | } else { |
2526 | IterMut { range: LazyLeafRange::none(), length: 0, _marker: PhantomData } |
2527 | } |
2528 | } |
2529 | |
2530 | /// Gets an iterator over the keys of the map, in sorted order. |
2531 | /// |
2532 | /// # Examples |
2533 | /// |
2534 | /// ``` |
2535 | /// use std::collections::BTreeMap; |
2536 | /// |
2537 | /// let mut a = BTreeMap::new(); |
2538 | /// a.insert(2, "b"); |
2539 | /// a.insert(1, "a"); |
2540 | /// |
2541 | /// let keys: Vec<_> = a.keys().cloned().collect(); |
2542 | /// assert_eq!(keys, [1, 2]); |
2543 | /// ``` |
2544 | #[stable(feature = "rust1", since = "1.0.0")] |
2545 | pub fn keys(&self) -> Keys<'_, K, V> { |
2546 | Keys { inner: self.iter() } |
2547 | } |
2548 | |
2549 | /// Gets an iterator over the values of the map, in order by key. |
2550 | /// |
2551 | /// # Examples |
2552 | /// |
2553 | /// ``` |
2554 | /// use std::collections::BTreeMap; |
2555 | /// |
2556 | /// let mut a = BTreeMap::new(); |
2557 | /// a.insert(1, "hello"); |
2558 | /// a.insert(2, "goodbye"); |
2559 | /// |
2560 | /// let values: Vec<&str> = a.values().cloned().collect(); |
2561 | /// assert_eq!(values, ["hello", "goodbye"]); |
2562 | /// ``` |
2563 | #[stable(feature = "rust1", since = "1.0.0")] |
2564 | pub fn values(&self) -> Values<'_, K, V> { |
2565 | Values { inner: self.iter() } |
2566 | } |
2567 | |
2568 | /// Gets a mutable iterator over the values of the map, in order by key. |
2569 | /// |
2570 | /// # Examples |
2571 | /// |
2572 | /// ``` |
2573 | /// use std::collections::BTreeMap; |
2574 | /// |
2575 | /// let mut a = BTreeMap::new(); |
2576 | /// a.insert(1, String::from("hello")); |
2577 | /// a.insert(2, String::from("goodbye")); |
2578 | /// |
2579 | /// for value in a.values_mut() { |
2580 | /// value.push_str("!"); |
2581 | /// } |
2582 | /// |
2583 | /// let values: Vec<String> = a.values().cloned().collect(); |
2584 | /// assert_eq!(values, [String::from("hello!"), |
2585 | /// String::from("goodbye!")]); |
2586 | /// ``` |
2587 | #[stable(feature = "map_values_mut", since = "1.10.0")] |
2588 | pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { |
2589 | ValuesMut { inner: self.iter_mut() } |
2590 | } |
2591 | |
2592 | /// Returns the number of elements in the map. |
2593 | /// |
2594 | /// # Examples |
2595 | /// |
2596 | /// ``` |
2597 | /// use std::collections::BTreeMap; |
2598 | /// |
2599 | /// let mut a = BTreeMap::new(); |
2600 | /// assert_eq!(a.len(), 0); |
2601 | /// a.insert(1, "a"); |
2602 | /// assert_eq!(a.len(), 1); |
2603 | /// ``` |
2604 | #[must_use] |
2605 | #[stable(feature = "rust1", since = "1.0.0")] |
2606 | #[rustc_const_unstable( |
2607 | feature = "const_btree_len", |
2608 | issue = "71835", |
2609 | implied_by = "const_btree_new" |
2610 | )] |
2611 | #[rustc_confusables( "length", "size")] |
2612 | pub const fn len(&self) -> usize { |
2613 | self.length |
2614 | } |
2615 | |
2616 | /// Returns `true` if the map contains no elements. |
2617 | /// |
2618 | /// # Examples |
2619 | /// |
2620 | /// ``` |
2621 | /// use std::collections::BTreeMap; |
2622 | /// |
2623 | /// let mut a = BTreeMap::new(); |
2624 | /// assert!(a.is_empty()); |
2625 | /// a.insert(1, "a"); |
2626 | /// assert!(!a.is_empty()); |
2627 | /// ``` |
2628 | #[must_use] |
2629 | #[stable(feature = "rust1", since = "1.0.0")] |
2630 | #[rustc_const_unstable( |
2631 | feature = "const_btree_len", |
2632 | issue = "71835", |
2633 | implied_by = "const_btree_new" |
2634 | )] |
2635 | pub const fn is_empty(&self) -> bool { |
2636 | self.len() == 0 |
2637 | } |
2638 | |
2639 | /// Returns a [`Cursor`] pointing at the gap before the smallest key |
2640 | /// greater than the given bound. |
2641 | /// |
2642 | /// Passing `Bound::Included(x)` will return a cursor pointing to the |
2643 | /// gap before the smallest key greater than or equal to `x`. |
2644 | /// |
2645 | /// Passing `Bound::Excluded(x)` will return a cursor pointing to the |
2646 | /// gap before the smallest key greater than `x`. |
2647 | /// |
2648 | /// Passing `Bound::Unbounded` will return a cursor pointing to the |
2649 | /// gap before the smallest key in the map. |
2650 | /// |
2651 | /// # Examples |
2652 | /// |
2653 | /// ``` |
2654 | /// #![feature(btree_cursors)] |
2655 | /// |
2656 | /// use std::collections::BTreeMap; |
2657 | /// use std::ops::Bound; |
2658 | /// |
2659 | /// let map = BTreeMap::from([ |
2660 | /// (1, "a"), |
2661 | /// (2, "b"), |
2662 | /// (3, "c"), |
2663 | /// (4, "d"), |
2664 | /// ]); |
2665 | /// |
2666 | /// let cursor = map.lower_bound(Bound::Included(&2)); |
2667 | /// assert_eq!(cursor.peek_prev(), Some((&1, &"a"))); |
2668 | /// assert_eq!(cursor.peek_next(), Some((&2, &"b"))); |
2669 | /// |
2670 | /// let cursor = map.lower_bound(Bound::Excluded(&2)); |
2671 | /// assert_eq!(cursor.peek_prev(), Some((&2, &"b"))); |
2672 | /// assert_eq!(cursor.peek_next(), Some((&3, &"c"))); |
2673 | /// |
2674 | /// let cursor = map.lower_bound(Bound::Unbounded); |
2675 | /// assert_eq!(cursor.peek_prev(), None); |
2676 | /// assert_eq!(cursor.peek_next(), Some((&1, &"a"))); |
2677 | /// ``` |
2678 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2679 | pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> |
2680 | where |
2681 | K: Borrow<Q> + Ord, |
2682 | Q: Ord, |
2683 | { |
2684 | let root_node = match self.root.as_ref() { |
2685 | None => return Cursor { current: None, root: None }, |
2686 | Some(root) => root.reborrow(), |
2687 | }; |
2688 | let edge = root_node.lower_bound(SearchBound::from_range(bound)); |
2689 | Cursor { current: Some(edge), root: self.root.as_ref() } |
2690 | } |
2691 | |
2692 | /// Returns a [`CursorMut`] pointing at the gap before the smallest key |
2693 | /// greater than the given bound. |
2694 | /// |
2695 | /// Passing `Bound::Included(x)` will return a cursor pointing to the |
2696 | /// gap before the smallest key greater than or equal to `x`. |
2697 | /// |
2698 | /// Passing `Bound::Excluded(x)` will return a cursor pointing to the |
2699 | /// gap before the smallest key greater than `x`. |
2700 | /// |
2701 | /// Passing `Bound::Unbounded` will return a cursor pointing to the |
2702 | /// gap before the smallest key in the map. |
2703 | /// |
2704 | /// # Examples |
2705 | /// |
2706 | /// ``` |
2707 | /// #![feature(btree_cursors)] |
2708 | /// |
2709 | /// use std::collections::BTreeMap; |
2710 | /// use std::ops::Bound; |
2711 | /// |
2712 | /// let mut map = BTreeMap::from([ |
2713 | /// (1, "a"), |
2714 | /// (2, "b"), |
2715 | /// (3, "c"), |
2716 | /// (4, "d"), |
2717 | /// ]); |
2718 | /// |
2719 | /// let mut cursor = map.lower_bound_mut(Bound::Included(&2)); |
2720 | /// assert_eq!(cursor.peek_prev(), Some((&1, &mut "a"))); |
2721 | /// assert_eq!(cursor.peek_next(), Some((&2, &mut "b"))); |
2722 | /// |
2723 | /// let mut cursor = map.lower_bound_mut(Bound::Excluded(&2)); |
2724 | /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b"))); |
2725 | /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c"))); |
2726 | /// |
2727 | /// let mut cursor = map.lower_bound_mut(Bound::Unbounded); |
2728 | /// assert_eq!(cursor.peek_prev(), None); |
2729 | /// assert_eq!(cursor.peek_next(), Some((&1, &mut "a"))); |
2730 | /// ``` |
2731 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2732 | pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> |
2733 | where |
2734 | K: Borrow<Q> + Ord, |
2735 | Q: Ord, |
2736 | { |
2737 | let (root, dormant_root) = DormantMutRef::new(&mut self.root); |
2738 | let root_node = match root.as_mut() { |
2739 | None => { |
2740 | return CursorMut { |
2741 | inner: CursorMutKey { |
2742 | current: None, |
2743 | root: dormant_root, |
2744 | length: &mut self.length, |
2745 | alloc: &mut *self.alloc, |
2746 | }, |
2747 | }; |
2748 | } |
2749 | Some(root) => root.borrow_mut(), |
2750 | }; |
2751 | let edge = root_node.lower_bound(SearchBound::from_range(bound)); |
2752 | CursorMut { |
2753 | inner: CursorMutKey { |
2754 | current: Some(edge), |
2755 | root: dormant_root, |
2756 | length: &mut self.length, |
2757 | alloc: &mut *self.alloc, |
2758 | }, |
2759 | } |
2760 | } |
2761 | |
2762 | /// Returns a [`Cursor`] pointing at the gap after the greatest key |
2763 | /// smaller than the given bound. |
2764 | /// |
2765 | /// Passing `Bound::Included(x)` will return a cursor pointing to the |
2766 | /// gap after the greatest key smaller than or equal to `x`. |
2767 | /// |
2768 | /// Passing `Bound::Excluded(x)` will return a cursor pointing to the |
2769 | /// gap after the greatest key smaller than `x`. |
2770 | /// |
2771 | /// Passing `Bound::Unbounded` will return a cursor pointing to the |
2772 | /// gap after the greatest key in the map. |
2773 | /// |
2774 | /// # Examples |
2775 | /// |
2776 | /// ``` |
2777 | /// #![feature(btree_cursors)] |
2778 | /// |
2779 | /// use std::collections::BTreeMap; |
2780 | /// use std::ops::Bound; |
2781 | /// |
2782 | /// let map = BTreeMap::from([ |
2783 | /// (1, "a"), |
2784 | /// (2, "b"), |
2785 | /// (3, "c"), |
2786 | /// (4, "d"), |
2787 | /// ]); |
2788 | /// |
2789 | /// let cursor = map.upper_bound(Bound::Included(&3)); |
2790 | /// assert_eq!(cursor.peek_prev(), Some((&3, &"c"))); |
2791 | /// assert_eq!(cursor.peek_next(), Some((&4, &"d"))); |
2792 | /// |
2793 | /// let cursor = map.upper_bound(Bound::Excluded(&3)); |
2794 | /// assert_eq!(cursor.peek_prev(), Some((&2, &"b"))); |
2795 | /// assert_eq!(cursor.peek_next(), Some((&3, &"c"))); |
2796 | /// |
2797 | /// let cursor = map.upper_bound(Bound::Unbounded); |
2798 | /// assert_eq!(cursor.peek_prev(), Some((&4, &"d"))); |
2799 | /// assert_eq!(cursor.peek_next(), None); |
2800 | /// ``` |
2801 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2802 | pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> |
2803 | where |
2804 | K: Borrow<Q> + Ord, |
2805 | Q: Ord, |
2806 | { |
2807 | let root_node = match self.root.as_ref() { |
2808 | None => return Cursor { current: None, root: None }, |
2809 | Some(root) => root.reborrow(), |
2810 | }; |
2811 | let edge = root_node.upper_bound(SearchBound::from_range(bound)); |
2812 | Cursor { current: Some(edge), root: self.root.as_ref() } |
2813 | } |
2814 | |
2815 | /// Returns a [`CursorMut`] pointing at the gap after the greatest key |
2816 | /// smaller than the given bound. |
2817 | /// |
2818 | /// Passing `Bound::Included(x)` will return a cursor pointing to the |
2819 | /// gap after the greatest key smaller than or equal to `x`. |
2820 | /// |
2821 | /// Passing `Bound::Excluded(x)` will return a cursor pointing to the |
2822 | /// gap after the greatest key smaller than `x`. |
2823 | /// |
2824 | /// Passing `Bound::Unbounded` will return a cursor pointing to the |
2825 | /// gap after the greatest key in the map. |
2826 | /// |
2827 | /// # Examples |
2828 | /// |
2829 | /// ``` |
2830 | /// #![feature(btree_cursors)] |
2831 | /// |
2832 | /// use std::collections::BTreeMap; |
2833 | /// use std::ops::Bound; |
2834 | /// |
2835 | /// let mut map = BTreeMap::from([ |
2836 | /// (1, "a"), |
2837 | /// (2, "b"), |
2838 | /// (3, "c"), |
2839 | /// (4, "d"), |
2840 | /// ]); |
2841 | /// |
2842 | /// let mut cursor = map.upper_bound_mut(Bound::Included(&3)); |
2843 | /// assert_eq!(cursor.peek_prev(), Some((&3, &mut "c"))); |
2844 | /// assert_eq!(cursor.peek_next(), Some((&4, &mut "d"))); |
2845 | /// |
2846 | /// let mut cursor = map.upper_bound_mut(Bound::Excluded(&3)); |
2847 | /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b"))); |
2848 | /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c"))); |
2849 | /// |
2850 | /// let mut cursor = map.upper_bound_mut(Bound::Unbounded); |
2851 | /// assert_eq!(cursor.peek_prev(), Some((&4, &mut "d"))); |
2852 | /// assert_eq!(cursor.peek_next(), None); |
2853 | /// ``` |
2854 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2855 | pub fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> |
2856 | where |
2857 | K: Borrow<Q> + Ord, |
2858 | Q: Ord, |
2859 | { |
2860 | let (root, dormant_root) = DormantMutRef::new(&mut self.root); |
2861 | let root_node = match root.as_mut() { |
2862 | None => { |
2863 | return CursorMut { |
2864 | inner: CursorMutKey { |
2865 | current: None, |
2866 | root: dormant_root, |
2867 | length: &mut self.length, |
2868 | alloc: &mut *self.alloc, |
2869 | }, |
2870 | }; |
2871 | } |
2872 | Some(root) => root.borrow_mut(), |
2873 | }; |
2874 | let edge = root_node.upper_bound(SearchBound::from_range(bound)); |
2875 | CursorMut { |
2876 | inner: CursorMutKey { |
2877 | current: Some(edge), |
2878 | root: dormant_root, |
2879 | length: &mut self.length, |
2880 | alloc: &mut *self.alloc, |
2881 | }, |
2882 | } |
2883 | } |
2884 | } |
2885 | |
2886 | /// A cursor over a `BTreeMap`. |
2887 | /// |
2888 | /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. |
2889 | /// |
2890 | /// Cursors always point to a gap between two elements in the map, and can |
2891 | /// operate on the two immediately adjacent elements. |
2892 | /// |
2893 | /// A `Cursor` is created with the [`BTreeMap::lower_bound`] and [`BTreeMap::upper_bound`] methods. |
2894 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2895 | pub struct Cursor<'a, K: 'a, V: 'a> { |
2896 | // If current is None then it means the tree has not been allocated yet. |
2897 | current: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>>, |
2898 | root: Option<&'a node::Root<K, V>>, |
2899 | } |
2900 | |
2901 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2902 | impl<K, V> Clone for Cursor<'_, K, V> { |
2903 | fn clone(&self) -> Self { |
2904 | let Cursor { current: Option |
2905 | Cursor { current, root } |
2906 | } |
2907 | } |
2908 | |
2909 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2910 | impl<K: Debug, V: Debug> Debug for Cursor<'_, K, V> { |
2911 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2912 | f.write_str(data:"Cursor") |
2913 | } |
2914 | } |
2915 | |
2916 | /// A cursor over a `BTreeMap` with editing operations. |
2917 | /// |
2918 | /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can |
2919 | /// safely mutate the map during iteration. This is because the lifetime of its yielded |
2920 | /// references is tied to its own lifetime, instead of just the underlying map. This means |
2921 | /// cursors cannot yield multiple elements at once. |
2922 | /// |
2923 | /// Cursors always point to a gap between two elements in the map, and can |
2924 | /// operate on the two immediately adjacent elements. |
2925 | /// |
2926 | /// A `CursorMut` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`] |
2927 | /// methods. |
2928 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2929 | pub struct CursorMut< |
2930 | 'a, |
2931 | K: 'a, |
2932 | V: 'a, |
2933 | #[unstable(feature = "allocator_api", issue = "32838")] A = Global, |
2934 | > { |
2935 | inner: CursorMutKey<'a, K, V, A>, |
2936 | } |
2937 | |
2938 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2939 | impl<K: Debug, V: Debug, A> Debug for CursorMut<'_, K, V, A> { |
2940 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2941 | f.write_str(data:"CursorMut") |
2942 | } |
2943 | } |
2944 | |
2945 | /// A cursor over a `BTreeMap` with editing operations, and which allows |
2946 | /// mutating the key of elements. |
2947 | /// |
2948 | /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can |
2949 | /// safely mutate the map during iteration. This is because the lifetime of its yielded |
2950 | /// references is tied to its own lifetime, instead of just the underlying map. This means |
2951 | /// cursors cannot yield multiple elements at once. |
2952 | /// |
2953 | /// Cursors always point to a gap between two elements in the map, and can |
2954 | /// operate on the two immediately adjacent elements. |
2955 | /// |
2956 | /// A `CursorMutKey` is created from a [`CursorMut`] with the |
2957 | /// [`CursorMut::with_mutable_key`] method. |
2958 | /// |
2959 | /// # Safety |
2960 | /// |
2961 | /// Since this cursor allows mutating keys, you must ensure that the `BTreeMap` |
2962 | /// invariants are maintained. Specifically: |
2963 | /// |
2964 | /// * The key of the newly inserted element must be unique in the tree. |
2965 | /// * All keys in the tree must remain in sorted order. |
2966 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2967 | pub struct CursorMutKey< |
2968 | 'a, |
2969 | K: 'a, |
2970 | V: 'a, |
2971 | #[unstable(feature = "allocator_api", issue = "32838")] A = Global, |
2972 | > { |
2973 | // If current is None then it means the tree has not been allocated yet. |
2974 | current: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>, |
2975 | root: DormantMutRef<'a, Option<node::Root<K, V>>>, |
2976 | length: &'a mut usize, |
2977 | alloc: &'a mut A, |
2978 | } |
2979 | |
2980 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2981 | impl<K: Debug, V: Debug, A> Debug for CursorMutKey<'_, K, V, A> { |
2982 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2983 | f.write_str(data:"CursorMutKey") |
2984 | } |
2985 | } |
2986 | |
2987 | impl<'a, K, V> Cursor<'a, K, V> { |
2988 | /// Advances the cursor to the next gap, returning the key and value of the |
2989 | /// element that it moved over. |
2990 | /// |
2991 | /// If the cursor is already at the end of the map then `None` is returned |
2992 | /// and the cursor is not moved. |
2993 | #[unstable(feature = "btree_cursors", issue = "107540")] |
2994 | pub fn next(&mut self) -> Option<(&'a K, &'a V)> { |
2995 | let current = self.current.take()?; |
2996 | match current.next_kv() { |
2997 | Ok(kv) => { |
2998 | let result = kv.into_kv(); |
2999 | self.current = Some(kv.next_leaf_edge()); |
3000 | Some(result) |
3001 | } |
3002 | Err(root) => { |
3003 | self.current = Some(root.last_leaf_edge()); |
3004 | None |
3005 | } |
3006 | } |
3007 | } |
3008 | |
3009 | /// Advances the cursor to the previous gap, returning the key and value of |
3010 | /// the element that it moved over. |
3011 | /// |
3012 | /// If the cursor is already at the start of the map then `None` is returned |
3013 | /// and the cursor is not moved. |
3014 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3015 | pub fn prev(&mut self) -> Option<(&'a K, &'a V)> { |
3016 | let current = self.current.take()?; |
3017 | match current.next_back_kv() { |
3018 | Ok(kv) => { |
3019 | let result = kv.into_kv(); |
3020 | self.current = Some(kv.next_back_leaf_edge()); |
3021 | Some(result) |
3022 | } |
3023 | Err(root) => { |
3024 | self.current = Some(root.first_leaf_edge()); |
3025 | None |
3026 | } |
3027 | } |
3028 | } |
3029 | |
3030 | /// Returns a reference to the key and value of the next element without |
3031 | /// moving the cursor. |
3032 | /// |
3033 | /// If the cursor is at the end of the map then `None` is returned. |
3034 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3035 | pub fn peek_next(&self) -> Option<(&'a K, &'a V)> { |
3036 | self.clone().next() |
3037 | } |
3038 | |
3039 | /// Returns a reference to the key and value of the previous element |
3040 | /// without moving the cursor. |
3041 | /// |
3042 | /// If the cursor is at the start of the map then `None` is returned. |
3043 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3044 | pub fn peek_prev(&self) -> Option<(&'a K, &'a V)> { |
3045 | self.clone().prev() |
3046 | } |
3047 | } |
3048 | |
3049 | impl<'a, K, V, A> CursorMut<'a, K, V, A> { |
3050 | /// Advances the cursor to the next gap, returning the key and value of the |
3051 | /// element that it moved over. |
3052 | /// |
3053 | /// If the cursor is already at the end of the map then `None` is returned |
3054 | /// and the cursor is not moved. |
3055 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3056 | pub fn next(&mut self) -> Option<(&K, &mut V)> { |
3057 | let (k, v) = self.inner.next()?; |
3058 | Some((&*k, v)) |
3059 | } |
3060 | |
3061 | /// Advances the cursor to the previous gap, returning the key and value of |
3062 | /// the element that it moved over. |
3063 | /// |
3064 | /// If the cursor is already at the start of the map then `None` is returned |
3065 | /// and the cursor is not moved. |
3066 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3067 | pub fn prev(&mut self) -> Option<(&K, &mut V)> { |
3068 | let (k, v) = self.inner.prev()?; |
3069 | Some((&*k, v)) |
3070 | } |
3071 | |
3072 | /// Returns a reference to the key and value of the next element without |
3073 | /// moving the cursor. |
3074 | /// |
3075 | /// If the cursor is at the end of the map then `None` is returned. |
3076 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3077 | pub fn peek_next(&mut self) -> Option<(&K, &mut V)> { |
3078 | let (k, v) = self.inner.peek_next()?; |
3079 | Some((&*k, v)) |
3080 | } |
3081 | |
3082 | /// Returns a reference to the key and value of the previous element |
3083 | /// without moving the cursor. |
3084 | /// |
3085 | /// If the cursor is at the start of the map then `None` is returned. |
3086 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3087 | pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> { |
3088 | let (k, v) = self.inner.peek_prev()?; |
3089 | Some((&*k, v)) |
3090 | } |
3091 | |
3092 | /// Returns a read-only cursor pointing to the same location as the |
3093 | /// `CursorMut`. |
3094 | /// |
3095 | /// The lifetime of the returned `Cursor` is bound to that of the |
3096 | /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the |
3097 | /// `CursorMut` is frozen for the lifetime of the `Cursor`. |
3098 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3099 | pub fn as_cursor(&self) -> Cursor<'_, K, V> { |
3100 | self.inner.as_cursor() |
3101 | } |
3102 | |
3103 | /// Converts the cursor into a [`CursorMutKey`], which allows mutating |
3104 | /// the key of elements in the tree. |
3105 | /// |
3106 | /// # Safety |
3107 | /// |
3108 | /// Since this cursor allows mutating keys, you must ensure that the `BTreeMap` |
3109 | /// invariants are maintained. Specifically: |
3110 | /// |
3111 | /// * The key of the newly inserted element must be unique in the tree. |
3112 | /// * All keys in the tree must remain in sorted order. |
3113 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3114 | pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A> { |
3115 | self.inner |
3116 | } |
3117 | } |
3118 | |
3119 | impl<'a, K, V, A> CursorMutKey<'a, K, V, A> { |
3120 | /// Advances the cursor to the next gap, returning the key and value of the |
3121 | /// element that it moved over. |
3122 | /// |
3123 | /// If the cursor is already at the end of the map then `None` is returned |
3124 | /// and the cursor is not moved. |
3125 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3126 | pub fn next(&mut self) -> Option<(&mut K, &mut V)> { |
3127 | let current = self.current.take()?; |
3128 | match current.next_kv() { |
3129 | Ok(mut kv) => { |
3130 | // SAFETY: The key/value pointers remain valid even after the |
3131 | // cursor is moved forward. The lifetimes then prevent any |
3132 | // further access to the cursor. |
3133 | let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() }; |
3134 | let (k, v) = (k as *mut _, v as *mut _); |
3135 | self.current = Some(kv.next_leaf_edge()); |
3136 | Some(unsafe { (&mut *k, &mut *v) }) |
3137 | } |
3138 | Err(root) => { |
3139 | self.current = Some(root.last_leaf_edge()); |
3140 | None |
3141 | } |
3142 | } |
3143 | } |
3144 | |
3145 | /// Advances the cursor to the previous gap, returning the key and value of |
3146 | /// the element that it moved over. |
3147 | /// |
3148 | /// If the cursor is already at the start of the map then `None` is returned |
3149 | /// and the cursor is not moved. |
3150 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3151 | pub fn prev(&mut self) -> Option<(&mut K, &mut V)> { |
3152 | let current = self.current.take()?; |
3153 | match current.next_back_kv() { |
3154 | Ok(mut kv) => { |
3155 | // SAFETY: The key/value pointers remain valid even after the |
3156 | // cursor is moved forward. The lifetimes then prevent any |
3157 | // further access to the cursor. |
3158 | let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() }; |
3159 | let (k, v) = (k as *mut _, v as *mut _); |
3160 | self.current = Some(kv.next_back_leaf_edge()); |
3161 | Some(unsafe { (&mut *k, &mut *v) }) |
3162 | } |
3163 | Err(root) => { |
3164 | self.current = Some(root.first_leaf_edge()); |
3165 | None |
3166 | } |
3167 | } |
3168 | } |
3169 | |
3170 | /// Returns a reference to the key and value of the next element without |
3171 | /// moving the cursor. |
3172 | /// |
3173 | /// If the cursor is at the end of the map then `None` is returned. |
3174 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3175 | pub fn peek_next(&mut self) -> Option<(&mut K, &mut V)> { |
3176 | let current = self.current.as_mut()?; |
3177 | // SAFETY: We're not using this to mutate the tree. |
3178 | let kv = unsafe { current.reborrow_mut() }.next_kv().ok()?.into_kv_mut(); |
3179 | Some(kv) |
3180 | } |
3181 | |
3182 | /// Returns a reference to the key and value of the previous element |
3183 | /// without moving the cursor. |
3184 | /// |
3185 | /// If the cursor is at the start of the map then `None` is returned. |
3186 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3187 | pub fn peek_prev(&mut self) -> Option<(&mut K, &mut V)> { |
3188 | let current = self.current.as_mut()?; |
3189 | // SAFETY: We're not using this to mutate the tree. |
3190 | let kv = unsafe { current.reborrow_mut() }.next_back_kv().ok()?.into_kv_mut(); |
3191 | Some(kv) |
3192 | } |
3193 | |
3194 | /// Returns a read-only cursor pointing to the same location as the |
3195 | /// `CursorMutKey`. |
3196 | /// |
3197 | /// The lifetime of the returned `Cursor` is bound to that of the |
3198 | /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the |
3199 | /// `CursorMutKey` is frozen for the lifetime of the `Cursor`. |
3200 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3201 | pub fn as_cursor(&self) -> Cursor<'_, K, V> { |
3202 | Cursor { |
3203 | // SAFETY: The tree is immutable while the cursor exists. |
3204 | root: unsafe { self.root.reborrow_shared().as_ref() }, |
3205 | current: self.current.as_ref().map(|current| current.reborrow()), |
3206 | } |
3207 | } |
3208 | } |
3209 | |
3210 | // Now the tree editing operations |
3211 | impl<'a, K: Ord, V, A: Allocator + Clone> CursorMutKey<'a, K, V, A> { |
3212 | /// Inserts a new key-value pair into the map in the gap that the |
3213 | /// cursor is currently pointing to. |
3214 | /// |
3215 | /// After the insertion the cursor will be pointing at the gap before the |
3216 | /// newly inserted element. |
3217 | /// |
3218 | /// # Safety |
3219 | /// |
3220 | /// You must ensure that the `BTreeMap` invariants are maintained. |
3221 | /// Specifically: |
3222 | /// |
3223 | /// * The key of the newly inserted element must be unique in the tree. |
3224 | /// * All keys in the tree must remain in sorted order. |
3225 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3226 | pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) { |
3227 | let edge = match self.current.take() { |
3228 | None => { |
3229 | // Tree is empty, allocate a new root. |
3230 | // SAFETY: We have no other reference to the tree. |
3231 | let root = unsafe { self.root.reborrow() }; |
3232 | debug_assert!(root.is_none()); |
3233 | let mut node = NodeRef::new_leaf(self.alloc.clone()); |
3234 | // SAFETY: We don't touch the root while the handle is alive. |
3235 | let handle = unsafe { node.borrow_mut().push_with_handle(key, value) }; |
3236 | *root = Some(node.forget_type()); |
3237 | *self.length += 1; |
3238 | self.current = Some(handle.left_edge()); |
3239 | return; |
3240 | } |
3241 | Some(current) => current, |
3242 | }; |
3243 | |
3244 | let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { |
3245 | drop(ins.left); |
3246 | // SAFETY: The handle to the newly inserted value is always on a |
3247 | // leaf node, so adding a new root node doesn't invalidate it. |
3248 | let root = unsafe { self.root.reborrow().as_mut().unwrap() }; |
3249 | root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) |
3250 | }); |
3251 | self.current = Some(handle.left_edge()); |
3252 | *self.length += 1; |
3253 | } |
3254 | |
3255 | /// Inserts a new key-value pair into the map in the gap that the |
3256 | /// cursor is currently pointing to. |
3257 | /// |
3258 | /// After the insertion the cursor will be pointing at the gap after the |
3259 | /// newly inserted element. |
3260 | /// |
3261 | /// # Safety |
3262 | /// |
3263 | /// You must ensure that the `BTreeMap` invariants are maintained. |
3264 | /// Specifically: |
3265 | /// |
3266 | /// * The key of the newly inserted element must be unique in the tree. |
3267 | /// * All keys in the tree must remain in sorted order. |
3268 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3269 | pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) { |
3270 | let edge = match self.current.take() { |
3271 | None => { |
3272 | // SAFETY: We have no other reference to the tree. |
3273 | match unsafe { self.root.reborrow() } { |
3274 | root @ None => { |
3275 | // Tree is empty, allocate a new root. |
3276 | let mut node = NodeRef::new_leaf(self.alloc.clone()); |
3277 | // SAFETY: We don't touch the root while the handle is alive. |
3278 | let handle = unsafe { node.borrow_mut().push_with_handle(key, value) }; |
3279 | *root = Some(node.forget_type()); |
3280 | *self.length += 1; |
3281 | self.current = Some(handle.right_edge()); |
3282 | return; |
3283 | } |
3284 | Some(root) => root.borrow_mut().last_leaf_edge(), |
3285 | } |
3286 | } |
3287 | Some(current) => current, |
3288 | }; |
3289 | |
3290 | let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { |
3291 | drop(ins.left); |
3292 | // SAFETY: The handle to the newly inserted value is always on a |
3293 | // leaf node, so adding a new root node doesn't invalidate it. |
3294 | let root = unsafe { self.root.reborrow().as_mut().unwrap() }; |
3295 | root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) |
3296 | }); |
3297 | self.current = Some(handle.right_edge()); |
3298 | *self.length += 1; |
3299 | } |
3300 | |
3301 | /// Inserts a new key-value pair into the map in the gap that the |
3302 | /// cursor is currently pointing to. |
3303 | /// |
3304 | /// After the insertion the cursor will be pointing at the gap before the |
3305 | /// newly inserted element. |
3306 | /// |
3307 | /// If the inserted key is not greater than the key before the cursor |
3308 | /// (if any), or if it not less than the key after the cursor (if any), |
3309 | /// then an [`UnorderedKeyError`] is returned since this would |
3310 | /// invalidate the [`Ord`] invariant between the keys of the map. |
3311 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3312 | pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { |
3313 | if let Some((prev, _)) = self.peek_prev() { |
3314 | if &key <= prev { |
3315 | return Err(UnorderedKeyError {}); |
3316 | } |
3317 | } |
3318 | if let Some((next, _)) = self.peek_next() { |
3319 | if &key >= next { |
3320 | return Err(UnorderedKeyError {}); |
3321 | } |
3322 | } |
3323 | unsafe { |
3324 | self.insert_after_unchecked(key, value); |
3325 | } |
3326 | Ok(()) |
3327 | } |
3328 | |
3329 | /// Inserts a new key-value pair into the map in the gap that the |
3330 | /// cursor is currently pointing to. |
3331 | /// |
3332 | /// After the insertion the cursor will be pointing at the gap after the |
3333 | /// newly inserted element. |
3334 | /// |
3335 | /// If the inserted key is not greater than the key before the cursor |
3336 | /// (if any), or if it not less than the key after the cursor (if any), |
3337 | /// then an [`UnorderedKeyError`] is returned since this would |
3338 | /// invalidate the [`Ord`] invariant between the keys of the map. |
3339 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3340 | pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { |
3341 | if let Some((prev, _)) = self.peek_prev() { |
3342 | if &key <= prev { |
3343 | return Err(UnorderedKeyError {}); |
3344 | } |
3345 | } |
3346 | if let Some((next, _)) = self.peek_next() { |
3347 | if &key >= next { |
3348 | return Err(UnorderedKeyError {}); |
3349 | } |
3350 | } |
3351 | unsafe { |
3352 | self.insert_before_unchecked(key, value); |
3353 | } |
3354 | Ok(()) |
3355 | } |
3356 | |
3357 | /// Removes the next element from the `BTreeMap`. |
3358 | /// |
3359 | /// The element that was removed is returned. The cursor position is |
3360 | /// unchanged (before the removed element). |
3361 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3362 | pub fn remove_next(&mut self) -> Option<(K, V)> { |
3363 | let current = self.current.take()?; |
3364 | if current.reborrow().next_kv().is_err() { |
3365 | self.current = Some(current); |
3366 | return None; |
3367 | } |
3368 | let mut emptied_internal_root = false; |
3369 | let (kv, pos) = current |
3370 | .next_kv() |
3371 | // This should be unwrap(), but that doesn't work because NodeRef |
3372 | // doesn't implement Debug. The condition is checked above. |
3373 | .ok()? |
3374 | .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); |
3375 | self.current = Some(pos); |
3376 | *self.length -= 1; |
3377 | if emptied_internal_root { |
3378 | // SAFETY: This is safe since current does not point within the now |
3379 | // empty root node. |
3380 | let root = unsafe { self.root.reborrow().as_mut().unwrap() }; |
3381 | root.pop_internal_level(self.alloc.clone()); |
3382 | } |
3383 | Some(kv) |
3384 | } |
3385 | |
3386 | /// Removes the preceding element from the `BTreeMap`. |
3387 | /// |
3388 | /// The element that was removed is returned. The cursor position is |
3389 | /// unchanged (after the removed element). |
3390 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3391 | pub fn remove_prev(&mut self) -> Option<(K, V)> { |
3392 | let current = self.current.take()?; |
3393 | if current.reborrow().next_back_kv().is_err() { |
3394 | self.current = Some(current); |
3395 | return None; |
3396 | } |
3397 | let mut emptied_internal_root = false; |
3398 | let (kv, pos) = current |
3399 | .next_back_kv() |
3400 | // This should be unwrap(), but that doesn't work because NodeRef |
3401 | // doesn't implement Debug. The condition is checked above. |
3402 | .ok()? |
3403 | .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); |
3404 | self.current = Some(pos); |
3405 | *self.length -= 1; |
3406 | if emptied_internal_root { |
3407 | // SAFETY: This is safe since current does not point within the now |
3408 | // empty root node. |
3409 | let root = unsafe { self.root.reborrow().as_mut().unwrap() }; |
3410 | root.pop_internal_level(self.alloc.clone()); |
3411 | } |
3412 | Some(kv) |
3413 | } |
3414 | } |
3415 | |
3416 | impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { |
3417 | /// Inserts a new key-value pair into the map in the gap that the |
3418 | /// cursor is currently pointing to. |
3419 | /// |
3420 | /// After the insertion the cursor will be pointing at the gap after the |
3421 | /// newly inserted element. |
3422 | /// |
3423 | /// # Safety |
3424 | /// |
3425 | /// You must ensure that the `BTreeMap` invariants are maintained. |
3426 | /// Specifically: |
3427 | /// |
3428 | /// * The key of the newly inserted element must be unique in the tree. |
3429 | /// * All keys in the tree must remain in sorted order. |
3430 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3431 | pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) { |
3432 | unsafe { self.inner.insert_after_unchecked(key, value) } |
3433 | } |
3434 | |
3435 | /// Inserts a new key-value pair into the map in the gap that the |
3436 | /// cursor is currently pointing to. |
3437 | /// |
3438 | /// After the insertion the cursor will be pointing at the gap after the |
3439 | /// newly inserted element. |
3440 | /// |
3441 | /// # Safety |
3442 | /// |
3443 | /// You must ensure that the `BTreeMap` invariants are maintained. |
3444 | /// Specifically: |
3445 | /// |
3446 | /// * The key of the newly inserted element must be unique in the tree. |
3447 | /// * All keys in the tree must remain in sorted order. |
3448 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3449 | pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) { |
3450 | unsafe { self.inner.insert_before_unchecked(key, value) } |
3451 | } |
3452 | |
3453 | /// Inserts a new key-value pair into the map in the gap that the |
3454 | /// cursor is currently pointing to. |
3455 | /// |
3456 | /// After the insertion the cursor will be pointing at the gap before the |
3457 | /// newly inserted element. |
3458 | /// |
3459 | /// If the inserted key is not greater than the key before the cursor |
3460 | /// (if any), or if it not less than the key after the cursor (if any), |
3461 | /// then an [`UnorderedKeyError`] is returned since this would |
3462 | /// invalidate the [`Ord`] invariant between the keys of the map. |
3463 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3464 | pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { |
3465 | self.inner.insert_after(key, value) |
3466 | } |
3467 | |
3468 | /// Inserts a new key-value pair into the map in the gap that the |
3469 | /// cursor is currently pointing to. |
3470 | /// |
3471 | /// After the insertion the cursor will be pointing at the gap after the |
3472 | /// newly inserted element. |
3473 | /// |
3474 | /// If the inserted key is not greater than the key before the cursor |
3475 | /// (if any), or if it not less than the key after the cursor (if any), |
3476 | /// then an [`UnorderedKeyError`] is returned since this would |
3477 | /// invalidate the [`Ord`] invariant between the keys of the map. |
3478 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3479 | pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { |
3480 | self.inner.insert_before(key, value) |
3481 | } |
3482 | |
3483 | /// Removes the next element from the `BTreeMap`. |
3484 | /// |
3485 | /// The element that was removed is returned. The cursor position is |
3486 | /// unchanged (before the removed element). |
3487 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3488 | pub fn remove_next(&mut self) -> Option<(K, V)> { |
3489 | self.inner.remove_next() |
3490 | } |
3491 | |
3492 | /// Removes the preceding element from the `BTreeMap`. |
3493 | /// |
3494 | /// The element that was removed is returned. The cursor position is |
3495 | /// unchanged (after the removed element). |
3496 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3497 | pub fn remove_prev(&mut self) -> Option<(K, V)> { |
3498 | self.inner.remove_prev() |
3499 | } |
3500 | } |
3501 | |
3502 | /// Error type returned by [`CursorMut::insert_before`] and |
3503 | /// [`CursorMut::insert_after`] if the key being inserted is not properly |
3504 | /// ordered with regards to adjacent keys. |
3505 | #[derive(Clone, PartialEq, Eq, Debug)] |
3506 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3507 | pub struct UnorderedKeyError {} |
3508 | |
3509 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3510 | impl fmt::Display for UnorderedKeyError { |
3511 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
3512 | write!(f, "key is not properly ordered relative to neighbors") |
3513 | } |
3514 | } |
3515 | |
3516 | #[unstable(feature = "btree_cursors", issue = "107540")] |
3517 | impl Error for UnorderedKeyError {} |
3518 | |
3519 | #[cfg(test)] |
3520 | mod tests; |
3521 |
Definitions
- BTreeMap
- root
- length
- alloc
- _marker
- drop
- clone
- clone_subtree
- replace
- get_or_insert_with
- Iter
- range
- length
- fmt
- default
- IterMut
- range
- length
- _marker
- fmt
- default
- IntoIter
- range
- length
- alloc
- iter
- fmt
- default
- Keys
- inner
- fmt
- Values
- inner
- fmt
- ValuesMut
- inner
- fmt
- IntoKeys
- inner
- fmt
- IntoValues
- inner
- fmt
- Range
- inner
- fmt
- RangeMut
- inner
- _marker
- fmt
- new
- clear
- new_in
- get
- get_key_value
- first_key_value
- first_entry
- pop_first
- last_key_value
- last_entry
- pop_last
- contains_key
- get_mut
- insert
- try_insert
- remove
- remove_entry
- retain
- append
- range
- range_mut
- entry
- split_off
- extract_if
- extract_if_inner
- into_keys
- into_values
- bulk_build_from_sorted_iter
- Item
- IntoIter
- into_iter
- Item
- next
- size_hint
- last
- min
- max
- next_back
- len
- clone
- Item
- IntoIter
- into_iter
- Item
- next
- size_hint
- last
- min
- max
- next_back
- len
- iter
- Item
- IntoIter
- into_iter
- drop
- DropGuard
- drop
- dying_next
- dying_next_back
- Item
- next
- size_hint
- next_back
- len
- Item
- next
- size_hint
- last
- min
- max
- next_back
- len
- clone
- default
- Item
- next
- size_hint
- last
- next_back
- len
- clone
- default
- ExtractIf
- pred
- inner
- alloc
- ExtractIfInner
- length
- dormant_root
- cur_leaf_edge
- range
- fmt
- Item
- next
- size_hint
- peek
- next
- size_hint
- Item
- next
- last
- min
- max
- default
- default
- Item
- next
- size_hint
- last
- next_back
- len
- default
- Item
- next
- size_hint
- last
- min
- max
- next_back
- len
- default
- Item
- next
- size_hint
- last
- next_back
- len
- default
- next_back
- clone
- Item
- next
- last
- min
- max
- next_back
- from_iter
- extend
- extend_one
- extend
- extend_one
- hash
- default
- eq
- partial_cmp
- cmp
- fmt
- Output
- index
- from
- iter
- iter_mut
- keys
- values
- values_mut
- len
- is_empty
- lower_bound
- lower_bound_mut
- upper_bound
- upper_bound_mut
- Cursor
- current
- root
- clone
- current
- root
- fmt
- CursorMut
- inner
- fmt
- CursorMutKey
- current
- root
- length
- alloc
- fmt
- next
- prev
- peek_next
- peek_prev
- next
- prev
- peek_next
- peek_prev
- as_cursor
- with_mutable_key
- next
- prev
- peek_next
- peek_prev
- as_cursor
- insert_after_unchecked
- insert_before_unchecked
- insert_after
- insert_before
- remove_next
- remove_prev
- insert_after_unchecked
- insert_before_unchecked
- insert_after
- insert_before
- remove_next
- remove_prev
- UnorderedKeyError
Learn Rust with the experts
Find out more