Struct PathMap 

pub struct PathMap<V: Clone + Send + Sync, A: Allocator = GlobalAlloc> { /* private fields */ }

A map type that uses a trie based on byte slices (&[u8]) known as “paths”

This type is implemented using some of the approaches explained in the “Bitwise trie with bitmap” Wikipedia article.

let mut map = PathMap::<String>::new();
map.set_val_at("one", "1".to_string());
map.set_val_at("two", "2".to_string());

assert!(map.contains("one"));
assert_eq!(map.get("two"), Some(&"2".to_string()));
assert!(!map.contains("three"));

Implementations

impl<V: Clone + Send + Sync + Unpin> PathMap<V, GlobalAlloc>

pub const fn new() -> Self

Creates a new empty map

pub fn single<P: AsRef<[u8]>>(path: P, val: V) -> Self

Creates a new single-element pathmap

pub fn new_from_ana<W, AlgF>(w: W, alg_f: AlgF) -> Self

where V: 'static, W: Default, AlgF: FnMut(W, &mut Option<V>, &mut TrieBuilder<V, W, GlobalAlloc>, &[u8]),

Creates a new PathMap by evaluating the specified anamorphism

alg_f: alg(w: W, val: &mut Option<V>, children: &mut ChildBuilder<W>, path: &[u8]) generates the value downstream and downstream children from a path

Setting the val option to Some within the closure sets the value at the current path.

The example below creates a trie with binary tree, 3 levels deep, where each level has a ‘L’ and an ‘R’ branch, and the leaves have a unit value.

let map = PathMap::<()>::new_from_ana(3, |idx, val, children, _path| {
    if idx > 0 {
        children.push(b"L", idx - 1);
        children.push(b"R", idx - 1);
    } else {
        *val = Some(());
    }
});

impl<V: Clone + Send + Sync + Unpin, A: Allocator> PathMap<V, A>

pub const INVIS_HASH: u128 = 19_008_872_547_456_455_701_376_587_154_203_820_551u128

pub const fn new_in(alloc: A) -> Self

Creates a new empty map in the specified allocator

pub fn single_in<P: AsRef<[u8]>>(path: P, val: V, alloc: A) -> Self

Creates a new single-element pathmap in the specified allocator

pub fn new_from_ana_in<W, AlgF>(w: W, alg_f: AlgF, alloc: A) -> Self

where V: 'static, W: Default, AlgF: FnMut(W, &mut Option<V>, &mut TrieBuilder<V, W, A>, &[u8]),

See new_from_ana for description of behavior

pub fn trie_ref_at_path<K: AsRef<[u8]>>( &self, path: K, ) -> TrieRefBorrowed<'_, V, A>

Creates a new TrieRef, referring to a position from the root of the PathMap

pub fn read_zipper<'a>(&'a self) -> ReadZipperUntracked<'a, 'static, V, A>

Creates a new read-only Zipper, starting at the root of a PathMap

pub fn read_zipper_at_borrowed_path<'path>( &self, path: &'path [u8], ) -> ReadZipperUntracked<'_, 'path, V, A>

Creates a new read-only Zipper, with the specified path from the root of the map; This method is much more efficient than read_zipper_at_path, but means the resulting zipper is bound by the 'path lifetime

pub fn read_zipper_at_path<K: AsRef<[u8]>>( &self, path: K, ) -> ReadZipperUntracked<'_, 'static, V, A>

Creates a new read-only Zipper, with the path specified from the root of the map

pub fn write_zipper(&mut self) -> WriteZipperUntracked<'_, 'static, V, A>

Creates a new write zipper starting at the root of the PathMap

pub fn write_zipper_at_path<'a, 'path>( &'a mut self, path: &'path [u8], ) -> WriteZipperUntracked<'a, 'path, V, A>

Creates a new write zipper with the specified path from the root of the map

pub fn zipper_head(&mut self) -> ZipperHead<'_, '_, V, A>

Creates a ZipperHead at the root of the map

pub fn into_read_zipper<K: AsRef<[u8]>>(self, path: K) -> ReadZipperOwned<V, A>

Transforms the map into a Zipper, which is handy when you need to embed the zipper in another struct without a lifetime parameter

pub fn into_write_zipper<K: AsRef<[u8]>>( self, path: K, ) -> WriteZipperOwned<V, A>

Transforms the map into a WriteZipperOwned, which is handy when you need to embed the zipper in another struct without a lifetime parameter

pub fn into_zipper_head<K: AsRef<[u8]>>(self, path: K) -> ZipperHeadOwned<V, A>

Transforms the map into a ZipperHead that owns the map’s contents. This is handy when the ZipperHead needs to be part of another structure

