Creating a growable binary heap or priority queue using Phobos?

SimonM user at example.net
Sun Nov 13 15:25:58 PST 2011


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?


More information about the Digitalmars-d-learn mailing list