Struct NodeRef

pub struct NodeRef<B, S>
where
    S: SplaySpec,
{ /* private fields */ }

Implementations

impl<S> NodeRef<Owned, S>

where S: SplaySpec,

pub fn new(node: NonNull<Node<S::T>>) -> Self

Examples found in repository

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

    pub unsafe fn from_data<A>(data: S::T, allocator: &mut A) -> Self
    where
        A: Allocator<Node<S::T>>,
    {
        Self::new(allocator.allocate(Node::new(data)))
    }
    pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, S> {
        unsafe { NodeRef::new_unchecked(self.node) }
    }
    pub fn borrow_datamut(&mut self) -> NodeRef<marker::DataMut<'_>, S> {
        unsafe { NodeRef::new_unchecked(self.node) }
    }
    pub fn into_dying(self) -> NodeRef<marker::Dying, S> {
        unsafe { NodeRef::new_unchecked(self.node) }
    }
}

impl<'a, S> NodeRef<marker::Immut<'a>, S>
where
    S: SplaySpec,
    S::T: 'a,
{
    pub fn data(&self) -> &'a S::T {
        unsafe { &(*self.as_ptr()).data }
    }
    pub fn left(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .left
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn right(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .right
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn traverse<F>(self, f: &mut F)
    where
        S::T: 'a,
        F: FnMut(Self),
    {
        if let Some(left) = self.clone().left() {
            left.traverse(f);
        }
        f(self);
        if let Some(right) = self.clone().right() {
            right.traverse(f);
        }
    }
}

impl<'a, S> NodeRef<marker::DataMut<'a>, S>
where
    S: SplaySpec,
    S::T: 'a,
{
    pub fn data(&self) -> &'a S::T {
        unsafe { &(*self.as_ptr()).data }
    }
    pub fn data_mut(&self) -> &'a mut S::T {
        unsafe { &mut (*self.as_ptr()).data }
    }
    pub fn left(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .left
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn right(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .right
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn reverse(&self) {
        unsafe {
            let node = &mut (*self.as_ptr());
            swap(&mut node.left, &mut node.right);
        }
    }
}

impl<'a, S> NodeRef<marker::Mut<'a>, S>
where
    S: SplaySpec,
    S::T: 'a,
{
    pub fn data(self) -> &'a S::T {
        unsafe { &(*self.as_ptr()).data }
    }
    pub fn data_mut(self) -> &'a mut S::T {
        unsafe { &mut (*self.as_ptr()).data }
    }
    pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
    }
    pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
    }
    pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
        unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
    }
    pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
        unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
    }
}

impl<S> NodeRef<marker::Dying, S>
where
    S: SplaySpec,
{
    pub unsafe fn into_inner(self) -> NonNull<Node<S::T>> {
        let node = self.node;
        unsafe {
            debug_assert!((*node.as_ptr()).left.is_none());
            debug_assert!((*node.as_ptr()).right.is_none());
        }
        node
    }
    pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
    where
        A: Allocator<Node<S::T>>,
    {
        let Node { data, left, right } = allocator.deallocate(self.node);
        debug_assert!(left.is_none());
        debug_assert!(right.is_none());
        data
    }
}

impl<S> NodeRef<marker::Owned, S>
where
    S: SplaySpec,
{
    /// `cmp(key)`: [`Ordering`] between splaying and `key`
    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }

pub unsafe fn from_data<A>(data: S::T, allocator: &mut A) -> Self

where A: Allocator<Node<S::T>>,

Examples found in repository

crates/competitive/src/data_structure/splay_tree/sequence.rs (lines 372-381)

    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) }
    }
    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: FnMut(&T::Agg) -> bool,
    {
        let mut range = self.range(range);
        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
        if !matches!(ord, Some(Ordering::Equal)) {
            return None;
        }
        let front_size = range.front().size();
        let left_size = range.root().left_size();
        Some(front_size + left_size)
    }
    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: FnMut(&T::Agg) -> bool,
    {
        let mut range = self.range(range);
        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
        if !matches!(ord, Some(Ordering::Equal)) {
            return None;
        }
        let front_size = range.front().size();
        let left_size = range.root().left_size();
        Some(front_size + left_size)
    }
    pub fn rotate_left(&mut self, mid: usize) {
        assert!(mid <= self.length);
        if mid != 0 || mid != self.length {
            self.range(mid..).drop_rotate_left()
        }
    }
    pub fn rotate_right(&mut self, k: usize) {
        assert!(k <= self.length);
        self.rotate_left(self.length - k);
    }
}

impl<T, A> Extend<T::Key> for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let nodes: Vec<_> = unsafe {
            iter.into_iter()
                .map(|key| {
                    let agg = T::single_agg(&key);
                    NodeRef::from_data(
                        LazyAggElement {
                            key,
                            agg,
                            lazy: T::act_unit(),
                            size: 1,
                            rev: false,
                        },
                        self.alloc.deref_mut(),
                    )
                })
                .collect()
        };
        self.length += nodes.len();
        let mut root = unsafe { Root::from_single_nodes(nodes) };
        self.root.append(&mut root);
    }

crates/competitive/src/data_structure/splay_tree/sized_map.rs (lines 203-206)

    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ord = self.splay_by_key(&key);
        self.length += (ord != Some(Ordering::Equal)) as usize;
        match ord {
            Some(Ordering::Equal) => {
                return Some(replace(
                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
                    value,
                ));
            }
            Some(Ordering::Less) => unsafe {
                self.root.insert_left(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
            _ => unsafe {
                self.root.insert_right(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
        }
        None
    }

pub fn borrow_mut(&mut self) -> NodeRef<Mut<'_>, S>

Examples found in repository

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

    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
        Some(self.root.as_ref()?.reborrow())
    }
    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
        Some(self.root.as_mut()?.borrow_datamut())
    }
    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: SplaySeeker<S = S>,
    {
        let (ord, root) = self.root.take()?.splay_by(seeker);
        self.root = Some(root);
        Some(ord)
    }
    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?;
        let right = root.borrow_mut().take_right();
        self.root = root.borrow_mut().take_left();
        self.append(&mut Self::new(right));
        Some(root)
    }
    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
        let right = root.borrow_mut().take_right();
        self.root = right;
        Some(root)
    }
    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
        let left = root.borrow_mut().take_left();
        self.root = left;
        Some(root)
    }
    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let left = root.borrow_mut().take_left();
        S::bottom_up(root.borrow_datamut());
        left
    }
    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let right = root.borrow_mut().take_right();
        S::bottom_up(root.borrow_datamut());
        right
    }

pub fn borrow_datamut(&mut self) -> NodeRef<DataMut<'_>, S>