pub fn iter<'a>(&'a self) -> impl Iterator<Item = (Vec<u8>, &'a V)> + 'a

Returns an iterator over all key-value pairs within the map

NOTE: This is much less efficient than using the read_zipper method

pub fn contains<K: AsRef<[u8]>>(&self, k: K) -> bool

Returns true if the map contains a value at the specified key, otherwise returns false

pub fn path_exists_at<K: AsRef<[u8]>>(&self, path: K) -> bool

Returns true if path is contained within the map, or false otherwise

pub fn contains_path<K: AsRef<[u8]>>(&self, k: K) -> bool

👎Deprecated

Deprecated alias for PathMap::path_exists_at

pub fn set_val_at<K: AsRef<[u8]>>(&mut self, path: K, v: V) -> Option<V>

Inserts v into the map at path. Panics if path has a zero length

Returns Some(replaced_val) if an existing value was replaced, otherwise returns None if the value was added to the map without replacing anything.

pub fn insert<K: AsRef<[u8]>>(&mut self, k: K, v: V) -> Option<V>

Alias for Self::set_val_at, so PathMap “feels” like other Rust collections

pub fn remove_val_at<K: AsRef<[u8]>>( &mut self, path: K, prune: bool, ) -> Option<V>

Removes the value at path from the map and returns it, or returns None if there was no value at path

If prune is true, the path will be pruned, otherwise it will be left dangling.

pub fn remove<K: AsRef<[u8]>>(&mut self, path: K) -> Option<V>

Alias for Self::remove_val_at, so PathMap “feels” like other Rust collections

pub fn get_val_at<K: AsRef<[u8]>>(&self, path: K) -> Option<&V>

Returns a reference to the value at the specified path, or None if no value exists

pub fn get<K: AsRef<[u8]>>(&self, path: K) -> Option<&V>

Alias for Self::get_val_at, so PathMap “feels” like other Rust collections

pub fn get_val_mut_at<K: AsRef<[u8]>>(&mut self, path: K) -> Option<&mut V>

Returns a mutable reference to the value at the specified path in the PathMap, if it exists

pub fn get_mut<K: AsRef<[u8]>>(&mut self, path: K) -> Option<&mut V>

Alias for Self::get_val_mut_at, so PathMap “feels” like other Rust collections

pub fn get_val_or_set_mut_with_at<F, K>(&mut self, path: K, func: F) -> &mut V

where F: FnOnce() -> V, K: AsRef<[u8]>,

Returns a mutable reference to the value at the specified path, inserting the result of func if no value exists

pub fn get_val_or_set_mut_at<K: AsRef<[u8]>>( &mut self, path: K, default: V, ) -> &mut V

Returns a mutable reference to the value at the specified path, inserting default if no value already exists

pub fn remove_branches_at<K: AsRef<[u8]>>( &mut self, path: K, prune: bool, ) -> bool

Removes all downstream branches below path. Does not affect a value at path

Returns true if at least one branch was removed.

If prune is true, the path will be pruned, otherwise it will be left dangling.

pub fn is_empty(&self) -> bool

Returns true if the map is empty, otherwise returns false

pub fn prune_path<K: AsRef<[u8]>>(&mut self, path: K) -> usize

Prunes the dangling path specified up to the first upstream value or fork in the path, and returns the number of path bytes removed

pub fn create_path<K: AsRef<[u8]>>(&mut self, path: K) -> bool

Creates the path specified as a dangling path. Returns true if new path bytes were created, or false if the path already existed

pub fn val_count(&self) -> usize

Returns the total number of values contained within the map

WARNING: This is not a cheap method. It may have an order-N cost

pub fn hash<VHash: Fn(&V) -> u128>(&self, vhash: VHash) -> u128

Hash the logical PathMap and all its values with the provided hash function (which can return PathMap::INVIS_HASH to ignore values).

pub fn join(&self, other: &Self) -> Self

where V: Lattice,

Returns a new PathMap containing the union of the paths in self and the paths in other

pub fn meet(&self, other: &Self) -> Self

where V: Lattice,

Returns a new PathMap containing the intersection of the paths in self and the paths in other

pub fn restrict(&self, other: &Self) -> Self

Returns a new PathMap where the paths in self are restricted by the paths leading to values in other

NOTE: if other has a root value, this function returns a clone of self because other’s root value validates all paths. If other does not have a root value, the returned map won’t have one either.

pub fn subtract(&self, other: &Self) -> Self

where V: DistributiveLattice,

Returns a new PathMap containing the contents from self minus the contents of other

pub fn merkleize(&mut self) -> MerkleizeResult

where V: Hash,

Optimize the PathMap by factoring shared subtries using a temporary Merkle Tree

Trait Implementations

impl<V: 'static + Clone + Send + Sync + Unpin, A: Allocator + 'static> Catamorphism<V> for PathMap<V, A>

fn into_cata_side_effect_fallible<W, Err, AlgF>( self, alg_f: AlgF, ) -> Result<W, Err>

where AlgF: FnMut(&ByteMask, &mut [W], Option<&V>, &[u8]) -> Result<W, Err>,

Allows the closure to return an error, stopping traversal immediately

fn into_cata_jumping_side_effect_fallible<W, Err, AlgF>( self, alg_f: AlgF, ) -> Result<W, Err>

where AlgF: FnMut(&ByteMask, &mut [W], usize, Option<&V>, &[u8]) -> Result<W, Err>,

Allows the closure to return an error, stopping traversal immediately

fn into_cata_cached_fallible<W, E, AlgF>(self, alg_f: AlgF) -> Result<W, E>

where W: Clone, AlgF: Fn(&ByteMask, &mut [W], Option<&V>) -> Result<W, E>,

Allows the closure to return an error, stopping traversal immediately

fn into_cata_jumping_cached_fallible<W, E, AlgF>( self, alg_f: AlgF, ) -> Result<W, E>

where W: Clone, AlgF: Fn(&ByteMask, &mut [W], Option<&V>, &[u8]) -> Result<W, E>,

Allows the closure to return an error, stopping traversal immediately

fn into_cata_side_effect<W, AlgF>(self, alg_f: AlgF) -> W

where AlgF: FnMut(&ByteMask, &mut [W], Option<&V>, &[u8]) -> W, Self: Sized,

Applies a “stepping” catamorphism to the trie descending from the zipper’s root, running the alg_f at every step (at every byte)

fn into_cata_jumping_side_effect<W, AlgF>(self, alg_f: AlgF) -> W

where AlgF: FnMut(&ByteMask, &mut [W], usize, Option<&V>, &[u8]) -> W, Self: Sized,

Applies a “jumping” catamorphism to the trie

fn into_cata_cached<W, AlgF>(self, alg_f: AlgF) -> W

where W: Clone, AlgF: Fn(&ByteMask, &mut [W], Option<&V>) -> W, Self: Sized,

Applies a cached, stepping, catamorphism to the trie descending from the zipper’s root, running the alg_f at every step (at every byte)

fn into_cata_jumping_cached<W, AlgF>(self, alg_f: AlgF) -> W

where W: Clone, AlgF: Fn(&ByteMask, &mut [W], Option<&V>, &[u8]) -> W, Self: Sized,

Applies a “jumping” catamorphism to the trie

impl<V: 'static + Clone + Send + Sync + Unpin, A: Allocator + 'static> CatamorphismDebug<V> for PathMap<V, A>

fn into_cata_jumping_cached_fallible_debug<W, E, AlgF>( self, alg_f: AlgF, ) -> Result<W, E>

where W: Clone, AlgF: Fn(&ByteMask, &mut [W], Option<&V>, &[u8], &[u8]) -> Result<W, E>,

A version of into_cata_jumping_cached where the full path is available to the closure; For debugging purposes only

impl<V: Clone + Send + Sync + Unpin, A: Allocator> Clone for PathMap<V, A>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<V: Clone + Send + Sync + Unpin + Debug, A: Allocator> Debug for PathMap<V, A>

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

Formats the value using the given formatter.

impl<V: Clone + Send + Sync + Unpin> Default for PathMap<V>

fn default() -> Self

Returns the “default value” for a type.

impl<V: Clone + Send + Sync + Unpin + DistributiveLattice, A: Allocator> DistributiveLattice for PathMap<V, A>

fn psubtract(&self, other: &Self) -> AlgebraicResult<Self>

Implements the partial subtract operation

impl<V: Clone + Send + Sync + Unpin, K: AsRef<[u8]>> From<(K, V)> for PathMap<V>

fn from(pair: (K, V)) -> Self

Converts to this type from the input type.

impl<'a> FromIterator<&'a [u8]> for PathMap<()>

fn from_iter<I: IntoIterator<Item = &'a [u8]>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, V: Clone + Send + Sync + Unpin, K: AsRef<[u8]>> FromIterator<&'a (K, V)> for PathMap<V>

fn from_iter<I: IntoIterator<Item = &'a (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<V: Clone + Send + Sync + Unpin, K: AsRef<[u8]>> FromIterator<(K, V)> for PathMap<V>

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<V: Clone + Send + Sync + Unpin + 'static, A: Allocator + 'static> IntoIterator for PathMap<V, A>

type Item = (Vec<u8>, V)

The type of the elements being iterated over.

type IntoIter = OwnedZipperIter<V, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<V: Clone + Lattice + Send + Sync + Unpin, A: Allocator> Lattice for PathMap<V, A>

fn pjoin(&self, other: &Self) -> AlgebraicResult<Self>

Implements the union operation between two instances of a type in a partial lattice, resulting in the creation of a new result instance

fn join_into(&mut self, other: Self) -> AlgebraicStatus

Implements the union operation between two instances of a type, consuming the other input operand, and modifying self to become the joined type

fn pmeet(&self, other: &Self) -> AlgebraicResult<Self>

Implements the intersection operation between two instances of a type in a partial lattice

fn join_all<S: AsRef<Self>, Args: AsRef<[S]>>(xs: Args) -> AlgebraicResult<Self>

where Self: Sized + Clone,

impl<V: Clone + Send + Sync, A: Allocator> Send for PathMap<V, A>

impl<V: Clone + Send + Sync, A: Allocator> Sync for PathMap<V, A>