Struct rankmap::rank_map::rank_map::RankMap

pub struct RankMap<K, V, R, S = RandomState> { /* private fields */ }

A hash map that supports key ranking. The rank can be used to get the element with the lowest rank in O(1) time, iterate over map’s keys and values from the lowest rank to the highest in O(N) or remove the element with the lowest rank in O(log(N)).

Implementation details:

Rank map is implemented using bi-directional references from the hash-table to the binary-heap and back which helps to get rid of hash-table lookups during binary-heap sift ups and downs:

             MAP                                        HEAP
╔═══╤══════╤═════════════════╗                 ╔═══╤════════════════╗
║idx│ key  │(value, heap-idx)║                 ║idx│(value, map-idx)║
╠═══╪══════╪═════════════════╣                 ╠═══╪════════════════╣
║ 0 │ key0 │   (value0, 0)   ║ ◀━━━━━━━━━━━━━▶ ║ 0 │   (rank0, 0)   ║
╟───┼──────┼─────────────────╢                 ╟───┼────────────────╢
║ 1 │ key1 │   (value1, 3)   ║ ◀━━━━┓  ┏━━━━━▶ ║ 1 │   (rank1, 2)   ║
╟───┼──────┼─────────────────╢      ┃  ┃       ╟───┼────────────────╢
║ 2 │ key2 │   (value2, 1)   ║ ◀━━━━━━━┛  ┏━━▶ ║ 2 │   (rank2, 3)   ║
╟───┼──────┼─────────────────╢      ┃     ┃    ╟───┼────────────────╢
║ 3 │ key3 │   (value3, 2)   ║ ◀━┓  ┗━━━━━━━━▶ ║ 3 │   (rank3, 1)   ║
╟───┼──────┼─────────────────╢   ┃        ┃    ╟───┼────────────────╢
╏               ...          ╏   ┗━━━━━━━━┛    ╏          ...       ╏
╟───┼──────┼─────────────────╢                 ╟───┼────────────────╢
║ N │ keyN │  (valueN, ...)  ║                 ║ N │  (rankN, ...)  ║
╚═══╧══════╧═════════════════╝                 ╚═══╧════════════════╝

Implementations

impl<K, V, R, S> RankMap<K, V, R, S>where R: PartialOrd + Copy,

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

Returns an iterator visiting all keys from the lowest rank to the highest.

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

Returns an iterator visiting all values from the lowest rank to the highest.

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

Returns a mutable iterator visiting all values from the lowest rank to the highest.

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

An iterator visiting all key-value pairs from the lowest rank to the highest.

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

Returns a mutable iterator visiting all key-value pairs from the lowest rank to the highest.

impl<K, V, R, S> RankMap<K, V, R, S>where K: Hash + Eq, R: PartialOrd + Copy, S: BuildHasher,

pub fn into_keys(self) -> IntoKeys<K>

pub fn into_values(self) -> IntoValues<V>

impl<K, V, R> RankMap<K, V, R>

pub fn new() -> Self

Creates an empty RankMap.

pub fn with_capacity(capacity: usize) -> Self

Creates an empty RankMap pre-allocating memory for the specified number of elements.

impl<K, V, R, S> RankMap<K, V, R, S>

pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self

Creates an empty RankMap pre-allocating memory for the specified number of elements, using hash_builder to hash the keys.

pub fn with_hasher(hash_builder: S) -> Self

Creates an empty RankMap which will use the given hash builder to hash keys.

pub fn hasher(&self) -> &S

Returns a reference to the map’s BuildHasher.

impl<K, V, R, S> RankMap<K, V, R, S>

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold without reallocation.

pub fn len(&self) -> usize

Returns the number of elements in the map.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

impl<K, V, R, S> RankMap<K, V, R, S>where K: Hash + Eq, S: BuildHasher,

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

Returns a reference to the value stored by the provided key if it is present, otherwise returns None.

Time complexity

Takes O(1) on average.

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

Returns a mutable reference to the value stored by the provided key if it is present, otherwise returns None.

Time complexity

Takes O(1) on average.

pub fn contains_key<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Checks if the item with the provided key exists in the map.

Time complexity

Takes O(1) on average.

pub fn shrink_to_fit(&mut self)

Shrink the capacity of the map as much as possible.

pub fn shrink_to(&mut self, min_capacity: usize)

Shrinks the capacity of the map with a lower limit.

pub fn clear(&mut self)

Clears the map.

Note: that this method has no effect on the map capacity.

impl<K, V, R, S> RankMap<K, V, R, S>where K: Hash + Eq, R: PartialOrd + Copy, S: BuildHasher,

pub fn get_with_rank<Q>(&self, key: &Q) -> Option<(&V, R)>where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value and the rank stored by the provided key if it is present, otherwise returns None.

Time complexity

Takes O(1) on average.

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

Inserts the item in the map and returns None or replaces the item with the same key returning it.

Time complexity

Takes O(log(N)) on average.

pub fn remove<Q>(&mut self, key: &Q) -> Option<(V, R)>where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes the item from the map by the key and returns it, or None if it is not found.

Time complexity

Takes O(log(N)) on average.

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

Removes the smallest item from the map and returns it, or None if it is empty.

Time complexity

Takes O(log(N)) on average.

pub fn top(&self) -> Option<(&K, &V, R)>

Returns the smallest item in the map, or None if it is empty.

Time complexity

Takes O(1).

Trait Implementations

impl<K, V, R, S> Clone for RankMap<K, V, R, S>where K: Clone, V: Clone, S: Clone, R: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug, R: Debug, S: Debug> Debug for RankMap<K, V, R, S>

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

Formats the value using the given formatter.

impl<K, V, R> Default for RankMap<K, V, R>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, R> Extend<(K, V, R)> for RankMap<K, V, R>where K: Hash + Eq, R: PartialOrd + Copy,

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

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<Q, K, V, R> Index<&Q> for RankMap<K, V, R>where K: Hash + Eq + Borrow<Q>, Q: Hash + Eq + ?Sized,

type Output = V

The returned type after indexing.

fn index(&self, index: &Q) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<Q, K, V, R> IndexMut<&Q> for RankMap<K, V, R>where K: Hash + Eq + Borrow<Q>, Q: Hash + Eq + ?Sized,

fn index_mut(&mut self, index: &Q) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'m, K, V, R, S> IntoIterator for &'m RankMap<K, V, R, S>where R: PartialOrd + Copy,

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

The type of the elements being iterated over.

type IntoIter = Iter<'m, K, V, R, S>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'m, K, V, R, S> IntoIterator for &'m mut RankMap<K, V, R, S>where R: PartialOrd + Copy,

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

The type of the elements being iterated over.

type IntoIter = IterMut<'m, K, V, R, S>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, R, S> IntoIterator for RankMap<K, V, R, S>where K: Hash + Eq, R: PartialOrd + Copy, S: BuildHasher,

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.