Struct ZeroTrieSimpleAscii

struct ZeroTrieSimpleAscii<Store: ?Sized> { ... }

A data structure that compactly maps from ASCII strings to integers.

For more information, see ZeroTrie.

Examples

use litemap::LiteMap;
use zerotrie::ZeroTrieSimpleAscii;

let mut map = LiteMap::new_vec();
map.insert(&b"foo"[..], 1);
map.insert(b"bar", 2);
map.insert(b"bazzoo", 3);

let trie = ZeroTrieSimpleAscii::try_from(&map)?;

assert_eq!(trie.get(b"foo"), Some(1));
assert_eq!(trie.get(b"bar"), Some(2));
assert_eq!(trie.get(b"bazzoo"), Some(3));
assert_eq!(trie.get(b"unknown"), None);

# Ok::<_, zerotrie::ZeroTrieBuildError>(())

The trie can only store ASCII bytes; a string with non-ASCII always returns None:

use zerotrie::ZeroTrieSimpleAscii;

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

assert!(matches!(trie.get(b"ab\xFF"), None));

Implementations

impl ZeroTrieSimpleAscii<[u8]>

fn from_bytes(trie: &[u8]) -> &Self

Casts from a byte slice to a reference to a trie with the same lifetime.

If the bytes are not a valid trie, unexpected behavior may occur.

impl<'a> ZeroTrieSimpleAscii<&'a [u8]>

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

Same as [ZeroTrieSimpleAscii::cursor()] but moves self to avoid having to doubly anchor the trie to the stack.

impl<N: usize> ZeroTrieSimpleAscii<[u8; N]>

const fn from_sorted_u8_tuples(tuples: &[(&[u8], usize)]) -> Self

Const Constructor: Creates an ZeroTrieSimpleAscii from a sorted slice of keys and values.

This function needs to know the exact length of the resulting trie at compile time. To figure out N, first set N to be too large (say 0xFFFF), then look at the resulting compile error which will tell you how to set N, like this:

the evaluated program panicked at 'Buffer too large. Size needed: 17'

That error message says you need to set N to 17.

Also see Self::from_sorted_str_tuples.

Panics

Panics if items is not sorted or if N is not correct.

Examples

Create a const ZeroTrieSimpleAscii at compile time:

use zerotrie::ZeroTrieSimpleAscii;

// The required capacity for this trie happens to be 17 bytes
const TRIE: ZeroTrieSimpleAscii<[u8; 17]> =
    ZeroTrieSimpleAscii::from_sorted_u8_tuples(&[
        (b"bar", 2),
        (b"bazzoo", 3),
        (b"foo", 1),
    ]);

assert_eq!(TRIE.get(b"foo"), Some(1));
assert_eq!(TRIE.get(b"bar"), Some(2));
assert_eq!(TRIE.get(b"bazzoo"), Some(3));
assert_eq!(TRIE.get(b"unknown"), None);

Panics if strings are not sorted:

# use zerotrie::ZeroTrieSimpleAscii;
const TRIE: ZeroTrieSimpleAscii<[u8; 17]> = ZeroTrieSimpleAscii::from_sorted_u8_tuples(&[
    (b"foo", 1),
    (b"bar", 2),
    (b"bazzoo", 3),
]);

Panics if capacity is too small:

# use zerotrie::ZeroTrieSimpleAscii;
const TRIE: ZeroTrieSimpleAscii<[u8; 15]> = ZeroTrieSimpleAscii::from_sorted_u8_tuples(&[
    (b"bar", 2),
    (b"bazzoo", 3),
    (b"foo", 1),
]);

Panics if capacity is too large:

# use zerotrie::ZeroTrieSimpleAscii;
const TRIE: ZeroTrieSimpleAscii<[u8; 20]> = ZeroTrieSimpleAscii::from_sorted_u8_tuples(&[
    (b"bar", 2),
    (b"bazzoo", 3),
    (b"foo", 1),
]);

const fn from_sorted_str_tuples(tuples: &[(&str, usize)]) -> Self