Examples found in repository

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

    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
        Some(self.root.as_ref()?.reborrow())
    }
    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
        Some(self.root.as_mut()?.borrow_datamut())
    }
    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: SplaySeeker<S = S>,
    {
        let (ord, root) = self.root.take()?.splay_by(seeker);
        self.root = Some(root);
        Some(ord)
    }
    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?;
        let right = root.borrow_mut().take_right();
        self.root = root.borrow_mut().take_left();
        self.append(&mut Self::new(right));
        Some(root)
    }
    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
        let right = root.borrow_mut().take_right();
        self.root = right;
        Some(root)
    }
    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
        let left = root.borrow_mut().take_left();
        self.root = left;
        Some(root)
    }
    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let left = root.borrow_mut().take_left();
        S::bottom_up(root.borrow_datamut());
        left
    }
    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let right = root.borrow_mut().take_right();
        S::bottom_up(root.borrow_datamut());
        right
    }

pub fn into_dying(self) -> NodeRef<Dying, S>

Examples found in repository

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

    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<T, A> Default for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<T> SplaySequence<T>
where
    T: MonoidAction,
{
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
    pub fn len(&self) -> usize {
        self.length
    }
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }
}
impl<T, A> SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    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) }
    }

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

    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<K, V, A> Default for SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<K, V> SplayMap<K, V> {
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
}
impl<K, V, A> SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.get_key_value(key).map(|(_, v)| v)
    }
    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.root.splay_by(SeekByKey::new(key))
    }
    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
        self.root.splay_by(SeekBySize::new(index))
    }
    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ord = self.splay_by_key(&key);
        self.length += (ord != Some(Ordering::Equal)) as usize;
        match ord {
            Some(Ordering::Equal) => {
                return Some(replace(
                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
                    value,
                ));
            }
            Some(Ordering::Less) => unsafe {
                self.root.insert_left(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
            _ => unsafe {
                self.root.insert_right(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
        }
        None
    }
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
    }
    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
    }

impl<'a, S> NodeRef<Immut<'a>, S>

where S: SplaySpec, S::T: 'a,

pub fn data(&self) -> &'a S::T

Examples found in repository

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

    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        self.key.cmp((node.data().0).0.borrow())
    }
}

struct SeekBySize<K, V> {
    index: usize,
    _marker: PhantomData<fn() -> (K, V)>,
}
impl<K, V> SeekBySize<K, V> {
    fn new(index: usize) -> Self {
        Self {
            index,
            _marker: PhantomData,
        }
    }
}
impl<K, V> SplaySeeker for SeekBySize<K, V> {
    type S = SizedSplay<(K, V)>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        let lsize = node.left().map(|l| l.data().1).unwrap_or_default();
        let ord = self.index.cmp(&lsize);
        if matches!(ord, Ordering::Greater) {
            self.index -= lsize + 1;
        }
        ord
    }
}

pub struct SplayMap<K, V, A = MemoryPool<Node<((K, V), usize)>>>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    root: Root<SizedSplay<(K, V)>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

impl<K, V, A> Debug for SplayMap<K, V, A>
where
    K: Debug,
    V: Debug,
    A: Allocator<Node<((K, V), usize)>>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SplayMap")
            .field("root", &self.root)
            .field("length", &self.length)
            .finish()
    }
}

impl<K, V, A> Drop for SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<K, V, A> Default for SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<K, V> SplayMap<K, V> {
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
}
impl<K, V, A> SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.get_key_value(key).map(|(_, v)| v)
    }
    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.root.splay_by(SeekByKey::new(key))
    }
    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
        self.root.splay_by(SeekBySize::new(index))
    }
    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }

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

    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
        let ord = self.index.cmp(&lsize);
        if matches!(ord, Ordering::Greater) {
            self.index -= lsize + 1;
        }
        ord
    }
}

struct SeekByAccCond<F, T>
where
    T: MonoidAction,
{
    acc: T::Agg,
    f: F,
    _marker: PhantomData<fn() -> T>,
}
impl<F, T> SeekByAccCond<F, T>
where
    T: MonoidAction,
{
    fn new(f: F) -> Self {
        Self {
            acc: T::agg_unit(),
            f,
            _marker: PhantomData,
        }
    }
}
impl<F, T> SplaySeeker for SeekByAccCond<F, T>
where
    F: FnMut(&T::Agg) -> bool,
    T: MonoidAction,
{
    type S = LazyAggSplay<T>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        if let Some(lagg) = node.left().map(|l| &l.data().agg) {
            let nacc = T::agg_operate(&self.acc, lagg);
            if (self.f)(&nacc) {
                return Ordering::Less;
            }
            self.acc = nacc;
        };
        self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
        if (self.f)(&self.acc) {
            Ordering::Equal
        } else {
            Ordering::Greater
        }
    }
}

struct SeekByRaccCond<F, T>
where
    T: MonoidAction,
{
    acc: T::Agg,
    f: F,
    _marker: PhantomData<fn() -> T>,
}
impl<F, T> SeekByRaccCond<F, T>
where
    T: MonoidAction,
{
    fn new(f: F) -> Self {
        Self {
            acc: T::agg_unit(),
            f,
            _marker: PhantomData,
        }
    }
}
impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
where
    F: FnMut(&T::Agg) -> bool,
    T: MonoidAction,
{
    type S = LazyAggSplay<T>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        if let Some(lagg) = node.right().map(|r| &r.data().agg) {
            let nacc = T::agg_operate(lagg, &self.acc);
            if (self.f)(&nacc) {
                return Ordering::Greater;
            }
            self.acc = nacc;
        };
        self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
        if (self.f)(&self.acc) {
            Ordering::Equal
        } else {
            Ordering::Less
        }
    }
}

pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    root: Root<LazyAggSplay<T>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

impl<T, A> Debug for SplaySequence<T, A>
where
    T: MonoidAction,
    T::Key: Debug,
    T::Agg: Debug,
    T::Act: Debug,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SplayMap")
            .field("root", &self.root)
            .field("length", &self.length)
            .finish()
    }
}

impl<T, A> Drop for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<T, A> Default for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<T> SplaySequence<T>
where
    T: MonoidAction,
{
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
    pub fn len(&self) -> usize {
        self.length
    }
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }
}
impl<T, A> SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    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) }
    }
    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: FnMut(&T::Agg) -> bool,
    {
        let mut range = self.range(range);
        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
        if !matches!(ord, Some(Ordering::Equal)) {
            return None;
        }
        let front_size = range.front().size();
        let left_size = range.root().left_size();
        Some(front_size + left_size)
    }
    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: FnMut(&T::Agg) -> bool,
    {
        let mut range = self.range(range);
        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
        if !matches!(ord, Some(Ordering::Equal)) {
            return None;
        }
        let front_size = range.front().size();
        let left_size = range.root().left_size();
        Some(front_size + left_size)
    }
    pub fn rotate_left(&mut self, mid: usize) {
        assert!(mid <= self.length);
        if mid != 0 || mid != self.length {
            self.range(mid..).drop_rotate_left()
        }
    }
    pub fn rotate_right(&mut self, k: usize) {
        assert!(k <= self.length);
        self.rotate_left(self.length - k);
    }
}

