Struct CoveringDifferenceView 

pub struct CoveringDifferenceView<'a, L, R> { /* private fields */ }

An immutable view over the covering difference of two TrieViews.

Returned by TrieView::covering_difference. Iterates over every prefix P_l in the left view for which there is no prefix P_r in the right view satisfying P_r.len ≤ P_l.len and P_r matching P_l’s leading bits.

Coverage is encoded directly in cov_data / cov_child: a set bit means that L slot is covered by R and must not be yielded. data_bitmap and child_bitmap are computed as left_bitmap & !cov_bitmap. The special case where an ancestor R covers the entire subtrie is represented by cov_data = 0x7FFFFFFF, cov_child = 0xFFFFFFFF (all 31 data bits and all 32 child bits), which drives both bitmaps to zero.

Trait Implementations

impl<'a, L, R> AsView<'a> for CoveringDifferenceView<'a, L, R>

where L: TrieView<'a>, R: TrieView<'a, P = L::P>,

type P = <L as TrieView<'a>>::P

The prefix type.

type View = CoveringDifferenceView<'a, L, R>

The concrete view type returned by view.

fn view(self) -> Self

Get a view rooted at the origin (the entire trie).

fn view_at(self, prefix: &Self::P) -> Option<Self::View>

where Self: Sized,

Get a view rooted at prefix, or None if the sub-trie is empty.

impl<'a, L: Clone, R: Clone> Clone for CoveringDifferenceView<'a, L, R>

fn clone(&self) -> CoveringDifferenceView<'a, L, R>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<'a, L, R> IntoIterator for CoveringDifferenceView<'a, L, R>

where L: TrieView<'a>, R: TrieView<'a, P = L::P>,

type Item = (<L as TrieView<'a>>::P, <L as TrieView<'a>>::T)

The type of the elements being iterated over.

type IntoIter = ViewIter<'a, CoveringDifferenceView<'a, L, R>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, L, R> TrieView<'a> for CoveringDifferenceView<'a, L, R>

where L: TrieView<'a>, R: TrieView<'a, P = L::P>,

fn data_bitmap(&self) -> u32

Effective data bitmap: left’s bitmap minus any bits covered by R.

When the entire subtrie is covered (cov_data = 0x7FFFFFFF), this returns 0 because left.data_bitmap() only uses bits 0-30 and !0x7FFFFFFF = 0x80000000.

fn child_bitmap(&self) -> u32

Effective child bitmap: left’s bitmap minus any children fully covered by R.

When the entire subtrie is covered (cov_child = 0xFFFFFFFF), this returns 0.

type P = <L as TrieView<'a>>::P

The prefix type.

type T = <L as TrieView<'a>>::T

The value type yielded by this view (e.g. &'a T, &'a mut T, (&'a L, &'a R)).

fn depth(&self) -> u32

Depth of the underlying MultiBitNode: always a multiple of K.

fn key(&self) -> <L::P as Prefix>::R

Accumulated key bits; only the top prefix_len bits are significant.

fn prefix_len(&self) -> u32

Binary-tree depth of this view’s root position (depth <= prefix_len < depth + K).

unsafe fn get_data(&mut self, data_bit: u32) -> L::T

Return the value at data_bit.

unsafe fn get_child(&mut self, child_bit: u32) -> Self

Return a child view at child_bit.

unsafe fn reposition(&mut self, key: <L::P as Prefix>::R, prefix_len: u32)

Move the cursor to a different location within the same multibit-node.

fn is_non_empty(&self) -> bool

Whether the sub-trie rooted at this view position is non-empty.

fn prefix(&self) -> Self::P

Reconstruct the prefix at this view’s root position.

fn value(self) -> Option<Self::T>

Return the value stored exactly at this view’s root position, if any.

fn prefix_value(self) -> Option<(Self::P, Self::T)>

Return the prefix and value stored exactly at this view’s root position, if any.

fn left(self) -> Option<Self>

Return a view into the left (0-bit) child sub-trie, or None if empty.

fn right(self) -> Option<Self>

Return a view into the right (1-bit) child sub-trie, or None if empty.

fn navigate_to( self, target_key: <Self::P as Prefix>::R, target_len: u32, ) -> Option<Self>

Navigate toward (target_key, target_len) from this view’s node.

fn find(self, prefix: &Self::P) -> Option<Self>

Navigate to prefix and return the view if the sub-trie is non-empty.

fn find_exact(self, prefix: &Self::P) -> Option<Self>

Navigate to prefix and return the view only if a value is stored exactly there.

fn find_exact_value(self, prefix: &Self::P) -> Option<(Self::P, Self::T)>

Navigate to prefix and return its prefix/value pair if a value is stored exactly there.

fn find_lpm(self, prefix: &Self::P) -> Option<Self>

where Self: Clone,

Find the view pointing at the longest prefix match for prefix.

fn find_lpm_value(self, prefix: &Self::P) -> Option<(Self::P, Self::T)>

Find the longest prefix match for prefix and return its prefix/value pair.

fn iter(self) -> ViewIter<'a, Self>

Return an iterator over all (prefix, value) pairs in this sub-trie.

fn iter_from(self, prefix: &Self::P, inclusive: bool) -> ViewIter<'a, Self>

Return an iterator starting at the given prefix in lexicographic order.

fn keys(self) -> ViewKeys<'a, Self>

Return an iterator over all prefixes in this sub-trie.

fn values(self) -> ViewValues<'a, Self>

Return an iterator over all values in this sub-trie.

fn intersection<R>( self, other: R, ) -> Option<IntersectionView<'a, Self, R::View>>

where R: AsView<'a, P = Self::P>,

Return the intersection of self and other as a view, or None if disjoint.

fn union<R>(self, other: R) -> UnionView<'a, Self, R::View>

where R: AsView<'a, P = Self::P>,

Return the union of self and other as a view.

fn covering_union<R>(self, other: R) -> CoveringUnionView<'a, Self, R::View>

where Self: Clone, R: AsView<'a, P = Self::P>, R::View: Clone,

Return the covering union of self and other as a view.

fn difference<R>(self, other: R) -> DifferenceView<'a, Self, R::View>

where R: AsView<'a, P = Self::P>,

Return the difference of self minus other as a view.

fn eq_keys<R: AsView<'a, P = Self::P>>(self, other: R) -> bool

Check whether self and other contain exactly the same set of prefixes, ignoring values.

fn eq_by<R, F>(self, other: R, cmp: F) -> bool

where Self::P: PartialEq, R: AsView<'a, P = Self::P>, F: FnMut(Self::T, <<R as AsView<'a>>::View as TrieView<'a>>::T) -> bool,

Check whether self and other contain the same prefixes with equal values, using cmp to compare each value pair.

fn covering_difference<R>( self, other: R, ) -> CoveringDifferenceView<'a, Self, R::View>

where R: AsView<'a, P = Self::P>,

Return the covering difference of self minus other as a view.

fn step(self, go_right: bool) -> Option<Self>

Step one binary level deeper, going left (0-bit) or right (1-bit).