Struct panoradix::map::RadixMap

pub struct RadixMap<K: Key + ?Sized, V> { /* fields omitted */ }

A map based on a Radix tree.

Radix trees are a implementation of the Trie data structure, where any node can have N edges, and the keys are split on the edges to save memory. There are no duplicate keys and values aren't only stored on the leaves of the tree.

This structure has the advantage of being fairly memory-efficient by compromising on key insertion speed. There is also quite a bit of fragmentation due to the abundance of heap memory usage in both the tree's structure and the data it contains.

You should probably only use this if you need to search by prefix in a large dataset of strings. Consider using a sorted tree structure, such as a BTreeMap or any implementation of a Binary tree available on crates.io.

The Key trait is left private for safety (see the implementation for str for an explanation). You can think of it as an abstraction over both T slices and str slices. Therefore when specifying the type of K, you'll give either [T] or str.

Methods

impl<K: Key + ?Sized, V> RadixMap<K, V>

pub fn new() -> RadixMap<K, V>

Makes a new empty RadixMap.

Examples

Basic usage:

use panoradix::RadixMap;

let mut map = RadixMap::new();

// entries can now be inserted into the empty map
map.insert("a", 1);

pub fn clear(&mut self)

Clears the map, removing all values.

Examples

Basic usage:

use panoradix::RadixMap;

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

pub fn len(&self) -> usize

Return the number of elements in the map.

Examples

Basic usage:

use panoradix::RadixMap;

let mut m = RadixMap::new();
m.insert("a", 1);
m.insert("b", 2);
m.insert("c", 3);
assert_eq!(m.len(), 3);

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

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated, and the old value is returned.

Examples

Basic usage:

use panoradix::RadixMap;

let mut map = RadixMap::new();
assert_eq!(map.insert("a", 37), None);
assert_eq!(map.is_empty(), false);

map.insert("a", 42);
assert_eq!(map.insert("a", 1337), Some(42));

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

Returns a reference to the value corresponding to the key.

Examples

Basic usage:

use panoradix::RadixMap;

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

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

Returns a mutable reference to the value corresponding to the key. map.insert("a", 0); *map.get_mut("a").unwrap() += 1; *map.get_mut("a").unwrap() += 1; assert_eq!(map.get("a"), Some(&2));

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

Returns if the key was inserted in the map.

Note: this is equivalent to calling get(key).is_some()

Examples

Basic usage:

use panoradix::RadixMap;

let mut map = RadixMap::new();
map.insert("a", 1);
map.insert("b", 2);
assert!(map.contains_key("a"));
assert!(map.contains_key("b"));
assert!(!map.contains_key("c"));

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Examples

Basic usage:

use panoradix::RadixMap;

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

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

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

Examples

Basic usage:

use panoradix::RadixMap;

let mut map = RadixMap::new();
map.insert("a", 1);
assert_eq!(map.remove("a"), Some(1));
assert_eq!(map.remove("a"), None);

Important traits for Iter<'a, K, V>

impl<'a, K: 'a + Key + ?Sized, V: 'a> Iterator for Iter<'a, K, V> type Item = (K::Owned, &'a V);

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

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

Examples

Basic usage:

use panoradix::RadixMap;

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

for (key, value) in map.iter() {
    println!("{}: {}", key, value);
}

let (first_key, first_value) = map.iter().next().unwrap();
assert_eq!((first_key, *first_value), ("a".to_string(), 1));

Important traits for Keys<'a, K, V>

impl<'a, K: 'a + Key + ?Sized, V: 'a> Iterator for Keys<'a, K, V> type Item = K::Owned;

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

Gets an iterator over the keys of the map (sorted).

Examples

Basic usage:

use panoradix::RadixMap;

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

for key in map.keys() {
    println!("{}", key);
}

let first_key = map.keys().next().unwrap();
assert_eq!(first_key, "a".to_string());

Important traits for Values<'a, K, V>

impl<'a, K: 'a + Key + ?Sized, V: 'a> Iterator for Values<'a, K, V> type Item = &'a V;

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

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

Examples

Basic usage:

use panoradix::RadixMap;

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

for value in map.values() {
    println!("{}", value);
}

let first_value = map.values().next().unwrap();
assert_eq!(first_value, &1);

Important traits for Matches<'a, K, V>

impl<'a, K: 'a + Key + ?Sized, V: 'a> Iterator for Matches<'a, K, V> type Item = (K::Owned, &'a V);

pub fn find<'a>(&'a self, key: &K) -> Matches<'a, K, V>

Gets an iterator over a filtered subset of the map, sorted by key.

The iterator resembles iter() since it yields key-value pairs from the map. Note that the full key will be yielded each time, not just the filtered suffix.

Examples

Basic usage:

use panoradix::RadixMap;

let mut map = RadixMap::new();
map.insert("abc", 1);
map.insert("acd", 2);
map.insert("abd", 3);
map.insert("bbb", 1);
map.insert("ccc", 1);

for (key, value) in map.find("a") {
    println!("{}: {}", key, value);
}

let (first_key, first_value) = map.find("a").next().unwrap();
assert_eq!((first_key, first_value), ("abc".to_string(), &1));

Trait Implementations

impl<K: Key + ?Sized, V> Default for RadixMap<K, V>

fn default() -> Self

Returns the "default value" for a type.

impl<K: ?Sized, V, T> FromIterator<(T, V)> for RadixMap<K, V> where
    K: Key,
    T: AsRef<K>, 

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

Creates a value from an iterator.