Repository: JuliaCollections/DataStructures.jl
Pull request #775 (2021-11-17 21:29:42)

Fixed long-standing bug in balanced_tree.jl that corrupted SortedMult…
…iDict

for certain insertions.


Patch:
diff --git a/docs/src/priority-queue.md b/docs/src/priority-queue.md
index 188d04b..1fa0593 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 6263be2..11c0804 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/avl_tree.jl b/src/avl_tree.jl
index bacf1cb..f9f4398 100644
--- a/src/avl_tree.jl
+++ b/src/avl_tree.jl
@@ -14,6 +14,9 @@ end
 
 AVLTreeNode(d) = AVLTreeNode{Any}(d)
 
+Base.setproperty!(x::AVLTreeNode{T}, f::Symbol, v) where {T} =
+    setfield!(x, f, v)
+
 AVLTreeNode_or_null{T} = Union{AVLTreeNode{T}, Nothing}
 
 mutable struct AVLTree{T}
@@ -27,7 +30,7 @@ AVLTree() = AVLTree{Any}()
 
 Base.length(tree::AVLTree) = tree.count
 
-get_height(node::Union{AVLTreeNode, Nothing}) = (node == nothing) ? 0 : node.height
+get_height(node::Union{AVLTreeNode, Nothing}) = (node == nothing) ? Int8(0) : node.height
 
 # balance is the difference of height between leftChild and rightChild of a node.
 function get_balance(node::Union{AVLTreeNode, Nothing})
@@ -40,25 +43,25 @@ end
 
 # computes the height of the subtree, which basically is
 # one added the maximum of the height of the left subtree and right subtree
-compute_height(node::AVLTreeNode) = 1 + max(get_height(node.leftChild), get_height(node.rightChild))
+compute_height(node::AVLTreeNode) = Int8(1) + max(get_height(node.leftChild), get_height(node.rightChild))
 
-get_subsize(node::AVLTreeNode_or_null) = (node == nothing) ? 0 : node.subsize
+get_subsize(node::AVLTreeNode_or_null) = (node == nothing) ? Int32(0) : node.subsize
 
 # compute the subtree size
 function compute_subtree_size(node::AVLTreeNode_or_null)
     if node == nothing
-        return 0
+        return Int32(0)
     else
         L = get_subsize(node.leftChild)
         R = get_subsize(node.rightChild)
-        return (L + R + 1)
+        return (L + R + Int32(1))
     end
 end
 
 """
     left_rotate(node_x::AVLTreeNode)
 
-Performs a left-rotation on `node_x`, updates height of the nodes, and returns the rotated node. 
+Performs a left-rotation on `node_x`, updates height of the nodes, and returns the rotated node.
 """
 function left_rotate(z::AVLTreeNode)
     y = z.rightChild
@@ -75,7 +78,7 @@ end
 """
     right_rotate(node_x::AVLTreeNode)
 
-Performs a right-rotation on `node_x`, updates height of the nodes, and returns the rotated node. 
+Performs a right-rotation on `node_x`, updates height of the nodes, and returns the rotated node.
 """
 function right_rotate(z::AVLTreeNode)
     y = z.leftChild
@@ -90,9 +93,9 @@ function right_rotate(z::AVLTreeNode)
 end
 
 """
-   minimum_node(tree::AVLTree, node::AVLTreeNode) 
+   minimum_node(tree::AVLTree, node::AVLTreeNode)
 
-Returns the AVLTreeNode with minimum value in subtree of `node`. 
+Returns the AVLTreeNode with minimum value in subtree of `node`.
 """
 function minimum_node(node::Union{AVLTreeNode, Nothing})
     while node != nothing && node.leftChild != nothing
@@ -107,17 +110,17 @@ function search_node(tree::AVLTree{K}, d::K) where K
     while node != nothing && node.data != nothing && node.data != d
 
         prev = node
-        if d < node.data 
+        if d < node.data
             node = node.leftChild
         else
             node = node.rightChild
         end
     end
-    
+
     return (node == nothing) ? prev : node
 end
 
-function Base.haskey(tree::AVLTree{K}, d::K) where K 
+function Base.haskey(tree::AVLTree{K}, d::K) where K
     (tree.root == nothing) && return false
     node = search_node(tree, d)
     return (node.data == d)
@@ -125,42 +128,42 @@ end
 
 Base.in(key, tree::AVLTree) = haskey(tree, key)
 
