]> git.proxmox.com Git - rustc.git/blob - src/libcollections/btree/map.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / libcollections / btree / map.rs
1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 use core::cmp::Ordering;
12 use core::fmt::Debug;
13 use core::hash::{Hash, Hasher};
14 use core::iter::FromIterator;
15 use core::marker::PhantomData;
16 use core::ops::Index;
17 use core::{fmt, intrinsics, mem, ptr};
18
19 use borrow::Borrow;
20 use Bound::{self, Included, Excluded, Unbounded};
21
22 use super::node::{self, NodeRef, Handle, marker};
23 use super::search;
24
25 use super::node::InsertResult::*;
26 use super::node::ForceResult::*;
27 use super::search::SearchResult::*;
28 use self::UnderflowResult::*;
29 use self::Entry::*;
30
31 /// A map based on a B-Tree.
32 ///
33 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
34 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
35 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
36 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
37 /// is done is *very* inefficient for modern computer architectures. In particular, every element
38 /// is stored in its own individually heap-allocated node. This means that every single insertion
39 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
40 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
41 /// the BST strategy.
42 ///
43 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
44 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
45 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
46 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
47 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
48 /// the node using binary search. As a compromise, one could also perform a linear search
49 /// that initially only checks every i<sup>th</sup> element for some choice of i.
50 ///
51 /// Currently, our implementation simply performs naive linear search. This provides excellent
52 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
53 /// would like to further explore choosing the optimal search strategy based on the choice of B,
54 /// and possibly other factors. Using linear search, searching for a random element is expected
55 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
56 /// however, performance is excellent.
57 ///
58 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
59 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
60 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
61 ///
62 /// # Examples
63 ///
64 /// ```
65 /// use std::collections::BTreeMap;
66 ///
67 /// // type inference lets us omit an explicit type signature (which
68 /// // would be `BTreeMap<&str, &str>` in this example).
69 /// let mut movie_reviews = BTreeMap::new();
70 ///
71 /// // review some books.
72 /// movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
73 /// movie_reviews.insert("Pulp Fiction", "Masterpiece.");
74 /// movie_reviews.insert("The Godfather", "Very enjoyable.");
75 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it alot.");
76 ///
77 /// // check for a specific one.
78 /// if !movie_reviews.contains_key("Les Misérables") {
79 /// println!("We've got {} reviews, but Les Misérables ain't one.",
80 /// movie_reviews.len());
81 /// }
82 ///
83 /// // oops, this review has a lot of spelling mistakes, let's delete it.
84 /// movie_reviews.remove("The Blues Brothers");
85 ///
86 /// // look up the values associated with some keys.
87 /// let to_find = ["Up!", "Office Space"];
88 /// for book in &to_find {
89 /// match movie_reviews.get(book) {
90 /// Some(review) => println!("{}: {}", book, review),
91 /// None => println!("{} is unreviewed.", book)
92 /// }
93 /// }
94 ///
95 /// // iterate over everything.
96 /// for (movie, review) in &movie_reviews {
97 /// println!("{}: \"{}\"", movie, review);
98 /// }
99 /// ```
100 ///
101 /// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
102 /// for more complex methods of getting, setting, updating and removing keys and
103 /// their values:
104 ///
105 /// ```
106 /// use std::collections::BTreeMap;
107 ///
108 /// // type inference lets us omit an explicit type signature (which
109 /// // would be `BTreeMap<&str, u8>` in this example).
110 /// let mut player_stats = BTreeMap::new();
111 ///
112 /// fn random_stat_buff() -> u8 {
113 /// // could actually return some random value here - let's just return
114 /// // some fixed value for now
115 /// 42
116 /// }
117 ///
118 /// // insert a key only if it doesn't already exist
119 /// player_stats.entry("health").or_insert(100);
120 ///
121 /// // insert a key using a function that provides a new value only if it
122 /// // doesn't already exist
123 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
124 ///
125 /// // update a key, guarding against the key possibly not being set
126 /// let stat = player_stats.entry("attack").or_insert(100);
127 /// *stat += random_stat_buff();
128 /// ```
129 #[stable(feature = "rust1", since = "1.0.0")]
130 pub struct BTreeMap<K, V> {
131 root: node::Root<K, V>,
132 length: usize
133 }
134
135 impl<K, V> Drop for BTreeMap<K, V> {
136 #[unsafe_destructor_blind_to_params]
137 fn drop(&mut self) {
138 unsafe {
139 for _ in ptr::read(self).into_iter() { }
140 }
141 }
142 }
143
144 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
145 fn clone(&self) -> BTreeMap<K, V> {
146 fn clone_subtree<K: Clone, V: Clone>(
147 node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
148 -> BTreeMap<K, V> {
149
150 match node.force() {
151 Leaf(leaf) => {
152 let mut out_tree = BTreeMap {
153 root: node::Root::new_leaf(),
154 length: 0
155 };
156
157 {
158 let mut out_node = match out_tree.root.as_mut().force() {
159 Leaf(leaf) => leaf,
160 Internal(_) => unreachable!()
161 };
162
163 let mut in_edge = leaf.first_edge();
164 while let Ok(kv) = in_edge.right_kv() {
165 let (k, v) = kv.into_kv();
166 in_edge = kv.right_edge();
167
168 out_node.push(k.clone(), v.clone());
169 out_tree.length += 1;
170 }
171 }
172
173 out_tree
174 },
175 Internal(internal) => {
176 let mut out_tree = clone_subtree(internal.first_edge().descend());
177
178 {
179 let mut out_node = out_tree.root.push_level();
180 let mut in_edge = internal.first_edge();
181 while let Ok(kv) = in_edge.right_kv() {
182 let (k, v) = kv.into_kv();
183 in_edge = kv.right_edge();
184
185 let k = (*k).clone();
186 let v = (*v).clone();
187 let subtree = clone_subtree(in_edge.descend());
188
189 // We can't destructure subtree directly
190 // because BTreeMap implements Drop
191 let (subroot, sublength) = unsafe {
192 let root = ptr::read(&subtree.root);
193 let length = subtree.length;
194 mem::forget(subtree);
195 (root, length)
196 };
197
198 out_node.push(k, v, subroot);
199 out_tree.length += 1 + sublength;
200 }
201 }
202
203 out_tree
204 }
205 }
206 }
207
208 clone_subtree(self.root.as_ref())
209 }
210 }
211
212 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
213 where K: Borrow<Q> + Ord,
214 Q: Ord
215 {
216 type Key = K;
217
218 fn get(&self, key: &Q) -> Option<&K> {
219 match search::search_tree(self.root.as_ref(), key) {
220 Found(handle) => Some(handle.into_kv().0),
221 GoDown(_) => None
222 }
223 }
224
225 fn take(&mut self, key: &Q) -> Option<K> {
226 match search::search_tree(self.root.as_mut(), key) {
227 Found(handle) => {
228 Some(OccupiedEntry {
229 handle: handle,
230 length: &mut self.length,
231 _marker: PhantomData,
232 }.remove_kv().0)
233 },
234 GoDown(_) => None
235 }
236 }
237
238 fn replace(&mut self, key: K) -> Option<K> {
239 match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
240 Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
241 GoDown(handle) => {
242 VacantEntry {
243 key: key,
244 handle: handle,
245 length: &mut self.length,
246 _marker: PhantomData,
247 }.insert(());
248 None
249 }
250 }
251 }
252 }
253
254 /// An iterator over a BTreeMap's entries.
255 #[stable(feature = "rust1", since = "1.0.0")]
256 pub struct Iter<'a, K: 'a, V: 'a> {
257 range: Range<'a, K, V>,
258 length: usize
259 }
260
261 /// A mutable iterator over a BTreeMap's entries.
262 #[stable(feature = "rust1", since = "1.0.0")]
263 pub struct IterMut<'a, K: 'a, V: 'a> {
264 range: RangeMut<'a, K, V>,
265 length: usize
266 }
267
268 /// An owning iterator over a BTreeMap's entries.
269 #[stable(feature = "rust1", since = "1.0.0")]
270 pub struct IntoIter<K, V> {
271 front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
272 back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
273 length: usize
274 }
275
276 /// An iterator over a BTreeMap's keys.
277 #[stable(feature = "rust1", since = "1.0.0")]
278 pub struct Keys<'a, K: 'a, V: 'a> {
279 inner: Iter<'a, K, V>,
280 }
281
282 /// An iterator over a BTreeMap's values.
283 #[stable(feature = "rust1", since = "1.0.0")]
284 pub struct Values<'a, K: 'a, V: 'a> {
285 inner: Iter<'a, K, V>,
286 }
287
288 /// A mutable iterator over a BTreeMap's values.
289 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
290 pub struct ValuesMut<'a, K: 'a, V: 'a> {
291 inner: IterMut<'a, K, V>,
292 }
293
294 /// An iterator over a sub-range of BTreeMap's entries.
295 pub struct Range<'a, K: 'a, V: 'a> {
296 front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
297 back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
298 }
299
300 /// A mutable iterator over a sub-range of BTreeMap's entries.
301 pub struct RangeMut<'a, K: 'a, V: 'a> {
302 front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
303 back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
304
305 // Be invariant in `K` and `V`
306 _marker: PhantomData<&'a mut (K, V)>,
307 }
308
309 /// A view into a single entry in a map, which may either be vacant or occupied.
310 #[stable(feature = "rust1", since = "1.0.0")]
311 pub enum Entry<'a, K: 'a, V: 'a> {
312 /// A vacant Entry
313 #[stable(feature = "rust1", since = "1.0.0")]
314 Vacant(
315 #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
316 ),
317
318 /// An occupied Entry
319 #[stable(feature = "rust1", since = "1.0.0")]
320 Occupied(
321 #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
322 ),
323 }
324
325 /// A vacant Entry.
326 #[stable(feature = "rust1", since = "1.0.0")]
327 pub struct VacantEntry<'a, K: 'a, V: 'a> {
328 key: K,
329 handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
330 length: &'a mut usize,
331
332 // Be invariant in `K` and `V`
333 _marker: PhantomData<&'a mut (K, V)>,
334 }
335
336 /// An occupied Entry.
337 #[stable(feature = "rust1", since = "1.0.0")]
338 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
339 handle: Handle<NodeRef<
340 marker::Mut<'a>,
341 K, V,
342 marker::LeafOrInternal
343 >, marker::KV>,
344
345 length: &'a mut usize,
346
347 // Be invariant in `K` and `V`
348 _marker: PhantomData<&'a mut (K, V)>,
349 }
350
351 impl<K: Ord, V> BTreeMap<K, V> {
352 /// Makes a new empty BTreeMap with a reasonable choice for B.
353 ///
354 /// # Examples
355 ///
356 /// Basic usage:
357 ///
358 /// ```
359 /// use std::collections::BTreeMap;
360 ///
361 /// let mut map = BTreeMap::new();
362 ///
363 /// // entries can now be inserted into the empty map
364 /// map.insert(1, "a");
365 /// ```
366 #[stable(feature = "rust1", since = "1.0.0")]
367 pub fn new() -> BTreeMap<K, V> {
368 BTreeMap {
369 root: node::Root::new_leaf(),
370 length: 0
371 }
372 }
373
374 /// Clears the map, removing all values.
375 ///
376 /// # Examples
377 ///
378 /// Basic usage:
379 ///
380 /// ```
381 /// use std::collections::BTreeMap;
382 ///
383 /// let mut a = BTreeMap::new();
384 /// a.insert(1, "a");
385 /// a.clear();
386 /// assert!(a.is_empty());
387 /// ```
388 #[stable(feature = "rust1", since = "1.0.0")]
389 pub fn clear(&mut self) {
390 // FIXME(gereeter) .clear() allocates
391 *self = BTreeMap::new();
392 }
393
394 /// Returns a reference to the value corresponding to the key.
395 ///
396 /// The key may be any borrowed form of the map's key type, but the ordering
397 /// on the borrowed form *must* match the ordering on the key type.
398 ///
399 /// # Examples
400 ///
401 /// Basic usage:
402 ///
403 /// ```
404 /// use std::collections::BTreeMap;
405 ///
406 /// let mut map = BTreeMap::new();
407 /// map.insert(1, "a");
408 /// assert_eq!(map.get(&1), Some(&"a"));
409 /// assert_eq!(map.get(&2), None);
410 /// ```
411 #[stable(feature = "rust1", since = "1.0.0")]
412 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
413 match search::search_tree(self.root.as_ref(), key) {
414 Found(handle) => Some(handle.into_kv().1),
415 GoDown(_) => None
416 }
417 }
418
419 /// Returns true if the map contains a value for the specified key.
420 ///
421 /// The key may be any borrowed form of the map's key type, but the ordering
422 /// on the borrowed form *must* match the ordering on the key type.
423 ///
424 /// # Examples
425 ///
426 /// Basic usage:
427 ///
428 /// ```
429 /// use std::collections::BTreeMap;
430 ///
431 /// let mut map = BTreeMap::new();
432 /// map.insert(1, "a");
433 /// assert_eq!(map.contains_key(&1), true);
434 /// assert_eq!(map.contains_key(&2), false);
435 /// ```
436 #[stable(feature = "rust1", since = "1.0.0")]
437 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
438 self.get(key).is_some()
439 }
440
441 /// Returns a mutable reference to the value corresponding to the key.
442 ///
443 /// The key may be any borrowed form of the map's key type, but the ordering
444 /// on the borrowed form *must* match the ordering on the key type.
445 ///
446 /// # Examples
447 ///
448 /// Basic usage:
449 ///
450 /// ```
451 /// use std::collections::BTreeMap;
452 ///
453 /// let mut map = BTreeMap::new();
454 /// map.insert(1, "a");
455 /// if let Some(x) = map.get_mut(&1) {
456 /// *x = "b";
457 /// }
458 /// assert_eq!(map[&1], "b");
459 /// ```
460 // See `get` for implementation notes, this is basically a copy-paste with mut's added
461 #[stable(feature = "rust1", since = "1.0.0")]
462 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
463 match search::search_tree(self.root.as_mut(), key) {
464 Found(handle) => Some(handle.into_kv_mut().1),
465 GoDown(_) => None
466 }
467 }
468
469 /// Inserts a key-value pair into the map.
470 ///
471 /// If the map did not have this key present, `None` is returned.
472 ///
473 /// If the map did have this key present, the value is updated, and the old
474 /// value is returned. The key is not updated, though; this matters for
475 /// types that can be `==` without being identical. See the [module-level
476 /// documentation] for more.
477 ///
478 /// [module-level documentation]: index.html#insert-and-complex-keys
479 ///
480 /// # Examples
481 ///
482 /// Basic usage:
483 ///
484 /// ```
485 /// use std::collections::BTreeMap;
486 ///
487 /// let mut map = BTreeMap::new();
488 /// assert_eq!(map.insert(37, "a"), None);
489 /// assert_eq!(map.is_empty(), false);
490 ///
491 /// map.insert(37, "b");
492 /// assert_eq!(map.insert(37, "c"), Some("b"));
493 /// assert_eq!(map[&37], "c");
494 /// ```
495 #[stable(feature = "rust1", since = "1.0.0")]
496 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
497 match self.entry(key) {
498 Occupied(mut entry) => Some(entry.insert(value)),
499 Vacant(entry) => {
500 entry.insert(value);
501 None
502 }
503 }
504 }
505
506 /// Removes a key from the map, returning the value at the key if the key
507 /// was previously in the map.
508 ///
509 /// The key may be any borrowed form of the map's key type, but the ordering
510 /// on the borrowed form *must* match the ordering on the key type.
511 ///
512 /// # Examples
513 ///
514 /// Basic usage:
515 ///
516 /// ```
517 /// use std::collections::BTreeMap;
518 ///
519 /// let mut map = BTreeMap::new();
520 /// map.insert(1, "a");
521 /// assert_eq!(map.remove(&1), Some("a"));
522 /// assert_eq!(map.remove(&1), None);
523 /// ```
524 #[stable(feature = "rust1", since = "1.0.0")]
525 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
526 match search::search_tree(self.root.as_mut(), key) {
527 Found(handle) => {
528 Some(OccupiedEntry {
529 handle: handle,
530 length: &mut self.length,
531 _marker: PhantomData,
532 }.remove())
533 },
534 GoDown(_) => None
535 }
536 }
537
538 /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
539 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
540 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
541 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
542 ///
543 /// # Examples
544 ///
545 /// Basic usage:
546 ///
547 /// ```
548 /// #![feature(btree_range, collections_bound)]
549 ///
550 /// use std::collections::BTreeMap;
551 /// use std::collections::Bound::{Included, Unbounded};
552 ///
553 /// let mut map = BTreeMap::new();
554 /// map.insert(3, "a");
555 /// map.insert(5, "b");
556 /// map.insert(8, "c");
557 /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
558 /// println!("{}: {}", key, value);
559 /// }
560 /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
561 /// ```
562 #[unstable(feature = "btree_range",
563 reason = "matches collection reform specification, waiting for dust to settle",
564 issue = "27787")]
565 pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
566 min: Bound<&Min>,
567 max: Bound<&Max>)
568 -> Range<K, V>
569 where K: Borrow<Min> + Borrow<Max>,
570 {
571 let front = match min {
572 Included(key) => match search::search_tree(self.root.as_ref(), key) {
573 Found(kv_handle) => match kv_handle.left_edge().force() {
574 Leaf(bottom) => bottom,
575 Internal(internal) => last_leaf_edge(internal.descend())
576 },
577 GoDown(bottom) => bottom
578 },
579 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
580 Found(kv_handle) => match kv_handle.right_edge().force() {
581 Leaf(bottom) => bottom,
582 Internal(internal) => first_leaf_edge(internal.descend())
583 },
584 GoDown(bottom) => bottom
585 },
586 Unbounded => first_leaf_edge(self.root.as_ref())
587 };
588
589 let back = match max {
590 Included(key) => match search::search_tree(self.root.as_ref(), key) {
591 Found(kv_handle) => match kv_handle.right_edge().force() {
592 Leaf(bottom) => bottom,
593 Internal(internal) => first_leaf_edge(internal.descend())
594 },
595 GoDown(bottom) => bottom
596 },
597 Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
598 Found(kv_handle) => match kv_handle.left_edge().force() {
599 Leaf(bottom) => bottom,
600 Internal(internal) => last_leaf_edge(internal.descend())
601 },
602 GoDown(bottom) => bottom
603 },
604 Unbounded => last_leaf_edge(self.root.as_ref())
605 };
606
607 Range {
608 front: front,
609 back: back
610 }
611 }
612
613 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
614 /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
615 /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
616 /// Thus range(Unbounded, Unbounded) will yield the whole collection.
617 ///
618 /// # Examples
619 ///
620 /// Basic usage:
621 ///
622 /// ```
623 /// #![feature(btree_range, collections_bound)]
624 ///
625 /// use std::collections::BTreeMap;
626 /// use std::collections::Bound::{Included, Excluded};
627 ///
628 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
629 /// .map(|&s| (s, 0))
630 /// .collect();
631 /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
632 /// *balance += 100;
633 /// }
634 /// for (name, balance) in &map {
635 /// println!("{} => {}", name, balance);
636 /// }
637 /// ```
638 #[unstable(feature = "btree_range",
639 reason = "matches collection reform specification, waiting for dust to settle",
640 issue = "27787")]
641 pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
642 min: Bound<&Min>,
643 max: Bound<&Max>)
644 -> RangeMut<K, V>
645 where K: Borrow<Min> + Borrow<Max>,
646 {
647 let root1 = self.root.as_mut();
648 let root2 = unsafe { ptr::read(&root1) };
649
650 let front = match min {
651 Included(key) => match search::search_tree(root1, key) {
652 Found(kv_handle) => match kv_handle.left_edge().force() {
653 Leaf(bottom) => bottom,
654 Internal(internal) => last_leaf_edge(internal.descend())
655 },
656 GoDown(bottom) => bottom
657 },
658 Excluded(key) => match search::search_tree(root1, key) {
659 Found(kv_handle) => match kv_handle.right_edge().force() {
660 Leaf(bottom) => bottom,
661 Internal(internal) => first_leaf_edge(internal.descend())
662 },
663 GoDown(bottom) => bottom
664 },
665 Unbounded => first_leaf_edge(root1)
666 };
667
668 let back = match max {
669 Included(key) => match search::search_tree(root2, key) {
670 Found(kv_handle) => match kv_handle.right_edge().force() {
671 Leaf(bottom) => bottom,
672 Internal(internal) => first_leaf_edge(internal.descend())
673 },
674 GoDown(bottom) => bottom
675 },
676 Excluded(key) => match search::search_tree(root2, key) {
677 Found(kv_handle) => match kv_handle.left_edge().force() {
678 Leaf(bottom) => bottom,
679 Internal(internal) => last_leaf_edge(internal.descend())
680 },
681 GoDown(bottom) => bottom
682 },
683 Unbounded => last_leaf_edge(root2)
684 };
685
686 RangeMut {
687 front: front,
688 back: back,
689 _marker: PhantomData
690 }
691 }
692
693 /// Gets the given key's corresponding entry in the map for in-place manipulation.
694 ///
695 /// # Examples
696 ///
697 /// Basic usage:
698 ///
699 /// ```
700 /// use std::collections::BTreeMap;
701 ///
702 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
703 ///
704 /// // count the number of occurrences of letters in the vec
705 /// for x in vec!["a","b","a","c","a","b"] {
706 /// *count.entry(x).or_insert(0) += 1;
707 /// }
708 ///
709 /// assert_eq!(count["a"], 3);
710 /// ```
711 #[stable(feature = "rust1", since = "1.0.0")]
712 pub fn entry(&mut self, key: K) -> Entry<K, V> {
713 match search::search_tree(self.root.as_mut(), &key) {
714 Found(handle) => Occupied(OccupiedEntry {
715 handle: handle,
716 length: &mut self.length,
717 _marker: PhantomData,
718 }),
719 GoDown(handle) => Vacant(VacantEntry {
720 key: key,
721 handle: handle,
722 length: &mut self.length,
723 _marker: PhantomData,
724 })
725 }
726 }
727 }
728
729 impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
730 type Item = (&'a K, &'a V);
731 type IntoIter = Iter<'a, K, V>;
732
733 fn into_iter(self) -> Iter<'a, K, V> {
734 self.iter()
735 }
736 }
737
738 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
739 type Item = (&'a K, &'a V);
740
741 fn next(&mut self) -> Option<(&'a K, &'a V)> {
742 if self.length == 0 {
743 None
744 } else {
745 self.length -= 1;
746 unsafe { Some(self.range.next_unchecked()) }
747 }
748 }
749
750 fn size_hint(&self) -> (usize, Option<usize>) {
751 (self.length, Some(self.length))
752 }
753 }
754
755 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
756 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
757 if self.length == 0 {
758 None
759 } else {
760 self.length -= 1;
761 unsafe { Some(self.range.next_back_unchecked()) }
762 }
763 }
764 }
765
766 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
767 fn len(&self) -> usize { self.length }
768 }
769
770 impl<'a, K, V> Clone for Iter<'a, K, V> {
771 fn clone(&self) -> Iter<'a, K, V> {
772 Iter {
773 range: self.range.clone(),
774 length: self.length
775 }
776 }
777 }
778
779 impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
780 type Item = (&'a K, &'a mut V);
781 type IntoIter = IterMut<'a, K, V>;
782
783 fn into_iter(self) -> IterMut<'a, K, V> {
784 self.iter_mut()
785 }
786 }
787
788 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
789 type Item = (&'a K, &'a mut V);
790
791 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
792 if self.length == 0 {
793 None
794 } else {
795 self.length -= 1;
796 unsafe { Some(self.range.next_unchecked()) }
797 }
798 }
799
800 fn size_hint(&self) -> (usize, Option<usize>) {
801 (self.length, Some(self.length))
802 }
803 }
804
805 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
806 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
807 if self.length == 0 {
808 None
809 } else {
810 self.length -= 1;
811 unsafe { Some(self.range.next_back_unchecked()) }
812 }
813 }
814 }
815
816 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
817 fn len(&self) -> usize { self.length }
818 }
819
820 impl<K, V> IntoIterator for BTreeMap<K, V> {
821 type Item = (K, V);
822 type IntoIter = IntoIter<K, V>;
823
824 fn into_iter(self) -> IntoIter<K, V> {
825 let root1 = unsafe { ptr::read(&self.root).into_ref() };
826 let root2 = unsafe { ptr::read(&self.root).into_ref() };
827 let len = self.length;
828 mem::forget(self);
829
830 IntoIter {
831 front: first_leaf_edge(root1),
832 back: last_leaf_edge(root2),
833 length: len
834 }
835 }
836 }
837
838 impl<K, V> Drop for IntoIter<K, V> {
839 fn drop(&mut self) {
840 for _ in &mut *self { }
841 unsafe {
842 let leaf_node = ptr::read(&self.front).into_node();
843 if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
844 let mut cur_node = first_parent.into_node();
845 while let Some(parent) = cur_node.deallocate_and_ascend() {
846 cur_node = parent.into_node()
847 }
848 }
849 }
850 }
851 }
852
853 impl<K, V> Iterator for IntoIter<K, V> {
854 type Item = (K, V);
855
856 fn next(&mut self) -> Option<(K, V)> {
857 if self.length == 0 {
858 return None;
859 } else {
860 self.length -= 1;
861 }
862
863 let handle = unsafe { ptr::read(&self.front) };
864
865 let mut cur_handle = match handle.right_kv() {
866 Ok(kv) => {
867 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
868 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
869 self.front = kv.right_edge();
870 return Some((k, v));
871 },
872 Err(last_edge) => unsafe {
873 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
874 }
875 };
876
877 loop {
878 match cur_handle.right_kv() {
879 Ok(kv) => {
880 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
881 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
882 self.front = first_leaf_edge(kv.right_edge().descend());
883 return Some((k, v));
884 },
885 Err(last_edge) => unsafe {
886 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
887 }
888 }
889 }
890 }
891
892 fn size_hint(&self) -> (usize, Option<usize>) {
893 (self.length, Some(self.length))
894 }
895 }
896
897 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
898 fn next_back(&mut self) -> Option<(K, V)> {
899 if self.length == 0 {
900 return None;
901 } else {
902 self.length -= 1;
903 }
904
905 let handle = unsafe { ptr::read(&self.back) };
906
907 let mut cur_handle = match handle.left_kv() {
908 Ok(kv) => {
909 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
910 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
911 self.back = kv.left_edge();
912 return Some((k, v));
913 },
914 Err(last_edge) => unsafe {
915 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
916 }
917 };
918
919 loop {
920 match cur_handle.left_kv() {
921 Ok(kv) => {
922 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
923 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
924 self.back = last_leaf_edge(kv.left_edge().descend());
925 return Some((k, v));
926 },
927 Err(last_edge) => unsafe {
928 cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
929 }
930 }
931 }
932 }
933 }
934
935 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
936 fn len(&self) -> usize { self.length }
937 }
938
939 impl<'a, K, V> Iterator for Keys<'a, K, V> {
940 type Item = &'a K;
941
942 fn next(&mut self) -> Option<&'a K> {
943 self.inner.next().map(|(k, _)| k)
944 }
945
946 fn size_hint(&self) -> (usize, Option<usize>) {
947 self.inner.size_hint()
948 }
949 }
950
951 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
952 fn next_back(&mut self) -> Option<&'a K> {
953 self.inner.next_back().map(|(k, _)| k)
954 }
955 }
956
957 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
958 fn len(&self) -> usize {
959 self.inner.len()
960 }
961 }
962
963 impl<'a, K, V> Clone for Keys<'a, K, V> {
964 fn clone(&self) -> Keys<'a, K, V> {
965 Keys {
966 inner: self.inner.clone()
967 }
968 }
969 }
970
971 impl<'a, K, V> Iterator for Values<'a, K, V> {
972 type Item = &'a V;
973
974 fn next(&mut self) -> Option<&'a V> {
975 self.inner.next().map(|(_, v)| v)
976 }
977
978 fn size_hint(&self) -> (usize, Option<usize>) {
979 self.inner.size_hint()
980 }
981 }
982
983 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
984 fn next_back(&mut self) -> Option<&'a V> {
985 self.inner.next_back().map(|(_, v)| v)
986 }
987 }
988
989 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
990 fn len(&self) -> usize {
991 self.inner.len()
992 }
993 }
994
995 impl<'a, K, V> Clone for Values<'a, K, V> {
996 fn clone(&self) -> Values<'a, K, V> {
997 Values {
998 inner: self.inner.clone()
999 }
1000 }
1001 }
1002
1003 impl<'a, K, V> Iterator for Range<'a, K, V> {
1004 type Item = (&'a K, &'a V);
1005
1006 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1007 if self.front == self.back {
1008 None
1009 } else {
1010 unsafe { Some(self.next_unchecked()) }
1011 }
1012 }
1013 }
1014
1015 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1016 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1017 type Item = &'a mut V;
1018
1019 fn next(&mut self) -> Option<&'a mut V> {
1020 self.inner.next().map(|(_, v)| v)
1021 }
1022
1023 fn size_hint(&self) -> (usize, Option<usize>) {
1024 self.inner.size_hint()
1025 }
1026 }
1027
1028 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1029 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
1030 fn next_back(&mut self) -> Option<&'a mut V> {
1031 self.inner.next_back().map(|(_, v)| v)
1032 }
1033 }
1034
1035 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1036 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
1037 fn len(&self) -> usize {
1038 self.inner.len()
1039 }
1040 }
1041
1042 impl<'a, K, V> Range<'a, K, V> {
1043 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
1044 let handle = self.front;
1045
1046 let mut cur_handle = match handle.right_kv() {
1047 Ok(kv) => {
1048 let ret = kv.into_kv();
1049 self.front = kv.right_edge();
1050 return ret;
1051 },
1052 Err(last_edge) => {
1053 let next_level = last_edge.into_node().ascend().ok();
1054 unwrap_unchecked(next_level)
1055 }
1056 };
1057
1058 loop {
1059 match cur_handle.right_kv() {
1060 Ok(kv) => {
1061 let ret = kv.into_kv();
1062 self.front = first_leaf_edge(kv.right_edge().descend());
1063 return ret;
1064 },
1065 Err(last_edge) => {
1066 let next_level = last_edge.into_node().ascend().ok();
1067 cur_handle = unwrap_unchecked(next_level);
1068 }
1069 }
1070 }
1071 }
1072 }
1073
1074 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1075 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1076 if self.front == self.back {
1077 None
1078 } else {
1079 unsafe { Some(self.next_back_unchecked()) }
1080 }
1081 }
1082 }
1083
1084 impl<'a, K, V> Range<'a, K, V> {
1085 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
1086 let handle = self.back;
1087
1088 let mut cur_handle = match handle.left_kv() {
1089 Ok(kv) => {
1090 let ret = kv.into_kv();
1091 self.back = kv.left_edge();
1092 return ret;
1093 },
1094 Err(last_edge) => {
1095 let next_level = last_edge.into_node().ascend().ok();
1096 unwrap_unchecked(next_level)
1097 }
1098 };
1099
1100 loop {
1101 match cur_handle.left_kv() {
1102 Ok(kv) => {
1103 let ret = kv.into_kv();
1104 self.back = last_leaf_edge(kv.left_edge().descend());
1105 return ret;
1106 },
1107 Err(last_edge) => {
1108 let next_level = last_edge.into_node().ascend().ok();
1109 cur_handle = unwrap_unchecked(next_level);
1110 }
1111 }
1112 }
1113 }
1114 }
1115
1116 impl<'a, K, V> Clone for Range<'a, K, V> {
1117 fn clone(&self) -> Range<'a, K, V> {
1118 Range {
1119 front: self.front,
1120 back: self.back
1121 }
1122 }
1123 }
1124
1125 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1126 type Item = (&'a K, &'a mut V);
1127
1128 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1129 if self.front == self.back {
1130 None
1131 } else {
1132 unsafe { Some (self.next_unchecked()) }
1133 }
1134 }
1135 }
1136
1137 impl<'a, K, V> RangeMut<'a, K, V> {
1138 unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
1139 let handle = ptr::read(&self.front);
1140
1141 let mut cur_handle = match handle.right_kv() {
1142 Ok(kv) => {
1143 let (k, v) = ptr::read(&kv).into_kv_mut();
1144 self.front = kv.right_edge();
1145 return (k, v);
1146 },
1147 Err(last_edge) => {
1148 let next_level = last_edge.into_node().ascend().ok();
1149 unwrap_unchecked(next_level)
1150 }
1151 };
1152
1153 loop {
1154 match cur_handle.right_kv() {
1155 Ok(kv) => {
1156 let (k, v) = ptr::read(&kv).into_kv_mut();
1157 self.front = first_leaf_edge(kv.right_edge().descend());
1158 return (k, v);
1159 },
1160 Err(last_edge) => {
1161 let next_level = last_edge.into_node().ascend().ok();
1162 cur_handle = unwrap_unchecked(next_level);
1163 }
1164 }
1165 }
1166 }
1167 }
1168
1169 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1170 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1171 if self.front == self.back {
1172 None
1173 } else {
1174 unsafe { Some(self.next_back_unchecked()) }
1175 }
1176 }
1177 }
1178
1179 impl<'a, K, V> RangeMut<'a, K, V> {
1180 unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
1181 let handle = ptr::read(&self.back);
1182
1183 let mut cur_handle = match handle.left_kv() {
1184 Ok(kv) => {
1185 let (k, v) = ptr::read(&kv).into_kv_mut();
1186 self.back = kv.left_edge();
1187 return (k, v);
1188 },
1189 Err(last_edge) => {
1190 let next_level = last_edge.into_node().ascend().ok();
1191 unwrap_unchecked(next_level)
1192 }
1193 };
1194
1195 loop {
1196 match cur_handle.left_kv() {
1197 Ok(kv) => {
1198 let (k, v) = ptr::read(&kv).into_kv_mut();
1199 self.back = last_leaf_edge(kv.left_edge().descend());
1200 return (k, v);
1201 },
1202 Err(last_edge) => {
1203 let next_level = last_edge.into_node().ascend().ok();
1204 cur_handle = unwrap_unchecked(next_level);
1205 }
1206 }
1207 }
1208 }
1209 }
1210
1211 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1212 fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
1213 let mut map = BTreeMap::new();
1214 map.extend(iter);
1215 map
1216 }
1217 }
1218
1219 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1220 #[inline]
1221 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1222 for (k, v) in iter {
1223 self.insert(k, v);
1224 }
1225 }
1226 }
1227
1228 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1229 fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
1230 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1231 }
1232 }
1233
1234 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1235 fn hash<H: Hasher>(&self, state: &mut H) {
1236 for elt in self {
1237 elt.hash(state);
1238 }
1239 }
1240 }
1241
1242 impl<K: Ord, V> Default for BTreeMap<K, V> {
1243 fn default() -> BTreeMap<K, V> {
1244 BTreeMap::new()
1245 }
1246 }
1247
1248 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
1249 fn eq(&self, other: &BTreeMap<K, V>) -> bool {
1250 self.len() == other.len() &&
1251 self.iter().zip(other).all(|(a, b)| a == b)
1252 }
1253 }
1254
1255 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
1256
1257 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
1258 #[inline]
1259 fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
1260 self.iter().partial_cmp(other.iter())
1261 }
1262 }
1263
1264 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
1265 #[inline]
1266 fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
1267 self.iter().cmp(other.iter())
1268 }
1269 }
1270
1271 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
1272 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1273 f.debug_map().entries(self.iter()).finish()
1274 }
1275 }
1276
1277 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
1278 where K: Borrow<Q>, Q: Ord
1279 {
1280 type Output = V;
1281
1282 #[inline]
1283 fn index(&self, key: &Q) -> &V {
1284 self.get(key).expect("no entry found for key")
1285 }
1286 }
1287
1288 fn first_leaf_edge<BorrowType, K, V>(
1289 mut node: NodeRef<BorrowType,
1290 K, V,
1291 marker::LeafOrInternal>
1292 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1293 loop {
1294 match node.force() {
1295 Leaf(leaf) => return leaf.first_edge(),
1296 Internal(internal) => {
1297 node = internal.first_edge().descend();
1298 }
1299 }
1300 }
1301 }
1302
1303 fn last_leaf_edge<BorrowType, K, V>(
1304 mut node: NodeRef<BorrowType,
1305 K, V,
1306 marker::LeafOrInternal>
1307 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
1308 loop {
1309 match node.force() {
1310 Leaf(leaf) => return leaf.last_edge(),
1311 Internal(internal) => {
1312 node = internal.last_edge().descend();
1313 }
1314 }
1315 }
1316 }
1317
1318 #[inline(always)]
1319 unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
1320 val.unwrap_or_else(|| {
1321 if cfg!(debug_assertions) {
1322 panic!("'unchecked' unwrap on None in BTreeMap");
1323 } else {
1324 intrinsics::unreachable();
1325 }
1326 })
1327 }
1328
1329 impl<K, V> BTreeMap<K, V> {
1330 /// Gets an iterator over the entries of the map, sorted by key.
1331 ///
1332 /// # Examples
1333 ///
1334 /// Basic usage:
1335 ///
1336 /// ```
1337 /// use std::collections::BTreeMap;
1338 ///
1339 /// let mut map = BTreeMap::new();
1340 /// map.insert(3, "c");
1341 /// map.insert(2, "b");
1342 /// map.insert(1, "a");
1343 ///
1344 /// for (key, value) in map.iter() {
1345 /// println!("{}: {}", key, value);
1346 /// }
1347 ///
1348 /// let (first_key, first_value) = map.iter().next().unwrap();
1349 /// assert_eq!((*first_key, *first_value), (1, "a"));
1350 /// ```
1351 #[stable(feature = "rust1", since = "1.0.0")]
1352 pub fn iter(&self) -> Iter<K, V> {
1353 Iter {
1354 range: Range {
1355 front: first_leaf_edge(self.root.as_ref()),
1356 back: last_leaf_edge(self.root.as_ref())
1357 },
1358 length: self.length
1359 }
1360 }
1361
1362 /// Gets a mutable iterator over the entries of the map, sorted by key.
1363 ///
1364 /// # Examples
1365 ///
1366 /// Basic usage:
1367 ///
1368 /// ```
1369 /// use std::collections::BTreeMap;
1370 ///
1371 /// let mut map = BTreeMap::new();
1372 /// map.insert("a", 1);
1373 /// map.insert("b", 2);
1374 /// map.insert("c", 3);
1375 ///
1376 /// // add 10 to the value if the key isn't "a"
1377 /// for (key, value) in map.iter_mut() {
1378 /// if key != &"a" {
1379 /// *value += 10;
1380 /// }
1381 /// }
1382 /// ```
1383 #[stable(feature = "rust1", since = "1.0.0")]
1384 pub fn iter_mut(&mut self) -> IterMut<K, V> {
1385 let root1 = self.root.as_mut();
1386 let root2 = unsafe { ptr::read(&root1) };
1387 IterMut {
1388 range: RangeMut {
1389 front: first_leaf_edge(root1),
1390 back: last_leaf_edge(root2),
1391 _marker: PhantomData,
1392 },
1393 length: self.length
1394 }
1395 }
1396
1397 /// Gets an iterator over the keys of the map, in sorted order.
1398 ///
1399 /// # Examples
1400 ///
1401 /// Basic usage:
1402 ///
1403 /// ```
1404 /// use std::collections::BTreeMap;
1405 ///
1406 /// let mut a = BTreeMap::new();
1407 /// a.insert(2, "b");
1408 /// a.insert(1, "a");
1409 ///
1410 /// let keys: Vec<_> = a.keys().cloned().collect();
1411 /// assert_eq!(keys, [1, 2]);
1412 /// ```
1413 #[stable(feature = "rust1", since = "1.0.0")]
1414 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1415 Keys { inner: self.iter() }
1416 }
1417
1418 /// Gets an iterator over the values of the map, in order by key.
1419 ///
1420 /// # Examples
1421 ///
1422 /// Basic usage:
1423 ///
1424 /// ```
1425 /// use std::collections::BTreeMap;
1426 ///
1427 /// let mut a = BTreeMap::new();
1428 /// a.insert(1, "hello");
1429 /// a.insert(2, "goodbye");
1430 ///
1431 /// let values: Vec<&str> = a.values().cloned().collect();
1432 /// assert_eq!(values, ["hello", "goodbye"]);
1433 /// ```
1434 #[stable(feature = "rust1", since = "1.0.0")]
1435 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1436 Values { inner: self.iter() }
1437 }
1438
1439 /// Gets a mutable iterator over the values of the map, in order by key.
1440 ///
1441 /// # Examples
1442 ///
1443 /// Basic usage:
1444 ///
1445 /// ```
1446 /// # #![feature(map_values_mut)]
1447 /// use std::collections::BTreeMap;
1448 ///
1449 /// let mut a = BTreeMap::new();
1450 /// a.insert(1, String::from("hello"));
1451 /// a.insert(2, String::from("goodbye"));
1452 ///
1453 /// for value in a.values_mut() {
1454 /// value.push_str("!");
1455 /// }
1456 ///
1457 /// let values: Vec<String> = a.values().cloned().collect();
1458 /// assert_eq!(values, [String::from("hello!"),
1459 /// String::from("goodbye!")]);
1460 /// ```
1461 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1462 pub fn values_mut<'a>(&'a mut self) -> ValuesMut<'a, K, V> {
1463 ValuesMut { inner: self.iter_mut() }
1464 }
1465
1466 /// Returns the number of elements in the map.
1467 ///
1468 /// # Examples
1469 ///
1470 /// Basic usage:
1471 ///
1472 /// ```
1473 /// use std::collections::BTreeMap;
1474 ///
1475 /// let mut a = BTreeMap::new();
1476 /// assert_eq!(a.len(), 0);
1477 /// a.insert(1, "a");
1478 /// assert_eq!(a.len(), 1);
1479 /// ```
1480 #[stable(feature = "rust1", since = "1.0.0")]
1481 pub fn len(&self) -> usize {
1482 self.length
1483 }
1484
1485 /// Returns true if the map contains no elements.
1486 ///
1487 /// # Examples
1488 ///
1489 /// Basic usage:
1490 ///
1491 /// ```
1492 /// use std::collections::BTreeMap;
1493 ///
1494 /// let mut a = BTreeMap::new();
1495 /// assert!(a.is_empty());
1496 /// a.insert(1, "a");
1497 /// assert!(!a.is_empty());
1498 /// ```
1499 #[stable(feature = "rust1", since = "1.0.0")]
1500 pub fn is_empty(&self) -> bool {
1501 self.len() == 0
1502 }
1503 }
1504
1505 impl<'a, K: Ord, V> Entry<'a, K, V> {
1506 /// Ensures a value is in the entry by inserting the default if empty, and returns
1507 /// a mutable reference to the value in the entry.
1508 #[stable(feature = "rust1", since = "1.0.0")]
1509 pub fn or_insert(self, default: V) -> &'a mut V {
1510 match self {
1511 Occupied(entry) => entry.into_mut(),
1512 Vacant(entry) => entry.insert(default),
1513 }
1514 }
1515
1516 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1517 /// and returns a mutable reference to the value in the entry.
1518 #[stable(feature = "rust1", since = "1.0.0")]
1519 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1520 match self {
1521 Occupied(entry) => entry.into_mut(),
1522 Vacant(entry) => entry.insert(default()),
1523 }
1524 }
1525 }
1526
1527 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
1528 /// Gets a reference to the key that would be used when inserting a value
1529 /// through the VacantEntry.
1530 #[unstable(feature = "map_entry_keys", issue = "32281")]
1531 pub fn key(&self) -> &K {
1532 &self.key
1533 }
1534
1535 /// Sets the value of the entry with the VacantEntry's key,
1536 /// and returns a mutable reference to it.
1537 #[stable(feature = "rust1", since = "1.0.0")]
1538 pub fn insert(self, value: V) -> &'a mut V {
1539 *self.length += 1;
1540
1541 let out_ptr;
1542
1543 let mut ins_k;
1544 let mut ins_v;
1545 let mut ins_edge;
1546
1547 let mut cur_parent = match self.handle.insert(self.key, value) {
1548 (Fit(handle), _) => return handle.into_kv_mut().1,
1549 (Split(left, k, v, right), ptr) => {
1550 ins_k = k;
1551 ins_v = v;
1552 ins_edge = right;
1553 out_ptr = ptr;
1554 left.ascend().map_err(|n| n.into_root_mut())
1555 }
1556 };
1557
1558 loop {
1559 match cur_parent {
1560 Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
1561 Fit(_) => return unsafe { &mut *out_ptr },
1562 Split(left, k, v, right) => {
1563 ins_k = k;
1564 ins_v = v;
1565 ins_edge = right;
1566 cur_parent = left.ascend().map_err(|n| n.into_root_mut());
1567 }
1568 },
1569 Err(root) => {
1570 root.push_level().push(ins_k, ins_v, ins_edge);
1571 return unsafe { &mut *out_ptr };
1572 }
1573 }
1574 }
1575 }
1576 }
1577
1578 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
1579 /// Gets a reference to the key in the entry.
1580 #[unstable(feature = "map_entry_keys", issue = "32281")]
1581 pub fn key(&self) -> &K {
1582 self.handle.reborrow().into_kv().0
1583 }
1584
1585 /// Gets a reference to the value in the entry.
1586 #[stable(feature = "rust1", since = "1.0.0")]
1587 pub fn get(&self) -> &V {
1588 self.handle.reborrow().into_kv().1
1589 }
1590
1591 /// Gets a mutable reference to the value in the entry.
1592 #[stable(feature = "rust1", since = "1.0.0")]
1593 pub fn get_mut(&mut self) -> &mut V {
1594 self.handle.kv_mut().1
1595 }
1596
1597 /// Converts the entry into a mutable reference to its value.
1598 #[stable(feature = "rust1", since = "1.0.0")]
1599 pub fn into_mut(self) -> &'a mut V {
1600 self.handle.into_kv_mut().1
1601 }
1602
1603 /// Sets the value of the entry with the OccupiedEntry's key,
1604 /// and returns the entry's old value.
1605 #[stable(feature = "rust1", since = "1.0.0")]
1606 pub fn insert(&mut self, value: V) -> V {
1607 mem::replace(self.get_mut(), value)
1608 }
1609
1610 /// Takes the value of the entry out of the map, and returns it.
1611 #[stable(feature = "rust1", since = "1.0.0")]
1612 pub fn remove(self) -> V {
1613 self.remove_kv().1
1614 }
1615
1616 fn remove_kv(self) -> (K, V) {
1617 *self.length -= 1;
1618
1619 let (small_leaf, old_key, old_val) = match self.handle.force() {
1620 Leaf(leaf) => {
1621 let (hole, old_key, old_val) = leaf.remove();
1622 (hole.into_node(), old_key, old_val)
1623 },
1624 Internal(mut internal) => {
1625 let key_loc = internal.kv_mut().0 as *mut K;
1626 let val_loc = internal.kv_mut().1 as *mut V;
1627
1628 let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
1629 let to_remove = unsafe { unwrap_unchecked(to_remove) };
1630
1631 let (hole, key, val) = to_remove.remove();
1632
1633 let old_key = unsafe {
1634 mem::replace(&mut *key_loc, key)
1635 };
1636 let old_val = unsafe {
1637 mem::replace(&mut *val_loc, val)
1638 };
1639
1640 (hole.into_node(), old_key, old_val)
1641 }
1642 };
1643
1644 // Handle underflow
1645 let mut cur_node = small_leaf.forget_type();
1646 while cur_node.len() < node::CAPACITY / 2 {
1647 match handle_underfull_node(cur_node) {
1648 AtRoot => break,
1649 EmptyParent(_) => unreachable!(),
1650 Merged(parent) => if parent.len() == 0 {
1651 // We must be at the root
1652 parent.into_root_mut().pop_level();
1653 break;
1654 } else {
1655 cur_node = parent.forget_type();
1656 },
1657 Stole(_) => break
1658 }
1659 }
1660
1661 (old_key, old_val)
1662 }
1663 }
1664
1665 enum UnderflowResult<'a, K, V> {
1666 AtRoot,
1667 EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1668 Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
1669 Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
1670 }
1671
1672 fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
1673 K, V,
1674 marker::LeafOrInternal>)
1675 -> UnderflowResult<'a, K, V> {
1676 let parent = if let Ok(parent) = node.ascend() {
1677 parent
1678 } else {
1679 return AtRoot;
1680 };
1681
1682 let (is_left, mut handle) = match parent.left_kv() {
1683 Ok(left) => (true, left),
1684 Err(parent) => match parent.right_kv() {
1685 Ok(right) => (false, right),
1686 Err(parent) => {
1687 return EmptyParent(parent.into_node());
1688 }
1689 }
1690 };
1691
1692 if handle.can_merge() {
1693 return Merged(handle.merge().into_node());
1694 } else {
1695 unsafe {
1696 let (k, v, edge) = if is_left {
1697 handle.reborrow_mut().left_edge().descend().pop()
1698 } else {
1699 handle.reborrow_mut().right_edge().descend().pop_front()
1700 };
1701
1702 let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
1703 let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
1704
1705 // FIXME: reuse cur_node?
1706 if is_left {
1707 match handle.reborrow_mut().right_edge().descend().force() {
1708 Leaf(mut leaf) => leaf.push_front(k, v),
1709 Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
1710 }
1711 } else {
1712 match handle.reborrow_mut().left_edge().descend().force() {
1713 Leaf(mut leaf) => leaf.push(k, v),
1714 Internal(mut internal) => internal.push(k, v, edge.unwrap())
1715 }
1716 }
1717 }
1718
1719 return Stole(handle.into_node());
1720 }
1721 }