Struct ImplicitSplayTree 

pub struct ImplicitSplayTree<T, A = MemoryPool<BstNode<ImplicitSplayTreeData<T>>>>
where
    T: LazyMapMonoid,
    A: Allocator<BstNode<ImplicitSplayTreeData<T>>>,
{
    root: Option<BstRoot<ImplicitSplayTreeSpec<T>>>,
    length: usize,
    allocator: ManuallyDrop<A>,
    _marker: PhantomData<fn() -> T>,
}

Fields

root: Option<BstRoot<ImplicitSplayTreeSpec<T>>>

length: usize

allocator: ManuallyDrop<A>

_marker: PhantomData<fn() -> T>

Implementations

impl<T> ImplicitSplayTree<T>

where T: LazyMapMonoid,

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository

crates/library_checker/src/data_structure/range_reverse_range_sum.rs (line 38)

pub fn range_reverse_range_sum_implicit_splay_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [i64; iter n]);
    let mut seq = ImplicitSplayTree::<RangeSumRangeAdd<i64>>::with_capacity(n);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Sum { l, r } => {
                let ans = seq.fold(l..r).0;
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 55)

pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
    reader: impl Read,
    writer: impl Write,
) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

impl<T, A> ImplicitSplayTree<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitSplayTreeData<T>>>,

fn node(&mut self, key: T::Key) -> BstRoot<ImplicitSplayTreeSpec<T>>

Examples found in repository

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

    pub fn insert(&mut self, index: usize, key: T::Key) {
        assert!(index <= self.length);
        let mut node = self.node(key);
        if self.root.is_none() {
            self.root = Some(node);
        } else if index == self.length {
            self.splay(SeekBySize::new(index));
            unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        } else {
            self.splay(SeekBySize::new(index));
            let mut root = self.root.take().unwrap();
            let left = unsafe { root.borrow_mut().left_mut().take() };
            if let Some(left) = left {
                unsafe { node.borrow_mut().left_mut().set(left) };
            }
            ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
            unsafe { node.borrow_mut().right_mut().set(root) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        }
        self.length += 1;
    }

    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
        if index >= self.length {
            return None;
        }
        self.splay(SeekBySize::new(index));
        let mut node = self.root.take().unwrap();
        ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
        let left = unsafe { node.borrow_mut().left_mut().take() };
        let right = unsafe { node.borrow_mut().right_mut().take() };
        self.root = ImplicitSplayTreeSpec::merge(left, right);
        self.length -= 1;
        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
        Some(data.value.key)
    }

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

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

    pub fn rotate_left(&mut self, mid: usize) {
        assert!(mid <= self.length);
        if mid == 0 || mid == self.length {
            return;
        }
        let (left, right) =
            ImplicitSplayTreeSpec::split(self.root.take(), SeekBySize::new(mid), EqualSide::Right);
        self.root = ImplicitSplayTreeSpec::merge(right, 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 ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let nodes = iter
            .into_iter()
            .map(|key| self.node(key))
            .collect::<Vec<_>>();
        let len = nodes.len();
        let root = if len == 0 {
            None
        } else {
            let mut stack = Vec::with_capacity(64);
            stack.push((0, len, None::<(usize, usize)>, false));
            while let Some((start, end, parent, visited)) = stack.pop() {
                if start == end {
                    continue;
                }
                let mid = start + (end - start) / 2;
                if visited {
                    ImplicitSplayTreeSpec::bottom_up(
                        BstRoot::new(nodes[mid].node).borrow_datamut(),
                    );
                    continue;
                }
                if let Some((parent, direction)) = parent {
                    let mut parent = nodes[parent].node;
                    unsafe { parent.as_mut().child[direction] = Some(nodes[mid].node) };
                }
                stack.push((start, end, parent, true));
                stack.push((mid + 1, end, Some((mid, 1)), false));
                stack.push((start, mid, Some((mid, 0)), false));
            }
            Some(BstRoot::new(nodes[len / 2].node))
        };
        self.root = ImplicitSplayTreeSpec::merge(self.root.take(), root);
        self.length += len;
    }

fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>

where Seeker: BstSeeker<Spec = ImplicitSplayTreeSpec<T>>,

Examples found in repository

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

    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
        if index >= self.length {
            return None;
        }
        self.splay(SeekBySize::new(index));
        Some(&self.root.as_ref()?.reborrow().into_data().value.key)
    }

    pub fn modify<F>(&mut self, index: usize, f: F)
    where
        F: FnOnce(&T::Key) -> T::Key,
    {
        assert!(index < self.length);
        self.splay(SeekBySize::new(index));
        let mut root = self.root.as_mut().unwrap().borrow_datamut();
        ImplicitSplayTreeSpec::top_down(root.reborrow_datamut());
        {
            let data = root.data_mut();
            data.value.key = f(&data.value.key);
        }
        ImplicitSplayTreeSpec::bottom_up(root);
    }

    pub fn insert(&mut self, index: usize, key: T::Key) {
        assert!(index <= self.length);
        let mut node = self.node(key);
        if self.root.is_none() {
            self.root = Some(node);
        } else if index == self.length {
            self.splay(SeekBySize::new(index));
            unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        } else {
            self.splay(SeekBySize::new(index));
            let mut root = self.root.take().unwrap();
            let left = unsafe { root.borrow_mut().left_mut().take() };
            if let Some(left) = left {
                unsafe { node.borrow_mut().left_mut().set(left) };
            }
            ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
            unsafe { node.borrow_mut().right_mut().set(root) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        }
        self.length += 1;
    }

    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
        if index >= self.length {
            return None;
        }
        self.splay(SeekBySize::new(index));
        let mut node = self.root.take().unwrap();
        ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
        let left = unsafe { node.borrow_mut().left_mut().take() };
        let right = unsafe { node.borrow_mut().right_mut().take() };
        self.root = ImplicitSplayTreeSpec::merge(left, right);
        self.length -= 1;
        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
        Some(data.value.key)
    }

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn update<R>(&mut self, range: R, act: T::Act)

