Root

competitive::data_structure::splay_tree::node

Struct Root 

Source 
pub struct Root<S>
where
    S: SplaySpec,
{
    root: Option<NodeRef<Owned, S>>,
}

Fields§

§root: Option<NodeRef<Owned, S>>

Implementations§

Source§

impl<S> Root<S>
where S: SplaySpec,

Source

pub fn new(root: Option<NodeRef<Owned, S>>) -> Self

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 468)
466    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467        if nodes.is_empty() {
468            Self::new(None)
469        } else {
470            let m = nodes.len() / 2;
471            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473            let mut node = NodeRef::new(nodes[m].node);
474            node.borrow_mut().set_left(left.root);
475            node.borrow_mut().set_right(right.root);
476            S::bottom_up(node.borrow_datamut());
477            Self::new(Some(node))
478        }
479    }
480    pub fn is_empty(&self) -> bool {
481        self.root.is_none()
482    }
483    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484        Some(self.root.as_ref()?.reborrow())
485    }
486    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487        Some(self.root.as_mut()?.borrow_datamut())
488    }
489    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490    where
491        Seeker: SplaySeeker<S = S>,
492    {
493        let (ord, root) = self.root.take()?.splay_by(seeker);
494        self.root = Some(root);
495        Some(ord)
496    }
497    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498        self.root = Some(match self.root.take() {
499            Some(root) => root.insert_left(node),
500            None => {
501                S::bottom_up(node.borrow_datamut());
502                node
503            }
504        });
505    }
506    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507        self.root = Some(match self.root.take() {
508            Some(root) => root.insert_right(node),
509            None => {
510                S::bottom_up(node.borrow_datamut());
511                node
512            }
513        });
514    }
515    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516        self.root = Some(match self.root.take() {
517            Some(root) => root.insert_first(node),
518            None => {
519                S::bottom_up(node.borrow_datamut());
520                node
521            }
522        });
523    }
524    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525        self.root = Some(match self.root.take() {
526            Some(root) => root.insert_last(node),
527            None => {
528                S::bottom_up(node.borrow_datamut());
529                node
530            }
531        });
532    }
533    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534        let mut root = self.root.take()?;
535        let right = root.borrow_mut().take_right();
536        self.root = root.borrow_mut().take_left();
537        self.append(&mut Self::new(right));
538        Some(root)
539    }
540    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542        let right = root.borrow_mut().take_right();
543        self.root = right;
544        Some(root)
545    }
546    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548        let left = root.borrow_mut().take_left();
549        self.root = left;
550        Some(root)
551    }
552    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553        let root = self.root.as_mut()?;
554        let left = root.borrow_mut().take_left();
555        S::bottom_up(root.borrow_datamut());
556        left
557    }
558    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559        let root = self.root.as_mut()?;
560        let right = root.borrow_mut().take_right();
561        S::bottom_up(root.borrow_datamut());
562        right
563    }
564    pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
565        let right = self.split_right();
566        replace(&mut self.root, right)
567    }
568    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569        let left = self.split_left();
570        replace(&mut self.root, left)
571    }
572    pub fn append(&mut self, other: &mut Self) {
573        self.root = match (self.root.take(), other.root.take()) {
574            (Some(node), None) | (None, Some(node)) => Some(node),
575            (Some(left), Some(right)) => Some(left.merge(right)),
576            (None, None) => None,
577        }
578    }
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
613}
614
615impl<S> Debug for Root<S>
616where
617    S: SplaySpec<T: Debug>,
618{
619    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
620        fn fmt_recurse<'a, S>(
621            node: NodeRef<marker::Immut<'a>, S>,
622            f: &mut fmt::Formatter<'_>,
623        ) -> fmt::Result
624        where
625            S: SplaySpec<T: 'a + Debug>,
626        {
627            write!(f, "[")?;
628            if let Some(left) = node.left() {
629                fmt_recurse(left, f)?;
630            }
631            node.data().fmt(f)?;
632            if let Some(right) = node.right() {
633                fmt_recurse(right, f)?;
634            }
635            write!(f, "]")?;
636            Ok(())
637        }
638        if let Some(root) = self.root.as_ref() {
639            let root = root.reborrow();
640            fmt_recurse(root, f)?;
641        }
642        Ok(())
643    }
644}
645
646pub struct NodeRange<'a, S>
647where
648    S: SplaySpec<T: 'a>,
649{
650    front: Root<S>,
651    back: Root<S>,
652    root: &'a mut Root<S>,
653}
654
655impl<'a, S> Debug for NodeRange<'a, S>
656where
657    S: SplaySpec<T: 'a + Debug>,
658{
659    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
660        f.debug_struct("NodeRange")
661            .field("front", &self.front)
662            .field("back", &self.back)
663            .field("root", &self.root)
664            .finish()
665    }
666}
667impl<'a, S> NodeRange<'a, S>
668where
669    S: SplaySpec<T: 'a>,
670{
671    pub fn new(root: &'a mut Root<S>) -> Self {
672        Self {
673            front: Default::default(),
674            back: Default::default(),
675            root,
676        }
677    }
678    pub fn three_way(
679        front: Option<NodeRef<marker::Owned, S>>,
680        root: &'a mut Root<S>,
681        back: Option<NodeRef<marker::Owned, S>>,
682    ) -> Self {
683        Self {
684            front: Root::new(front),
685            back: Root::new(back),
686            root,
687        }
688    }
Source

pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<Owned, S>>) -> Self

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 460)
438    fn extend<I>(&mut self, iter: I)
439    where
440        I: IntoIterator<Item = T::Key>,
441    {
442        let nodes: Vec<_> = unsafe {
443            iter.into_iter()
444                .map(|key| {
445                    let agg = T::single_agg(&key);
446                    NodeRef::from_data(
447                        LazyAggElement {
448                            key,
449                            agg,
450                            lazy: T::act_unit(),
451                            size: 1,
452                            rev: false,
453                        },
454                        self.alloc.deref_mut(),
455                    )
456                })
457                .collect()
458        };
459        self.length += nodes.len();
460        let mut root = unsafe { Root::from_single_nodes(nodes) };
461        self.root.append(&mut root);
462    }
Source

