Struct set_trie::SetTrie

pub struct SetTrie<K, T>(_);

SetTries allow for efficient subset and superset queries. Think of it as a HashMap, where you want the key to be within or containing a range.

let mut trie = set_trie::SetTrie::new();

trie.insert(&[1, 3, 5], "foo");
trie.insert(&[3], "bar");

assert_eq!(trie.subsets(&[&1, &3, &5, &6]).collect::<Vec<_>>(), vec![&"foo", &"bar"]);
assert_eq!(trie.supersets(&[&5]).collect::<Vec<_>>(), vec![&"foo"])

Restrictions

Keys are required to be Ord, as the trie stores the nodes in sorted order by key. This means that the caller must ensure that provided keys are in sorted order, lest nonsensical results be returned.

Performance

Subsets and Supersets are lazily evaluated. Note that superset queries are far more expensive than subset queries, so attempt to structure your problem around subsets.

Implementations

impl<K, T> SetTrie<K, T>

#[must_use]pub const fn new() -> Self

Create a new, empty SetTrie, without allocating any space for the nodes.

impl<K, T> SetTrie<K, T> where
    K: Ord, 

#[must_use]pub fn entry<IK: IntoIterator<Item = K>>(
    &mut self,
    keys: IK
) -> EntryBuilder<'_, K, T, IK::IntoIter>

A view into a single node in the trie; which must either be created or already exists.

pub fn insert(&mut self, keys: impl IntoIterator<Item = K>, item: T)

Insert the item in the given node. Will create the node if needed.

pub fn insert_many<IK: IntoIterator<Item = K>, IT: IntoIterator<Item = T>>(
    &mut self,
    keys: IK,
    item: IT
)

Inserts multiple items in the given node. More performant that repeatedly calling insert.

#[must_use]pub fn subsets<'a, 'b>(&'a self, keys: &'b [K]) -> Subset<'a, 'b, K, T>

Iterates over all subsets of keys using DFS, meaning that the keys are visited in order of the query:

let mut trie = set_trie::SetTrie::new();
trie.insert(&[1], "foo");
trie.insert(&[1, 2], "bar");
trie.insert(&[1, 2, 3], "baz");

assert_eq!(trie.subsets(&[&1, &2, &3]).collect::<Vec<_>>(), vec![&"foo", &"bar", &"baz"]);

#[must_use]pub fn values(&self) -> Values<'_, K, T>

Iterates over all values in the trie using DFS, meaning that values are visited in order of the keys stored in the trie.

let mut trie = set_trie::SetTrie::new();
trie.insert(&[1], "foo");
trie.insert(&[1, 2], "bar");
trie.insert(&[1, 2, 3], "baz");

assert_eq!(trie.values().collect::<Vec<_>>(), vec![&"foo", &"bar", &"baz"]);

#[must_use]pub fn supersets<'a, 'b>(&'a self, keys: &'b [K]) -> SuperSet<'a, 'b, K, T>

Iterates over all supersets of keys in the trie using DFS, meaning that values are visited in order of the query.

let mut trie = set_trie::SetTrie::new();
trie.insert(&[1], "foo");
trie.insert(&[1, 2], "bar");
trie.insert(&[1, 2, 3], "baz");

assert_eq!(trie.supersets(&[&1]).collect::<Vec<_>>(), vec![&"foo", &"bar", &"baz"]);

Remarks

Note that the empty set will provide the same result as values. There is currently no fast path in the trie, so if you know that your query contains no keys, use SetTrie::values instead.

Trait Implementations

impl<K: Debug, T: Debug> Debug for SetTrie<K, T>

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

Formats the value using the given formatter.

impl<K: Default, T: Default> Default for SetTrie<K, T>

fn default() -> SetTrie<K, T>

Returns the "default value" for a type.

impl<I, K, T> Extend<(I, T)> for SetTrie<K, T> where
    I: IntoIterator<Item = K>,
    K: Ord, 

fn extend<F: IntoIterator<Item = (I, T)>>(&mut self, iter: F)

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub 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<I, K, T> FromIterator<(I, T)> for SetTrie<K, T> where
    I: IntoIterator<Item = K>,
    K: Ord, 

fn from_iter<F: IntoIterator<Item = (I, T)>>(iter: F) -> Self

Creates a value from an iterator.