Struct SearchTree

pub struct SearchTree { /* private fields */ }

A transaction search tree sorted by feerate order and searchable for probabilistic weighted sampling.

All log(n) expressions below are in base 64 (based on constants chosen within the sweep_bptree crate).

The tree has the following properties: 1. Linear time ordered access (ascending / descending) 2. Insertions/removals in log(n) time 3. Search for a weight point p ∈ [0, total_weight) in log(n) time 4. Compute the prefix weight of a key, i.e., the sum of weights up to that key (inclusive) according to key order, in log(n) time 5. Access the total weight in O(1) time. The total weight has numerical stability since it is recomputed from subtree weights for each item insertion/removal

Computing the prefix weight is a crucial operation if the tree is used for random sampling and the tree is highly imbalanced in terms of weight variance. See Frontier::sample_inplace() for more details.

Implementations

impl SearchTree

pub fn new() -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn insert(&mut self, key: FeerateTransactionKey) -> bool

Inserts a key into the tree in log(n) time. Returns false if the key was already in the tree.

pub fn remove(&mut self, key: &FeerateTransactionKey) -> bool

Remove a key from the tree in log(n) time. Returns false if the key was not in the tree.

pub fn search(&self, query: f64) -> &FeerateTransactionKey

Search for a weight point query ∈ [0, total_weight) in log(n) time

pub fn total_weight(&self) -> f64

Access the total weight in O(1) time

pub fn prefix_weight(&self, key: &FeerateTransactionKey) -> f64

Computes the prefix weight of a key, i.e., the sum of weights up to that key (inclusive) according to key order, in log(n) time

pub fn descending_iter( &self, ) -> impl DoubleEndedIterator<Item = &FeerateTransactionKey> + ExactSizeIterator + FusedIterator

Iterate the tree in descending key order (going down from the highest key). Linear in the number of keys actually iterated.

pub fn ascending_iter( &self, ) -> impl DoubleEndedIterator<Item = &FeerateTransactionKey> + ExactSizeIterator + FusedIterator

Iterate the tree in ascending key order (going up from the lowest key). Linear in the number of keys actually iterated.

pub fn first(&self) -> Option<&FeerateTransactionKey>

The lowest key in the tree (by key order)

pub fn last(&self) -> Option<&FeerateTransactionKey>

The highest key in the tree (by key order)

Trait Implementations

impl Default for SearchTree

fn default() -> Self

Returns the “default value” for a type.