where R: RangeBounds<usize>,

Examples found in repository

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 70)

pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
    reader: impl Read,
    writer: impl Write,
) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn fold<R>(&mut self, range: R) -> T::Agg

where R: RangeBounds<usize>,

Examples found in repository

crates/library_checker/src/data_structure/range_reverse_range_sum.rs (line 47)

pub fn range_reverse_range_sum_implicit_splay_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [i64; iter n]);
    let mut seq = ImplicitSplayTree::<RangeSumRangeAdd<i64>>::with_capacity(n);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Sum { l, r } => {
                let ans = seq.fold(l..r).0;
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 73)

pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
    reader: impl Read,
    writer: impl Write,
) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn reverse<R>(&mut self, range: R)

where R: RangeBounds<usize>,

Examples found in repository

crates/library_checker/src/data_structure/range_reverse_range_sum.rs (line 44)

pub fn range_reverse_range_sum_implicit_splay_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [i64; iter n]);
    let mut seq = ImplicitSplayTree::<RangeSumRangeAdd<i64>>::with_capacity(n);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Sum { l, r } => {
                let ans = seq.fold(l..r).0;
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 67)

pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
    reader: impl Read,
    writer: impl Write,
) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn get(&mut self, index: usize) -> Option<&T::Key>

pub fn modify<F>(&mut self, index: usize, f: F)

where F: FnOnce(&T::Key) -> T::Key,

pub fn insert(&mut self, index: usize, key: T::Key)

Examples found in repository

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 61)

pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
    reader: impl Read,
    writer: impl Write,
) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn remove(&mut self, index: usize) -> Option<T::Key>

Examples found in repository

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 64)

pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
    reader: impl Read,
    writer: impl Write,
) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn partition_point_acc<F>(&mut self, left: usize, pred: F) -> usize

where F: FnMut(&T::Agg) -> bool,

pub fn rpartition_point_acc<F>(&mut self, right: usize, pred: F) -> usize

where F: FnMut(&T::Agg) -> bool,

pub fn rotate_left(&mut self, mid: usize)

Examples found in repository

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

    pub fn rotate_right(&mut self, k: usize) {
        assert!(k <= self.length);
        self.rotate_left(self.length - k);
    }

pub fn rotate_right(&mut self, k: usize)

Trait Implementations

impl<T, A> Default for ImplicitSplayTree<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitSplayTreeData<T>>> + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T, A> Drop for ImplicitSplayTree<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitSplayTreeData<T>>>,

fn drop(&mut self)

Executes the destructor for this type.

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

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

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

impl<T, A> Extend<<T as LazyMapMonoid>::Key> for ImplicitSplayTree<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitSplayTreeData<T>>>,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = T::Key>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

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

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

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

Reserves capacity in a collection for the given number of additional elements.