D: Strange behavior from std.container.BinaryHeap with custom function for comparison
I wrote the following code for the heap Node*
s that are in the module node
:
import std.exception, std.container;
public import node;
alias NodeArray = Array!(const (Node)*);
alias NodeHeap = BinaryHeap!(NodeArray, cmp_node_ptr);
auto make_heap() {
return new NodeHeap(NodeArray(cast(const(Node)*)[]));
}
void insert(NodeHeap* heap, in Node* u) {
enforce(heap && u);
heap.insert(u);
}
pure bool cmp_node_ptr(in Node* a, in Node* b) {
enforce(a && b);
return (a.val > b.val);
}
Then I tried the following unit tests where it make_leaf
returns a Node*
initialized with the given argument:
unittest {
auto u = make_leaf(10);
auto heap = make_heap();
insert(heap, u); //bad things happen here
assert(heap.front == u);
auto v = make_leaf(20);
insert(heap, v);
assert(heap.front == u); //assures heap property
}
Tests hit on a commented line and then throw a force error on the line enforce(a && b)
in cmp_node_ptr
. I am completely lost as to why this is happening.
source to share
you are doing the wrong thing in this statement:
NodeArray(cast(const(Node)*)[])
you obviously want to create an empty NodeArray, but what you really got is a NodeArray with one null element. The NodeArray constructor takes a list of values for the new array as arguments, and you pass one "empty array" (which is essentially zero), thus creating a NodeArray with one empty element.
the right way:
NodeArray()
i.e:.
auto make_heap() {
return new NodeHeap();
}
make this change and everything will be fine.
ps seems like notation D for multiple arguments like U (U [] values ...) made you think that the constructor takes another array as an initializer.
pps sorry, corrected make_heap () code: accidentally forgot to write "NodeArray ()" in it. and edited it again since no empty NodeArray () call is needed here. double mistake!
source to share