Struct Implicit Splay Tree &nbsp; Copy item path

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)

35pub fn range_reverse_range_sum_implicit_splay_tree(reader: impl Read, writer: impl Write) {
36    prepare_io!(reader, writer);
37    sc!(n, q, a: [i64; iter n]);
38    let mut seq = ImplicitSplayTree::<RangeSumRangeAdd<i64>>::with_capacity(n);
39    seq.extend(a);
40    for _ in 0..q {
41        sc!(query: Query);
42        match query {
43            Query::Reverse { l, r } => {
44                seq.reverse(l..r);
45            }
46            Query::Sum { l, r } => {
47                let ans = seq.fold(l..r).0;
48                pp!(ans);
49            }
50        }
51    }
52}

More examples

Hide additional examples

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

48pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
49    reader: impl Read,
50    writer: impl Write,
51) {
52    prepare_io!(reader, writer);
53    sc!(n, q, a: [M; iter n]);
54
55    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
56    seq.extend(a);
57    for _ in 0..q {
58        sc!(query: Query);
59        match query {
60            Query::Insert { i, x } => {
61                seq.insert(i, x);
62            }
63            Query::Remove { i } => {
64                seq.remove(i);
65            }
66            Query::Reverse { l, r } => {
67                seq.reverse(l..r);
68            }
69            Query::Update { l, r, bc } => {
70                seq.update(l..r, bc);
71            }
72            Query::Fold { l, r } => {
73                pp!(seq.fold(l..r).0);
74            }
75        }
76    }
77}

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)

320    pub fn insert(&mut self, index: usize, key: T::Key) {
321        assert!(index <= self.length);
322        let mut node = self.node(key);
323        if self.root.is_none() {
324            self.root = Some(node);
325        } else if index == self.length {
326            self.splay(SeekBySize::new(index));
327            unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
328            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
329            self.root = Some(node);
330        } else {
331            self.splay(SeekBySize::new(index));
332            let mut root = self.root.take().unwrap();
333            let left = unsafe { root.borrow_mut().left_mut().take() };
334            if let Some(left) = left {
335                unsafe { node.borrow_mut().left_mut().set(left) };
336            }
337            ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
338            unsafe { node.borrow_mut().right_mut().set(root) };
339            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
340            self.root = Some(node);
341        }
342        self.length += 1;
343    }
344
345    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
346        if index >= self.length {
347            return None;
348        }
349        self.splay(SeekBySize::new(index));
350        let mut node = self.root.take().unwrap();
351        ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
352        let left = unsafe { node.borrow_mut().left_mut().take() };
353        let right = unsafe { node.borrow_mut().right_mut().take() };
354        self.root = ImplicitSplayTreeSpec::merge(left, right);
355        self.length -= 1;
356        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
357        Some(data.value.key)
358    }
359
360    pub fn partition_point_acc<F>(&mut self, left: usize, mut pred: F) -> usize
361    where
362        F: FnMut(&T::Agg) -> bool,
363    {
364        let mut split3 = Split3::seek_by_size(&mut self.root, left..);
365        let front_size = split3
366            .left()
367            .map(|node| node.into_data().size)
368            .unwrap_or_default();
369        let split = split3.split_mid(SeekByAccCond::new(|acc| !pred(acc)), EqualSide::Right);
370        let index = split
371            .left()
372            .map(|node| node.into_data().size)
373            .unwrap_or_default();
374        front_size + index
375    }
376
377    pub fn rpartition_point_acc<F>(&mut self, right: usize, mut pred: F) -> usize
378    where
379        F: FnMut(&T::Agg) -> bool,
380    {
381        let mut split3 = Split3::seek_by_size(&mut self.root, ..right);
382        let split = split3.split_mid(SeekByRaccCond::new(|acc| !pred(acc)), EqualSide::Left);
383        split
384            .left()
385            .map(|node| node.into_data().size)
386            .unwrap_or_default()
387    }
388
389    pub fn rotate_left(&mut self, mid: usize) {
390        assert!(mid <= self.length);
391        if mid == 0 || mid == self.length {
392            return;
393        }
394        let (left, right) =
395            ImplicitSplayTreeSpec::split(self.root.take(), SeekBySize::new(mid), EqualSide::Right);
396        self.root = ImplicitSplayTreeSpec::merge(right, left);
397    }
398
399    pub fn rotate_right(&mut self, k: usize) {
400        assert!(k <= self.length);
401        self.rotate_left(self.length - k);
402    }
403}
404
405impl<T, A> Extend<T::Key> for ImplicitSplayTree<T, A>
406where
407    T: LazyMapMonoid,
408    A: Allocator<ImplicitSplayTreeNode<T>>,
409{
410    fn extend<I>(&mut self, iter: I)
411    where
412        I: IntoIterator<Item = T::Key>,
413    {
414        let nodes = iter
415            .into_iter()
416            .map(|key| self.node(key))
417            .collect::<Vec<_>>();
418        let len = nodes.len();
419        let root = if len == 0 {
420            None
421        } else {
422            let mut stack = Vec::with_capacity(64);
423            stack.push((0, len, None::<(usize, usize)>, false));
424            while let Some((start, end, parent, visited)) = stack.pop() {
425                if start == end {
426                    continue;
427                }
428                let mid = start + (end - start) / 2;
429                if visited {
430                    ImplicitSplayTreeSpec::bottom_up(
431                        BstRoot::new(nodes[mid].node).borrow_datamut(),
432                    );
433                    continue;
434                }
435                if let Some((parent, direction)) = parent {
436                    let mut parent = nodes[parent].node;
437                    unsafe { parent.as_mut().child[direction] = Some(nodes[mid].node) };
438                }
439                stack.push((start, end, parent, true));
440                stack.push((mid + 1, end, Some((mid, 1)), false));
441                stack.push((start, mid, Some((mid, 0)), false));
442            }
443            Some(BstRoot::new(nodes[len / 2].node))
444        };
445        self.root = ImplicitSplayTreeSpec::merge(self.root.take(), root);
446        self.length += len;
447    }

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)

