competitive::data_structure::splay_tree::node

Struct NodeRange

pub struct NodeRange<'a, S>where
    S: SplaySpec<T: 'a>,{
    front: Root<S>,
    back: Root<S>,
    root: &'a mut Root<S>,
}

Fields§

§front: Root<S>§back: Root<S>§root: &'a mut Root<S>

Implementations§

Source §

impl<'a, S> NodeRange<'a, S>
where S: SplaySpec<T: 'a>,

Source

pub fn new(root: &'a mut Root<S>) -> Self

Examples found in repository ?

crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 246)

244    pub fn iter(&mut self) -> Iter<'_, K, V> {
245        Iter {
246            iter: NodeRange::new(&mut self.root),
247        }
248    }

More examples

Hide additional examples

crates/competitive/src/data_structure/splay_tree/node.rs (line 584)

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 three_way( front: Option<NodeRef<Owned, S>>, root: &'a mut Root<S>, back: Option<NodeRef<Owned, S>>, ) -> Self

Examples found in repository ?

crates/competitive/src/data_structure/splay_tree/node.rs (line 598)

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 next_checked(&mut self) -> Option<NodeRef<DataMut<'a>, S>>

Examples found in repository ?

crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 300)

299    fn next(&mut self) -> Option<Self::Item> {
300        self.iter.next_checked().map(|node| node.data().0.clone())
301    }

Source

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

Examples found in repository ?

crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 325)

323    fn next_back(&mut self) -> Option<Self::Item> {
324        self.iter
325            .next_back_checked()
326            .map(|node| node.data().0.clone())
327    }

Source

pub fn root(&self) -> &Root<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    }

Source

pub fn root_mut(&mut self) -> &mut Root<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    }
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    }

Source

pub fn front(&self) -> &Root<S>

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

pub fn drop_rotate_left(self)

Examples found in repository ?

crates/competitive/src/data_structure/splay_tree/sequence.rs (line 424)

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    }