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 301)

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

Source

pub fn len(&self) -> usize

Examples found in repository ?

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

296    pub fn len(&self) -> usize {
297        self.node_id_manager.len()
298    }

Source

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

Examples found in repository ?

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

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

Source

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

Examples found in repository ?

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

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

Source

pub fn clear(&mut self)

Examples found in repository ?

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

304    pub fn clear(&mut self) {
305        unsafe {
306            if let Some(root) = self.root.take() {
307                root.into_dying().drop_all(self.allocator.deref_mut());
308            }
309            self.node_id_manager.clear();
310        }
311    }

Source

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

Examples found in repository ?

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

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

Source

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

Examples found in repository ?

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

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