d_heap bug

From: Tsvetomir Valtchev (chango_at_[hidden])
Date: 2002-10-31 12:07:54

[I tried to contact the library's author, dietmar.kuehl_at_claas-
solutions.de, but the message bounced back.]

Dear Dietmar,

I was looking for a better heap class than the one in STL and I was 
delighted to come across your d_heap class included in the Boost 
library. Unfortunately, I had a number of problems with it, and I 
figured you might be interested in some feedback. 

First, the class didn't compile with VC.NET (and probably won't with 
VC 6 either). This might be due to non-conformance on the part of 
Microsoft's compiler and some known limitations with template 
support, but for some of the issues I think they were due to the non-
conformance of the code itself.

Second, to my dismay, the code turned out to be seriously flawed. 
The following simple fragment, for example, causes a crash:

THeap::pointer ptrs[10];
ptrs[0] = heap.push(12);
ptrs[1] = heap.push(16);
heap.remove(ptrs[0]);
heap.remove(ptrs[1]); 

After some debugging and deciphering of the code, I found that the 
remove() function didn't handle a special case where the node to 
be 'sifted up' coincided with the last "hole" left in the tree. I 
think pop() had a similar problem. (In my fixed version, I have 
expressed pop() in terms of remove(), which resolves the problem and 
also avoids some code duplication.)

I hope some day you get around to publishing an improved version. 
Another suggestion I have is some way to make sure that the 
pointer's passed back by client code are valid. Extensive use of 
assertions throughout the code might also prevent various 
programming errors.

Regards,

// Chango V.