impl<T, A> Extend<T::Key> for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let nodes: Vec<_> = unsafe {
            iter.into_iter()
                .map(|key| {
                    let agg = T::single_agg(&key);
                    NodeRef::from_data(
                        LazyAggElement {
                            key,
                            agg,
                            lazy: T::act_unit(),
                            size: 1,
                            rev: false,
                        },
                        self.alloc.deref_mut(),
                    )
                })
                .collect()
        };
        self.length += nodes.len();
        let mut root = unsafe { Root::from_single_nodes(nodes) };
        self.root.append(&mut root);
    }
}

impl<T> Root<LazyAggSplay<T>>
where
    T: MonoidAction,
{
    fn size(&self) -> usize {
        self.root().map(|root| root.data().size).unwrap_or_default()
    }
    fn left_size(&self) -> usize {
        self.root()
            .and_then(|root| root.left().map(|left| left.data().size))
            .unwrap_or_default()
    }

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

        fn fmt_recurse<'a, S>(
            node: NodeRef<marker::Immut<'a>, S>,
            f: &mut fmt::Formatter<'_>,
        ) -> fmt::Result
        where
            S: SplaySpec,
            S::T: 'a + Debug,
        {
            write!(f, "[")?;
            if let Some(left) = node.left() {
                fmt_recurse(left, f)?;
            }
            node.data().fmt(f)?;
            if let Some(right) = node.right() {
                fmt_recurse(right, f)?;
            }
            write!(f, "]")?;
            Ok(())
        }

pub fn left(&self) -> Option<Self>

Examples found in repository

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

    pub fn traverse<F>(self, f: &mut F)
    where
        S::T: 'a,
        F: FnMut(Self),
    {
        if let Some(left) = self.clone().left() {
            left.traverse(f);
        }
        f(self);
        if let Some(right) = self.clone().right() {
            right.traverse(f);
        }
    }
}

impl<'a, S> NodeRef<marker::DataMut<'a>, S>
where
    S: SplaySpec,
    S::T: 'a,
{
    pub fn data(&self) -> &'a S::T {
        unsafe { &(*self.as_ptr()).data }
    }
    pub fn data_mut(&self) -> &'a mut S::T {
        unsafe { &mut (*self.as_ptr()).data }
    }
    pub fn left(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .left
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn right(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .right
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn reverse(&self) {
        unsafe {
            let node = &mut (*self.as_ptr());
            swap(&mut node.left, &mut node.right);
        }
    }
}

impl<'a, S> NodeRef<marker::Mut<'a>, S>
where
    S: SplaySpec,
    S::T: 'a,
{
    pub fn data(self) -> &'a S::T {
        unsafe { &(*self.as_ptr()).data }
    }
    pub fn data_mut(self) -> &'a mut S::T {
        unsafe { &mut (*self.as_ptr()).data }
    }
    pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
    }
    pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
    }
    pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
        unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
    }
    pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
        unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
    }
}

impl<S> NodeRef<marker::Dying, S>
where
    S: SplaySpec,
{
    pub unsafe fn into_inner(self) -> NonNull<Node<S::T>> {
        let node = self.node;
        unsafe {
            debug_assert!((*node.as_ptr()).left.is_none());
            debug_assert!((*node.as_ptr()).right.is_none());
        }
        node
    }
    pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
    where
        A: Allocator<Node<S::T>>,
    {
        let Node { data, left, right } = allocator.deallocate(self.node);
        debug_assert!(left.is_none());
        debug_assert!(right.is_none());
        data
    }
}

impl<S> NodeRef<marker::Owned, S>
where
    S: SplaySpec,
{
    /// `cmp(key)`: [`Ordering`] between splaying and `key`
    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
        Some(self.root.as_ref()?.reborrow())
    }
    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
        Some(self.root.as_mut()?.borrow_datamut())
    }
    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: SplaySeeker<S = S>,
    {
        let (ord, root) = self.root.take()?.splay_by(seeker);
        self.root = Some(root);
        Some(ord)
    }
    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?;
        let right = root.borrow_mut().take_right();
        self.root = root.borrow_mut().take_left();
        self.append(&mut Self::new(right));
        Some(root)
    }
    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
        let right = root.borrow_mut().take_right();
        self.root = right;
        Some(root)
    }
    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
        let left = root.borrow_mut().take_left();
        self.root = left;
        Some(root)
    }
    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let left = root.borrow_mut().take_left();
        S::bottom_up(root.borrow_datamut());
        left
    }
    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let right = root.borrow_mut().take_right();
        S::bottom_up(root.borrow_datamut());
        right
    }
    pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let right = self.split_right();
        replace(&mut self.root, right)
    }
    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let left = self.split_left();
        replace(&mut self.root, left)
    }
    pub fn append(&mut self, other: &mut Self) {
        self.root = match (self.root.take(), other.root.take()) {
            (Some(node), None) | (None, Some(node)) => Some(node),
            (Some(left), Some(right)) => Some(left.merge(right)),
            (None, None) => None,
        }
    }
    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
    where
        Seeker: SplaySeeker<S = S>,
    {
        if self.is_empty() {
            return NodeRange::new(self);
        }
        let right = match end {
            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Greater | Ordering::Equal => self.split_right(),
                Ordering::Less => self.split_right_eq(),
            },
            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Greater => self.split_right(),
                Ordering::Less | Ordering::Equal => self.split_right_eq(),
            },
            Bound::Unbounded => None,
        };
        if self.is_empty() {
            return NodeRange::three_way(None, self, right);
        }
        let left = match start {
            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Less | Ordering::Equal => self.split_left(),
                Ordering::Greater => self.split_left_eq(),
            },
            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Less => self.split_left(),
                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
            },
            Bound::Unbounded => None,
        };
        NodeRange::three_way(left, self, right)
    }
}

impl<S> Debug for Root<S>
where
    S: SplaySpec,
    S::T: Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fn fmt_recurse<'a, S>(
            node: NodeRef<marker::Immut<'a>, S>,
            f: &mut fmt::Formatter<'_>,
        ) -> fmt::Result
        where
            S: SplaySpec,
            S::T: 'a + Debug,
        {
            write!(f, "[")?;
            if let Some(left) = node.left() {
                fmt_recurse(left, f)?;
            }
            node.data().fmt(f)?;
            if let Some(right) = node.right() {
                fmt_recurse(right, f)?;
            }
            write!(f, "]")?;
            Ok(())
        }

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

    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        let lsize = node.left().map(|l| l.data().1).unwrap_or_default();
        let ord = self.index.cmp(&lsize);
        if matches!(ord, Ordering::Greater) {
            self.index -= lsize + 1;
        }
        ord
    }

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

    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
        let ord = self.index.cmp(&lsize);
        if matches!(ord, Ordering::Greater) {
            self.index -= lsize + 1;
        }
        ord
    }
}