-function Base.insert!(tree::AVLTree{K}, d::K) where K
+function insert_node(node::Nothing, key::K) where K
+    return AVLTreeNode{K}(key)
+end
+function insert_node(node::AVLTreeNode{K}, key::K) where K
+    if key < node.data
+        node.leftChild = insert_node(node.leftChild, key)
+    else
+        node.rightChild = insert_node(node.rightChild, key)
+    end
+
+    node.subsize = compute_subtree_size(node)
+    node.height = compute_height(node)
+    balance = get_balance(node)
 
-    function insert_node(node::Union{AVLTreeNode, Nothing}, key)
-        if node == nothing
-            return AVLTreeNode{K}(key)
-        elseif key < node.data
-            node.leftChild = insert_node(node.leftChild, key)
+    if balance > 1
+        if key < node.leftChild.data
+            return right_rotate(node)
         else
-            node.rightChild = insert_node(node.rightChild, key)
-        end
-        
-        node.subsize = compute_subtree_size(node)
-        node.height = compute_height(node)
-        balance = get_balance(node)
-        
-        if balance > 1
-            if key < node.leftChild.data
-                return right_rotate(node)
-            else
-                node.leftChild = left_rotate(node.leftChild)
-                return right_rotate(node)
-            end
+            node.leftChild = left_rotate(node.leftChild)
+            return right_rotate(node)
         end
+    end
 
-        if balance < -1
-            if key > node.rightChild.data
-                return left_rotate(node)
-            else
-                node.rightChild = right_rotate(node.rightChild)
-                return left_rotate(node)
-            end
+    if balance < -1
+        if key > node.rightChild.data
+            return left_rotate(node)
+        else
+            node.rightChild = right_rotate(node.rightChild)
+            return left_rotate(node)
         end
-
-        return node
     end
 
+    return node
+end
+
+function Base.insert!(tree::AVLTree{K}, d::K) where K
     haskey(tree, d) && return tree
 
     tree.root = insert_node(tree.root, d)
@@ -173,55 +176,54 @@ function Base.push!(tree::AVLTree{K}, key0) where K
     insert!(tree, key)
 end
 
-function Base.delete!(tree::AVLTree{K}, d::K) where K
-
-    function delete_node!(node::Union{AVLTreeNode, Nothing}, key)
-        if key < node.data
-            node.leftChild = delete_node!(node.leftChild, key)
-        elseif key > node.data
-            node.rightChild = delete_node!(node.rightChild, key)
+function delete_node!(node::AVLTreeNode{K}, key::K) where K
+    if key < node.data
+        node.leftChild = delete_node!(node.leftChild, key)
+    elseif key > node.data
+        node.rightChild = delete_node!(node.rightChild, key)
+    else
+        if node.leftChild == nothing
+            result = node.rightChild
+            return result
+        elseif node.rightChild == nothing
+            result = node.leftChild
+            return result
         else
-            if node.leftChild == nothing
-                result = node.rightChild
-                return result
-            elseif node.rightChild == nothing
-                result = node.leftChild
-                return result
-            else 
-                result = minimum_node(node.rightChild)
-                node.data = result.data
-                node.rightChild = delete_node!(node.rightChild, result.data)
-            end 
+            result = minimum_node(node.rightChild)
+            node.data = result.data
+            node.rightChild = delete_node!(node.rightChild, result.data)
         end
-        
-        node.subsize = compute_subtree_size(node)
-        node.height = compute_height(node)
-        balance = get_balance(node)
-
-        if balance > 1
-            if get_balance(node.leftChild) >= 0
-                return right_rotate(node)
-            else
-                node.leftChild = left_rotate(node.leftChild)
-                return right_rotate(node)
-            end
+    end
+
+    node.subsize = compute_subtree_size(node)
+    node.height = compute_height(node)
+    balance = get_balance(node)
+
+    if balance > 1
+        if get_balance(node.leftChild) >= 0
+            return right_rotate(node)
+        else
+            node.leftChild = left_rotate(node.leftChild)
+            return right_rotate(node)
         end
+    end
 
-        if balance < -1
-            if get_balance(node.rightChild) <= 0
-                return left_rotate(node)
-            else
-                node.rightChild = right_rotate(node.rightChild)
-                return left_rotate(node)
-            end
-        end 
-        
-        return node
+    if balance < -1
+        if get_balance(node.rightChild) <= 0
+            return left_rotate(node)
+        else
+            node.rightChild = right_rotate(node.rightChild)
+            return left_rotate(node)
+        end
     end
 
