competitive::data_structure::splay_tree::sequence

Struct LazyAggSplay

Source 
pub struct LazyAggSplay<T> { /* private fields */ }

Implementations§

Source§

impl<T> LazyAggSplay<T>
where T: MonoidAction,

Source

pub fn update_lazy(node: NodeRef<DataMut<'_>, Self>, lazy: &T::Act)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 67)
64    fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
65        let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
66        if let Some(left) = node.left() {
67            Self::update_lazy(left, &lazy);
68        }
69        if let Some(right) = node.right() {
70            Self::update_lazy(right, &lazy);
71        }
72        if replace(&mut node.data_mut().rev, false) {
73            if let Some(left) = node.left() {
74                Self::reverse(left);
75            }
76            if let Some(right) = node.right() {
77                Self::reverse(right);
78            }
79        }
80        node
81    }
82    fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
83        let mut agg = T::single_agg(&node.data().key);
84        let mut size = 1;
85        if let Some(left) = node.left() {
86            let data = left.data();
87            agg = T::agg_operate(&data.agg, &agg);
88            // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
89            size += data.size;
90        }
91        if let Some(right) = node.right() {
92            let data = right.data();
93            agg = T::agg_operate(&agg, &data.agg);
94            size += data.size;
95        }
96        let data = node.data_mut();
97        data.agg = agg;
98        data.size = size;
99        node
100    }
101}
102impl<T> SplaySpec for LazyAggSplay<T>
103where
104    T: MonoidAction,
105{
106    type T = LazyAggElement<T>;
107    fn has_bottom_up() -> bool {
108        true
109    }
110    fn top_down(node: NodeRef<marker::DataMut<'_>, Self>) {
111        Self::propagate(node);
112    }
113    fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
114        Self::recalc(node);
115    }
116}
117
118struct SeekBySize<T> {
119    index: usize,
120    _marker: PhantomData<fn() -> T>,
121}
122impl<T> SeekBySize<T> {
123    fn new(index: usize) -> Self {
124        Self {
125            index,
126            _marker: PhantomData,
127        }
128    }
129}
130impl<T> SplaySeeker for SeekBySize<T>
131where
132    T: MonoidAction,
133{
134    type S = LazyAggSplay<T>;
135    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
136        let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
137        let ord = self.index.cmp(&lsize);
138        if matches!(ord, Ordering::Greater) {
139            self.index -= lsize + 1;
140        }
141        ord
142    }
143}
144
145struct SeekByAccCond<F, T>
146where
147    T: MonoidAction,
148{
149    acc: T::Agg,
150    f: F,
151    _marker: PhantomData<fn() -> T>,
152}
153impl<F, T> SeekByAccCond<F, T>
154where
155    T: MonoidAction,
156{
157    fn new(f: F) -> Self {
158        Self {
159            acc: T::agg_unit(),
160            f,
161            _marker: PhantomData,
162        }
163    }
164}
165impl<F, T> SplaySeeker for SeekByAccCond<F, T>
166where
167    F: FnMut(&T::Agg) -> bool,
168    T: MonoidAction,
169{
170    type S = LazyAggSplay<T>;
171    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
172        if let Some(lagg) = node.left().map(|l| &l.data().agg) {
173            let nacc = T::agg_operate(&self.acc, lagg);
174            if (self.f)(&nacc) {
175                return Ordering::Less;
176            }
177            self.acc = nacc;
178        };
179        self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
180        if (self.f)(&self.acc) {
181            Ordering::Equal
182        } else {
183            Ordering::Greater
184        }
185    }
186}
187
188struct SeekByRaccCond<F, T>
189where
190    T: MonoidAction,
191{
192    acc: T::Agg,
193    f: F,
194    _marker: PhantomData<fn() -> T>,
195}
196impl<F, T> SeekByRaccCond<F, T>
197where
198    T: MonoidAction,
199{
200    fn new(f: F) -> Self {
201        Self {
202            acc: T::agg_unit(),
203            f,
204            _marker: PhantomData,
205        }
206    }
207}
208impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
209where
210    F: FnMut(&T::Agg) -> bool,
211    T: MonoidAction,
212{
213    type S = LazyAggSplay<T>;
214    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
215        if let Some(lagg) = node.right().map(|r| &r.data().agg) {
216            let nacc = T::agg_operate(lagg, &self.acc);
217            if (self.f)(&nacc) {
218                return Ordering::Greater;
219            }
220            self.acc = nacc;
221        };
222        self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
223        if (self.f)(&self.acc) {
224            Ordering::Equal
225        } else {
226            Ordering::Less
227        }
228    }
229}
230
231pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
232where
233    T: MonoidAction,
234    A: Allocator<Node<LazyAggElement<T>>>,
235{
236    root: Root<LazyAggSplay<T>>,
237    length: usize,
238    alloc: ManuallyDrop<A>,
239}
240
241impl<T, A> Debug for SplaySequence<T, A>
242where
243    T: MonoidAction,
244    T::Key: Debug,
245    T::Agg: Debug,
246    T::Act: Debug,
247    A: Allocator<Node<LazyAggElement<T>>>,
248{
249    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
250        f.debug_struct("SplayMap")
251            .field("root", &self.root)
252            .field("length", &self.length)
253            .finish()
254    }
255}
256
257impl<T, A> Drop for SplaySequence<T, A>
258where
259    T: MonoidAction,
260    A: Allocator<Node<LazyAggElement<T>>>,
261{
262    fn drop(&mut self) {
263        unsafe {
264            while let Some(node) = self.root.take_first() {
265                self.alloc.deallocate(node.into_dying().into_inner());
266            }
267            ManuallyDrop::drop(&mut self.alloc);
268        }
269    }
270}
271
272impl<T, A> Default for SplaySequence<T, A>
273where
274    T: MonoidAction,
275    A: Allocator<Node<LazyAggElement<T>>> + Default,
276{
277    fn default() -> Self {
278        Self {
279            root: Root::default(),
280            length: 0,
281            alloc: Default::default(),
282        }
283    }
284}
285
286impl<T> SplaySequence<T>
287where
288    T: MonoidAction,
289{
290    pub fn new() -> Self {
291        Default::default()
292    }
293    pub fn with_capacity(capacity: usize) -> Self {
294        Self {
295            root: Root::default(),
296            length: 0,
297            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
298        }
299    }
300    pub fn len(&self) -> usize {
301        self.length
302    }
303    pub fn is_empty(&self) -> bool {
304        self.length == 0
305    }
306}
307impl<T, A> SplaySequence<T, A>
308where
309    T: MonoidAction,
310    A: Allocator<Node<LazyAggElement<T>>>,
311{
312    fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
313    where
314        R: RangeBounds<usize>,
315    {
316        let start = match range.start_bound() {
317            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
318            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
319            Bound::Unbounded => Bound::Unbounded,
320        };
321        let end = match range.end_bound() {
322            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
323            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
324            Bound::Unbounded => Bound::Unbounded,
325        };
326        self.root.range(start, end)
327    }
328    pub fn update<R>(&mut self, range: R, x: T::Act)
329    where
330        R: RangeBounds<usize>,
331    {
332        if let Some(root) = self.range(range).root_mut().root_data_mut() {
333            LazyAggSplay::<T>::update_lazy(root, &x);
334        }
335    }
Source

pub fn reverse(node: NodeRef<DataMut<'_>, Self>)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 74)
64    fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
65        let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
66        if let Some(left) = node.left() {
67            Self::update_lazy(left, &lazy);
68        }
69        if let Some(right) = node.right() {
70            Self::update_lazy(right, &lazy);
71        }
72        if replace(&mut node.data_mut().rev, false) {
73            if let Some(left) = node.left() {
74                Self::reverse(left);
75            }
76            if let Some(right) = node.right() {
77                Self::reverse(right);
78            }
79        }
80        node
81    }
82    fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
83        let mut agg = T::single_agg(&node.data().key);
84        let mut size = 1;
85        if let Some(left) = node.left() {
86            let data = left.data();
87            agg = T::agg_operate(&data.agg, &agg);
88            // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
89            size += data.size;
90        }
91        if let Some(right) = node.right() {
92            let data = right.data();
93            agg = T::agg_operate(&agg, &data.agg);
94            size += data.size;
95        }
96        let data = node.data_mut();
97        data.agg = agg;
98        data.size = size;
99        node
100    }
101}
102impl<T> SplaySpec for LazyAggSplay<T>
103where
104    T: MonoidAction,
105{
106    type T = LazyAggElement<T>;
107    fn has_bottom_up() -> bool {
108        true
109    }
110    fn top_down(node: NodeRef<marker::DataMut<'_>, Self>) {
111        Self::propagate(node);
112    }
113    fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
114        Self::recalc(node);
115    }
116}
117
118struct SeekBySize<T> {
119    index: usize,
120    _marker: PhantomData<fn() -> T>,
121}
122impl<T> SeekBySize<T> {
123    fn new(index: usize) -> Self {
124        Self {
125            index,
126            _marker: PhantomData,
127        }
128    }
129}
130impl<T> SplaySeeker for SeekBySize<T>
131where
132    T: MonoidAction,
133{
134    type S = LazyAggSplay<T>;
135    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
136        let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
137        let ord = self.index.cmp(&lsize);
138        if matches!(ord, Ordering::Greater) {
139            self.index -= lsize + 1;
140        }
141        ord
142    }
143}
144
145struct SeekByAccCond<F, T>
146where
147    T: MonoidAction,
148{
149    acc: T::Agg,
150    f: F,
151    _marker: PhantomData<fn() -> T>,
152}
153impl<F, T> SeekByAccCond<F, T>
154where
155    T: MonoidAction,
156{
157    fn new(f: F) -> Self {
158        Self {
159            acc: T::agg_unit(),
160            f,
161            _marker: PhantomData,
162        }
163    }
164}
165impl<F, T> SplaySeeker for SeekByAccCond<F, T>
166where
167    F: FnMut(&T::Agg) -> bool,
168    T: MonoidAction,
169{
170    type S = LazyAggSplay<T>;
171    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
172        if let Some(lagg) = node.left().map(|l| &l.data().agg) {
173            let nacc = T::agg_operate(&self.acc, lagg);
174            if (self.f)(&nacc) {
175                return Ordering::Less;
176            }
177            self.acc = nacc;
178        };
179        self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
180        if (self.f)(&self.acc) {
181            Ordering::Equal
182        } else {
183            Ordering::Greater
184        }
185    }
186}
187
188struct SeekByRaccCond<F, T>
189where
190    T: MonoidAction,
191{
192    acc: T::Agg,
193    f: F,
194    _marker: PhantomData<fn() -> T>,
195}
196impl<F, T> SeekByRaccCond<F, T>
197where
198    T: MonoidAction,
199{
200    fn new(f: F) -> Self {
201        Self {
202            acc: T::agg_unit(),
203            f,
204            _marker: PhantomData,
205        }
206    }
207}
208impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
209where
210    F: FnMut(&T::Agg) -> bool,
211    T: MonoidAction,
212{
213    type S = LazyAggSplay<T>;
214    fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
215        if let Some(lagg) = node.right().map(|r| &r.data().agg) {
216            let nacc = T::agg_operate(lagg, &self.acc);
217            if (self.f)(&nacc) {
218                return Ordering::Greater;
219            }
220            self.acc = nacc;
221        };
222        self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
223        if (self.f)(&self.acc) {
224            Ordering::Equal
225        } else {
226            Ordering::Less
227        }
228    }
229}
230
231pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
232where
233    T: MonoidAction,
234    A: Allocator<Node<LazyAggElement<T>>>,
235{
236    root: Root<LazyAggSplay<T>>,
237    length: usize,
238    alloc: ManuallyDrop<A>,
239}
240
241impl<T, A> Debug for SplaySequence<T, A>
242where
243    T: MonoidAction,
244    T::Key: Debug,
245    T::Agg: Debug,
246    T::Act: Debug,
247    A: Allocator<Node<LazyAggElement<T>>>,
248{
249    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
250        f.debug_struct("SplayMap")
251            .field("root", &self.root)
252            .field("length", &self.length)
253            .finish()
254    }
255}
256
257impl<T, A> Drop for SplaySequence<T, A>
258where
259    T: MonoidAction,
260    A: Allocator<Node<LazyAggElement<T>>>,
261{
262    fn drop(&mut self) {
263        unsafe {
264            while let Some(node) = self.root.take_first() {
265                self.alloc.deallocate(node.into_dying().into_inner());
266            }
267            ManuallyDrop::drop(&mut self.alloc);
268        }
269    }
270}
271
272impl<T, A> Default for SplaySequence<T, A>
273where
274    T: MonoidAction,
275    A: Allocator<Node<LazyAggElement<T>>> + Default,
276{
277    fn default() -> Self {
278        Self {
279            root: Root::default(),
280            length: 0,
281            alloc: Default::default(),
282        }
283    }
284}
285
286impl<T> SplaySequence<T>
287where
288    T: MonoidAction,
289{
290    pub fn new() -> Self {
291        Default::default()
292    }
293    pub fn with_capacity(capacity: usize) -> Self {
294        Self {
295            root: Root::default(),
296            length: 0,
297            alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
298        }
299    }
300    pub fn len(&self) -> usize {
301        self.length
302    }
303    pub fn is_empty(&self) -> bool {
304        self.length == 0
305    }
306}
307impl<T, A> SplaySequence<T, A>
308where
309    T: MonoidAction,
310    A: Allocator<Node<LazyAggElement<T>>>,
311{
312    fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
313    where
314        R: RangeBounds<usize>,
315    {
316        let start = match range.start_bound() {
317            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
318            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
319            Bound::Unbounded => Bound::Unbounded,
320        };
321        let end = match range.end_bound() {
322            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
323            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
324            Bound::Unbounded => Bound::Unbounded,
325        };
326        self.root.range(start, end)
327    }
328    pub fn update<R>(&mut self, range: R, x: T::Act)
329    where
330        R: RangeBounds<usize>,
331    {
332        if let Some(root) = self.range(range).root_mut().root_data_mut() {
333            LazyAggSplay::<T>::update_lazy(root, &x);
334        }
335    }
336    pub fn fold<R>(&mut self, range: R) -> T::Agg
337    where
338        R: RangeBounds<usize>,
339    {
340        if let Some(root) = self.range(range).root().root() {
341            root.data().agg.clone()
342        } else {
343            T::agg_unit()
344        }
345    }
346    pub fn reverse<R>(&mut self, range: R)
347    where
348        R: RangeBounds<usize>,
349    {
350        if let Some(root) = self.range(range).root_mut().root_data_mut() {
351            LazyAggSplay::<T>::reverse(root);
352        }
353    }

Trait Implementations§

Auto Trait Implementations§

§

impl<T> Freeze for LazyAggSplay<T>

§

impl<T> RefUnwindSafe for LazyAggSplay<T>

§

impl<T> Send for LazyAggSplay<T>

§

impl<T> Sync for LazyAggSplay<T>

§

impl<T> Unpin for LazyAggSplay<T>

§

impl<T> UnwindSafe for LazyAggSplay<T>

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, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

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

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

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.