Struct TriePosition 

pub struct TriePosition { /* private fields */ }

Encapsulates logic for moving around in paged storage for a binary trie.

Implementations

impl TriePosition

pub fn new() -> Self

Create a new TriePosition at the root.

pub fn from_path_and_depth(path: KeyPath, depth: u16) -> Self

Create a new TriePosition based on the first depth bits of path.

Panics if depth is zero.

pub fn from_bitslice(slice: &BitSlice<u8, Msb0>) -> Self

Create a new TriePosition based on a bitslice.

pub fn is_root(&self) -> bool

Whether the position is at the root.

pub fn depth(&self) -> u16

Get the current depth of the position.

pub fn path(&self) -> &BitSlice<u8, Msb0>

Get the path to the current position.

pub fn raw_path(&self) -> [u8; 32]

Get the raw key at the current position.

Note that if you have called up, this might have bits beyond depth which are set.

pub fn down(&mut self, bit: bool)

Move the position down by 1, towards either the left or right child.

Panics on depth out of range.

pub fn up(&mut self, d: u16)

Move the position up by d bits.

Panics if d is greater than the current depth.

pub fn sibling(&mut self)

Move the position to the sibling node.

Panic if at the root.

pub fn peek_last_bit(&self) -> bool

Peek at the last bit of the path.

Panics if at the root.

pub fn page_id(&self) -> Option<PageId>

Get the page ID this position lands in. Returns None at the root.

pub fn child_page_index(&self) -> ChildPageIndex

Get the child page index, relative to the current page, where the children of the current node are stored.

Panics if the position is not in the last layer of the page.

pub fn sibling_child_page_index(&self) -> ChildPageIndex

Get the child page index, relative to the current page, where the children of the sibling node are stored.

Panics if the position is not in the last layer of the page.

pub fn child_node_indices(&self) -> ChildNodeIndices

Transform a bit-path to the index in a page corresponding to the child node indices.

Panics if the node is not at a depth in the range 1..=5

pub fn sibling_index(&self) -> usize

Get the index of the sibling node within a page.

pub fn node_index(&self) -> usize

Get the index of the current node within a page.

pub fn depth_in_page(&self) -> usize

Get the number of bits traversed in the current page.

Note that every page has traversed at least 1 bit, therefore the return value would be between 1 and DEPTH, with the exception of the root node, which has traversed 0 bits.

pub fn is_first_layer_in_page(&self) -> bool

Fast path for checking whether this is in the first layer in the page.

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

Get the number of shared bits between this position and other.

This is essentially the depth of a hypothetical internal node which both positions would descend from.

pub fn subtrie_contains(&self, path: &KeyPath) -> bool

Whether the sub-trie indicated by this position would contain a given key-path.

Trait Implementations

impl Clone for TriePosition

fn clone(&self) -> TriePosition

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for TriePosition

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

Formats the value using the given formatter.

impl PartialEq for TriePosition

fn eq(&self, other: &Self) -> 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 Eq for TriePosition