Struct TreapSpec 

pub struct TreapSpec<M, L> {
    _marker: PhantomData<(M, L)>,
}

Fields

_marker: PhantomData<(M, L)>

Implementations

impl<M, L> TreapSpec<M, L>

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

pub fn merge_ordered( left: Option<BstRoot<TreapSpec<M, L>>>, right: Option<BstRoot<TreapSpec<M, L>>>, ) -> Option<BstRoot<TreapSpec<M, L>>>

Examples found in repository

crates/competitive/src/data_structure/treap.rs (line 201)

    pub fn merge_ordered(
        left: Option<TreapRoot<M, L>>,
        right: Option<TreapRoot<M, L>>,
    ) -> Option<TreapRoot<M, L>> {
        match (left, right) {
            (None, None) => None,
            (None, Some(node)) | (Some(node), None) => Some(node),
            (Some(mut left), Some(mut right)) => unsafe {
                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
                    Self::top_down(left.borrow_datamut());
                    let key = &left.reborrow().into_data().key.key;
                    let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), EqualSide::Right);
                    let ll = left.borrow_mut().left().take();
                    let lr = left.borrow_mut().right().take();
                    if let Some(l) = Self::merge_ordered(ll, rl) {
                        left.borrow_mut().left().set(l);
                    }
                    if let Some(r) = Self::merge_ordered(lr, rr) {
                        left.borrow_mut().right().set(r);
                    }
                    Self::bottom_up(left.borrow_datamut());
                    Some(left)
                } else {
                    Self::top_down(right.borrow_datamut());
                    let key = &right.reborrow().into_data().key.key;
                    let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), EqualSide::Right);
                    let rl = right.borrow_mut().left().take();
                    let rr = right.borrow_mut().right().take();
                    if let Some(l) = Self::merge_ordered(ll, rl) {
                        right.borrow_mut().left().set(l);
                    }
                    if let Some(r) = Self::merge_ordered(lr, rr) {
                        right.borrow_mut().right().set(r);
                    }
                    Self::bottom_up(right.borrow_datamut());
                    Some(right)
                }
            },
        }
    }
}

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

impl<M, L, A> Default for Treap<M, L, A>
where
    M: MonoidAct<Key: Ord>,
    L: LazyMapMonoid,
    A: Allocator<TreapNode<M, L>> + Default,
{
    fn default() -> Self {
        Self {
            root: None,
            node_id_manager: Default::default(),
            rng: Xorshift::new(),
            allocator: ManuallyDrop::new(A::default()),
            _marker: PhantomData,
        }
    }
}

impl<M, L, A> Drop for Treap<M, L, A>
where
    M: MonoidAct<Key: Ord>,
    L: LazyMapMonoid,
    A: Allocator<TreapNode<M, L>>,
{
    fn drop(&mut self) {
        unsafe {
            if let Some(root) = self.root.take() {
                root.into_dying().drop_all(self.allocator.deref_mut());
            }
            ManuallyDrop::drop(&mut self.allocator);
        }
    }
}

impl<M, L> Treap<M, L>
where
    M: MonoidAct<Key: Ord>,
    L: LazyMapMonoid,
{
    pub fn new() -> Self {
        Self::default()
    }
}

impl<M, L, A> Treap<M, L, A>
where
    M: MonoidAct<Key: Ord>,
    L: LazyMapMonoid,
    A: Allocator<TreapNode<M, L>>,
{
    pub fn len(&self) -> usize {
        self.node_id_manager.len()
    }

    pub fn is_empty(&self) -> bool {
        self.node_id_manager.is_empty()
    }

    pub fn clear(&mut self) {
        unsafe {
            if let Some(root) = self.root.take() {
                root.into_dying().drop_all(self.allocator.deref_mut());
            }
            self.node_id_manager.clear();
        }
    }

    pub fn get(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(&M::Key, &L::Key)> {
        if !self.node_id_manager.contains(&node_id) {
            return None;
        }
        unsafe {
            WithParent::resolve_top_down::<TreapSpec<M, L>>(
                node_id.reborrow_datamut(&mut self.root),
            );
            let data = node_id.reborrow(&self.root).into_data();
            Some((&data.key.key, &data.value.key))
        }
    }

    pub fn change(
        &mut self,
        node_id: BstNodeId<TreapSpec<M, L>>,
        f: impl FnOnce(&mut L::Key),
    ) -> bool {
        if !self.node_id_manager.contains(&node_id) {
            return false;
        }
        unsafe {
            WithParent::resolve_top_down::<TreapSpec<M, L>>(
                node_id.reborrow_datamut(&mut self.root),
            );
            let data = node_id.reborrow_datamut(&mut self.root).into_data_mut();
            f(&mut data.value.key);
            WithParent::resolve_bottom_up::<TreapSpec<M, L>>(
                node_id.reborrow_datamut(&mut self.root),
            );
        }
        true
    }

    pub fn change_key_value(
        &mut self,
        node_id: BstNodeId<TreapSpec<M, L>>,
        f: impl FnOnce(&mut M::Key, &mut L::Key),
    ) -> bool {
        if !self.node_id_manager.contains(&node_id) {
            return false;
        }
        unsafe {
            WithParent::resolve_top_down::<TreapSpec<M, L>>(
                node_id.reborrow_datamut(&mut self.root),
            );
            let mut node = if WithParent::is_root(node_id.reborrow(&self.root)) {
                WithParent::remove_root(&mut self.root).unwrap_unchecked()
            } else {
                WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
            };
            let data = node.borrow_datamut().into_data_mut();
            f(&mut data.key.key, &mut data.value.key);
            self.root = TreapSpec::merge_ordered(self.root.take(), Some(node));
            true
        }
    }

Trait Implementations

impl<M, L> BstSpec for TreapSpec<M, L>

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

type Parent = WithParent<<TreapSpec<M, L> as BstSpec>::Data>

type Data = TreapData<M, L>

fn top_down(node: BstDataMutRef<'_, Self>)

fn bottom_up(node: BstDataMutRef<'_, Self>)

fn merge( left: Option<BstRoot<TreapSpec<M, L>>>, right: Option<BstRoot<TreapSpec<M, L>>>, ) -> Option<BstRoot<TreapSpec<M, L>>>

fn split<Seeker>( node: Option<BstRoot<TreapSpec<M, L>>>, seeker: Seeker, equal_side: EqualSide, ) -> (Option<BstRoot<TreapSpec<M, L>>>, Option<BstRoot<TreapSpec<M, L>>>)

where Seeker: BstSeeker<Spec = Self>,