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>

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);

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());

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));

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);

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());

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);

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));

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());

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);

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.