Struct AugmentedRBTreeInt 

pub struct AugmentedRBTreeInt<K, V, S, A, P>
where
    P: TreePolicy<K = K, V = V, S = S>,
    A: Allocator,
{ /* private fields */ }

A Red-Black Tree that supports augmentation through the Augment trait.

Implementations

impl<K, V, S, P> AugmentedRBTreeInt<K, V, S, Global, P>

where P: TreePolicy<K = K, V = V, S = S>,

pub fn new() -> Self

Creates a new, empty AugmentedRBTree using the global allocator.

impl<K, V, S, A, P> AugmentedRBTreeInt<K, V, S, A, P>

where P: TreePolicy<K = K, V = V, S = S>, A: Allocator,

pub fn insert(&mut self, key: K, value: V) -> Option<V>

where K: Ord,

Inserts a key-value pair into the tree. If the key already exists, its value is updated.

Returns

Returns Some(old_value) if the key was already present, or None if the key was newly inserted.

Examples

let mut tree = AugmentedRBTree::<String, i32, SubtreeSize>::new();
tree.insert("hello".to_string(), 1);
assert_eq!(tree.insert("hello".to_string(), 2), Some(1));
assert_eq!(tree.insert("world".to_string(), 3), None);

pub fn try_insert( &mut self, key: K, value: V, ) -> Result<Option<V>, OutOfMemoryError>

where K: Ord,

Try to insert a key with a value

pub fn len(&self) -> usize

Returns the number of elements in the tree.

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns a reference to the value associated with the given key, if it exists in the tree.

The key may be any borrowed form of the tree’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

let mut tree = AugmentedRBTree::<String, i32, SubtreeSize>::new();
tree.insert("hello".to_string(), 1);
assert_eq!(tree.get("hello"), Some(&1));
assert_eq!(tree.get("world"), None);

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns a mutable reference to the value associated with the given key, if it exists.

The key may be any borrowed form of the tree’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

let mut tree = AugmentedRBTree::<String, i32, SubtreeSize>::new();
tree.insert("hello".to_string(), 1);
if let Some(v) = tree.get_mut("hello") {
    *v = 42;
}
assert_eq!(tree.get("hello"), Some(&42));

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns true if the tree contains a value for the given key.

The key may be any borrowed form of the tree’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

let mut tree = AugmentedRBTree::<String, i32, SubtreeSize>::new();
tree.insert("hello".to_string(), 1);
assert!(tree.contains_key("hello"));
assert!(!tree.contains_key("world"));

pub fn get_key_value_stats<Q>(&self, key: &Q) -> Option<(&K, &V, &S)>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns a reference to the key-value-stats tuple for the given key, if it exists.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(1, "a");
assert_eq!(tree.get_key_value_stats(&1), Some((&1, &"a", &1)));

pub fn get_value_stats<Q>(&self, key: &Q) -> Option<(&V, &S)>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns a reference to the key-value-stats tuple for the given key, if it exists.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(1, "a");
assert_eq!(tree.get_value_stats(&1), Some((&"a", &1)));

pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns a reference to the key-value tuple for the given key, if it exists.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(1, "a");
assert_eq!(tree.get_key_value(&1), Some((&1, &"a")));

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Removes the node with the given key from the tree, if it exists, and returns its value. If the key does not exist in the tree, returns None.

The key may be any borrowed form of the tree’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

let mut tree = AugmentedRBTree::<String, i32, SubtreeSize>::new();
tree.insert("hello".to_string(), 1);
assert_eq!(tree.remove("hello"), Some(1));
assert_eq!(tree.remove("hello"), None);

pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Removes and returns the key-value pair for the given key if it exists.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(1, "a");
assert_eq!(tree.remove_entry(&1), Some((1, "a")));
assert_eq!(tree.remove_entry(&1), None);

pub fn first_key_value_stats(&self) -> Option<(&K, &V, &S)>

where K: Ord,

Returns a reference to the first (minimum) key-value-stats entry in the tree.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(3, "c");
tree.insert(1, "a");
tree.insert(2, "b");
assert_eq!(tree.first_key_value_stats(), Some((&1, &"a", &1)));

