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