competitive::data_structure::binary_search_tree::seeker

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§

Source §

impl<'a, Spec, K, Q> SeekByKey<'a, Spec, K, Q>
where Q: ?Sized,

Source

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

Examples found in repository ?

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

142    pub fn seek_by_key<K, Q, R>(node: &'a mut Option<BstRoot<Spec>>, range: R) -> Self
143    where
144        Spec: BstSpec<Data: BstDataAccess<data::marker::Key, Value = K>>,
145        K: Borrow<Q>,
146        Q: Ord + ?Sized,
147        R: RangeBounds<Q>,
148    {
149        let start = match range.start_bound() {
150            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
151            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
152            Bound::Unbounded => Bound::Unbounded,
153        };
154        let end = match range.end_bound() {
155            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
156            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
157            Bound::Unbounded => Bound::Unbounded,
158        };
159        Self::new(node, start, end)
160    }

More examples

Hide additional examples

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

192    pub fn merge_ordered(
193        left: Option<TreapRoot<M, L>>,
194        right: Option<TreapRoot<M, L>>,
195    ) -> Option<TreapRoot<M, L>> {
196        match (left, right) {
197            (None, None) => None,
198            (None, Some(node)) | (Some(node), None) => Some(node),
199            (Some(mut left), Some(mut right)) => unsafe {
200                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201                    Self::top_down(left.borrow_datamut());
202                    let key = &left.reborrow().into_data().key.key;
203                    let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204                    let ll = left.borrow_mut().left().take();
205                    let lr = left.borrow_mut().right().take();
206                    if let Some(l) = Self::merge_ordered(ll, rl) {
207                        left.borrow_mut().left().set(l);
208                    }
209                    if let Some(r) = Self::merge_ordered(lr, rr) {
210                        left.borrow_mut().right().set(r);
211                    }
212                    Self::bottom_up(left.borrow_datamut());
213                    Some(left)
214                } else {
215                    Self::top_down(right.borrow_datamut());
216                    let key = &right.reborrow().into_data().key.key;
217                    let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218                    let rl = right.borrow_mut().left().take();
219                    let rr = right.borrow_mut().right().take();
220                    if let Some(l) = Self::merge_ordered(ll, rl) {
221                        right.borrow_mut().left().set(l);
222                    }
223                    if let Some(r) = Self::merge_ordered(lr, rr) {
224                        right.borrow_mut().right().set(r);
225                    }
226                    Self::bottom_up(right.borrow_datamut());
227                    Some(right)
228                }
229            },
230        }
231    }
232}
233
234pub struct Treap<M, L, A = BoxAllocator<TreapNode<M, L>>>
235where
236    M: MonoidAct<Key: Ord>,
237    L: LazyMapMonoid,
238    A: Allocator<TreapNode<M, L>>,
239{
240    root: Option<TreapRoot<M, L>>,
241    node_id_manager: BstNodeIdManager<TreapSpec<M, L>>,
242    rng: Xorshift,
243    allocator: ManuallyDrop<A>,
244    _marker: PhantomData<(M, L)>,
245}
246
247impl<M, L, A> Default for Treap<M, L, A>
248where
249    M: MonoidAct<Key: Ord>,
250    L: LazyMapMonoid,
251    A: Allocator<TreapNode<M, L>> + Default,
252{
253    fn default() -> Self {
254        Self {
255            root: None,
256            node_id_manager: Default::default(),
257            rng: Xorshift::new(),
258            allocator: ManuallyDrop::new(A::default()),
259            _marker: PhantomData,
260        }
261    }
262}
263
264impl<M, L, A> Drop for Treap<M, L, A>
265where
266    M: MonoidAct<Key: Ord>,
267    L: LazyMapMonoid,
268    A: Allocator<TreapNode<M, L>>,
269{
270    fn drop(&mut self) {
271        unsafe {
272            if let Some(root) = self.root.take() {
273                root.into_dying().drop_all(self.allocator.deref_mut());
274            }
275            ManuallyDrop::drop(&mut self.allocator);
276        }
277    }
278}
279
280impl<M, L> Treap<M, L>
281where
282    M: MonoidAct<Key: Ord>,
283    L: LazyMapMonoid,
284{
285    pub fn new() -> Self {
286        Self::default()
287    }
288}
289
290impl<M, L, A> Treap<M, L, A>
291where
292    M: MonoidAct<Key: Ord>,
293    L: LazyMapMonoid,
294    A: Allocator<TreapNode<M, L>>,
295{
296    pub fn len(&self) -> usize {
297        self.node_id_manager.len()
298    }
299
300    pub fn is_empty(&self) -> bool {
301        self.node_id_manager.is_empty()
302    }
303
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    }
312
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    }
402
403    pub fn range_by_key<Q, R>(&mut self, range: R) -> TreapSplit3<'_, M, L>
404    where
405        M: MonoidAct<Key: Borrow<Q>>,
406        Q: Ord + ?Sized,
407        R: RangeBounds<Q>,
408    {
409        let split3 = Split3::seek_by_key(&mut self.root, range);
410        TreapSplit3 {
411            split3,
412            key_updated: false,
413        }
414    }
415
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    }