pub fn last_key_value_stats(&self) -> Option<(&K, &V, &S)>

where K: Ord,

Returns a reference to the last (maximum) key-value-stats entry in the tree.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(3, "c");
tree.insert(1, "a");
tree.insert(2, "b");
assert_eq!(tree.last_key_value_stats(), Some((&3, &"c", &1)));

pub fn pop_first(&mut self) -> Option<(K, V)>

where K: Ord,

Removes and returns the first (minimum) key-value pair from the tree.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(3, "c");
tree.insert(1, "a");
tree.insert(2, "b");
assert_eq!(tree.pop_first(), Some((1, "a")));
assert_eq!(tree.len(), 2);

pub fn pop_last(&mut self) -> Option<(K, V)>

where K: Ord,

Removes and returns the last (maximum) key-value pair from the tree.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(3, "c");
tree.insert(1, "a");
tree.insert(2, "b");
assert_eq!(tree.pop_last(), Some((3, "c")));
assert_eq!(tree.len(), 2);

pub fn root_stats(&self) -> Option<&S>

Returns the augmentation data (stats) stored at the root, covering the entire tree.

For augmentations like sum or count, this gives the aggregate result over all elements. Returns None if the tree is empty.

Examples

let mut tree = AugmentedRBTree::<i32, i32, Sum>::new();
tree.insert(1, 10);
tree.insert(2, 20);
tree.insert(3, 30);
assert_eq!(tree.root_stats(), Some(&60));

pub fn is_empty(&self) -> bool

Returns true if the tree contains no elements.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
assert!(tree.is_empty());
tree.insert(1, "a");
assert!(!tree.is_empty());

pub fn clear(&mut self)

Clears the tree, removing all elements.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(1, "a");
tree.clear();
assert!(tree.is_empty());

impl<K, V, S, A: Allocator, P> AugmentedRBTreeInt<K, V, S, A, P>

where P: TreePolicy<K = K, V = V, S = S>,

pub fn new_in(alloc: A) -> Self

Creates a new, empty AugmentedRBTree with the specified allocator.

pub fn iter(&self) -> Iter<'_, K, V, S>

Returns an iterator over the entries of the tree in sorted order by key.

Examples

let mut tree = AugmentedRBTree::<i32, &str, Unit>::new();
tree.insert(2, "b");
tree.insert(1, "a");
tree.insert(3, "c");

let entries: Vec<_> = tree.iter().collect();
assert_eq!(entries, vec![(&1, &"a", &()), (&2, &"b", &()), (&3, &"c", &())]);

pub fn iter_mut(&mut self) -> IterMut<'_, K, V, S, P>

where P: TreePolicy<K = K, V = V, S = S>,

Returns a mutable iterator over the entries of the tree in sorted order by key.

Examples

let mut tree = AugmentedRBTree::<i32, i32, Unit>::new();
tree.insert(1, 10);
tree.insert(2, 20);

for mut node_guard in tree.iter_mut() {
    *node_guard.value_mut() *= 2;
}

assert_eq!(tree.get(&1), Some(&20));
assert_eq!(tree.get(&2), Some(&40));

pub fn keys(&self) -> Keys<'_, K, V, S>

Returns an iterator over the keys of the tree in sorted order.

Examples

let mut tree = AugmentedRBTree::<i32, &str, Unit>::new();
tree.insert(2, "b");
tree.insert(1, "a");
tree.insert(3, "c");

let keys: Vec<_> = tree.keys().collect();
assert_eq!(keys, vec![&1, &2, &3]);

pub fn values(&self) -> Values<'_, K, V, S>

Returns an iterator over the values of the tree in order by key.

Examples

let mut tree = AugmentedRBTree::<i32, &str, Unit>::new();
tree.insert(2, "b");
tree.insert(1, "a");
tree.insert(3, "c");

let values: Vec<_> = tree.values().collect();
assert_eq!(values, vec![&"a", &"b", &"c"]);

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, S, P>

where P: TreePolicy<K = K, V = V, S = S>,

