Lines Matching defs:key
22287 /// Sorts the slice with a key extraction function.
22290 /// worst-case, where the key function is *O*(*m*).
22292 /// For expensive key functions (e.g. functions that are not simple property accesses or
22328 /// Sorts the slice with a key extraction function.
22330 /// During sorting, the key function is called only once per element.
22333 /// worst-case, where the key function is *O*(*m*).
22335 /// For simple key functions (e.g., functions that are property accesses or
23360 /// first: after all, isn't the point of `Arc<T>` thread safety? The key is
29192 /// Appends all key-value pairs from the union of two ascending iterators,
29196 /// If both iterators produce the same key, this method drops the pair from
29215 /// Pushes all key-value pairs to the end of the tree, incrementing a
29223 // Iterate through all key-value pairs, pushing them into nodes at the right level.
29224 for (key, value) in iter {
29225 // Try to push key-value pair into the current leaf node.
29227 cur_node.push(key, value);
29253 // Push key-value pair and new right subtree.
29259 open_node.push(key, value, right_tree);
29282 /// If two keys are equal, returns the key-value pair from the right source.
29560 /// Looks up a given key in a (sub)tree headed by the node, recursively.
29562 /// returns a `GoDown` with the handle of the leaf edge where the key belongs.
29564 /// The result is meaningful only if the tree is ordered by key, like the tree
29568 key: &Q,
29575 self = match self.search_node(key) {
29587 /// the nearest node that has at least one key contained in the range.
29599 /// The result is meaningful only if the tree is ordered by key.
29664 /// The result is meaningful only if the tree is ordered by key.
29694 /// Looks up a given key in the node, without recursion.
29696 /// returns a `GoDown` with the handle of the edge where the key might be found
29697 /// (if the node is internal) or where the key can be inserted.
29699 /// The result is meaningful only if the tree is ordered by key, like the tree
29701 pub fn search_node<Q: ?Sized>(self, key: &Q) -> SearchResult<BorrowType, K, V, Type, Type>
29706 match unsafe { self.find_key_index(key, 0) } {
29712 /// Returns either the KV index in the node at which the key (or an equivalent)
29713 /// exists, or the edge index where the key belongs, starting from a particular index.
29715 /// The result is meaningful only if the tree is ordered by key, like the tree
29720 unsafe fn find_key_index<Q: ?Sized>(&self, key: &Q, start_index: usize) -> IndexResult
29729 match key.cmp(k.borrow()) {
29742 /// The result is meaningful only if the tree is ordered by key.
29752 Included(key) => match unsafe { self.find_key_index(key, 0) } {
29756 Excluded(key) => match unsafe { self.find_key_index(key, 0) } {
29766 /// with an additional parameter to skip part of the key array.
29780 Included(key) => match unsafe { self.find_key_index(key, start_index) } {
29784 Excluded(key) => match unsafe { self.find_key_index(key, start_index) } {
29817 // - Keys must appear in ascending order (according to the key's type).
29851 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
29852 /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
29895 /// // Look up the value for a key (will panic if the key is not found).
29922 /// // insert a key only if it doesn't already exist
29925 /// // insert a key using a function that provides a new value only if it
29929 /// // update a key, guarding against the key possibly not being set
30033 fn get(&self, key: &Q) -> Option<&K> {
30035 match root_node.search_tree(key) {
30041 fn take(&mut self, key: &Q) -> Option<K> {
30044 match root_node.search_tree(key) {
30052 fn replace(&mut self, key: K) -> Option<K> {
30055 match root_node.search_tree::<K>(&key) {
30056 Found(mut kv) => Some(mem::replace(kv.key_mut(), key)),
30058 VacantEntry { key, handle, dormant_map, _marker: PhantomData }.insert(());
30201 f.debug_list().entries(self.inner.iter().map(|(key, _)| key)).finish()
30308 /// Returns a reference to the value corresponding to the key.
30310 /// The key may be any borrowed form of the map's key type, but the ordering
30311 /// on the borrowed form *must* match the ordering on the key type.
30326 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
30332 match root_node.search_tree(key) {
30338 /// Returns the key-value pair corresponding to the supplied key.
30340 /// The supplied key may be any borrowed form of the map's key type, but the ordering
30341 /// on the borrowed form *must* match the ordering on the key type.
30366 /// Returns the first key-value pair in the map.
30367 /// The key in this pair is the minimum key in the map.
30393 /// The key of this entry is the minimum key in the map.
30405 /// if *entry.key() > 0 {
30424 /// The key of this element is the minimum key that was in the map.
30437 /// while let Some((key, _val)) = map.pop_first() {
30438 /// assert!(map.iter().all(|(k, _v)| *k > key));
30450 /// Returns the last key-value pair in the map.
30451 /// The key in this pair is the maximum key in the map.
30476 /// The key of this entry is the maximum key in the map.
30488 /// if *entry.key() > 0 {
30507 /// The key of this element is the maximum key that was in the map.
30520 /// while let Some((key, _val)) = map.pop_last() {
30521 /// assert!(map.iter().all(|(k, _v)| *k < key));
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
30536 /// on the borrowed form *must* match the ordering on the key type.
30551 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
30556 self.get(key).is_some()
30559 /// Returns a mutable reference to the value corresponding to the key.
30561 /// The key may be any borrowed form of the map's key type, but the ordering
30562 /// on the borrowed form *must* match the ordering on the key type.
30580 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
30586 match root_node.search_tree(key) {
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
30597 /// value is returned. The key is not updated, though; this matters for
30619 pub fn insert(&mut self, key: K, value: V) -> Option<V>
30623 match self.entry(key) {
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
30651 /// assert_eq!(err.entry.key(), &37);
30656 pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V>>
30660 match self.entry(key) {
30666 /// Removes a key from the map, returning the value at the key if the key
30669 /// The key may be any borrowed form of the map's key type, but the ordering
30670 /// on the borrowed form *must* match the ordering on the key type.
30686 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
30691 self.remove_entry(key).map(|(_, v)| v)
30694 /// Removes a key from the map, returning the stored key and value if the key
30697 /// The key may be any borrowed form of the map's key type, but the ordering
30698 /// on the borrowed form *must* match the ordering on the key type.
30713 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
30720 match root_node.search_tree(key) {
30826 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
30827 /// println!("{}: {}", key, value);
30889 /// Gets the given key's corresponding entry in the map for in-place manipulation.
30908 pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
30915 match root_node.search_tree(&key) {
30918 Vacant(VacantEntry { key, handle, dormant_map, _marker: PhantomData })
30923 /// Splits the collection into two at the given key. Returns everything after the given key,
30924 /// including the key.
30953 pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
30964 let right_root = left_root.split_off(key);
30972 /// Creates an iterator that visits all elements (key-value pairs) in
30973 /// ascending key order and uses a closure to determine if an element should
31053 /// Creates a consuming iterator visiting all the values, in order by key.
31746 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
31813 /// Returns a reference to the value corresponding to the supplied key.
31817 /// Panics if the key is not present in the `BTreeMap`.
31819 fn index(&self, key: &Q) -> &V {
31820 self.get(key).expect("no entry found for key")
31825 /// Gets an iterator over the entries of the map, sorted by key.
31839 /// for (key, value) in map.iter() {
31840 /// println!("{}: {}", key, value);
31857 /// Gets a mutable iterator over the entries of the map, sorted by key.
31871 /// // add 10 to the value if the key isn't "a"
31872 /// for (key, value) in map.iter_mut() {
31873 /// if key != &"a" {
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.
32101 /// a given number of distinct key-value pairs.
32120 /// Split off a tree with key-value pairs at and after the given key.
32121 /// The result is meaningful only if the tree is ordered by key,
32125 pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
32135 let mut split_edge = match left_node.search_node(key) {
32136 // key is going to the right tree
33073 /// Splits the collection into two at the given key. Returns everything after the given key,
33074 /// including the key.
33103 pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
33107 BTreeSet { map: self.map.split_off(key) }
33786 /// If there are no such edges, i.e., if the tree contains no key within
33855 /// The result is meaningful only if the tree is ordered by key, like the tree
33878 /// The result is meaningful only if the tree is ordered by key, like the tree
33988 /// on the right side, and the key-value pair in between, which is either
33992 /// implies that if no more key-value pair exists, the entire remainder of
34016 /// on the left side, and the key-value pair in between, which is either
34020 /// implies that if no more key-value pair exists, the entire remainder of
34059 /// key and value in between.
34072 /// key and value in between.
34087 /// key and value in between.
34102 /// key and value in between.
34118 /// Moves the leaf edge handle to the next leaf edge and returns the key and value
34136 /// Moves the leaf edge handle to the previous leaf edge and returns the key and value
34280 fn get(&self, key: &Q) -> Option<&Self::Key>;
34281 fn take(&mut self, key: &Q) -> Option<Self::Key>;
34282 fn replace(&mut self, key: Self::Key) -> Option<Self::Key>;
35021 let key = data[data.len() / 2];
35022 let right = set.split_off(&key);
35024 assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
35025 assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
35086 pub(super) key: K,
35097 f.debug_tuple("VacantEntry").field(self.key()).finish()
35115 f.debug_struct("OccupiedEntry").field("key", self.key()).field("value", self.get()).finish()
35119 /// The error returned by [`try_insert`](BTreeMap::try_insert) when the key already exists.
35134 .field("key", self.entry.key())
35146 "failed to insert {:?}, key {:?} already exists with value {:?}",
35148 self.entry.key(),
35200 /// This method allows for generating key-derived values for insertion by providing the default
35201 /// function a reference to the key that was moved during the `.entry(key)` method call.
35203 /// The reference to the moved key is provided so that cloning or copying the key is
35213 /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
35223 let value = default(entry.key());
35229 /// Returns a reference to this entry's key.
35237 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
35240 pub fn key(&self) -> &K {
35242 Occupied(ref entry) => entry.key(),
35243 Vacant(ref entry) => entry.key(),
35306 /// Gets a reference to the key that would be used when inserting a value
35315 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
35318 pub fn key(&self) -> &K {
35319 &self.key
35322 /// Take ownership of the key.
35338 self.key
35341 /// Sets the value of the entry with the `VacantEntry`'s key,
35359 let out_ptr = match self.handle.insert_recursing(self.key, value) {
35383 /// Gets a reference to the key in the entry.
35392 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
35395 pub fn key(&self) -> &K {
35399 /// Take ownership of the key and value from the map.
35500 /// Sets the value of the entry with the `OccupiedEntry`'s key,
35769 assert_eq!(map.first_entry().unwrap().key(), &0);
35770 assert_eq!(map.last_entry().unwrap().key(), &(size - 1));
35829 // 1 key-value pair:
35849 // 2 key-value pairs:
35861 // 1 key-value pair:
36198 // Tests tree with a root and 2 leaves. The single key in the root node is
36732 assert_eq!(map.first_entry().unwrap().key().id(), 1);
36733 assert_eq!(map.last_entry().unwrap().key().id(), 2);
36764 assert_eq!(map.first_entry().unwrap().key().id(), 1);
36765 assert_eq!(map.last_entry().unwrap().key().id(), 2);
36849 // Existing key (insert)
36860 // Existing key (update)
36872 // Existing key (take)
36883 // Inexistent key (insert)
37356 let key = "hello there";
37359 a.insert(key, value);
37361 assert_eq!(a[key], value);
37363 match a.entry(key) {
37365 Occupied(e) => assert_eq!(key, *e.key()),
37368 assert_eq!(a[key], value);
37375 let key = "hello there";
37379 match a.entry(key) {
37382 assert_eq!(key, *e.key());
37387 assert_eq!(a[key], value);
37397 assert_eq!(a.first_entry().unwrap().key(), &1);
37398 assert_eq!(a.last_entry().unwrap().key(), &1);
37400 assert_eq!(a.first_entry().unwrap().key(), &1);
37401 assert_eq!(a.last_entry().unwrap().key(), &2);
37403 assert_eq!(a.first_entry().unwrap().key(), &0);
37404 assert_eq!(a.last_entry().unwrap().key(), &2);
37411 assert_eq!(a.first_entry().unwrap().key(), &1);
37412 assert_eq!(a.last_entry().unwrap().key(), &1);
37506 left.insert(b.spawn(Panic::InDrop), ()); // first duplicate key, dropped during append
37630 let key = data[data.len() / 2].0;
37631 let right = map.split_off(&key);
37635 assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
37636 assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
37737 /// Removes a key-value pair from the tree, and returns that pair, as well as
38362 /// Borrows exclusive access to an element of the key storage area.
38371 // until the key slice reference is dropped, as we have unique access
38420 let key = unsafe { (&*keys.get_unchecked(idx)).assume_init_ref() };
38422 (key, val)
38534 /// Adds a key-value pair to the end of the node.
38535 pub fn push(&mut self, key: K, val: V) {
38541 self.key_area_mut(idx).write(key);
38548 /// Adds a key-value pair, and an edge to go to the right of that pair,
38550 pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
38558 self.key_area_mut(idx).write(key);
38618 /// A reference to a specific key-value pair or edge within a node. The `Node` parameter
38619 /// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key-value
38623 /// a child node, these represent the spaces where child pointers would go between the key-value
38642 /// Retrieves the node that contains the edge or key-value pair this handle points to.
38654 /// Creates a new handle to a key-value pair in `node`.
38737 /// The goal of the split point is for its key and value to end up in a parent node;
38752 /// Inserts a new key-value pair between the key-value pairs to the right and left of
38757 fn insert_fit(&mut self, key: K, val: V) -> *mut V {
38762 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
38772 /// Inserts a new key-value pair between the key-value pairs to the right and left of
38776 fn insert(mut self, key: K, val: V) -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
38778 let val_ptr = self.insert_fit(key, val);
38793 let val_ptr = insertion_edge.insert_fit(key, val);
38812 /// Inserts a new key-value pair and an edge that will go to the right of that new pair
38813 /// between this edge and the key-value pair to the right of this edge. This method assumes
38815 fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
38821 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
38830 /// Inserts a new key-value pair and an edge that will go to the right of that new pair
38831 /// between this edge and the key-value pair to the right of this edge. This method splits
38835 key: K,
38842 self.insert_fit(key, val, edge);
38857 insertion_edge.insert_fit(key, val, edge);
38864 /// Inserts a new key-value pair between the key-value pairs to the right and left of
38873 key: K,
38876 let (mut split, val_ptr) = match self.insert(key, value) {
38954 // We cannot call separate key and value methods, because calling the second one
38958 let key = leaf.keys.get_unchecked_mut(self.idx).assume_init_mut();
38960 (key, val)
38964 /// Replace the key and value that the KV handle refers to.
38966 let (key, val) = self.kv_mut();
38967 (mem::replace(key, k), mem::replace(val, v))
39001 /// - The node is truncated to only contain the key-value pairs to the left of
39003 /// - The key and value pointed to by this handle are extracted.
39004 /// - All the key-value pairs to the right of this handle are put into a newly
39015 /// Removes the key-value pair pointed to by this handle and returns it, along with the edge
39016 /// that the key-value pair collapsed into.
39033 /// - The node is truncated to only contain the edges and key-value pairs to the
39035 /// - The key and value pointed to by this handle are extracted.
39036 /// - All the edges and key-value pairs to the right of this handle are put into
39058 /// around an internal key-value pair.
39201 /// Merges the parent's key-value pair and both adjacent child nodes into
39209 /// Merges the parent's key-value pair and both adjacent child nodes into
39217 /// Merges the parent's key-value pair and both adjacent child nodes into
39240 /// Removes a key-value pair from the left child and places it in the key-value storage
39241 /// of the parent, while pushing the old parent key-value pair into the right child.
39252 /// Removes a key-value pair from the right child and places it in the key-value storage
39253 /// of the parent, while pushing the old parent key-value pair onto the left child.
39303 // Move parent's key-value pair to the right child.
39352 // Move parent's key-value pair to the left child.
39508 // Some key and value split off, to be inserted elsewhere.
42864 /// Binary searches this sorted `VecDeque` with a key extraction function.
42866 /// Assumes that the `VecDeque` is sorted by the key, for instance with
42867 /// [`make_contiguous().sort_by_key()`] using the same key extraction function.
48289 /// key.
48304 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
48309 self.dedup_by(|a, b| key(a) == key(b))