SplaySpec

competitive::data_structure::splay_tree::node

Trait SplaySpec 

Source 
pub trait SplaySpec: Sized {
    type T;

    // Provided methods
    fn has_bottom_up() -> bool { ... }
    fn top_down(_node: NodeRef<DataMut<'_>, Self>) { ... }
    fn bottom_up(_node: NodeRef<DataMut<'_>, Self>) { ... }
}

Required Associated Types§

Source

type T

Provided Methods§

Source

fn has_bottom_up() -> bool

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 404)
287    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288    where
289        Seeker: SplaySeeker<S = S>,
290    {
291        let mut x = self;
292        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295        let mut left_entry = &mut left_subtree;
296        let mut right_entry = &mut right_subtree;
297        let mut stack = vec![];
298
299        macro_rules! add {
300            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303                *$entry = $node;
304                if S::has_bottom_up() {
305                    stack.push($ptr.node);
306                }
307                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308            };
309        }
310
311        let root_ord = loop {
312            S::top_down(x.borrow_datamut());
313            match seeker.splay_seek(x.reborrow()) {
314                Ordering::Less => {
315                    if let Some(mut y) = x.borrow_mut().take_left() {
316                        S::top_down(y.borrow_datamut());
317                        match seeker.splay_seek(y.reborrow()) {
318                            Ordering::Less => {
319                                if let Some(mut z) = y.borrow_mut().take_left() {
320                                    S::top_down(z.borrow_datamut());
321                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
322                                    S::bottom_up(x.borrow_datamut());
323                                    y.borrow_mut().set_right(Some(x));
324                                    add!(@right Some(y));
325                                    x = z;
326                                } else {
327                                    add!(@right Some(x));
328                                    x = y;
329                                    break Ordering::Less;
330                                }
331                            }
332                            Ordering::Equal => {
333                                add!(@right Some(x));
334                                x = y;
335                                break Ordering::Equal;
336                            }
337                            Ordering::Greater => {
338                                if let Some(mut z) = y.borrow_mut().take_right() {
339                                    S::top_down(z.borrow_datamut());
340                                    add!(@right Some(x));
341                                    add!(@left Some(y));
342                                    x = z;
343                                } else {
344                                    add!(@right Some(x));
345                                    x = y;
346                                    break Ordering::Greater;
347                                }
348                            }
349                        }
350                    } else {
351                        break Ordering::Less;
352                    }
353                }
354                Ordering::Equal => break Ordering::Equal,
355                Ordering::Greater => {
356                    if let Some(mut y) = x.borrow_mut().take_right() {
357                        S::top_down(y.borrow_datamut());
358                        match seeker.splay_seek(y.reborrow()) {
359                            Ordering::Less => {
360                                if let Some(mut z) = y.borrow_mut().take_left() {
361                                    S::top_down(z.borrow_datamut());
362                                    add!(@left Some(x));
363                                    add!(@right Some(y));
364                                    x = z;
365                                } else {
366                                    add!(@left Some(x));
367                                    x = y;
368                                    break Ordering::Less;
369                                }
370                            }
371                            Ordering::Equal => {
372                                add!(@left Some(x));
373                                x = y;
374                                break Ordering::Equal;
375                            }
376                            Ordering::Greater => {
377                                if let Some(mut z) = y.borrow_mut().take_right() {
378                                    S::top_down(z.borrow_datamut());
379                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
380                                    S::bottom_up(x.borrow_datamut());
381                                    y.borrow_mut().set_left(Some(x));
382                                    add!(@left Some(y));
383                                    x = z;
384                                } else {
385                                    add!(@left Some(x));
386                                    x = y;
387                                    break Ordering::Greater;
388                                }
389                            }
390                        }
391                    } else {
392                        break Ordering::Greater;
393                    }
394                }
395            }
396        };
397        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399        unsafe {
400            x.borrow_mut()
401                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402            x.borrow_mut()
403                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404            if S::has_bottom_up() {
405                while let Some(node) = stack.pop() {
406                    S::bottom_up(NodeRef::new_unchecked(node));
407                }
408            }
409        }
410        S::bottom_up(x.borrow_datamut());
411        (root_ord, x)
412    }
Source

