aboutsummaryrefslogtreecommitdiff
path: root/libcollections/btree/map.rs
diff options
context:
space:
mode:
Diffstat (limited to 'libcollections/btree/map.rs')
-rw-r--r--libcollections/btree/map.rs198
1 files changed, 187 insertions, 11 deletions
diff --git a/libcollections/btree/map.rs b/libcollections/btree/map.rs
index 20ef273..29f3e4b 100644
--- a/libcollections/btree/map.rs
+++ b/libcollections/btree/map.rs
@@ -286,7 +286,7 @@ pub struct Values<'a, K: 'a, V: 'a> {
}
/// A mutable iterator over a BTreeMap's values.
-#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
+#[stable(feature = "map_values_mut", since = "1.10.0")]
pub struct ValuesMut<'a, K: 'a, V: 'a> {
inner: IterMut<'a, K, V>,
}
@@ -842,13 +842,13 @@ impl<K: Ord, V> BTreeMap<K, V> {
// Check if right-most child is underfull.
let mut last_edge = internal.last_edge();
let right_child_len = last_edge.reborrow().descend().len();
- if right_child_len < node::CAPACITY / 2 {
+ if right_child_len < node::MIN_LEN {
// We need to steal.
let mut last_kv = match last_edge.left_kv() {
Ok(left) => left,
Err(_) => unreachable!(),
};
- last_kv.bulk_steal_left(node::CAPACITY/2 - right_child_len);
+ last_kv.bulk_steal_left(node::MIN_LEN - right_child_len);
last_edge = last_kv.right_edge();
}
@@ -856,6 +856,174 @@ impl<K: Ord, V> BTreeMap<K, V> {
cur_node = last_edge.descend();
}
}
+
+ /// Splits the collection into two at the given key. Returns everything after the given key,
+ /// including the key.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// #![feature(btree_split_off)]
+ /// use std::collections::BTreeMap;
+ ///
+ /// let mut a = BTreeMap::new();
+ /// a.insert(1, "a");
+ /// a.insert(2, "b");
+ /// a.insert(3, "c");
+ /// a.insert(17, "d");
+ /// a.insert(41, "e");
+ ///
+ /// let b = a.split_off(&3);
+ ///
+ /// assert_eq!(a.len(), 2);
+ /// assert_eq!(b.len(), 3);
+ ///
+ /// assert_eq!(a[&1], "a");
+ /// assert_eq!(a[&2], "b");
+ ///
+ /// assert_eq!(b[&3], "c");
+ /// assert_eq!(b[&17], "d");
+ /// assert_eq!(b[&41], "e");
+ /// ```
+ #[unstable(feature = "btree_split_off",
+ reason = "recently added as part of collections reform 2",
+ issue = "19986")]
+ pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self where K: Borrow<Q> {
+ if self.is_empty() {
+ return Self::new();
+ }
+
+ let total_num = self.len();
+
+ let mut right = Self::new();
+ for _ in 0..(self.root.as_ref().height()) {
+ right.root.push_level();
+ }
+
+ {
+ let mut left_node = self.root.as_mut();
+ let mut right_node = right.root.as_mut();
+
+ loop {
+ let mut split_edge = match search::search_node(left_node, key) {
+ // key is going to the right tree
+ Found(handle) => handle.left_edge(),
+ GoDown(handle) => handle
+ };
+
+ split_edge.move_suffix(&mut right_node);
+
+ match (split_edge.force(), right_node.force()) {
+ (Internal(edge), Internal(node)) => {
+ left_node = edge.descend();
+ right_node = node.first_edge().descend();
+ }
+ (Leaf(_), Leaf(_)) => { break; },
+ _ => { unreachable!(); }
+ }
+ }
+ }
+
+ self.fix_right_border();
+ right.fix_left_border();
+
+ if self.root.as_ref().height() < right.root.as_ref().height() {
+ self.recalc_length();
+ right.length = total_num - self.len();
+ } else {
+ right.recalc_length();
+ self.length = total_num - right.len();
+ }
+
+ right
+ }
+
+ /// Calculates the number of elements if it is incorrect.
+ fn recalc_length(&mut self) {
+ fn dfs<K, V>(node: NodeRef<marker::Immut, K, V, marker::LeafOrInternal>) -> usize {
+ let mut res = node.len();
+
+ if let Internal(node) = node.force() {
+ let mut edge = node.first_edge();
+ loop {
+ res += dfs(edge.reborrow().descend());
+ match edge.right_kv() {
+ Ok(right_kv) => { edge = right_kv.right_edge(); },
+ Err(_) => { break; }
+ }
+ }
+ }
+
+ res
+ }
+
+ self.length = dfs(self.root.as_ref());
+ }
+
+ /// Removes empty levels on the top.
+ fn fix_top(&mut self) {
+ loop {
+ {
+ let node = self.root.as_ref();
+ if node.height() == 0 || node.len() > 0 {
+ break;
+ }
+ }
+ self.root.pop_level();
+ }
+ }
+
+ fn fix_right_border(&mut self) {
+ self.fix_top();
+
+ {
+ let mut cur_node = self.root.as_mut();
+
+ while let Internal(node) = cur_node.force() {
+ let mut last_kv = node.last_kv();
+
+ if last_kv.can_merge() {
+ cur_node = last_kv.merge().descend();
+ } else {
+ let right_len = last_kv.reborrow().right_edge().descend().len();
+ // `MINLEN + 1` to avoid readjust if merge happens on the next level.
+ if right_len < node::MIN_LEN + 1 {
+ last_kv.bulk_steal_left(node::MIN_LEN + 1 - right_len);
+ }
+ cur_node = last_kv.right_edge().descend();
+ }
+ }
+ }
+
+ self.fix_top();
+ }
+
+ /// The symmetric clone of `fix_right_border`.
+ fn fix_left_border(&mut self) {
+ self.fix_top();
+
+ {
+ let mut cur_node = self.root.as_mut();
+
+ while let Internal(node) = cur_node.force() {
+ let mut first_kv = node.first_kv();
+
+ if first_kv.can_merge() {
+ cur_node = first_kv.merge().descend();
+ } else {
+ let left_len = first_kv.reborrow().left_edge().descend().len();
+ if left_len < node::MIN_LEN + 1 {
+ first_kv.bulk_steal_right(node::MIN_LEN + 1 - left_len);
+ }
+ cur_node = first_kv.left_edge().descend();
+ }
+ }
+ }
+
+ self.fix_top();
+ }
}
impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
@@ -1144,7 +1312,7 @@ impl<'a, K, V> Iterator for Range<'a, K, V> {
}
}
-#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
+#[stable(feature = "map_values_mut", since = "1.10.0")]
impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
type Item = &'a mut V;
@@ -1157,14 +1325,14 @@ impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
}
}
-#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
+#[stable(feature = "map_values_mut", since = "1.10.0")]
impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
fn next_back(&mut self) -> Option<&'a mut V> {
self.inner.next_back().map(|(_, v)| v)
}
}
-#[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
+#[stable(feature = "map_values_mut", since = "1.10.0")]
impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
fn len(&self) -> usize {
self.inner.len()
@@ -1575,7 +1743,6 @@ impl<K, V> BTreeMap<K, V> {
/// Basic usage:
///
/// ```
- /// # #![feature(map_values_mut)]
/// use std::collections::BTreeMap;
///
/// let mut a = BTreeMap::new();
@@ -1590,8 +1757,8 @@ impl<K, V> BTreeMap<K, V> {
/// assert_eq!(values, [String::from("hello!"),
/// String::from("goodbye!")]);
/// ```
- #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
- pub fn values_mut<'a>(&'a mut self) -> ValuesMut<'a, K, V> {
+ #[stable(feature = "map_values_mut", since = "1.10.0")]
+ pub fn values_mut(&mut self) -> ValuesMut<K, V> {
ValuesMut { inner: self.iter_mut() }
}
@@ -1654,12 +1821,21 @@ impl<'a, K: Ord, V> Entry<'a, K, V> {
Vacant(entry) => entry.insert(default()),
}
}
+
+ /// Returns a reference to this entry's key.
+ #[stable(feature = "map_entry_keys", since = "1.10.0")]
+ pub fn key(&self) -> &K {
+ match *self {
+ Occupied(ref entry) => entry.key(),
+ Vacant(ref entry) => entry.key(),
+ }
+ }
}
impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
/// Gets a reference to the key that would be used when inserting a value
/// through the VacantEntry.
- #[unstable(feature = "map_entry_keys", issue = "32281")]
+ #[stable(feature = "map_entry_keys", since = "1.10.0")]
pub fn key(&self) -> &K {
&self.key
}
@@ -1709,7 +1885,7 @@ impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
/// Gets a reference to the key in the entry.
- #[unstable(feature = "map_entry_keys", issue = "32281")]
+ #[stable(feature = "map_entry_keys", since = "1.10.0")]
pub fn key(&self) -> &K {
self.handle.reborrow().into_kv().0
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-11 03:04:21 +0000