unsafe fn from_single_nodes_inner(nodes: &[NodeRef<Owned, S>]) -> Self

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 464)
463    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464        unsafe { Self::from_single_nodes_inner(&nodes) }
465    }
466    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467        if nodes.is_empty() {
468            Self::new(None)
469        } else {
470            let m = nodes.len() / 2;
471            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473            let mut node = NodeRef::new(nodes[m].node);
474            node.borrow_mut().set_left(left.root);
475            node.borrow_mut().set_right(right.root);
476            S::bottom_up(node.borrow_datamut());
477            Self::new(Some(node))
478        }
479    }
Source

pub fn is_empty(&self) -> bool

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 583)
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
Source

pub fn root(&self) -> Option<NodeRef<Immut<'_>, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 334)
330    pub fn fold<R>(&mut self, range: R) -> T::Agg
331    where
332        R: RangeBounds<usize>,
333    {
334        if let Some(root) = self.range(range).root().root() {
335            root.data().agg.clone()
336        } else {
337            T::agg_unit()
338        }
339    }
340    pub fn reverse<R>(&mut self, range: R)
341    where
342        R: RangeBounds<usize>,
343    {
344        if let Some(root) = self.range(range).root_mut().root_data_mut() {
345            LazyAggSplay::<T>::reverse(root);
346        }
347    }
348    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349        self.root.splay_by(SeekBySize::new(index))?;
350        self.root.root().map(|root| &root.data().key)
351    }
352    pub fn modify<F>(&mut self, index: usize, f: F)
353    where
354        F: FnOnce(&T::Key) -> T::Key,
355    {
356        self.root.splay_by(SeekBySize::new(index)).unwrap();
357        let data = self.root.root_data_mut().unwrap().data_mut();
358        data.key = f(&data.key);
359        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360    }
361    pub fn insert(&mut self, index: usize, x: T::Key) {
362        assert!(index <= self.length);
363        self.root.splay_by(SeekBySize::new(index));
364        let agg = T::single_agg(&x);
365        unsafe {
366            let node = NodeRef::from_data(
367                LazyAggElement {
368                    key: x,
369                    agg,
370                    lazy: T::act_unit(),
371                    size: 1,
372                    rev: false,
373                },
374                self.alloc.deref_mut(),
375            );
376            if index == self.length {
377                self.root.insert_right(node);
378            } else {
379                self.root.insert_left(node);
380            }
381        }
382        self.length += 1;
383    }
384    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385        if index >= self.length {
386            return None;
387        }
388        self.root.splay_by(SeekBySize::new(index));
389        self.length -= 1;
390        let node = self.root.take_root().unwrap().into_dying();
391        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392    }
393    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394    where
395        R: RangeBounds<usize>,
396        F: FnMut(&T::Agg) -> bool,
397    {
398        let mut range = self.range(range);
399        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400        if !matches!(ord, Some(Ordering::Equal)) {
401            return None;
402        }
403        let front_size = range.front().size();
404        let left_size = range.root().left_size();
405        Some(front_size + left_size)
406    }
407    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408    where
409        R: RangeBounds<usize>,
410        F: FnMut(&T::Agg) -> bool,
411    {
412        let mut range = self.range(range);
413        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414        if !matches!(ord, Some(Ordering::Equal)) {
415            return None;
416        }
417        let front_size = range.front().size();
418        let left_size = range.root().left_size();
419        Some(front_size + left_size)
420    }
421    pub fn rotate_left(&mut self, mid: usize) {
422        assert!(mid <= self.length);
423        if mid != 0 || mid != self.length {
424            self.range(mid..).drop_rotate_left()
425        }
426    }
427    pub fn rotate_right(&mut self, k: usize) {
428        assert!(k <= self.length);
429        self.rotate_left(self.length - k);
430    }
431}
432
433impl<T, A> Extend<T::Key> for SplaySequence<T, A>
434where
435    T: LazyMapMonoid,
436    A: Allocator<Node<LazyAggElement<T>>>,
437{
438    fn extend<I>(&mut self, iter: I)
439    where
440        I: IntoIterator<Item = T::Key>,
441    {
442        let nodes: Vec<_> = unsafe {
443            iter.into_iter()
444                .map(|key| {
445                    let agg = T::single_agg(&key);
446                    NodeRef::from_data(
447                        LazyAggElement {
448                            key,
449                            agg,
450                            lazy: T::act_unit(),
451                            size: 1,
452                            rev: false,
453                        },
454                        self.alloc.deref_mut(),
455                    )
456                })
457                .collect()
458        };
459        self.length += nodes.len();
460        let mut root = unsafe { Root::from_single_nodes(nodes) };
461        self.root.append(&mut root);
462    }
463}
464
465impl<T> Root<LazyAggSplay<T>>
466where
467    T: LazyMapMonoid,
468{
469    fn size(&self) -> usize {
470        self.root().map(|root| root.data().size).unwrap_or_default()
471    }
472    fn left_size(&self) -> usize {
473        self.root()
474            .and_then(|root| root.left().map(|left| left.data().size))
475            .unwrap_or_default()
476    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 171)
163    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
164    where
165        K: Borrow<Q>,
166        Q: Ord + ?Sized,
167    {
168        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
169            return None;
170        }
171        self.root.root().map(|node| {
172            let ((k, v), _) = node.data();
173            (k, v)
174        })
175    }
176    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
177        self.root.splay_by(SeekBySize::new(index))
178    }
179    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
180        if index >= self.length {
181            return None;
182        }
183        self.splay_at(index);
184        self.root.root().map(|node| {
185            let ((k, v), _) = node.data();
186            (k, v)
187        })
188    }
Source