fn top_down(_node: NodeRef<DataMut<'_>, Self>)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 312)
287    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288    where
289        Seeker: SplaySeeker<S = S>,
290    {
291        let mut x = self;
292        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295        let mut left_entry = &mut left_subtree;
296        let mut right_entry = &mut right_subtree;
297        let mut stack = vec![];
298
299        macro_rules! add {
300            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303                *$entry = $node;
304                if S::has_bottom_up() {
305                    stack.push($ptr.node);
306                }
307                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308            };
309        }
310
311        let root_ord = loop {
312            S::top_down(x.borrow_datamut());
313            match seeker.splay_seek(x.reborrow()) {
314                Ordering::Less => {
315                    if let Some(mut y) = x.borrow_mut().take_left() {
316                        S::top_down(y.borrow_datamut());
317                        match seeker.splay_seek(y.reborrow()) {
318                            Ordering::Less => {
319                                if let Some(mut z) = y.borrow_mut().take_left() {
320                                    S::top_down(z.borrow_datamut());
321                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
322                                    S::bottom_up(x.borrow_datamut());
323                                    y.borrow_mut().set_right(Some(x));
324                                    add!(@right Some(y));
325                                    x = z;
326                                } else {
327                                    add!(@right Some(x));
328                                    x = y;
329                                    break Ordering::Less;
330                                }
331                            }
332                            Ordering::Equal => {
333                                add!(@right Some(x));
334                                x = y;
335                                break Ordering::Equal;
336                            }
337                            Ordering::Greater => {
338                                if let Some(mut z) = y.borrow_mut().take_right() {
339                                    S::top_down(z.borrow_datamut());
340                                    add!(@right Some(x));
341                                    add!(@left Some(y));
342                                    x = z;
343                                } else {
344                                    add!(@right Some(x));
345                                    x = y;
346                                    break Ordering::Greater;
347                                }
348                            }
349                        }
350                    } else {
351                        break Ordering::Less;
352                    }
353                }
354                Ordering::Equal => break Ordering::Equal,
355                Ordering::Greater => {
356                    if let Some(mut y) = x.borrow_mut().take_right() {
357                        S::top_down(y.borrow_datamut());
358                        match seeker.splay_seek(y.reborrow()) {
359                            Ordering::Less => {
360                                if let Some(mut z) = y.borrow_mut().take_left() {
361                                    S::top_down(z.borrow_datamut());
362                                    add!(@left Some(x));
363                                    add!(@right Some(y));
364                                    x = z;
365                                } else {
366                                    add!(@left Some(x));
367                                    x = y;
368                                    break Ordering::Less;
369                                }
370                            }
371                            Ordering::Equal => {
372                                add!(@left Some(x));
373                                x = y;
374                                break Ordering::Equal;
375                            }
376                            Ordering::Greater => {
377                                if let Some(mut z) = y.borrow_mut().take_right() {
378                                    S::top_down(z.borrow_datamut());
379                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
380                                    S::bottom_up(x.borrow_datamut());
381                                    y.borrow_mut().set_left(Some(x));
382                                    add!(@left Some(y));
383                                    x = z;
384                                } else {
385                                    add!(@left Some(x));
386                                    x = y;
387                                    break Ordering::Greater;
388                                }
389                            }
390                        }
391                    } else {
392                        break Ordering::Greater;
393                    }
394                }
395            }
396        };
397        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399        unsafe {
400            x.borrow_mut()
401                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402            x.borrow_mut()
403                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404            if S::has_bottom_up() {
405                while let Some(node) = stack.pop() {
406                    S::bottom_up(NodeRef::new_unchecked(node));
407                }
408            }
409        }
410        S::bottom_up(x.borrow_datamut());
411        (root_ord, x)
412    }
413    pub fn insert_left(mut self, mut node: Self) -> Self {
414        if let Some(left) = self.borrow_mut().take_left() {
415            node.borrow_mut().set_left(Some(left));
416            S::bottom_up(self.borrow_datamut());
417        };
418        node.borrow_mut().set_right(Some(self));
419        S::bottom_up(node.borrow_datamut());
420        node
421    }
422    pub fn insert_right(mut self, mut node: Self) -> Self {
423        if let Some(right) = self.borrow_mut().take_right() {
424            node.borrow_mut().set_right(Some(right));
425            S::bottom_up(self.borrow_datamut());
426        }
427        node.borrow_mut().set_left(Some(self));
428        S::bottom_up(node.borrow_datamut());
429        node
430    }
431    pub fn insert_first(self, mut node: Self) -> Self {
432        node.borrow_mut().set_right(Some(self));
433        S::bottom_up(node.borrow_datamut());
434        node
435    }
436    pub fn insert_last(self, mut node: Self) -> Self {
437        node.borrow_mut().set_left(Some(self));
438        S::bottom_up(node.borrow_datamut());
439        node
440    }
441    pub fn merge(mut self, mut other: Self) -> Self {
442        if other.reborrow().left().is_none() {
443            S::top_down(other.borrow_datamut());
444            other.borrow_mut().set_left(Some(self));
445            S::bottom_up(other.borrow_datamut());
446            other
447        } else {
448            self = self.splay_by(SeekRight::new()).1;
449            self.borrow_mut().set_right(Some(other));
450            S::bottom_up(self.borrow_datamut());
451            self
452        }
453    }
Source

