www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Creating a growable binary heap or priority queue using Phobos?

reply SimonM <user example.net> writes:
Hey, I'm trying to use the BinaryHeap in Phobos, but somehow can't get 
it working with the Array!(T) container so that the heap can actually be 
growable. I keep getting this error:

Error: template instance BinaryHeap!(myArray,"a > b") does not match 
template declaration BinaryHeap(Store,alias less = "a < b") if 
(isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))

The documentation 
(http://d-programming-language.org/phobos/std_container.html#BinaryHeap) 
says that BinaryHeap should be growable with any container that supports 
the insertBack function, which Array!(T) does 
(http://d-programming-language.org/phobos/std_container.html#insertBack).

I've found the following questions in the newsgroup that all asked the 
same question, without really resolving it (without using their own 
implementation):

2011, 28 March: 
http://www.digitalmars.com/d/archives/digitalmars/D/learn/Growable_BinaryHeap_use_w_Array_25362.html

2011, 6 March: 
http://www.digitalmars.com/d/archives/digitalmars/D/learn/How_do_you_use_BinaryHeap_with_Array_or_just_make_a_growable_heap_25928.html

2009, 27 April: 
http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html

 From those threads, I found that the reason might be related to the 
fact that the isRandomAccessRange template returns false when used with 
an Array!(T) object, for example this
----------------------------------------
import std.range;
import std.container;

void main(){
	pragma(msg,isRandomAccessRange!(Array!(uint)));
}
----------------------------------------
prints out false during compilation.

Is there any way to use Array!(T) with a BinaryHeap, or any other way to 
have a growable BinaryHeap?
Nov 13 2011
next sibling parent reply SimonM <user example.net> writes:
On 2011/11/13 22:49 PM, SimonM wrote:

 Hey, I'm trying to use the BinaryHeap in Phobos, but somehow can't get
 it working with the Array!(T) container so that the heap can actually be
 growable. I keep getting this error:

 Error: template instance BinaryHeap!(myArray,"a > b") does not match
 template declaration BinaryHeap(Store,alias less = "a < b") if
 (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))

 The documentation
 (http://d-programming-language.org/phobos/std_container.html#BinaryHeap)
 says that BinaryHeap should be growable with any container that supports
 the insertBack function, which Array!(T) does
 (http://d-programming-language.org/phobos/std_container.html#insertBack).

 I've found the following questions in the newsgroup that all asked the
 same question, without really resolving it (without using their own
 implementation):

 2011, 28 March:
 http://www.digitalmars.com/d/archives/digitalmars/D/learn/Growable_BinaryHeap_use_w_Array_25362.html


 2011, 6 March:
 http://www.digitalmars.com/d/archives/digitalmars/D/learn/How_do_you_use_BinaryHeap_with_Array_or_just_make_a_growable_heap_25928.html


 2009, 27 April:
 http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html


  From those threads, I found that the reason might be related to the
 fact that the isRandomAccessRange template returns false when used with
 an Array!(T) object, for example this
 ----------------------------------------
 import std.range;
 import std.container;

 void main(){
 pragma(msg,isRandomAccessRange!(Array!(uint)));
 }
 ----------------------------------------
 prints out false during compilation.

 Is there any way to use Array!(T) with a BinaryHeap, or any other way to
 have a growable BinaryHeap?


Okay, I might on the wrong track, but part of the reason that the 
isRandomAccessRange template fails might be because, while Array!(T) 
internally uses a Range, it doesn't itself actually provide the save() 
and popBack() functions that a Range does?
Nov 13 2011
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, November 13, 2011 23:12:30 SimonM wrote:

 Okay, I might on the wrong track, but part of the reason that the
 isRandomAccessRange template fails might be because, while Array!(T)
 internally uses a Range, it doesn't itself actually provide the save()
 and popBack() functions that a Range does?


A std.container.Array is not a range. It's a container. Yes, it uses an arary 
internally, which _ is_ a range, but it controls that memory and doesn't given 
out slices of that internal array. If you want a range over an Array, then 
slice it.

- Jonathan M Davis
Nov 13 2011
parent reply SimonM <user example.net> writes:
On 2011/11/13 23:22 PM, Jonathan M Davis wrote:

 On Sunday, November 13, 2011 23:12:30 SimonM wrote:

 Okay, I might on the wrong track, but part of the reason that the
 isRandomAccessRange template fails might be because, while Array!(T)
 internally uses a Range, it doesn't itself actually provide the save()
 and popBack() functions that a Range does?


 A std.container.Array is not a range. It's a container. Yes, it uses an arary
 internally, which _ is_ a range, but it controls that memory and doesn't given
 out slices of that internal array. If you want a range over an Array, then
 slice it.

 - Jonathan M Davis


Okay, that makes sense, but it seems that BinaryHeap should be able to 
work with a Range or a Container, as the documentation states:

"If Store is a range, the BinaryHeap cannot grow beyond the size of that 
range. If Store is a container that supports insertBack, the BinaryHeap 
may grow by adding elements to the container."

Yet, nothing I try seems to work:
----------------------------------------
import std.range;
import std.container;

void main(){
	// use dynamic array to create BinaryHeap
	int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
	auto heapA = BinaryHeap!(int[])(a); //heapify(a);
	
	// use Array!(T) struct to create BinaryHeap
	auto b = Array!(int)(a);
	
	// The following lines both fail to compile with:
     // Error: this._store()[this._length()] is not an lvalue
	//auto heapB = BinaryHeap!(Array!(int))(b);
	//auto heapB = heapify(b);
	
	// Try to use a Range, but the following lines both fail to compile with:
	//Error: function std.container.Array!(int).Array.Range.opSlice (uint 
a, uint b) is not callable using argument types ()
	//auto heapB = BinaryHeap!(Array!(int).Range)(b[]);
	//auto heapB = heapify(b[]);
}
----------------------------------------

What am I doing wrong?
Nov 13 2011
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, November 14, 2011 01:25:58 SimonM wrote:

 What am I doing wrong?


I don't know. I've never used BinaryHeap. I'd have to study it. I just noticed 
that you were trying to use treat Array as a range, which isn't going to work 
(regardless of whatever BinaryHeap does), so I tried to help you on that 
count.

- Jonathan M Davis
Nov 13 2011
parent SimonM <user example.net> writes:
On 2011/11/14 01:55 AM, Jonathan M Davis wrote:

 On Monday, November 14, 2011 01:25:58 SimonM wrote:

 What am I doing wrong?


 I don't know. I've never used BinaryHeap. I'd have to study it. I just noticed
 that you were trying to use treat Array as a range, which isn't going to work
 (regardless of whatever BinaryHeap does), so I tried to help you on that
 count.

 - Jonathan M Davis


Well it definitely helps; and now I understand it better as well, so thanks!
Nov 13 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
SimonM:


 2009, 27 April: 
 http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html


See the working version:
http://rosettacode.org/wiki/Huffman_coding#D

Bye,
bearophile
Nov 13 2011
parent reply SimonM <user example.net> writes:
On 2011/11/14 02:10 AM, bearophile wrote:

 SimonM:


 2009, 27 April:
 http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html


 See the working version:
 http://rosettacode.org/wiki/Huffman_coding#D

 Bye,
 bearophile


Okay, I looked at the example, and it seems that the only reason it 
works is because that piece of code never requires the array's length to 
grow larger than it's initial length (at the start of the loop, 2 
elements are taken out, and at the end, only one is inserted back in).

If I try using a BinaryHeap with a range, then, like the documentation 
mentions, I can't grow that BinaryHeap any larger than it's initial 
size, because I got the following error: "Cannot grow a heap created 
over a range". But somehow I can't get it working with an Array!(T) like 
the documentation implies it should be capable of?
Nov 13 2011
parent reply "qznc" <qznc web.de> writes:
On Monday, 14 November 2011 at 06:15:18 UTC, SimonM wrote:

 On 2011/11/14 02:10 AM, bearophile wrote:

 SimonM:


 2009, 27 April:
 http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html


 See the working version:
 http://rosettacode.org/wiki/Huffman_coding#D

 Bye,
 bearophile


 Okay, I looked at the example, and it seems that the only 
 reason it works is because that piece of code never requires 
 the array's length to grow larger than it's initial length (at 
 the start of the loop, 2 elements are taken out, and at the 
 end, only one is inserted back in).

 If I try using a BinaryHeap with a range, then, like the 
 documentation mentions, I can't grow that BinaryHeap any larger 
 than it's initial size, because I got the following error: 
 "Cannot grow a heap created over a range". But somehow I can't 
 get it working with an Array!(T) like the documentation implies 
 it should be capable of?


Is this problem resolved? I cannot produce a growable BinaryHeap 
myself.
Jun 22 2013
parent "qznc" <qznc web.de> writes:
On Saturday, 22 June 2013 at 07:48:25 UTC, qznc wrote:

 On Monday, 14 November 2011 at 06:15:18 UTC, SimonM wrote:

 On 2011/11/14 02:10 AM, bearophile wrote:

 SimonM:


 2009, 27 April:
 http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html


 See the working version:
 http://rosettacode.org/wiki/Huffman_coding#D

 Bye,
 bearophile


 Okay, I looked at the example, and it seems that the only 
 reason it works is because that piece of code never requires 
 the array's length to grow larger than it's initial length (at 
 the start of the loop, 2 elements are taken out, and at the 
 end, only one is inserted back in).

 If I try using a BinaryHeap with a range, then, like the 
 documentation mentions, I can't grow that BinaryHeap any 
 larger than it's initial size, because I got the following 
 error: "Cannot grow a heap created over a range". But somehow 
 I can't get it working with an Array!(T) like the 
 documentation implies it should be capable of?


 Is this problem resolved? I cannot produce a growable 
 BinaryHeap myself.


Ok, got it. Instead of using a dynamic array directly, wrapping 
it into a std.container.Array works.

import std.container: Array, heapify;

Foo[] arr = ...;
auto wrapped = Array!Foo(arr);
auto queue = heapify(wrapped);

In general, other containers should work as well, since 
containers provide an insertBack method whereas the builtin 
arrays/ranges do not.
Jun 22 2013