Struct ZeroTrieSimpleAscii

#[repr(transparent)]
pub struct ZeroTrieSimpleAscii<Store>
where
    Store: ?Sized,
{ /* private fields */ }

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);

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<const N: usize> ZeroTrieSimpleAscii<[u8; N]>

pub const fn from_sorted_u8_tuples( tuples: &[(&[u8], usize)], ) -> ZeroTrieSimpleAscii<[u8; N]>

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:

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:

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:

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

pub const fn from_sorted_str_tuples( tuples: &[(&str, usize)], ) -> ZeroTrieSimpleAscii<[u8; N]>

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:

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

impl<Store> ZeroTrieSimpleAscii<Store>

where Store: AsRef<[u8]> + ?Sized,

pub fn cursor(&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<'a> ZeroTrieSimpleAscii<&'a [u8]>

pub fn into_cursor(self) -> ZeroTrieSimpleAsciiCursor<'a>

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

impl<Store> ZeroTrieSimpleAscii<Store>

pub const fn into_zerotrie(self) -> ZeroTrie<Store>

Wrap this specific ZeroTrie variant into a ZeroTrie.

impl<Store> ZeroTrieSimpleAscii<Store>

pub const fn from_store(store: Store) -> ZeroTrieSimpleAscii<Store>

Create a trie directly from a store.

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

pub fn into_store(self) -> Store

Takes the byte store from this trie.

pub fn convert_store<X>(self) -> ZeroTrieSimpleAscii<X>

where X: From<Store>,

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>

where Store: AsRef<[u8]> + ?Sized,

pub fn get<K>(&self, key: K) -> Option<usize>

where K: AsRef<[u8]>,

Queries the trie for a string.

pub fn is_empty(&self) -> bool

Returns true if the trie is empty.

pub fn byte_len(&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());

pub fn as_bytes(&self) -> &[u8]

Returns the bytes contained in the underlying store.

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

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

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

Returns a trie with a store borrowing from this trie.

impl<Store> ZeroTrieSimpleAscii<Store>

where Store: AsRef<[u8]> + ?Sized,

pub fn to_owned(&self) -> ZeroTrieSimpleAscii<Vec<u8>>

Converts a possibly-borrowed $name to an owned one.

✨ Enabled with the alloc Cargo feature.

Examples

use zerotrie::ZeroTrieSimpleAscii;

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

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

pub fn iter( &self, ) -> Map<ZeroTrieIterator<'_>, fn(_: (Vec<u8>, usize)) -> (String, usize)>

Returns an iterator over the key/value pairs in this trie.

✨ Enabled with the alloc Cargo feature.

Examples

use zerotrie::ZeroTrieSimpleAscii;

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

let mut it = trie.iter();
assert_eq!(it.next(), Some(("abc".into(), 0)));
assert_eq!(it.next(), Some(("abcdef".into(), 1)));
assert_eq!(it.next(), None);

impl ZeroTrieSimpleAscii<[u8]>

pub fn from_bytes(trie: &[u8]) -> &ZeroTrieSimpleAscii<[u8]>

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

where Store: AsRef<[u8]> + ?Sized,

pub fn to_btreemap(&self) -> BTreeMap<String, usize>

Exports the data from this ZeroTrie type into a BTreeMap.

✨ Enabled with the alloc Cargo feature.

Examples

use zerotrie::ZeroTrieSimpleAscii;
use std::collections::BTreeMap;

let trie = ZeroTrieSimpleAscii::from_bytes(b"abc\x81def\x82");
let items = trie.to_btreemap();

assert_eq!(items.len(), 2);

let recovered_trie: ZeroTrieSimpleAscii<Vec<u8>> = items
    .into_iter()
    .collect();
assert_eq!(trie.as_bytes(), recovered_trie.as_bytes());

impl<Store> ZeroTrieSimpleAscii<Store>

where Store: AsRef<[u8]> + ?Sized,

pub fn to_litemap(&self) -> LiteMap<String, usize>

Exports the data from this ZeroTrie type into a LiteMap.

✨ Enabled with the litemap Cargo feature.

Examples

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

let trie = ZeroTrieSimpleAscii::from_bytes(b"abc\x81def\x82");

let items = trie.to_litemap();
assert_eq!(items.len(), 2);

let recovered_trie: ZeroTrieSimpleAscii<Vec<u8>> = items
    .iter()
    .map(|(k, v)| (k, *v))
    .collect();
assert_eq!(trie.as_bytes(), recovered_trie.as_bytes());

Trait Implementations

impl<Store> AsRef<ZeroTrieSimpleAscii<[u8]>> for ZeroTrieSimpleAscii<Store>

where Store: AsRef<[u8]> + ?Sized,

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

Converts this type into a shared reference of the (usually inferred) input type.

impl Borrow<ZeroTrieSimpleAscii<[u8]>> for ZeroTrieSimpleAscii<&[u8]>

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

Immutably borrows from an owned value.

impl Borrow<ZeroTrieSimpleAscii<[u8]>> for ZeroTrieSimpleAscii<Box<[u8]>>

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

Immutably borrows from an owned value.

impl Borrow<ZeroTrieSimpleAscii<[u8]>> for ZeroTrieSimpleAscii<Vec<u8>>

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

Immutably borrows from an owned value.

impl<Store> Clone for ZeroTrieSimpleAscii<Store>

where Store: Clone + ?Sized,

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Store> Debug for ZeroTrieSimpleAscii<Store>

where Store: Debug + ?Sized,

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

Formats the value using the given formatter.

impl<Store> Default for ZeroTrieSimpleAscii<Store>

where Store: Default + ?Sized,

fn default() -> ZeroTrieSimpleAscii<Store>

Returns the “default value” for a type.

impl<'data, 'de, Store> Deserialize<'de> for ZeroTrieSimpleAscii<Store>

where 'de: 'data, Store: From<&'data [u8]> + From<Vec<u8>> + 'data,

fn deserialize<D>( deserializer: D, ) -> Result<ZeroTrieSimpleAscii<Store>, <D as Deserializer<'de>>::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, K> FromIterator<(K, usize)> for ZeroTrieSimpleAscii<Vec<u8>>

where K: AsRef<[u8]>,

fn from_iter<T>(iter: T) -> ZeroTrieSimpleAscii<Vec<u8>>

where T: IntoIterator<Item = (K, usize)>,

Creates a value from an iterator.

impl<Store> PartialEq for ZeroTrieSimpleAscii<Store>

where Store: PartialEq + ?Sized,

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

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<Store> Serialize for ZeroTrieSimpleAscii<Store>

where Store: AsRef<[u8]>,

fn serialize<S>( &self, serializer: S, ) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl ToOwned for ZeroTrieSimpleAscii<[u8]>

fn to_owned(&self) -> <ZeroTrieSimpleAscii<[u8]> as ToOwned>::Owned

This impl allows ZeroTrieSimpleAscii to be used inside of a Cow.

Note that it is also possible to use ZeroTrieSimpleAscii<ZeroVec<u8>> for a similar result.

✨ Enabled with the alloc Cargo feature.

Examples

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

let trie: Cow<ZeroTrieSimpleAscii<[u8]>> = Cow::Borrowed(ZeroTrieSimpleAscii::from_bytes(b"abc\x85"));
assert_eq!(trie.get(b"abc"), Some(5));

type Owned = ZeroTrieSimpleAscii<Box<[u8]>>

The resulting type after obtaining ownership.

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

Uses borrowed data to replace owned data, usually by cloning.

impl<'a, K> TryFrom<&'a BTreeMap<K, usize>> for ZeroTrieSimpleAscii<Vec<u8>>

where K: Borrow<[u8]>,

type Error = ZeroTrieBuildError

The type returned in the event of a conversion error.

fn try_from( map: &'a BTreeMap<K, usize>, ) -> Result<ZeroTrieSimpleAscii<Vec<u8>>, <ZeroTrieSimpleAscii<Vec<u8>> as TryFrom<&'a BTreeMap<K, usize>>>::Error>

Performs the conversion.

impl<'a, K, S> TryFrom<&'a LiteMap<K, usize, S>> for ZeroTrieSimpleAscii<Vec<u8>>

where K: Borrow<[u8]>, S: StoreIterable<'a, K, usize>,

type Error = ZeroTrieBuildError

The type returned in the event of a conversion error.

fn try_from( map: &'a LiteMap<K, usize, S>, ) -> Result<ZeroTrieSimpleAscii<Vec<u8>>, <ZeroTrieSimpleAscii<Vec<u8>> as TryFrom<&'a LiteMap<K, usize, S>>>::Error>

Performs the conversion.

impl<Store> VarULE for ZeroTrieSimpleAscii<Store>

where Store: VarULE,

fn validate_bytes(bytes: &[u8]) -> Result<(), UleError>

Validates a byte slice, &[u8].

unsafe fn from_bytes_unchecked(bytes: &[u8]) -> &ZeroTrieSimpleAscii<Store>

Takes a byte slice, &[u8], and return it as &Self with the same lifetime, assuming that this byte slice has previously been run through Self::parse_bytes() with success.

fn parse_bytes(bytes: &[u8]) -> Result<&Self, UleError>

Parses a byte slice, &[u8], and return it as &Self with the same lifetime.

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

Given &Self, returns a &[u8] with the same lifetime.

fn to_boxed(&self) -> Box<Self>

Allocate on the heap as a Box<T>

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

where Store2: ZeroFrom<'zf, Store1>,

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

Clone the other C into a struct that may retain references into C.

impl<Store> Copy for ZeroTrieSimpleAscii<Store>

where Store: Copy + ?Sized,

impl<Store> Eq for ZeroTrieSimpleAscii<Store>

where Store: Eq + ?Sized,

impl<Store> StructuralPartialEq for ZeroTrieSimpleAscii<Store>

where Store: ?Sized,