pub fn root_data_mut(&mut self) -> Option<NodeRef<DataMut<'_>, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 326)
322    pub fn update<R>(&mut self, range: R, x: T::Act)
323    where
324        R: RangeBounds<usize>,
325    {
326        if let Some(root) = self.range(range).root_mut().root_data_mut() {
327            LazyAggSplay::<T>::update_lazy(root, &x);
328        }
329    }
330    pub fn fold<R>(&mut self, range: R) -> T::Agg
331    where
332        R: RangeBounds<usize>,
333    {
334        if let Some(root) = self.range(range).root().root() {
335            root.data().agg.clone()
336        } else {
337            T::agg_unit()
338        }
339    }
340    pub fn reverse<R>(&mut self, range: R)
341    where
342        R: RangeBounds<usize>,
343    {
344        if let Some(root) = self.range(range).root_mut().root_data_mut() {
345            LazyAggSplay::<T>::reverse(root);
346        }
347    }
348    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349        self.root.splay_by(SeekBySize::new(index))?;
350        self.root.root().map(|root| &root.data().key)
351    }
352    pub fn modify<F>(&mut self, index: usize, f: F)
353    where
354        F: FnOnce(&T::Key) -> T::Key,
355    {
356        self.root.splay_by(SeekBySize::new(index)).unwrap();
357        let data = self.root.root_data_mut().unwrap().data_mut();
358        data.key = f(&data.key);
359        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 198)
189    pub fn insert(&mut self, key: K, value: V) -> Option<V>
190    where
191        K: Ord,
192    {
193        let ord = self.splay_by_key(&key);
194        self.length += (ord != Some(Ordering::Equal)) as usize;
195        match ord {
196            Some(Ordering::Equal) => {
197                return Some(replace(
198                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199                    value,
200                ));
201            }
202            Some(Ordering::Less) => unsafe {
203                self.root.insert_left(NodeRef::from_data(
204                    ((key, value), 1),
205                    self.alloc.deref_mut(),
206                ));
207            },
208            _ => unsafe {
209                self.root.insert_right(NodeRef::from_data(
210                    ((key, value), 1),
211                    self.alloc.deref_mut(),
212                ));
213            },
214        }
215        None
216    }
Source

pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
where Seeker: SplaySeeker<S = S>,

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 349)
348    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349        self.root.splay_by(SeekBySize::new(index))?;
350        self.root.root().map(|root| &root.data().key)
351    }
352    pub fn modify<F>(&mut self, index: usize, f: F)
353    where
354        F: FnOnce(&T::Key) -> T::Key,
355    {
356        self.root.splay_by(SeekBySize::new(index)).unwrap();
357        let data = self.root.root_data_mut().unwrap().data_mut();
358        data.key = f(&data.key);
359        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360    }
361    pub fn insert(&mut self, index: usize, x: T::Key) {
362        assert!(index <= self.length);
363        self.root.splay_by(SeekBySize::new(index));
364        let agg = T::single_agg(&x);
365        unsafe {
366            let node = NodeRef::from_data(
367                LazyAggElement {
368                    key: x,
369                    agg,
370                    lazy: T::act_unit(),
371                    size: 1,
372                    rev: false,
373                },
374                self.alloc.deref_mut(),
375            );
376            if index == self.length {
377                self.root.insert_right(node);
378            } else {
379                self.root.insert_left(node);
380            }
381        }
382        self.length += 1;
383    }
384    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385        if index >= self.length {
386            return None;
387        }
388        self.root.splay_by(SeekBySize::new(index));
389        self.length -= 1;
390        let node = self.root.take_root().unwrap().into_dying();
391        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392    }
393    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394    where
395        R: RangeBounds<usize>,
396        F: FnMut(&T::Agg) -> bool,
397    {
398        let mut range = self.range(range);
399        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400        if !matches!(ord, Some(Ordering::Equal)) {
401            return None;
402        }
403        let front_size = range.front().size();
404        let left_size = range.root().left_size();
405        Some(front_size + left_size)
406    }
407    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408    where
409        R: RangeBounds<usize>,
410        F: FnMut(&T::Agg) -> bool,
411    {
412        let mut range = self.range(range);
413        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414        if !matches!(ord, Some(Ordering::Equal)) {
415            return None;
416        }
417        let front_size = range.front().size();
418        let left_size = range.root().left_size();
419        Some(front_size + left_size)
420    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 161)
156    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
157    where
158        K: Borrow<Q>,
159        Q: Ord + ?Sized,
160    {
161        self.root.splay_by(SeekByKey::new(key))
162    }
163    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
164    where
165        K: Borrow<Q>,
166        Q: Ord + ?Sized,
167    {
168        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
169            return None;
170        }
171        self.root.root().map(|node| {
172            let ((k, v), _) = node.data();
173            (k, v)
174        })
175    }
176    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
177        self.root.splay_by(SeekBySize::new(index))
178    }
crates/competitive/src/data_structure/splay_tree/node.rs (line 587)
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
Source

