Struct SeekBySize 

struct SeekBySize<T> {
    index: usize,
    _marker: PhantomData<fn() -> T>,
}

Fields

index: usize

_marker: PhantomData<fn() -> T>

Implementations

impl<T> SeekBySize<T>

fn new(index: usize) -> Self

Examples found in repository

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

    fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
    where
        R: RangeBounds<usize>,
    {
        let start = match range.start_bound() {
            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
            Bound::Unbounded => Bound::Unbounded,
        };
        let end = match range.end_bound() {
            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
            Bound::Unbounded => Bound::Unbounded,
        };
        self.root.range(start, end)
    }
    pub fn update<R>(&mut self, range: R, x: T::Act)
    where
        R: RangeBounds<usize>,
    {
        if let Some(root) = self.range(range).root_mut().root_data_mut() {
            LazyAggSplay::<T>::update_lazy(root, &x);
        }
    }
    pub fn fold<R>(&mut self, range: R) -> T::Agg
    where
        R: RangeBounds<usize>,
    {
        if let Some(root) = self.range(range).root().root() {
            root.data().agg.clone()
        } else {
            T::agg_unit()
        }
    }
    pub fn reverse<R>(&mut self, range: R)
    where
        R: RangeBounds<usize>,
    {
        if let Some(root) = self.range(range).root_mut().root_data_mut() {
            LazyAggSplay::<T>::reverse(root);
        }
    }
    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
        self.root.splay_by(SeekBySize::new(index))?;
        self.root.root().map(|root| &root.data().key)
    }
    pub fn modify<F>(&mut self, index: usize, f: F)
    where
        F: FnOnce(&T::Key) -> T::Key,
    {
        self.root.splay_by(SeekBySize::new(index)).unwrap();
        let data = self.root.root_data_mut().unwrap().data_mut();
        data.key = f(&data.key);
        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
    }
    pub fn insert(&mut self, index: usize, x: T::Key) {
        assert!(index <= self.length);
        self.root.splay_by(SeekBySize::new(index));
        let agg = T::single_agg(&x);
        unsafe {
            let node = NodeRef::from_data(
                LazyAggElement {
                    key: x,
                    agg,
                    lazy: T::act_unit(),
                    size: 1,
                    rev: false,
                },
                self.alloc.deref_mut(),
            );
            if index == self.length {
                self.root.insert_right(node);
            } else {
                self.root.insert_left(node);
            }
        }
        self.length += 1;
    }
    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
        if index >= self.length {
            return None;
        }
        self.root.splay_by(SeekBySize::new(index));
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
    }

Trait Implementations

impl<T> SplaySeeker for SeekBySize<T>

where T: LazyMapMonoid,

type S = LazyAggSplay<T>

fn splay_seek(&mut self, node: NodeRef<Immut<'_>, Self::S>) -> Ordering