Repository: JuliaCollections/DataStructures.jl
Pull request #513 (2019-07-10 16:35:21)

Adding `eltype` for containers
Most of the containers did not have a defined `eltype` operation. I added it (or corrected the current implementation) for:
- `CircularBuffer`
- `Deque`
- `DisjointSet`
- `FenwickTree`
- `AbstractHeap`
- `IntSet`
- `LinkedList`
- `MutableList`
- `Queue`
- `SortedSet`
- `Stack`

Please let me know if I missed any. I purposefully avoided associative containers in this PR, though it should be defined for them as well. It makes sense to have a Key-Value associative container return `Pair{K, V}` from `eltype` similar to how `Dict` does it in Julia core.


Patch:
diff --git a/src/circular_buffer.jl b/src/circular_buffer.jl
index 0efa4b2..c687bed 100644
--- a/src/circular_buffer.jl
+++ b/src/circular_buffer.jl
@@ -162,6 +162,8 @@ Return the number of elements currently in the buffer.
 """
 Base.length(cb::CircularBuffer) = cb.length
 
+Base.eltype(::Type{CircularBuffer{T}}) where T = T
+
 """
     size(cb)
 
diff --git a/src/deque.jl b/src/deque.jl
index eaa0a66..5cd2dc1 100644
--- a/src/deque.jl
+++ b/src/deque.jl
@@ -83,6 +83,7 @@ deque(::Type{T}) where {T} = Deque{T}()
 isempty(q::Deque) = q.len == 0
 length(q::Deque) = q.len
 num_blocks(q::Deque) = q.nblocks
+Base.eltype(::Type{Deque{T}}) where T = T
 
 """
     front(q::Deque)
diff --git a/src/disjoint_set.jl b/src/disjoint_set.jl
index bd63398..2e989e9 100644
--- a/src/disjoint_set.jl
+++ b/src/disjoint_set.jl
@@ -24,6 +24,7 @@ end
 
 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
@@ -127,6 +128,7 @@ end
 
 length(s::DisjointSets) = length(s.internal)
 num_groups(s::DisjointSets) = num_groups(s.internal)
+Base.eltype(::Type{DisjointSets{T}}) where T = T
 
 """
     find_root{T}(s::DisjointSets{T}, x::T)
diff --git a/src/fenwick.jl b/src/fenwick.jl
index 30a359a..c1d078b 100644
--- a/src/fenwick.jl
+++ b/src/fenwick.jl
@@ -27,6 +27,7 @@ function FenwickTree(a::AbstractVector{U}) where U
 end
 
 length(ft::FenwickTree) = ft.n
+Base.eltype(::Type{FenwickTree{T}}) where T = T
 
 """
     inc!(ft::FenwickTree{T}, ind, val)
diff --git a/src/heaps.jl b/src/heaps.jl
index 5400f8a..5560c1d 100644
--- a/src/heaps.jl
+++ b/src/heaps.jl
@@ -75,6 +75,8 @@ include("heaps/minmax_heap.jl")
 
 # generic functions
 
+Base.eltype(::Type{<:AbstractHeap{T}}) where T = T
+
 function extract_all!(h::AbstractHeap{VT}) where VT
     n = length(h)
     r = Vector{VT}(undef, n)
diff --git a/src/int_set.jl b/src/int_set.jl
index ffff6ea..169c054 100644
--- a/src/int_set.jl
+++ b/src/int_set.jl
@@ -21,7 +21,7 @@ function copy!(to::IntSet, from::IntSet)
     to.inverse = from.inverse
     to
 end
-eltype(s::IntSet) = Int
+Base.eltype(::Type{IntSet}) = Int
 sizehint!(s::IntSet, n::Integer) = (_resize0!(s.bits, n+1); s)
 
 # An internal function for setting the inclusion bit for a given integer n >= 0
diff --git a/src/list.jl b/src/list.jl
index ff3b294..c9d5d62 100644
--- a/src/list.jl
+++ b/src/list.jl
@@ -1,5 +1,7 @@
 abstract type LinkedList{T} end
 
+Base.eltype(::Type{<:LinkedList{T}}) where T = T
+
 mutable struct Nil{T} <: LinkedList{T}
 end
 
diff --git a/src/mutable_list.jl b/src/mutable_list.jl
index 15cccc3..3d17256 100644
--- a/src/mutable_list.jl
+++ b/src/mutable_list.jl
@@ -47,7 +47,7 @@ end
 isempty(l::MutableLinkedList) = l.len == 0
 length(l::MutableLinkedList) = l.len
 collect(l::MutableLinkedList{T}) where T = T[x for x in l]
-eltype(l::MutableLinkedList{T}) where T = T
+Base.eltype(::Type{<:MutableLinkedList{T}}) where T = T
 lastindex(l::MutableLinkedList) = l.len
 
 function first(l::MutableLinkedList)
diff --git a/src/queue.jl b/src/queue.jl
index 94396eb..feb5d55 100644
--- a/src/queue.jl
+++ b/src/queue.jl
@@ -14,6 +14,7 @@ Queue{T}(blksize::Integer) where {T} = Queue(Deque{T}(blksize))
 
 isempty(s::Queue) = isempty(s.store)
 length(s::Queue) = length(s.store)
+Base.eltype(::Type{Queue{T}}) where T = T
 
 front(s::Queue) = front(s.store)
 back(s::Queue) = back(s.store)
diff --git a/src/sorted_set.jl b/src/sorted_set.jl
index c4c2cd8..143db27 100644
--- a/src/sorted_set.jl
+++ b/src/sorted_set.jl
@@ -180,8 +180,7 @@ end
 Returns the key type for SortedSet.
 This function may also be applied to the type itself. Time: O(1)
 """
