Struct SplayTree 

pub struct SplayTree<K, V, A = MemoryPool<BstNode<SplayTreeData<K, V>>>>
where
    A: Allocator<BstNode<SplayTreeData<K, V>>>,
{
    root: Option<BstRoot<SplayTreeSpec<K, V>>>,
    length: usize,
    allocator: ManuallyDrop<A>,
}

Fields

root: Option<BstRoot<SplayTreeSpec<K, V>>>

length: usize

allocator: ManuallyDrop<A>

Implementations

impl<K, V> SplayTree<K, V>

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

impl<K, V, A> SplayTree<K, V, A>

where A: Allocator<BstNode<SplayTreeData<K, V>>>,

fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>

where Seeker: BstSeeker<Spec = SplayTreeSpec<K, V>>,

Examples found in repository

crates/competitive/src/data_structure/splay_tree.rs (line 197)

    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.splay(SeekByKey::new(key))
    }

    fn splay_by_size(&mut self, index: usize) -> Option<Ordering> {
        self.splay(SeekBySize::new(index))
    }

fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>

where K: Borrow<Q>, Q: Ord + ?Sized,

Examples found in repository

crates/competitive/src/data_structure/splay_tree.rs (line 217)

    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        matches!(self.splay_by_key(key)?, Ordering::Equal).then(|| {
            let data = self.root.as_ref().unwrap().reborrow().into_data();
            (&data.key, &data.value)
        })
    }

    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_by_size(index);
        let data = self.root.as_ref()?.reborrow().into_data();
        Some((&data.key, &data.value))
    }

    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ordering = self.splay_by_key(&key);
        if matches!(ordering, Some(Ordering::Equal)) {
            return Some(replace(
                &mut self
                    .root
                    .as_mut()
                    .unwrap()
                    .borrow_datamut()
                    .data_mut()
                    .value,
                value,
            ));
        }
        let mut node = BstRoot::from_data(
            SplayTreeData {
                key,
                value,
                size: 1,
            },
            self.allocator.deref_mut(),
        );
        if let Some(mut root) = self.root.take() {
            match ordering.unwrap() {
                Ordering::Greater => {
                    let left = unsafe { root.borrow_mut().left_mut().take() };
                    if let Some(left) = left {
                        unsafe { node.borrow_mut().left_mut().set(left) };
                    }
                    SplayTreeSpec::bottom_up(root.borrow_datamut());
                    unsafe { node.borrow_mut().right_mut().set(root) };
                }
                Ordering::Less => {
                    let right = unsafe { root.borrow_mut().right_mut().take() };
                    if let Some(right) = right {
                        unsafe { node.borrow_mut().right_mut().set(right) };
                    }
                    SplayTreeSpec::bottom_up(root.borrow_datamut());
                    unsafe { node.borrow_mut().left_mut().set(root) };
                }
                Ordering::Equal => unreachable!(),
            }
            SplayTreeSpec::bottom_up(node.borrow_datamut());
        }
        self.root = Some(node);
        self.length += 1;
        None
    }

    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        Some(self.remove_root().1)
    }

fn splay_by_size(&mut self, index: usize) -> Option<Ordering>

Examples found in repository

crates/competitive/src/data_structure/splay_tree.rs (line 227)

    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_by_size(index);
        let data = self.root.as_ref()?.reborrow().into_data();
        Some((&data.key, &data.value))
    }

    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ordering = self.splay_by_key(&key);
        if matches!(ordering, Some(Ordering::Equal)) {
            return Some(replace(
                &mut self
                    .root
                    .as_mut()
                    .unwrap()
                    .borrow_datamut()
                    .data_mut()
                    .value,
                value,
            ));
        }
        let mut node = BstRoot::from_data(
            SplayTreeData {
                key,
                value,
                size: 1,
            },
            self.allocator.deref_mut(),
        );
        if let Some(mut root) = self.root.take() {
            match ordering.unwrap() {
                Ordering::Greater => {
                    let left = unsafe { root.borrow_mut().left_mut().take() };
                    if let Some(left) = left {
                        unsafe { node.borrow_mut().left_mut().set(left) };
                    }
                    SplayTreeSpec::bottom_up(root.borrow_datamut());
                    unsafe { node.borrow_mut().right_mut().set(root) };
                }
                Ordering::Less => {
                    let right = unsafe { root.borrow_mut().right_mut().take() };
                    if let Some(right) = right {
                        unsafe { node.borrow_mut().right_mut().set(right) };
                    }
                    SplayTreeSpec::bottom_up(root.borrow_datamut());
                    unsafe { node.borrow_mut().left_mut().set(root) };
                }
                Ordering::Equal => unreachable!(),
            }
            SplayTreeSpec::bottom_up(node.borrow_datamut());
        }
        self.root = Some(node);
        self.length += 1;
        None
    }

    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        Some(self.remove_root().1)
    }

    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
        if index >= self.length {
            return None;
        }
        self.splay_by_size(index);
        Some(self.remove_root())
    }

pub fn get<Q>(&mut self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: Ord + ?Sized,

pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>

where K: Borrow<Q>, Q: Ord + ?Sized,

Examples found in repository

crates/competitive/src/data_structure/splay_tree.rs (line 209)

    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.get_key_value(key).map(|(_, value)| value)
    }

pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)>

pub fn insert(&mut self, key: K, value: V) -> Option<V>

where K: Ord,

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Ord + ?Sized,

pub fn remove_at(&mut self, index: usize) -> Option<(K, V)>

fn remove_root(&mut self) -> (K, V)

Examples found in repository

crates/competitive/src/data_structure/splay_tree.rs (line 292)

    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        Some(self.remove_root().1)
    }

    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
        if index >= self.length {
            return None;
        }
        self.splay_by_size(index);
        Some(self.remove_root())
    }

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn iter(&mut self) -> Iter<'_, K, V>

pub fn range<Q, R>(&mut self, range: R) -> Iter<'_, K, V>

where K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>,

pub fn range_at<R>(&mut self, range: R) -> Iter<'_, K, V>

where R: RangeBounds<usize>,

Trait Implementations

impl<K, V, A> Debug for SplayTree<K, V, A>

where K: Debug, V: Debug, A: Allocator<BstNode<SplayTreeData<K, V>>>,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V, A> Default for SplayTree<K, V, A>

where A: Allocator<BstNode<SplayTreeData<K, V>>> + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, A> Drop for SplayTree<K, V, A>

where A: Allocator<BstNode<SplayTreeData<K, V>>>,

fn drop(&mut self)

Executes the destructor for this type.

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.