impl ZeroTrieSimpleAsciiCursor<'_>

fn step(self: &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);

fn take_value(self: &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());

fn probe(self: &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:

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

fn is_empty(self: &Self) -> bool

Checks whether the cursor points to an empty trie.

Use this to determine when to stop iterating.

impl Write for ZeroTrieSimpleAsciiCursor<'_>

fn write_str(self: &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(self: &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");

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

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

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

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

impl<'a> Freeze for ZeroTrieSimpleAsciiCursor<'a>

impl<'a> RefUnwindSafe for ZeroTrieSimpleAsciiCursor<'a>

impl<'a> Send for ZeroTrieSimpleAsciiCursor<'a>

impl<'a> Sync for ZeroTrieSimpleAsciiCursor<'a>

impl<'a> Unpin for ZeroTrieSimpleAsciiCursor<'a>

impl<'a> UnsafeUnpin for ZeroTrieSimpleAsciiCursor<'a>

impl<'a> UnwindSafe for ZeroTrieSimpleAsciiCursor<'a>

impl<T> Any for ZeroTrieSimpleAsciiCursor<'a>

fn type_id(self: &Self) -> TypeId

impl<T> Borrow for ZeroTrieSimpleAsciiCursor<'a>

fn borrow(self: &Self) -> &T

impl<T> BorrowMut for ZeroTrieSimpleAsciiCursor<'a>

fn borrow_mut(self: &mut Self) -> &mut T

impl<T> CloneToUninit for ZeroTrieSimpleAsciiCursor<'a>

unsafe fn clone_to_uninit(self: &Self, dest: *mut u8)

impl<T> ErasedDestructor for ZeroTrieSimpleAsciiCursor<'a>

impl<T> From for ZeroTrieSimpleAsciiCursor<'a>

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> ToOwned for ZeroTrieSimpleAsciiCursor<'a>

fn to_owned(self: &Self) -> T

fn clone_into(self: &Self, target: &mut T)

impl<T, U> Into for ZeroTrieSimpleAsciiCursor<'a>

fn into(self: Self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of [From]<T> for U chooses to do.

impl<T, U> TryFrom for ZeroTrieSimpleAsciiCursor<'a>

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto for ZeroTrieSimpleAsciiCursor<'a>

fn try_into(self: Self) -> Result<U, <U as TryFrom<T>>::Error>