Repository: JuliaCollections/DataStructures.jl (julia)

Issue:
Use `push!` and `pop!` for `PriorityQueue` etc
We should use `push!` and `pop!` instead of `enqueue!` and `dequeue!`, 
so that different data structures are interchangeable without changing code.

cf. #289

Pull request description:
I took a stab at the remaining part of #296. Please note my [comment on discourse](https://discourse.julialang.org/t/taking-push-and-pop-seriously/34326/20?u=jonas-schulze) on instead using `put!` and `take!`, but I think a consistent API is more important now.

If the refactor of `popfirst!` to match `eltype` went too far (*breaking change*), I can drop the corresponding commit. Also, I for now deprecated `enqueue(pq, key, val)` in favor of `Base.push!(pq, key=>val)` instead of `Base.insert!(pq, key, val)`. Less is more, I think. `Dict` doesn't have `push!` nor `insert!`.

This is ready for comments, but there are some parts missing:

- [x] Decide on refactor of `popfirst!` (Edit: it's fine)
- [x] Decide on `push!` vs `insert!` (Edit: it's ok as it is)
- [x] Update docs

Close #296

Patch:
diff --git a/docs/src/priority-queue.md b/docs/src/priority-queue.md
index 188d04bbd..1fa059347 100644
--- a/docs/src/priority-queue.md
+++ b/docs/src/priority-queue.md
@@ -14,11 +14,9 @@ Usage:
 ```julia
 PriorityQueue{K, V}()     # construct a new priority queue with keys of type K and priorities of type V (forward ordering by default)
 PriorityQueue{K, V}(ord)  # construct a new priority queue with the given types and ordering ord (Base.Order.Forward or Base.Order.Reverse)
-enqueue!(pq, k, v)        # insert the key k into pq with priority v
-enqueue!(pq, k=>v)        # (same, using Pairs)
-dequeue!(pq)              # remove and return the lowest priority key
-dequeue_pair!(pq)         # remove and return the lowest priorty key and value
-peek(pq)                  # return the lowest priority key and value without removing it
+push!(pq, k=>v)           # insert the key k into pq with priority v
+popfirst!(pq)             # remove and return the lowest priority key and value
+first(pq)                 # return the lowest priority key and value without removing it
 delete!(pq, k)            # delete the mapping for the given key in a priority queue, and return the priority queue.
 ```
 
@@ -28,8 +26,7 @@ inserted and priorities accessed or changed using indexing notation.
 Examples:
 
 ```jldoctest
-julia> # Julia code
-       pq = PriorityQueue();
+julia> pq = PriorityQueue();
 
 julia> # Insert keys with associated priorities
        pq["a"] = 10; pq["b"] = 5; pq["c"] = 15; pq
@@ -45,7 +42,9 @@ PriorityQueue{Any, Any, Base.Order.ForwardOrdering} with 3 entries:
   "b" => 5
   "c" => 15
 ```
-It is also possible to iterate over the priorities and elements of the queue in sorted order. 
+
+It is also possible to iterate over the priorities and elements of the queue in sorted order.
+
 ```jldoctest
 julia> pq = PriorityQueue("a"=>2, "b"=>1, "c"=>3)
 PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
@@ -67,6 +66,7 @@ b
 a
 c
 ```
+
 ```@meta
 DocTestSetup = nothing
 ```
diff --git a/src/DataStructures.jl b/src/DataStructures.jl
index 6263be219..11c0804ad 100644
--- a/src/DataStructures.jl
+++ b/src/DataStructures.jl
@@ -5,6 +5,9 @@ module DataStructures
                 isbitsunion, isiterable, dict_with_eltype, KeySet, Callable, _tablesz,
                 findnextnot, unsafe_getindex, unsafe_setindex!, peek
 
+    # Exports for old version of julia where Base doesn't export this
+    export peek
+    export popat!
 
     using Compat # Provides Base.Order.ReverseOrdering(). May remove this line with julia 1.4
     using OrderedCollections
@@ -15,7 +18,6 @@ module DataStructures
     export complement, complement!
 
     export Deque, Stack, Queue, CircularDeque
-    export enqueue!, dequeue!, dequeue_pair!, update!
     export capacity, num_blocks, top_with_handle, sizehint!
 
     export Accumulator, counter, reset!, inc!, dec!
@@ -27,6 +29,7 @@ module DataStructures
     export MutableBinaryHeap, MutableBinaryMinHeap, MutableBinaryMaxHeap
     export heapify!, heapify, heappop!, heappush!, isheap
     export BinaryMinMaxHeap, popmin!, popmax!, popall!
+    export update!
 
     export Trie, subtrie, keys_with_prefix, partial_path, find_prefixes
 
@@ -100,7 +103,7 @@ module DataStructures
     export status
     export deref_key, deref_value, deref, advance, regress
 
-    export PriorityQueue, peek
+    export PriorityQueue
 
     include("priorityqueue.jl")
     include("sparse_int_set.jl")
diff --git a/src/deprecations.jl b/src/deprecations.jl
index c9b102410..673fafe7e 100644
--- a/src/deprecations.jl
+++ b/src/deprecations.jl
@@ -9,4 +9,16 @@ Base.@deprecate_binding IntDisjointSets IntDisjointSet
 @deprecate DisjointSets(xs...) DisjointSet(xs)
 # Enqueue and dequeue deprecations
 @deprecate enqueue!(q::Queue, x) Base.push!(q, x)
+@deprecate enqueue!(q::PriorityQueue, x) Base.push!(q, x)
+@deprecate enqueue!(q::PriorityQueue, k, v) Base.push!(q, k=>v)
 @deprecate dequeue!(q::Queue) Base.popfirst!(q)
+@deprecate dequeue!(q::PriorityQueue) Base.popfirst!(q).first # maybe better: `val, _ = popfirst!(pq)`
+@deprecate dequeue!(q::PriorityQueue, x) popat!(q, x).first
+@deprecate dequeue_pair!(q::PriorityQueue) Base.popfirst!(q)
+@deprecate dequeue_pair!(q::PriorityQueue, key) popat!(q, key)
+
+function Base.peek(q::PriorityQueue)
+    Expr(:meta, :noinline)
+    Base.depwarn("`peek(q::PriorityQueue)` is deprecated, use `first(q)` instead.", :peek)
+    first(q)
+end
diff --git a/src/priorityqueue.jl b/src/priorityqueue.jl
index ba499447a..88d7665e9 100644
--- a/src/priorityqueue.jl
+++ b/src/priorityqueue.jl
@@ -7,13 +7,13 @@
     PriorityQueue{K, V}([ord])
 
 Construct a new [`PriorityQueue`](@ref), with keys of type
-`K` and values/priorites of type `V`.
+`K` and values/priorities of type `V`.
 If an order is not given, the priority queue is min-ordered using
 the default comparison for `V`.
 
 A `PriorityQueue` acts like a `Dict`, mapping values to their
-priorities, with the addition of a `dequeue!` function to remove the
-lowest priority element.
+priorities. New elements are added using `push!` and retrieved
+using `popfirst!` or `popat!` based on their priority.
 
 ```jldoctest
 julia> PriorityQueue(Base.Order.Forward, "a" => 2, "b" => 3, "c" => 1)
@@ -117,12 +117,12 @@ Base.isempty(pq::PriorityQueue) = isempty(pq.xs)
 Base.haskey(pq::PriorityQueue, key) = haskey(pq.index, key)
 
 """
-    peek(pq)
+    first(pq)
 
 Return the lowest priority key and value from a priority queue without removing that
-key from the queue.
+pair from the queue.
 """
-Base.peek(pq::PriorityQueue) = pq.xs[1]
+Base.first(pq::PriorityQueue) = first(pq.xs)
 
 function percolate_down!(pq::PriorityQueue, i::Integer)
     x = pq.xs[i]
@@ -183,14 +183,14 @@ end
 function Base.get!(pq::PriorityQueue, key, default)
     i = get(pq.index, key, 0)
     if i == 0
-        enqueue!(pq, key, default)
+        push!(pq, key=>default)
         return default
     else
         return pq.xs[i].second
     end
 end
 
-# Change the priority of an existing element, or equeue it if it isn't present.
+# Change the priority of an existing element, or enqueue it if it isn't present.
 function Base.setindex!(pq::PriorityQueue{K, V}, value, key) where {K,V}
     i = get(pq.index, key, 0)
     if i != 0
@@ -202,24 +202,24 @@ function Base.setindex!(pq::PriorityQueue{K, V}, value, key) where {K,V}
             percolate_up!(pq, i)
         end
     else
-        enqueue!(pq, key, value)
+        push!(pq, key=>value)
     end
     return value
 end
 
 """
-    enqueue!(pq, k=>v)
+    push!(pq, k=>v)
 
 Insert the a key `k` into a priority queue `pq` with priority `v`.
 
 ```jldoctest
-julia> a = PriorityQueue(PriorityQueue("a"=>1, "b"=>2, "c"=>3))
+julia> a = PriorityQueue("a"=>1, "b"=>2, "c"=>3)
 PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
   "a" => 1
   "b" => 2
   "c" => 3
 
-julia> enqueue!(a, "d"=>4)
+julia> push!(a, "d"=>4)
 PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 4 entries:
   "a" => 1
   "b" => 2
@@ -227,7 +227,7 @@ PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 4 entries:
   "d" => 4
 ```
 """
-function enqueue!(pq::PriorityQueue{K,V}, pair::Pair{K,V}) where {K,V}
+function Base.push!(pq::PriorityQueue{K,V}, pair::Pair{K,V}) where {K,V}
     key = pair.first
     if haskey(pq, key)
         throw(ArgumentError("PriorityQueue keys must be unique"))
@@ -239,44 +239,12 @@ function enqueue!(pq::PriorityQueue{K,V}, pair::Pair{K,V}) where {K,V}
     return pq
 end
 
-"""
-    enqueue!(pq, k, v)
-
-Insert the a key `k` into a priority queue `pq` with priority `v`.
+Base.push!(pq::PriorityQueue{K,V}, kv::Pair) where {K,V} = push!(pq, Pair{K,V}(kv.first, kv.second))
 
 """
-enqueue!(pq::PriorityQueue, key, value) = enqueue!(pq, key=>value)
-enqueue!(pq::PriorityQueue{K,V}, kv) where {K,V} = enqueue!(pq, Pair{K,V}(kv.first, kv.second))
+    popfirst!(pq)
 
-"""
-    dequeue!(pq)
-
-Remove and return the lowest priority key from a priority queue.
-
-```jldoctest
-julia> a = PriorityQueue(Base.Order.Forward, ["a" => 2, "b" => 3, "c" => 1])
-PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
-  "c" => 1
-  "a" => 2
-  "b" => 3
-
-julia> dequeue!(a)
-"c"
-
-julia> a
-PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 2 entries:
-  "a" => 2
-  "b" => 3
-```
-"""
-dequeue!(pq::PriorityQueue) = dequeue_pair!(pq).first
-
-dequeue!(pq::PriorityQueue, key) = dequeue_pair!(pq, key).first
-
-"""
-    dequeue_pair!(pq)
-
-Remove and return a the lowest priority key and value from a priority queue as a pair.
+Remove and return the lowest priority key and value from a priority queue as a pair.
 
 ```jldoctest
 julia> a = PriorityQueue(Base.Order.Forward, "a" => 2, "b" => 3, "c" => 1)
@@ -285,7 +253,7 @@ PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 3 entries:
   "a" => 2
   "b" => 3
 
-julia> dequeue_pair!(a)
+julia> popfirst!(a)
 "c" => 1
 
 julia> a
@@ -294,7 +262,7 @@ PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 2 entries:
   "b" => 3
 ```
 """
-function dequeue_pair!(pq::PriorityQueue)
+function Base.popfirst!(pq::PriorityQueue)
     x = pq.xs[1]
     y = pop!(pq.xs)
     if !isempty(pq)
@@ -306,10 +274,14 @@ function dequeue_pair!(pq::PriorityQueue)
     return x
 end
 
-function dequeue_pair!(pq::PriorityQueue, key)
+if isdefined(Base, :popat!)  # We will overload if it is defined, else we define on our own
+    import Base: popat!
+end
+
+function popat!(pq::PriorityQueue, key)
     idx = pq.index[key]
     force_up!(pq, idx)
-    dequeue_pair!(pq)
+    popfirst!(pq)
 end
 
 """
@@ -330,7 +302,7 @@ PriorityQueue{String, Int64, Base.Order.ForwardOrdering} with 2 entries:
 ```
 """
 function Base.delete!(pq::PriorityQueue, key)
-    dequeue_pair!(pq, key)
+    popat!(pq, key)
     return pq
 end
 
@@ -386,7 +358,7 @@ function Base.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
+        return popfirst!(state.pq), state
     else
         _iterate(pq, iterate(pq.index))
     end
@@ -394,7 +366,7 @@ end
 
 function Base.iterate(pq::PriorityQueue, state::_PQIteratorState)
     isempty(state.pq) && return nothing
-    return dequeue_pair!(state.pq), state
+    return popfirst!(state.pq), state
 end
 
 Base.iterate(pq::PriorityQueue, i) = _iterate(pq, iterate(pq.index, i))


Test patch:
diff --git a/test/test_deprecations.jl b/test/test_deprecations.jl
index 21c6b9eec..565e42883 100644
--- a/test/test_deprecations.jl
+++ b/test/test_deprecations.jl
@@ -42,7 +42,7 @@ end
     end
 end
 
-@testset "enqueue! dequeue!" begin
+@testset "Queue enqueue! dequeue!" begin
     s = Queue{Int}(5)
     n = 100
 
@@ -76,3 +76,43 @@ end
         @test length(s) == n - i
     end
 end
+
+@testset "PriorityQueue enqueue! dequeue!" begin
+    s = PriorityQueue{Int,Int}()
+    n = 100
+
+    @test length(s) == 0
+    @test isempty(s)
+    @test_throws BoundsError first(s)
+    @test_throws BoundsError dequeue!(s)
+
+    for i = 1 : n
+        enqueue!(s, i=>i)
+        @test first(s) == (1=>1)
+        @test !isempty(s)
+        @test length(s) == i
+    end
+
+    for i = 1 : n
+        x = dequeue!(s)
+        @test x == i
+        if i < n
+            @test first(s) == (i+1 => i+1)
+        else
+            @test_throws BoundsError first(s)
+        end
+        @test isempty(s) == (i == n)
+        @test length(s) == n - i
+    end
+end
+
+@testset "peek" begin
+    pq = PriorityQueue{Int,Int}()
+    push!(pq, 1 => 1)
+    push!(pq, 2 => 2)
+    @test peek(pq) == (1=>1)
+    pq = PriorityQueue{Int,Int}()
+    push!(pq, 2 => 2)
+    push!(pq, 1 => 1)
+    @test peek(pq) == (1=>1)
+end
diff --git a/test/test_priority_queue.jl b/test/test_priority_queue.jl
index 4d1a0a8fc..35dc8e611 100644
--- a/test/test_priority_queue.jl
+++ b/test/test_priority_queue.jl
@@ -7,9 +7,9 @@ import Base.Order.Reverse
 
     # Test dequeing in sorted order.
     function test_issorted!(pq::PriorityQueue, priorities, rev=false)
-        last = dequeue!(pq)
+        last, _ = popfirst!(pq)
         while !isempty(pq)
-            value = dequeue!(pq)
+            value, _ = popfirst!(pq)
             if !rev
                 @test priorities[last] <= priorities[value]
             else
@@ -23,7 +23,7 @@ import Base.Order.Reverse
         i = 0
         while !isempty(pq)
             krqst =  keys[i+=1]
-            krcvd = dequeue!(pq, krqst)
+            krcvd, _ = popat!(pq, krqst)
             @test krcvd == krqst
         end
     end
@@ -77,17 +77,17 @@ import Base.Order.Reverse
         @testset "construction from pairs" begin
             @testset "pq9" begin
                 pq9 = PriorityQueue('a'=>1, 'b'=>2)
-                @test peek(pq9) == ('a'=>1)
+                @test first(pq9) == ('a'=>1)
             end
 
             @testset "pq10" begin
                 pq10 = PriorityQueue(Reverse, 'a'=>1, 'b'=>2)
-                @test peek(pq10) == ('b'=>2)
+                @test first(pq10) == ('b'=>2)
             end
 
             @testset "pq11" begin
                 pq11 = PriorityQueue(Pair{Char}['a'=>1,'b'=>2])
-                @test peek(pq11) == ('a'=>1)
+                @test first(pq11) == ('a'=>1)
             end
         end
 
@@ -110,15 +110,15 @@ import Base.Order.Reverse
     @testset "PriorityQueueMethods" begin
         pq1 = PriorityQueue('a'=>1, 'b'=>2)
 
-        @testset "peek/get/dequeue!/get!" begin
-            @test peek(pq1) == ('a'=>1)
+        @testset "first/get/popfirst!/get!" begin
+            @test first(pq1) == ('a'=>1)
             @test get(pq1, 'a', 0) == 1
             @test get(pq1, 'c', 0) == 0
             @test get!(pq1, 'b', 20) == 2
-            @test dequeue!(pq1) == 'a'
-            @test dequeue!(pq1) == 'b'
+            @test popfirst!(pq1).first == 'a'
+            @test popfirst!(pq1).first == 'b'
             @test get!(pq1, 'c', 0) == 0
-            @test peek(pq1) == ('c'=>0)
+            @test first(pq1) == ('c'=>0)
             @test get!(pq1, 'c', 3) == 0
         end
 
@@ -127,39 +127,39 @@ import Base.Order.Reverse
         ks, vs = 1:n, rand(1:pmax, n)
         priorities = Dict(zip(ks, vs))
 
-        @testset "peek" begin
+        @testset "first" begin
             pq1 = PriorityQueue(priorities)
             lowpri = findmin(vs)
-            @test peek(pq1)[2] == pq1[ks[lowpri[2]]]
+            @test first(pq1)[2] == pq1[ks[lowpri[2]]]
         end
 
         @testset "enqueue error throw" begin
             ks, vs = 1:n, rand(1:pmax, n)
             pq = PriorityQueue(zip(ks, vs))
-            @test_throws ArgumentError enqueue!(pq, 1, 10)
+            @test_throws ArgumentError push!(pq, 1=>10)
         end
 
         @testset "Iteration" begin
             pq = PriorityQueue(priorities)
             pq2 = PriorityQueue()
             for kv in pq
-                enqueue!(pq2, kv)
+                push!(pq2, kv)
             end
             @test pq == pq2
         end
 
-        @testset "enqueing pairs via enqueue!" begin
+        @testset "enqueing pairs via push!" begin
             pq = PriorityQueue()
             for kv in priorities
-                enqueue!(pq, kv)
+                push!(pq, kv)
             end
             test_issorted!(pq, priorities)
         end
 
-        @testset "enqueing values via enqueue!" begin
+        @testset "enqueing values via push!" begin
             pq = PriorityQueue()
             for (k, v) in priorities
-                enqueue!(pq, k, v)
+                push!(pq, k=>v)
             end
             test_issorted!(pq, priorities)
         end
@@ -190,23 +190,24 @@ import Base.Order.Reverse
 
         @testset "dequeuing" begin
             pq = PriorityQueue(priorities)
-            @test_throws KeyError dequeue!(pq, 0)
+            @test_throws KeyError popat!(pq, 0)
 
-            @test 10 == dequeue!(pq, 10)
+            v, _ = popat!(pq, 10)
+            @test v == 10
             while !isempty(pq)
-                @test 10 != dequeue!(pq)
+                v, _ = popfirst!(pq)
+                @test v != 10
             end
 
             pq = PriorityQueue(1.0 => 1)
-            @test dequeue!(pq, 1.0f0) isa Float64
-        end
+            @test popat!(pq, 1.0f0) isa eltype(pq)
+            @test eltype(pq) == Pair{Float64, Int64}
 
-        @testset "dequeuing pair" begin
             priorities2 = Dict(zip('a':'e', 5:-1:1))
             pq = PriorityQueue(priorities2)
-            @test_throws KeyError dequeue_pair!(pq, 'g')
-            @test dequeue_pair!(pq) == ('e'=> 1)
-            @test dequeue_pair!(pq, 'b') == ('b'=>4)
+            @test_throws KeyError popat!(pq, 'g')
+            @test popfirst!(pq) == ('e'=> 1)
+            @test popat!(pq, 'b') == ('b'=>4)
             @test length(pq) == 3
         end
 
@@ -222,7 +223,7 @@ import Base.Order.Reverse
             @test !isempty(pq)
             empty!(pq)
             @test isempty(pq)
-            enqueue!(pq, "a"=>2)
+            push!(pq, "a"=>2)
             @test length(pq) == 1
         end
     end