Repository: JuliaCollections/DataStructures.jl
Pull request #452 (2018-09-24 12:40:33)

fix push! and update! for heaps to convert the input value
This fixes issue #399. That issue did not consider the case of updating a value in a mutable heap, but this PR contains a fix for that as well.

codecov[bot]: # [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452?src=pr&el=h1) Report
> Merging [#452](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/3fd4b20584d3cff08bbcaffd9a2f30249c63b32f?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452/graphs/tree.svg?width=650&token=7FHvoCSQ7k&height=150&src=pr)](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452?src=pr&el=tree)

```diff
@@            Coverage Diff            @@
##           master    #452      +/-   ##
=========================================
+ Coverage    98.8%   98.8%   +<.01%     
=========================================
  Files          27      27              
  Lines        1335    1336       +1     
=========================================
+ Hits         1319    1320       +1     
  Misses         16      16
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/heaps/binary\_heap.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452/diff?src=pr&el=tree#diff-c3JjL2hlYXBzL2JpbmFyeV9oZWFwLmps) | `100% <ø> (ø)` | :arrow_up: |
| [src/heaps/mutable\_binary\_heap.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452/diff?src=pr&el=tree#diff-c3JjL2hlYXBzL211dGFibGVfYmluYXJ5X2hlYXAuamw=) | `100% <100%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452?src=pr&el=footer). Last update [3fd4b20...ae86159](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/452?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

oxinabox: Yes, this is good, 
and correct.
Thank you

Patch:
diff --git a/src/heaps/binary_heap.jl b/src/heaps/binary_heap.jl
index baad627..75e0180 100644
--- a/src/heaps/binary_heap.jl
+++ b/src/heaps/binary_heap.jl
@@ -134,14 +134,13 @@ length(h::BinaryHeap) = length(h.valtree)
 
 isempty(h::BinaryHeap) = isempty(h.valtree)
 
-function push!(h::BinaryHeap{T}, v::T) where T
+function push!(h::BinaryHeap, v)
     valtree = h.valtree
     push!(valtree, v)
     _heap_bubble_up!(h.comparer, valtree, length(valtree))
     h
 end
 
-
 """
     top(h::BinaryHeap)
 
diff --git a/src/heaps/mutable_binary_heap.jl b/src/heaps/mutable_binary_heap.jl
index 942794c..09f0912 100644
--- a/src/heaps/mutable_binary_heap.jl
+++ b/src/heaps/mutable_binary_heap.jl
@@ -197,12 +197,12 @@ length(h::MutableBinaryHeap) = length(h.nodes)
 
 isempty(h::MutableBinaryHeap) = isempty(h.nodes)
 
-function push!(h::MutableBinaryHeap{T}, v::T) where T
+function push!(h::MutableBinaryHeap{T}, v) where T
     nodes = h.nodes
     nodemap = h.node_map
     i = length(nodemap) + 1
     nd_id = length(nodes) + 1
-    push!(nodes, MutableBinaryHeapNode(v, i))
+    push!(nodes, MutableBinaryHeapNode(convert(T, v), i))
     push!(nodemap, nd_id)
     _heap_bubble_up!(h.comparer, nodes, nodemap, nd_id)
     i
@@ -228,15 +228,16 @@ pop!(h::MutableBinaryHeap{T}) where {T} = _binary_heap_pop!(h.comparer, h.nodes,
 Replace the element at index `i` in heap `h` with `v`.
 This is equivalent to `h[i]=v`.
 """
-function update!(h::MutableBinaryHeap{T}, i::Int, v::T) where T
+function update!(h::MutableBinaryHeap{T}, i::Int, v) where T
     nodes = h.nodes
     nodemap = h.node_map
     comp = h.comparer
 
     nd_id = nodemap[i]
     v0 = nodes[nd_id].value
-    nodes[nd_id] = MutableBinaryHeapNode(v, i)
-    if compare(comp, v, v0)
+    x = convert(T, v)
+    nodes[nd_id] = MutableBinaryHeapNode(x, i)
+    if compare(comp, x, v0)
         _heap_bubble_up!(comp, nodes, nodemap, nd_id)
     else
         _heap_bubble_down!(comp, nodes, nodemap, nd_id)


Test patch:
diff --git a/test/test_binheap.jl b/test/test_binheap.jl
index 4f1a9c5..4c75583 100644
--- a/test/test_binheap.jl
+++ b/test/test_binheap.jl
@@ -125,4 +125,14 @@
         end
     end
 
+    @testset "push! type conversion" begin # issue 399
+        h = binary_minheap(Float64)
+        push!(h, 3.0)
+        push!(h, 5)
+        push!(h, Rational(4, 8))
+        push!(h, Complex(10.1, 0.0))
+
+        @test isequal(h.valtree, [0.5, 5.0, 3.0, 10.1])
+    end
+
 end # @testset BinaryHeap
diff --git a/test/test_mutable_binheap.jl b/test/test_mutable_binheap.jl
index 3b43de3..7ff8f24 100644
--- a/test/test_mutable_binheap.jl
+++ b/test/test_mutable_binheap.jl
@@ -209,4 +209,16 @@ end
         end
     end
 
+    @testset "test push! and update! conversion" begin # issue 399
+        h = mutable_binary_minheap(Float64)
+        push!(h, 3.0)
+        push!(h, 5)
+        push!(h, Rational(4, 8))
+        push!(h, Complex(10.1, 0.0))
+        @test isequal(heap_values(h), [0.5, 5.0, 3.0, 10.1])
+
+        update!(h, 2, 20)
+        @test isequal(heap_values(h), [0.5, 10.1, 3.0, 20.0])
+    end
+
 end # @testset MutableBinheap