Struct Split 

pub struct Split<'a, Spec>
where
    Spec: BstSpec,
{
    left: Option<BstRoot<Spec>>,
    right: Option<BstRoot<Spec>>,
    root: &'a mut Option<BstRoot<Spec>>,
}

Fields

left: Option<BstRoot<Spec>>

right: Option<BstRoot<Spec>>

root: &'a mut Option<BstRoot<Spec>>

Implementations

impl<'a, Spec> Split<'a, Spec>

where Spec: BstSpec,

pub fn new<Seek>( node: &'a mut Option<BstRoot<Spec>>, seeker: Seek, equal_side: EqualSide, ) -> Self

where Seek: BstSeeker<Spec = Spec>,

Examples found in repository

crates/competitive/src/data_structure/binary_search_tree/split.rs (line 142)

    pub fn split_mid<Seek>(&mut self, seeker: Seek, equal_side: EqualSide) -> Split<'_, Spec>
    where
        Seek: BstSeeker<Spec = Spec>,
    {
        Split::new(&mut self.mid, seeker, equal_side)
    }

crates/competitive/src/data_structure/treap.rs (lines 417-421)

    pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>
    where
        M: MonoidAct<Key: Borrow<Q>>,
        Q: Ord + ?Sized,
    {
        let split = Split::new(
            &mut self.root,
            SeekByKey::<TreapSpec<M, L>, M::Key, Q>::new(key),
            EqualSide::Right,
        );
        let node = split.right()?.leftmost();
        matches!(node.into_data().key.key.borrow().cmp(key), Ordering::Equal)
            .then(|| self.node_id_manager.registered_node_id(node))
            .flatten()
    }

    pub fn find_by_acc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
    where
        F: FnMut(&L::Agg) -> bool,
    {
        let split = Split::new(
            &mut self.root,
            SeekByAccCond::<TreapSpec<M, L>, L, F>::new(f),
            EqualSide::Right,
        );
        let node = split.right()?.leftmost();
        self.node_id_manager.registered_node_id(node)
    }

    pub fn find_by_racc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
    where
        F: FnMut(&L::Agg) -> bool,
    {
        let split = Split::new(
            &mut self.root,
            SeekByRaccCond::<TreapSpec<M, L>, L, F>::new(f),
            EqualSide::Left,
        );
        let node = split.left()?.rightmost();
        self.node_id_manager.registered_node_id(node)
    }

crates/competitive/src/data_structure/implicit_treap.rs (line 414)

    pub fn insert(&mut self, index: usize, x: T::Key) {
        assert!(index <= self.length);
        let node = self.node(x);
        if index == 0 {
            self.root = ImplicitTreapSpec::<T>::merge(Some(node), self.root.take());
        } else if index == self.length {
            self.root = ImplicitTreapSpec::<T>::merge(self.root.take(), Some(node));
        } else {
            let mut node = Some(node);
            let mut split = Split::new(&mut self.root, SeekBySize::new(index), EqualSide::Right);
            split.manually_merge(|left, right| {
                ImplicitTreapSpec::<T>::merge(
                    ImplicitTreapSpec::<T>::merge(left, node.take()),
                    right,
                )
            });
        }
        self.length += 1;
    }

pub fn left(&self) -> Option<BstImmutRef<'_, Spec>>

Examples found in repository

crates/competitive/src/data_structure/treap.rs (line 450)

    pub fn find_by_racc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
    where
        F: FnMut(&L::Agg) -> bool,
    {
        let split = Split::new(
            &mut self.root,
            SeekByRaccCond::<TreapSpec<M, L>, L, F>::new(f),
            EqualSide::Left,
        );
        let node = split.left()?.rightmost();
        self.node_id_manager.registered_node_id(node)
    }

crates/competitive/src/data_structure/implicit_splay_tree.rs (line 371)

    pub fn partition_point_acc<F>(&mut self, left: usize, mut pred: F) -> usize
    where
        F: FnMut(&T::Agg) -> bool,
    {
        let mut split3 = Split3::seek_by_size(&mut self.root, left..);
        let front_size = split3
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default();
        let split = split3.split_mid(SeekByAccCond::new(|acc| !pred(acc)), EqualSide::Right);
        let index = split
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default();
        front_size + index
    }

    pub fn rpartition_point_acc<F>(&mut self, right: usize, mut pred: F) -> usize
    where
        F: FnMut(&T::Agg) -> bool,
    {
        let mut split3 = Split3::seek_by_size(&mut self.root, ..right);
        let split = split3.split_mid(SeekByRaccCond::new(|acc| !pred(acc)), EqualSide::Left);
        split
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default()
    }

crates/competitive/src/data_structure/implicit_treap.rs (line 475)

    pub fn partition_point_acc<F>(&mut self, left: usize, mut pred: F) -> usize
    where
        F: FnMut(&T::Agg) -> bool,
    {
        let mut split3 = Split3::seek_by_size(&mut self.root, left..);
        let front_size = split3
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default();
        let split = split3.split_mid(SeekByAccCond::new(|acc| !pred(acc)), EqualSide::Right);
        let index = split
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default();
        front_size + index
    }

    pub fn rpartition_point_acc<F>(&mut self, right: usize, mut pred: F) -> usize
    where
        F: FnMut(&T::Agg) -> bool,
    {
        let mut split3 = Split3::seek_by_size(&mut self.root, ..right);
        let split = split3.split_mid(SeekByRaccCond::new(|acc| !pred(acc)), EqualSide::Left);
        split
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default()
    }

pub fn right(&self) -> Option<BstImmutRef<'_, Spec>>

Examples found in repository

crates/competitive/src/data_structure/treap.rs (line 422)

    pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>
    where
        M: MonoidAct<Key: Borrow<Q>>,
        Q: Ord + ?Sized,
    {
        let split = Split::new(
            &mut self.root,
            SeekByKey::<TreapSpec<M, L>, M::Key, Q>::new(key),
            EqualSide::Right,
        );
        let node = split.right()?.leftmost();
        matches!(node.into_data().key.key.borrow().cmp(key), Ordering::Equal)
            .then(|| self.node_id_manager.registered_node_id(node))
            .flatten()
    }

    pub fn find_by_acc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
    where
        F: FnMut(&L::Agg) -> bool,
    {
        let split = Split::new(
            &mut self.root,
            SeekByAccCond::<TreapSpec<M, L>, L, F>::new(f),
            EqualSide::Right,
        );
        let node = split.right()?.leftmost();
        self.node_id_manager.registered_node_id(node)
    }

pub fn left_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>>

pub fn right_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>>

pub fn manually_merge<F>(&mut self, f: F)

where F: FnMut(Option<BstRoot<Spec>>, Option<BstRoot<Spec>>) -> Option<BstRoot<Spec>>,

Examples found in repository

crates/competitive/src/data_structure/implicit_treap.rs (lines 415-420)

    pub fn insert(&mut self, index: usize, x: T::Key) {
        assert!(index <= self.length);
        let node = self.node(x);
        if index == 0 {
            self.root = ImplicitTreapSpec::<T>::merge(Some(node), self.root.take());
        } else if index == self.length {
            self.root = ImplicitTreapSpec::<T>::merge(self.root.take(), Some(node));
        } else {
            let mut node = Some(node);
            let mut split = Split::new(&mut self.root, SeekBySize::new(index), EqualSide::Right);
            split.manually_merge(|left, right| {
                ImplicitTreapSpec::<T>::merge(
                    ImplicitTreapSpec::<T>::merge(left, node.take()),
                    right,
                )
            });
        }
        self.length += 1;
    }

Trait Implementations

impl<'a, Spec> Drop for Split<'a, Spec>

where Spec: BstSpec,

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.