6
\$\begingroup\$

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<Option<Box<VEBTree>>>,
    summary: Option<Box<VEBTree>>,
    // 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<Self, &'static str> {
        if max_elem <= 1 {
            Err("universe size must be > 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;
            Ok(VEBTree {
                universe: max_elem,
                sqrt_universe: sqrt_universe,
                min: max_elem,
                max: -1,
                summary: if max_elem <= 2 {
                    None
                } else {
                    Some(Box::new(VEBTree::new(sqrt_universe).unwrap()))
                },
                children: if max_elem <= 2 {
                    vec![]
                } else {
                    vec![None; sqrt_universe as usize]
                },
            })
        }
    }

    pub fn minimum(&self) -> i64 {
        self.min
    }

    pub fn maximum(&self) -> i64 {
        self.max
    }

    pub fn universe(&self) -> i64 {
        self.universe
    }

    pub fn is_empty(&self) -> bool {
        self.min > self.max
    }

    pub fn has(&self, x: i64) -> bool {
        if x == self.min || x == self.max {
            true
        } else if self.universe == 2 || x > self.universe {
            false
        } else {
            subtree!(self, self.high(x) as usize).map_or(false, |subtree| {
                subtree.has(self.low(x))
            })
        }
    }

    fn find_in_subtree(&self, x: i64) -> Option<i64> {
        // we need to look in a different cluster. Since universe > 2, we know summary exists.
        summary!(self).find_next(self.high(x)).map_or(None, |next_index| {
            Some(self.index(next_index, subtree!(self, next_index as usize).unwrap().minimum()))
        })
    }

    pub fn find_next(&self, x: i64) -> Option<i64> {
        // base case
        if self.is_empty() {
            None
        } else if self.universe == 2 {
            if x == 0 && self.max == 1 {
                Some(1)
            } else {
                None
            }
        } else if x < self.min {
            Some(self.min)
        } else {
            let idx = self.high(x);
            let low = self.low(x);
            // look in subtrees
            subtree!(self, idx as usize).map_or_else(|| {
                self.find_in_subtree(x)
            }, |subtree| {
                let max_low = subtree!(self, idx as usize).unwrap().maximum();
                if low < max_low {
                    Some(self.index(idx, subtree.find_next(low).unwrap()))
                } else {
                    self.find_in_subtree(x)
                }
            })
        }
    }

    fn empty_insert(&mut self, x: i64) {
        self.min = x;
        self.max = x;
    }

    pub fn insert(&mut self, mut x: i64) {
        match self.is_empty() {
            true => self.empty_insert(x),
            false => {
                if self.min == self.max {
                    if x < self.min {
                        self.min = x;
                    }
                    if x > self.max {
                        self.max = x;
                    }
                }
                if x < self.min {
                    mem::swap(&mut self.min, &mut x);
                }
                if x > self.max {
                    self.max = x;
                }
                let idx = self.high(x);
                let low = self.low(x);
                let sqrt = self.sqrt_universe;
                let subtree = &mut self.children[idx as usize];
                match *subtree {
                    Some(ref mut subtree) => subtree.insert(low),
                    None => {
                        let mut new_tree = VEBTree::new(sqrt).unwrap();
                        new_tree.empty_insert(low);
                        mem::replace(subtree, Some(Box::new(new_tree)));
                        summary_mut!(self).insert(idx);
                    },
                }
            },
        };
    }

    pub fn delete(&mut self, mut x: i64) {
        match self.min == self.max && self.min == x {
            // base case - empty the tree
            true => { self.min = self.universe; self.max = -1; },
            false => {
                if self.min == x {
                    // we need to calculate the new minimum
                    self.min = if summary!(self).is_empty() {
                        self.max // return
                    } else {
                        // we need to insert the old minimum
                        x = subtree!(self, summary!(self).minimum() as usize).unwrap().minimum();
                        x
                    }
                }
                if self.max == x {
                    // we need to calculate the new maximum
                    self.max = if summary!(self).is_empty() { // only 1 element in the tree
                        self.min
                    } else {
                        subtree!(self, summary!(self).maximum() as usize).unwrap().maximum()
                    }
                }
                if !summary!(self).is_empty() {
                    // recurse
                    let idx = self.high(x);
                    let low = self.low(x);
                    let mut subtree = &mut self.children[idx as usize];
                    subtree.as_mut().unwrap().delete(low);
                    // don't store empty trees, and remove from summary as well
                    if subtree.as_ref().unwrap().is_empty() {
                        subtree.take();
                        summary_mut!(self).delete(idx);
                    }
                }
            },
        };
    }

}
\$\endgroup\$
5
\$\begingroup\$

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 <= 1, but then report as the error that universe size must be > 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 <= 2 would be clearer as if max_elem == 2, seeing as 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.

\$\endgroup\$
  • \$\begingroup\$ Regarding the match x { true => ..., false => ... }, I did that to mimic guards in Haskell, which would be written similarly, but I do agree that it would be nicer indentation with an if. Also - nice catch on the math error, that's a result of translation from a different language. \$\endgroup\$ – zrneely Aug 29 '15 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.