Lines Matching defs:map
971 .map(|(idx, e)| idx as $type ^ e)
1009 .map(|(idx, e)| idx.wrapping_add(e))
1030 .map(|(i, (d, s))| d.wrapping_add(i as u8) ^ s)
1053 input.into_iter().map(|e| unsafe { std::mem::transmute_copy(&e) }).collect()
1085 .map(|(i, e)| Droppable(i ^ e.0))
1120 b.iter(|| (0..LEN).map(|_| u32::default()).collect::<Vec<_>>());
1168 v.extend(data.iter().map(|t| t.1));
1304 ($name: ident, $n: expr, $map: ident) => {
1308 let mut map = $map::new();
1314 map.insert(i, i);
1320 map.insert(k, k);
1321 map.remove(&k);
1323 black_box(map);
1329 ($name: ident, $n: expr, $map: ident) => {
1332 let mut map = $map::new();
1336 map.insert(i * 2, i * 2);
1342 map.insert(i, i);
1343 map.remove(&i);
1346 black_box(map);
1352 ($name: ident, $n: expr, $map: ident) => {
1355 let mut map = $map::new();
1360 let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
1363 map.insert(k, k);
1371 let t = map.get(&keys[i]);
1380 ($name: ident, $n: expr, $map: ident) => {
1383 let mut map = $map::new();
1388 map.insert(i, i);
1394 let x = map.get(&i);
1415 let mut map = BTreeMap::<i32, i32>::new();
1419 map.insert(rng.gen(), rng.gen());
1423 for entry in &map {
1445 let mut map = BTreeMap::<i32, i32>::new();
1449 map.insert(rng.gen(), rng.gen());
1453 for kv in map.iter_mut() {
1475 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
1478 black_box(map.first_key_value());
1479 black_box(map.last_key_value());
1507 let map: BTreeMap<_, _> = (0..BENCH_RANGE_SIZE).map(|i| (i, i)).collect();
1512 black_box(map.range(f(i, j)));
1541 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
1544 black_box(map.iter());
1582 // The returned map has small keys and values.
1585 (0..n).map(|i| (i, i)).collect::<BTreeMap<_, _>>()
1588 // The returned map has small keys and large values.
1590 (0..n).map(|i| (i, [i; FAT])).collect::<BTreeMap<_, _>>()
1615 let mut map = src.clone();
1616 assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
1617 assert_eq!(map.len(), 100 / 2);
1631 let mut map = src.clone();
1632 while map.pop_first().is_some() {}
1633 map
1641 let mut map = src.clone();
1642 while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
1643 let v = map.remove(&elt);
1646 map
1654 let mut map = src.clone();
1656 let v = map.remove(&i);
1659 assert_eq!(map.len(), 100 / 2);
1660 map
1686 let mut map = src.clone();
1687 assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2);
1688 assert_eq!(map.len(), 10_000 / 2);
1702 let mut map = src.clone();
1703 while map.pop_first().is_some() {}
1704 map
1712 let mut map = src.clone();
1713 while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
1714 let v = map.remove(&elt);
1717 map
1725 let mut map = src.clone();
1727 let v = map.remove(&i);
1730 assert_eq!(map.len(), 10_000 / 2);
1731 map
1757 let mut map = src.clone();
1758 assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
1759 assert_eq!(map.len(), 100 / 2);
1773 let mut map = src.clone();
1774 while map.pop_first().is_some() {}
1775 map
1783 let mut map = src.clone();
1784 while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
1785 let v = map.remove(&elt);
1788 map
1796 let mut map = src.clone();
1798 let v = map.remove(&i);
1801 assert_eq!(map.len(), 100 / 2);
1802 map
2029 mod map;
2042 let v: Vec<_> = (0..100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect();
2071 let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
2079 let xss: Vec<Vec<i32>> = (0..100).map(|i| (0..i).collect()).collect();
2261 (&mut rng).sample_iter(&Standard).map(|x| [x; 16]).take(len).collect()
2280 let v = v.iter().map(|s| &**s).collect::<Vec<&str>>();
2358 let mut v: Vec<_> = (0..1 + (n / mem::size_of::<$ty>() as u64)).map($f).collect();
3401 let iter = (0..SHARED_ITER_MAX).filter(|x| x % 2 == 0).map(Box::new);
3422 let iter = (0..SHARED_ITER_MAX).map(Box::new);
3441 let iter = (0..SHARED_ITER_MAX).map(drop);
3459 let iter = (0..SHARED_ITER_MAX).map(|val| match val {
3577 for j in string[ip..].char_indices().map(|(i, _)| i).chain(Some(string.len() - ip)) {
4954 v.iter().map(|x| x.len()).sum()
5646 assert_eq!(owned.as_ref().map(|s| &**s), Some("string"));
6822 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
6839 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
6864 let v = (0..5).map(|x| Rc::new(x)).collect::<Vec<_>>();
6866 let mut v = v.iter().map(|r| Wrap(r.clone())).collect::<Vec<_>>();
7199 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
7203 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
7218 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
7222 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
7226 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
7230 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
7530 .map(|i| i.0 + i.1)
7532 .map(|(a, b)| a + b)
7536 .map(|e| if e != usize::MAX { Ok(std::num::NonZeroUsize::new(e)) } else { Err(()) });
7545 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
7560 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
7577 drop_count.iter().map(Rc::strong_count).all(|count| count == 1),
7860 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
7912 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
8741 let iter = (0..8).map(move |bit| (x >> bit) & 1 == 1);
9154 let iter = (0..SHARED_ITER_MAX).filter(|x| x % 2 == 0).map(Box::new);
9175 let iter = (0..SHARED_ITER_MAX).map(Box::new);
9194 let iter = (0..SHARED_ITER_MAX).map(drop);
9212 let iter = (0..SHARED_ITER_MAX).map(|val| match val {
9270 let mut v: Vec<_> = (0..3).map(square).collect();
9280 v = (0..5).map(square).collect();
9645 rng.sample_iter::<i32, _>(&Standard).map(|x| x % modulus).take(len).collect();
9727 .map(|_| {
10558 v.get_mut(1).map(|e| *e = 7);
10713 let sink: Box<_> = src.into_vec().into_iter().map(std::convert::identity).collect();
10988 .map(|id| DropCounter {
11528 assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), vec![4, 3, 2]);
13519 let heap: BinaryHeap<_> = src.into_iter().map(std::convert::identity).collect();
13522 let sink: Vec<_> = heap.into_iter().map(std::convert::identity).collect();
13739 data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect();
13766 let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
13799 for size in (0..8).map(|i| 2usize.pow(i)) {
13816 for size in (0..8).map(|i| 2usize.pow(i)) {
13852 .map(|_| {
15133 slice.iter().map(|s| s.borrow().as_ref().len()).try_fold(n, usize::checked_add)
15668 assert_eq!(Arc::try_unwrap(x).map(|x| *x), Ok("hello"));
15708 assert_eq!(Arc::try_unwrap(x).map(|x| *x), Ok("hello"));
16803 decode_utf16(v.iter().cloned()).map(|r| r.unwrap_or(REPLACEMENT_CHARACTER)).collect()
21682 .map(|inner| {
22371 $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
22703 let size = slice.iter().map(|slice| slice.borrow().len()).sum();
22722 let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
22745 slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
25127 .map(|inner| {
26550 assert_eq!(Rc::try_unwrap(x).map(|x| *x), Ok("hello"));
26590 assert_eq!(Rc::try_unwrap(x).map(|x| *x), Ok("hello"));
27102 self.head.map(|node| unsafe {
27143 self.tail.map(|node| unsafe {
27616 unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
27642 unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
27662 unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
27688 unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
27734 self.pop_front_node().map(Node::into_element)
27774 self.pop_back_node().map(Node::into_element)
27949 self.head.map(|node| unsafe {
27977 self.tail.map(|node| unsafe {
28003 self.head.map(|node| unsafe {
28031 self.tail.map(|node| unsafe {
28164 unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
28179 next.map(|next| &(*next.as_ptr()).element)
28195 prev.map(|prev| &(*prev.as_ptr()).element)
28261 unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
28276 next.map(|next| &mut (*next.as_ptr()).element)
28292 prev.map(|prev| &mut (*prev.as_ptr()).element)
29265 // Increment length every iteration, to make sure the map drops
29821 // An empty map may be represented both by the absence of a root node or by a
29824 /// A map based on a [B-Tree].
29828 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
29852 /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
30042 let (map, dormant_map) = DormantMutRef::new(self);
30043 let root_node = map.root.as_mut()?.borrow_mut();
30053 let (map, dormant_map) = DormantMutRef::new(self);
30054 let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut();
30183 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
30201 f.debug_list().entries(self.inner.iter().map(|(key, _)| key)).finish()
30219 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
30275 /// let mut map = BTreeMap::new();
30277 /// // entries can now be inserted into the empty map
30278 /// map.insert(1, "a");
30289 /// Clears the map, removing all elements.
30310 /// The key may be any borrowed form of the map's key type, but the ordering
30320 /// let mut map = BTreeMap::new();
30321 /// map.insert(1, "a");
30322 /// assert_eq!(map.get(&1), Some(&"a"));
30323 /// assert_eq!(map.get(&2), None);
30340 /// The supplied key may be any borrowed form of the map's key type, but the ordering
30348 /// let mut map = BTreeMap::new();
30349 /// map.insert(1, "a");
30350 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
30351 /// assert_eq!(map.get_key_value(&2), None);
30366 /// Returns the first key-value pair in the map.
30367 /// The key in this pair is the minimum key in the map.
30377 /// let mut map = BTreeMap::new();
30378 /// assert_eq!(map.first_key_value(), None);
30379 /// map.insert(1, "b");
30380 /// map.insert(2, "a");
30381 /// assert_eq!(map.first_key_value(), Some((&1, &"b")));
30389 root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv)
30392 /// Returns the first entry in the map for in-place manipulation.
30393 /// The key of this entry is the minimum key in the map.
30401 /// let mut map = BTreeMap::new();
30402 /// map.insert(1, "a");
30403 /// map.insert(2, "b");
30404 /// if let Some(mut entry) = map.first_entry() {
30409 /// assert_eq!(*map.get(&1).unwrap(), "first");
30410 /// assert_eq!(*map.get(&2).unwrap(), "b");
30417 let (map, dormant_map) = DormantMutRef::new(self);
30418 let root_node = map.root.as_mut()?.borrow_mut();
30423 /// Removes and returns the first element in the map.
30424 /// The key of this element is the minimum key that was in the map.
30428 /// Draining elements in ascending order, while keeping a usable map each iteration.
30434 /// let mut map = BTreeMap::new();
30435 /// map.insert(1, "a");
30436 /// map.insert(2, "b");
30437 /// while let Some((key, _val)) = map.pop_first() {
30438 /// assert!(map.iter().all(|(k, _v)| *k > key));
30440 /// assert!(map.is_empty());
30447 self.first_entry().map(|entry| entry.remove_entry())
30450 /// Returns the last key-value pair in the map.
30451 /// The key in this pair is the maximum key in the map.
30461 /// let mut map = BTreeMap::new();
30462 /// map.insert(1, "b");
30463 /// map.insert(2, "a");
30464 /// assert_eq!(map.last_key_value(), Some((&2, &"a")));
30472 root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv)
30475 /// Returns the last entry in the map for in-place manipulation.
30476 /// The key of this entry is the maximum key in the map.
30484 /// let mut map = BTreeMap::new();
30485 /// map.insert(1, "a");
30486 /// map.insert(2, "b");
30487 /// if let Some(mut entry) = map.last_entry() {
30492 /// assert_eq!(*map.get(&1).unwrap(), "a");
30493 /// assert_eq!(*map.get(&2).unwrap(), "last");
30500 let (map, dormant_map) = DormantMutRef::new(self);
30501 let root_node = map.root.as_mut()?.borrow_mut();
30506 /// Removes and returns the last element in the map.
30507 /// The key of this element is the maximum key that was in the map.
30511 /// Draining elements in descending order, while keeping a usable map each iteration.
30517 /// let mut map = BTreeMap::new();
30518 /// map.insert(1, "a");
30519 /// map.insert(2, "b");
30520 /// while let Some((key, _val)) = map.pop_last() {
30521 /// assert!(map.iter().all(|(k, _v)| *k < key));
30523 /// assert!(map.is_empty());
30530 self.last_entry().map(|entry| entry.remove_entry())
30533 /// Returns `true` if the map contains a value for the specified key.
30535 /// The key may be any borrowed form of the map's key type, but the ordering
30545 /// let mut map = BTreeMap::new();
30546 /// map.insert(1, "a");
30547 /// assert_eq!(map.contains_key(&1), true);
30548 /// assert_eq!(map.contains_key(&2), false);
30561 /// The key may be any borrowed form of the map's key type, but the ordering
30571 /// let mut map = BTreeMap::new();
30572 /// map.insert(1, "a");
30573 /// if let Some(x) = map.get_mut(&1) {
30576 /// assert_eq!(map[&1], "b");
30592 /// Inserts a key-value pair into the map.
30594 /// If the map did not have this key present, `None` is returned.
30596 /// If the map did have this key present, the value is updated, and the old
30610 /// let mut map = BTreeMap::new();
30611 /// assert_eq!(map.insert(37, "a"), None);
30612 /// assert_eq!(map.is_empty(), false);
30614 /// map.insert(37, "b");
30615 /// assert_eq!(map.insert(37, "c"), Some("b"));
30616 /// assert_eq!(map[&37], "c");
30632 /// Tries to insert a key-value pair into the map, and returns
30635 /// If the map already had this key present, nothing is updated, and
30647 /// let mut map = BTreeMap::new();
30648 /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
30650 /// let err = map.try_insert(37, "b").unwrap_err();
30666 /// Removes a key from the map, returning the value at the key if the key
30667 /// was previously in the map.
30669 /// The key may be any borrowed form of the map's key type, but the ordering
30679 /// let mut map = BTreeMap::new();
30680 /// map.insert(1, "a");
30681 /// assert_eq!(map.remove(&1), Some("a"));
30682 /// assert_eq!(map.remove(&1), None);
30691 self.remove_entry(key).map(|(_, v)| v)
30694 /// Removes a key from the map, returning the stored key and value if the key
30695 /// was previously in the map.
30697 /// The key may be any borrowed form of the map's key type, but the ordering
30707 /// let mut map = BTreeMap::new();
30708 /// map.insert(1, "a");
30709 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
30710 /// assert_eq!(map.remove_entry(&1), None);
30718 let (map, dormant_map) = DormantMutRef::new(self);
30719 let root_node = map.root.as_mut()?.borrow_mut();
30737 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
30739 /// map.retain(|&k, _| k % 2 == 0);
30740 /// assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
30802 /// Constructs a double-ended iterator over a sub-range of elements in the map.
30822 /// let mut map = BTreeMap::new();
30823 /// map.insert(3, "a");
30824 /// map.insert(5, "b");
30825 /// map.insert(8, "c");
30826 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
30829 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
30845 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
30864 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"]
30866 /// .map(|&s| (s, 0))
30868 /// for (_, balance) in map.range_mut("B".."Cheryl") {
30871 /// for (name, balance) in &map {
30889 /// Gets the given key's corresponding entry in the map for in-place manipulation.
30913 let (map, dormant_map) = DormantMutRef::new(self);
30914 let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut();
30975 /// the map and yielded. If the closure returns `false`, or panics, the
30976 /// element remains in the map and will not be yielded.
30992 /// Splitting a map into even and odd keys, reusing the original map:
30998 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
30999 /// let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect();
31000 /// let odds = map;
31031 /// The map cannot be used after calling this.
31054 /// The map cannot be used after calling this.
31318 self.inner.next().map(|(k, _)| k)
31341 self.inner.next_back().map(|(k, _)| k)
31367 self.inner.next().map(|(_, v)| v)
31382 self.inner.next_back().map(|(_, v)| v)
31417 /// Reference to the length field in the borrowed map, updated live.
31419 /// Buried reference to the root field in the borrowed map.
31423 /// Empty if the map has no root, if iteration went beyond the last leaf edge,
31470 edge.reborrow().next_kv().ok().map(Handle::into_kv)
31536 self.inner.next().map(|(_, v)| v)
31551 self.inner.next_back().map(|(_, v)| v)
31576 self.inner.next().map(|(k, _)| k)
31599 self.inner.next_back().map(|(k, _)| k)
31618 self.inner.next().map(|(_, v)| v)
31633 self.inner.next_back().map(|(_, v)| v)
31722 let mut map = BTreeMap::new();
31723 map.extend(iter);
31724 map
31746 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
31825 /// Gets an iterator over the entries of the map, sorted by key.
31834 /// let mut map = BTreeMap::new();
31835 /// map.insert(3, "c");
31836 /// map.insert(2, "b");
31837 /// map.insert(1, "a");
31839 /// for (key, value) in map.iter() {
31843 /// let (first_key, first_value) = map.iter().next().unwrap();
31857 /// Gets a mutable iterator over the entries of the map, sorted by key.
31866 /// let mut map = BTreeMap::new();
31867 /// map.insert("a", 1);
31868 /// map.insert("b", 2);
31869 /// map.insert("c", 3);
31872 /// for (key, value) in map.iter_mut() {
31895 /// Gets an iterator over the keys of the map, in sorted order.
31916 /// Gets an iterator over the values of the map, in order by key.
31937 /// Gets a mutable iterator over the values of the map, in order by key.
31963 /// Returns the number of elements in the map.
31984 /// Returns `true` if the map contains no elements.
32177 use super::map::{BTreeMap, Keys};
32232 map: BTreeMap<T, ()>,
32238 BTreeSet { map: self.map.clone() }
32242 self.map.clone_from(&other.map);
32273 iter: super::map::IntoIter<T, ()>,
32285 iter: super::map::Range<'a, T, ()>,
32411 BTreeSet { map: BTreeMap::new() }
32443 Range { iter: self.map.range(range) }
32628 self.map.clear()
32652 self.map.contains_key(value)
32676 Recover::get(&self.map, value)
32831 self.map.first_key_value().map(|(k, _)| k)
32857 self.map.last_key_value().map(|(k, _)| k)
32882 self.map.pop_first().map(|kv| kv.0)
32907 self.map.pop_last().map(|kv| kv.0)
32935 self.map.insert(value, ()).is_none()
32958 Recover::replace(&mut self.map, value)
32986 self.map.remove(value).is_some()
33010 Recover::take(&mut self.map, value)
33070 self.map.append(&mut other.map);
33107 BTreeSet { map: self.map.split_off(key) }
33143 DrainFilter { pred, inner: self.map.drain_filter_inner() }
33175 Iter { iter: self.map.keys() }
33194 self.map.len()
33243 IntoIter { iter: self.map.into_iter() }
33265 inner: super::map::DrainFilterInner<'a, T, ()>,
33285 f.debug_tuple("DrainFilter").field(&self.inner.peek().map(|(k, _)| k)).finish()
33299 self.inner.next(&mut mapped_pred).map(|(k, _)| k)
33495 self.iter.next().map(|(k, _)| k)
33505 self.iter.next_back().map(|(k, _)| k)
33530 self.iter.next().map(|(k, _)| k)
33549 self.iter.next_back().map(|(k, _)| k)
33772 front: self.front.as_ref().map(|f| f.reborrow()),
33773 back: self.back.as_ref().map(|b| b.reborrow()),
34266 pub mod map;
34981 // Unlike the function with the same name in map/tests, returns no values.
34986 Vec::from_iter((0..len).map(|_| rng.next()))
35056 /// A view into a single entry in a map, which may either be vacant or occupied.
35124 /// The entry in the map that was already occupied.
35163 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35164 /// map.entry("poneyland").or_insert(12);
35166 /// assert_eq!(map["poneyland"], 12);
35184 /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
35187 /// map.entry("poneyland").or_insert_with(|| s);
35189 /// assert_eq!(map["poneyland"], "hoho".to_string());
35211 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35213 /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
35215 /// assert_eq!(map["poneyland"], 9);
35236 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35237 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
35248 /// potential inserts into the map.
35255 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35257 /// map.entry("poneyland")
35260 /// assert_eq!(map["poneyland"], 42);
35262 /// map.entry("poneyland")
35265 /// assert_eq!(map["poneyland"], 43);
35292 /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
35293 /// map.entry("poneyland").or_default();
35295 /// assert_eq!(map["poneyland"], None);
35314 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35315 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
35330 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35332 /// if let Entry::Vacant(v) = map.entry("poneyland") {
35350 /// let mut map: BTreeMap<&str, u32> = BTreeMap::new();
35352 /// if let Entry::Vacant(o) = map.entry("poneyland") {
35355 /// assert_eq!(map["poneyland"], 37);
35362 let map = unsafe { self.dormant_map.awaken() };
35363 map.length += 1;
35369 let map = unsafe { self.dormant_map.awaken() };
35370 let root = map.root.as_mut().unwrap();
35372 map.length += 1;
35390 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35391 /// map.entry("poneyland").or_insert(12);
35392 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
35399 /// Take ownership of the key and value from the map.
35407 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35408 /// map.entry("poneyland").or_insert(12);
35410 /// if let Entry::Occupied(o) = map.entry("poneyland") {
35411 /// // We delete the entry from the map.
35416 /// // println!("{}", map["poneyland"]);
35431 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35432 /// map.entry("poneyland").or_insert(12);
35434 /// if let Entry::Occupied(o) = map.entry("poneyland") {
35456 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35457 /// map.entry("poneyland").or_insert(12);
35459 /// assert_eq!(map["poneyland"], 12);
35460 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
35467 /// assert_eq!(map["poneyland"], 24);
35486 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35487 /// map.entry("poneyland").or_insert(12);
35489 /// assert_eq!(map["poneyland"], 12);
35490 /// if let Entry::Occupied(o) = map.entry("poneyland") {
35493 /// assert_eq!(map["poneyland"], 22);
35509 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35510 /// map.entry("poneyland").or_insert(12);
35512 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
35515 /// assert_eq!(map["poneyland"], 15);
35522 /// Takes the value of the entry out of the map, and returns it.
35530 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
35531 /// map.entry("poneyland").or_insert(12);
35533 /// if let Entry::Occupied(o) = map.entry("poneyland") {
35537 /// // println!("{}", map["poneyland"]);
35549 let map = unsafe { self.dormant_map.awaken() };
35550 map.length -= 1;
35552 let root = map.root.as_mut().unwrap();
35606 // Panics if the map (or the code navigating it) is corrupted.
35629 // Panics if the map is corrupted or if the keys are not in strictly
35643 self.root.as_ref().map(node::Root::height)
35701 let mut map = BTreeMap::new();
35702 map.check();
35703 assert_eq!(map.height(), None);
35704 assert_eq!(map.len(), 0);
35706 map.insert(0, ());
35707 while map.height() == Some(0) {
35708 let last_key = *map.last_key_value().unwrap().0;
35709 map.insert(last_key + 1, ());
35711 map.check();
35716 assert_eq!(map.height(), Some(1));
35717 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1, "{}", map.dump_keys());
35719 while map.height() == Some(1) {
35720 let last_key = *map.last_key_value().unwrap().0;
35721 map.insert(last_key + 1, ());
35723 map.check();
35731 assert_eq!(map.height(), Some(2));
35732 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2, "{}", map.dump_keys());
35740 let map: BTreeMap<_, _> = (0..2).map(|i| (Governed(i, &gov), ())).collect();
35742 map.check();
35749 let map: BTreeMap<_, _> = (0..2).map(|i| (Governed(i, &gov), ())).collect();
35751 map.check_invariants();
35756 let mut map = BTreeMap::new();
35760 assert_eq!(map.len(), 0);
35763 assert_eq!(map.insert(i, 10 * i), None);
35764 assert_eq!(map.len(), i + 1);
35767 assert_eq!(map.first_key_value(), Some((&0, &0)));
35768 assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1)))));
35769 assert_eq!(map.first_entry().unwrap().key(), &0);
35770 assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
35773 assert_eq!(map.get(&i).unwrap(), &(i * 10));
35777 assert_eq!(map.get(&i), None);
35781 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
35782 assert_eq!(map.len(), size);
35786 assert_eq!(map.get(&i).unwrap(), &(i * 100));
35790 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
35791 assert_eq!(map.len(), size - i - 1);
35795 assert_eq!(map.get(&(2 * i)), None);
35796 assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
35800 assert_eq!(map.remove(&(2 * i)), None);
35801 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
35802 assert_eq!(map.len(), size / 2 - i - 1);
35804 map.check();
35809 let mut map = BTreeMap::new();
35811 assert_eq!(map.remove(&1), None);
35812 assert_eq!(map.len(), 0);
35813 assert_eq!(map.get(&1), None);
35814 assert_eq!(map.get_mut(&1), None);
35815 assert_eq!(map.first_key_value(), None);
35816 assert_eq!(map.last_key_value(), None);
35817 assert_eq!(map.keys().count(), 0);
35818 assert_eq!(map.values().count(), 0);
35819 assert_eq!(map.range(..).next(), None);
35820 assert_eq!(map.range(..1).next(), None);
35821 assert_eq!(map.range(1..).next(), None);
35822 assert_eq!(map.range(1..=1).next(), None);
35823 assert_eq!(map.range(1..2).next(), None);
35824 assert_eq!(map.height(), None);
35825 assert_eq!(map.insert(1, 1), None);
35826 assert_eq!(map.height(), Some(0));
35827 map.check();
35830 assert_eq!(map.len(), 1);
35831 assert_eq!(map.get(&1), Some(&1));
35832 assert_eq!(map.get_mut(&1), Some(&mut 1));
35833 assert_eq!(map.first_key_value(), Some((&1, &1)));
35834 assert_eq!(map.last_key_value(), Some((&1, &1)));
35835 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
35836 assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]);
35837 assert_eq!(map.insert(1, 2), Some(1));
35838 assert_eq!(map.len(), 1);
35839 assert_eq!(map.get(&1), Some(&2));
35840 assert_eq!(map.get_mut(&1), Some(&mut 2));
35841 assert_eq!(map.first_key_value(), Some((&1, &2)));
35842 assert_eq!(map.last_key_value(), Some((&1, &2)));
35843 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]);
35844 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]);
35845 assert_eq!(map.insert(2, 4), None);
35846 assert_eq!(map.height(), Some(0));
35847 map.check();
35850 assert_eq!(map.len(), 2);
35851 assert_eq!(map.get(&2), Some(&4));
35852 assert_eq!(map.get_mut(&2), Some(&mut 4));
35853 assert_eq!(map.first_key_value(), Some((&1, &2)));
35854 assert_eq!(map.last_key_value(), Some((&2, &4)));
35855 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]);
35856 assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]);
35857 assert_eq!(map.remove(&1), Some(2));
35858 assert_eq!(map.height(), Some(0));
35859 map.check();
35862 assert_eq!(map.len(), 1);
35863 assert_eq!(map.get(&1), None);
35864 assert_eq!(map.get_mut(&1), None);
35865 assert_eq!(map.get(&2), Some(&4));
35866 assert_eq!(map.get_mut(&2), Some(&mut 4));
35867 assert_eq!(map.first_key_value(), Some((&2, &4)));
35868 assert_eq!(map.last_key_value(), Some((&2, &4)));
35869 assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]);
35870 assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]);
35871 assert_eq!(map.remove(&2), Some(4));
35872 assert_eq!(map.height(), Some(0));
35873 map.check();
35876 assert_eq!(map.len(), 0);
35877 assert_eq!(map.get(&1), None);
35878 assert_eq!(map.get_mut(&1), None);
35879 assert_eq!(map.first_key_value(), None);
35880 assert_eq!(map.last_key_value(), None);
35881 assert_eq!(map.keys().count(), 0);
35882 assert_eq!(map.values().count(), 0);
35883 assert_eq!(map.range(..).next(), None);
35884 assert_eq!(map.range(..1).next(), None);
35885 assert_eq!(map.range(1..).next(), None);
35886 assert_eq!(map.range(1..=1).next(), None);
35887 assert_eq!(map.range(1..2).next(), None);
35888 assert_eq!(map.remove(&1), None);
35889 assert_eq!(map.height(), Some(0));
35890 map.check();
35898 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
35911 test(size, map.iter().map(|(&k, &v)| (k, v)));
35912 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
35913 test(size, map.into_iter());
35921 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
35934 test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
35935 test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
35936 test(size, map.into_iter().rev());
35946 let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect();
35949 assert_eq!(map.iter_mut().count(), size);
35950 assert_eq!(map.iter_mut().rev().count(), size);
35953 for (i, (k, v)) in map.iter_mut().enumerate() {
35960 for (i, (k, v)) in map.iter_mut().rev().enumerate() {
35967 for (i, (k, v)) in map.iter_mut().enumerate() {
35971 map.check();
36012 let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
36034 let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect();
36035 let mut it = map.iter_mut();
36046 map.check();
36051 let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect();
36052 let mut it = map.iter_mut();
36061 map.check();
36069 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
36087 test(size, map.iter().map(|(&k, &v)| (k, v)));
36088 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
36089 test(size, map.into_iter());
36128 fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> {
36129 map.range(range)
36130 .map(|(&k, &v)| {
36141 let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
36145 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
36146 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
36147 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
36148 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
36149 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
36150 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
36151 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
36152 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
36153 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
36154 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
36155 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
36156 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
36157 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
36158 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
36159 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
36160 assert_eq!(range_keys(&map, ..), all);
36162 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
36163 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
36164 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
36165 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
36166 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
36167 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
36168 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
36169 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
36170 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
36171 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
36172 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
36173 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
36174 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
36175 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
36176 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
36177 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
36178 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
36179 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
36180 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
36181 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
36182 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
36183 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
36184 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
36185 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
36186 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
36187 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
36188 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
36189 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
36191 assert_eq!(range_keys(&map, ..3), vec![1, 2]);
36192 assert_eq!(range_keys(&map, 3..), vec![3, 4]);
36193 assert_eq!(range_keys(&map, 2..=3), vec![2, 3]);
36201 let map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect();
36204 assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
36205 assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
36206 assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
36207 assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
36209 assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
36210 assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
36211 assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
36212 assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
36220 let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect();
36224 assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all);
36225 assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all);
36226 assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all);
36227 assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all);
36228 assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all);
36229 assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all);
36230 assert_eq!(range_keys(&map, (Included(0), Included(size))), all);
36231 assert_eq!(range_keys(&map, (Included(0), Unbounded)), all);
36232 assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all);
36233 assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all);
36234 assert_eq!(range_keys(&map, (Included(1), Included(size))), all);
36235 assert_eq!(range_keys(&map, (Included(1), Unbounded)), all);
36236 assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all);
36237 assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all);
36238 assert_eq!(range_keys(&map, (Unbounded, Included(size))), all);
36239 assert_eq!(range_keys(&map, ..), all);
36241 assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]);
36242 assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]);
36243 assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]);
36244 assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]);
36245 assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]);
36246 assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]);
36247 assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first);
36248 assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first);
36249 assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first);
36250 assert_eq!(range_keys(&map, (Included(0), Included(1))), first);
36251 assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first);
36252 assert_eq!(range_keys(&map, (Included(1), Included(1))), first);
36253 assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first);
36254 assert_eq!(range_keys(&map, (Unbounded, Included(1))), first);
36255 assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last);
36256 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last);
36257 assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last);
36258 assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last);
36259 assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last);
36260 assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last);
36261 assert_eq!(range_keys(&map, (Included(size), Included(size))), last);
36262 assert_eq!(range_keys(&map, (Included(size), Unbounded)), last);
36263 assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]);
36264 assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]);
36265 assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]);
36266 assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]);
36267 assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]);
36268 assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]);
36280 check(map.range(..=100), map.range(..101));
36281 check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
36282 check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]);
36288 let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
36290 assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]);
36295 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
36296 assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
36297 assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
36303 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
36304 map.range((Excluded(2), Excluded(2)));
36310 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
36311 map.range((Included(3), Included(2)));
36317 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
36318 map.range((Included(3), Excluded(2)));
36324 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
36325 map.range((Excluded(3), Included(2)));
36331 let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
36332 map.range((Excluded(3), Excluded(2)));
36337 let mut map = BTreeMap::new();
36338 map.insert(Cyclic3::B, ());
36343 map.range(Cyclic3::C..=Cyclic3::A);
36383 let map = (0..12).map(|i| (CompositeKey(i, EvilTwin(i)), ())).collect::<BTreeMap<_, _>>();
36384 map.range(EvilTwin(5)..=EvilTwin(7));
36391 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
36393 fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
36394 let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
36395 let mut pairs = (0..size).map(|i| (i, i));
36403 test(&map, size, Included(&0), Excluded(&size));
36404 test(&map, size, Unbounded, Excluded(&size));
36405 test(&map, size, Included(&0), Included(&(size - 1)));
36406 test(&map, size, Unbounded, Included(&(size - 1)));
36407 test(&map, size, Included(&0), Unbounded);
36408 test(&map, size, Unbounded, Unbounded);
36413 let mut map = BTreeMap::new();
36414 map.insert("aardvark".to_string(), 1);
36415 map.insert("baboon".to_string(), 2);
36416 map.insert("coyote".to_string(), 3);
36417 map.insert("dingo".to_string(), 4);
36419 let mut iter = map.range::<str, _>((Included("b"), Excluded("d")));
36430 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
36434 let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
36435 let mut pairs = (i..=j).map(|i| (i, i));
36451 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
36455 let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
36456 let mut pairs = (i..=j).map(|i| (i, i));
36465 map.check();
36470 let mut map: BTreeMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect();
36472 map.retain(|&k, _| k % 2 == 0);
36473 assert_eq!(map.len(), 50);
36474 assert_eq!(map[&2], 20);
36475 assert_eq!(map[&4], 40);
36476 assert_eq!(map[&6], 60);
36484 let mut map: BTreeMap<i32, i32> = BTreeMap::new();
36485 map.drain_filter(|_, _| unreachable!("there's nothing to decide on"));
36486 assert!(map.is_empty());
36487 map.check();
36493 let pairs = (0..3).map(|i| (i, i));
36494 let mut map: BTreeMap<_, _> = pairs.collect();
36495 assert!(map.drain_filter(|_, _| false).eq(iter::empty()));
36496 map.check();
36502 let pairs = (0..3).map(|i| (i, i));
36503 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36504 assert!(map.drain_filter(|_, _| true).eq(pairs));
36505 assert!(map.is_empty());
36506 map.check();
36512 let pairs = (0..3).map(|i| (i, i));
36513 let mut map: BTreeMap<_, _> = pairs.collect();
36515 map.drain_filter(|_, v| {
36521 assert!(map.keys().copied().eq(0..3));
36522 assert!(map.values().copied().eq(6..9));
36523 map.check();
36529 let pairs = (0..3).map(|i| (i, i));
36530 let mut map: BTreeMap<_, _> = pairs.collect();
36532 map.drain_filter(|_, v| {
36536 .eq((0..3).map(|i| (i, i + 6)))
36538 assert!(map.is_empty());
36539 map.check();
36544 let pairs = (0..3).map(|i| (i, i));
36545 let mut map: BTreeMap<_, _> = pairs.collect();
36546 map.drain_filter(|_, _| false);
36547 assert!(map.keys().copied().eq(0..3));
36548 map.check();
36553 let pairs = (0..3).map(|i| (i, i));
36555 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36556 map.drain_filter(|i, _| *i == doomed);
36557 assert_eq!(map.len(), 2);
36558 map.check();
36564 let pairs = (0..3).map(|i| (i, i));
36566 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36567 map.drain_filter(|i, _| *i != sacred);
36568 assert!(map.keys().copied().eq(sacred..=sacred));
36569 map.check();
36575 let pairs = (0..3).map(|i| (i, i));
36576 let mut map: BTreeMap<_, _> = pairs.collect();
36577 map.drain_filter(|_, _| true);
36578 assert!(map.is_empty());
36579 map.check();
36584 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
36585 let mut map: BTreeMap<_, _> = pairs.collect();
36586 map.drain_filter(|_, _| false);
36587 assert!(map.keys().copied().eq(0..NODE_CAPACITY));
36588 map.check();
36593 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
36595 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36596 map.drain_filter(|i, _| *i == doomed);
36597 assert_eq!(map.len(), NODE_CAPACITY - 1);
36598 map.check();
36604 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
36606 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36607 map.drain_filter(|i, _| *i != sacred);
36608 assert!(map.keys().copied().eq(sacred..=sacred));
36609 map.check();
36615 let pairs = (0..NODE_CAPACITY).map(|i| (i, i));
36616 let mut map: BTreeMap<_, _> = pairs.collect();
36617 map.drain_filter(|_, _| true);
36618 assert!(map.is_empty());
36619 map.check();
36624 let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect();
36625 assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8);
36626 assert_eq!(map.len(), 8);
36627 map.check();
36632 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
36633 let mut map: BTreeMap<_, _> = pairs.collect();
36634 map.drain_filter(|_, _| true);
36635 assert!(map.is_empty());
36636 map.check();
36641 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
36643 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36644 map.drain_filter(|i, _| *i == doomed);
36645 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1);
36646 map.check();
36652 let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i));
36654 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36655 map.drain_filter(|i, _| *i != sacred);
36656 assert!(map.keys().copied().eq(sacred..=sacred));
36657 map.check();
36663 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
36665 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36666 map.drain_filter(|i, _| *i == doomed);
36667 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
36668 map.check();
36674 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
36676 let mut map: BTreeMap<_, _> = pairs.clone().collect();
36677 map.drain_filter(|i, _| *i != sacred);
36678 assert!(map.keys().copied().eq(sacred..=sacred));
36679 map.check();
36685 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
36686 let mut map: BTreeMap<_, _> = pairs.collect();
36687 map.drain_filter(|_, _| true);
36688 assert!(map.is_empty());
36689 map.check();
36697 let mut map = BTreeMap::new();
36698 map.insert(a.spawn(Panic::Never), ());
36699 map.insert(b.spawn(Panic::InDrop), ());
36700 map.insert(c.spawn(Panic::Never), ());
36702 catch_unwind(move || drop(map.drain_filter(|dummy, _| dummy.query(true)))).unwrap_err();
36717 let mut map = BTreeMap::new();
36718 map.insert(a.spawn(Panic::Never), ());
36719 map.insert(b.spawn(Panic::InQuery), ());
36720 map.insert(c.spawn(Panic::InQuery), ());
36722 catch_unwind(AssertUnwindSafe(|| drop(map.drain_filter(|dummy, _| dummy.query(true)))))
36731 assert_eq!(map.len(), 2);
36732 assert_eq!(map.first_entry().unwrap().key().id(), 1);
36733 assert_eq!(map.last_entry().unwrap().key().id(), 2);
36734 map.check();
36743 let mut map = BTreeMap::new();
36744 map.insert(a.spawn(Panic::Never), ());
36745 map.insert(b.spawn(Panic::InQuery), ());
36746 map.insert(c.spawn(Panic::InQuery), ());
36749 let mut it = map.drain_filter(|dummy, _| dummy.query(true));
36763 assert_eq!(map.len(), 2);
36764 assert_eq!(map.first_entry().unwrap().key().id(), 1);
36765 assert_eq!(map.last_entry().unwrap().key().id(), 2);
36766 map.check();
36774 let mut map = BTreeMap::new();
36775 map.insert("0".to_string(), 1);
36776 assert_eq!(map["0"], 1);
36780 let mut map = BTreeMap::new();
36781 map.insert(Box::new(0), 1);
36782 assert_eq!(map[&0], 1);
36786 let mut map = BTreeMap::new();
36787 map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
36788 assert_eq!(map[&[0, 1][..]], 1);
36792 let mut map = BTreeMap::new();
36793 map.insert(Rc::new(0), 1);
36794 assert_eq!(map[&0], 1);
36847 let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
36850 match map.entry(1) {
36857 assert_eq!(map.get(&1).unwrap(), &100);
36858 assert_eq!(map.len(), 6);
36861 match map.entry(2) {
36868 assert_eq!(map.get(&2).unwrap(), &200);
36869 assert_eq!(map.len(), 6);
36870 map.check();
36873 match map.entry(3) {
36879 assert_eq!(map.get(&3), None);
36880 assert_eq!(map.len(), 5);
36881 map.check();
36884 match map.entry(10) {
36890 assert_eq!(map.get(&10).unwrap(), &1000);
36891 assert_eq!(map.len(), 6);
36892 map.check();
36937 // do not cause segfaults when used with zero-sized values. All other map behavior is
36974 let mut map = BTreeMap::new();
36977 map.insert(i, ());
36979 assert_eq!(map.len(), len);
36980 map.clear();
36981 map.check();
36982 assert!(map.is_empty());
36992 let mut map = BTreeMap::new();
36993 map.insert(a.spawn(Panic::Never), ());
36994 map.insert(b.spawn(Panic::InDrop), ());
36995 map.insert(c.spawn(Panic::Never), ());
36997 catch_unwind(AssertUnwindSafe(|| map.clear())).unwrap_err();
37001 assert_eq!(map.len(), 0);
37003 drop(map);
37011 let mut map = BTreeMap::new();
37013 assert_eq!(map.len(), 0);
37016 assert_eq!(map.insert(i, 10 * i), None);
37017 assert_eq!(map.len(), i + 1);
37018 map.check();
37019 assert_eq!(map, map.clone());
37023 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
37024 assert_eq!(map.len(), size);
37025 map.check();
37026 assert_eq!(map, map.clone());
37030 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
37031 assert_eq!(map.len(), size - i - 1);
37032 map.check();
37033 assert_eq!(map, map.clone());
37037 assert_eq!(map.remove(&(2 * i)), None);
37038 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
37039 assert_eq!(map.len(), size / 2 - i - 1);
37040 map.check();
37041 assert_eq!(map, map.clone());
37045 map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect();
37046 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1);
37047 assert_eq!(map, map.clone());
37048 map.insert(0, 0);
37049 assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2);
37050 assert_eq!(map, map.clone());
37051 map.check();
37060 let mut map = BTreeMap::new();
37061 map.insert(a.spawn(Panic::Never), ());
37062 map.insert(b.spawn(Panic::InClone), ());
37063 map.insert(c.spawn(Panic::Never), ());
37065 catch_unwind(|| map.clone()).unwrap_err();
37072 assert_eq!(map.len(), 3);
37074 drop(map);
37169 fn map<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ {
37238 fn map<T: Send>(v: BTreeMap<T, T>) -> impl Send {
37307 fn map<K>(mut map: BTreeMap<K, ()>) {
37308 map.is_empty();
37309 map.len();
37310 map.clear();
37311 map.iter();
37312 map.iter_mut();
37313 map.keys();
37314 map.values();
37315 map.values_mut();
37317 map.into_values();
37319 map.into_iter();
37321 map.into_keys();
37325 fn map_debug<K: Debug>(mut map: BTreeMap<K, ()>) {
37326 format!("{:?}", map);
37327 format!("{:?}", map.iter());
37328 format!("{:?}", map.iter_mut());
37329 format!("{:?}", map.keys());
37330 format!("{:?}", map.values());
37331 format!("{:?}", map.values_mut());
37333 format!("{:?}", map.into_iter());
37335 format!("{:?}", map.into_keys());
37337 format!("{:?}", map.into_values());
37341 fn map_clone<K: Clone>(mut map: BTreeMap<K, ()>) {
37342 map.clone_from(&map.clone());
37420 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i * 2 + 1, ())).collect();
37421 assert!(map.insert(pos * 2, ()).is_none());
37422 map.check();
37430 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i * 2 + 1, ())).collect();
37431 map.compact();
37432 let root_node = map.root.as_ref().unwrap().reborrow();
37437 assert!(map.insert(pos * 2, ()).is_none());
37438 map.check();
37540 Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
37547 let mut map = BTreeMap::from_iter(data.clone());
37548 let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
37549 map.check();
37553 assert!(map.into_iter().eq(data));
37561 let mut map = BTreeMap::from_iter(data.clone());
37562 let right = map.split_off(&data.iter().min().unwrap().0);
37563 map.check();
37567 assert!(map.into_iter().eq(None));
37575 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
37590 let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i));
37607 let mut data = Vec::from_iter((0..len).map(|_| (rng.next(), ())));
37609 let mut map = BTreeMap::from_iter(data.iter().copied());
37611 let small_keys = data.iter().take(len / 2).map(|kv| kv.0);
37612 let large_keys = data.iter().skip(len / 2).map(|kv| kv.0);
37614 let right = map.split_off(&split_key);
37615 map.check();
37617 assert!(map.keys().copied().eq(small_keys));
37629 let mut map = BTreeMap::from_iter(data.clone());
37631 let right = map.split_off(&key);
37632 map.check();
37635 assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
37646 let mut map = BTreeMap::new();
37647 map.insert("a", a.spawn(Panic::Never));
37648 map.insert("b", b.spawn(Panic::Never));
37649 map.insert("c", c.spawn(Panic::Never));
37650 map.insert("d", d.spawn(Panic::InDrop));
37651 map.insert("e", e.spawn(Panic::Never));
37653 catch_unwind(move || drop(map.into_iter())).unwrap_err();
37666 let dummies: Vec<_> = (0..size).map(|i| CrashTestDummy::new(i)).collect();
37667 let map: BTreeMap<_, _> = (0..size)
37668 .map(|i| {
37673 catch_unwind(move || drop(map.into_iter())).unwrap_err();
37683 let map: BTreeMap<_, _> = vec.into_iter().collect();
37684 let keys: Vec<_> = map.into_keys().collect();
37695 let map: BTreeMap<_, _> = vec.into_iter().collect();
37696 let values: Vec<_> = map.into_values().collect();
37707 let mut map = BTreeMap::new();
37712 map.insert(i, i);
37713 map.remove(&(0xFF - i));
37715 map.check();
37722 let mut map = BTreeMap::new();
37727 map.insert(Governed(i, &gov), ());
37728 map.remove(&Governed(0xFF - i, &gov));
37731 map.check_invariants();
37733 use super::map::MIN_LEN;
37739 /// a root node that is internal, which the caller should pop from the map
37740 /// holding the tree. The caller should also decrement the map's length.
37902 Ordering::Less => self.peeked = b_next.take().map(Peeked::B),
37903 Ordering::Greater => self.peeked = a_next.take().map(Peeked::A),
38245 .map(|parent| Handle {
39731 use super::map::MIN_LEN;
39913 //! A map based on a B-Tree.
39915 pub use super::btree::map::*;
40214 self.iter.next().map(|elt| unsafe { ptr::read(elt) })
40227 self.iter.next_back().map(|elt| unsafe { ptr::read(elt) })
41031 /// output.extend(data.iter().map(|&val| {
41069 /// output.extend(data.iter().map(|&val| {
42853 let cmp_back = back.first().map(|elem| f(elem));
42858 back.binary_search_by(f).map(|idx| idx + front.len()).map_err(|idx| idx + front.len())
42951 if let Some(true) = back.first().map(|v| pred(v)) {
43786 let range: VecDeque<_> = tester.range_mut(start..end).map(|v| *v).collect();
44330 //! let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect();
44700 self.data.pop().map(|mut item| {
46367 self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
46379 self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
47641 /// output.extend(data.iter().map(|&val| {
47683 /// output.extend(data.iter().map(|&val| {
49086 .map(|(src, dst)| dst.write(src.clone()))