competitive::data_structure::splay_tree::node

Struct Root

Source 
pub struct Root<S>
where
    S: SplaySpec,
{ /* private fields */ }

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

pub fn is_empty(&self) -> bool

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

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

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 340)
336    pub fn fold<R>(&mut self, range: R) -> T::Agg
337    where
338        R: RangeBounds<usize>,
339    {
340        if let Some(root) = self.range(range).root().root() {
341            root.data().agg.clone()
342        } else {
343            T::agg_unit()
344        }
345    }
346    pub fn reverse<R>(&mut self, range: R)
347    where
348        R: RangeBounds<usize>,
349    {
350        if let Some(root) = self.range(range).root_mut().root_data_mut() {
351            LazyAggSplay::<T>::reverse(root);
352        }
353    }
354    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
355        self.root.splay_by(SeekBySize::new(index))?;
356        self.root.root().map(|root| &root.data().key)
357    }
358    pub fn modify<F>(&mut self, index: usize, f: F)
359    where
360        F: FnOnce(&T::Key) -> T::Key,
361    {
362        self.root.splay_by(SeekBySize::new(index)).unwrap();
363        let data = self.root.root_data_mut().unwrap().data_mut();
364        data.key = f(&data.key);
365        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
366    }
367    pub fn insert(&mut self, index: usize, x: T::Key) {
368        assert!(index <= self.length);
369        self.root.splay_by(SeekBySize::new(index));
370        let agg = T::single_agg(&x);
371        unsafe {
372            let node = NodeRef::from_data(
373                LazyAggElement {
374                    key: x,
375                    agg,
376                    lazy: T::act_unit(),
377                    size: 1,
378                    rev: false,
379                },
380                self.alloc.deref_mut(),
381            );
382            if index == self.length {
383                self.root.insert_right(node);
384            } else {
385                self.root.insert_left(node);
386            }
387        }
388        self.length += 1;
389    }
390    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
391        if index >= self.length {
392            return None;
393        }
394        self.root.splay_by(SeekBySize::new(index));
395        self.length -= 1;
396        let node = self.root.take_root().unwrap().into_dying();
397        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
398    }
399    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
400    where
401        R: RangeBounds<usize>,
402        F: FnMut(&T::Agg) -> bool,
403    {
404        let mut range = self.range(range);
405        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
406        if !matches!(ord, Some(Ordering::Equal)) {
407            return None;
408        }
409        let front_size = range.front().size();
410        let left_size = range.root().left_size();
411        Some(front_size + left_size)
412    }
413    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
414    where
415        R: RangeBounds<usize>,
416        F: FnMut(&T::Agg) -> bool,
417    {
418        let mut range = self.range(range);
419        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
420        if !matches!(ord, Some(Ordering::Equal)) {
421            return None;
422        }
423        let front_size = range.front().size();
424        let left_size = range.root().left_size();
425        Some(front_size + left_size)
426    }
427    pub fn rotate_left(&mut self, mid: usize) {
428        assert!(mid <= self.length);
429        if mid != 0 || mid != self.length {
430            self.range(mid..).drop_rotate_left()
431        }
432    }
433    pub fn rotate_right(&mut self, k: usize) {
434        assert!(k <= self.length);
435        self.rotate_left(self.length - k);
436    }
437}
438
439impl<T, A> Extend<T::Key> for SplaySequence<T, A>
440where
441    T: MonoidAction,
442    A: Allocator<Node<LazyAggElement<T>>>,
443{
444    fn extend<I>(&mut self, iter: I)
445    where
446        I: IntoIterator<Item = T::Key>,
447    {
448        let nodes: Vec<_> = unsafe {
449            iter.into_iter()
450                .map(|key| {
451                    let agg = T::single_agg(&key);
452                    NodeRef::from_data(
453                        LazyAggElement {
454                            key,
455                            agg,
456                            lazy: T::act_unit(),
457                            size: 1,
458                            rev: false,
459                        },
460                        self.alloc.deref_mut(),
461                    )
462                })
463                .collect()
464        };
465        self.length += nodes.len();
466        let mut root = unsafe { Root::from_single_nodes(nodes) };
467        self.root.append(&mut root);
468    }
469}
470
471impl<T> Root<LazyAggSplay<T>>
472where
473    T: MonoidAction,
474{
475    fn size(&self) -> usize {
476        self.root().map(|root| root.data().size).unwrap_or_default()
477    }
478    fn left_size(&self) -> usize {
479        self.root()
480            .and_then(|root| root.left().map(|left| left.data().size))
481            .unwrap_or_default()
482    }
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 332)
328    pub fn update<R>(&mut self, range: R, x: T::Act)
329    where
330        R: RangeBounds<usize>,
331    {
332        if let Some(root) = self.range(range).root_mut().root_data_mut() {
333            LazyAggSplay::<T>::update_lazy(root, &x);
334        }
335    }
336    pub fn fold<R>(&mut self, range: R) -> T::Agg
337    where
338        R: RangeBounds<usize>,
339    {
340        if let Some(root) = self.range(range).root().root() {
341            root.data().agg.clone()
342        } else {
343            T::agg_unit()
344        }
345    }
346    pub fn reverse<R>(&mut self, range: R)
347    where
348        R: RangeBounds<usize>,
349    {
350        if let Some(root) = self.range(range).root_mut().root_data_mut() {
351            LazyAggSplay::<T>::reverse(root);
352        }
353    }
354    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
355        self.root.splay_by(SeekBySize::new(index))?;
356        self.root.root().map(|root| &root.data().key)
357    }
358    pub fn modify<F>(&mut self, index: usize, f: F)
359    where
360        F: FnOnce(&T::Key) -> T::Key,
361    {
362        self.root.splay_by(SeekBySize::new(index)).unwrap();
363        let data = self.root.root_data_mut().unwrap().data_mut();
364        data.key = f(&data.key);
365        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
366    }
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 355)
354    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
355        self.root.splay_by(SeekBySize::new(index))?;
356        self.root.root().map(|root| &root.data().key)
357    }
358    pub fn modify<F>(&mut self, index: usize, f: F)
359    where
360        F: FnOnce(&T::Key) -> T::Key,
361    {
362        self.root.splay_by(SeekBySize::new(index)).unwrap();
363        let data = self.root.root_data_mut().unwrap().data_mut();
364        data.key = f(&data.key);
365        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
366    }
367    pub fn insert(&mut self, index: usize, x: T::Key) {
368        assert!(index <= self.length);
369        self.root.splay_by(SeekBySize::new(index));
370        let agg = T::single_agg(&x);
371        unsafe {
372            let node = NodeRef::from_data(
373                LazyAggElement {
374                    key: x,
375                    agg,
376                    lazy: T::act_unit(),
377                    size: 1,
378                    rev: false,
379                },
380                self.alloc.deref_mut(),
381            );
382            if index == self.length {
383                self.root.insert_right(node);
384            } else {
385                self.root.insert_left(node);
386            }
387        }
388        self.length += 1;
389    }
390    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
391        if index >= self.length {
392            return None;
393        }
394        self.root.splay_by(SeekBySize::new(index));
395        self.length -= 1;
396        let node = self.root.take_root().unwrap().into_dying();
397        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
398    }
399    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
400    where
401        R: RangeBounds<usize>,
402        F: FnMut(&T::Agg) -> bool,
403    {
404        let mut range = self.range(range);
405        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
406        if !matches!(ord, Some(Ordering::Equal)) {
407            return None;
408        }
409        let front_size = range.front().size();
410        let left_size = range.root().left_size();
411        Some(front_size + left_size)
412    }
413    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
414    where
415        R: RangeBounds<usize>,
416        F: FnMut(&T::Agg) -> bool,
417    {
418        let mut range = self.range(range);
419        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
420        if !matches!(ord, Some(Ordering::Equal)) {
421            return None;
422        }
423        let front_size = range.front().size();
424        let left_size = range.root().left_size();
425        Some(front_size + left_size)
426    }
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 596)
588    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
589    where
590        Seeker: SplaySeeker<S = S>,
591    {
592        if self.is_empty() {
593            return NodeRange::new(self);
594        }
595        let right = match end {
596            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
597                Ordering::Greater | Ordering::Equal => self.split_right(),
598                Ordering::Less => self.split_right_eq(),
599            },
600            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
601                Ordering::Greater => self.split_right(),
602                Ordering::Less | Ordering::Equal => self.split_right_eq(),
603            },
604            Bound::Unbounded => None,
605        };
606        if self.is_empty() {
607            return NodeRange::three_way(None, self, right);
608        }
609        let left = match start {
610            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
611                Ordering::Less | Ordering::Equal => self.split_left(),
612                Ordering::Greater => self.split_left_eq(),
613            },
614            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
615                Ordering::Less => self.split_left(),
616                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
617            },
618            Bound::Unbounded => None,
619        };
620        NodeRange::three_way(left, self, right)
621    }
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 385)
367    pub fn insert(&mut self, index: usize, x: T::Key) {
368        assert!(index <= self.length);
369        self.root.splay_by(SeekBySize::new(index));
370        let agg = T::single_agg(&x);
371        unsafe {
372            let node = NodeRef::from_data(
373                LazyAggElement {
374                    key: x,
375                    agg,
376                    lazy: T::act_unit(),
377                    size: 1,
378                    rev: false,
379                },
380                self.alloc.deref_mut(),
381            );
382            if index == self.length {
383                self.root.insert_right(node);
384            } else {
385                self.root.insert_left(node);
386            }
387        }
388        self.length += 1;
389    }
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 383)
367    pub fn insert(&mut self, index: usize, x: T::Key) {
368        assert!(index <= self.length);
369        self.root.splay_by(SeekBySize::new(index));
370        let agg = T::single_agg(&x);
371        unsafe {
372            let node = NodeRef::from_data(
373                LazyAggElement {
374                    key: x,
375                    agg,
376                    lazy: T::act_unit(),
377                    size: 1,
378                    rev: false,
379                },
380                self.alloc.deref_mut(),
381            );
382            if index == self.length {
383                self.root.insert_right(node);
384            } else {
385                self.root.insert_left(node);
386            }
387        }
388        self.length += 1;
389    }
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 712)
709    pub fn next_back_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
710        let last = self.root.take_last()?;
711        let noderef = unsafe { NodeRef::new_unchecked(last.node) };
712        self.back.insert_first(last);
713        Some(noderef)
714    }
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 706)
703    pub fn next_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
704        let first = self.root.take_first()?;
705        let noderef = unsafe { NodeRef::new_unchecked(first.node) };
706        self.front.insert_last(first);
707        Some(noderef)
708    }
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 396)
390    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
391        if index >= self.length {
392            return None;
393        }
394        self.root.splay_by(SeekBySize::new(index));
395        self.length -= 1;
396        let node = self.root.take_root().unwrap().into_dying();
397        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
398    }
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 264)
262    fn drop(&mut self) {
263        unsafe {
264            while let Some(node) = self.root.take_first() {
265                self.alloc.deallocate(node.into_dying().into_inner());
266            }
267            ManuallyDrop::drop(&mut self.alloc);
268        }
269    }
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 704)
703    pub fn next_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
704        let first = self.root.take_first()?;
705        let noderef = unsafe { NodeRef::new_unchecked(first.node) };
706        self.front.insert_last(first);
707        Some(noderef)
708    }
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 710)
709    pub fn next_back_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
710        let last = self.root.take_last()?;
711        let noderef = unsafe { NodeRef::new_unchecked(last.node) };
712        self.back.insert_first(last);
713        Some(noderef)
714    }
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 578)
577    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
578        let left = self.split_left();
579        replace(&mut self.root, left)
580    }
581    pub fn append(&mut self, other: &mut Self) {
582        self.root = match (self.root.take(), other.root.take()) {
583            (Some(node), None) | (None, Some(node)) => Some(node),
584            (Some(left), Some(right)) => Some(left.merge(right)),
585            (None, None) => None,
586        }
587    }
588    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
589    where
590        Seeker: SplaySeeker<S = S>,
591    {
592        if self.is_empty() {
593            return NodeRange::new(self);
594        }
595        let right = match end {
596            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
597                Ordering::Greater | Ordering::Equal => self.split_right(),
598                Ordering::Less => self.split_right_eq(),
599            },
600            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
601                Ordering::Greater => self.split_right(),
602                Ordering::Less | Ordering::Equal => self.split_right_eq(),
603            },
604            Bound::Unbounded => None,
605        };
606        if self.is_empty() {
607            return NodeRange::three_way(None, self, right);
608        }
609        let left = match start {
610            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
611                Ordering::Less | Ordering::Equal => self.split_left(),
612                Ordering::Greater => self.split_left_eq(),
613            },
614            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
615                Ordering::Less => self.split_left(),
616                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
617            },
618            Bound::Unbounded => None,
619        };
620        NodeRange::three_way(left, self, right)
621    }
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 574)
573    pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
574        let right = self.split_right();
575        replace(&mut self.root, right)
576    }
577    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
578        let left = self.split_left();
579        replace(&mut self.root, left)
580    }
581    pub fn append(&mut self, other: &mut Self) {
582        self.root = match (self.root.take(), other.root.take()) {
583            (Some(node), None) | (None, Some(node)) => Some(node),
584            (Some(left), Some(right)) => Some(left.merge(right)),
585            (None, None) => None,
586        }
587    }
588    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
589    where
590        Seeker: SplaySeeker<S = S>,
591    {
592        if self.is_empty() {
593            return NodeRange::new(self);
594        }
595        let right = match end {
596            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
597                Ordering::Greater | Ordering::Equal => self.split_right(),
598                Ordering::Less => self.split_right_eq(),
599            },
600            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
601                Ordering::Greater => self.split_right(),
602                Ordering::Less | Ordering::Equal => self.split_right_eq(),
603            },
604            Bound::Unbounded => None,
605        };
606        if self.is_empty() {
607            return NodeRange::three_way(None, self, right);
608        }
609        let left = match start {
610            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
611                Ordering::Less | Ordering::Equal => self.split_left(),
612                Ordering::Greater => self.split_left_eq(),
613            },
614            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
615                Ordering::Less => self.split_left(),
616                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
617            },
618            Bound::Unbounded => None,
619        };
620        NodeRange::three_way(left, self, right)
621    }
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 612)
588    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
589    where
590        Seeker: SplaySeeker<S = S>,
591    {
592        if self.is_empty() {
593            return NodeRange::new(self);
594        }
595        let right = match end {
596            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
597                Ordering::Greater | Ordering::Equal => self.split_right(),
598                Ordering::Less => self.split_right_eq(),
599            },
600            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
601                Ordering::Greater => self.split_right(),
602                Ordering::Less | Ordering::Equal => self.split_right_eq(),
603            },
604            Bound::Unbounded => None,
605        };
606        if self.is_empty() {
607            return NodeRange::three_way(None, self, right);
608        }
609        let left = match start {
610            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
611                Ordering::Less | Ordering::Equal => self.split_left(),
612                Ordering::Greater => self.split_left_eq(),
613            },
614            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
615                Ordering::Less => self.split_left(),
616                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
617            },
618            Bound::Unbounded => None,
619        };
620        NodeRange::three_way(left, self, right)
621    }
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 598)
588    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
589    where
590        Seeker: SplaySeeker<S = S>,
591    {
592        if self.is_empty() {
593            return NodeRange::new(self);
594        }
595        let right = match end {
596            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
597                Ordering::Greater | Ordering::Equal => self.split_right(),
598                Ordering::Less => self.split_right_eq(),
599            },
600            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
601                Ordering::Greater => self.split_right(),
602                Ordering::Less | Ordering::Equal => self.split_right_eq(),
603            },
604            Bound::Unbounded => None,
605        };
606        if self.is_empty() {
607            return NodeRange::three_way(None, self, right);
608        }
609        let left = match start {
610            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
611                Ordering::Less | Ordering::Equal => self.split_left(),
612                Ordering::Greater => self.split_left_eq(),
613            },
614            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
615                Ordering::Less => self.split_left(),
616                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
617            },
618            Bound::Unbounded => None,
619        };
620        NodeRange::three_way(left, self, right)
621    }
Source

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

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

Trait Implementations§

Source§

impl<S> Debug for Root<S>
where S: SplaySpec, S::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.