struct SeekByAccCond<F, T>
where
    T: MonoidAction,
{
    acc: T::Agg,
    f: F,
    _marker: PhantomData<fn() -> T>,
}
impl<F, T> SeekByAccCond<F, T>
where
    T: MonoidAction,
{
    fn new(f: F) -> Self {
        Self {
            acc: T::agg_unit(),
            f,
            _marker: PhantomData,
        }
    }
}
impl<F, T> SplaySeeker for SeekByAccCond<F, T>
where
    F: FnMut(&T::Agg) -> bool,
    T: MonoidAction,
{
    type S = LazyAggSplay<T>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        if let Some(lagg) = node.left().map(|l| &l.data().agg) {
            let nacc = T::agg_operate(&self.acc, lagg);
            if (self.f)(&nacc) {
                return Ordering::Less;
            }
            self.acc = nacc;
        };
        self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
        if (self.f)(&self.acc) {
            Ordering::Equal
        } else {
            Ordering::Greater
        }
    }
}

struct SeekByRaccCond<F, T>
where
    T: MonoidAction,
{
    acc: T::Agg,
    f: F,
    _marker: PhantomData<fn() -> T>,
}
impl<F, T> SeekByRaccCond<F, T>
where
    T: MonoidAction,
{
    fn new(f: F) -> Self {
        Self {
            acc: T::agg_unit(),
            f,
            _marker: PhantomData,
        }
    }
}
impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
where
    F: FnMut(&T::Agg) -> bool,
    T: MonoidAction,
{
    type S = LazyAggSplay<T>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        if let Some(lagg) = node.right().map(|r| &r.data().agg) {
            let nacc = T::agg_operate(lagg, &self.acc);
            if (self.f)(&nacc) {
                return Ordering::Greater;
            }
            self.acc = nacc;
        };
        self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
        if (self.f)(&self.acc) {
            Ordering::Equal
        } else {
            Ordering::Less
        }
    }
}

pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    root: Root<LazyAggSplay<T>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

impl<T, A> Debug for SplaySequence<T, A>
where
    T: MonoidAction,
    T::Key: Debug,
    T::Agg: Debug,
    T::Act: Debug,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SplayMap")
            .field("root", &self.root)
            .field("length", &self.length)
            .finish()
    }
}

impl<T, A> Drop for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<T, A> Default for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<T> SplaySequence<T>
where
    T: MonoidAction,
{
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
    pub fn len(&self) -> usize {
        self.length
    }
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }
}
impl<T, A> SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    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) }
    }
    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: FnMut(&T::Agg) -> bool,
    {
        let mut range = self.range(range);
        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
        if !matches!(ord, Some(Ordering::Equal)) {
            return None;
        }
        let front_size = range.front().size();
        let left_size = range.root().left_size();
        Some(front_size + left_size)
    }
    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: FnMut(&T::Agg) -> bool,
    {
        let mut range = self.range(range);
        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
        if !matches!(ord, Some(Ordering::Equal)) {
            return None;
        }
        let front_size = range.front().size();
        let left_size = range.root().left_size();
        Some(front_size + left_size)
    }
    pub fn rotate_left(&mut self, mid: usize) {
        assert!(mid <= self.length);
        if mid != 0 || mid != self.length {
            self.range(mid..).drop_rotate_left()
        }
    }
    pub fn rotate_right(&mut self, k: usize) {
        assert!(k <= self.length);
        self.rotate_left(self.length - k);
    }
}

impl<T, A> Extend<T::Key> for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let nodes: Vec<_> = unsafe {
            iter.into_iter()
                .map(|key| {
                    let agg = T::single_agg(&key);
                    NodeRef::from_data(
                        LazyAggElement {
                            key,
                            agg,
                            lazy: T::act_unit(),
                            size: 1,
                            rev: false,
                        },
                        self.alloc.deref_mut(),
                    )
                })
                .collect()
        };
        self.length += nodes.len();
        let mut root = unsafe { Root::from_single_nodes(nodes) };
        self.root.append(&mut root);
    }
}

impl<T> Root<LazyAggSplay<T>>
where
    T: MonoidAction,
{
    fn size(&self) -> usize {
        self.root().map(|root| root.data().size).unwrap_or_default()
    }
    fn left_size(&self) -> usize {
        self.root()
            .and_then(|root| root.left().map(|left| left.data().size))
            .unwrap_or_default()
    }

pub fn right(&self) -> Option<Self>

Examples found in repository

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

    pub fn traverse<F>(self, f: &mut F)
    where
        S::T: 'a,
        F: FnMut(Self),
    {
        if let Some(left) = self.clone().left() {
            left.traverse(f);
        }
        f(self);
        if let Some(right) = self.clone().right() {
            right.traverse(f);
        }
    }
}

impl<'a, S> NodeRef<marker::DataMut<'a>, S>
where
    S: SplaySpec,
    S::T: 'a,
{
    pub fn data(&self) -> &'a S::T {
        unsafe { &(*self.as_ptr()).data }
    }
    pub fn data_mut(&self) -> &'a mut S::T {
        unsafe { &mut (*self.as_ptr()).data }
    }
    pub fn left(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .left
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn right(&self) -> Option<Self> {
        unsafe {
            (*self.as_ptr())
                .right
                .map(|node| NodeRef::new_unchecked(node))
        }
    }
    pub fn reverse(&self) {
        unsafe {
            let node = &mut (*self.as_ptr());
            swap(&mut node.left, &mut node.right);
        }
    }
}

impl<'a, S> NodeRef<marker::Mut<'a>, S>
where
    S: SplaySpec,
    S::T: 'a,
{
    pub fn data(self) -> &'a S::T {
        unsafe { &(*self.as_ptr()).data }
    }
    pub fn data_mut(self) -> &'a mut S::T {
        unsafe { &mut (*self.as_ptr()).data }
    }
    pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
    }
    pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
    }
    pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
        unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
    }
    pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
        unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
    }
}

impl<S> NodeRef<marker::Dying, S>
where
    S: SplaySpec,
{
    pub unsafe fn into_inner(self) -> NonNull<Node<S::T>> {
        let node = self.node;
        unsafe {
            debug_assert!((*node.as_ptr()).left.is_none());
            debug_assert!((*node.as_ptr()).right.is_none());
        }
        node
    }
    pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
    where
        A: Allocator<Node<S::T>>,
    {
        let Node { data, left, right } = allocator.deallocate(self.node);
        debug_assert!(left.is_none());
        debug_assert!(right.is_none());
        data
    }
}

