digitalmars.D.bugs - [Issue 17094] New: std.container.binaryheap doesn't manage store
- via Digitalmars-d-bugs (154/154) Jan 15 2017 https://issues.dlang.org/show_bug.cgi?id=17094
via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> 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 2017