Optimize RBTree by keeping #elements & min & max element @ top of tree

[przygienda]

very common to ask how many elements in the tree & smallest/largest element. Implementation would benefit from having

len, min, max

@ the top of the tree and according methods.

if you think you'd pull that up I can implement it.

[Amanieu]

I can accept a pull request to add min and max, those are useful to have around.

However len is a bit tricker: none of the other intrusive collections track a length, and it is generally quite easy to track externally on the side. I would prefer not tracking len for that reason.

[przygienda]

sounds good. I see I get to it.

On Fri, Jul 30, 2021 at 11:39 PM Amanieu @.***> wrote:

I can accept a pull request to add min and max, those are useful to have around.

However len is a bit tricker: none of the other intrusive collections track a length, and it is generally quite easy to track externally on the side. I would prefer not tracking len for that reason.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/Amanieu/intrusive-rs/issues/62#issuecomment-890167951, or unsubscribe https://github.com/notifications/unsubscribe-auth/AANDIC2SEZMYJOXPZIBYWCDT2ML2DANCNFSM5BJCCPGQ .

[przygienda]

well, loolking @ it & right now I'd also like to know whether the tree changed, i.e. mark it dirty when elements get inserted/removed (well, at least when the min/max changed). I try to implement a wrapper (maybe a better way to go about this business since otherwise generic RBTree will start get polluted).

So, utter mystery in the following code. the first assignment works fine, it goes directly over the RBTree and can run lower_bound but when I define a generic min() with bounds it tells me the key is not Ord. Well, the RBTree should somewhere contrain the key to Ord (and it seems to somehow in inner_lower_bound but unfortunately this does not seem to work when calling it in the generic implemenation of the surrounding structure). Any clue? How comes the i32 Ord is not percolating down in the generic?

/// wraps an RBTree to mark it dirty any time we pull a mutable
/// reference to it and provide min/max
pub struct DirtyRBTree<A>
    where
        A: Default,
        A: for<'a> KeyAdapter<'a>,
    // for<'a> <A as KeyAdapter<'a>>::Key: Ord,
        <A as Adapter>::LinkOps: RBTreeOps,
// <<A as Adapter>::PointerOps as PointerOps>::Pointer: Clone,
// <A::PointerOps as PointerOps>::Value: Debug
{
    tree: RBTree<A>,
    dirty: bool,
}

impl<A> Default for DirtyRBTree<A>
    where
        A: Default,
        A: for<'a> KeyAdapter<'a>,
    // for<'a> <A as KeyAdapter<'a>>::Key: Ord,
        <A as Adapter>::LinkOps: RBTreeOps,
// <<A as Adapter>::PointerOps as PointerOps>::Pointer: Clone,
// <A::PointerOps as PointerOps>::Value: Debug
{
    fn default() -> Self {
        Self {
            tree: RBTree::new(A::default()),
            dirty: false,
        }
    }
}

impl<A> DirtyRBTree<A>
    where
        A: Default,
        A: for<'a> KeyAdapter<'a>,
    // for<'a> <A as KeyAdapter<'a>>::Key: Ord,
        <A as Adapter>::LinkOps: RBTreeOps,
// <<A as Adapter>::PointerOps as PointerOps>::Pointer: Clone,
// <A::PointerOps as PointerOps>::Value: Debug
{
    fn get_mut(&mut self) -> &mut RBTree<A> {
        self.dirty = true;
        &mut self.tree
    }

    fn get(&self) -> &RBTree<A> {
        &self.tree
    }

    fn is_dirty(&self) -> bool { self.dirty }

    fn clear_dirty(&mut self) { self.dirty = false; }

    fn min(&self) -> Option<<<A as Adapter>::PointerOps as PointerOps>::Pointer>
        where
                for <'a> <A as KeyAdapter<'a>>::Key: Ord,
                <<A as Adapter>::PointerOps as PointerOps>::Pointer: Clone, {
        self.tree.lower_bound(Unbounded).clone_pointer()
    }
}

pub struct inside {
    key: i32,
    v: RBTreeLink,
}

intrusive_adapter!(pub keyad = Rc<inside>: inside { v: RBTreeLink } );

impl<'a> KeyAdapter<'a> for keyad
{
    type Key = i32;
    fn get_key(&self, x: &'a inside) -> Self::Key
    { x.key }
}

#[derive(Default)]
pub struct outside {
    tree: DirtyRBTree<keyad>,
}

fn main() {
    let t = outside::default();

    let minv = t.tree.get().lower_bound(Unbounded).get();
    let overmethod = t.tree.min();
}

[przygienda]

I found a combination of lifetimes that work, unfortunately it's a mix of 'a and for <'b>

tedious

impl<'a, A> DirtyRBTree<'a, A>
    where
        A: Default + Adapter,
        <A as Adapter>::LinkOps: RBTreeOps,
{
    fn i_get_mut(&mut self) -> &mut RBTree<A> {
        self.dirty = true;
        &mut self.tree
    }

    fn i_get(&self) -> &RBTree<A> {
        &self.tree
    }

    fn i_is_dirty(&self) -> bool { self.dirty }

    fn i_clear_dirty(&mut self) { self.dirty = false; }

    fn i_min(&'a self) -> Option<<<A as Adapter>::PointerOps as PointerOps>::Pointer>
        where
            A: for <'b> KeyAdapter<'b> ,
            for <'b> <<A as Adapter>::PointerOps as PointerOps>::Pointer: Clone,
            <A as KeyAdapter<'a>>::Key: Ord,
    {
        let tree : &RBTree<A> = self.i_get();
        tree.lower_bound(Unbounded).clone_pointer()
    }
}

[Amanieu]

That's correct.

[Amanieu]

Actually you don't need the 'a on DirtyRBTree. You can do everything with just 'b.

[przygienda]

BTW, in same vein, having lenght kept on the linked lists would be great for some implemenation logic