Struct datazoo::bimultimap::Bimultimap

pub struct Bimultimap<K: Eq + Ord, V: Eq + Ord> { /* private fields */ }

A read-only bi-directional multimap.

This has very good perf for small sets of key and values that themselves shouldn’t take much memory.

Furthermore, not only can you get all values associated with a given key, but also all keys associated with a given value. See Bimultimap::get_keys_of and Bimultimap::get.

Design

Consider K = char and V = i64. A Bimultimap stores a limited subset of char and i64 and an association list.

Keys and values are stored in two sorted lists, associations in a bitset matrix.

Keys

E	G	H	M	S	T

Values

-5	-1	10	342	1024

Associations

	E	G	H	M	S	T
-5			█	█		█
-1	█	█				█
10			█	█
342		█	█		█
1024						█

Example

use datazoo::Bimultimap;

let associations: Vec<(char, i64)> = vec![
    ('E', -1),
    ('G', -1), ('G', 342),
    ('H', -5), ('H', 10), ('H', 342),
    ('M', -5), ('M', 10),
    ('S', 342),
    ('T',-5), ('T',-1), ('T',1024),
];
let map: Bimultimap<char, i64> = associations.into_iter().collect();

let assocs = map.get(&'V').copied().collect::<Vec<_>>();
assert_eq!(&assocs, &[]);

let assocs = map.get(&'T').copied().collect::<Vec<_>>();
assert_eq!(&assocs, &[-5, -1, 1024]);

let assocs = map.get_keys_of(&-1).copied().collect::<Vec<_>>();
assert_eq!(&assocs, &['E', 'G', 'T']);

Implementations

impl<K: Eq + Ord, V: Eq + Ord> Bimultimap<K, V>

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

All keys present in this map, sorted.

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

All values present in this map, sorted.

pub fn get(&self, key: &K) -> impl SortedIterator<Item = &V> + '_

Get all values associated with key.

pub fn get_keys_of(&self, value: &V) -> impl SortedIterator<Item = &K> + '_

Get all keys associated with value.

Trait Implementations

impl<K: Eq + Ord + Debug, V: Eq + Ord + Debug> Debug for Bimultimap<K, V>

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

Formats the value using the given formatter.

impl<K: Eq + Ord + Clone, V: Eq + Ord + Clone> FromIterator<(K, V)> for Bimultimap<K, V>

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

Create a Bimultimap with all associations.

Note that this takes into account