297    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
298        if index >= self.length {
299            return None;
300        }
301        self.splay(SeekBySize::new(index));
302        Some(&self.root.as_ref()?.reborrow().into_data().value.key)
303    }
304
305    pub fn modify<F>(&mut self, index: usize, f: F)
306    where
307        F: FnOnce(&T::Key) -> T::Key,
308    {
309        assert!(index < self.length);
310        self.splay(SeekBySize::new(index));
311        let mut root = self.root.as_mut().unwrap().borrow_datamut();
312        ImplicitSplayTreeSpec::top_down(root.reborrow_datamut());
313        {
314            let data = root.data_mut();
315            data.value.key = f(&data.value.key);
316        }
317        ImplicitSplayTreeSpec::bottom_up(root);
318    }
319
320    pub fn insert(&mut self, index: usize, key: T::Key) {
321        assert!(index <= self.length);
322        let mut node = self.node(key);
323        if self.root.is_none() {
324            self.root = Some(node);
325        } else if index == self.length {
326            self.splay(SeekBySize::new(index));
327            unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
328            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
329            self.root = Some(node);
330        } else {
331            self.splay(SeekBySize::new(index));
332            let mut root = self.root.take().unwrap();
333            let left = unsafe { root.borrow_mut().left_mut().take() };
334            if let Some(left) = left {
335                unsafe { node.borrow_mut().left_mut().set(left) };
336            }
337            ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
338            unsafe { node.borrow_mut().right_mut().set(root) };
339            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
340            self.root = Some(node);
341        }
342        self.length += 1;
343    }
344
345    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
346        if index >= self.length {
347            return None;
348        }
349        self.splay(SeekBySize::new(index));
350        let mut node = self.root.take().unwrap();
351        ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
352        let left = unsafe { node.borrow_mut().left_mut().take() };
353        let right = unsafe { node.borrow_mut().right_mut().take() };
354        self.root = ImplicitSplayTreeSpec::merge(left, right);
355        self.length -= 1;
356        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
357        Some(data.value.key)
358    }

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)

48pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
49    reader: impl Read,
50    writer: impl Write,
51) {
52    prepare_io!(reader, writer);
53    sc!(n, q, a: [M; iter n]);
54
55    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
56    seq.extend(a);
57    for _ in 0..q {
58        sc!(query: Query);
59        match query {
60            Query::Insert { i, x } => {
61                seq.insert(i, x);
62            }
63            Query::Remove { i } => {
64                seq.remove(i);
65            }
66            Query::Reverse { l, r } => {
67                seq.reverse(l..r);
68            }
69            Query::Update { l, r, bc } => {
70                seq.update(l..r, bc);
71            }
72            Query::Fold { l, r } => {
73                pp!(seq.fold(l..r).0);
74            }
75        }
76    }
77}

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)

35pub fn range_reverse_range_sum_implicit_splay_tree(reader: impl Read, writer: impl Write) {
36    prepare_io!(reader, writer);
37    sc!(n, q, a: [i64; iter n]);
38    let mut seq = ImplicitSplayTree::<RangeSumRangeAdd<i64>>::with_capacity(n);
39    seq.extend(a);
40    for _ in 0..q {
41        sc!(query: Query);
42        match query {
43            Query::Reverse { l, r } => {
44                seq.reverse(l..r);
45            }
46            Query::Sum { l, r } => {
47                let ans = seq.fold(l..r).0;
48                pp!(ans);
49            }
50        }
51    }
52}

More examples

Hide additional examples

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

48pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
49    reader: impl Read,
50    writer: impl Write,
51) {
52    prepare_io!(reader, writer);
53    sc!(n, q, a: [M; iter n]);
54
55    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
56    seq.extend(a);
57    for _ in 0..q {
58        sc!(query: Query);
59        match query {
60            Query::Insert { i, x } => {
61                seq.insert(i, x);
62            }
63            Query::Remove { i } => {
64                seq.remove(i);
65            }
66            Query::Reverse { l, r } => {
67                seq.reverse(l..r);
68            }
69            Query::Update { l, r, bc } => {
70                seq.update(l..r, bc);
71            }
72            Query::Fold { l, r } => {
73                pp!(seq.fold(l..r).0);
74            }
75        }
76    }
77}

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)

35pub fn range_reverse_range_sum_implicit_splay_tree(reader: impl Read, writer: impl Write) {
36    prepare_io!(reader, writer);
37    sc!(n, q, a: [i64; iter n]);
38    let mut seq = ImplicitSplayTree::<RangeSumRangeAdd<i64>>::with_capacity(n);
39    seq.extend(a);
40    for _ in 0..q {
41        sc!(query: Query);
42        match query {
43            Query::Reverse { l, r } => {
44                seq.reverse(l..r);
45            }
46            Query::Sum { l, r } => {
47                let ans = seq.fold(l..r).0;
48                pp!(ans);
49            }
50        }
51    }
52}

More examples

Hide additional examples

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

48pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
49    reader: impl Read,
50    writer: impl Write,
51) {
52    prepare_io!(reader, writer);
53    sc!(n, q, a: [M; iter n]);
54
55    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
56    seq.extend(a);
57    for _ in 0..q {
58        sc!(query: Query);
59        match query {
60            Query::Insert { i, x } => {
61                seq.insert(i, x);
62            }
63            Query::Remove { i } => {
64                seq.remove(i);
65            }
66            Query::Reverse { l, r } => {
67                seq.reverse(l..r);
68            }
69            Query::Update { l, r, bc } => {
70                seq.update(l..r, bc);
71            }
72            Query::Fold { l, r } => {
73                pp!(seq.fold(l..r).0);
74            }
75        }
76    }
77}

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)

48pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
49    reader: impl Read,
50    writer: impl Write,
51) {
52    prepare_io!(reader, writer);
53    sc!(n, q, a: [M; iter n]);
54
55    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
56    seq.extend(a);
57    for _ in 0..q {
58        sc!(query: Query);
59        match query {
60            Query::Insert { i, x } => {
61                seq.insert(i, x);
62            }
63            Query::Remove { i } => {
64                seq.remove(i);
65            }
66            Query::Reverse { l, r } => {
67                seq.reverse(l..r);
68            }
69            Query::Update { l, r, bc } => {
70                seq.update(l..r, bc);
71            }
72            Query::Fold { l, r } => {
73                pp!(seq.fold(l..r).0);
74            }
75        }
76    }
77}

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)

48pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
49    reader: impl Read,
50    writer: impl Write,
51) {
52    prepare_io!(reader, writer);
53    sc!(n, q, a: [M; iter n]);
54
55    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
56    seq.extend(a);
57    for _ in 0..q {
58        sc!(query: Query);
59        match query {
60            Query::Insert { i, x } => {
61                seq.insert(i, x);
62            }
63            Query::Remove { i } => {
64                seq.remove(i);
65            }
66            Query::Reverse { l, r } => {
67                seq.reverse(l..r);
68            }
69            Query::Update { l, r, bc } => {
70                seq.update(l..r, bc);
71            }
72            Query::Fold { l, r } => {
73                pp!(seq.fold(l..r).0);
74            }
75        }
76    }
77}

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)

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

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. Read more

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. Read more

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. Read more

impl<T, A> Extend<<T as LazyMapMonoid>::Key> for ImplicitSplayTree<T, A>
where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitSplayTreeData<T>>>,

fn extend(&mut self, iter: I)
where I: IntoIterator<Item = T::Key>,

Extends a collection with the contents of an iterator. Read more

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. Read more

Auto Trait Implementations§

impl<T, A = MemoryPool<BstNode<ImplicitSplayTreeData<T>>>> !Send for ImplicitSplayTree<T, A>

impl<T, A = MemoryPool<BstNode<ImplicitSplayTreeData<T>>>> !Sync for ImplicitSplayTree<T, A>

impl<T, A> Freeze for ImplicitSplayTree<T, A>
where Option<BstNodeRef<Owned, ImplicitSplayTreeSpec<T>>>: Freeze, ManuallyDrop<A>: Freeze, PhantomData<fn() -> T>: Freeze,

impl<T, A> RefUnwindSafe for ImplicitSplayTree<T, A>
where Option<BstNodeRef<Owned, ImplicitSplayTreeSpec<T>>>: RefUnwindSafe, ManuallyDrop<A>: RefUnwindSafe, PhantomData<fn() -> T>: RefUnwindSafe,

impl<T, A> Unpin for ImplicitSplayTree<T, A>
where Option<BstNodeRef<Owned, ImplicitSplayTreeSpec<T>>>: Unpin, ManuallyDrop<A>: Unpin, PhantomData<fn() -> T>: Unpin,

impl<T, A> UnsafeUnpin for ImplicitSplayTree<T, A>
where Option<BstNodeRef<Owned, ImplicitSplayTreeSpec<T>>>: UnsafeUnpin, ManuallyDrop<A>: UnsafeUnpin, PhantomData<fn() -> T>: UnsafeUnpin,

impl<T, A> UnwindSafe for ImplicitSplayTree<T, A>
where Option<BstNodeRef<Owned, ImplicitSplayTreeSpec<T>>>: UnwindSafe, ManuallyDrop<A>: UnwindSafe, PhantomData<fn() -> T>: UnwindSafe,

Blanket Implementations§

impl<T> Any for T
where T: 'static + ?Sized,

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

impl<T> Borrow<T> for T
where T: ?Sized,

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

impl<T> BorrowMut<T> for T
where T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more

impl<T> From<T> for T

fn from(t: T) -> T

Returns the argument unchanged.

impl<T, U> Into for T
where U: From<T>,

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

type Error = !

The type returned in the event of a conversion error.

fn try_from(value: U) -> Result<T, !>

Performs the conversion.

impl<T, U> TryInto for T
where U: TryFrom<T>,

type Error = >::Error

The type returned in the event of a conversion error.