mdhondt / veb Goto Github PK

Hello Mr. Dhondt,

Not an issue, but a "thank you" message...

I would like to congratulate you with your careful and very, very complete implementation of a Van Emde Boas tree. As the head of research at a Vienna, Austria startup, I was working on a prototype for a new feature in our server-side software, and I needed a vEB tree. I implemented the one given by Sedgewick, but introduced a bug into my code. Careful inspection of yours made me clear, within a brief time, where my bug was located. Nice work !

Best regards,

Jan van Oort
Head of research
Kivu Technologies GmbH, Vienna, Austria

Hi, I wanted to run some tests with a vEB Tree and I was testing with your code. I was trying to create a vEB with a universe size of 200 but it fails when trying to insert at offset 128. The getUniverse() method reports 200 but the insert of value 128 (always 128) fails with:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 16 out of bounds for length 16

I get this failure at line 794 inside the insert() method:

if (universeSize > 2)
    if (clusters[high(key)].getMin() == NIL) {

I started my tests using a vEB Tree of size 16 (perfect square of 2^(2^2)) so I am wondering if the restriction that is talked about in the CLR book that there is no restriction on the universe size having to be an even square of 2 is not implement in your code? It looked like it was since you have the lower and upper square methods.

Thank you,
Ray