BinaryHeap

[Philippe Sigaud]

On Wed, Jun 2, 2010 at 04:09, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

> I think I figured how to define BinaryHeap properly.
>
> Currently BinaryHeap is parameterized by its storage support, which must be
> a random-access range.
>
> It is easy to make BinaryHeap figure out whether its support is a
> random-access _container_ versus a random-access range. In the former case,
> it supports growing. Otherwise, the functionality remains as it is (the heap
> is bounded by the length of the range).
>
> Container-parameterized code for the win!


Some naive questions:

- For the container case, how does it grow? By adding an element to the
container and re-heapifying it? Or is the input container used once to
create the heap and then discarded, the heap maintaining some internal
storage, f.e. an array of the container's elements?

- In the current BH implementation, the reallocation inside the push method
is strange:
    // the type param is Range, _store is a Range.
    // reallocate
     _store.length = (_length + 1) * 2;
Shouldn't you use a ElementType!Range[] instead of a Range for _store? I
don't think many ranges allow their length to be changed that way. Or is it
a side effect of having @property length now?

Ah, I get it. You will now separate container-supported BH, that can cleanly
grow by using the inherent possibility of containers to grow. And you will
not permit range-supported BH to grow this way, because there is not
meaninigful way to grow a range. Is that it?

- If I have a range but want to grow the BH afterwards, I first create a
container from the range and wrap BinaryHeap around? There should be a
simple container for this kind of conversion. Some array?

- Could that be done for other wrappers, like Set? A set for a range
couldn't grow, while a Set!Container could.


Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100602/a72342db/attachment.html>