Repository: JuliaCollections/DataStructures.jl
Pull request #720 (2021-01-18 20:13:46)

Fix MutableBinaryHeap, issue similar to #686
Issue with `Base.Order.ReverseOrdering`. Mirror of #686, only related to a `MutableBinaryHeap` implementation. Depends on https://github.com/JuliaLang/julia/pull/37822.


Patch:
diff --git a/src/heaps/arrays_as_heaps.jl b/src/heaps/arrays_as_heaps.jl
index b2202be..47af9e4 100644
--- a/src/heaps/arrays_as_heaps.jl
+++ b/src/heaps/arrays_as_heaps.jl
@@ -2,6 +2,7 @@
 
 using Base.Order: Forward, Ordering, lt
 
+const DefaultReverseOrdering = Base.ReverseOrdering{Base.ForwardOrdering}
 
 # Heap operations on flat arrays
 # ------------------------------
diff --git a/src/heaps/binary_heap.jl b/src/heaps/binary_heap.jl
index 503852e..2b399f8 100644
--- a/src/heaps/binary_heap.jl
+++ b/src/heaps/binary_heap.jl
@@ -50,8 +50,6 @@ BinaryHeap(ordering::Base.Ordering, xs::AbstractVector{T}) where T = BinaryHeap{
 BinaryHeap{T, O}() where {T, O<:Base.Ordering} = BinaryHeap{T}(O())
 BinaryHeap{T, O}(xs::AbstractVector) where {T, O<:Base.Ordering} = BinaryHeap{T}(O(), xs)
 
-const DefaultReverseOrdering = Base.ReverseOrdering{Base.ForwardOrdering}
-
 # These constructors needed for BinaryMaxHeap, until we have https://github.com/JuliaLang/julia/pull/37822
 BinaryHeap{T, DefaultReverseOrdering}() where {T} = BinaryHeap{T}(Base.Reverse)
 BinaryHeap{T, DefaultReverseOrdering}(xs::AbstractVector) where {T} = BinaryHeap{T}(Base.Reverse, xs)
diff --git a/src/heaps/mutable_binary_heap.jl b/src/heaps/mutable_binary_heap.jl
index cc6525d..699aa53 100644
--- a/src/heaps/mutable_binary_heap.jl
+++ b/src/heaps/mutable_binary_heap.jl
@@ -179,9 +179,13 @@ MutableBinaryHeap(ordering::Base.Ordering, xs::AbstractVector{T}) where T = Muta
 MutableBinaryHeap{T, O}() where {T, O<:Base.Ordering} = MutableBinaryHeap{T}(O())
 MutableBinaryHeap{T, O}(xs::AbstractVector) where {T, O<:Base.Ordering} = MutableBinaryHeap{T}(O(), xs)
 
+# These constructors needed for BinaryMaxHeap, until we have https://github.com/JuliaLang/julia/pull/37822
+MutableBinaryHeap{T, DefaultReverseOrdering}() where {T} = MutableBinaryHeap{T}(Base.Reverse)
+MutableBinaryHeap{T, DefaultReverseOrdering}(xs::AbstractVector) where {T} = MutableBinaryHeap{T}(Base.Reverse, xs)
+
 # Forward/reverse ordering type aliases
 const MutableBinaryMinHeap{T} = MutableBinaryHeap{T, Base.ForwardOrdering}
-const MutableBinaryMaxHeap{T} = MutableBinaryHeap{T, Base.ReverseOrdering}
+const MutableBinaryMaxHeap{T} = MutableBinaryHeap{T, DefaultReverseOrdering}
 
 MutableBinaryMinHeap(xs::AbstractVector{T}) where T = MutableBinaryMinHeap{T}(xs)
 MutableBinaryMaxHeap(xs::AbstractVector{T}) where T = MutableBinaryMaxHeap{T}(xs)


Test patch:
diff --git a/test/test_mutable_binheap.jl b/test/test_mutable_binheap.jl
index b600566..e12c123 100644
--- a/test/test_mutable_binheap.jl
+++ b/test/test_mutable_binheap.jl
@@ -78,6 +78,12 @@ end
         @test true
     end
 
+    @testset "Type Aliases" begin
+        # https://github.com/JuliaCollections/DataStructures.jl/issues/686
+        @test MutableBinaryMaxHeap{Int}() isa MutableBinaryMaxHeap{Int}
+        @test MutableBinaryMinHeap{Int}() isa MutableBinaryMinHeap{Int}
+    end
+
     @testset "basic tests" begin
         h = MutableBinaryMinHeap{Int}()