competitive::data_structure::binary_search_tree::node_id

Struct BstNodeIdManager

pub struct BstNodeIdManager<Spec>where
    Spec: BstSpec,{
    node_ids: HashMap<BstNodePtr<Spec::Data, Spec::Parent>, u64>,
}

Fields§

§node_ids: HashMap<BstNodePtr<Spec::Data, Spec::Parent>, u64>

Implementations§

Source §

impl<Spec> BstNodeIdManager<Spec>
where Spec: BstSpec,

Source

pub fn new() -> Self

Source

pub fn is_empty(&self) -> bool

Examples found in repository ?

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

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

Source

pub fn len(&self) -> usize

Examples found in repository ?

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

291    pub fn len(&self) -> usize {
292        self.node_id_manager.len()
293    }

Source

pub fn contains(&self, node_id: &BstNodeId<Spec>) -> bool

Examples found in repository ?

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

308    pub fn get(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(&M::Key, &L::Key)> {
309        if !self.node_id_manager.contains(&node_id) {
310            return None;
311        }
312        unsafe {
313            WithParent::resolve_top_down::<TreapSpec<M, L>>(
314                node_id.reborrow_datamut(&mut self.root),
315            );
316            let data = node_id.reborrow(&self.root).into_data();
317            Some((&data.key.key, &data.value.key))
318        }
319    }
320
321    pub fn change(
322        &mut self,
323        node_id: BstNodeId<TreapSpec<M, L>>,
324        f: impl FnOnce(&mut L::Key),
325    ) -> bool {
326        if !self.node_id_manager.contains(&node_id) {
327            return false;
328        }
329        unsafe {
330            WithParent::resolve_top_down::<TreapSpec<M, L>>(
331                node_id.reborrow_datamut(&mut self.root),
332            );
333            let data = node_id.reborrow_datamut(&mut self.root).into_data_mut();
334            f(&mut data.value.key);
335            WithParent::resolve_bottom_up::<TreapSpec<M, L>>(
336                node_id.reborrow_datamut(&mut self.root),
337            );
338        }
339        true
340    }
341
342    pub fn change_key_value(
343        &mut self,
344        node_id: BstNodeId<TreapSpec<M, L>>,
345        f: impl FnOnce(&mut M::Key, &mut L::Key),
346    ) -> bool {
347        if !self.node_id_manager.contains(&node_id) {
348            return false;
349        }
350        unsafe {
351            WithParent::resolve_top_down::<TreapSpec<M, L>>(
352                node_id.reborrow_datamut(&mut self.root),
353            );
354            let mut node = if WithParent::is_root(node_id.reborrow(&self.root)) {
355                WithParent::remove_root(&mut self.root).unwrap_unchecked()
356            } else {
357                WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
358            };
359            let data = node.borrow_datamut().into_data_mut();
360            f(&mut data.key.key, &mut data.value.key);
361            self.root = TreapSpec::merge_ordered(self.root.take(), Some(node));
362            true
363        }
364    }
365
366    pub fn insert(&mut self, key: M::Key, value: L::Key) -> BstNodeId<TreapSpec<M, L>> {
367        let (left, right) =
368            TreapSpec::split(self.root.take(), SeekByKey::new(&key), EqualSide::Right);
369        let data = TreapData {
370            priority: self.rng.rand64(),
371            key: MonoidActElement::from_key(key),
372            value: LazyMapElement::from_key(value),
373        };
374        let node = BstRoot::from_data(data, self.allocator.deref_mut());
375        let node_id = self.node_id_manager.register(&node);
376        self.root = TreapSpec::merge(TreapSpec::merge(left, Some(node)), right);
377        node_id
378    }
379
380    pub fn remove(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(M::Key, L::Key)> {
381        if !self.node_id_manager.contains(&node_id) {
382            return None;
383        }
384        unsafe {
385            WithParent::resolve_top_down::<TreapSpec<M, L>>(
386                node_id.reborrow_datamut(&mut self.root),
387            );
388            let node = if WithParent::is_root(node_id.reborrow(&self.root)) {
389                WithParent::remove_root(&mut self.root).unwrap_unchecked()
390            } else {
391                WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
392            };
393            self.node_id_manager.unregister(node_id);
394            let data = node.into_dying().into_data(self.allocator.deref_mut());
395            Some((data.key.key, data.value.key))
396        }
397    }

Source

pub fn registered_node_id( &self, node: BstNodeRef<Immut<'_>, Spec>, ) -> Option<BstNodeId<Spec>>

Examples found in repository ?

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

412    pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>
413    where
414        M: MonoidAct<Key: Borrow<Q>>,
415        Q: Ord + ?Sized,
416    {
417        let split = Split::new(
418            &mut self.root,
419            SeekByKey::<TreapSpec<M, L>, M::Key, Q>::new(key),
420            EqualSide::Right,
421        );
422        let node = split.right()?.leftmost();
423        matches!(node.into_data().key.key.borrow().cmp(key), Ordering::Equal)
424            .then(|| self.node_id_manager.registered_node_id(node))
425            .flatten()
426    }
427
428    pub fn find_by_acc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
429    where
430        F: FnMut(&L::Agg) -> bool,
431    {
432        let split = Split::new(
433            &mut self.root,
434            SeekByAccCond::<TreapSpec<M, L>, L, F>::new(f),
435            EqualSide::Right,
436        );
437        let node = split.right()?.leftmost();
438        self.node_id_manager.registered_node_id(node)
439    }
440
441    pub fn find_by_racc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
442    where
443        F: FnMut(&L::Agg) -> bool,
444    {
445        let split = Split::new(
446            &mut self.root,
447            SeekByRaccCond::<TreapSpec<M, L>, L, F>::new(f),
448            EqualSide::Left,
449        );
450        let node = split.left()?.rightmost();
451        self.node_id_manager.registered_node_id(node)
452    }

Source

pub fn clear(&mut self)

Examples found in repository ?

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

299    pub fn clear(&mut self) {
300        unsafe {
301            if let Some(root) = self.root.take() {
302                root.into_dying().drop_all(self.allocator.deref_mut());
303            }
304            self.node_id_manager.clear();
305        }
306    }

Source

pub fn register(&mut self, node: &BstRoot<Spec>) -> BstNodeId<Spec>

Examples found in repository ?

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

366    pub fn insert(&mut self, key: M::Key, value: L::Key) -> BstNodeId<TreapSpec<M, L>> {
367        let (left, right) =
368            TreapSpec::split(self.root.take(), SeekByKey::new(&key), EqualSide::Right);
369        let data = TreapData {
370            priority: self.rng.rand64(),
371            key: MonoidActElement::from_key(key),
372            value: LazyMapElement::from_key(value),
373        };
374        let node = BstRoot::from_data(data, self.allocator.deref_mut());
375        let node_id = self.node_id_manager.register(&node);
376        self.root = TreapSpec::merge(TreapSpec::merge(left, Some(node)), right);
377        node_id
378    }

Source

pub fn unregister(&mut self, node_id: BstNodeId<Spec>)

Examples found in repository ?

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

380    pub fn remove(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(M::Key, L::Key)> {
381        if !self.node_id_manager.contains(&node_id) {
382            return None;
383        }
384        unsafe {
385            WithParent::resolve_top_down::<TreapSpec<M, L>>(
386                node_id.reborrow_datamut(&mut self.root),
387            );
388            let node = if WithParent::is_root(node_id.reborrow(&self.root)) {
389                WithParent::remove_root(&mut self.root).unwrap_unchecked()
390            } else {
391                WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
392            };
393            self.node_id_manager.unregister(node_id);
394            let data = node.into_dying().into_data(self.allocator.deref_mut());
395            Some((data.key.key, data.value.key))
396        }
397    }