-@inline eltype(m::SortedSet{K,Ord}) where {K,Ord <: Ordering} = K
-@inline eltype(::Type{SortedSet{K,Ord}}) where {K,Ord <: Ordering} = K
+@inline Base.eltype(::Type{SortedSet{K,Ord}}) where {K,Ord <: Ordering} = K
 
 """
     keytype(sc)
diff --git a/src/stack.jl b/src/stack.jl
index b688eb9..0be6e02 100644
--- a/src/stack.jl
+++ b/src/stack.jl
@@ -9,6 +9,7 @@ Stack{T}(blksize::Integer) where {T} = Stack(Deque{T}(blksize))
 
 isempty(s::Stack) = isempty(s.store)
 length(s::Stack) = length(s.store)
+Base.eltype(::Type{Stack{T}}) where T = T
 
 top(s::Stack) = back(s.store)
 


Test patch:
diff --git a/test/test_circ_deque.jl b/test/test_circ_deque.jl
index 1a45821..7dfc08a 100644
--- a/test/test_circ_deque.jl
+++ b/test/test_circ_deque.jl
@@ -3,6 +3,7 @@
     @testset "Core Functionality" begin
         D = CircularDeque{Int}(5)
         @test eltype(D) == Int
+        @test eltype(typeof(D)) == Int
         @test capacity(D) == 5
         @test length(D) == 0
         @test isempty(D)
diff --git a/test/test_circular_buffer.jl b/test/test_circular_buffer.jl
index 9b3cb78..f31b2cf 100644
--- a/test/test_circular_buffer.jl
+++ b/test/test_circular_buffer.jl
@@ -8,6 +8,8 @@
             @test_throws BoundsError first(cb)
             @test isempty(cb) == true
             @test isfull(cb) == false
+            @test eltype(cb) == Int
+            @test eltype(typeof(cb)) == Int
         end
         
         @testset "With 1 element" begin
diff --git a/test/test_deque.jl b/test/test_deque.jl
index 6dc5775..4597eb1 100644
--- a/test/test_deque.jl
+++ b/test/test_deque.jl
@@ -4,6 +4,8 @@
             q = Deque{Int}()
             @test length(q) == 0
             @test isempty(q)
+            @test eltype(q) == Int
+            @test eltype(typeof(q)) == Int
             @test q.blksize == DataStructures.DEFAULT_DEQUEUE_BLOCKSIZE
             @test_throws ArgumentError front(q)
             @test_throws ArgumentError back(q)
diff --git a/test/test_disjoint_set.jl b/test/test_disjoint_set.jl
index 449b144..3eec1ab 100644
--- a/test/test_disjoint_set.jl
+++ b/test/test_disjoint_set.jl
@@ -5,6 +5,8 @@
 
         @testset "basic tests" begin
             @test length(s) == 10
+            @test eltype(s) == Int
+            @test eltype(typeof(s)) == Int
             @test num_groups(s) == 10
 
             for i = 1:10
@@ -55,6 +57,8 @@
         @testset "basic tests" begin
             @test length(s) == 10
             @test num_groups(s) == 10
+            @test eltype(s) == Int
+            @test eltype(typeof(s)) == Int
 
             r = [find_root(s, i) for i in 1 : 10]
             @test isequal(r, collect(1:10))
diff --git a/test/test_fenwick.jl b/test/test_fenwick.jl
index 144e5eb..7a89b93 100644
--- a/test/test_fenwick.jl
+++ b/test/test_fenwick.jl
@@ -3,6 +3,8 @@
         f1 = FenwickTree{Float64}(5)
         @test f1.bi_tree == zeros(5)
         @test length(f1) == 5
+        @test eltype(f1) == Float64
+        @test eltype(typeof(f1)) == Float64
         
         arr = [1.2, 8.7, 7.2, 3.5]
         f3 = FenwickTree(arr)
diff --git a/test/test_int_set.jl b/test/test_int_set.jl
index 3a0f301..60805b2 100644
--- a/test/test_int_set.jl
+++ b/test/test_int_set.jl
@@ -11,7 +11,8 @@ import DataStructures: IntSet
     end
 
     @testset "eltype, empty" begin
-        @test eltype(IntSet()) ===  Int
+        @test eltype(IntSet()) == Int
+        @test eltype(typeof(IntSet())) == Int
         @test isequal(empty(IntSet([1,2,3])), IntSet())
     end
 
diff --git a/test/test_list.jl b/test/test_list.jl
index 2f28d77..02f79b1 100644
--- a/test/test_list.jl
+++ b/test/test_list.jl
@@ -1,5 +1,12 @@
 @testset "LinkedList" begin
 
+    @testset "basic tests" begin
+        l = list(2, 3)
+        @test length(l) == 2
+        @test eltype(l) == Int
+        @test eltype(typeof(l)) == Int
+    end
+
     @testset "l0" begin
         l0 = nil(Char)
         @test length(l0) == 0
diff --git a/test/test_minmax_heap.jl b/test/test_minmax_heap.jl
index 8a8bdb7..50f70bc 100644
--- a/test/test_minmax_heap.jl
+++ b/test/test_minmax_heap.jl
@@ -10,6 +10,15 @@ using Base.Order: Forward, Reverse
         @test is_minmax_heap([])
         @test is_minmax_heap([rand()])
     end
+
+    @testset "basic tests" begin
+        h = BinaryMinMaxHeap{Int}()
+
+        @test length(h) == 0
+        @test isempty(h)
+        @test eltype(h) == Int
+        @test eltype(typeof(h)) == Int
+    end
     
     @testset "make heap tests" begin
         vs = [10, 4, 6, 1, 16, 2, 20, 17, 13, 5]
diff --git a/test/test_mutable_binheap.jl b/test/test_mutable_binheap.jl
index ed2f72c..1484bf4 100644
--- a/test/test_mutable_binheap.jl
+++ b/test/test_mutable_binheap.jl
@@ -54,6 +54,15 @@ end
 
     vs = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
 
+    @testset "basic tests" begin
+        h = MutableBinaryMinHeap{Int}()
+
+        @test length(h) == 0
+        @test isempty(h)
+        @test eltype(h) == Int
+        @test eltype(typeof(h)) == Int
+    end
+
     @testset "make mutable binary minheap" begin
         h = MutableBinaryMinHeap(vs)
 
diff --git a/test/test_mutable_list.jl b/test/test_mutable_list.jl
index c92c563..b5f51aa 100644
--- a/test/test_mutable_list.jl
+++ b/test/test_mutable_list.jl
@@ -9,6 +9,7 @@
         @test lastindex(l1) == 0
         @test collect(l1) == Int[]
         @test eltype(l1) == Int
+        @test eltype(typeof(l1)) == Int
         @test_throws ArgumentError pop!(l1)
         @test_throws ArgumentError popfirst!(l1)
     end
diff --git a/test/test_queue.jl b/test/test_queue.jl
index 1d9d4de..d689a44 100644
--- a/test/test_queue.jl
+++ b/test/test_queue.jl
@@ -13,6 +13,8 @@
         n = 100
 
         @test length(s) == 0
+        @test eltype(s) == Int
+        @test eltype(typeof(s)) == Int
         @test isempty(s)
         @test_throws ArgumentError front(s)
         @test_throws ArgumentError back(s)
diff --git a/test/test_stack.jl b/test/test_stack.jl
index 38d2b3b..60460e4 100644
--- a/test/test_stack.jl
+++ b/test/test_stack.jl
@@ -15,6 +15,8 @@
         @test isa(s, Stack{Int})
         @test length(s) == 0
         @test isempty(s)
+        @test eltype(s) == Int
+        @test eltype(typeof(s)) == Int
         @test_throws ArgumentError top(s)
         @test_throws ArgumentError pop!(s)