www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 17094] New: std.container.binaryheap doesn't manage store

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

          Issue ID: 17094
           Summary: std.container.binaryheap doesn't manage store length
                    consistently when inserting
           Product: D
           Version: D2
          Hardware: All
               URL: http://dlang.org/
                OS: All
            Status: NEW
          Severity: normal
          Priority: P3
         Component: phobos
          Assignee: nobody puremagic.com
          Reporter: jrdemail2000-dlang yahoo.com

When inserting into a BinaryHeap, the underlying data "store" length may or may
not be updated, depending the type of container used and whether there is
already capacity.

This leaves the data store in a state where cannot be used. This appears to be
a bug, described used cases indicate the store can be accessed, implying the
length should be correct.

A unit test example from the documentation:

   import std.algorithm.comparison : equal;
   int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
   auto h = heapify(a);
   assert(h.front == 16);
   assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));

The last line is accessing the data store. This program has the above, then
follows with the same notion, but done by inserting elements into an existing
heap instead:

void main(string[] args)
{
    import std.container.binaryheap;
    import std.algorithm.comparison : equal;

    /* Current unit test. */
    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
    auto h = heapify(a);
    assert(h.front == 16);
    assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));

    /* Same, but using insert. Fails on last line. */
    int[] vals = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
    int[] b;
    auto h2 = heapify(b);
    foreach (v; vals) h2.insert(v);
    assert(h2.front == 16);
    assert(equal(b, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));  // Fails
}

Documentation for binaryheap implies throughout that structure is being applied
to the underlying data store, and that this can be accessed.

A specific use case where this is problematic is when extracting the elements
to reorder the underlying data store. From the documentation:

    Extracting elements from the BinaryHeap to completion leaves the
    underlying store sorted in ascending order but, again, yields
    elements in descending order.

This is useful when identifying a top-k set of elements, then want to access in
ascending order, which is the order of the data store in the description above.
However, because the data store length is not correctly set, it cannot be
accessed normally.

The below program has some diagnostics. It inserts in heaps built with both
dynamics arrays and std.container.array.Array. It also shows the difference
when capacity has and has not been preallocated.

When run, it shows that the underlying data store gets updated when an
std.container.array.Array is used and preallocated with reserve(), not
otherwise the lengths are not updated.

------bug_binaryheap.h-----
void main(string[] args)
{
    import std.container.binaryheap;
    import std.container.array;
    import std.stdio;

    int[] vals = [3, 8, 9, 2, 6, 4, 5, 1, 7];
    int[] storeX;
    int[] storeXRes;
    Array!int storeY;
    Array!int storeYRes;

    storeXRes.reserve(vals.length);
    storeYRes.reserve(vals.length);

    writeln("                      X  XRes  Y  YRes");
    writeln("Before heapify");
    writefln("  Store capacity:    %2d   %2d  %2d  %2d",
             storeX.capacity, storeXRes.capacity, storeY.capacity,
storeYRes.capacity);

    auto heapX    = heapify(storeX, 0);
    auto heapXRes = heapify(storeXRes, 0);
    auto heapY    = heapify(storeY, 0);
    auto heapYRes = heapify(storeYRes, 0);

    writeln("After heapify");
    writefln("  Heap lengths:      %2d   %2d  %2d  %2d",
             heapX.length, heapXRes.length, heapY.length, heapYRes.length);
    writefln("  Store lengths:     %2d   %2d  %2d  %2d",
             storeX.length, storeXRes.length, storeY.length, storeYRes.length);

    writefln("  Heap capacity:     %2d   %2d  %2d  %2d",
             heapX.capacity, heapXRes.capacity, heapY.capacity,
heapYRes.capacity);
    writefln("  Store capacity:    %2d   %2d  %2d  %2d",
             storeX.capacity, storeXRes.capacity, storeY.capacity,
storeYRes.capacity);

    foreach (v; vals)
    {
        heapX.insert(v);
        heapXRes.insert(v);
        heapY.insert(v);
        heapYRes.insert(v);
    }

    writeln("After inserts");
    writefln("  Heap lengths       %2d   %2d  %2d  %2d",
             heapX.length, heapXRes.length, heapY.length, heapYRes.length);
    writefln("  Store lengths:     %2d   %2d  %2d  %2d",
             storeX.length, storeXRes.length, storeY.length, storeYRes.length);

    writefln("  Heap capacity:     %2d   %2d  %2d  %2d",
             heapX.capacity, heapXRes.capacity, heapY.capacity,
heapYRes.capacity);
    writefln("  Store capacity:    %2d   %2d  %2d  %2d",
             storeX.capacity, storeXRes.capacity, storeY.capacity,
storeYRes.capacity);

    auto storeX2    = heapX.release;
    auto storeX2Res = heapXRes.release;
    auto storeY2    = heapY.release;
    auto storeY2Res = heapYRes.release;

    writeln("After release:");
    writefln("  Heap lengths       %2d   %2d  %2d  %2d",
             heapX.length, heapXRes.length, heapY.length, heapYRes.length);
    writefln("  Store lengths:     %2d   %2d  %2d  %2d",
             storeX.length, storeXRes.length, storeY.length, storeYRes.length);
    writefln("  Returned lengths:  %2d   %2d  %2d  %2d",
             storeX2.length, storeX2Res.length, storeY2.length,
storeY2Res.length);
}
---------------------------

Note: X is built in array, Y is std.container.array.Array. XRes and YRes have
been pre-allocated with with reserve().

$ dmd bug_binaryheap.d
$ ./bug_binaryheap 
                      X  XRes  Y  YRes
Before heapify
  Store capacity:     0   15   0   9
After heapify
  Heap lengths:       0    0   0   0
  Store lengths:      0    0   0   0
  Heap capacity:      0   15   0   9
  Store capacity:     0   15   0   9
After inserts
  Heap lengths        9    9   9   9
  Store lengths:      0    0   0   9
  Heap capacity:     15   15  11   9
  Store capacity:     0    0   0   9
After release:
  Heap lengths        0    0   0   0
  Store lengths:      0    0   0   9
  Returned lengths:   9    9   9   9

$ dmd --version
DMD64 D Compiler v2.073.0-b1
Copyright (c) 1999-2016 by Digital Mars written by Walter Bright

--
Jan 15