Struct SplayMap 

pub struct SplayMap<K, V, A = MemoryPool<Node<((K, V), usize)>>>
where
    A: Allocator<Node<((K, V), usize)>>,
{
    root: Root<SizedSplay<(K, V)>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

Fields

root: Root<SizedSplay<(K, V)>>

length: usize

alloc: ManuallyDrop<A>

Implementations

impl<K, V> SplayMap<K, V>

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

impl<K, V, A> SplayMap<K, V, A>

where A: Allocator<Node<((K, V), usize)>>,

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

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

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/sized_map.rs (line 168)

    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
        self.root.splay_by(SeekBySize::new(index))
    }
    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ord = self.splay_by_key(&key);
        self.length += (ord != Some(Ordering::Equal)) as usize;
        match ord {
            Some(Ordering::Equal) => {
                return Some(replace(
                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
                    value,
                ));
            }
            Some(Ordering::Less) => unsafe {
                self.root.insert_left(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
            _ => unsafe {
                self.root.insert_right(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
        }
        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;
        }
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
    }

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/sized_map.rs (line 154)

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

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

Examples found in repository

crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 183)

    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ord = self.splay_by_key(&key);
        self.length += (ord != Some(Ordering::Equal)) as usize;
        match ord {
            Some(Ordering::Equal) => {
                return Some(replace(
                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
                    value,
                ));
            }
            Some(Ordering::Less) => unsafe {
                self.root.insert_left(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
            _ => unsafe {
                self.root.insert_right(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
        }
        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;
        }
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
    }
    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
    }

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)>

pub fn len(&self) -> usize

Examples found in repository

crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 242)

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

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 SplayMap<K, V, A>

where K: Debug, V: Debug, A: Allocator<Node<((K, V), usize)>>,

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

Formats the value using the given formatter.

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

where A: Allocator<Node<((K, V), usize)>> + Default,

fn default() -> Self

Returns the “default value” for a type.

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

where A: Allocator<Node<((K, V), usize)>>,

fn drop(&mut self)

Executes the destructor for this type.