impl<S> NodeRef<marker::Owned, S>
where
    S: SplaySpec,
{
    /// `cmp(key)`: [`Ordering`] between splaying and `key`
    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
        Some(self.root.as_ref()?.reborrow())
    }
    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
        Some(self.root.as_mut()?.borrow_datamut())
    }
    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: SplaySeeker<S = S>,
    {
        let (ord, root) = self.root.take()?.splay_by(seeker);
        self.root = Some(root);
        Some(ord)
    }
    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?;
        let right = root.borrow_mut().take_right();
        self.root = root.borrow_mut().take_left();
        self.append(&mut Self::new(right));
        Some(root)
    }
    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
        let right = root.borrow_mut().take_right();
        self.root = right;
        Some(root)
    }
    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
        let left = root.borrow_mut().take_left();
        self.root = left;
        Some(root)
    }
    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let left = root.borrow_mut().take_left();
        S::bottom_up(root.borrow_datamut());
        left
    }
    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let right = root.borrow_mut().take_right();
        S::bottom_up(root.borrow_datamut());
        right
    }
    pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let right = self.split_right();
        replace(&mut self.root, right)
    }
    pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let left = self.split_left();
        replace(&mut self.root, left)
    }
    pub fn append(&mut self, other: &mut Self) {
        self.root = match (self.root.take(), other.root.take()) {
            (Some(node), None) | (None, Some(node)) => Some(node),
            (Some(left), Some(right)) => Some(left.merge(right)),
            (None, None) => None,
        }
    }
    pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
    where
        Seeker: SplaySeeker<S = S>,
    {
        if self.is_empty() {
            return NodeRange::new(self);
        }
        let right = match end {
            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Greater | Ordering::Equal => self.split_right(),
                Ordering::Less => self.split_right_eq(),
            },
            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Greater => self.split_right(),
                Ordering::Less | Ordering::Equal => self.split_right_eq(),
            },
            Bound::Unbounded => None,
        };
        if self.is_empty() {
            return NodeRange::three_way(None, self, right);
        }
        let left = match start {
            Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Less | Ordering::Equal => self.split_left(),
                Ordering::Greater => self.split_left_eq(),
            },
            Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
                Ordering::Less => self.split_left(),
                Ordering::Greater | Ordering::Equal => self.split_left_eq(),
            },
            Bound::Unbounded => None,
        };
        NodeRange::three_way(left, self, right)
    }
}

impl<S> Debug for Root<S>
where
    S: SplaySpec,
    S::T: Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fn fmt_recurse<'a, S>(
            node: NodeRef<marker::Immut<'a>, S>,
            f: &mut fmt::Formatter<'_>,
        ) -> fmt::Result
        where
            S: SplaySpec,
            S::T: 'a + Debug,
        {
            write!(f, "[")?;
            if let Some(left) = node.left() {
                fmt_recurse(left, f)?;
            }
            node.data().fmt(f)?;
            if let Some(right) = node.right() {
                fmt_recurse(right, f)?;
            }
            write!(f, "]")?;
            Ok(())
        }

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

    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        if let Some(lagg) = node.right().map(|r| &r.data().agg) {
            let nacc = T::agg_operate(lagg, &self.acc);
            if (self.f)(&nacc) {
                return Ordering::Greater;
            }
            self.acc = nacc;
        };
        self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
        if (self.f)(&self.acc) {
            Ordering::Equal
        } else {
            Ordering::Less
        }
    }

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

where S::T: 'a, F: FnMut(Self),

Examples found in repository

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

    pub fn traverse<F>(self, f: &mut F)
    where
        S::T: 'a,
        F: FnMut(Self),
    {
        if let Some(left) = self.clone().left() {
            left.traverse(f);
        }
        f(self);
        if let Some(right) = self.clone().right() {
            right.traverse(f);
        }
    }

impl<'a, S> NodeRef<DataMut<'a>, S>

where S: SplaySpec, S::T: 'a,

pub fn data(&self) -> &'a S::T

Examples found in repository

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

    fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
        let l = node.left().map(|p| p.data().1).unwrap_or_default();
        let r = node.right().map(|p| p.data().1).unwrap_or_default();
        node.data_mut().1 = l + r + 1;
    }
}

struct SeekByKey<'a, K, V, Q>
where
    Q: ?Sized,
{
    key: &'a Q,
    _marker: PhantomData<fn() -> (K, V)>,
}
impl<'a, K, V, Q> SeekByKey<'a, K, V, Q>
where
    Q: ?Sized,
{
    fn new(key: &'a Q) -> Self {
        Self {
            key,
            _marker: PhantomData,
        }
    }
}
impl<K, V, Q> SplaySeeker for SeekByKey<'_, K, V, Q>
where
    K: Borrow<Q>,
    Q: Ord + ?Sized,
{
    type S = SizedSplay<(K, V)>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        self.key.cmp((node.data().0).0.borrow())
    }
}

struct SeekBySize<K, V> {
    index: usize,
    _marker: PhantomData<fn() -> (K, V)>,
}
impl<K, V> SeekBySize<K, V> {
    fn new(index: usize) -> Self {
        Self {
            index,
            _marker: PhantomData,
        }
    }
}
impl<K, V> SplaySeeker for SeekBySize<K, V> {
    type S = SizedSplay<(K, V)>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        let lsize = node.left().map(|l| l.data().1).unwrap_or_default();
        let ord = self.index.cmp(&lsize);
        if matches!(ord, Ordering::Greater) {
            self.index -= lsize + 1;
        }
        ord
    }
}

pub struct SplayMap<K, V, A = MemoryPool<Node<((K, V), usize)>>>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    root: Root<SizedSplay<(K, V)>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

impl<K, V, A> Debug for SplayMap<K, V, A>
where
    K: Debug,
    V: Debug,
    A: Allocator<Node<((K, V), usize)>>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SplayMap")
            .field("root", &self.root)
            .field("length", &self.length)
            .finish()
    }
}

impl<K, V, A> Drop for SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<K, V, A> Default for SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<K, V> SplayMap<K, V> {
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
}
impl<K, V, A> SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.get_key_value(key).map(|(_, v)| v)
    }
    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.root.splay_by(SeekByKey::new(key))
    }
    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
        self.root.splay_by(SeekBySize::new(index))
    }
    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ord = self.splay_by_key(&key);
        self.length += (ord != Some(Ordering::Equal)) as usize;
        match ord {
            Some(Ordering::Equal) => {
                return Some(replace(
                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
                    value,
                ));
            }
            Some(Ordering::Less) => unsafe {
                self.root.insert_left(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
            _ => unsafe {
                self.root.insert_right(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
        }
        None
    }
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
    }
    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
    }
    pub fn len(&self) -> usize {
        self.length
    }
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    pub fn iter(&mut self) -> Iter<'_, K, V> {
        Iter {
            iter: NodeRange::new(&mut self.root),
        }
    }
    pub fn range<Q, R>(&mut self, range: R) -> Iter<'_, K, V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
        R: RangeBounds<Q>,
    {
        let start = match range.start_bound() {
            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
            Bound::Unbounded => Bound::Unbounded,
        };
        let end = match range.end_bound() {
            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
            Bound::Unbounded => Bound::Unbounded,
        };
        Iter {
            iter: self.root.range(start, end),
        }
    }
    pub fn range_at<R>(&mut self, range: R) -> Iter<'_, K, V>
    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,
        };
        Iter {
            iter: self.root.range(start, end),
        }
    }
}

