Re: [PATCH] binary heap implementation

Hi.

A brief response to earlier messages in this thread:

1. I agree that it's a good idea to use Datum rather than void *.
2. I don't think it's worth getting rid of binaryheap_node.
3. I agree that it makes sense to go with what we have now (after
Robert's reworking of my patch) and reconsider if needed when
there are more users of the code.
4. I agree with all of Tom's suggestions as well.

At 2012-11-20 18:01:10 -0500, tgl(at)sss(dot)pgh(dot)pa(dot)us wrote:
>
> Is it actually required that the output be exactly these three values,
> or is the specification really <0, 0, >0 ?

The code did require -1/0/+1, but I changed it to expect only <0, 0, >0.
So you're right, the comment should be changed.

> This in binaryheap_replace_first is simply bizarre:
>
> if (key)
> heap->nodes[0].key = key;
> if (val)
> heap->nodes[0].value = val;

It's a leftover from the earlier implementation that used pointers,
where you could pass in NULL to leave either key or value unchanged.

> While I'm thinking about it, why are the fields of a binaryheap_node
> called "key" and "value"? That implies a semantics not actually used
> here. Maybe "value1" and "value2" instead?

Yes, I discussed this with Andres earlier (and considered ptr and value
or p1 and p2), but decided to wait for others to comment on the naming.
I have no problem with value1 and value2, though I'd very slightly
prefer d1 and d2 (d for Datum) now.

Robert: thanks again for your work on the patch. Do you want me to make
the changes Tom suggests above, or are you already doing it?

-- Abhijit