Struct SeekByKey 

pub struct SeekByKey<'a, Spec, K, Q>
where
    Q: ?Sized,
{
    key: &'a Q,
    _marker: PhantomData<fn() -> (Spec, K)>,
}

Fields

key: &'a Q

_marker: PhantomData<fn() -> (Spec, K)>

Implementations

impl<'a, Spec, K, Q> SeekByKey<'a, Spec, K, Q>

where Q: ?Sized,

pub fn new(key: &'a Q) -> Self

Examples found in repository

crates/competitive/src/data_structure/splay_tree.rs (line 197)

    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.splay(SeekByKey::new(key))
    }

crates/competitive/src/data_structure/binary_search_tree/split.rs (line 161)

    pub fn seek_by_key<K, Q, R>(node: &'a mut Option<BstRoot<Spec>>, range: R) -> Self
    where
        Spec: BstSpec<Data: BstDataAccess<data::marker::Key, Value = K>>,
        K: Borrow<Q>,
        Q: Ord + ?Sized,
        R: RangeBounds<Q>,
    {
        let start = match range.start_bound() {
            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
            Bound::Unbounded => Bound::Unbounded,
        };
        let end = match range.end_bound() {
            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
            Bound::Unbounded => Bound::Unbounded,
        };
        Self::new(node, start, end)
    }

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

    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
        }
    }

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

    pub fn remove(&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 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))
            };
            self.node_id_manager.unregister(node_id);
            let data = node.into_dying().into_data(self.allocator.deref_mut());
            Some((data.key.key, data.value.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>,
    {
        let split3 = Split3::seek_by_key(&mut self.root, range);
        TreapSplit3 {
            split3,
            key_updated: false,
        }
    }

    pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>
    where
        M: MonoidAct<Key: Borrow<Q>>,
        Q: Ord + ?Sized,
    {
        let split = Split::new(
            &mut self.root,
            SeekByKey::<TreapSpec<M, L>, M::Key, Q>::new(key),
            EqualSide::Right,
        );
        let node = split.right()?.leftmost();
        matches!(node.into_data().key.key.borrow().cmp(key), Ordering::Equal)
            .then(|| self.node_id_manager.registered_node_id(node))
            .flatten()
    }

Trait Implementations

impl<Spec, K, Q> BstSeeker for SeekByKey<'_, Spec, K, Q>

where Spec: BstSpec<Data: BstDataAccess<Key, Value = K>>, K: Borrow<Q>, Q: Ord + ?Sized,

type Spec = Spec

fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering