www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - BinaryHeap

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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!


Andrei
Jun 01 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6d77c6f01725104881219a5
Content-Type: text/plain; charset=ISO-8859-1

On Wed, Jun 2, 2010 at 04:09, Andrei Alexandrescu <
SeeWebsiteForEmail 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 --0016e6d77c6f01725104881219a5 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Wed, Jun 2, 2010 at 04:09, Andrei Alexandresc= u <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">Se= eWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D"g= mail_quote" style=3D"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-ac= cess _container_ versus a random-access range. In the former case, it suppo= rts growing. Otherwise, the functionality remains as it is (the heap is bou= nded by the length of the range).<br> <br> Container-parameterized code for the win!<font color=3D"#888888"></font></b= lockquote><div><br>Some naive questions:<br><br>- For the container case, h= ow 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 containe= r&#39;s elements?<br> <br>- In the current BH implementation, the reallocation inside the push me= thod is strange:<br>=A0=A0=A0 // the type param is Range, _store is a Range= .<br>=A0=A0=A0 // reallocate<br>=A0=A0=A0=A0 _store.length =3D (_length + 1= ) * 2;<br>Shouldn&#39;t you use a ElementType!Range[] instead of a Range fo= r _store? I don&#39;t think many ranges allow their length to be changed th= at 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 cl= eanly 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 si= mple 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&#39;t grow,= while a Set!Container could.<br> <br><br>Philippe<br>=A0<br></div></div> --0016e6d77c6f01725104881219a5--
Jun 02 2010