fn bottom_up(_node: NodeRef<DataMut<'_>, Self>)

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 359)
352    pub fn modify<F>(&mut self, index: usize, f: F)
353    where
354        F: FnOnce(&T::Key) -> T::Key,
355    {
356        self.root.splay_by(SeekBySize::new(index)).unwrap();
357        let data = self.root.root_data_mut().unwrap().data_mut();
358        data.key = f(&data.key);
359        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360    }
More examples
Hide additional examples
crates/competitive/src/data_structure/splay_tree/node.rs (line 322)
287    pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288    where
289        Seeker: SplaySeeker<S = S>,
290    {
291        let mut x = self;
292        // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293        let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294        let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295        let mut left_entry = &mut left_subtree;
296        let mut right_entry = &mut right_subtree;
297        let mut stack = vec![];
298
299        macro_rules! add {
300            (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301            (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302            (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303                *$entry = $node;
304                if S::has_bottom_up() {
305                    stack.push($ptr.node);
306                }
307                $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308            };
309        }
310
311        let root_ord = loop {
312            S::top_down(x.borrow_datamut());
313            match seeker.splay_seek(x.reborrow()) {
314                Ordering::Less => {
315                    if let Some(mut y) = x.borrow_mut().take_left() {
316                        S::top_down(y.borrow_datamut());
317                        match seeker.splay_seek(y.reborrow()) {
318                            Ordering::Less => {
319                                if let Some(mut z) = y.borrow_mut().take_left() {
320                                    S::top_down(z.borrow_datamut());
321                                    x.borrow_mut().set_left(y.borrow_mut().take_right());
322                                    S::bottom_up(x.borrow_datamut());
323                                    y.borrow_mut().set_right(Some(x));
324                                    add!(@right Some(y));
325                                    x = z;
326                                } else {
327                                    add!(@right Some(x));
328                                    x = y;
329                                    break Ordering::Less;
330                                }
331                            }
332                            Ordering::Equal => {
333                                add!(@right Some(x));
334                                x = y;
335                                break Ordering::Equal;
336                            }
337                            Ordering::Greater => {
338                                if let Some(mut z) = y.borrow_mut().take_right() {
339                                    S::top_down(z.borrow_datamut());
340                                    add!(@right Some(x));
341                                    add!(@left Some(y));
342                                    x = z;
343                                } else {
344                                    add!(@right Some(x));
345                                    x = y;
346                                    break Ordering::Greater;
347                                }
348                            }
349                        }
350                    } else {
351                        break Ordering::Less;
352                    }
353                }
354                Ordering::Equal => break Ordering::Equal,
355                Ordering::Greater => {
356                    if let Some(mut y) = x.borrow_mut().take_right() {
357                        S::top_down(y.borrow_datamut());
358                        match seeker.splay_seek(y.reborrow()) {
359                            Ordering::Less => {
360                                if let Some(mut z) = y.borrow_mut().take_left() {
361                                    S::top_down(z.borrow_datamut());
362                                    add!(@left Some(x));
363                                    add!(@right Some(y));
364                                    x = z;
365                                } else {
366                                    add!(@left Some(x));
367                                    x = y;
368                                    break Ordering::Less;
369                                }
370                            }
371                            Ordering::Equal => {
372                                add!(@left Some(x));
373                                x = y;
374                                break Ordering::Equal;
375                            }
376                            Ordering::Greater => {
377                                if let Some(mut z) = y.borrow_mut().take_right() {
378                                    S::top_down(z.borrow_datamut());
379                                    x.borrow_mut().set_right(y.borrow_mut().take_left());
380                                    S::bottom_up(x.borrow_datamut());
381                                    y.borrow_mut().set_left(Some(x));
382                                    add!(@left Some(y));
383                                    x = z;
384                                } else {
385                                    add!(@left Some(x));
386                                    x = y;
387                                    break Ordering::Greater;
388                                }
389                            }
390                        }
391                    } else {
392                        break Ordering::Greater;
393                    }
394                }
395            }
396        };
397        *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398        *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399        unsafe {
400            x.borrow_mut()
401                .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402            x.borrow_mut()
403                .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404            if S::has_bottom_up() {
405                while let Some(node) = stack.pop() {
406                    S::bottom_up(NodeRef::new_unchecked(node));
407                }
408            }
409        }
410        S::bottom_up(x.borrow_datamut());
411        (root_ord, x)
412    }
413    pub fn insert_left(mut self, mut node: Self) -> Self {
414        if let Some(left) = self.borrow_mut().take_left() {
415            node.borrow_mut().set_left(Some(left));
416            S::bottom_up(self.borrow_datamut());
417        };
418        node.borrow_mut().set_right(Some(self));
419        S::bottom_up(node.borrow_datamut());
420        node
421    }
422    pub fn insert_right(mut self, mut node: Self) -> Self {
423        if let Some(right) = self.borrow_mut().take_right() {
424            node.borrow_mut().set_right(Some(right));
425            S::bottom_up(self.borrow_datamut());
426        }
427        node.borrow_mut().set_left(Some(self));
428        S::bottom_up(node.borrow_datamut());
429        node
430    }
431    pub fn insert_first(self, mut node: Self) -> Self {
432        node.borrow_mut().set_right(Some(self));
433        S::bottom_up(node.borrow_datamut());
434        node
435    }
436    pub fn insert_last(self, mut node: Self) -> Self {
437        node.borrow_mut().set_left(Some(self));
438        S::bottom_up(node.borrow_datamut());
439        node
440    }
441    pub fn merge(mut self, mut other: Self) -> Self {
442        if other.reborrow().left().is_none() {
443            S::top_down(other.borrow_datamut());
444            other.borrow_mut().set_left(Some(self));
445            S::bottom_up(other.borrow_datamut());
446            other
447        } else {
448            self = self.splay_by(SeekRight::new()).1;
449            self.borrow_mut().set_right(Some(other));
450            S::bottom_up(self.borrow_datamut());
451            self
452        }
453    }
454}
455
456impl<S> Root<S>
457where
458    S: SplaySpec,
459{
460    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461        Self { root }
462    }
463    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464        unsafe { Self::from_single_nodes_inner(&nodes) }
465    }
466    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467        if nodes.is_empty() {
468            Self::new(None)
469        } else {
470            let m = nodes.len() / 2;
471            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473            let mut node = NodeRef::new(nodes[m].node);
474            node.borrow_mut().set_left(left.root);
475            node.borrow_mut().set_right(right.root);
476            S::bottom_up(node.borrow_datamut());
477            Self::new(Some(node))
478        }
479    }
480    pub fn is_empty(&self) -> bool {
481        self.root.is_none()
482    }
483    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484        Some(self.root.as_ref()?.reborrow())
485    }
486    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487        Some(self.root.as_mut()?.borrow_datamut())
488    }
489    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490    where
491        Seeker: SplaySeeker<S = S>,
492    {
493        let (ord, root) = self.root.take()?.splay_by(seeker);
494        self.root = Some(root);
495        Some(ord)
496    }
497    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498        self.root = Some(match self.root.take() {
499            Some(root) => root.insert_left(node),
500            None => {
501                S::bottom_up(node.borrow_datamut());
502                node
503            }
504        });
505    }
506    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507        self.root = Some(match self.root.take() {
508            Some(root) => root.insert_right(node),
509            None => {
510                S::bottom_up(node.borrow_datamut());
511                node
512            }
513        });
514    }
515    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516        self.root = Some(match self.root.take() {
517            Some(root) => root.insert_first(node),
518            None => {
519                S::bottom_up(node.borrow_datamut());
520                node
521            }
522        });
523    }
524    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525        self.root = Some(match self.root.take() {
526            Some(root) => root.insert_last(node),
527            None => {
528                S::bottom_up(node.borrow_datamut());
529                node
530            }
531        });
532    }
533    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534        let mut root = self.root.take()?;
535        let right = root.borrow_mut().take_right();
536        self.root = root.borrow_mut().take_left();
537        self.append(&mut Self::new(right));
538        Some(root)
539    }
540    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542        let right = root.borrow_mut().take_right();
543        self.root = right;
544        Some(root)
545    }
546    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548        let left = root.borrow_mut().take_left();
549        self.root = left;
550        Some(root)
551    }
552    pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553        let root = self.root.as_mut()?;
554        let left = root.borrow_mut().take_left();
555        S::bottom_up(root.borrow_datamut());
556        left
557    }
558    pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559        let root = self.root.as_mut()?;
560        let right = root.borrow_mut().take_right();
561        S::bottom_up(root.borrow_datamut());
562        right
563    }

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§