pub fn insert_left(&mut self, node: NodeRef<Owned, S>)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 379)
361    pub fn insert(&mut self, index: usize, x: T::Key) {
362        assert!(index <= self.length);
363        self.root.splay_by(SeekBySize::new(index));
364        let agg = T::single_agg(&x);
365        unsafe {
366            let node = NodeRef::from_data(
367                LazyAggElement {
368                    key: x,
369                    agg,
370                    lazy: T::act_unit(),
371                    size: 1,
372                    rev: false,
373                },
374                self.alloc.deref_mut(),
375            );
376            if index == self.length {
377                self.root.insert_right(node);
378            } else {
379                self.root.insert_left(node);
380            }
381        }
382        self.length += 1;
383    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (lines 203-206)
189    pub fn insert(&mut self, key: K, value: V) -> Option<V>
190    where
191        K: Ord,
192    {
193        let ord = self.splay_by_key(&key);
194        self.length += (ord != Some(Ordering::Equal)) as usize;
195        match ord {
196            Some(Ordering::Equal) => {
197                return Some(replace(
198                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199                    value,
200                ));
201            }
202            Some(Ordering::Less) => unsafe {
203                self.root.insert_left(NodeRef::from_data(
204                    ((key, value), 1),
205                    self.alloc.deref_mut(),
206                ));
207            },
208            _ => unsafe {
209                self.root.insert_right(NodeRef::from_data(
210                    ((key, value), 1),
211                    self.alloc.deref_mut(),
212                ));
213            },
214        }
215        None
216    }
Source

pub fn insert_right(&mut self, node: NodeRef<Owned, S>)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 377)
361    pub fn insert(&mut self, index: usize, x: T::Key) {
362        assert!(index <= self.length);
363        self.root.splay_by(SeekBySize::new(index));
364        let agg = T::single_agg(&x);
365        unsafe {
366            let node = NodeRef::from_data(
367                LazyAggElement {
368                    key: x,
369                    agg,
370                    lazy: T::act_unit(),
371                    size: 1,
372                    rev: false,
373                },
374                self.alloc.deref_mut(),
375            );
376            if index == self.length {
377                self.root.insert_right(node);
378            } else {
379                self.root.insert_left(node);
380            }
381        }
382        self.length += 1;
383    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (lines 209-212)
189    pub fn insert(&mut self, key: K, value: V) -> Option<V>
190    where
191        K: Ord,
192    {
193        let ord = self.splay_by_key(&key);
194        self.length += (ord != Some(Ordering::Equal)) as usize;
195        match ord {
196            Some(Ordering::Equal) => {
197                return Some(replace(
198                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199                    value,
200                ));
201            }
202            Some(Ordering::Less) => unsafe {
203                self.root.insert_left(NodeRef::from_data(
204                    ((key, value), 1),
205                    self.alloc.deref_mut(),
206                ));
207            },
208            _ => unsafe {
209                self.root.insert_right(NodeRef::from_data(
210                    ((key, value), 1),
211                    self.alloc.deref_mut(),
212                ));
213            },
214        }
215        None
216    }
Source

pub fn insert_first(&mut self, node: NodeRef<Owned, S>)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 698)
695    pub fn next_back_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
696        let last = self.root.take_last()?;
697        let noderef = unsafe { NodeRef::new_unchecked(last.node) };
698        self.back.insert_first(last);
699        Some(noderef)
700    }
Source

pub fn insert_last(&mut self, node: NodeRef<Owned, S>)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 692)
689    pub fn next_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
690        let first = self.root.take_first()?;
691        let noderef = unsafe { NodeRef::new_unchecked(first.node) };
692        self.front.insert_last(first);
693        Some(noderef)
694    }
Source

pub fn take_root(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 390)
384    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385        if index >= self.length {
386            return None;
387        }
388        self.root.splay_by(SeekBySize::new(index));
389        self.length -= 1;
390        let node = self.root.take_root().unwrap().into_dying();
391        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 226)
217    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
218    where
219        K: Borrow<Q>,
220        Q: Ord + ?Sized,
221    {
222        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
223            return None;
224        }
225        self.length -= 1;
226        let node = self.root.take_root().unwrap().into_dying();
227        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
228    }
229    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
230        if index >= self.length {
231            return None;
232        }
233        self.splay_at(index);
234        self.length -= 1;
235        let node = self.root.take_root().unwrap().into_dying();
236        unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
237    }
Source

