Skip to main content

WithParent

competitive::data_structure::binary_search_tree::node

Struct WithParent 

Source 
pub struct WithParent<Data> {
    pub parent: Option<NonNull<BstNode<Data, Self>>>,
}

Fields§

§parent: Option<NonNull<BstNode<Data, Self>>>

Implementations§

Source§

impl<Data> WithParent<Data>

Source

pub fn resolve_top_down<Spec>(node: BstNodeRef<DataMut<'_>, Spec>)
where Spec: BstSpec<Data = Data, Parent = Self>,

Examples found in repository?
crates/competitive/src/data_structure/treap.rs (lines 313-315)
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 resolve_bottom_up<Spec>(node: BstNodeRef<DataMut<'_>, Spec>)
where Spec: BstSpec<Data = Data, Parent = Self>,

Examples found in repository?
crates/competitive/src/data_structure/treap.rs (lines 335-337)
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    }
More examples
Hide additional examples
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 217)
193    pub unsafe fn remove_not_root<Spec>(
194        mut node: BstNodeRef<marker::Mut<'_>, Spec>,
195    ) -> BstNodeRef<marker::Owned, Spec>
196    where
197        Spec: BstSpec<Data = Data, Parent = Self>,
198    {
199        assert!(!Self::is_root(node.reborrow()));
200        unsafe {
201            let left = node.left_mut().take();
202            let right = node.right_mut().take();
203            let merged = Spec::merge(left, right);
204            let node_inner = node.node;
205            let mut parent = node.ascend().unwrap_unchecked();
206            let mut node = if let Some(merged) = merged {
207                let node = if parent
208                    .reborrow()
209                    .left()
210                    .descend()
211                    .is_ok_and(|n| n.node == node_inner)
212                {
213                    parent.left_mut().replace(merged)
214                } else {
215                    parent.right_mut().replace(merged)
216                };
217                Self::resolve_bottom_up(parent.reborrow_datamut());
218                node.unwrap_unchecked()
219            } else {
220                let node = if parent
221                    .reborrow()
222                    .left()
223                    .descend()
224                    .is_ok_and(|n| n.node == node_inner)
225                {
226                    parent.left_mut().take()
227                } else {
228                    parent.right_mut().take()
229                };
230                Self::resolve_bottom_up(parent.reborrow_datamut());
231                node.unwrap_unchecked()
232            };
233            Spec::bottom_up(node.borrow_datamut());
234            node
235        }
236    }
Source

pub fn is_root<Spec>(node: BstNodeRef<Immut<'_>, Spec>) -> bool
where Spec: BstSpec<Data = Data, Parent = Self>,

Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 354)
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    }
More examples
Hide additional examples
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 199)
193    pub unsafe fn remove_not_root<Spec>(
194        mut node: BstNodeRef<marker::Mut<'_>, Spec>,
195    ) -> BstNodeRef<marker::Owned, Spec>
196    where
197        Spec: BstSpec<Data = Data, Parent = Self>,
198    {
199        assert!(!Self::is_root(node.reborrow()));
200        unsafe {
201            let left = node.left_mut().take();
202            let right = node.right_mut().take();
203            let merged = Spec::merge(left, right);
204            let node_inner = node.node;
205            let mut parent = node.ascend().unwrap_unchecked();
206            let mut node = if let Some(merged) = merged {
207                let node = if parent
208                    .reborrow()
209                    .left()
210                    .descend()
211                    .is_ok_and(|n| n.node == node_inner)
212                {
213                    parent.left_mut().replace(merged)
214                } else {
215                    parent.right_mut().replace(merged)
216                };
217                Self::resolve_bottom_up(parent.reborrow_datamut());
218                node.unwrap_unchecked()
219            } else {
220                let node = if parent
221                    .reborrow()
222                    .left()
223                    .descend()
224                    .is_ok_and(|n| n.node == node_inner)
225                {
226                    parent.left_mut().take()
227                } else {
228                    parent.right_mut().take()
229                };
230                Self::resolve_bottom_up(parent.reborrow_datamut());
231                node.unwrap_unchecked()
232            };
233            Spec::bottom_up(node.borrow_datamut());
234            node
235        }
236    }
Source

pub unsafe fn remove_root<Spec>( root: &mut Option<BstRoot<Spec>>, ) -> Option<BstNodeRef<Owned, Spec>>
where Spec: BstSpec<Data = Data, Parent = Self>,

Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 355)
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 unsafe fn remove_not_root<Spec>( node: BstNodeRef<Mut<'_>, Spec>, ) -> BstNodeRef<Owned, Spec>
where Spec: BstSpec<Data = Data, Parent = Self>,

Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 357)
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    }

Trait Implementations§

Source§

impl<Data> Default for WithParent<Data>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<Data> ParentStrategy for WithParent<Data>

Source§

type Data = Data

Source§

fn take_parent<Spec>(node: BstNodeRef<Mut<'_>, Spec>)
where Spec: BstSpec<Data = Self::Data, Parent = Self>,

Source§

fn set_parent<Spec>( node: BstNodeRef<Mut<'_>, Spec>, parent: Option<NonNull<BstNode<Spec::Data, Self>>>, )
where Spec: BstSpec<Data = Self::Data, Parent = Self>,

Auto Trait Implementations§

§

impl<Data> !Send for WithParent<Data>

§

impl<Data> !Sync for WithParent<Data>

§

impl<Data> Freeze for WithParent<Data>
where Option<NonNull<BstNode<Data, WithParent<Data>>>>: Freeze,

§

impl<Data> RefUnwindSafe for WithParent<Data>
where Option<NonNull<BstNode<Data, WithParent<Data>>>>: RefUnwindSafe,

§

impl<Data> Unpin for WithParent<Data>
where Option<NonNull<BstNode<Data, WithParent<Data>>>>: Unpin,

§

impl<Data> UnsafeUnpin for WithParent<Data>
where Option<NonNull<BstNode<Data, WithParent<Data>>>>: UnsafeUnpin,

§

impl<Data> UnwindSafe for WithParent<Data>
where Option<NonNull<BstNode<Data, WithParent<Data>>>>: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.