Skip to main content

ImplicitTreapSpec

competitive::data_structure::implicit_treap

Struct ImplicitTreapSpec 

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

Fields§

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

Implementations§

Source§

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

Source

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

Examples found in repository?
crates/competitive/src/data_structure/implicit_treap.rs (line 117)
113    fn top_down(mut node: BstDataMutRef<'_, Self>) {
114        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
115            let act = replace(&mut node.data_mut().value.act, T::act_unit());
116            if let Ok(left) = node.reborrow_datamut().left().descend() {
117                Self::update_act(left, &act);
118            }
119            if let Ok(right) = node.reborrow_datamut().right().descend() {
120                Self::update_act(right, &act);
121            }
122        }
123        if node.reborrow().into_data().rev {
124            node.data_mut().rev = false;
125            if let Ok(left) = node.reborrow_datamut().left().descend() {
126                Self::reverse(left);
127            }
128            if let Ok(right) = node.reborrow_datamut().right().descend() {
129                Self::reverse(right);
130            }
131        }
132    }
133
134    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
135        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
136        let mut size = 1;
137        if let Ok(left) = node.reborrow().left().descend() {
138            let data = left.into_data();
139            agg = T::agg_operate(&data.value.agg, &agg);
140            size += data.size;
141        }
142        if let Ok(right) = node.reborrow().right().descend() {
143            let data = right.into_data();
144            agg = T::agg_operate(&agg, &data.value.agg);
145            size += data.size;
146        }
147        let data = node.data_mut();
148        data.value.agg = agg;
149        data.size = size;
150    }
151
152    fn merge(
153        left: Option<ImplicitTreapRoot<T>>,
154        right: Option<ImplicitTreapRoot<T>>,
155    ) -> Option<ImplicitTreapRoot<T>> {
156        match (left, right) {
157            (None, None) => None,
158            (None, Some(node)) | (Some(node), None) => Some(node),
159            (Some(mut left), Some(mut right)) => unsafe {
160                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
161                    Self::top_down(left.borrow_datamut());
162                    let lr = left.borrow_mut().right().take();
163                    let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
164                    left.borrow_mut().right().set(lr);
165                    Self::bottom_up(left.borrow_datamut());
166                    Some(left)
167                } else {
168                    Self::top_down(right.borrow_datamut());
169                    let rl = right.borrow_mut().left().take();
170                    let rl = Self::merge(Some(left), rl).unwrap_unchecked();
171                    right.borrow_mut().left().set(rl);
172                    Self::bottom_up(right.borrow_datamut());
173                    Some(right)
174                }
175            },
176        }
177    }
178
179    fn split<Seeker>(
180        node: Option<ImplicitTreapRoot<T>>,
181        mut seeker: Seeker,
182        equal_side: EqualSide,
183    ) -> (Option<ImplicitTreapRoot<T>>, Option<ImplicitTreapRoot<T>>)
184    where
185        Seeker: BstSeeker<Spec = Self>,
186    {
187        match node {
188            None => (None, None),
189            Some(mut node) => {
190                Self::top_down(node.borrow_datamut());
191                if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
192                    unsafe {
193                        let right = node.borrow_mut().right().take();
194                        let (l, r) = Self::split(right, seeker, equal_side);
195                        if let Some(l) = l {
196                            node.borrow_mut().right().set(l);
197                        }
198                        Self::bottom_up(node.borrow_datamut());
199                        (Some(node), r)
200                    }
201                } else {
202                    unsafe {
203                        let left = node.borrow_mut().left().take();
204                        let (l, r) = Self::split(left, seeker, equal_side);
205                        if let Some(r) = r {
206                            node.borrow_mut().left().set(r);
207                        }
208                        Self::bottom_up(node.borrow_datamut());
209                        (l, Some(node))
210                    }
211                }
212            }
213        }
214    }
215}
216
217pub struct ImplicitTreap<T, A = MemoryPool<ImplicitTreapNode<T>>>
218where
219    T: LazyMapMonoid,
220    A: Allocator<ImplicitTreapNode<T>>,
221{
222    root: Option<ImplicitTreapRoot<T>>,
223    length: usize,
224    rng: Xorshift,
225    allocator: ManuallyDrop<A>,
226    _marker: PhantomData<fn() -> T>,
227}
228
229impl<T, A> Default for ImplicitTreap<T, A>
230where
231    T: LazyMapMonoid,
232    A: Allocator<ImplicitTreapNode<T>> + Default,
233{
234    fn default() -> Self {
235        Self {
236            root: None,
237            length: 0,
238            rng: Xorshift::new(),
239            allocator: ManuallyDrop::new(A::default()),
240            _marker: PhantomData,
241        }
242    }
243}
244
245impl<T, A> Drop for ImplicitTreap<T, A>
246where
247    T: LazyMapMonoid,
248    A: Allocator<ImplicitTreapNode<T>>,
249{
250    fn drop(&mut self) {
251        unsafe {
252            if let Some(root) = self.root.take() {
253                root.into_dying().drop_all(self.allocator.deref_mut());
254            }
255            ManuallyDrop::drop(&mut self.allocator);
256        }
257    }
258}
259
260impl<T> ImplicitTreap<T>
261where
262    T: LazyMapMonoid,
263{
264    pub fn new() -> Self {
265        Self::default()
266    }
267
268    pub fn with_capacity(capacity: usize) -> Self {
269        Self {
270            root: None,
271            length: 0,
272            rng: Xorshift::new(),
273            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
274            _marker: PhantomData,
275        }
276    }
277}
278
279impl<T, A> ImplicitTreap<T, A>
280where
281    T: LazyMapMonoid,
282    A: Allocator<ImplicitTreapNode<T>>,
283{
284    fn node(&mut self, key: T::Key) -> ImplicitTreapRoot<T> {
285        BstRoot::from_data(
286            ImplicitTreapData {
287                priority: self.rng.rand64(),
288                value: LazyMapElement::from_key(key),
289                size: 1,
290                rev: false,
291            },
292            self.allocator.deref_mut(),
293        )
294    }
295
296    fn build<I>(&mut self, iter: I) -> (Option<ImplicitTreapRoot<T>>, usize)
297    where
298        I: IntoIterator<Item = T::Key>,
299    {
300        let mut stack = vec![];
301        let mut len = 0;
302        for key in iter {
303            let mut cur = self.node(key).node;
304            let mut left = None;
305            unsafe {
306                while stack
307                    .last()
308                    .is_some_and(|node: &NonNull<ImplicitTreapNode<T>>| {
309                        node.as_ref().data.priority < cur.as_ref().data.priority
310                    })
311                {
312                    left = stack.pop();
313                }
314                cur.as_mut().child[0] = left;
315                if let Some(parent) = stack.last_mut() {
316                    parent.as_mut().child[1] = Some(cur);
317                }
318            }
319            stack.push(cur);
320            len += 1;
321        }
322        let root = stack.first().copied().map(BstRoot::new);
323        if let Some(mut root) = root {
324            Self::build_bottom_up(root.borrow_datamut());
325            (Some(root), len)
326        } else {
327            (None, len)
328        }
329    }
330
331    fn build_bottom_up(mut node: BstDataMutRef<'_, ImplicitTreapSpec<T>>) {
332        if let Ok(left) = node.reborrow_datamut().left().descend() {
333            Self::build_bottom_up(left);
334        }
335        if let Ok(right) = node.reborrow_datamut().right().descend() {
336            Self::build_bottom_up(right);
337        }
338        ImplicitTreapSpec::<T>::bottom_up(node);
339    }
340
341    pub fn len(&self) -> usize {
342        self.length
343    }
344
345    pub fn is_empty(&self) -> bool {
346        self.length == 0
347    }
348
349    pub fn update<R>(&mut self, range: R, x: T::Act)
350    where
351        R: RangeBounds<usize>,
352    {
353        let mut split = Split3::seek_by_size(&mut self.root, range);
354        if let Some(root) = split.mid_datamut() {
355            ImplicitTreapSpec::<T>::update_act(root, &x);
356        }
357    }
Source

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

Examples found in repository?
crates/competitive/src/data_structure/implicit_treap.rs (line 126)
113    fn top_down(mut node: BstDataMutRef<'_, Self>) {
114        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
115            let act = replace(&mut node.data_mut().value.act, T::act_unit());
116            if let Ok(left) = node.reborrow_datamut().left().descend() {
117                Self::update_act(left, &act);
118            }
119            if let Ok(right) = node.reborrow_datamut().right().descend() {
120                Self::update_act(right, &act);
121            }
122        }
123        if node.reborrow().into_data().rev {
124            node.data_mut().rev = false;
125            if let Ok(left) = node.reborrow_datamut().left().descend() {
126                Self::reverse(left);
127            }
128            if let Ok(right) = node.reborrow_datamut().right().descend() {
129                Self::reverse(right);
130            }
131        }
132    }
133
134    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
135        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
136        let mut size = 1;
137        if let Ok(left) = node.reborrow().left().descend() {
138            let data = left.into_data();
139            agg = T::agg_operate(&data.value.agg, &agg);
140            size += data.size;
141        }
142        if let Ok(right) = node.reborrow().right().descend() {
143            let data = right.into_data();
144            agg = T::agg_operate(&agg, &data.value.agg);
145            size += data.size;
146        }
147        let data = node.data_mut();
148        data.value.agg = agg;
149        data.size = size;
150    }
151
152    fn merge(
153        left: Option<ImplicitTreapRoot<T>>,
154        right: Option<ImplicitTreapRoot<T>>,
155    ) -> Option<ImplicitTreapRoot<T>> {
156        match (left, right) {
157            (None, None) => None,
158            (None, Some(node)) | (Some(node), None) => Some(node),
159            (Some(mut left), Some(mut right)) => unsafe {
160                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
161                    Self::top_down(left.borrow_datamut());
162                    let lr = left.borrow_mut().right().take();
163                    let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
164                    left.borrow_mut().right().set(lr);
165                    Self::bottom_up(left.borrow_datamut());
166                    Some(left)
167                } else {
168                    Self::top_down(right.borrow_datamut());
169                    let rl = right.borrow_mut().left().take();
170                    let rl = Self::merge(Some(left), rl).unwrap_unchecked();
171                    right.borrow_mut().left().set(rl);
172                    Self::bottom_up(right.borrow_datamut());
173                    Some(right)
174                }
175            },
176        }
177    }
178
179    fn split<Seeker>(
180        node: Option<ImplicitTreapRoot<T>>,
181        mut seeker: Seeker,
182        equal_side: EqualSide,
183    ) -> (Option<ImplicitTreapRoot<T>>, Option<ImplicitTreapRoot<T>>)
184    where
185        Seeker: BstSeeker<Spec = Self>,
186    {
187        match node {
188            None => (None, None),
189            Some(mut node) => {
190                Self::top_down(node.borrow_datamut());
191                if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
192                    unsafe {
193                        let right = node.borrow_mut().right().take();
194                        let (l, r) = Self::split(right, seeker, equal_side);
195                        if let Some(l) = l {
196                            node.borrow_mut().right().set(l);
197                        }
198                        Self::bottom_up(node.borrow_datamut());
199                        (Some(node), r)
200                    }
201                } else {
202                    unsafe {
203                        let left = node.borrow_mut().left().take();
204                        let (l, r) = Self::split(left, seeker, equal_side);
205                        if let Some(r) = r {
206                            node.borrow_mut().left().set(r);
207                        }
208                        Self::bottom_up(node.borrow_datamut());
209                        (l, Some(node))
210                    }
211                }
212            }
213        }
214    }
215}
216
217pub struct ImplicitTreap<T, A = MemoryPool<ImplicitTreapNode<T>>>
218where
219    T: LazyMapMonoid,
220    A: Allocator<ImplicitTreapNode<T>>,
221{
222    root: Option<ImplicitTreapRoot<T>>,
223    length: usize,
224    rng: Xorshift,
225    allocator: ManuallyDrop<A>,
226    _marker: PhantomData<fn() -> T>,
227}
228
229impl<T, A> Default for ImplicitTreap<T, A>
230where
231    T: LazyMapMonoid,
232    A: Allocator<ImplicitTreapNode<T>> + Default,
233{
234    fn default() -> Self {
235        Self {
236            root: None,
237            length: 0,
238            rng: Xorshift::new(),
239            allocator: ManuallyDrop::new(A::default()),
240            _marker: PhantomData,
241        }
242    }
243}
244
245impl<T, A> Drop for ImplicitTreap<T, A>
246where
247    T: LazyMapMonoid,
248    A: Allocator<ImplicitTreapNode<T>>,
249{
250    fn drop(&mut self) {
251        unsafe {
252            if let Some(root) = self.root.take() {
253                root.into_dying().drop_all(self.allocator.deref_mut());
254            }
255            ManuallyDrop::drop(&mut self.allocator);
256        }
257    }
258}
259
260impl<T> ImplicitTreap<T>
261where
262    T: LazyMapMonoid,
263{
264    pub fn new() -> Self {
265        Self::default()
266    }
267
268    pub fn with_capacity(capacity: usize) -> Self {
269        Self {
270            root: None,
271            length: 0,
272            rng: Xorshift::new(),
273            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
274            _marker: PhantomData,
275        }
276    }
277}
278
279impl<T, A> ImplicitTreap<T, A>
280where
281    T: LazyMapMonoid,
282    A: Allocator<ImplicitTreapNode<T>>,
283{
284    fn node(&mut self, key: T::Key) -> ImplicitTreapRoot<T> {
285        BstRoot::from_data(
286            ImplicitTreapData {
287                priority: self.rng.rand64(),
288                value: LazyMapElement::from_key(key),
289                size: 1,
290                rev: false,
291            },
292            self.allocator.deref_mut(),
293        )
294    }
295
296    fn build<I>(&mut self, iter: I) -> (Option<ImplicitTreapRoot<T>>, usize)
297    where
298        I: IntoIterator<Item = T::Key>,
299    {
300        let mut stack = vec![];
301        let mut len = 0;
302        for key in iter {
303            let mut cur = self.node(key).node;
304            let mut left = None;
305            unsafe {
306                while stack
307                    .last()
308                    .is_some_and(|node: &NonNull<ImplicitTreapNode<T>>| {
309                        node.as_ref().data.priority < cur.as_ref().data.priority
310                    })
311                {
312                    left = stack.pop();
313                }
314                cur.as_mut().child[0] = left;
315                if let Some(parent) = stack.last_mut() {
316                    parent.as_mut().child[1] = Some(cur);
317                }
318            }
319            stack.push(cur);
320            len += 1;
321        }
322        let root = stack.first().copied().map(BstRoot::new);
323        if let Some(mut root) = root {
324            Self::build_bottom_up(root.borrow_datamut());
325            (Some(root), len)
326        } else {
327            (None, len)
328        }
329    }
330
331    fn build_bottom_up(mut node: BstDataMutRef<'_, ImplicitTreapSpec<T>>) {
332        if let Ok(left) = node.reborrow_datamut().left().descend() {
333            Self::build_bottom_up(left);
334        }
335        if let Ok(right) = node.reborrow_datamut().right().descend() {
336            Self::build_bottom_up(right);
337        }
338        ImplicitTreapSpec::<T>::bottom_up(node);
339    }
340
341    pub fn len(&self) -> usize {
342        self.length
343    }
344
345    pub fn is_empty(&self) -> bool {
346        self.length == 0
347    }
348
349    pub fn update<R>(&mut self, range: R, x: T::Act)
350    where
351        R: RangeBounds<usize>,
352    {
353        let mut split = Split3::seek_by_size(&mut self.root, range);
354        if let Some(root) = split.mid_datamut() {
355            ImplicitTreapSpec::<T>::update_act(root, &x);
356        }
357    }
358
359    pub fn fold<R>(&mut self, range: R) -> T::Agg
360    where
361        R: RangeBounds<usize>,
362    {
363        let split = Split3::seek_by_size(&mut self.root, range);
364        split
365            .mid()
366            .map(|node| node.into_data().value.agg.clone())
367            .unwrap_or_else(T::agg_unit)
368    }
369
370    pub fn reverse<R>(&mut self, range: R)
371    where
372        R: RangeBounds<usize>,
373    {
374        let mut split = Split3::seek_by_size(&mut self.root, range);
375        if let Some(root) = split.mid_datamut() {
376            ImplicitTreapSpec::<T>::reverse(root);
377        }
378    }

Trait Implementations§

Auto Trait Implementations§

§

impl<T> Freeze for ImplicitTreapSpec<T>
where PhantomData<fn() -> T>: Freeze,

§

impl<T> RefUnwindSafe for ImplicitTreapSpec<T>
where PhantomData<fn() -> T>: RefUnwindSafe,

§

impl<T> Send for ImplicitTreapSpec<T>
where PhantomData<fn() -> T>: Send,

§

impl<T> Sync for ImplicitTreapSpec<T>
where PhantomData<fn() -> T>: Sync,

§

impl<T> Unpin for ImplicitTreapSpec<T>
where PhantomData<fn() -> T>: Unpin,

§

impl<T> UnsafeUnpin for ImplicitTreapSpec<T>
where PhantomData<fn() -> T>: UnsafeUnpin,

§

impl<T> UnwindSafe for ImplicitTreapSpec<T>
where PhantomData<fn() -> T>: UnwindSafe,

Blanket Implementations§

Source§

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

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

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

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

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

Source§

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

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

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

Source§

fn into(self) -> U

Calls U::from(self).

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

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

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

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

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

Performs the conversion.
Source§

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

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.