pub fn take_first(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 258)
256    fn drop(&mut self) {
257        unsafe {
258            while let Some(node) = self.root.take_first() {
259                self.alloc.deallocate(node.into_dying().into_inner());
260            }
261            ManuallyDrop::drop(&mut self.alloc);
262        }
263    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 112)
110    fn drop(&mut self) {
111        unsafe {
112            while let Some(node) = self.root.take_first() {
113                self.alloc.deallocate(node.into_dying().into_inner());
114            }
115            ManuallyDrop::drop(&mut self.alloc);
116        }
117    }
crates/competitive/src/data_structure/splay_tree/node.rs (line 690)
689    pub fn next_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
690        let first = self.root.take_first()?;
691        let noderef = unsafe { NodeRef::new_unchecked(first.node) };
692        self.front.insert_last(first);
693        Some(noderef)
694    }
Source

pub fn take_last(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 696)
695    pub fn next_back_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
696        let last = self.root.take_last()?;
697        let noderef = unsafe { NodeRef::new_unchecked(last.node) };
698        self.back.insert_first(last);
699        Some(noderef)
700    }
Source

pub fn split_left(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 569)
568    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569        let left = self.split_left();
570        replace(&mut self.root, left)
571    }
572    pub fn append(&mut self, other: &mut Self) {
573        self.root = match (self.root.take(), other.root.take()) {
574            (Some(node), None) | (None, Some(node)) => Some(node),
575            (Some(left), Some(right)) => Some(left.merge(right)),
576            (None, None) => None,
577        }
578    }
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
Source

pub fn split_right(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 565)
564    pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
565        let right = self.split_right();
566        replace(&mut self.root, right)
567    }
568    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569        let left = self.split_left();
570        replace(&mut self.root, left)
571    }
572    pub fn append(&mut self, other: &mut Self) {
573        self.root = match (self.root.take(), other.root.take()) {
574            (Some(node), None) | (None, Some(node)) => Some(node),
575            (Some(left), Some(right)) => Some(left.merge(right)),
576            (None, None) => None,
577        }
578    }
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
Source

pub fn split_left_eq(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 603)
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
Source

pub fn split_right_eq(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 589)
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
Source