Const Constructor: Creates an ZeroTrieSimpleAscii from a sorted slice of keys and values.

This function needs to know the exact length of the resulting trie at compile time. To figure out N, first set N to be too large (say 0xFFFF), then look at the resulting compile error which will tell you how to set N, like this:

the evaluated program panicked at 'Buffer too large. Size needed: 17'

That error message says you need to set N to 17.

Also see Self::from_sorted_u8_tuples.

Panics

Panics if items is not sorted, if N is not correct, or if any of the strings contain non-ASCII characters.

Examples

Create a const ZeroTrieSimpleAscii at compile time:

use zerotrie::ZeroTrieSimpleAscii;

// The required capacity for this trie happens to be 17 bytes
const TRIE: ZeroTrieSimpleAscii<[u8; 17]> =
    ZeroTrieSimpleAscii::from_sorted_str_tuples(&[
        ("bar", 2),
        ("bazzoo", 3),
        ("foo", 1),
    ]);

assert_eq!(TRIE.get(b"foo"), Some(1));
assert_eq!(TRIE.get(b"bar"), Some(2));
assert_eq!(TRIE.get(b"bazzoo"), Some(3));
assert_eq!(TRIE.get(b"unknown"), None);

Panics if the strings are not ASCII:

# use zerotrie::ZeroTrieSimpleAscii;
const TRIE: ZeroTrieSimpleAscii<[u8; 100]> = ZeroTrieSimpleAscii::from_sorted_str_tuples(&[
    ("bár", 2),
    ("båzzöo", 3),
    ("foo", 1),
]);

impl<Store> ZeroTrieSimpleAscii<Store>

fn get<K>(self: &Self, key: K) -> Option<usize>
where
    K: AsRef<[u8]>

Queries the trie for a string.

fn is_empty(self: &Self) -> bool

Returns true if the trie is empty.

fn byte_len(self: &Self) -> usize

Returns the size of the trie in number of bytes.

To get the number of keys in the trie, use .iter().count():

use zerotrie::ZeroTrieSimpleAscii;

// A trie with two values: "abc" and "abcdef"
let trie: &ZeroTrieSimpleAscii<[u8]> = ZeroTrieSimpleAscii::from_bytes(b"abc\x80def\x81");

assert_eq!(8, trie.byte_len());
assert_eq!(2, trie.iter().count());

fn as_bytes(self: &Self) -> &[u8]

Returns the bytes contained in the underlying store.

fn as_borrowed(self: &Self) -> &ZeroTrieSimpleAscii<[u8]>

Returns this trie as a reference transparent over a byte slice.

fn as_borrowed_slice(self: &Self) -> ZeroTrieSimpleAscii<&[u8]>

Returns a trie with a store borrowing from this trie.

impl<Store> ZeroTrieSimpleAscii<Store>

const fn from_store(store: Store) -> Self

Create a trie directly from a store.

If the store does not contain valid bytes, unexpected behavior may occur.

fn into_store(self: Self) -> Store

Takes the byte store from this trie.

fn convert_store<X: From<Store>>(self: Self) -> ZeroTrieSimpleAscii<X>

Converts this trie's store to a different store implementing the From trait.

For example, use this to change ZeroTrieSimpleAscii<Vec<u8>> to ZeroTrieSimpleAscii<Cow<[u8]>>.

Examples

use std::borrow::Cow;
use zerotrie::ZeroTrieSimpleAscii;

let trie: ZeroTrieSimpleAscii<Vec<u8>> = ZeroTrieSimpleAscii::from_bytes(b"abc\x85").to_owned();
let cow: ZeroTrieSimpleAscii<Cow<[u8]>> = trie.convert_store();

assert_eq!(cow.get(b"abc"), Some(5));

impl<Store> ZeroTrieSimpleAscii<Store>

const fn into_zerotrie(self: Self) -> ZeroTrie<Store>

Wrap this specific ZeroTrie variant into a ZeroTrie.

impl<Store> ZeroTrieSimpleAscii<Store>