+    return node
+end
+
+function Base.delete!(tree::AVLTree{K}, d::K) where K
     # if the key is not in the tree, do nothing and return the tree
     !haskey(tree, d) && return tree
-    
+
     # if the key is present, delete it from the tree
     tree.root = delete_node!(tree.root, d)
     tree.count -= 1
@@ -244,12 +246,12 @@ function sorted_rank(tree::AVLTree{K}, key::K) where K
         else
             node = node.leftChild
         end
-    end 
+    end
     rank += (1 + get_subsize(node.leftChild))
     return rank
 end
 
-function Base.getindex(tree::AVLTree{K}, ind::Integer) where K 
+function Base.getindex(tree::AVLTree{K}, ind::Integer) where K
     @boundscheck (1 <= ind <= tree.count) || throw(BoundsError("$ind should be in between 1 and $(tree.count)"))
     function traverse_tree(node::AVLTreeNode_or_null, idx)
         if (node != nothing)
@@ -263,6 +265,6 @@ function Base.getindex(tree::AVLTree{K}, ind::Integer) where K
             end
         end
     end
-    value = traverse_tree(tree.root, ind) 
+    value = traverse_tree(tree.root, ind)
     return value
-end
\ No newline at end of file
+end
diff --git a/src/balanced_tree.jl b/src/balanced_tree.jl
index 13d15e5..81cf7c8 100644
--- a/src/balanced_tree.jl
+++ b/src/balanced_tree.jl
@@ -354,6 +354,7 @@ end
 ## done whether the iterm
 ## is already in the tree, so insertion of a new item always succeeds.
 
+
 function Base.insert!(t::BalancedTree23{K,D,Ord}, k, d, allowdups::Bool) where {K,D,Ord <: Ordering}
 
     ## First we find the greatest data node that is <= k.
