Struct Treap 

pub struct Treap<M, L, A = BoxAllocator<BstNode<TreapData<M, L>, WithParent<TreapData<M, L>>>>>
where
    M: MonoidAct<Key: Ord>,
    L: LazyMapMonoid,
    A: Allocator<BstNode<TreapData<M, L>, WithParent<TreapData<M, L>>>>,
{
    root: Option<BstRoot<TreapSpec<M, L>>>,
    node_id_manager: BstNodeIdManager<TreapSpec<M, L>>,
    rng: Xorshift,
    allocator: ManuallyDrop<A>,
    _marker: PhantomData<(M, L)>,
}

Fields

root: Option<BstRoot<TreapSpec<M, L>>>

node_id_manager: BstNodeIdManager<TreapSpec<M, L>>

rng: Xorshift

allocator: ManuallyDrop<A>

_marker: PhantomData<(M, L)>

Implementations

impl<M, L> Treap<M, L>

where M: MonoidAct<Key: Ord>, L: LazyMapMonoid,

pub fn new() -> Self

impl<M, L, A> Treap<M, L, A>

where M: MonoidAct<Key: Ord>, L: LazyMapMonoid, A: Allocator<BstNode<TreapData<M, L>, WithParent<TreapData<M, L>>>>,

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn clear(&mut self)

pub fn get( &mut self, node_id: BstNodeId<TreapSpec<M, L>>, ) -> Option<(&M::Key, &L::Key)>

pub fn change( &mut self, node_id: BstNodeId<TreapSpec<M, L>>, f: impl FnOnce(&mut L::Key), ) -> bool

pub fn change_key_value( &mut self, node_id: BstNodeId<TreapSpec<M, L>>, f: impl FnOnce(&mut M::Key, &mut L::Key), ) -> bool

pub fn insert( &mut self, key: M::Key, value: L::Key, ) -> BstNodeId<TreapSpec<M, L>>

pub fn remove( &mut self, node_id: BstNodeId<TreapSpec<M, L>>, ) -> Option<(M::Key, L::Key)>

pub fn range_by_key<Q, R>(&mut self, range: R) -> TreapSplit3<'_, M, L>

where M: MonoidAct<Key: Borrow<Q>>, Q: Ord + ?Sized, R: RangeBounds<Q>,

pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>

where M: MonoidAct<Key: Borrow<Q>>, Q: Ord + ?Sized,

pub fn find_by_acc_cond<F>( &mut self, f: F, ) -> Option<BstNodeId<TreapSpec<M, L>>>

where F: FnMut(&L::Agg) -> bool,

pub fn find_by_racc_cond<F>( &mut self, f: F, ) -> Option<BstNodeId<TreapSpec<M, L>>>

where F: FnMut(&L::Agg) -> bool,

Trait Implementations

impl<M, L, A> Default for Treap<M, L, A>

where M: MonoidAct<Key: Ord>, L: LazyMapMonoid, A: Allocator<BstNode<TreapData<M, L>, WithParent<TreapData<M, L>>>> + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<M, L, A> Drop for Treap<M, L, A>

where M: MonoidAct<Key: Ord>, L: LazyMapMonoid, A: Allocator<BstNode<TreapData<M, L>, WithParent<TreapData<M, L>>>>,

fn drop(&mut self)

Executes the destructor for this type.