Struct treap_map::TreapMap

pub struct TreapMap<C: TreapMapConfig> { /* private fields */ }

A treap map data structure.

See TreapMapConfig for more details.

Implementations

impl<C: TreapMapConfig> TreapMap<C>

pub fn new() -> TreapMap<C>

pub fn new_with_rng(rng: XorShiftRng) -> TreapMap<C>

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn contains_key(&self, key: &C::SearchKey) -> bool

pub fn insert( &mut self, key: C::SearchKey, value: C::Value, weight: C::Weight ) -> Option<C::Value>

pub fn remove(&mut self, key: &C::SearchKey) -> Option<C::Value>

pub fn update<U, I, T, E>( &mut self, key: &C::SearchKey, update: U, insert: I ) -> Result<T, E>

where U: FnOnce(&mut Node<C>) -> Result<ApplyOpOutcome<T>, E>, I: FnOnce(&mut dyn RngCore) -> Result<(Node<C>, T), E>,

Updates the value of a node with the given key in the treap map.

Parameters

• key: The search key of the node to be updated.
• update: A function that is called if a node with the given key already exists. It takes a mutable reference to the node and returns an ApplyOpOutcome<T> or a custom error E. See ApplyOpOutcome for more details.
• insert: A function that is called if a node with the given key does not exist. It takes a mutable reference to a random number generator (for computing priority for a Node) and should return a tuple containing a new Node<C> and a value of type T, or an error of type E.
  • WARNING: The key of the new node must match the key provided to the function.

pub fn sum_weight(&self) -> C::Weight

pub fn get(&self, key: &C::SearchKey) -> Option<&C::Value>

pub fn get_by_weight(&self, weight: C::Weight) -> Option<&C::Value>

where C::Weight: Ord,

pub fn search<F>(&self, f: F) -> Option<SearchResult<'_, C, C::Weight>>

where F: FnMut(&C::Weight, &Node<C>) -> SearchDirection<C::Weight>,

See details in crate::accumulate_weight_search

pub fn search_no_weight<F>(&self, f: F) -> Option<SearchResult<'_, C, NoWeight>>

where F: FnMut(&Node<C>) -> SearchDirection<()>,

See details in crate::accumulate_weight_search If the search process does not require accessing ‘weight’, this function can outperform search by eliminating the maintenance of the ‘weight’ dimension.

pub fn iter(&self) -> Iter<'_, C>

pub fn iter_range(&self, key: &C::SearchKey) -> Iter<'_, C>

where C: TreapMapConfig<SortKey = ()>,

pub fn values(&self) -> impl Iterator<Item = &C::Value>

pub fn key_values(&self) -> impl Iterator<Item = (&C::SearchKey, &C::Value)>

Trait Implementations

impl<C: TreapMapConfig> MallocSizeOf for TreapMap<C>

where Node<C>: MallocSizeOf, C::ExtMap: MallocSizeOf,

fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize

Measure the heap usage of all descendant heap-allocated structures, but not the space taken up by the value itself.