Struct Trie 

pub struct Trie { /* private fields */ }

A trie over strings, split into Unicode scalar values, with a weight per term.

Implementations

impl Trie

pub fn build(items: &[(&str, u16)]) -> Result<Trie, BuildError>

Builds a trie. Duplicate terms are merged, keeping the entry with the highest weight (the first one among equal weights).

Term ids are positions in the byte-sorted, deduplicated list, not positions in items; Trie::input_index maps an id back to the index in items of the entry that was kept.

Terms are stored as given, one symbol per code point, without any folding: for ASCII this is the behaviour of earlier versions exactly. Trie::build_normalized folds case and diacritics.

pub fn build_normalized( items: &[(&str, u16)], normalizer: &Normalizer, ) -> Result<Trie, BuildError>

Builds a trie of the terms normalised by normalizer, and remembers it so that Searcher::search_text normalises queries the same way.

Terms that are equal after normalisation are merged as by Trie::build (highest weight, then first); Trie::term returns the normalised text and Trie::input_index the index in items of the entry kept, from which the caller recovers its original spelling.

use keyhammer::text::Normalizer;
use keyhammer::trie::Trie;

let items = [("Café", 5), ("cafe", 9), ("São Paulo", 1)];
let trie = Trie::build_normalized(&items, &Normalizer::new()).unwrap();
assert_eq!(trie.len(), 2);
assert_eq!(trie.term(0), "cafe");
assert_eq!(trie.input_index(0), 1); // "cafe" (weight 9) was kept
assert_eq!(trie.term(1), "sao paulo");
assert_eq!(trie.normalizer(), Some(Normalizer::new()));

pub fn normalizer(&self) -> Option<Normalizer>

The normaliser the trie was built with (Trie::build_normalized), or None (Trie::build).

pub fn len(&self) -> usize

Number of distinct terms.

pub fn is_empty(&self) -> bool

Whether the trie holds no terms (never true for a built trie).

pub fn node_count(&self) -> usize

Number of trie nodes, root included.

pub fn term(&self, id: u32) -> &str

The term with the given id.

pub fn weight(&self, id: u32) -> u16

The weight of the term with the given id.

pub fn input_index(&self, id: u32) -> u32

The index, in the slice given to Trie::build, of the entry kept for the term with the given id: for duplicates, the entry with the highest weight, and the first one among equal weights. Returns u32::MAX for an out-of-range id.

pub fn label(&self, v: usize) -> char

The symbol on the edge leading into node v, as a char ('\0' for the root).

Panics

Panics if v is not a node index, that is, if v >= self.node_count(). Unlike Trie::term, Trie::weight and Trie::input_index, which answer for an unknown id, the per-node accessors index directly.

Examples

use keyhammer::trie::Trie;
let trie = Trie::build(&[("car", 9), ("cat", 4)]).unwrap();
// Nodes in breadth-first order: root, c, a, r, t.
assert_eq!(trie.node_count(), 5);
assert_eq!(trie.label(0), '\0');
assert_eq!(trie.label(1), 'c');
assert_eq!(trie.label(4), 't');
// One node per code point, not per UTF-8 byte.
let trie = Trie::build(&[("né", 1)]).unwrap();
assert_eq!(trie.node_count(), 3);
assert_eq!(trie.label(2), 'é');

An index past the last node panics:

let trie = Trie::build(&[("a", 1)]).unwrap();
trie.label(trie.node_count());

pub fn children(&self, v: usize) -> Range<usize>

The node indices of the children of v.

Panics

Panics if v is not a node index, that is, if v >= self.node_count(). Unlike Trie::term, Trie::weight and Trie::input_index, which answer for an unknown id, the per-node accessors index directly.

Examples

use keyhammer::trie::Trie;
let trie = Trie::build(&[("car", 9), ("cat", 4)]).unwrap();
// Nodes in breadth-first order: root, c, a, r, t.
assert_eq!(trie.node_count(), 5);
assert_eq!(trie.children(0), 1..2);
assert_eq!(trie.children(2), 3..5); // a -> r, t
assert!(trie.children(3).is_empty());

pub fn term_id(&self, v: usize) -> u32

The id of the term that ends at v, or NO_TERM.

Panics

Panics if v is not a node index, that is, if v >= self.node_count(). Unlike Trie::term, Trie::weight and Trie::input_index, which answer for an unknown id, the per-node accessors index directly.

Examples

use keyhammer::trie::{NO_TERM, Trie};
let trie = Trie::build(&[("car", 9), ("cat", 4)]).unwrap();
// Nodes in breadth-first order: root, c, a, r, t.
assert_eq!(trie.node_count(), 5);
assert_eq!(trie.term_id(0), NO_TERM);
assert_eq!(trie.term_id(3), 0); // "car"
assert_eq!(trie.term_id(4), 1); // "cat"

pub fn max_weight(&self, v: usize) -> u16

The largest weight among the terms at or below v.

Panics

Panics if v is not a node index, that is, if v >= self.node_count(). Unlike Trie::term, Trie::weight and Trie::input_index, which answer for an unknown id, the per-node accessors index directly.

Examples

use keyhammer::trie::Trie;
let trie = Trie::build(&[("car", 9), ("cat", 4)]).unwrap();
// Nodes in breadth-first order: root, c, a, r, t.
assert_eq!(trie.node_count(), 5);
assert_eq!(trie.max_weight(0), 9);
assert_eq!(trie.max_weight(4), 4);

pub fn len_min(&self, v: usize) -> u16

The length, in symbols, of the shortest term at or below v.

Panics

Panics if v is not a node index, that is, if v >= self.node_count(). Unlike Trie::term, Trie::weight and Trie::input_index, which answer for an unknown id, the per-node accessors index directly.

Examples

use keyhammer::trie::Trie;
let trie = Trie::build(&[("a", 1), ("abc", 1)]).unwrap();
assert_eq!(trie.len_min(0), 1);
assert_eq!(trie.len_min(trie.children(0).start), 1);

pub fn len_max(&self, v: usize) -> u16

The length, in symbols, of the longest term at or below v.

Panics

Panics if v is not a node index, that is, if v >= self.node_count(). Unlike Trie::term, Trie::weight and Trie::input_index, which answer for an unknown id, the per-node accessors index directly.

Examples

use keyhammer::trie::Trie;
let trie = Trie::build(&[("a", 1), ("abc", 1)]).unwrap();
assert_eq!(trie.len_max(0), 3);
let a = trie.children(0).start;
assert_eq!(trie.len_max(a), 3);

pub fn below_mask(&self, v: usize) -> u64

The symbol classes (symbol_class) that appear on edges strictly below v.

Panics

Panics if v is not a node index, that is, if v >= self.node_count(). Unlike Trie::term, Trie::weight and Trie::input_index, which answer for an unknown id, the per-node accessors index directly.

Examples

use keyhammer::cost::symbol_class;
use keyhammer::trie::Trie;
let trie = Trie::build(&[("ab", 1)]).unwrap();
let a = trie.children(0).start;
let class = |c: char| symbol_class(c.into());
assert_eq!(trie.below_mask(0), class('a') | class('b'));
assert_eq!(trie.below_mask(a), class('b')); // not its own edge
let b = trie.children(a).start;
assert_eq!(trie.below_mask(b), 0);

Trait Implementations

impl Clone for Trie

fn clone(&self) -> Trie

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Trie

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

Formats the value using the given formatter.