On 2011-03-28 20:24:55 +0200, Jonathan M Davis said:
Well, Array definitely shouldn't be a random access range. The range for it
(which you'd typically get by slicing it) would be random access, but the
container itself isn't a range of any kind. Containers aren't ranges (barring
the oddities of dynamic arrays). I've never used BinaryHeap, but glancing at
it, my guess would be that the correct solution (if you want to use Array with
it) is to create an Array and then pass its range to heapify:
Array!uint a;
//... put stuff in a.
auto heap = heapify(a[]);
I'm not sure if that's growable or not though.
Hm. I can't even get the slicing to work:
/path/to/phobos/std/container.d(2436): Error: function
std.container.Array!(uint).Array.Range.opSlice (uint a, uint b) is not
callable using argument types ()
Glancing at BinaryHeap, it'll work with arrays though, so you don't
need to use Array.
Hm. The docs say "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."
So it seems that a container (such as Array, which has insertBack)
should be usable, according to the docs. And an array/slice would not
be growable. (At least, it isn't growable in practice.) See also:
http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html
What
I'm looking for is a completely standard priority queue, where I can
add and remove objects, and not have to know the maximum size
beforehand.
I'd also like to have tuple entries, but it seems that BinaryHeap has
trouble with that as well...
I don't know what the ideal container to use with a BinaryHeap is
though. Also, in my experience, Array is pretty buggy at this point, so
I'm not sure how far you'll get with it.
Yeah, it seems to be. At the moment, I've just reimplemented BinaryHeap
myself (with a subset of the Phobos API), so that it can handle arrays
of tuples (which I couldn't get std.container.BinaryHeap to accept). I
then wrapped it in a PriorityQueue class, which takes care of resizing
the array (and having BinaryHeap switch to the possibly reallocated new
one).
Not an ideal solution, but at least it works.
--
Magnus Lie Hetland
http://hetland.org