fn cursor(self: &Self) -> ZeroTrieSimpleAsciiCursor<'_>

Gets a cursor into the current trie.

Useful to query a trie with data that is not a slice.

This is currently supported only on ZeroTrieSimpleAscii and ZeroAsciiIgnoreCaseTrie.

Examples

Get a value out of a trie by writing it to the cursor:

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

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

// Get out the value for "abc"
let mut cursor = trie.cursor();
write!(&mut cursor, "abc");
assert_eq!(cursor.take_value(), Some(0));

Find the longest prefix match:

use zerotrie::ZeroTrieSimpleAscii;

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

// Find the longest prefix of the string "abcdxy":
let query = b"abcdxy";
let mut longest_prefix = 0;
let mut cursor = trie.cursor();
for (i, b) in query.iter().enumerate() {
    // Checking is_empty() is not required, but it is
    // good for efficiency
    if cursor.is_empty() {
        break;
    }
    if cursor.take_value().is_some() {
        longest_prefix = i;
    }
    cursor.step(*b);
}

// The longest prefix is "abc" which is length 3:
assert_eq!(longest_prefix, 3);

impl Borrow for ZeroTrieSimpleAscii<&[u8]>

fn borrow(self: &Self) -> &ZeroTrieSimpleAscii<[u8]>

impl<'zf, Store1, Store2> ZeroFrom for ZeroTrieSimpleAscii<Store2>

fn zero_from(other: &'zf ZeroTrieSimpleAscii<Store1>) -> Self

impl<Store> AsRef for ZeroTrieSimpleAscii<Store>

fn as_ref(self: &Self) -> &ZeroTrieSimpleAscii<[u8]>

impl<Store> Freeze for ZeroTrieSimpleAscii<Store>

impl<Store> RefUnwindSafe for ZeroTrieSimpleAscii<Store>

impl<Store> Send for ZeroTrieSimpleAscii<Store>

impl<Store> Sync for ZeroTrieSimpleAscii<Store>

impl<Store> Unpin for ZeroTrieSimpleAscii<Store>

impl<Store> UnsafeUnpin for ZeroTrieSimpleAscii<Store>

impl<Store> UnwindSafe for ZeroTrieSimpleAscii<Store>

impl<Store: $crate::clone::Clone + ?Sized> Clone for ZeroTrieSimpleAscii<Store>

fn clone(self: &Self) -> ZeroTrieSimpleAscii<Store>

impl<Store: $crate::cmp::Eq + ?Sized> Eq for ZeroTrieSimpleAscii<Store>

impl<Store: $crate::cmp::PartialEq + ?Sized> PartialEq for ZeroTrieSimpleAscii<Store>

fn eq(self: &Self, other: &ZeroTrieSimpleAscii<Store>) -> bool

impl<Store: $crate::default::Default + ?Sized> Default for ZeroTrieSimpleAscii<Store>

fn default() -> ZeroTrieSimpleAscii<Store>

impl<Store: $crate::fmt::Debug + ?Sized> Debug for ZeroTrieSimpleAscii<Store>

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

impl<Store: $crate::marker::Copy + ?Sized> Copy for ZeroTrieSimpleAscii<Store>

impl<Store: ?Sized> StructuralPartialEq for ZeroTrieSimpleAscii<Store>

impl<T> Any for ZeroTrieSimpleAscii<Store>

fn type_id(self: &Self) -> TypeId

impl<T> Borrow for ZeroTrieSimpleAscii<Store>

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

impl<T> BorrowMut for ZeroTrieSimpleAscii<Store>

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

impl<T> CloneToUninit for ZeroTrieSimpleAscii<Store>

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

impl<T> ErasedDestructor for ZeroTrieSimpleAscii<Store>

impl<T> From for ZeroTrieSimpleAscii<Store>

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> ToOwned for ZeroTrieSimpleAscii<Store>

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

impl<T, U> Into for ZeroTrieSimpleAscii<Store>

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 ZeroTrieSimpleAscii<Store>

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

impl<T, U> TryInto for ZeroTrieSimpleAscii<Store>

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