Implementing a van Emde Boas tree in Rust

I wanted to implement a van Emde Boas Tree in Rust, to start learning the language. Much of my implementation is derived from the pseudo-code on wikipedia, with the exception that empty subtrees are not stored.

Besides the obvious lack of docstrings on public methods, what could be improved?

```
use std::mem;

#[derive(Debug)]
pub struct VEBTree {
// box is necessary for recursion
children: Vec>>,
summary: Option>,
// special cases of min and max:
// if the tree is empty, min > max
// if the tree contains only one element, min == max == that element.
min: i64,
max: i64,
universe: i64,
sqrt_universe: i64,
}

impl Clone for VEBTree {
fn clone(&self) -> Self {
VEBTree {
children: self.children.clone(),
summary: self.summary.clone(),
min: self.min,
max: self.max,
universe: self.universe,
sqrt_universe: self.sqrt_universe,
}
}
}

// helper macros

macro_rules! subtree {
( $self_: ident, $x: expr ) => {
$self_.children.get($x).expect("child idx out of bounds").as_ref()
}
}

macro_rules! summary {
( $self_: ident ) => {
$self_.summary.as_ref().expect("summary not present")
}
}

macro_rules! summary_mut {
( $self_: ident ) => {
$self_.summary.as_mut().expect("summary not present")
}
}

impl VEBTree {
fn high(&self, x: i64) -> i64 {
((x as f64) / (self.sqrt_universe as f64)).floor() as i64
}

fn low(&self, x: i64) -> i64 {
x % self.sqrt_universe
}

fn index(&self, i: i64, j: i64) -> i64 {
i * self.sqrt_universe + j
}

pub fn new(max_elem: i64) -> Result {
if max_elem 2")
} else if max_elem > isize::max_value() as i64 {
Err("universe too big")
} else {
// sqrt_universe: 2^(floor(log_2(universe) / 2))
let sqrt_universe = ((((max_elem as f64).ln()) / (2f64).ln()) / 2f64).exp2() as i64

The name VEBTree should, under Rust conventions, be VebTree.

The macros could be written as private methods, and I tend to think that they’d be clearer thus. I would expect them to be inlined automatically, but you could mark them #[inline] also; because of inlining, there will be no performance difference to the macros.

Box wrapping is only needed to provide indirection so that recursive data types work. summary thus needs it, but children doesn’t.

Your Clone implementation could (and thus should) be replaced with #[derive(Clone)].

You check if max_elem 2; the clause, however, would correspond to > 1.

Now, concerning the equation; for starters, ((((max_elem as f64).ln()) / (2f64).ln()) / 2f64).exp2() as i64 should be written as ((max_elem as f64).ln() / 2f64.ln() / 2f64).exp2() as i64—superfluous parentheses hamper reading. But there is a more significant issue at stake: the actual equation being calculated.

The comment gives this equation: $$2^{floor\left(\frac{log_2 x}2\right)}$$

But the code calculates this equation: $$floor\left(2^\frac{log_2 x}2\right)$$

These give quite different results; the comment would yield only powers of two, but the latter will yield all integers, and might as well be max_elem.sqrt().

I feel that if max_elem 1 has already been asserted.

In insert: match x { true => …, false => … } would normally be nicer written as if x { … } else { … }. One less indentation level, and a more natural way of expressing it.

In delete: summary!(self)` is being called quite a few times; it feels like it should be possible to remove some of them, but I haven’t thought about it much at all.

StackExchange Code Review Q#102124, answer score: 5