Struct aatree::map::AATreeMap

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

Implementations

impl<K, V> AATreeMap<K, V>

pub fn get<Q>(&self, key: &Q) -> Option<&V>where
    K: Ord + Borrow<Q>,
    Q: Ord + ?Sized,

Returns a reference to the value corresponding to the key.

Example

let mut map = AATreeMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>where
    K: Ord + Borrow<Q>,
    Q: Ord + ?Sized,

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

Example

let mut map = AATreeMap::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);

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

Gets the given key’s corresponding entry, allowing for in-place manipulation of the entry as well as inserting an entry with that key if it does not exist yet.

Example

let mut map = AATreeMap::new();
let entry = map.entry(1);
assert!(matches!(entry, Entry::Vacant(_)));
entry.or_insert('a');
assert_eq!(map.get(&1), Some(&'a'));

let entry = map.entry(1);
assert!(matches!(entry, Entry::Occupied(_)));
entry.and_modify(|value| *value = 'b');
assert_eq!(map.get(&1), Some(&'b'));

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>where
    K: Ord + Borrow<Q>,
    Q: Ord + ?Sized,

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

Example

let mut map = AATreeMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
*map.get_mut(&1).unwrap() = "b";
assert_eq!(map.get(&1), Some(&"b"));

pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>where
    K: Ord + Debug,
    V: Debug,

Gets the first entry (that is, with the smallest key) in the map, allowing for in-place manipulation of the entry.

Example

let mut map = AATreeMap::new();
let entry = map.first_entry();
assert!(entry.is_none());

map.insert(1, 'a');
map.insert(3, 'c');
println!("{map:?}");

let Some(mut entry) = map.first_entry() else { unreachable!() };
*entry.get_mut() = 'b';
assert_eq!(map.get(&1), Some(&'b'));
assert_eq!(map.get(&3), Some(&'c'));

pub fn first_key_value(&self) -> Option<(&K, &V)>where
    K: Ord,

Returns a reference to the first entry (that is, with the smallest key) in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.first_key_value(), None);
map.insert(3, "a");
map.insert(1, "b");
map.insert(2, "c");
assert_eq!(map.first_key_value(), Some((&1, &"b")));

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

Returns and removes the first entry (that is, with the smallest key) in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.pop_first(), None);
map.insert(3, "a");
map.insert(1, "b");
map.insert(2, "c");
assert_eq!(map.pop_first(), Some((1, "b")));
assert_eq!(map.pop_first(), Some((2, "c")));
assert_eq!(map.pop_first(), Some((3, "a")));
assert_eq!(map.pop_first(), None);

pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>where
    K: Ord,

Gets the last entry (that is, with the largest key) in the map, allowing for in-place manipulation of the entry.

Example

let mut map = AATreeMap::new();
let entry = map.last_entry();
assert!(entry.is_none());

map.insert(1, 'a');
map.insert(3, 'c');

let Some(mut entry) = map.last_entry() else { unreachable!() };
*entry.get_mut() = 'b';
assert_eq!(map.get(&1), Some(&'a'));
assert_eq!(map.get(&3), Some(&'b'));

pub fn last_key_value(&self) -> Option<(&K, &V)>where
    K: Ord,

Returns a reference to the last entry (that is, with the largest key) in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.last_key_value(), None);
map.insert(1, "a");
map.insert(3, "b");
map.insert(2, "c");
assert_eq!(map.last_key_value(), Some((&3, &"b")));

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

Returns and removes the last entry (that is, with the largest key) in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.pop_last(), None);
map.insert(1, "a");
map.insert(3, "b");
map.insert(2, "c");
assert_eq!(map.pop_last(), Some((3, "b")));
assert_eq!(map.pop_last(), Some((2, "c")));
assert_eq!(map.pop_last(), Some((1, "a")));
assert_eq!(map.pop_last(), None);

pub fn pop_largest(&mut self) -> Option<(K, V)>where
    K: Ord,

pub fn first_key_value_at_or_after<Q>(&self, k: &Q) -> Option<(&K, &V)>where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Returns a reference to the first entry with a key greater than or equal to k in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.first_key_value_at_or_after(&15), None);
map.insert(10, "a");
map.insert(30, "b");
map.insert(20, "c");
assert_eq!(map.first_key_value_at_or_after(&15), Some((&20, &"c")));

pub fn first_key_value_mut_at_or_after<Q>(
    &mut self,
    k: &Q
) -> Option<(&K, &mut V)>where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Returns a mutable reference to the first entry with a key greater than or equal to k in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.first_key_value_mut_at_or_after(&15), None);
map.insert(10, "a");
map.insert(30, "b");
map.insert(20, "c");
let (_, value) = map.first_key_value_mut_at_or_after(&15).unwrap();
assert_eq!(*value, "c");
*value = "d";
assert_eq!(map.first_key_value_at_or_after(&15), Some((&20, &"d")));

pub fn last_key_value_at_or_before<Q>(&self, k: &Q) -> Option<(&K, &V)>where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Returns a reference to the last entry with a key smaller than or equal to k in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.last_key_value_at_or_before(&25), None);
map.insert(10, "a");
map.insert(30, "b");
map.insert(20, "c");
assert_eq!(map.last_key_value_at_or_before(&25), Some((&20, &"c")));

pub fn last_key_value_mut_at_or_before<Q>(
    &mut self,
    k: &Q
) -> Option<(&K, &mut V)>where
    K: Borrow<Q> + Ord + Debug,
    V: Debug,
    Q: Ord + ?Sized,

