competitive::data_structure::implicit_splay_tree

Struct ImplicitSplayTreeSpec

pub struct ImplicitSplayTreeSpec<T> {
    _marker: PhantomData<fn() -> T>,
}

Fields§

§_marker: PhantomData<fn() -> T>

Implementations§

Source §

impl<T> ImplicitSplayTreeSpec<T>
where T: LazyMapMonoid,

Source

fn update_act(node: BstDataMutRef<'_, Self>, act: &T::Act)

Examples found in repository ?

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

112    fn top_down(mut node: BstDataMutRef<'_, Self>) {
113        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
114            let act = replace(&mut node.data_mut().value.act, T::act_unit());
115            if let Ok(left) = node.reborrow_datamut().left().descend() {
116                Self::update_act(left, &act);
117            }
118            if let Ok(right) = node.reborrow_datamut().right().descend() {
119                Self::update_act(right, &act);
120            }
121        }
122        if node.reborrow().into_data().rev {
123            node.data_mut().rev = false;
124            if let Ok(left) = node.reborrow_datamut().left().descend() {
125                Self::reverse(left);
126            }
127            if let Ok(right) = node.reborrow_datamut().right().descend() {
128                Self::reverse(right);
129            }
130        }
131    }
132
133    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
134        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
135        let mut size = 1;
136        if let Ok(left) = node.reborrow().left().descend() {
137            let data = left.into_data();
138            agg = T::agg_operate(&data.value.agg, &agg);
139            size += data.size;
140        }
141        if let Ok(right) = node.reborrow().right().descend() {
142            let data = right.into_data();
143            agg = T::agg_operate(&agg, &data.value.agg);
144            size += data.size;
145        }
146        let data = node.data_mut();
147        data.value.agg = agg;
148        data.size = size;
149    }
150
151    fn merge(
152        left: Option<ImplicitSplayTreeRoot<T>>,
153        right: Option<ImplicitSplayTreeRoot<T>>,
154    ) -> Option<ImplicitSplayTreeRoot<T>> {
155        splay_operations::merge(left, right)
156    }
157
158    fn split<Seeker>(
159        node: Option<ImplicitSplayTreeRoot<T>>,
160        seeker: Seeker,
161        equal_side: EqualSide,
162    ) -> (
163        Option<ImplicitSplayTreeRoot<T>>,
164        Option<ImplicitSplayTreeRoot<T>>,
165    )
166    where
167        Seeker: BstSeeker<Spec = Self>,
168    {
169        splay_operations::split(node, seeker, equal_side)
170    }
171}
172
173pub struct ImplicitSplayTree<T, A = MemoryPool<ImplicitSplayTreeNode<T>>>
174where
175    T: LazyMapMonoid,
176    A: Allocator<ImplicitSplayTreeNode<T>>,
177{
178    root: Option<ImplicitSplayTreeRoot<T>>,
179    length: usize,
180    allocator: ManuallyDrop<A>,
181    _marker: PhantomData<fn() -> T>,
182}
183
184impl<T, A> Default for ImplicitSplayTree<T, A>
185where
186    T: LazyMapMonoid,
187    A: Allocator<ImplicitSplayTreeNode<T>> + Default,
188{
189    fn default() -> Self {
190        Self {
191            root: None,
192            length: 0,
193            allocator: ManuallyDrop::new(A::default()),
194            _marker: PhantomData,
195        }
196    }
197}
198
199impl<T, A> Drop for ImplicitSplayTree<T, A>
200where
201    T: LazyMapMonoid,
202    A: Allocator<ImplicitSplayTreeNode<T>>,
203{
204    fn drop(&mut self) {
205        unsafe {
206            if let Some(root) = self.root.take() {
207                root.into_dying().drop_all(self.allocator.deref_mut());
208            }
209            ManuallyDrop::drop(&mut self.allocator);
210        }
211    }
212}
213
214impl<T> ImplicitSplayTree<T>
215where
216    T: LazyMapMonoid,
217{
218    pub fn new() -> Self {
219        Self::default()
220    }
221
222    pub fn with_capacity(capacity: usize) -> Self {
223        Self {
224            root: None,
225            length: 0,
226            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
227            _marker: PhantomData,
228        }
229    }
230}
231
232impl<T, A> ImplicitSplayTree<T, A>
233where
234    T: LazyMapMonoid,
235    A: Allocator<ImplicitSplayTreeNode<T>>,
236{
237    fn node(&mut self, key: T::Key) -> ImplicitSplayTreeRoot<T> {
238        BstRoot::from_data(
239            ImplicitSplayTreeData {
240                value: LazyMapElement::from_key(key),
241                size: 1,
242                rev: false,
243            },
244            self.allocator.deref_mut(),
245        )
246    }
247
248    #[inline]
249    fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
250    where
251        Seeker: BstSeeker<Spec = ImplicitSplayTreeSpec<T>>,
252    {
253        let (ordering, root) = splay_operations::splay(self.root.take()?, seeker);
254        self.root = Some(root);
255        Some(ordering)
256    }
257
258    pub fn len(&self) -> usize {
259        self.length
260    }
261
262    pub fn is_empty(&self) -> bool {
263        self.length == 0
264    }
265
266    pub fn update<R>(&mut self, range: R, act: T::Act)
267    where
268        R: RangeBounds<usize>,
269    {
270        let mut split = Split3::seek_by_size(&mut self.root, range);
271        if let Some(root) = split.mid_datamut() {
272            ImplicitSplayTreeSpec::update_act(root, &act);
273        }
274    }

Source

fn reverse(node: BstDataMutRef<'_, Self>)

Examples found in repository ?

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

112    fn top_down(mut node: BstDataMutRef<'_, Self>) {
113        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
114            let act = replace(&mut node.data_mut().value.act, T::act_unit());
115            if let Ok(left) = node.reborrow_datamut().left().descend() {
116                Self::update_act(left, &act);
117            }
118            if let Ok(right) = node.reborrow_datamut().right().descend() {
119                Self::update_act(right, &act);
120            }
121        }
122        if node.reborrow().into_data().rev {
123            node.data_mut().rev = false;
124            if let Ok(left) = node.reborrow_datamut().left().descend() {
125                Self::reverse(left);
126            }
127            if let Ok(right) = node.reborrow_datamut().right().descend() {
128                Self::reverse(right);
129            }
130        }
131    }
132
133    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
134        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
135        let mut size = 1;
136        if let Ok(left) = node.reborrow().left().descend() {
137            let data = left.into_data();
138            agg = T::agg_operate(&data.value.agg, &agg);
139            size += data.size;
140        }
141        if let Ok(right) = node.reborrow().right().descend() {
142            let data = right.into_data();
143            agg = T::agg_operate(&agg, &data.value.agg);
144            size += data.size;
145        }
146        let data = node.data_mut();
147        data.value.agg = agg;
148        data.size = size;
149    }
150
151    fn merge(
152        left: Option<ImplicitSplayTreeRoot<T>>,
153        right: Option<ImplicitSplayTreeRoot<T>>,
154    ) -> Option<ImplicitSplayTreeRoot<T>> {
155        splay_operations::merge(left, right)
156    }
157
158    fn split<Seeker>(
159        node: Option<ImplicitSplayTreeRoot<T>>,
160        seeker: Seeker,
161        equal_side: EqualSide,
162    ) -> (
163        Option<ImplicitSplayTreeRoot<T>>,
164        Option<ImplicitSplayTreeRoot<T>>,
165    )
166    where
167        Seeker: BstSeeker<Spec = Self>,
168    {
169        splay_operations::split(node, seeker, equal_side)
170    }
171}
172
173pub struct ImplicitSplayTree<T, A = MemoryPool<ImplicitSplayTreeNode<T>>>
174where
175    T: LazyMapMonoid,
176    A: Allocator<ImplicitSplayTreeNode<T>>,
177{
178    root: Option<ImplicitSplayTreeRoot<T>>,
179    length: usize,
180    allocator: ManuallyDrop<A>,
181    _marker: PhantomData<fn() -> T>,
182}
183
184impl<T, A> Default for ImplicitSplayTree<T, A>
185where
186    T: LazyMapMonoid,
187    A: Allocator<ImplicitSplayTreeNode<T>> + Default,
188{
189    fn default() -> Self {
190        Self {
191            root: None,
192            length: 0,
193            allocator: ManuallyDrop::new(A::default()),
194            _marker: PhantomData,
195        }
196    }
197}
198
199impl<T, A> Drop for ImplicitSplayTree<T, A>
200where
201    T: LazyMapMonoid,
202    A: Allocator<ImplicitSplayTreeNode<T>>,
203{
204    fn drop(&mut self) {
205        unsafe {
206            if let Some(root) = self.root.take() {
207                root.into_dying().drop_all(self.allocator.deref_mut());
208            }
209            ManuallyDrop::drop(&mut self.allocator);
210        }
211    }
212}
213
214impl<T> ImplicitSplayTree<T>
215where
216    T: LazyMapMonoid,
217{
218    pub fn new() -> Self {
219        Self::default()
220    }
221
222    pub fn with_capacity(capacity: usize) -> Self {
223        Self {
224            root: None,
225            length: 0,
226            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
227            _marker: PhantomData,
228        }
229    }
230}
231
232impl<T, A> ImplicitSplayTree<T, A>
233where
234    T: LazyMapMonoid,
235    A: Allocator<ImplicitSplayTreeNode<T>>,
236{
237    fn node(&mut self, key: T::Key) -> ImplicitSplayTreeRoot<T> {
238        BstRoot::from_data(
239            ImplicitSplayTreeData {
240                value: LazyMapElement::from_key(key),
241                size: 1,
242                rev: false,
243            },
244            self.allocator.deref_mut(),
245        )
246    }
247
248    #[inline]
249    fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
250    where
251        Seeker: BstSeeker<Spec = ImplicitSplayTreeSpec<T>>,
252    {
253        let (ordering, root) = splay_operations::splay(self.root.take()?, seeker);
254        self.root = Some(root);
255        Some(ordering)
256    }
257
258    pub fn len(&self) -> usize {
259        self.length
260    }
261
262    pub fn is_empty(&self) -> bool {
263        self.length == 0
264    }
265
266    pub fn update<R>(&mut self, range: R, act: T::Act)
267    where
268        R: RangeBounds<usize>,
269    {
270        let mut split = Split3::seek_by_size(&mut self.root, range);
271        if let Some(root) = split.mid_datamut() {
272            ImplicitSplayTreeSpec::update_act(root, &act);
273        }
274    }
275
276    pub fn fold<R>(&mut self, range: R) -> T::Agg
277    where
278        R: RangeBounds<usize>,
279    {
280        let split = Split3::seek_by_size(&mut self.root, range);
281        split
282            .mid()
283            .map(|node| node.into_data().value.agg.clone())
284            .unwrap_or_else(T::agg_unit)
285    }
286
287    pub fn reverse<R>(&mut self, range: R)
288    where
289        R: RangeBounds<usize>,
290    {
291        let mut split = Split3::seek_by_size(&mut self.root, range);
292        if let Some(root) = split.mid_datamut() {
293            ImplicitSplayTreeSpec::reverse(root);
294        }
295    }