<div class="gmail_quote">On Wed, Jun 2, 2010 at 04:09, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I think I figured how to define BinaryHeap properly.<br>
<br>
Currently BinaryHeap is parameterized by its storage support, which must be a random-access range.<br>
<br>
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).<br>
<br>
Container-parameterized code for the win!<font color="#888888"></font></blockquote><div><br>Some naive questions:<br><br>- 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?<br>
<br>- In the current BH implementation, the reallocation inside the push method is strange:<br> // the type param is Range, _store is a Range.<br> // reallocate<br> _store.length = (_length + 1) * 2;<br>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?<br>
<br>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?<br>
<br>- 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?<br><br>- Could that be done for other wrappers, like Set? A set for a range couldn't grow, while a Set!Container could.<br>
<br><br>Philippe<br> <br></div></div>