Repository: JuliaCollections/DataStructures.jl
Pull request #567 (2020-01-11 21:02:41)

Add additional constructors for DisjointSets
Add additional `DisjointSets` constructors to address: #562.

codecov[bot]: # [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/567?src=pr&el=h1) Report
> Merging [#567](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/567?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/54af1eb49640bdc00f3aa7ffec13a750afa0d9bc?src=pr&el=desc) will **increase** coverage by `0.04%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master     #567      +/-   ##
==========================================
+ Coverage   87.82%   87.87%   +0.04%     
==========================================
  Files          32       32              
  Lines        2087     2095       +8     
==========================================
+ Hits         1833     1841       +8     
  Misses        254      254
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/567?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/disjoint\_set.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/567/diff?src=pr&el=tree#diff-c3JjL2Rpc2pvaW50X3NldC5qbA==) | `95.65% <100%> (+0.91%)` | :arrow_up: |

------

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

c-p-murphy: Thanks for taking the time to review this—I think it should be all set now, but feel free to let me know if I misunderstood any of your suggestions or if you notice anything else that should be modified.

Patch:
diff --git a/Project.toml b/Project.toml
index 4f6b945..d25018a 100644
--- a/Project.toml
+++ b/Project.toml
@@ -1,6 +1,6 @@
 name = "DataStructures"
 uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
-version = "0.17.7"
+version = "0.17.8"
 
 [deps]
 InteractiveUtils = "b77e0a4c-d291-57a0-90e8-8db25a27a240"
diff --git a/src/disjoint_set.jl b/src/disjoint_set.jl
index 2e989e9..0016985 100644
--- a/src/disjoint_set.jl
+++ b/src/disjoint_set.jl
@@ -26,7 +26,6 @@ length(s::IntDisjointSets) = length(s.parents)
 num_groups(s::IntDisjointSets) = s.ngroups
 Base.eltype(::Type{IntDisjointSets}) = Int
 
-
 # find the root element of the subset that contains x
 # path compression is implemented here
 #
@@ -111,6 +110,7 @@ mutable struct DisjointSets{T}
     revmap::Vector{T}
     internal::IntDisjointSets
 
+    DisjointSets{T}() where T = new{T}(Dict{T,Int}(), Vector{T}(), IntDisjointSets(0))
     function DisjointSets{T}(xs) where T    # xs must be iterable
         imap = Dict{T,Int}()
         rmap = Vector{T}()
@@ -126,9 +126,21 @@ mutable struct DisjointSets{T}
     end
 end
 
+DisjointSets() = DisjointSets{Any}()
+DisjointSets(xs::T...) where T = DisjointSets{T}(xs)
+DisjointSets{T}(xs::T...) where T = DisjointSets{T}(xs)
+DisjointSets(xs) = _DisjointSets(xs, Base.IteratorEltype(xs))
+_DisjointSets(xs, ::Base.HasEltype) = DisjointSets{eltype(xs)}(xs)
+function _DisjointSets(xs, ::Base.EltypeUnknown)
+    T = Base.@default_eltype(xs)
+    (isconcretetype(T) || T === Union{}) || return grow_to!(DisjointSets{T}(), xs)
+    return DisjointSets{T}(xs)
+end
+
 length(s::DisjointSets) = length(s.internal)
 num_groups(s::DisjointSets) = num_groups(s.internal)
 Base.eltype(::Type{DisjointSets{T}}) where T = T
+empty(s::DisjointSets{T}, ::Type{U}=T) where {T,U} = DisjointSets{U}()
 
 """
     find_root{T}(s::DisjointSets{T}, x::T)
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_disjoint_set.jl b/test/test_disjoint_set.jl
index 468df55..5eb2649 100644
--- a/test/test_disjoint_set.jl
+++ b/test/test_disjoint_set.jl
@@ -54,11 +54,22 @@
         # DisjointSets supports arbitrary indices
         s = DisjointSets{Int}(1:10)
 
+        @testset "constructor" begin
+            @test DisjointSets() isa DisjointSets{Any}
+            @test DisjointSets{Int}(1:10) isa DisjointSets{Int}
+            @test DisjointSets{Float64}(1.0:10.0...) isa DisjointSets{Float64}
+            @test DisjointSets(collect(1:10)) isa DisjointSets{Int}
+            @test DisjointSets(collect(1.0:10.0)...) isa DisjointSets{Float64}
+            @test DisjointSets(x*im for x = 1:10) isa DisjointSets{Complex{Int}}
+        end
+
         @testset "basic tests" begin
             @test length(s) == 10
             @test num_groups(s) == 10
             @test eltype(s) == Int
             @test eltype(typeof(s)) == Int
+            @test length(empty(s)) == num_groups(empty(s)) == 0
+            @test empty(s) isa DisjointSets{eltype(s)}
 
             r = [find_root(s, i) for i in 1 : 10]
             @test isequal(r, collect(1:10))
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