Returns a mutable reference to the last entry with a key smaller than or equal to k in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.last_key_value_mut_at_or_before(&25), None);
map.insert(10, "a");
map.insert(30, "b");
map.insert(20, "c");
let (_, value) = map.last_key_value_mut_at_or_before(&25).unwrap();
assert_eq!(*value, "c");
*value = "d";
assert_eq!(map.last_key_value_at_or_before(&25), Some((&20, &"d")));

impl<K, V> AATreeMap<K, V>

pub const fn new() -> Self

Construct a new, empty AA-Tree based map.

Example

let map = AATreeMap::new();
assert!(map.is_empty());

pub fn len(&self) -> usize

Returns the number of elements in the map.

Example

let mut map = AATreeMap::new();
assert_eq!(map.len(), 0);
map.insert(1, "a");
assert_eq!(map.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Example

let mut map = AATreeMap::new();
assert!(map.is_empty());
map.insert(1, "a");
assert!(!map.is_empty());

pub fn clear(&mut self)

Clears the map, removing all elements.

Example

let mut map = AATreeMap::new();
map.insert(1, "a");
map.clear();
assert!(map.is_empty());

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

Creates an iterator over this map that visits all entries with the keys in ascending order.

pub fn keys(&self) -> impl Iterator<Item = &K>

Creates an iterator visiting all the keys, in sorted order.

pub fn values(&self) -> impl Iterator<Item = &V>

Creates an iterator visiting all the values, in sorted order.

pub fn into_keys(self) -> impl Iterator<Item = K>

Creates a consuming iterator visiting all the keys, in sorted order. The map cannot be used after calling this.

pub fn into_values(self) -> impl Iterator<Item = V>

Creates a consuming iterator visiting all the values, in order by key. The map cannot be used after calling this.

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

Insert a new element into the map, or overwrite an existing element with the same key. If a value was overwritten, the old value will be returned.

Example

let mut map = AATreeMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
map.insert(1, "b");
assert_eq!(map.get(&1), Some(&"b"));

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

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

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");

let mut b = BTreeMap::new();
b.insert(3, "d");
b.insert(4, "e");
b.insert(5, "f");

a.append(&mut b);

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");
assert_eq!(a[&3], "d");
assert_eq!(a[&4], "e");
assert_eq!(a[&5], "f");

pub fn contains_key<Q>(&self, k: &Q) -> boolwhere
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Check if a key is contained within this map.

Example

let mut map = AATreeMap::new();
assert!(!map.contains_key(&1));
map.insert(1, "a");
assert!(map.contains_key(&1));

pub fn remove<Q>(&mut self, k: &Q) -> Option<V>where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Remove a key from the map if it exists, and return the value that was previously stored in the map for that key.

Example

let mut map = AATreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
assert_eq!(map.get(&1), Some(&"a"));
let value = map.remove(&1);
assert_eq!(value, Some("a"));
assert_eq!(map.get(&1), None);

pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Remove a key from the map if it exists, and return the key and the value that was previously stored in the map for that key.

Example

let mut map = AATreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
assert_eq!(map.get(&1), Some(&"a"));
let value = map.remove(&1);
assert_eq!(value, Some("a"));
assert_eq!(map.get(&1), None);

Trait Implementations

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

fn clone(&self) -> AATreeMap<K, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for AATreeMap<K, V>

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

Formats the value using the given formatter.

impl<K, V> Default for AATreeMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K, V> Deserialize<'de> for AATreeMap<K, V>where
    K: Deserialize<'de> + Ord,
    V: Deserialize<'de>,

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>where
    D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, K: Ord + Copy + 'a, V: Ord + Copy + 'a> Extend<(&'a K, &'a V)> for AATreeMap<K, V>

fn extend<I: IntoIterator<Item = (&'a K, &'a 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: Ord, V> Extend<(K, V)> for AATreeMap<K, V>

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: Ord, V, const N: usize> From<[(K, V); N]> for AATreeMap<K, V>

fn from(array: [(K, V); N]) -> Self

Converts to this type from the input type.

impl<K: Ord, V> From<Vec<(K, V), Global>> for AATreeMap<K, V>

fn from(vec: Vec<(K, V)>) -> Self

Converts to this type from the input type.

impl<K: Ord, V> FromIterator<(K, V)> for AATreeMap<K, V>

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

Creates a value from an iterator.

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

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

The type of the elements being iterated over.

type IntoIter = AAIter<'a, KeyValue<K, V>, (&'a K, &'a 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 AATreeMap<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = AAIntoIter<KeyValue<K, V>, (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, T> OpenapiType for AATreeMap<K, T>where
    T: OpenapiType,

fn visit_type<V: Visitor>(visitor: &mut V)

fn schema() -> OpenapiSchema

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

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

This method returns an Ordering between self and other.

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

Compares and returns the maximum of two values.

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

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

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

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<K: PartialOrd, V: PartialOrd> PartialOrd<AATreeMap<K, V>> for AATreeMap<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

This method tests less than (for self and other) and is used by the < operator.

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

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

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

This method tests greater than (for self and other) and is used by the > operator.

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

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

impl<K, V> Serialize for AATreeMap<K, V>where
    K: Serialize,
    V: Serialize,

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>where
    S: Serializer,

Serialize this value into the given Serde serializer.

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