[Issue 17094] std.container.binaryheap doesn't manage store length consistently when inserting

[d-bugmail at puremagic.com]

https://issues.dlang.org/show_bug.cgi?id=17094

Simen Kjaeraas <simen.kjaras at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |INVALID

--- Comment #5 from Simen Kjaeraas <simen.kjaras at gmail.com> ---
(In reply to Jon Degenhardt from comment #3)
> Reserve is used to preallocate the necessary space. It is not necessary to
> reallocate.

Try this:

    int[] a;
    int[] b = a;
    assert(a.ptr == b.ptr);
    a.reserve(10);
    assert(a.ptr != b.ptr);

Then tell me that reserve() doesn't reallocate. For good measure, here's a case
where a isn't initialized to null:

    int[] a = new int[1];
    int[] b = a;
    assert(a.ptr == b.ptr);
    a.reserve(256);
    assert(a.ptr != b.ptr);


(In reply to Jon Degenhardt from comment #4)
> A bit of a follow-up to the last pair of comments: The discussion of whether
> size was reserved, the implied notions of reference vs value semantics,
> etc., is in my view an incorrect focus. The key issue involved is this
> paragraph in the documentation:
> 
>     Simply extracting elements from a $(D BinaryHeap) container is
>     tantamount to lazily fetching elements of $(D Store) in descending
>     order. Extracting elements from the $(D BinaryHeap) to completion
>     leaves the underlying store sorted in ascending order but, again,
>     yields elements in descending order.

The slice from which you initialize the heap is not its store. This is why it's
not a bug.

The source of confusion, as mentioned in comment #2, is that slices aren't
really containers, but the language sometimes treats them as if they are.
Slices in D are basically this structure:

struct Slice(T) {
    T* ptr;
    size_t length;

    ref T opIndex(size_t index) {
        assert(index < length);
        return ptr[index];
    }

    Slice opSlice(size_t start, size_t end) {
        assert(start <= end);
        assert(end < length);
        return Slice(ptr + start, end - start);
    }
}

When you write 'int[] a;', you allocate the above structure on the stack. Once
it goes out of scope, there's no way to update its ptr or length. Since it's
not even passed by ref to heapify, heapify has no idea where the original slice
lives, and is utterly incapable of updating it even if it wanted to. So yeah,
the binaryHeap can't, shouldn't, and doesn't update the slice it's initialized
from, and if you somehow make it do that, only bad things will come of it.
Nasal demons will be the least of your problems.


> The second sentence is the key issue - A key use case of a binary heap is to
> take a top-n set of items, then generate the top-n order by extracting as
> described. This is what fails, and why this is a bug. The documentation
> indicates binary heap supports this, as it should. 

It does support that, but not when it's initialized from a slice, since a slice
is not a container.
If you want a store that's updated to reflect the contents of the heap, you
need to use a store with reference semantics, like std.container.array:

    import std.algorithm.comparison;
    import std.container.array;
    import std.container.binaryHeap;
    import std.stdio;

    auto a = Array!int(new int[0]);
    auto h = a.heapify;
    h.insert(1);
    h.insert(2);
    h.insert(3);
    h.insert(4);
    h.insert(5);
    assert(equal(a[], [5,4,2,1,3]));

> If there are cases where
> it does not support it, it should be clear about this. But really, this use
> case should be supported.

Now here we might have found some common ground. All the examples for
binaryHeap use slices. As pointed out ad nauseam above, this is a Bad Idea™ if
you want to look at what the binaryHeap does to that slice when you insert into
it. However, there's nothing inherently wrong in initializing a binaryHeap from
a slice.

The documentation does not adequately convey this information, and should be
amended to more clearly point this out. Filed this as bug 18333.

--