Returns a mutable iterator over the values of the tree in order by key.

Note

Because this is an augmented tree, this iterator yields a smart guard NodeGuard rather than a raw reference. You must declare the loop variable as mut.

Examples

let mut tree = AugmentedRBTree::<i32, i32, SubtreeSize>::new();
tree.insert(1, 10);
tree.insert(2, 20);

for mut v in tree.values_mut() {
    *v *= 2;
}

assert_eq!(tree.get(&1), Some(&20));
assert_eq!(tree.get(&2), Some(&40));

pub fn stats(&self) -> Stats<'_, K, V, S>

where P: TreePolicy<K = K, V = V, S = S>,

Returns an iterator over the stats of the tree in order by key.

Examples

let mut tree = AugmentedRBTree::<i32, i32, SumAugmentation>::new();
tree.insert(1, 1);
tree.insert(2, 2);
tree.insert(3, 3);

let stats: Vec<_> = tree.stats().map(|x| *x).collect();
assert_eq!(stats, vec![1, 6, 3]);

pub fn range<'a, Q, R>(&'a self, range: R) -> Range<'a, K, V, S>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized + 'a, R: RangeBounds<Q>,

Returns an iterator over a sub-range of entries in the tree.

Constructs a double-ended iterator over a sub-range of entries in the tree. The simplest way is to use the range syntax min..max, thus range(min..max) will yield elements from min (inclusive) to max (exclusive). The range may also be entered as (Bound<T>, Bound<T>).

Panics

Panics if the range start is greater than the range end, or if the range start equals the range end and both bounds are Excluded.

Examples

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
for (k, v) in [(1, "a"), (2, "b"), (3, "c"), (4, "d"), (5, "e")] {
    tree.insert(k, v);
}

let range: Vec<_> = tree.range(2..=4).map(|(k, v, _)| (*k, *v)).collect();
assert_eq!(range, vec![(2, "b"), (3, "c"), (4, "d")]);

pub fn range_mut<'a, Q, R>(&'a mut self, range: R) -> RangeMut<'a, K, V, S, P>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized + 'a, R: RangeBounds<Q>,

Returns a mutable iterator over a sub-range of entries in the tree.

Examples

let mut tree = AugmentedRBTree::<i32, i32, SubtreeSize>::new();
for i in 1..=5 { tree.insert(i, i * 10); }

for mut node_guard in tree.range_mut(2..=4) {
    *node_guard.value_mut() += 1;
}

assert_eq!(tree.get(&2), Some(&21));
assert_eq!(tree.get(&3), Some(&31));
assert_eq!(tree.get(&4), Some(&41));
assert_eq!(tree.get(&1), Some(&10)); // untouched

pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S, A, P>

where K: Ord,

Gets the given key’s corresponding entry in the tree for in-place manipulation.

Examples

let mut tree = AugmentedRBTree::<&str, u32, SubtreeSize>::new();

for word in ["hello", "world", "hello", "rust"] {
    let count = tree.entry(word).or_insert(0);
    *count += 1;
}

assert_eq!(tree.get(&"hello"), Some(&2));
assert_eq!(tree.get(&"world"), Some(&1));
assert_eq!(tree.get(&"rust"), Some(&1));

pub fn visit_topology<F>(&self, visitor: F)

where F: FnMut(&K, Color, Option<&K>, Option<&K>),

Visits each node in the tree and invokes the provided callback function with the current node’s key, color, and its children’s keys (if they exist).

pub fn try_clone(&self) -> Result<Self, OutOfMemoryError>

where K: Clone, V: Clone, A: Allocator + Clone,

Attempts to clone the entire tree, returning a new tree with the same structure and values.

pub fn nav_cursor<Q>( &self, location: TreeLocation<&Q>, ) -> NavCursor<'_, K, V, S>

where K: Borrow<Q> + Ord, Q: Ord,

Initializes an immutable navigation cursor positioned at the specified location within the tree.

The cursor’s starting node is determined dynamically based on the requested variant:

TreeLocation Request	Target Condition
Root	Position at the root node of the tree
At(key)	Find node x for which x == key
LowerBound(Included(key))	Find the smallest node x for which x >= key
LowerBound(Excluded(key))	Find the smallest node x for which x > key
LowerBound(Unbounded)	Find the smallest node x in the tree
UpperBound(Included(key))	Find the largest node x for which x <= key
UpperBound(Excluded(key))	Find the largest node x for which x < key
UpperBound(Unbounded)	Find the largest node x in the tree
Leftmost	Find the smallest node x in the tree
Rightmost	Find the largest node x in the tree

pub fn nav_cursor_mut<Q>( &mut self, location: TreeLocation<&Q>, ) -> NavCursorMut<'_, K, V, S, A, P>

where K: Borrow<Q> + Ord, Q: Ord,

Initializes a mutable navigation cursor positioned at the specified location within the tree.

This cursor allows safely mutating node values or removing the current node from the tree. The initial position rules are identical to the immutable variant:

TreeLocation Request	Target Condition
Root	Position at the root node of the tree
At(key)	Find node x for which x == key
LowerBound(Included(key))	Find the smallest node x for which x >= key
LowerBound(Excluded(key))	Find the smallest node x for which x > key
LowerBound(Unbounded)	Find the smallest node x in the tree
UpperBound(Included(key))	Find the largest node x for which x <= key
UpperBound(Excluded(key))	Find the largest node x for which x < key
UpperBound(Unbounded)	Find the largest node x in the tree
Leftmost	Find the smallest node x in the tree
Rightmost	Find the largest node x in the tree

Trait Implementations

impl<K, V, S, A, P> Clone for AugmentedRBTreeInt<K, V, S, A, P>

where K: Clone, V: Clone, A: Allocator + Clone, P: TreePolicy<K = K, V = V, S = S>,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K, V, S, A: Allocator, P> Debug for AugmentedRBTreeInt<K, V, S, A, P>

where P: TreePolicy<K = K, V = V, S = S>, K: Debug, V: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V, S, P> Default for AugmentedRBTreeInt<K, V, S, Global, P>

where P: TreePolicy<K = K, V = V, S = S>,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, S, A, P> Eq for AugmentedRBTreeInt<K, V, S, A, P>

where P: TreePolicy<K = K, V = V, S = S>, K: Eq, V: Eq, A: Allocator,

impl<K, V, S, A: Allocator, P: TreePolicy<K = K, V = V, S = S>> Extend<(K, V)> for AugmentedRBTreeInt<K, V, S, A, P>

where K: Ord,

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, S, A, P> FromIterator<(K, V)> for AugmentedRBTreeInt<K, V, S, A, P>

where K: Ord, A: Allocator + Default, P: TreePolicy<K = K, V = V, S = S>,

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<K, V, S, A: Allocator, P: TreePolicy<K = K, V = V, S = S>> IntoIterator for AugmentedRBTreeInt<K, V, S, A, P>

fn into_iter(self) -> Self::IntoIter

Consumes the tree and returns an iterator over its entries in sorted order by key.

Examples

let mut tree = AugmentedRBTree::<i32, &str, Unit>::new();
tree.insert(2, "b");
tree.insert(1, "a");
tree.insert(3, "c");

let entries: Vec<_> = tree.into_iter().collect();
assert_eq!(entries, vec![(1, "a"), (2, "b"), (3, "c")]);

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V, S, A, P>

Which kind of iterator are we turning this into?

impl<'a, K, V, S, A: Allocator, P> IntoIterator for &'a AugmentedRBTreeInt<K, V, S, A, P>

where P: TreePolicy<K = K, V = V, S = S>,

type Item = (&'a K, &'a V, &'a S)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V, S>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V, S, A: Allocator, P: TreePolicy<K = K, V = V, S = S>> IntoIterator for &'a mut AugmentedRBTreeInt<K, V, S, A, P>

type Item = NodeGuard<'a, K, V, S, P>

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V, S, P>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, S, A, P> PartialEq for AugmentedRBTreeInt<K, V, S, A, P>

where P: TreePolicy<K = K, V = V, S = S>, K: PartialEq, V: PartialEq, A: Allocator,

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.