@@ -395,134 +396,122 @@ function Base.insert!(t::BalancedTree23{K,D,Ord}, k, d, allowdups::Bool) where {
     ## go back and fix the parent.
 
     newind = push_or_reuse!(t.data, t.freedatainds, KDRec{K,D}(0,k,d))
+    push!(t.useddatacells, newind)
     p1 = parent
-    oldchild = leafind
     newchild = newind
     minkeynewchild = k
     splitroot = false
     curdepth = depth
+    existingchild = leafind
 
+    
     ## This loop ascends the tree (i.e., follows the path from a leaf to the root)
     ## starting from the parent p1 of
-    ## where the new key k would go.  For each 3-node we encounter
+    ## where the new key k will go.
+    ## Variables updated by the loop:
+    ##   p1: parent of where the new node goes
+    ##   newchild: index of the child to be inserted
+    ##   minkeynewchild: the minimum key in the subtree rooted at newchild
+    ##   existingchild: a child of p1; the newchild must
+    ##      be inserted in the slot to the right of existingchild
+    ##   curdepth: depth of newchild
+    ## For each 3-node we encounter
     ## during the ascent, we add a new child, which requires splitting
     ## the 3-node into two 2-nodes.  Then we keep going until we hit the root.
     ## If we encounter a 2-node, then the ascent can stop; we can
-    ## change the 2-node to a 3-node with the new child. Invariants
-    ## during this loop are:
-    ##     p1: the parent node (a tree node index) where the insertion must occur
-    ##     oldchild,newchild: the two children of the parent node; oldchild
-    ##          was already in the tree; newchild was just added to it.
-    ##     minkeynewchild:  This is the key that is the minimum value in
-    ##         the subtree rooted at newchild.
-
-    while t.tree[p1].child3 > 0
-        isleaf = (curdepth == depth)
-        oldtreenode = t.tree[p1]
-
-        ## Node p1 index a 3-node. There are three cases for how to
-        ## insert new child.  All three cases involve splitting the
-        ## existing node (oldtreenode, numbered p1) into
-        ## two new nodes.  One keeps the index p1; the other has
-        ## has a new index called newparentnum.
-
-
-        cmp = isleaf ? cmp3_leaf(ord, oldtreenode, minkeynewchild) :
-                      cmp3_nonleaf(ord, oldtreenode, minkeynewchild)
-
-        if cmp == 1
-            lefttreenodenew = TreeNode{K}(oldtreenode.child1, newchild, 0,
-                                          oldtreenode.parent,
-                                          minkeynewchild, minkeynewchild)
-            righttreenodenew = TreeNode{K}(oldtreenode.child2, oldtreenode.child3, 0,
-                                           oldtreenode.parent, oldtreenode.splitkey2,
-                                           oldtreenode.splitkey2)
-            minkeynewchild = oldtreenode.splitkey1
-            whichp = 1
-        elseif cmp == 2
-            lefttreenodenew = TreeNode{K}(oldtreenode.child1, oldtreenode.child2, 0,
-                                          oldtreenode.parent,
-                                          oldtreenode.splitkey1, oldtreenode.splitkey1)
-            righttreenodenew = TreeNode{K}(newchild, oldtreenode.child3, 0,
-                                           oldtreenode.parent,
-                                           oldtreenode.splitkey2, oldtreenode.splitkey2)
-            whichp = 2
+    ## change the 2-node to a 3-node with the new child.
+
+    while true
+
+
+        # Let newchild1,...newchild4 be the new children of
+        # the parent node
+        # Initially, take the three children of the existing parent
+        # node and set newchild4 to 0.
+
+        newchild1 = t.tree[p1].child1
+        newchild2 = t.tree[p1].child2
+        minkeychild2 = t.tree[p1].splitkey1
+        newchild3 = t.tree[p1].child3
+        minkeychild3 = t.tree[p1].splitkey2
+        p1parent = t.tree[p1].parent
+        newchild4 = 0
+
+        # Now figure out which of the 4 children is the new node
+        # and insert it into newchild1 ... newchild4
+
+        if newchild1 == existingchild
+            newchild4 = newchild3
+            minkeychild4 = minkeychild3
+            newchild3 = newchild2
+            minkeychild3 = minkeychild2
+            newchild2 = newchild
+            minkeychild2 = minkeynewchild
+        elseif newchild2 == existingchild
+            newchild4 = newchild3
+            minkeychild4 = minkeychild3
+            newchild3 = newchild
+            minkeychild3 = minkeynewchild
+        elseif newchild3 == existingchild
+            newchild4 = newchild
+            minkeychild4 = minkeynewchild
         else
-            lefttreenodenew = TreeNode{K}(oldtreenode.child1, oldtreenode.child2, 0,
-                                          oldtreenode.parent,
-                                          oldtreenode.splitkey1, oldtreenode.splitkey1)
-            righttreenodenew = TreeNode{K}(oldtreenode.child3, newchild, 0,
-                                           oldtreenode.parent,
-                                           minkeynewchild, minkeynewchild)
-            minkeynewchild = oldtreenode.splitkey2
-            whichp = 2
+            throw(AssertionError("Tree structure is corrupted 1"))
+        end
+
+        # Two cases: either we need to split the tree node
+        # if newchild4>0 else we convert a 2-node to a 3-node
+        # if newchild4==0
+
+        if newchild4 == 0
+            # Change the parent from a 2-node to a 3-node
+            t.tree[p1] = TreeNode{K}(newchild1, newchild2, newchild3,
+                                     p1parent, minkeychild2, minkeychild3)
+            if curdepth == depth
+                replaceparent!(t.data, newchild, p1)
+            else
+                replaceparent!(t.tree, newchild, p1)
+            end
+            break
         end
-        # Replace p1 with a new 2-node and insert another 2-node at
-        # index newparentnum.
-        t.tree[p1] = lefttreenodenew
-        newparentnum = push_or_reuse!(t.tree, t.freetreeinds, righttreenodenew)
-        if isleaf
-            par = (whichp == 1) ? p1 : newparentnum
-            # fix the parent of the new datanode.
-            replaceparent!(t.data, newind, par)
-            push!(t.useddatacells, newind)
-            replaceparent!(t.data, righttreenodenew.child1, newparentnum)
-            replaceparent!(t.data, righttreenodenew.child2, newparentnum)
+        # Split the parent
+        t.tree[p1] = TreeNode{K}(newchild1, newchild2, 0,
+                                 p1parent, minkeychild2, minkeychild2)
+        newtreenode = TreeNode{K}(newchild3, newchild4, 0,
+                                  p1parent, minkeychild4, minkeychild2)
+        newparentnum = push_or_reuse!(t.tree, t.freetreeinds, newtreenode)
+        if curdepth == depth
+            replaceparent!(t.data, newchild2, p1)
+            replaceparent!(t.data, newchild3, newparentnum)
+            replaceparent!(t.data, newchild4, newparentnum)
         else
-            # If this is not a leaf, we still have to fix the
-            # parent fields of the two nodes that are now children
-            ## of the newparent.
-            replaceparent!(t.tree, righttreenodenew.child1, newparentnum)
-            replaceparent!(t.tree, righttreenodenew.child2, newparentnum)
+            replaceparent!(t.tree, newchild2, p1)
+            replaceparent!(t.tree, newchild3, newparentnum)
+            replaceparent!(t.tree, newchild4, newparentnum)
         end
-        oldchild = p1
+        # Update the loop variables for the next level of the
+        # ascension
+        existingchild = p1
         newchild = newparentnum
-        ## If p1 is the root (i.e., we have encountered only 3-nodes during
-        ## our ascent of the tree), then the root must be split.
-        if p1 == t.rootloc
-            @invariant curdepth == 1
+        p1 = p1parent
+        minkeynewchild = minkeychild3
+        curdepth -= 1
+        if curdepth == 0
             splitroot = true
             break
         end
-        p1 = t.tree[oldchild].parent
-        curdepth -= 1
     end
 
-    ## big loop terminated either because a 2-node was reached
-    ## (splitroot == false) or we went up the whole tree seeing
-    ## only 3-nodes (splitroot == true).
-    if !splitroot
-
-        ## If our ascent reached a 2-node, then we convert it to
-        ## a 3-node by giving it a child3 field that is >0.
-        ## Encountering a 2-node halts the ascent up the tree.
-
-        isleaf = curdepth == depth
-        oldtreenode = t.tree[p1]
-        cmpres = isleaf ? cmp2_leaf(ord, oldtreenode, minkeynewchild) :
-                         cmp2_nonleaf(ord, oldtreenode, minkeynewchild)
-
-
-        t.tree[p1] = cmpres == 1 ?
-                         TreeNode{K}(oldtreenode.child1, newchild, oldtreenode.child2,
-                                     oldtreenode.parent,
-                                     minkeynewchild, oldtreenode.splitkey1) :
-                         TreeNode{K}(oldtreenode.child1, oldtreenode.child2, newchild,
-                                     oldtreenode.parent,
-                                     oldtreenode.splitkey1, minkeynewchild)
-        if isleaf
-            replaceparent!(t.data, newind, p1)
-            push!(t.useddatacells, newind)
-        end
-    else
-        ## Splitroot is set if the ascent of the tree encountered only 3-nodes.
-        ## In this case, the root itself was replaced by two nodes, so we need
-        ## a new root above those two.
+    # If the root has been split, then we need to add a level
+    # to the tree that is the parent of the old root and the new node.
 
-        newroot = TreeNode{K}(oldchild, newchild, 0, 0,
-                              minkeynewchild, minkeynewchild)
+    if splitroot
+        @invariant existingchild == t.rootloc
+        newroot = TreeNode{K}(existingchild, newchild, 0,
+                              0, minkeynewchild, minkeynewchild)
+        
         newrootloc = push_or_reuse!(t.tree, t.freetreeinds, newroot)
-        replaceparent!(t.tree, oldchild, newrootloc)
+        replaceparent!(t.tree, existingchild, newrootloc)
         replaceparent!(t.tree, newchild, newrootloc)
         t.rootloc = newrootloc
         t.depth += 1
@@ -615,7 +604,7 @@ end
 ##, 1 if i2 precedes i1.
 
 function compareInd(t::BalancedTree23, i1::Int, i2::Int)
-    @assert(i1 in t.useddatacells && i2 in t.useddatacells)
+    @invariant(i1 in t.useddatacells && i2 in t.useddatacells)
     if i1 == i2
         return 0
     end
@@ -624,6 +613,7 @@ function compareInd(t::BalancedTree23, i1::Int, i2::Int)
     p1 = t.data[i1].parent
     p2 = t.data[i2].parent
     @invariant_support_statement curdepth = t.depth
+    curdepth = t.depth
     while true
         @invariant curdepth > 0
         if p1 == p2
@@ -647,6 +637,7 @@ function compareInd(t::BalancedTree23, i1::Int, i2::Int)
         p1 = t.tree[i1a].parent
         p2 = t.tree[i2a].parent
         @invariant_support_statement curdepth -= 1
+        curdepth -= 1
     end
 end
 
diff --git a/src/deprecations.jl b/src/deprecations.jl
index c9b1024..673fafe 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 ba49944..88d7665 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))
diff --git a/src/red_black_tree.jl b/src/red_black_tree.jl
index a7c2d85..b51cd32 100644
--- a/src/red_black_tree.jl
+++ b/src/red_black_tree.jl
@@ -17,6 +17,9 @@ end
 RBTreeNode() = RBTreeNode{Any}()
 RBTreeNode(d) = RBTreeNode{Any}(d)
 
