Struct AvlTreeMap

pub struct AvlTreeMap<K, V> { /* private fields */ }

An ordered map implemented with an AVL tree.

use avl::AvlTreeMap;
let mut map = AvlTreeMap::new();
map.insert(0, "zero");
map.insert(1, "one");
map.insert(2, "two");
assert_eq!(map.get(&1), Some(&"one"));
map.remove(&1);
assert!(map.get(&1).is_none());

Implementations

impl<K, V> AvlTreeMap<K, V>

pub fn new() -> Self

where K: Ord,

Creates an empty map. No memory is allocated until the first item is inserted.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn len(&self) -> usize

Returns the number of elements in the map.

pub fn clear(&mut self)

Clears the map, deallocating all memory.

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

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

Returns a reference to the value corresponding to the key.

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

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

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

Returns a mutable reference to the value corresponding to the key.

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

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

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

Returns references to the key-value pair corresponding to the key.

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

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

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

Returns true if the key is in the map, else false.

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

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

where K: Ord,

Inserts a key-value pair into the map. Returns None if the key is not in the map. Updates the value if the key is already in the map and returns the old value.

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

where K: Ord,

Gets the map entry of given key for in-place manipulation.

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

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

Removes a key from the map. Returns the value at the key if the key was previously in the map.

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

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

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

Removes a key from the map. Returns the stored key and value if the key was previously in the map.

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

pub fn append(&mut self, other: &mut Self)

where K: Ord,

Moves all elements from other into self, leaving other empty.

pub fn split_off<Q>(&mut self, key: &Q) -> Self

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

Splits the collection into two at the given key. Returns everything after the given key, including the key.

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

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

Gets an iterator over a range of elements in the map, in order by key.

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

Panics

Panics if range start > end. Panics if range start == end and both bounds are Excluded.

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

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

Gets a mutable iterator over a range of elements in the map, in order by key.

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

Panics

Panics if range start > end. Panics if range start == end and both bounds are Excluded.

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

Gets an iterator over the entries of the map, sorted by key.

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

Gets an iterator over the keys of the map, in sorted order.

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

Gets an iterator over the values of the map, in order by key.

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

Gets a mutable iterator over the values of the map, in order by key.

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

Gets a mutable iterator over the entries of the map, sorted by key.

pub fn traverse_level_order<F>(&self, f: F)

where F: FnMut(usize, &K, &V),

Traverses the map in level-order and calls the given closure for each level-key-value triple.

Trait Implementations

impl<K: Clone, V: Clone> Clone for AvlTreeMap<K, V>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V> Debug for AvlTreeMap<K, V>

where K: Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K: Ord, V> Default for AvlTreeMap<K, V>

fn default() -> Self

Creates an empty map.

impl<K, V> Drop for AvlTreeMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K, V> Extend<(&'a K, &'a V)> for AvlTreeMap<K, V>

where K: Ord + Copy, V: Copy,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = (&'a K, &'a V)>,

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: Ord, V> Extend<(K, V)> for AvlTreeMap<K, V>

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = (K, V)>,

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: Ord, V> FromIterator<(K, V)> for AvlTreeMap<K, V>

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

Creates a value from an iterator.

impl<K: Hash, V: Hash> Hash for AvlTreeMap<K, V>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<Q, K, V> Index<&Q> for AvlTreeMap<K, V>

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

fn index(&self, key: &Q) -> &V

Returns a reference to the value for the given key.

Panics

Panics if the key is not present in the map.

type Output = V

The returned type after indexing.

impl<'a, K, V> IntoIterator for &'a AvlTreeMap<K, V>

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

The type of the elements being iterated over.

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

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> IntoIterator for &'a mut AvlTreeMap<K, V>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V> IntoIterator for AvlTreeMap<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Ord, V: Ord> Ord for AvlTreeMap<K, V>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<K: PartialEq, V: PartialEq> PartialEq for AvlTreeMap<K, V>

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: PartialOrd, V: PartialOrd> PartialOrd for AvlTreeMap<K, V>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K: Eq, V: Eq> Eq for AvlTreeMap<K, V>

impl<K, V> Send for AvlTreeMap<K, V>

where K: Send, V: Send,

impl<K, V> Sync for AvlTreeMap<K, V>

where K: Sync, V: Sync,