pub fn append(&mut self, other: &mut Self)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 537)
533    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534        let mut root = self.root.take()?;
535        let right = root.borrow_mut().take_right();
536        self.root = root.borrow_mut().take_left();
537        self.append(&mut Self::new(right));
538        Some(root)
539    }
540    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542        let right = root.borrow_mut().take_right();
543        self.root = right;
544        Some(root)
545    }
546    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548        let left = root.borrow_mut().take_left();
549        self.root = left;
550        Some(root)
551    }
552    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553        let root = self.root.as_mut()?;
554        let left = root.borrow_mut().take_left();
555        S::bottom_up(root.borrow_datamut());
556        left
557    }
558    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559        let root = self.root.as_mut()?;
560        let right = root.borrow_mut().take_right();
561        S::bottom_up(root.borrow_datamut());
562        right
563    }
564    pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
565        let right = self.split_right();
566        replace(&mut self.root, right)
567    }
568    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569        let left = self.split_left();
570        replace(&mut self.root, left)
571    }
572    pub fn append(&mut self, other: &mut Self) {
573        self.root = match (self.root.take(), other.root.take()) {
574            (Some(node), None) | (None, Some(node)) => Some(node),
575            (Some(left), Some(right)) => Some(left.merge(right)),
576            (None, None) => None,
577        }
578    }
579    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580    where
581        Seeker: SplaySeeker<S = S>,
582    {
583        if self.is_empty() {
584            return NodeRange::new(self);
585        }
586        let right = match end {
587            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588                Ordering::Greater | Ordering::Equal => self.split_right(),
589                Ordering::Less => self.split_right_eq(),
590            },
591            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592                Ordering::Greater => self.split_right(),
593                Ordering::Less | Ordering::Equal => self.split_right_eq(),
594            },
595            Bound::Unbounded => None,
596        };
597        if self.is_empty() {
598            return NodeRange::three_way(None, self, right);
599        }
600        let left = match start {
601            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602                Ordering::Less | Ordering::Equal => self.split_left(),
603                Ordering::Greater => self.split_left_eq(),
604            },
605            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606                Ordering::Less => self.split_left(),
607                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608            },
609            Bound::Unbounded => None,
610        };
611        NodeRange::three_way(left, self, right)
612    }
613}
614
615impl<S> Debug for Root<S>
616where
617    S: SplaySpec<T: Debug>,
618{
619    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
620        fn fmt_recurse<'a, S>(
621            node: NodeRef<marker::Immut<'a>, S>,
622            f: &mut fmt::Formatter<'_>,
623        ) -> fmt::Result
624        where
625            S: SplaySpec<T: 'a + Debug>,
626        {
627            write!(f, "[")?;
628            if let Some(left) = node.left() {
629                fmt_recurse(left, f)?;
630            }
631            node.data().fmt(f)?;
632            if let Some(right) = node.right() {
633                fmt_recurse(right, f)?;
634            }
635            write!(f, "]")?;
636            Ok(())
637        }
638        if let Some(root) = self.root.as_ref() {
639            let root = root.reborrow();
640            fmt_recurse(root, f)?;
641        }
642        Ok(())
643    }
644}
645
646pub struct NodeRange<'a, S>
647where
648    S: SplaySpec<T: 'a>,
649{
650    front: Root<S>,
651    back: Root<S>,
652    root: &'a mut Root<S>,
653}
654
655impl<'a, S> Debug for NodeRange<'a, S>
656where
657    S: SplaySpec<T: 'a + Debug>,
658{
659    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
660        f.debug_struct("NodeRange")
661            .field("front", &self.front)
662            .field("back", &self.back)
663            .field("root", &self.root)
664            .finish()
665    }
666}
667impl<'a, S> NodeRange<'a, S>
668where
669    S: SplaySpec<T: 'a>,
670{
671    pub fn new(root: &'a mut Root<S>) -> Self {
672        Self {
673            front: Default::default(),
674            back: Default::default(),
675            root,
676        }
677    }
678    pub fn three_way(
679        front: Option<NodeRef<marker::Owned, S>>,
680        root: &'a mut Root<S>,
681        back: Option<NodeRef<marker::Owned, S>>,
682    ) -> Self {
683        Self {
684            front: Root::new(front),
685            back: Root::new(back),
686            root,
687        }
688    }
689    pub fn next_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
690        let first = self.root.take_first()?;
691        let noderef = unsafe { NodeRef::new_unchecked(first.node) };
692        self.front.insert_last(first);
693        Some(noderef)
694    }
695    pub fn next_back_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
696        let last = self.root.take_last()?;
697        let noderef = unsafe { NodeRef::new_unchecked(last.node) };
698        self.back.insert_first(last);
699        Some(noderef)
700    }
701    pub fn root(&self) -> &Root<S> {
702        self.root
703    }
704    pub fn root_mut(&mut self) -> &mut Root<S> {
705        self.root
706    }
707    pub fn front(&self) -> &Root<S> {
708        &self.front
709    }
710    pub fn drop_rotate_left(mut self) {
711        self.root.append(&mut self.back);
712        self.root.append(&mut self.front);
713    }
714}
715impl<'a, S> Drop for NodeRange<'a, S>
716where
717    S: SplaySpec<T: 'a>,
718{
719    fn drop(&mut self) {
720        swap(self.root, &mut self.front);
721        self.root.append(&mut self.front);
722        self.root.append(&mut self.back);
723    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 461)
438    fn extend<I>(&mut self, iter: I)
439    where
440        I: IntoIterator<Item = T::Key>,
441    {
442        let nodes: Vec<_> = unsafe {
443            iter.into_iter()
444                .map(|key| {
445                    let agg = T::single_agg(&key);
446                    NodeRef::from_data(
447                        LazyAggElement {
448                            key,
449                            agg,
450                            lazy: T::act_unit(),
451                            size: 1,
452                            rev: false,
453                        },
454                        self.alloc.deref_mut(),
455                    )
456                })
457                .collect()
458        };
459        self.length += nodes.len();
460        let mut root = unsafe { Root::from_single_nodes(nodes) };
461        self.root.append(&mut root);
462    }
Source

pub fn range<Seeker>( &mut self, start: Bound<Seeker>, end: Bound<Seeker>, ) -> NodeRange<'_, S>
where Seeker: SplaySeeker<S = S>,

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 320)
306    fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
307    where
308        R: RangeBounds<usize>,
309    {
310        let start = match range.start_bound() {
311            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
312            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
313            Bound::Unbounded => Bound::Unbounded,
314        };
315        let end = match range.end_bound() {
316            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
317            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
318            Bound::Unbounded => Bound::Unbounded,
319        };
320        self.root.range(start, end)
321    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 266)
249    pub fn range<Q, R>(&mut self, range: R) -> Iter<'_, K, V>
250    where
251        K: Borrow<Q>,
252        Q: Ord + ?Sized,
253        R: RangeBounds<Q>,
254    {
255        let start = match range.start_bound() {
256            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
257            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
258            Bound::Unbounded => Bound::Unbounded,
259        };
260        let end = match range.end_bound() {
261            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
262            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
263            Bound::Unbounded => Bound::Unbounded,
264        };
265        Iter {
266            iter: self.root.range(start, end),
267        }
268    }
269    pub fn range_at<R>(&mut self, range: R) -> Iter<'_, K, V>
270    where
271        R: RangeBounds<usize>,
272    {
273        let start = match range.start_bound() {
274            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
275            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
276            Bound::Unbounded => Bound::Unbounded,
277        };
278        let end = match range.end_bound() {
279            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
280            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
281            Bound::Unbounded => Bound::Unbounded,
282        };
283        Iter {
284            iter: self.root.range(start, end),
285        }
286    }
Source§

