Struct zerotrie::cursor::ZeroTrieSimpleAsciiCursor

pub struct ZeroTrieSimpleAsciiCursor<'a> {
    trie: ZeroTrieSimpleAscii<&'a [u8]>,
}

A cursor into a ZeroTrieSimpleAscii, useful for stepwise lookup.

For examples, see ZeroTrieSimpleAscii::cursor().

Fields

trie: ZeroTrieSimpleAscii<&'a [u8]>

Implementations

impl<'a> ZeroTrieSimpleAsciiCursor<'a>

pub fn step(&mut self, byte: u8)

Steps the cursor one character into the trie based on the character’s byte value.

Examples

Unrolled loop checking for string presence at every step:

use zerotrie::ZeroTrieSimpleAscii;

// A trie with two values: "abc" and "abcdef"
let trie = ZeroTrieSimpleAscii::from_bytes(b"abc\x80def\x81");

// Search the trie for the string "abcdxy"
let mut cursor = trie.cursor();
assert_eq!(cursor.take_value(), None); // ""
cursor.step(b'a');
assert_eq!(cursor.take_value(), None); // "a"
cursor.step(b'b');
assert_eq!(cursor.take_value(), None); // "ab"
cursor.step(b'c');
assert_eq!(cursor.take_value(), Some(0)); // "abc"
cursor.step(b'd');
assert_eq!(cursor.take_value(), None); // "abcd"
assert!(!cursor.is_empty());
cursor.step(b'x'); // no strings have the prefix "abcdx"
assert!(cursor.is_empty());
assert_eq!(cursor.take_value(), None); // "abcdx"
cursor.step(b'y');
assert_eq!(cursor.take_value(), None); // "abcdxy"

If the byte is not ASCII, the cursor will become empty:

use zerotrie::ZeroTrieSimpleAscii;

// A trie with two values: "abc" and "abcdef"
let trie = ZeroTrieSimpleAscii::from_bytes(b"abc\x80def\x81");

let mut cursor = trie.cursor();
assert_eq!(cursor.take_value(), None); // ""
cursor.step(b'a');
assert_eq!(cursor.take_value(), None); // "a"
cursor.step(b'b');
assert_eq!(cursor.take_value(), None); // "ab"
cursor.step(b'\xFF');
assert!(cursor.is_empty());
assert_eq!(cursor.take_value(), None);

pub fn take_value(&mut self) -> Option<usize>

Takes the value at the current position.

Calling this function on a new cursor is equivalent to calling .get() with the empty string (except that it can only be called once).

Examples

use zerotrie::ZeroTrieSimpleAscii;

// A trie with two values: "" and "abc"
let trie = ZeroTrieSimpleAscii::from_bytes(b"\x80abc\x81");

assert_eq!(Some(0), trie.get(""));
let mut cursor = trie.cursor();
assert_eq!(Some(0), cursor.take_value());
assert_eq!(None, cursor.take_value());

pub fn probe(&mut self, index: usize) -> Option<AsciiProbeResult>

Steps the cursor one character into the trie based on an edge index, returning the corresponding character as a byte.

This function is similar to Self::step(), but it takes an index instead of a char. This enables stepwise iteration over the contents of the trie.

If there are multiple possibilities for the next byte, the index argument allows visiting them in order. Since this function steps the cursor, the cursor must be cloned (a cheap operation) in order to visit multiple children.

Examples

Continually query index 0 to extract the first item from a trie:

use zerotrie::ZeroTrieSimpleAscii;

let data: &[(String, usize)] = &[
    ("ab".to_string(), 111),
    ("abcxyz".to_string(), 22),
    ("abde".to_string(), 333),
    ("afg".to_string(), 44),
];

let trie: ZeroTrieSimpleAscii<Vec<u8>> =
    data.iter().map(|(s, v)| (s.as_str(), *v)).collect();

let mut cursor = trie.cursor();
let mut key = String::new();
let value = loop {
    if let Some(value) = cursor.take_value() {
        break value;
    }
    let probe_result = cursor.probe(0).unwrap();
    key.push(char::from(probe_result.byte));
};

assert_eq!(key, "ab");
assert_eq!(value, 111);

Stepwise iterate over all entries in the trie:

// (trie built as in previous example)

// Initialize the iteration at the first child of the trie.
let mut stack = Vec::from([(trie.cursor(), 0, 0)]);
let mut key = Vec::new();
let mut results = Vec::new();
loop {
    let Some((mut cursor, index, suffix_len)) = stack.pop() else {
        // Nothing left in the trie.
        break;
    };
    // Check to see if there is a value at the current node.
    if let Some(value) = cursor.take_value() {
        results.push((String::from_utf8(key.clone()).unwrap(), value));
    }
    // Now check for children of the current node.
    let mut sub_cursor = cursor.clone();
    if let Some(probe_result) = sub_cursor.probe(index) {
        // Found a child. Add the current byte edge to the key.
        key.push(probe_result.byte);
        // Add the child to the stack, and also add back the current
        // node if there are more siblings to visit.
        if index + 1 < probe_result.total_siblings as usize {
            stack.push((cursor, index + 1, suffix_len));
            stack.push((sub_cursor, 0, 1));
        } else {
            stack.push((sub_cursor, 0, suffix_len + 1));
        }
    } else {
        // No more children. Pop this node's bytes from the key.
        for _ in 0..suffix_len {
            key.pop();
        }
    }
}

assert_eq!(&results, data);

pub fn is_empty(&self) -> bool

Checks whether the cursor points to an empty trie.

Use this to determine when to stop iterating.

Trait Implementations

impl<'a> Clone for ZeroTrieSimpleAsciiCursor<'a>

fn clone(&self) -> ZeroTrieSimpleAsciiCursor<'a>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a> Debug for ZeroTrieSimpleAsciiCursor<'a>

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

Formats the value using the given formatter.

impl<'a> Write for ZeroTrieSimpleAsciiCursor<'a>

fn write_str(&mut self, s: &str) -> Result

Steps the cursor through each ASCII byte of the string.

If the string contains non-ASCII chars, an error is returned.

Examples

use core::fmt::Write;
use zerotrie::ZeroTrieSimpleAscii;

// A trie with two values: "abc" and "abcdef"
let trie = ZeroTrieSimpleAscii::from_bytes(b"abc\x80def\x81");

let mut cursor = trie.cursor();
cursor.write_str("abcdxy").expect("all ASCII");
cursor.write_str("🚂").expect_err("non-ASCII");

fn write_char(&mut self, c: char) -> Result

Equivalent to ZeroTrieSimpleAsciiCursor::step(), except returns an error if the char is non-ASCII.

Examples

use core::fmt::Write;
use zerotrie::ZeroTrieSimpleAscii;

// A trie with two values: "abc" and "abcdef"
let trie = ZeroTrieSimpleAscii::from_bytes(b"abc\x80def\x81");

let mut cursor = trie.cursor();
cursor.write_char('a').expect("ASCII");
cursor.write_char('x').expect("ASCII");
cursor.write_char('🚂').expect_err("non-ASCII");

fn write_fmt(&mut self, args: Arguments<'_>) -> Result<(), Error>

Glue for usage of the write! macro with implementors of this trait.