orium / rpds

Rust persistent data structures
Mozilla Public License 2.0
1.24k stars 58 forks source link

extract variants of remove on HashTrieMap and RedBlackTreeMap #72

Open maboesanman opened 1 year ago

maboesanman commented 1 year ago

when removing items from HashTrieMap and RedBlackTreeMap, if you want an owned value you always have to clone. In theory you shouldn't have to clone in all cases, for example when using insert_mut then removing the same value, its possible the item is only owned by a single collection and therefore try_unwrap could be used to produce the owned value.

Even if there wasn't an efficient implementation right off the bat, even one that always clones would be a convenient quality of life feature, especially for working with RedBlackTreeMap as a priority queue.

I propose the following methods:

impl<K, V> HashTrieMap<K, V> {
    pub fn extract<Q: ?Sized>(&self, key: &Q) -> (HashTrieMap<K, V, P, H>, Option<(K, V)>)
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        todo!()
    }

    pub fn extract_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        todo!()
    }
}

impl<K, V> RedBlackTreeMap <K, V> {
    pub fn extract<Q: ?Sized>(&self, key: &Q) -> (RedBlackTreeMap <K, V, P, H>, Option<(K, V)>)
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        todo!()
    }

    pub fn extract_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        todo!()
    }

    pub fn extract_min(&self) -> (RedBlackTreeMap <K, V, P, H>, Option<(K, V)>) {
        todo!()
    }

    pub fn extract_min_mut(&mut self) -> Option<(K, V)> {
        todo!()
    }

    pub fn extract_max(&self) -> (RedBlackTreeMap <K, V, P, H>, Option<(K, V)>) {
        todo!()
    }

    pub fn extract_max_mut(&mut self) -> Option<(K, V)> {
        todo!()
    }
}