Looking for feedback on my treap implementation

code review
1

Hi everyone!

I’ve been working on a Rust implementation of a treap data structure as part of studying algorithms and data structures.
I’d really appreciate some feedback from people more experienced with Rust.

The implementation is here:

Many thanks in advance!

2

I'd expect being able to pass a random number generator into the data structure, or at least a seed, rather than it using the global generator.

3

  • This is subjective, but when I have two fundamentally related types like Treap and Node, I prefer to put them next to each other, rather than letting any impls sit between them. This allows readers to see the whole data structure definition at once, which can help understanding.

  • Your PartialEq, PartialOrd, and Ord implementation can call len() as a cheap early test, so that they don’t have to compare lots of elements and only give up at the end, if one treap is a prefix of another.

  • In my opinion, len() would be better if written as:

    pub fn len(&self) -> usize {
    match self.root {
        None => 0,
        Some(root) => root.size,
    }
}

    This is immediately comprehensible without the reader needing to work through what as_deref() and map_or() do, and is less work for the compiler because it doesn’t have to instantiate two generic functions. I wouldn’t necessarily suggest this if it were in the middle of a chain, but since it isn’t, I think one should write straightforward, simple, boring code.

  • fn new() should be const fn new(); it’s very useful to be able to define constants that contain empty data structures.

    (This suggestion might conflict with @tczajka’s, depending on how you choose to go about it.)

  • The ordering on the borrowed form **must** match the ordering on the key type.

    While I admit the standard library does say this too, I think it is bad practice. You should say, if you say anything, that K must obey the requirements of the Borrow trait. This makes it clear that you’re not establishing a special condition for use of get() in particular.

  • assert_range() and the functions that call it should be marked with the #[track_caller] attribute. This makes panic locations point to the caller that provided the incorrect range, rather than your implementation code. (It does not affect backtraces; this is for having more useful information when backtraces are not enabled, and putting the “blame” in the right place.)

  • Consider making your library no_std compatible. This will largely consist of:

    • Adding #![no_std] and extern crate alloc;
    • Changing all your imports to refer to core and alloc instead of std, and adding a few more like use alloc::boxed::Box;
    • Removing the dependency on rand’s global RNG.
4

Thank you so much for the in-depth review!
I’ve only recently started learning Rust, so your advice is incredibly helpful and much appreciated!

I also wanted to implement the Entry API, but I ran into borrowck issues. I’m not sure how to overcome them without using unsafe or some “ugly” workarounds, such as using rank to traverse the tree or making the Entry methods only modify temporary state and then propagating the changes in Drop.

6

my experience with reviewing (and writing tbh) Rust code is that match is always underrated.

It's oftentimes shorter than Option and Result methods, esp. when the transformation is not trivial.

7

Also, looking into source code for iterators, it seems they check the size hint to short-circuit on length already: iterator.rs - source

8

That's only for TrustedLen iterators defined by the standard library.

9

Oh, you are right! I stand corrected!

10

Your PartialEq, PartialOrd, and Ord implementation can call len() as a cheap early test

another cheap early test to perform is to cast the boxes to pointers and to compare the pointers, if 2 boxes point to the same address they must be equal.
e.g. :

if self.node.as_ref().map(|x| x.as_ptr()) == other.node.as_ref().map(|x| x.as_ptr()) {
    return Ordering::Equal;
}