+Base.setproperty!(x::RBTreeNode{K}, f::Symbol, v) where {K} =
+    setfield!(x, f, v)
+
 function create_null_node(K::Type)
     node = RBTreeNode{K}()
     node.color = false
diff --git a/src/splay_tree.jl b/src/splay_tree.jl
index a87614b..e6e8045 100644
--- a/src/splay_tree.jl
+++ b/src/splay_tree.jl
@@ -11,12 +11,15 @@ end
 SplayTreeNode(d) = SplayTreeNode{Any}(d)
 SplayTreeNode() = SplayTreeNode{Any}()
 
+Base.setproperty!(x::SplayTreeNode{K}, f::Symbol, v) where {K} =
+    setfield!(x, f, v)
+
 mutable struct SplayTree{K}
     root::Union{SplayTreeNode{K}, Nothing}
     count::Int
 
     SplayTree{K}() where K = new{K}(nothing, 0)
-end 
+end
 
 Base.length(tree::SplayTree) = tree.count
 
@@ -41,7 +44,7 @@ function left_rotate!(tree::SplayTree, node_x::SplayTreeNode)
         node_y.leftChild = node_x
     end
     node_x.parent = node_y
-end    
+end
 
 function right_rotate!(tree::SplayTree, node_x::SplayTreeNode)
     node_y = node_x.leftChild
