Repository: JuliaCollections/DataStructures.jl
Pull request #568 (2020-01-19 21:22:22)

Fix DisjointSets constructor error
Address error introduced by #567 in situations like the following:

```julia
DisjointSets(x % 2 == 0 ? x+1//x : x*im for x = 1:10)
```


Patch:
diff --git a/Project.toml b/Project.toml
index b7ae7b2..35f1eba 100644
--- a/Project.toml
+++ b/Project.toml
@@ -1,6 +1,6 @@
 name = "DataStructures"
 uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
-version = "0.17.9"
+version = "0.17.10"
 
 [deps]
 InteractiveUtils = "b77e0a4c-d291-57a0-90e8-8db25a27a240"
diff --git a/src/disjoint_set.jl b/src/disjoint_set.jl
index c38b312..6ff5a28 100644
--- a/src/disjoint_set.jl
+++ b/src/disjoint_set.jl
@@ -16,9 +16,9 @@
 """
     IntDisjointSets(n::Integer)
 
-A forest of disjoint sets of integers, which is a data structure 
-(also called a union–find data structure or merge–find set) 
-that tracks a set of elements partitioned 
+A forest of disjoint sets of integers, which is a data structure
+(also called a union–find data structure or merge–find set)
+that tracks a set of elements partitioned
 into a number of disjoint (non-overlapping) subsets.
 """
 mutable struct IntDisjointSets
@@ -84,7 +84,7 @@ function union!(s::IntDisjointSets, x::Integer, y::Integer)
     parents = s.parents
     xroot = find_root_impl!(parents, x)
     yroot = find_root_impl!(parents, y)
-    xroot != yroot ?  root_union!(s, xroot, yroot) : xroot
+    xroot != yroot ? root_union!(s, xroot, yroot) : xroot
 end
 
 """
@@ -110,10 +110,9 @@ function root_union!(s::IntDisjointSets, x::Integer, y::Integer)
     x
 end
 
-
 """
     push!(s::IntDisjointSets)
-    
+
 Make a new subset with an automatically chosen new element x.
 Returns the new element.
 """
@@ -125,7 +124,6 @@ function push!(s::IntDisjointSets)
     return x
 end
 
-
 """
     DisjointSets{T}(xs)
 
@@ -134,7 +132,7 @@ A forest of disjoint sets of arbitrary value type T.
 It is a wrapper of IntDisjointSets, which uses a
 dictionary to map the input value to an internal index.
 """
-mutable struct DisjointSets{T}
+mutable struct DisjointSets{T} <: AbstractSet{T}
     intmap::Dict{T,Int}
     revmap::Vector{T}
     internal::IntDisjointSets
@@ -162,10 +160,13 @@ 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)
+    (isconcretetype(T) || T === Union{}) || return Base.grow_to!(DisjointSets{T}(), xs)
     return DisjointSets{T}(xs)
 end
 
+iterate(s::DisjointSets) = iterate(s.revmap)
+iterate(s::DisjointSets, i) = iterate(s.revmap, i)
+
 length(s::DisjointSets) = length(s.internal)
 
 """
@@ -176,6 +177,11 @@ Get a number of groups.
 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}()
+function sizehint!(s::DisjointSets, n::Integer)
+    sizehint!(s.intmap, n)
+    sizehint!(s.revmap, n)
+    return s
+end
 
 """
     find_root{T}(s::DisjointSets{T}, x::T)
@@ -199,7 +205,6 @@ and return the root of the new set.
 """
 union!(s::DisjointSets{T}, x::T, y::T) where {T} = s.revmap[union!(s.internal, s.intmap[x], s.intmap[y])]
 
-
 """
     root_union!(s::DisjointSets{T}, x::T, y::T)
 
@@ -209,10 +214,9 @@ Assume x ≠ y (unsafe).
 """
 root_union!(s::DisjointSets{T}, x::T, y::T) where {T} = s.revmap[root_union!(s.internal, s.intmap[x], s.intmap[y])]
 
-
 """
     push!(s::DisjointSets{T}, x::T)
-    
+
 Make a new subset with an automatically chosen new element x.
 Returns the new element.
 """


Test patch:
diff --git a/test/test_disjoint_set.jl b/test/test_disjoint_set.jl
index 5eb2649..5576dea 100644
--- a/test/test_disjoint_set.jl
+++ b/test/test_disjoint_set.jl
@@ -61,6 +61,8 @@
             @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}}
+            g = (x % 2 == 0 ? x+1//x : x*im for x = 1:10)
+            @test DisjointSets(g) isa DisjointSets{Number}
         end
 
         @testset "basic tests" begin
@@ -70,6 +72,11 @@
             @test eltype(typeof(s)) == Int
             @test length(empty(s)) == num_groups(empty(s)) == 0
             @test empty(s) isa DisjointSets{eltype(s)}
+            @test collect(s) == collect(1:10)
+            g = (x % 2 == 0 ? x+1//x : x*im for x = 1:10)
+            s1 = DisjointSets(g)
+            @test length(s1) == 10
+            @test sizehint!(s1, 100) === s1
 
             r = [find_root(s, i) for i in 1 : 10]
             @test isequal(r, collect(1:10))
@@ -116,6 +123,7 @@
         @testset "Some tests using non-integer disjoint sets" begin
             elems = ["a", "b", "c", "d"]
             a = DisjointSets{AbstractString}(elems)
+            @test collect(a) == ["a", "b", "c", "d"]
             union!(a, "a", "b")
             @test in_same_set(a,"a","b")
             @test find_root(a,"a") == find_root(a,"b")