Repository: JuliaCollections/DataStructures.jl
Pull request #566 (2020-01-05 14:38:50)

Provide support for 3-arguments pop! for SortedDict to match Base.pop
The standard `Base.pop!` provides a 3-arg function:
```
pop!(h::Dict, key, default) in Base at dict.jl:608
```
This functionality is missing in `OrderedDict` and hence making it impossible to use `OrderedDict` as a drop-in replacement for `Dict`. This adds the missing functionality along with the unit tests.

StephenVavasis: It appears that the code for SortedDict has been modified, but not the code for SortedSet?  The rewritten in-line documentation implies that `default` is available for both SortedDict and SortedSet.
codecov[bot]: # [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/566?src=pr&el=h1) Report
> Merging [#566](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/566?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/54af1eb49640bdc00f3aa7ffec13a750afa0d9bc?src=pr&el=desc) will **increase** coverage by `0.08%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master     #566      +/-   ##
==========================================
+ Coverage   87.82%   87.91%   +0.08%     
==========================================
  Files          32       32              
  Lines        2087     2094       +7     
==========================================
+ Hits         1833     1841       +8     
+ Misses        254      253       -1
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/566?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/sorted\_set.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/566/diff?src=pr&el=tree#diff-c3JjL3NvcnRlZF9zZXQuamw=) | `83.45% <100%> (+0.51%)` | :arrow_up: |
| [src/sorted\_dict.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/566/diff?src=pr&el=tree#diff-c3JjL3NvcnRlZF9kaWN0Lmps) | `85.98% <100%> (+0.4%)` | :arrow_up: |
| [src/container\_loops.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/566/diff?src=pr&el=tree#diff-c3JjL2NvbnRhaW5lcl9sb29wcy5qbA==) | `28.33% <0%> (+0.83%)` | :arrow_up: |

------

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

pszufe: OK done with the SortedSet and all tests pass.
pszufe: Dear @StephenVavasis do you need anything else to merge that pull request? I believe it is very important for the API of DataStructures.jl to match those of Julia `Base`.
StephenVavasis: This PR looks fine to me, but I don't ever do merging. (I'm not sure I have the permission, and even if I did, I don't know how.)

pszufe: @oxinabox I guess that you do PR merging in this repo. Do you need anything else to merge this PR? 
oxinabox: @StephenVavasis you should have permission to merge.
You should do merging.
What can I do to help you become comfortable with merging and tagging releases?

I will merge this one and tag a release

Patch:
diff --git a/src/sorted_dict.jl b/src/sorted_dict.jl
index d0eea4e..4943a5c 100644
--- a/src/sorted_dict.jl
+++ b/src/sorted_dict.jl
@@ -462,12 +462,13 @@ Returns `sc`. Time: O(*c* log *n*)
 end
 
 """
-    pop!(sc, k)
+    pop!(sc, k[, default])
 
 Deletes the item with key `k` in SortedDict or SortedSet `sc` and
 returns the value that was associated with `k` in the case of
-SortedDict or `k` itself in the case of SortedSet. A `KeyError`
-results if `k` is not in `sc`. Time: O(*c* log *n*)
+SortedDict or `k` itself in the case of SortedSet. If `k` is not in `sc`
+return `default`, or throw a `KeyError` if `default` is not specified.
+Time: O(*c* log *n*)
 """
 @inline function pop!(m::SortedDict, k_)
     i, exactfound = findkey(m.bt, convert(keytype(m), k_))
@@ -477,6 +478,14 @@ results if `k` is not in `sc`. Time: O(*c* log *n*)
     d
 end
 
+@inline function pop!(m::SortedDict, k_, default)
+    i, exactfound = findkey(m.bt, convert(keytype(m), k_))
+    !exactfound && return default
+    d = m.bt.data[i].d
+    delete!(m.bt, i)
+    d
+end
+
 
 ## Check if two SortedDicts are equal in the sense of containing
 ## the same (K,D) pairs.  This sense of equality does not mean
diff --git a/src/sorted_set.jl b/src/sorted_set.jl
index 143db27..17aab83 100644
--- a/src/sorted_set.jl
+++ b/src/sorted_set.jl
@@ -236,12 +236,13 @@ end
 
 
 """
-    pop!(sc, k)
+    pop!(sc, k[, default])
 
 Deletes the item with key `k` in SortedDict or SortedSet `sc` and
 returns the value that was associated with `k` in the case of
-SortedDict or `k` itself in the case of SortedSet. A `KeyError`
-results if `k` is not in `sc`. Time: O(*c* log *n*)
+SortedDict or `k` itself in the case of SortedSet. If `k` is not in `sc`
+return `default`, or throw a `KeyError` if `default` is not specified.
+Time: O(*c* log *n*)
 """
 @inline function pop!(m::SortedSet, k_)
     k = convert(keytype(m),k_)
@@ -252,6 +253,15 @@ results if `k` is not in `sc`. Time: O(*c* log *n*)
     k
 end
 
+@inline function pop!(m::SortedSet, k_, default)
+    k = convert(keytype(m),k_)
+    i, exactfound = findkey(m.bt, k)
+    !exactfound && return default
+    d = m.bt.data[i].d
+    delete!(m.bt, i)
+    k
+end
+
 """
     pop!(ss)
 


Test patch:
diff --git a/test/test_sorted_containers.jl b/test/test_sorted_containers.jl
index cc815e6..0a5b2d0 100644
--- a/test/test_sorted_containers.jl
+++ b/test/test_sorted_containers.jl
@@ -361,6 +361,26 @@ function testSortedDictMethods()
     end
     my_assert(isempty(m1))
     my_assert(length(m1) == 0)
+    N = 1000
+    for i = 2:N
+        m1[i] = convert(Float64,i) ^ 2
+    end
+    my_assert(!isempty(m1))
+    my_assert(length(m1) == N - 1)
+    for i = 2 : N
+        d = pop!(m1, i, -1.0)
+        my_assert(d == convert(Float64,i)^2)
+        d2 = pop!(m1, i, -1.0)
+        my_assert(d2 == -1.0)
+        d3 = pop!(m1, i, nothing)
+        my_assert(d3 == nothing)
+
+        if i % 200 == 0
+            checkcorrectness(m1.bt, false)
+        end
+    end
+    my_assert(isempty(m1))
+    my_assert(length(m1) == 0)
     for i = N : -1 : 2
         m1[i] = convert(Float64,i) ^ 2
         if i % 200 == 0
@@ -1689,7 +1709,12 @@ end
     @test_throws ArgumentError (("a",6) in m)
     @test_throws ArgumentError ((2,5) in m1)
 
-
-
+    s = SortedSet([10,30,50])
+    @test pop!(s,10) == 10
+    @test pop!(s,30,-1) == 30
+    @test pop!(s,30, nothing) == nothing
+    @test pop!(s,50, nothing) == 50
+    @test pop!(s,50, nothing) == nothing
+    @test isempty(s)
 
 end