@@ -59,7 +62,7 @@ function right_rotate!(tree::SplayTree, node_x::SplayTreeNode)
     end
     node_y.rightChild = node_x
     node_x.parent = node_y
-end 
+end
 
 # The splaying operation moves node_x to the root of the tree using the series of rotations.
 function splay!(tree::SplayTree, node_x::SplayTreeNode)
@@ -71,7 +74,7 @@ function splay!(tree::SplayTree, node_x::SplayTreeNode)
             if node_x == parent.leftChild
                 # zig rotation
                 right_rotate!(tree, node_x.parent)
-            else 
+            else
                 # zag rotation
                 left_rotate!(tree, node_x.parent)
             end
@@ -104,7 +107,7 @@ function maximum_node(node::Union{SplayTreeNode, Nothing})
     return node
 end
 
-# Join operations joins two trees S and T 
+# Join operations joins two trees S and T
 # All the items in S are smaller than the items in T.
 # This is a two-step process.
 # In the first step, splay the largest node in S. This moves the largest node to the root node.
@@ -157,10 +160,10 @@ function Base.delete!(tree::SplayTree{K}, d::K) where K
     x = search_node(tree, d)
     (x == nothing) && return tree
     t = nothing
-    s = nothing 
-    
+    s = nothing
+
     splay!(tree, x)
-    
+
     if x.rightChild !== nothing
         t = x.rightChild
         t.parent = nothing
@@ -211,7 +214,7 @@ function Base.push!(tree::SplayTree{K}, d0) where K
     return tree
 end
 
-function Base.getindex(tree::SplayTree{K}, ind) where K 
+function Base.getindex(tree::SplayTree{K}, ind) where K
     @boundscheck (1 <= ind <= tree.count) || throw(KeyError("$ind should be in between 1 and $(tree.count)"))
     function traverse_tree_inorder(node::Union{SplayTreeNode, Nothing})
         if (node != nothing)
@@ -222,6 +225,6 @@ function Base.getindex(tree::SplayTree{K}, ind) where K
             return K[]
         end
     end
-    arr = traverse_tree_inorder(tree.root) 
+    arr = traverse_tree_inorder(tree.root)
     return @inbounds arr[ind]
 end


Test patch:
diff --git a/test/runtests.jl b/test/runtests.jl
index 7a5aa76..33927d2 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -5,7 +5,8 @@ using Serialization
 
 import DataStructures: IntSet
 