impl<T> Root<LazyAggSplay<T>>
where T: LazyMapMonoid,

Source

fn size(&self) -> usize

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 403)
393    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394    where
395        R: RangeBounds<usize>,
396        F: FnMut(&T::Agg) -> bool,
397    {
398        let mut range = self.range(range);
399        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400        if !matches!(ord, Some(Ordering::Equal)) {
401            return None;
402        }
403        let front_size = range.front().size();
404        let left_size = range.root().left_size();
405        Some(front_size + left_size)
406    }
407    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408    where
409        R: RangeBounds<usize>,
410        F: FnMut(&T::Agg) -> bool,
411    {
412        let mut range = self.range(range);
413        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414        if !matches!(ord, Some(Ordering::Equal)) {
415            return None;
416        }
417        let front_size = range.front().size();
418        let left_size = range.root().left_size();
419        Some(front_size + left_size)
420    }
Source

fn left_size(&self) -> usize

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 404)
393    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394    where
395        R: RangeBounds<usize>,
396        F: FnMut(&T::Agg) -> bool,
397    {
398        let mut range = self.range(range);
399        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400        if !matches!(ord, Some(Ordering::Equal)) {
401            return None;
402        }
403        let front_size = range.front().size();
404        let left_size = range.root().left_size();
405        Some(front_size + left_size)
406    }
407    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408    where
409        R: RangeBounds<usize>,
410        F: FnMut(&T::Agg) -> bool,
411    {
412        let mut range = self.range(range);
413        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414        if !matches!(ord, Some(Ordering::Equal)) {
415            return None;
416        }
417        let front_size = range.front().size();
418        let left_size = range.root().left_size();
419        Some(front_size + left_size)
420    }

Trait Implementations§

Source§

impl<S> Debug for Root<S>
where S: SplaySpec<T: Debug>,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<S> Default for Root<S>
where S: SplaySpec,

Source§

fn default() -> Self

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

Auto Trait Implementations§

§

impl<S> Freeze for Root<S>

§

impl<S> RefUnwindSafe for Root<S>
where <S as SplaySpec>::T: RefUnwindSafe,

§

impl<S> !Send for Root<S>

§

impl<S> !Sync for Root<S>

§

impl<S> Unpin for Root<S>

§

impl<S> UnwindSafe for Root<S>
where <S as SplaySpec>::T: RefUnwindSafe,

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, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

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

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

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.