#[derive(Debug)]
pub struct Iter<'a, K, V> {
    iter: NodeRange<'a, SizedSplay<(K, V)>>,
}
impl<K, V> Iterator for Iter<'_, K, V>
where
    K: Clone,
    V: Clone,
{
    type Item = (K, V);
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next_checked().map(|node| node.data().0.clone())
    }
    fn last(mut self) -> Option<Self::Item> {
        self.next_back()
    }
    fn min(mut self) -> Option<Self::Item> {
        self.next()
    }
    fn max(mut self) -> Option<Self::Item> {
        self.next_back()
    }
}
impl<K, V> FusedIterator for Iter<'_, K, V>
where
    K: Clone,
    V: Clone,
{
}
impl<K, V> DoubleEndedIterator for Iter<'_, K, V>
where
    K: Clone,
    V: Clone,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter
            .next_back_checked()
            .map(|node| node.data().0.clone())
    }

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

    pub fn update_lazy(mut node: NodeRef<marker::DataMut<'_>, Self>, lazy: &T::Act) {
        T::act_operate_assign(&mut node.data_mut().lazy, lazy);
        node.data_mut().key = T::act_key(&node.data().key, lazy);
        if let Some(nxlazy) = T::act_agg(&node.data().agg, lazy) {
            node.data_mut().agg = nxlazy;
        } else {
            node = Self::propagate(node);
            Self::recalc(node);
        }
    }
    pub fn reverse(node: NodeRef<marker::DataMut<'_>, Self>) {
        node.reverse();
        T::toggle(&mut node.data_mut().agg);
        node.data_mut().rev ^= true;
    }
    fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
        if let Some(left) = node.left() {
            Self::update_lazy(left, &lazy);
        }
        if let Some(right) = node.right() {
            Self::update_lazy(right, &lazy);
        }
        if replace(&mut node.data_mut().rev, false) {
            if let Some(left) = node.left() {
                Self::reverse(left);
            }
            if let Some(right) = node.right() {
                Self::reverse(right);
            }
        }
        node
    }
    fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let mut agg = T::single_agg(&node.data().key);
        let mut size = 1;
        if let Some(left) = node.left() {
            let data = left.data();
            agg = T::agg_operate(&data.agg, &agg);
            // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
            size += data.size;
        }
        if let Some(right) = node.right() {
            let data = right.data();
            agg = T::agg_operate(&agg, &data.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.agg = agg;
        data.size = size;
        node
    }

pub fn data_mut(&self) -> &'a mut S::T

Examples found in repository

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

    fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
        let l = node.left().map(|p| p.data().1).unwrap_or_default();
        let r = node.right().map(|p| p.data().1).unwrap_or_default();
        node.data_mut().1 = l + r + 1;
    }
}

struct SeekByKey<'a, K, V, Q>
where
    Q: ?Sized,
{
    key: &'a Q,
    _marker: PhantomData<fn() -> (K, V)>,
}
impl<'a, K, V, Q> SeekByKey<'a, K, V, Q>
where
    Q: ?Sized,
{
    fn new(key: &'a Q) -> Self {
        Self {
            key,
            _marker: PhantomData,
        }
    }
}
impl<K, V, Q> SplaySeeker for SeekByKey<'_, K, V, Q>
where
    K: Borrow<Q>,
    Q: Ord + ?Sized,
{
    type S = SizedSplay<(K, V)>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        self.key.cmp((node.data().0).0.borrow())
    }
}

struct SeekBySize<K, V> {
    index: usize,
    _marker: PhantomData<fn() -> (K, V)>,
}
impl<K, V> SeekBySize<K, V> {
    fn new(index: usize) -> Self {
        Self {
            index,
            _marker: PhantomData,
        }
    }
}
impl<K, V> SplaySeeker for SeekBySize<K, V> {
    type S = SizedSplay<(K, V)>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        let lsize = node.left().map(|l| l.data().1).unwrap_or_default();
        let ord = self.index.cmp(&lsize);
        if matches!(ord, Ordering::Greater) {
            self.index -= lsize + 1;
        }
        ord
    }
}

pub struct SplayMap<K, V, A = MemoryPool<Node<((K, V), usize)>>>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    root: Root<SizedSplay<(K, V)>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

impl<K, V, A> Debug for SplayMap<K, V, A>
where
    K: Debug,
    V: Debug,
    A: Allocator<Node<((K, V), usize)>>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SplayMap")
            .field("root", &self.root)
            .field("length", &self.length)
            .finish()
    }
}

impl<K, V, A> Drop for SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<K, V, A> Default for SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<K, V> SplayMap<K, V> {
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
}
impl<K, V, A> SplayMap<K, V, A>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.get_key_value(key).map(|(_, v)| v)
    }
    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.root.splay_by(SeekByKey::new(key))
    }
    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
        self.root.splay_by(SeekBySize::new(index))
    }
    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ord = self.splay_by_key(&key);
        self.length += (ord != Some(Ordering::Equal)) as usize;
        match ord {
            Some(Ordering::Equal) => {
                return Some(replace(
                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
                    value,
                ));
            }
            Some(Ordering::Less) => unsafe {
                self.root.insert_left(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
            _ => unsafe {
                self.root.insert_right(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
        }
        None
    }

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

    pub fn update_lazy(mut node: NodeRef<marker::DataMut<'_>, Self>, lazy: &T::Act) {
        T::act_operate_assign(&mut node.data_mut().lazy, lazy);
        node.data_mut().key = T::act_key(&node.data().key, lazy);
        if let Some(nxlazy) = T::act_agg(&node.data().agg, lazy) {
            node.data_mut().agg = nxlazy;
        } else {
            node = Self::propagate(node);
            Self::recalc(node);
        }
    }
    pub fn reverse(node: NodeRef<marker::DataMut<'_>, Self>) {
        node.reverse();
        T::toggle(&mut node.data_mut().agg);
        node.data_mut().rev ^= true;
    }
    fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
        if let Some(left) = node.left() {
            Self::update_lazy(left, &lazy);
        }
        if let Some(right) = node.right() {
            Self::update_lazy(right, &lazy);
        }
        if replace(&mut node.data_mut().rev, false) {
            if let Some(left) = node.left() {
                Self::reverse(left);
            }
            if let Some(right) = node.right() {
                Self::reverse(right);
            }
        }
        node
    }
    fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let mut agg = T::single_agg(&node.data().key);
        let mut size = 1;
        if let Some(left) = node.left() {
            let data = left.data();
            agg = T::agg_operate(&data.agg, &agg);
            // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
            size += data.size;
        }
        if let Some(right) = node.right() {
            let data = right.data();
            agg = T::agg_operate(&agg, &data.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.agg = agg;
        data.size = size;
        node
    }
}
impl<T> SplaySpec for LazyAggSplay<T>
where
    T: MonoidAction,
{
    type T = LazyAggElement<T>;
    fn has_bottom_up() -> bool {
        true
    }
    fn top_down(node: NodeRef<marker::DataMut<'_>, Self>) {
        Self::propagate(node);
    }
    fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
        Self::recalc(node);
    }
}

struct SeekBySize<T> {
    index: usize,
    _marker: PhantomData<fn() -> T>,
}
impl<T> SeekBySize<T> {
    fn new(index: usize) -> Self {
        Self {
            index,
            _marker: PhantomData,
        }
    }
}
impl<T> SplaySeeker for SeekBySize<T>
where
    T: MonoidAction,
{
    type S = LazyAggSplay<T>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
        let ord = self.index.cmp(&lsize);
        if matches!(ord, Ordering::Greater) {
            self.index -= lsize + 1;
        }
        ord
    }
}