-@test [] == detect_ambiguities(Base, Core, DataStructures)
+@test [] == detect_ambiguities(Core, DataStructures)
+@test [] == detect_ambiguities(Base, DataStructures)
 
 tests = ["deprecations",
          "int_set",
@@ -34,7 +35,7 @@ tests = ["deprecations",
          "dibit_vector",
          "swiss_dict",
          "avl_tree",
-         "red_black_tree", 
+         "red_black_tree",
          "splay_tree"
         ]
 
diff --git a/test/test_avl_tree.jl b/test/test_avl_tree.jl
index 78ddae4..0f4c64b 100644
--- a/test/test_avl_tree.jl
+++ b/test/test_avl_tree.jl
@@ -26,7 +26,7 @@
         end
 
         @test length(t) == 50
-        
+
         for i in 1:100
             if iseven(i)
                 @test haskey(t, i)
@@ -43,19 +43,19 @@
     end
 
     @testset "handling different cases of delete!" begin
-        t2 = AVLTree()
+        t2 = AVLTree{Int}()
         for i in 1:100000
             insert!(t2, i)
         end
 
         @test length(t2) == 100000
-        
+
         nums = rand(1:100000, 8599)
         visited = Set()
-        for num in nums 
+        for num in nums
             if !(num in visited)
                 delete!(t2, num)
-                push!(visited, num) 
+                push!(visited, num)
             end
         end
 
@@ -67,7 +67,7 @@
 
     @testset "handling different cases of insert!" begin
         nums = rand(1:100000, 1000)
-        t3 = AVLTree()
+        t3 = AVLTree{Int}()
         uniq_nums = Set(nums)
         for num in uniq_nums
             insert!(t3, num)
@@ -84,20 +84,20 @@
         @test !in('c', t4)
     end
 
-    @testset "search_node" begin 
-        t5 = AVLTree()
+    @testset "search_node" begin
+        t5 = AVLTree{Int}()
         for i in 1:32
             push!(t5, i)
         end
         n1 = search_node(t5, 21)
         @test n1.data == 21
         n2 = search_node(t5, 35)
-        @test n2.data == 32 
+        @test n2.data == 32
         n3 = search_node(t5, 0)
         @test n3.data == 1
-    end 
+    end
 
-    @testset "getindex" begin 
+    @testset "getindex" begin
         t6 = AVLTree{Int}()
         for i in 1:10
             push!(t6, i)
@@ -117,7 +117,7 @@
     end
 
     @testset "minimum_node" begin
-        t8 = AVLTree()
+        t8 = AVLTree{Int}()
         @test minimum_node(t8.root) == nothing
         for i in 1:32
             push!(t8, i)
@@ -132,7 +132,7 @@
         end
     end
 
-    @testset "rank" begin 
+    @testset "rank" begin
         t9 = AVLTree{Int}()
         for i in 1:20
             push!(t9, i)
@@ -142,4 +142,4 @@
         end
         @test_throws KeyError sorted_rank(t9, 21)
     end
-end
\ No newline at end of file
+end
diff --git a/test/test_deprecations.jl b/test/test_deprecations.jl
index 21c6b9e..565e428 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 4d1a0a8..35dc8e6 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
diff --git a/test/test_sorted_containers.jl b/test/test_sorted_containers.jl
index c1b2733..8a246bc 100644
--- a/test/test_sorted_containers.jl
+++ b/test/test_sorted_containers.jl
@@ -1403,6 +1403,32 @@ function testSortedMultiDict()
     end
     # issue #216
     my_assert(DataStructures.isordered(SortedMultiDict{Int, String}))
+    # issue #773
+    s = SortedMultiDict{Int, Int}()           
+    insert!(s, 4, 41)
+    insert!(s, 3, 31)
+    insert!(s, 2, 21)
+    insert!(s, 2, 22)
+    insert!(s, 2, 23)
+    insert!(s, 2, 24)
+    insert!(s, 2, 25)
+    insert!(s, 2, 26)
+    insert!(s, 1, 11)
+    insert!(s, 1, 12)
+    st1 = insert!(s, 1, 13)
+    st2 = insert!(s, 1, 14)
+    st3 = insert!(s, 1, 15)
+    st4 = insert!(s, 1, 16)
+    st5 = insert!(s, 1, 17)
+    st6 = insert!(s, 1, 18)
+    delete!((s, st6))
+    delete!((s, st5))
+    delete!((s, st4))
+    delete!((s, st3))
+    delete!((s, st2))
+    delete!((s, st1))
+    insert!(s, 1, 19)
+    checkcorrectness(s.bt, true)
     true
 end