competitive::data_structure::splay_tree::node

Struct NodeRange

pub struct NodeRange<'a, S>where
    S: SplaySpec,
    S::T: 'a,
{ /* private fields */ }

Implementations§

Source §

impl<'a, S> NodeRange<'a, S>
where S: SplaySpec, S::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 593)

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 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 607)

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

Source

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

Source

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

Examples found in repository ?

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

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    }

Source

pub fn drop_rotate_left(self)

Examples found in repository ?

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

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    }