struct SeekByAccCond<F, T>
where
    T: MonoidAction,
{
    acc: T::Agg,
    f: F,
    _marker: PhantomData<fn() -> T>,
}
impl<F, T> SeekByAccCond<F, T>
where
    T: MonoidAction,
{
    fn new(f: F) -> Self {
        Self {
            acc: T::agg_unit(),
            f,
            _marker: PhantomData,
        }
    }
}
impl<F, T> SplaySeeker for SeekByAccCond<F, T>
where
    F: FnMut(&T::Agg) -> bool,
    T: MonoidAction,
{
    type S = LazyAggSplay<T>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        if let Some(lagg) = node.left().map(|l| &l.data().agg) {
            let nacc = T::agg_operate(&self.acc, lagg);
            if (self.f)(&nacc) {
                return Ordering::Less;
            }
            self.acc = nacc;
        };
        self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
        if (self.f)(&self.acc) {
            Ordering::Equal
        } else {
            Ordering::Greater
        }
    }
}

struct SeekByRaccCond<F, T>
where
    T: MonoidAction,
{
    acc: T::Agg,
    f: F,
    _marker: PhantomData<fn() -> T>,
}
impl<F, T> SeekByRaccCond<F, T>
where
    T: MonoidAction,
{
    fn new(f: F) -> Self {
        Self {
            acc: T::agg_unit(),
            f,
            _marker: PhantomData,
        }
    }
}
impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
where
    F: FnMut(&T::Agg) -> bool,
    T: MonoidAction,
{
    type S = LazyAggSplay<T>;
    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
        if let Some(lagg) = node.right().map(|r| &r.data().agg) {
            let nacc = T::agg_operate(lagg, &self.acc);
            if (self.f)(&nacc) {
                return Ordering::Greater;
            }
            self.acc = nacc;
        };
        self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
        if (self.f)(&self.acc) {
            Ordering::Equal
        } else {
            Ordering::Less
        }
    }
}

pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    root: Root<LazyAggSplay<T>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

impl<T, A> Debug for SplaySequence<T, A>
where
    T: MonoidAction,
    T::Key: Debug,
    T::Agg: Debug,
    T::Act: Debug,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SplayMap")
            .field("root", &self.root)
            .field("length", &self.length)
            .finish()
    }
}

impl<T, A> Drop for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }
}

impl<T, A> Default for SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>> + Default,
{
    fn default() -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: Default::default(),
        }
    }
}

impl<T> SplaySequence<T>
where
    T: MonoidAction,
{
    pub fn new() -> Self {
        Default::default()
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: Root::default(),
            length: 0,
            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
        }
    }
    pub fn len(&self) -> usize {
        self.length
    }
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }
}
impl<T, A> SplaySequence<T, A>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    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 left(&self) -> Option<Self>

Examples found in repository

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

    fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
        let l = node.left().map(|p| p.data().1).unwrap_or_default();
        let r = node.right().map(|p| p.data().1).unwrap_or_default();
        node.data_mut().1 = l + r + 1;
    }

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

    fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
        if let Some(left) = node.left() {
            Self::update_lazy(left, &lazy);
        }
        if let Some(right) = node.right() {
            Self::update_lazy(right, &lazy);
        }
        if replace(&mut node.data_mut().rev, false) {
            if let Some(left) = node.left() {
                Self::reverse(left);
            }
            if let Some(right) = node.right() {
                Self::reverse(right);
            }
        }
        node
    }
    fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let mut agg = T::single_agg(&node.data().key);
        let mut size = 1;
        if let Some(left) = node.left() {
            let data = left.data();
            agg = T::agg_operate(&data.agg, &agg);
            // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
            size += data.size;
        }
        if let Some(right) = node.right() {
            let data = right.data();
            agg = T::agg_operate(&agg, &data.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.agg = agg;
        data.size = size;
        node
    }

pub fn right(&self) -> Option<Self>

Examples found in repository

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

    fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
        let l = node.left().map(|p| p.data().1).unwrap_or_default();
        let r = node.right().map(|p| p.data().1).unwrap_or_default();
        node.data_mut().1 = l + r + 1;
    }

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

    fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
        if let Some(left) = node.left() {
            Self::update_lazy(left, &lazy);
        }
        if let Some(right) = node.right() {
            Self::update_lazy(right, &lazy);
        }
        if replace(&mut node.data_mut().rev, false) {
            if let Some(left) = node.left() {
                Self::reverse(left);
            }
            if let Some(right) = node.right() {
                Self::reverse(right);
            }
        }
        node
    }
    fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
        let mut agg = T::single_agg(&node.data().key);
        let mut size = 1;
        if let Some(left) = node.left() {
            let data = left.data();
            agg = T::agg_operate(&data.agg, &agg);
            // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
            size += data.size;
        }
        if let Some(right) = node.right() {
            let data = right.data();
            agg = T::agg_operate(&agg, &data.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.agg = agg;
        data.size = size;
        node
    }

pub fn reverse(&self)

Examples found in repository

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

    pub fn reverse(node: NodeRef<marker::DataMut<'_>, Self>) {
        node.reverse();
        T::toggle(&mut node.data_mut().agg);
        node.data_mut().rev ^= true;
    }

impl<'a, S> NodeRef<Mut<'a>, S>

where S: SplaySpec, S::T: 'a,

pub fn data(self) -> &'a S::T

pub fn data_mut(self) -> &'a mut S::T

pub fn take_left(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository

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

    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
        Some(self.root.as_ref()?.reborrow())
    }
    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
        Some(self.root.as_mut()?.borrow_datamut())
    }
    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: SplaySeeker<S = S>,
    {
        let (ord, root) = self.root.take()?.splay_by(seeker);
        self.root = Some(root);
        Some(ord)
    }
    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?;
        let right = root.borrow_mut().take_right();
        self.root = root.borrow_mut().take_left();
        self.append(&mut Self::new(right));
        Some(root)
    }
    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
        let right = root.borrow_mut().take_right();
        self.root = right;
        Some(root)
    }
    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
        let left = root.borrow_mut().take_left();
        self.root = left;
        Some(root)
    }
    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let left = root.borrow_mut().take_left();
        S::bottom_up(root.borrow_datamut());
        left
    }

pub fn take_right(&mut self) -> Option<NodeRef<Owned, S>>

Examples found in repository

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

    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
        Some(self.root.as_ref()?.reborrow())
    }
    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
        Some(self.root.as_mut()?.borrow_datamut())
    }
    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: SplaySeeker<S = S>,
    {
        let (ord, root) = self.root.take()?.splay_by(seeker);
        self.root = Some(root);
        Some(ord)
    }
    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?;
        let right = root.borrow_mut().take_right();
        self.root = root.borrow_mut().take_left();
        self.append(&mut Self::new(right));
        Some(root)
    }
    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
        let right = root.borrow_mut().take_right();
        self.root = right;
        Some(root)
    }
    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
        let left = root.borrow_mut().take_left();
        self.root = left;
        Some(root)
    }
    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let left = root.borrow_mut().take_left();
        S::bottom_up(root.borrow_datamut());
        left
    }
    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let root = self.root.as_mut()?;
        let right = root.borrow_mut().take_right();
        S::bottom_up(root.borrow_datamut());
        right
    }

