Repository: JuliaCollections/DataStructures.jl
Pull request #493 (2019-04-09 21:22:14)

Issue#369: Ordered iterator interface for priority queue
Ordered iterator interface for priority queues. 

The original unordered interface is preserved as that is used for most common functionalities like copying etc. This interface is a kind of a heapsort implementation but in place store has not been used. 

sambitdash: Fixes issue #369 
codecov[bot]: # [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=h1) Report
> Merging [#493](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/640379baf779d93abbfcd7567af996bab75dabf7?src=pr&el=desc) will **decrease** coverage by `0.23%`.
> The diff coverage is `53.33%`.

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

```diff
@@            Coverage Diff            @@
##           master    #493      +/-   ##
=========================================
- Coverage   89.33%   89.1%   -0.24%     
=========================================
  Files          31      31              
  Lines        2372    2386      +14     
=========================================
+ Hits         2119    2126       +7     
- Misses        253     260       +7
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/DataStructures.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493/diff?src=pr&el=tree#diff-c3JjL0RhdGFTdHJ1Y3R1cmVzLmps) | `100% <ø> (ø)` | :arrow_up: |
| [src/priorityqueue.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493/diff?src=pr&el=tree#diff-c3JjL3ByaW9yaXR5cXVldWUuamw=) | `92.59% <53.33%> (-4.93%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?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/493?src=pr&el=footer). Last update [640379b...2a7224c](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

codecov[bot]: # [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=h1) Report
> Merging [#493](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/640379baf779d93abbfcd7567af996bab75dabf7?src=pr&el=desc) will **decrease** coverage by `0.23%`.
> The diff coverage is `53.33%`.

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

```diff
@@            Coverage Diff            @@
##           master    #493      +/-   ##
=========================================
- Coverage   89.33%   89.1%   -0.24%     
=========================================
  Files          31      31              
  Lines        2372    2386      +14     
=========================================
+ Hits         2119    2126       +7     
- Misses        253     260       +7
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/DataStructures.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493/diff?src=pr&el=tree#diff-c3JjL0RhdGFTdHJ1Y3R1cmVzLmps) | `100% <ø> (ø)` | :arrow_up: |
| [src/priorityqueue.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493/diff?src=pr&el=tree#diff-c3JjL3ByaW9yaXR5cXVldWUuamw=) | `92.59% <53.33%> (-4.93%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?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/493?src=pr&el=footer). Last update [640379b...2a7224c](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/493?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

oxinabox: Should we call this `sort`?

sambitdash: I would be OK with sort if we had implementation using the in place array. Since we are making a copy it's more like an overlay iterator.
sambitdash: @kmsquire please review again. I guess the concerns raised on the default iteration is now resolved. I did a quick scan of `AbstractDict`. Did not find an obvious usage of `iterator` which will not get the advantage of an ordered iteration. For example, `keys` and `values` should be ordered by priority as well. `copy` or its implementation `merge!` pick up one by one key value pairs. Do you think I should implement the merge! using unordered iteration option?
sambitdash: `copy` on PQs fail. Here is the result. 

```
julia> pq1 = copy(pq)
Dict{String,Int64} with 3 entries:
  "c" => 15
  "b" => 5
  "a" => 10
```
Copying creates a `Dict` which is incorrect behavior. This needs the `empty`() method be defined for PQs as well,  just as `empty!()`. 
sambitdash: @oxinabox and @kmsquire The last check-in will fail on `SortedDict` tests due to ambiguous declarations. I am defining the `merge!` interface to iterate unordered from `PriorityQueue`.  Would you be able to comment what can be going wrong here. With `empty()` declared the `copy` issue is fixed now. 
oxinabox: Can you post the error message?

Generally that one includes instructions about how to fix it
kmsquire: Not enough time to review right now, will try to get to it this weekend.
sambitdash: > Not enough time to review right now, will try to get to it this weekend.

@kmsquire No hurry. Take your time. 
sambitdash: Error Message:

```
17.31s$ julia --check-bounds=yes --color=yes -e "if VERSION < v\"0.7.0-DEV.5183\"; Pkg.test(\"${JL_PKG}\", coverage=true); else using Pkg; Pkg.test(coverage=true); end"
   Testing DataStructures
 Resolving package versions...
 Installed Primes ─ v0.4.0
Skipping Base.active_repl
Skipping Base.active_repl_backend
Test Failed at /home/travis/build/JuliaCollections/DataStructures.jl/test/runtests.jl:8
  Expression: [] == detect_ambiguities(Base, Core, DataStructures)
   Evaluated: Any[] == Tuple{Method,Method}[(merge!(d::AbstractDict{K,V}, other::PriorityQueue{K,V,O} where O<:Base.Order.Ordering) where {K, V} in DataStructures at /home/travis/build/JuliaCollections/DataStructures.jl/src/priorityqueue.jl:363, merge!(m::SortedDict{K,D,Ord}, others::AbstractDict{K,D}...) where {K, D, Ord<:Ordering} in DataStructures at /home/travis/build/JuliaCollections/DataStructures.jl/src/sorted_dict.jl:577)]
ERROR: LoadError: There was an error during testing
in expression starting at /home/travis/build/JuliaCollections/DataStructures.jl/test/runtests.jl:8
ERROR: Package DataStructures errored during testing
Stacktrace:
 [1] pkgerror(::String, ::Vararg{String,N} where N) at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.0/Pkg/src/Types.jl:120
 [2] #test#65(::Bool, ::Function, ::Pkg.Types.Context, ::Array{Pkg.Types.PackageSpec,1}) at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.0/Pkg/src/Operations.jl:1357
 [3] #test at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:0 [inlined]
 [4] #test#42(::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::Pkg.Types.Context, ::Array{Pkg.Types.PackageSpec,1}) at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:273
 [5] #test#41 at ./none:0 [inlined]
 [6] #test at ./none:0 [inlined]
 [7] #test#38 at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.0/Pkg/src/API.jl:252 [inlined]
 [8] (::getfield(Pkg.API, Symbol("#kw##test")))(::NamedTuple{(:coverage,),Tuple{Bool}}, ::typeof(Pkg.API.test)) at ./none:0
 [9] top-level scope at none:1
```
sambitdash: All errors are addressed. Please review the code. I will add test cases for `merge!` once we agree to go with these changes. 

Patch:
diff --git a/Project.toml b/Project.toml
index 14c06b6..5dcd6a0 100644
--- a/Project.toml
+++ b/Project.toml
@@ -6,14 +6,14 @@ version = "0.14.0"
 InteractiveUtils = "b77e0a4c-d291-57a0-90e8-8db25a27a240"
 OrderedCollections = "bac558e1-5e72-5ebc-8fee-abe8a469f55d"
 
+[compat]
+OrderedCollections = "1.0.1"
+
 [extras]
-Test = "8dfed614-e22c-5e08-85e1-65c5234f0b40"
 Primes = "27ebfcd6-29c5-5fa9-bf4b-fb8fc14df3ae"
 Random = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"
 Serialization = "9e88b42a-f829-5b0c-bbe9-9e923198166b"
+Test = "8dfed614-e22c-5e08-85e1-65c5234f0b40"
 
 [targets]
 test = ["Test", "Primes", "Random", "Serialization"]
-
-[compat]
-OrderedCollections = "1.0.1"
diff --git a/docs/src/heaps.md b/docs/src/heaps.md
index 51c2606..2d43930 100644
--- a/docs/src/heaps.md
+++ b/docs/src/heaps.md
@@ -18,6 +18,7 @@ push!(h, v)       # add a value to the heap
 top(h)            # return the top value of a heap
 
 pop!(h)           # removes the top value, and returns it
+
 ```
 
 Mutable heaps (values can be changed after being pushed to a heap) are
@@ -29,6 +30,8 @@ i = push!(h, v)              # adds a value to the heap and and returns a handle
 
 update!(h, i, v)             # updates the value of an element (referred to by the handle i)
 
+delete!(h, i)               # deletes the node with handle i from the heap
+
 v, i = top_with_handle(h)    # returns the top value of a heap and its handle
 ```
 
diff --git a/src/heaps.jl b/src/heaps.jl
index 94cef7e..5400f8a 100644
--- a/src/heaps.jl
+++ b/src/heaps.jl
@@ -37,6 +37,9 @@
 #   - update!(h, i, v)    updates the value of an element
 #                         (referred to by the handle i)
 #
+#   - delete!(h, i)      deletes the node with
+#                         handle i from the heap
+#
 #   - top_with_handle(h)  return the top value of a heap
 #                         and its handle
 #
diff --git a/src/heaps/mutable_binary_heap.jl b/src/heaps/mutable_binary_heap.jl
index 864d01a..b91351a 100644
--- a/src/heaps/mutable_binary_heap.jl
+++ b/src/heaps/mutable_binary_heap.jl
@@ -101,10 +101,10 @@ function _heap_bubble_down!(comp::Comp,
 end
 
 function _binary_heap_pop!(comp::Comp,
-    nodes::Vector{MutableBinaryHeapNode{T}}, nodemap::Vector{Int}) where {Comp,T}
+    nodes::Vector{MutableBinaryHeapNode{T}}, nodemap::Vector{Int}, nd_id::Int=1) where {Comp,T}
 
-    # extract root node
-    rt = nodes[1]
+    # extract node
+    rt = nodes[nd_id]
     v = rt.value
     @inbounds nodemap[rt.handle] = 0
 
@@ -112,12 +112,16 @@ function _binary_heap_pop!(comp::Comp,
         # clear
         empty!(nodes)
     else
-        # place last node to root
-        @inbounds nodes[1] = new_rt = pop!(nodes)
-        @inbounds nodemap[new_rt.handle] = 1
+        # move the last node to the position of the removed node
+        @inbounds nodes[nd_id] = new_rt = pop!(nodes)
+        @inbounds nodemap[new_rt.handle] = nd_id
 
         if length(nodes) > 1
-            _heap_bubble_down!(comp, nodes, nodemap, 1)
+            if compare(comp, new_rt.value, v)
+                _heap_bubble_up!(comp, nodes, nodemap, nd_id)
+            else
+                _heap_bubble_down!(comp, nodes, nodemap, nd_id)
+            end
         end
     end
     v
@@ -252,5 +256,16 @@ function update!(h::MutableBinaryHeap{T}, i::Int, v) where T
     end
 end
 
+"""
+    delete!{T}(h::MutableBinaryHeap{T}, i::Int)
+
+Deletes the element with handle `i` from heap `h` . 
+"""     
+function delete!(h::MutableBinaryHeap{T}, i::Int) where T
+     nd_id = h.node_map[i]
+    _binary_heap_pop!(h.comparer, h.nodes, h.node_map, nd_id)
+    h
+end
+
 setindex!(h::MutableBinaryHeap, v, i::Int) = update!(h, i, v)
 getindex(h::MutableBinaryHeap, i::Int) = h.nodes[h.node_map[i]].value
diff --git a/src/priorityqueue.jl b/src/priorityqueue.jl
index 2479dc5..7a02f81 100644
--- a/src/priorityqueue.jl
+++ b/src/priorityqueue.jl
@@ -35,6 +35,8 @@ struct PriorityQueue{K,V,O<:Ordering} <: AbstractDict{K,V}
         new{K,V,O}(Vector{Pair{K,V}}(), o, Dict{K, Int}())
     end
 
+    PriorityQueue{K, V, O}(xs::Array{Pair{K,V}, 1}, o::O, index::Dict{K, Int}) where {K,V,O<:Ordering} = new(xs, o, index)
+
     function PriorityQueue{K,V,O}(o::O, itr) where {K,V,O<:Ordering}
         xs = Vector{Pair{K,V}}(undef, length(itr))
         index = Dict{K, Int}()
@@ -56,6 +58,10 @@ struct PriorityQueue{K,V,O<:Ordering} <: AbstractDict{K,V}
     end
 end
 
+# A copy constructor
+PriorityQueue(xs::Array{Pair{K,V}, 1}, o::O, index::Dict{K, Int}) where {K,V,O<:Ordering} =
+    PriorityQueue{K,V,O}(xs, o, index)
+
 # Any-Any constructors
 PriorityQueue(o::Ordering=Forward) = PriorityQueue{Any,Any,typeof(o)}(o)
 
@@ -351,13 +357,62 @@ function empty!(pq::PriorityQueue)
     pq
 end
 
+empty(pq::PriorityQueue) = PriorityQueue(empty(pq.xs), pq.o, empty(pq.index))
+
+merge!(d::SortedDict, other::PriorityQueue) = invoke(merge!, Tuple{AbstractDict, PriorityQueue}, d, other)
+
+function merge!(d::AbstractDict, other::PriorityQueue)
+    next = iterate(other, false)
+    while next !== nothing
+        (k, v), state = next
+        d[k] = v
+        next = iterate(other, state)
+    end
+    return d
+end
+
+function merge!(combine::Function, d::AbstractDict, other::PriorityQueue)
+    next = iterate(other, false)
+    while next !== nothing
+        (k, v), state = next
+        d[k] = haskey(d, k) ? combine(d[k], v) : v
+        next = iterate(other, state)
+    end
+    return d
+end
+
+# Opaque not to be exported. 
+mutable struct _PQIteratorState{K, V, O <: Ordering}
+    pq::PriorityQueue{K, V, O}
+    _PQIteratorState{K, V, O}(pq::PriorityQueue{K, V, O}) where {K, V, O <: Ordering} = new(pq)
+end
+
+_PQIteratorState(pq::PriorityQueue{K, V, O}) where {K, V, O <: Ordering} = _PQIteratorState{K, V, O}(pq)
+
 # Unordered iteration through key value pairs in a PriorityQueue
+# O(n) iteration.
 function _iterate(pq::PriorityQueue, state)
-    state == nothing && return nothing
     (k, idx), i = state
     return (pq.xs[idx], i)
 end
+_iterate(pq::PriorityQueue, ::Nothing) = nothing
 
-iterate(pq::PriorityQueue) = _iterate(pq, iterate(pq.index))
+iterate(pq::PriorityQueue, ::Nothing) = nothing
 
+function iterate(pq::PriorityQueue, ordered::Bool=true)
+    if ordered 
+        isempty(pq) && return nothing
+        state = _PQIteratorState(PriorityQueue(copy(pq.xs), pq.o, copy(pq.index)))
+        return dequeue_pair!(state.pq), state
+    else
+        _iterate(pq, iterate(pq.index))
+    end
+end
+
+function iterate(pq::PriorityQueue, state::_PQIteratorState)
+    isempty(state.pq) && return nothing
+    return dequeue_pair!(state.pq), state
+end
+    
 iterate(pq::PriorityQueue, i) = _iterate(pq, iterate(pq.index, i))
+


Test patch:
diff --git a/test/test_mutable_binheap.jl b/test/test_mutable_binheap.jl
index 9efa7ca..ed2f72c 100644
--- a/test/test_mutable_binheap.jl
+++ b/test/test_mutable_binheap.jl
@@ -157,6 +157,29 @@ end
         @test pop!(h) == 2
         @test isequal(heap_values(h), [7, 10])
         @test isequal(list_values(h), [10, 7])
+        
+    end
+
+    @testset "test delete!" begin
+        vs=[1,2,4,6,3]
+        h = MutableBinaryMinHeap(vs)
+
+        @test isequal(heap_values(delete!(h,1)), [2, 3, 4, 6])
+        @test isequal(heap_values(delete!(h,5)), [2, 6, 4])
+        @test_throws BoundsError delete!(h,10)
+        @test_throws BoundsError delete!(h,0)
+        @test_throws BoundsError delete!(h,-5)
+        @test pop!(h) == 2
+        @test pop!(h) == 4
+        push!(h,2)
+        @test pop!(h) == 2
+        @test pop!(h) == 6
+        @test isempty(h)
+        #bubble_up test
+        vv = [1, 9, 22, 17, 11, 33, 27, 21, 19]
+        hp = MutableBinaryMinHeap(vv)
+        delete!(hp, 6)
+        @test isequal(extract_all!(hp), [1, 9, 11, 17, 19, 21, 22, 27])
     end
 
     @testset "test update! and top_with_handle" begin
diff --git a/test/test_priority_queue.jl b/test/test_priority_queue.jl
index 111dfba..456814a 100644
--- a/test/test_priority_queue.jl
+++ b/test/test_priority_queue.jl
@@ -225,8 +225,51 @@ import Base.Order.Reverse
     end
 
     @testset "Iteration" begin
-        pq = PriorityQueue('a'=>'A')
-        @test collect(pq) == ['a' => 'A']
+        pq = PriorityQueue(["a" => 10, "b" => 5, "c" => 15])
+        @test collect(pq)         == ["b" => 5, "a" => 10, "c" => 15]
+        @test collect(keys(pq))   == ["b", "a", "c"]
+        @test collect(values(pq)) == [5, 10, 15]
+    end
+
+    @testset "UnorderedIteration" begin
+        pq = PriorityQueue(["a" => 10, "b" => 5, "c" => 15])
+        res = Pair{String, Int}[]
+        next = iterate(pq, false)
+        while next !== nothing
+            p, i = next
+            push!(res, p)
+            next = iterate(pq, i)
+        end
+        @test Set(res) == Set(["a" => 10, "b" => 5, "c" => 15])
+        empty!(res)
+        next = iterate(pq, true)
+        while next !== nothing
+            p, i = next
+            push!(res, p)
+            next = iterate(pq, i)
+        end
+        @test res == ["b" => 5, "a" => 10, "c" => 15]
+    end
+
+    # Copy and merge operations in PriorityQueue utilize unordered
+    # iteration
+    @testset "Copy and Merge" begin
+        v = [i for i=10000:-1:1]
+        pq1 = PriorityQueue(zip(v, 10 .* v))
+        @test collect(merge!(Dict(), pq1)) != collect(pq1)
+        pq = PriorityQueue(["a" => 10, "b" => 5, "c" => 15])
+        sd = SortedDict(["d"=>6, "e"=>4])
+        merge!(sd, pq)
+        @test collect(sd) == ["a" => 10, "b" => 5, "c" => 15, "d" => 6, "e" => 4]
+        d = merge!(Dict("d"=> 6), pq)
+        @test Set(collect(d)) == Set(["c" => 15, "b" => 5, "a" => 10, "d" => 6])
+        sd = SortedDict(["c"=>6, "e"=>4])
+        merge!(+, sd, pq)
+        @test collect(sd) == ["a" => 10, "b" => 5, "c" => 21, "e" => 4]
+        pq1 = empty(pq)
+        @test length(pq1) == 0
+        pq1 = copy(pq)
+        @test pq1 isa PriorityQueue
     end
 
     @testset "LowLevelHeapOperations" begin