pub fn set_left(&mut self, node: Option<NodeRef<Owned, S>>)

Examples found in repository

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

    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }

pub fn set_right(&mut self, node: Option<NodeRef<Owned, S>>)

Examples found in repository

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

    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
    where
        Seeker: SplaySeeker<S = S>,
    {
        let mut x = self;
        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
        let mut left_entry = &mut left_subtree;
        let mut right_entry = &mut right_subtree;
        let mut stack = vec![];

        macro_rules! add {
            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
                *$entry = $node;
                if S::has_bottom_up() {
                    stack.push($ptr.node);
                }
                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
            };
        }

        let root_ord = loop {
            S::top_down(x.borrow_datamut());
            match seeker.splay_seek(x.reborrow()) {
                Ordering::Less => {
                    if let Some(mut y) = x.borrow_mut().take_left() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_right(Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@right Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@right Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@right Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Less;
                    }
                }
                Ordering::Equal => break Ordering::Equal,
                Ordering::Greater => {
                    if let Some(mut y) = x.borrow_mut().take_right() {
                        S::top_down(y.borrow_datamut());
                        match seeker.splay_seek(y.reborrow()) {
                            Ordering::Less => {
                                if let Some(mut z) = y.borrow_mut().take_left() {
                                    S::top_down(z.borrow_datamut());
                                    add!(@left Some(x));
                                    add!(@right Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Less;
                                }
                            }
                            Ordering::Equal => {
                                add!(@left Some(x));
                                x = y;
                                break Ordering::Equal;
                            }
                            Ordering::Greater => {
                                if let Some(mut z) = y.borrow_mut().take_right() {
                                    S::top_down(z.borrow_datamut());
                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
                                    S::bottom_up(x.borrow_datamut());
                                    y.borrow_mut().set_left(Some(x));
                                    add!(@left Some(y));
                                    x = z;
                                } else {
                                    add!(@left Some(x));
                                    x = y;
                                    break Ordering::Greater;
                                }
                            }
                        }
                    } else {
                        break Ordering::Greater;
                    }
                }
            }
        };
        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
        unsafe {
            x.borrow_mut()
                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
            x.borrow_mut()
                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
            if S::has_bottom_up() {
                while let Some(node) = stack.pop() {
                    S::bottom_up(NodeRef::new_unchecked(node));
                }
            }
        }
        S::bottom_up(x.borrow_datamut());
        (root_ord, x)
    }
    pub fn insert_left(mut self, mut node: Self) -> Self {
        if let Some(left) = self.borrow_mut().take_left() {
            node.borrow_mut().set_left(Some(left));
            S::bottom_up(self.borrow_datamut());
        };
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_right(mut self, mut node: Self) -> Self {
        if let Some(right) = self.borrow_mut().take_right() {
            node.borrow_mut().set_right(Some(right));
            S::bottom_up(self.borrow_datamut());
        }
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_first(self, mut node: Self) -> Self {
        node.borrow_mut().set_right(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn insert_last(self, mut node: Self) -> Self {
        node.borrow_mut().set_left(Some(self));
        S::bottom_up(node.borrow_datamut());
        node
    }
    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }

impl<S> NodeRef<Dying, S>

where S: SplaySpec,

pub unsafe fn into_inner(self) -> NonNull<Node<S::T>>

Examples found in repository

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

    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }

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

    fn drop(&mut self) {
        unsafe {
            while let Some(node) = self.root.take_first() {
                self.alloc.deallocate(node.into_dying().into_inner());
            }
            ManuallyDrop::drop(&mut self.alloc);
        }
    }

pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T

where A: Allocator<Node<S::T>>,

Examples found in repository

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

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

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

    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
    }
    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
    }

impl<S> NodeRef<Owned, S>

where S: SplaySpec,

pub fn splay_by<Seeker>(self, seeker: Seeker) -> (Ordering, Self)

where Seeker: SplaySeeker<S = S>,

cmp(key): Ordering between splaying and key

Examples found in repository

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

    pub fn merge(mut self, mut other: Self) -> Self {
        if other.reborrow().left().is_none() {
            S::top_down(other.borrow_datamut());
            other.borrow_mut().set_left(Some(self));
            S::bottom_up(other.borrow_datamut());
            other
        } else {
            self = self.splay_by(SeekRight::new()).1;
            self.borrow_mut().set_right(Some(other));
            S::bottom_up(self.borrow_datamut());
            self
        }
    }
}

impl<S> Root<S>
where
    S: SplaySpec,
{
    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
        Self { root }
    }
    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
        unsafe { Self::from_single_nodes_inner(&nodes) }
    }
    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
        if nodes.is_empty() {
            Self::new(None)
        } else {
            let m = nodes.len() / 2;
            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
            let mut node = NodeRef::new(nodes[m].node);
            node.borrow_mut().set_left(left.root);
            node.borrow_mut().set_right(right.root);
            S::bottom_up(node.borrow_datamut());
            Self::new(Some(node))
        }
    }
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
        Some(self.root.as_ref()?.reborrow())
    }
    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
        Some(self.root.as_mut()?.borrow_datamut())
    }
    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: SplaySeeker<S = S>,
    {
        let (ord, root) = self.root.take()?.splay_by(seeker);
        self.root = Some(root);
        Some(ord)
    }
    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }
    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?;
        let right = root.borrow_mut().take_right();
        self.root = root.borrow_mut().take_left();
        self.append(&mut Self::new(right));
        Some(root)
    }
    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
        let right = root.borrow_mut().take_right();
        self.root = right;
        Some(root)
    }
    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
        let left = root.borrow_mut().take_left();
        self.root = left;
        Some(root)
    }

pub fn insert_left(self, node: Self) -> Self

Examples found in repository

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

    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_left(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }

pub fn insert_right(self, node: Self) -> Self

Examples found in repository

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

    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_right(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }

pub fn insert_first(self, node: Self) -> Self

Examples found in repository

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

    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_first(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }

pub fn insert_last(self, node: Self) -> Self

Examples found in repository

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

    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
        self.root = Some(match self.root.take() {
            Some(root) => root.insert_last(node),
            None => {
                S::bottom_up(node.borrow_datamut());
                node
            }
        });
    }

pub fn merge(self, other: Self) -> Self

Examples found in repository

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

    pub fn append(&mut self, other: &mut Self) {
        self.root = match (self.root.take(), other.root.take()) {
            (Some(node), None) | (None, Some(node)) => Some(node),
            (Some(left), Some(right)) => Some(left.merge(right)),
            (None, None) => None,
        }
    }

Trait Implementations

impl<'a, S> Clone for NodeRef<Immut<'a>, S>

where S: SplaySpec, S::T: 'a,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'a, S> Copy for NodeRef<Immut<'a>, S>

where S: SplaySpec, S::T: 'a,