Repository: JuliaCollections/DataStructures.jl
Pull request #524 (2019-08-14 09:29:15)

deprecate ClassifierCollection
First part of #496  

I don't know what to recommend using instead.
Probably a `DefaultDict(Collection)`?



Patch:
diff --git a/.gitignore b/.gitignore
index ead5283..fb1a162 100644
--- a/.gitignore
+++ b/.gitignore
@@ -3,3 +3,4 @@ docs/build/
 docs/site/
 docs/Manifest.toml
 Manifest.toml
+benchmark/*.json
diff --git a/.travis.yml b/.travis.yml
index 185caf2..da20077 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -22,8 +22,25 @@ after_success:
 # https://juliadocs.github.io/Documenter.jl/stable/man/hosting/#.travis.yml-Configuration-1
 jobs:
   include:
+    - name: "Benchmark"
+      julia: 1.2
+      os: linux
+      before_script:
+        - git fetch origin '+refs/heads/master:refs/remotes/origin/master'
+        - git branch baseline origin/master
+        # Run benchmark outside `script` so that it's hidden by default:
+        - julia --project=benchmark -e '
+              using Pkg; Pkg.instantiate();
+              include("benchmark/runjudge.jl");'
+
+      script:
+        - julia --project=benchmark -e '
+              using Pkg; Pkg.instantiate();
+              include("benchmark/pprintjudge.jl");'
+      after_success: skip
+      if: type = pull_request
     - stage: "Documentation"
-      julia: 1.0
+      julia: 1.2
       os: linux
       script:
         - julia --project=docs/ -e 'using Pkg; Pkg.develop(PackageSpec(path=pwd()));
diff --git a/Changelog.md b/Changelog.md
index c0be3f8..00de0e4 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -91,7 +91,7 @@ v0.4.2 / 2016-01-13
 ==================
 
   * Fix OrderedDict constructors (with tests)
-  * Add IntSet to DataStructures 
+  * Add IntSet to DataStructures
     (see #114, https://github.com/JuliaLang/julia/pull/10065)
   * Dead code, tree.jl removal
 
@@ -341,7 +341,7 @@ v0.2.5 / 2013-10-08
   * Revised implementation of Deque, without using Union(Nothing, DequeBlock).
   * Fixed the doc regarding API for heaps: binary_heap -> binary_{min|max}heap and mutable_binary_heap -> mutable_binary_{min|max}heap
   * Added 1 missing API call to the documentation
-  * Fixed bugs related to Dequeue functions front and back. 
+  * Fixed bugs related to Dequeue functions front and back.
     * Front would give garbage data when called on a newly created queue, and back when popping a queue from the front.
   * Implemented simple show method inside Dequeue to hide unnecessary (large!) implementation detail from the client, in particular when using REPL
 
@@ -374,4 +374,3 @@ v0.2.5 / 2013-10-08
   * add stack and queue (tested)
   * add Dequeue (tested)
   * Initial commit
-
diff --git a/Project.toml b/Project.toml
index 80e3d6b..fd2280a 100644
--- a/Project.toml
+++ b/Project.toml
@@ -1,6 +1,6 @@
 name = "DataStructures"
 uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
-version = "0.17.0"
+version = "0.17.4"
 
 [deps]
 InteractiveUtils = "b77e0a4c-d291-57a0-90e8-8db25a27a240"
diff --git a/README.md b/README.md
index 183b572..28c4d84 100644
--- a/README.md
+++ b/README.md
@@ -29,6 +29,7 @@ This package implements a variety of data structures, including
 -   DataStructures.IntSet
 -   Priority Queue
 -   Fenwick Tree
+-   SparseIntSet
 
 Resources
 ---------
diff --git a/REQUIRE b/REQUIRE
deleted file mode 100644
index 2d93685..0000000
--- a/REQUIRE
+++ /dev/null
@@ -1,2 +0,0 @@
-julia 0.7
-OrderedCollections 1.0.1
diff --git a/benchmark/Project.toml b/benchmark/Project.toml
new file mode 100644
index 0000000..16acc49
--- /dev/null
+++ b/benchmark/Project.toml
@@ -0,0 +1,3 @@
+[deps]
+BenchmarkTools = "6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf"
+PkgBenchmark = "32113eaa-f34f-5b0d-bd6c-c81e245fc73d"
diff --git a/benchmark/README.md b/benchmark/README.md
new file mode 100644
index 0000000..fca9ed4
--- /dev/null
+++ b/benchmark/README.md
@@ -0,0 +1,43 @@
+## Notes on regression testing with PkgBenchmark
+
+### To troubleshoot benchmark script locally:
+```
+julia --project=benchmark -e '
+    using Pkg; Pkg.instantiate();
+    include("benchmark/runbenchmarks.jl");'
+```
+
+### To compare against baseline locally:
+
+Note, must have a `baseline` branch, which will be the refrence point against the currently active branch. A common use case is to point the baseline to the previous commit.
+
+This can be accomplished with
+```
+git branch baseline HEAD~
+```
+
+If there are errors preventing branch creation (likely due to earlier local benchmarking), may force a repoint with
+```
+git branch -f baseline HEAD~
+```
+
+Then run this command:
+```
+julia --project=benchmark -e '
+    using Pkg; Pkg.instantiate();
+    include("benchmark/runjudge.jl");
+    include("benchmark/pprintjudge.jl");'
+```
+
+### To compare against baseline locally (without re-running baseline):
+
+Running the above baseline comparison produces a `benchmark/result-baseline.json` file which is
+used as a refrence for new changes.
+If the baseline remains unchanged during development, then it is unnecessary to regenerate this file,
+and the following command may be used to save benchmarking time.
+```
+julia --project=benchmark -e '
+    using Pkg; Pkg.instantiate();
+    include("benchmark/incrementalrunjudge.jl");
+    include("benchmark/pprintjudge.jl");'
+```
\ No newline at end of file
diff --git a/benchmark/bench_heap.jl b/benchmark/bench_heap.jl
new file mode 100644
index 0000000..db70ec0
--- /dev/null
+++ b/benchmark/bench_heap.jl
@@ -0,0 +1,107 @@
+module BenchHeap
+
+using DataStructures
+using BenchmarkTools
+using Random
+
+function push_heap(h::AbstractHeap, xs::Vector)
+    n = length(xs)
+
+    for i = 1 : n
+        push!(h, xs[i])
+    end
+end
+
+function pop_heap(h::AbstractHeap)
+    n = length(h)
+
+    for i = 1 : n
+        pop!(h)
+    end
+end
+
+suite = BenchmarkGroup()
+
+heaptypes = [BinaryHeap, MutableBinaryHeap]
+aexps = [1,3]
+datatypes = [Int, Float64]
+baseorderings = Dict(
+    "Min" => DataStructures.LessThan,
+    #"Max" => DataStructures.GreaterThan,
+    )
+fastfloatorderings = Dict(
+    # These will be enabled upon reordering change
+    #"FastMin" => DataStructures.FasterForward(),
+    #"FastMax" => DataStructures.FasterReverse(),
+    )
+
+for heap in heaptypes
+    for aexp in aexps
+        for dt in datatypes
+            Random.seed!(0)
+            a = rand(dt, 10^aexp)
+
+            orderings = baseorderings
+            if dt == Float64
+                # swap to faster ordering operation
+                for (k,v) in orderings
+                    if haskey(fastfloatorderings, k)
+                        orderings["Slow"*k] = v
+                        orderings[k] = fastfloatorderings[k]
+                    end
+                end
+            end
+
+            for (ord_str, ord) in orderings
+                prepath = [string(heap)]
+                postpath = [string(dt), "10^"*string(aexp), ord_str]
+                suite[vcat(prepath, ["make"], postpath)] =
+                    @benchmarkable $(heap){$dt,$ord}($a)
+                suite[vcat(prepath, ["push"], postpath)] =
+                    @benchmarkable push_heap(h, $a) setup=(h=$(heap){$dt,$ord}())
+                suite[vcat(prepath, ["pop"], postpath)] =
+                    @benchmarkable pop_heap(h) setup=(h=$(heap){$dt,$ord}($a))
+            end
+        end
+    end
+end
+
+# Quick check to ensure no Float regressions with Min/Max convenience functions
+# These don't fit in well with the above loop, since ordering is hardcoded.
+heapalias = Dict(
+    "BinaryMinHeap" => BinaryMinHeap,
+    "BinaryMaxHeap" => BinaryMaxHeap,
+    "BinaryMinMaxHeap" => BinaryMinMaxHeap, # <- no alias issue
+)
+for (heapname, heap) in heapalias
+    for aexp in aexps
+        for dt in [Float64]
+            Random.seed!(0)
+            a = rand(dt, 10^aexp)
+            prepath = [heapname]
+            postpath = [string(dt), "10^"*string(aexp)]
+            suite[vcat(prepath, ["make"], postpath)] =
+                @benchmarkable $(heap)($a)
+            suite[vcat(prepath, ["push"], postpath)] =
+                @benchmarkable push_heap(h, $a) setup=(h=$(heap){$dt}())
+            suite[vcat(prepath, ["pop"], postpath)] =
+                @benchmarkable pop_heap(h) setup=(h=$(heap)($a))
+        end
+    end
+end
+
+for func in [nlargest, nsmallest]
+    for aexp in [4]
+        Random.seed!(0);
+        a = rand(10^aexp);
+        for nexp in [2]
+            n = 10^nexp
+            suite[[string(func), "a=rand(10^"*string(aexp)*")", "n=10^"*string(nexp)]] =
+                @benchmarkable $(func)($n, $a)
+        end
+    end
+end
+
+end  # module
+
+BenchHeap.suite
diff --git a/benchmark/bench_sparse_int_set.jl b/benchmark/bench_sparse_int_set.jl
new file mode 100644
index 0000000..7e1c0b3
--- /dev/null
+++ b/benchmark/bench_sparse_int_set.jl
@@ -0,0 +1,77 @@
+module BenchSparseIntSet
+
+using DataStructures
+using BenchmarkTools
+using Random
+
+suite = BenchmarkGroup()
+
+rand_setup =  (
+	Random.seed!(1234);
+	ids1 = rand(1:30000, 1000);
+	ids2 = rand(1:30000, 1000);
+)
+
+function create_fill_packed(ids1)
+	y = SparseIntSet()
+	for i in ids1
+		push!(y, i)
+	end
+end
+
+suite["create_fill"] =
+	@benchmarkable create_fill_packed(ids1) setup=rand_setup
+
+suite["in while not in"] =
+	@benchmarkable in(23, y) evals=1000 setup=(y = SparseIntSet();)
+suite["in while in"] =
+	@benchmarkable in(5199, y) evals=1000 setup=(y=SparseIntSet(); push!(y, 5199))
+
+function pop_push(y)
+	pop!(y, 5199)
+	push!(y, 5199)
+end
+
+suite["pop push worst case"] = @benchmarkable pop_push(y) setup=(y=SparseIntSet(); push!(y, 5199))
+suite["pop push"] = @benchmarkable pop_push(y) setup=(y=SparseIntSet(); push!(y, 5199); push!(y, 5200))
+
+function iterate_one_bench(x)
+	t = 0
+	for i in x
+		t += i
+	end
+	return t
+end
+function iterate_two_bench(x,y)
+	t = 0
+	for (ix, iy) in zip(x, y)
+		t += ix + iy
+	end
+	return t
+end
+function iterate_two_exclude_one_bench(x,y,z)
+	t = 0
+	for (ix, iy) in zip(x, y, exclude=(z,))
+		t += ix + iy
+	end
+	return t
+end
+
+x_y_z_setup = (
+	Random.seed!(1234);
+	x = SparseIntSet(rand(1:30000, 1000));
+	y = SparseIntSet(rand(1:30000, 1000));
+	z = SparseIntSet(rand(1:30000, 1000));
+)
+
+suite["iterate one"] =
+	@benchmarkable iterate_one_bench(x) setup=x_y_z_setup
+
+suite["iterate two"] =
+	@benchmarkable iterate_two_bench(x,y) setup=x_y_z_setup
+
+suite["iterate two exclude one"] =
+	@benchmarkable iterate_two_exclude_one_bench(x,y,z) setup=x_y_z_setup
+
+end  # module
+BenchSparseIntSet.suite
diff --git a/benchmark/benchmarks.jl b/benchmark/benchmarks.jl
new file mode 100644
index 0000000..38e03e6
--- /dev/null
+++ b/benchmark/benchmarks.jl
@@ -0,0 +1,14 @@
+using Pkg
+tempdir = mktempdir()
+Pkg.activate(tempdir)
+Pkg.develop(PackageSpec(path=joinpath(@__DIR__, "..")))
+Pkg.add(["BenchmarkTools", "PkgBenchmark", "Random"])
+Pkg.resolve()
+
+using DataStructures
+using BenchmarkTools
+
+const SUITE = BenchmarkGroup()
+
+SUITE["heap"] = include("bench_heap.jl")
+SUITE["SparseIntSet"] = include("bench_sparse_int_set.jl")
diff --git a/benchmark/incrementalrunjudge.jl b/benchmark/incrementalrunjudge.jl
new file mode 100644
index 0000000..ffe91c7
--- /dev/null
+++ b/benchmark/incrementalrunjudge.jl
@@ -0,0 +1,17 @@
+# This file was copied from Transducers.jl
+# which is available under an MIT license (see LICENSE).
+using PkgBenchmark
+
+mkconfig(; kwargs...) =
+    BenchmarkConfig(
+        env = Dict(
+            "JULIA_NUM_THREADS" => "1",
+        );
+        kwargs...
+    )
+
+group_target = benchmarkpkg(
+    dirname(@__DIR__),
+    mkconfig(),
+    resultfile = joinpath(@__DIR__, "result-target.json"),
+)
diff --git a/benchmark/pprinthelper.jl b/benchmark/pprinthelper.jl
new file mode 100644
index 0000000..bf31d85
--- /dev/null
+++ b/benchmark/pprinthelper.jl
@@ -0,0 +1,22 @@
+# This file was copied from Transducers.jl
+# which is available under an MIT license (see LICENSE).
+using PkgBenchmark
+using Markdown
+
+function displayresult(result)
+    md = sprint(export_markdown, result)
+    md = replace(md, ":x:" => "❌")
+    md = replace(md, ":white_check_mark:" => "✅")
+    display(Markdown.parse(md))
+end
+
+function printnewsection(name)
+    println()
+    println()
+    println()
+    printstyled("▃" ^ displaysize(stdout)[2]; color=:blue)
+    println()
+    printstyled(name; bold=true)
+    println()
+    println()
+end
diff --git a/benchmark/pprintjudge.jl b/benchmark/pprintjudge.jl
new file mode 100644
index 0000000..fb634e5
--- /dev/null
+++ b/benchmark/pprintjudge.jl
@@ -0,0 +1,15 @@
+# This file was copied from Transducers.jl
+# which is available under an MIT license (see LICENSE).
+using PkgBenchmark
+include("pprinthelper.jl")
+group_target = PkgBenchmark.readresults(joinpath(@__DIR__, "result-target.json"))
+group_baseline = PkgBenchmark.readresults(joinpath(@__DIR__, "result-baseline.json"))
+judgement = judge(group_target, group_baseline)
+
+displayresult(judgement)
+
+printnewsection("Target result")
+displayresult(group_target)
+
+printnewsection("Baseline result")
+displayresult(group_baseline)
diff --git a/benchmark/runbenchmarks.jl b/benchmark/runbenchmarks.jl
new file mode 100644
index 0000000..1f70070
--- /dev/null
+++ b/benchmark/runbenchmarks.jl
@@ -0,0 +1,12 @@
+# This file was copied from Transducers.jl
+# which is available under an MIT license (see LICENSE).
+using PkgBenchmark
+benchmarkpkg(
+    dirname(@__DIR__),
+    BenchmarkConfig(
+        env = Dict(
+            "JULIA_NUM_THREADS" => "1",
+        ),
+    ),
+    resultfile = joinpath(@__DIR__, "result.json"),
+)
diff --git a/benchmark/runjudge.jl b/benchmark/runjudge.jl
new file mode 100644
index 0000000..c0b5603
--- /dev/null
+++ b/benchmark/runjudge.jl
@@ -0,0 +1,25 @@
+# This file was copied from Transducers.jl
+# which is available under an MIT license (see LICENSE).
+using PkgBenchmark
+
+mkconfig(; kwargs...) =
+    BenchmarkConfig(
+        env = Dict(
+            "JULIA_NUM_THREADS" => "1",
+        );
+        kwargs...
+    )
+
+group_target = benchmarkpkg(
+    dirname(@__DIR__),
+    mkconfig(),
+    resultfile = joinpath(@__DIR__, "result-target.json"),
+)
+
+group_baseline = benchmarkpkg(
+    dirname(@__DIR__),
+    mkconfig(id = "baseline"),
+    resultfile = joinpath(@__DIR__, "result-baseline.json"),
+)
+
+judgement = judge(group_target, group_baseline)
diff --git a/docs/Project.toml b/docs/Project.toml
index dfa65cd..d7906fc 100644
--- a/docs/Project.toml
+++ b/docs/Project.toml
@@ -1,2 +1,5 @@
 [deps]
 Documenter = "e30172f5-a6a5-5a46-863b-614d45cd2de4"
+
+[compat]
+Documenter = "0.23"
diff --git a/docs/make.jl b/docs/make.jl
index 26e8573..35424e2 100644
--- a/docs/make.jl
+++ b/docs/make.jl
@@ -1,9 +1,9 @@
 using Documenter
 using DataStructures
 
+DocMeta.setdocmeta!(DataStructures, :DocTestSetup, :(using DataStructures); recursive=true)
 
 makedocs(
-    format = :html,
     sitename = "DataStructures.jl",
     pages = [
         "index.md",
@@ -24,14 +24,10 @@ makedocs(
         "intset.md",
         "sorted_containers.md",
     ],
-    modules = [DataStructures]
+    modules = [DataStructures],
+    format = Documenter.HTML()
 )
 
 deploydocs(
     repo = "github.com/JuliaCollections/DataStructures.jl.git",
-    julia  = "0.7",
-    latest = "master",
-    target = "build",
-    deps = nothing,  # we use the `format = :html`, without `mkdocs`
-    make = nothing,  # we use the `format = :html`, without `mkdocs`
 )
diff --git a/docs/mkdocs.yml b/docs/mkdocs.yml
deleted file mode 100644
index f6affbd..0000000
--- a/docs/mkdocs.yml
+++ /dev/null
@@ -1,24 +0,0 @@
-site_name:        DataStructures.jl
-repo_url:         https://github.com/JuliaCollections/DataStructures.jl
-site_description: Documentation for the Julia DataStructures package
-site_author:      JuliaCollections
-
-theme: readthedocs
-
-extra_css:
-  - assets/Documenter.css
-
-extra_javascript:
-  - https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS_HTML
-  - assets/mathjaxhelper.js
-
-markdown_extensions:
-  - extra
-  - tables
-  - fenced_code
-  - mdx_math
-
-docs_dir: 'build'
-
-pages:
-  - Home: index.md
diff --git a/docs/src/heaps.md b/docs/src/heaps.md
index 2d43930..01eab09 100644
--- a/docs/src/heaps.md
+++ b/docs/src/heaps.md
@@ -55,7 +55,7 @@ h = MutableBinaryMaxHeap([1,4,3,2])    # create a mutable min/max heap from a ve
 ```
 
 ## Min-max heaps
-Min-max heaps maintain the minimum _and_ the maximum of a set, 
+Min-max heaps maintain the minimum _and_ the maximum of a set,
 allowing both to be retrieved in constant (`O(1)`) time.
 The min-max heaps in this package are subtypes of `AbstractMinMaxHeap <: AbstractHeap`
 and have the same interface as other heaps with the following additions:
@@ -73,7 +73,7 @@ popmax!(h, k)  # remove and return the largest k elements
 popall!(h)     # remove and return all the elements, sorted smallest to largest
 popall!(h, o)  # remove and return all the elements according to ordering o
 ```
-The usual `top(h)` and `pop!(h)` are defined to be `minimum(h)` and `popmin!(h)`, 
+The usual `top(h)` and `pop!(h)` are defined to be `minimum(h)` and `popmin!(h)`,
 respectively.
 
 This package includes an implementation of a binary min-max heap (`BinaryMinMaxHeap`).
diff --git a/docs/src/index.md b/docs/src/index.md
index 16e3a10..8854f4a 100644
--- a/docs/src/index.md
+++ b/docs/src/index.md
@@ -38,8 +38,9 @@ Pages = [
     "robin_dict.md",
     "trie.md",
     "linked_list.md",
-    "mutable_linked_list.md"
+    "mutable_linked_list.md",
     "intset.md",
     "sorted_containers.md",
+    "sparse_int_set.md"
 ]
 ```
diff --git a/docs/src/priority-queue.md b/docs/src/priority-queue.md
index b456361..4958f65 100644
--- a/docs/src/priority-queue.md
+++ b/docs/src/priority-queue.md
@@ -1,3 +1,7 @@
+```@meta
+DocTestSetup = :(using DataStructures)
+```
+
 # Priority Queue
 
 The `PriorityQueue` type provides a basic priority queue implementation
@@ -23,21 +27,25 @@ inserted and priorities accessed or changed using indexing notation.
 
 Examples:
 
-```julia
+```jldoctest
 julia> # Julia code
        pq = PriorityQueue();
 
 julia> # Insert keys with associated priorities
        pq["a"] = 10; pq["b"] = 5; pq["c"] = 15; pq
-DataStructures.PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
-  "c" => 15
+PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
   "b" => 5
   "a" => 10
+  "c" => 15
 
 julia> # Change the priority of an existing key
        pq["a"] = 0; pq
-DataStructures.PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
-  "c" => 15
-  "b" => 5
+PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
   "a" => 0
+  "b" => 5
+  "c" => 15
+```
+
+```@meta
+DocTestSetup = nothing
 ```
diff --git a/docs/src/robin_dict.md b/docs/src/robin_dict.md
index c17d4eb..0bb5655 100644
--- a/docs/src/robin_dict.md
+++ b/docs/src/robin_dict.md
@@ -1,3 +1,7 @@
+```@meta
+DocTestSetup = :(using DataStructures)
+```
+
 # RobinDict
 
 `RobinDict` provides a standard dictionary, conforming to the AbstractDict protocol, which uses the Robin Hood hashing algorithm with backward-shift deletion to provide improved average performance over Dict.
@@ -6,7 +10,7 @@ The interface of `RobinDict` replicates that of `Dict`.
 
 Examples:
 
-```julia
+```jldoctest
 julia> d = RobinDict{Int, Char}(1 => 'a', 2 => 'b')
 RobinDict{Int64,Char} with 2 entries:
   2 => 'b'
@@ -34,3 +38,6 @@ julia> pop!(d)
 3 => 'c'
 ```
 
+```@meta
+DocTestSetup = nothing
+```
diff --git a/docs/src/sorted_containers.md b/docs/src/sorted_containers.md
index 86398ae..5fda05c 100644
--- a/docs/src/sorted_containers.md
+++ b/docs/src/sorted_containers.md
@@ -185,10 +185,6 @@ call, and _c_ denotes the time needed to compare two keys.
 
 ```@docs
 getindex(m::SortedDict, k_)
-```
-
-```@docs
-find(m::SortedDict, k_)
 ```
 
     deref((sc, st))
@@ -456,7 +452,7 @@ end
 
 Here, `st1` and `st2` are semitokens that refer to the container `sc`.
 Token `(sc,st1)` may not be the before-start token and
-token `(sc,st2)` may not be the past-end token. 
+token `(sc,st2)` may not be the past-end token.
 It is acceptable for `(sc,st1)` to be the past-end token or `(sc,st2)`
 to be the before-start token or both (in these cases, the body is not executed).
 If `compare(sc,st1,st2)==1` then the body is not executed. A second
@@ -647,10 +643,6 @@ valtype(sc::SortedDict)
 ordtype(sc::SortedDict)
 ```
 
-```@docs
-similar(sc::SortedDict)
-```
-
 ```@docs
 orderobject(sc::SortedDict)
 ```
@@ -773,7 +765,7 @@ Lt((x,y) -> isless(lowercase(x),lowercase(y)))
 The ordering object is indicated in the above list of constructors in
 the `o` position (see above for constructor syntax).
 
-This approach may suffer from a performance hit because higher performance 
+This approach may suffer from a performance hit because higher performance
 may be possible if an equality method is also available as well as a
 less-than method.
 A more complicated but higher-performance method to implement
diff --git a/docs/src/sparse_int_set.md b/docs/src/sparse_int_set.md
new file mode 100644
index 0000000..452318b
--- /dev/null
+++ b/docs/src/sparse_int_set.md
@@ -0,0 +1,8 @@
+# DataStructures.SparseIntSet
+
+Implementation of a __Sparse Integer Set__, for background see [Sparse Sets](https://www.computist.xyz/2018/06/sparse-sets.html).
+Only positive non-zero `Int`s are allowed inside the set.
+The idea is to have one **packed** `Vector` storing all the `Int`s contained in the set as to allow for fast iteration, and a sparse, paged **reverse** `Vector` with the position of a particular `Int` inside the **packed** `Vector`. This allows for very fast iteration, insertion and deletion of indices.
+Most behavior is similar to a normal `IntSet`, however `collect`, `first` and `last` are with respected to the **packed** vector, in which the ordering is not guaranteed.
+The **reverse** `Vector` is paged, meaning that it is a `Vector{Vector{Int}}` where each of the `Vector{Int}`s has the length of one memory page of `Int`s. Every time an index that was not yet in the range of the already present pages, a new one will be created and added to the **reverse**, allowing for dynamical growth.
+Popping the last `Int` of a particular page will automatically clean up the memory of that page.
diff --git a/src/DataStructures.jl b/src/DataStructures.jl
index 7ec2f77..cad5f76 100644
--- a/src/DataStructures.jl
+++ b/src/DataStructures.jl
@@ -104,4 +104,6 @@ module DataStructures
     export PriorityQueue, peek
 
     include("priorityqueue.jl")
+    include("sparse_int_set.jl")
+    export SparseIntSet
 end
diff --git a/src/circular_buffer.jl b/src/circular_buffer.jl
index c687bed..58f1448 100644
--- a/src/circular_buffer.jl
+++ b/src/circular_buffer.jl
@@ -1,8 +1,8 @@
 """
     CircularBuffer{T}(n)
 
-The CircularBuffer type implements a circular buffer of fixed capacity 
-where new items are pushed to the back of the list, overwriting values 
+The CircularBuffer type implements a circular buffer of fixed capacity
+where new items are pushed to the back of the list, overwriting values
 in a circular fashion.
 
 Allocate a buffer of elements of type `T` with maximum capacity `n`.
@@ -115,7 +115,7 @@ end
 """
     pushfirst!(cb, data)
 
-Insert one or more items at the beginning of CircularBuffer 
+Insert one or more items at the beginning of CircularBuffer
 and overwrite back if full.
 """
 function pushfirst!(cb::CircularBuffer, data)
@@ -193,3 +193,26 @@ capacity(cb::CircularBuffer) = cb.capacity
 Test whether the buffer is full.
 """
 isfull(cb::CircularBuffer) = length(cb) == cb.capacity
+
+"""
+    first(cb)
+
+Get the first element of CircularBuffer.
+"""
+Base.@propagate_inbounds function Base.first(cb::CircularBuffer)
+    @boundscheck if cb.length == 0
+        throw(BoundsError(cb, 1))
+    end
+    cb.buffer[cb.first]
+end
+"""
+    last(cb)
+
+Get the last element of CircularBuffer.
+"""
+Base.@propagate_inbounds function Base.last(cb::CircularBuffer)
+    @boundscheck if cb.length == 0
+        throw(BoundsError(cb, 1))
+    end
+    cb.buffer[_buffer_index(cb, cb.length)]
+end
diff --git a/src/classified_collections.jl b/src/classified_collections.jl
index 25a4c94..8684976 100644
--- a/src/classified_collections.jl
+++ b/src/classified_collections.jl
@@ -6,6 +6,11 @@
 
 mutable struct ClassifiedCollections{K, Collection}
     map::Dict{K, Collection}
+
+    function ClassifiedCollections{K, Collection}(map) where {K, Collection}
+        @warn "ClassifiedCollections will be removed from DataStructures.jl in v0.18."
+        return new(map)
+    end
 end
 
 ## constructors
diff --git a/src/container_loops.jl b/src/container_loops.jl
index 1a09fcd..fce62c5 100644
--- a/src/container_loops.jl
+++ b/src/container_loops.jl
@@ -258,7 +258,7 @@ onlysemitokens(ba::SAIterableTypesBase) = SAOnlySemiTokensIteration(ba)
 
 
 
-    
+
 function nexthelper(c::SAContainer, state::SAIterationState)
     sn = state.next
     (sn < 3 || !(sn in c.bt.useddatacells)) && throw(BoundsError())
@@ -266,12 +266,12 @@ function nexthelper(c::SAContainer, state::SAIterationState)
 end
 
 
-    
+
 getitem(::SDMIterableTypesBase, dt, sn) = dt.k => dt.d
 getitem(::SSIterableTypesBase, dt, sn) = dt.k
 getitem(::SDMKeyIteration, dt, sn) = dt.k
 getitem(::SDMValIteration, dt, sn) = dt.d
-getitem(::SDMSemiTokenIteration, dt, sn) = (IntSemiToken(sn), dt.k, dt.d) 
+getitem(::SDMSemiTokenIteration, dt, sn) = (IntSemiToken(sn), dt.k, dt.d)
 getitem(::SSSemiTokenIteration, dt, sn) = (IntSemiToken(sn), dt.k)
 getitem(::SDMSemiTokenKeyIteration, dt, sn) = (IntSemiToken(sn), dt.k)
 getitem(::SDMSemiTokenValIteration, dt, sn) = (IntSemiToken(sn), dt.d)
diff --git a/src/fenwick.jl b/src/fenwick.jl
index c1d078b..22a3a1f 100644
--- a/src/fenwick.jl
+++ b/src/fenwick.jl
@@ -5,17 +5,17 @@ end
 
 """
     FenwickTree{T}(n)
-    
+
 Constructs a [`FenwickTree`](https://en.wikipedia.org/wiki/Fenwick_tree) of length `n`.
- 
+
 """
 FenwickTree{T}(n::Integer) where T = FenwickTree{T}(zeros(T, n), n)
 
 """
-    FenwickTree(counts::AbstractArray) 
-    
+    FenwickTree(counts::AbstractArray)
+
 Constructs a [`FenwickTree`](https://en.wikipedia.org/wiki/Fenwick_tree) from an array of `counts`
- 
+
 """
 function FenwickTree(a::AbstractVector{U}) where U
     n = length(a)
@@ -34,7 +34,7 @@ Base.eltype(::Type{FenwickTree{T}}) where T = T
 
 Increases the value of the [`FenwickTree`] by `val` from the index `ind` upto the length of the Fenwick Tree.
 
-""" 
+"""
 function inc!(ft::FenwickTree{T}, ind::Integer, val = 1) where T
     val0 = convert(T, val)
     i = ind
@@ -51,7 +51,7 @@ end
 
 Decreases the value of the [`FenwickTree`] by `val` from the index `ind` upto the length of the Fenwick Tree.
 
-""" 
+"""
 dec!(ft::FenwickTree, ind::Integer, val = 1 ) = inc!(ft, ind, -val)
 
 """
@@ -59,7 +59,7 @@ dec!(ft::FenwickTree, ind::Integer, val = 1 ) = inc!(ft, ind, -val)
 
 Increases the value of the [`FenwickTree`] by `val` from the indices from `left` and decreases it from the `right`.
 
-"""    
+"""
 function incdec!(ft::FenwickTree{T}, left::Integer, right::Integer, val = one(T)) where T
     val0 = convert(T, val)
     inc!(ft, left, val0)
@@ -68,7 +68,7 @@ end
 
 """
     prefixsum(ft::FenwickTree{T}, ind)
-    
+
 Return the cumulative sum from index 1 upto `ind` of the [`FenwickTree`](@ref)
 
 # Examples
@@ -86,7 +86,7 @@ function prefixsum(ft::FenwickTree{T}, ind::Integer) where T
     i = ind
     n = ft.n
     @boundscheck 1 <= i <= n || throw(ArgumentError("$i should be in between 1 and $n"))
-    @inbounds while i > 0 
+    @inbounds while i > 0
         sum += ft.bi_tree[i]
         i -= i&(-i)
     end
diff --git a/src/heaps/minmax_heap.jl b/src/heaps/minmax_heap.jl
index b86229d..5009c1a 100644
--- a/src/heaps/minmax_heap.jl
+++ b/src/heaps/minmax_heap.jl
@@ -6,9 +6,9 @@
 
 mutable struct BinaryMinMaxHeap{T} <: AbstractMinMaxHeap{T}
     valtree::Vector{T}
-    
+
     BinaryMinMaxHeap{T}() where {T} = new{T}(Vector{T}())
-    
+
     function BinaryMinMaxHeap(xs::AbstractVector{T}) where {T}
         valtree = _make_binary_minmax_heap(xs)
         new{T}(valtree)
@@ -41,7 +41,7 @@ function _minmax_heap_bubble_up!(A::AbstractVector, i::Integer)
             # bubble up min
             _minmax_heap_bubble_up!(A, i, Forward)
         end
-        
+
     else
         # max level
         if i > 1 && A[i] < A[hparent(i)]
@@ -55,7 +55,7 @@ function _minmax_heap_bubble_up!(A::AbstractVector, i::Integer)
             _minmax_heap_bubble_up!(A, i, Reverse)
         end
     end
-   return 
+   return
 end
 
 function _minmax_heap_bubble_up!(A::AbstractVector, i::Integer, o::Ordering, x=A[i])
@@ -67,7 +67,7 @@ function _minmax_heap_bubble_up!(A::AbstractVector, i::Integer, o::Ordering, x=A
             _minmax_heap_bubble_up!(A, gparent, o)
         end
     end
-    return          
+    return
 end
 
 function _minmax_heap_trickle_down!(A::AbstractVector, i::Integer)
@@ -80,7 +80,7 @@ function _minmax_heap_trickle_down!(A::AbstractVector, i::Integer)
 end
 
 function _minmax_heap_trickle_down!(A::AbstractVector, i::Integer, o::Ordering, x=A[i])
-                    
+
     if haschildren(i, A)
         # get the index of the extremum (min or max) descendant
         extremum = o === Forward ? minimum : maximum
@@ -106,7 +106,7 @@ function _minmax_heap_trickle_down!(A::AbstractVector, i::Integer, o::Ordering,
     end
     return
 end
-                    
+
 ################################################
 #
 # utilities
@@ -118,10 +118,10 @@ end
 @inline rchild(i) = 2*i+1
 @inline children(i) = (lchild(i), rchild(i))
 @inline hparent(i) = i ÷ 2
-@inline on_minlevel(i) = level(i) % 2 == 0 
+@inline on_minlevel(i) = level(i) % 2 == 0
 @inline haschildren(i, A) = lchild(i) ≤ length(A)
 @inline isgrandchild(j, i) = j > rchild(i)
-@inline hasgrandparent(i) = i ≥ 4 
+@inline hasgrandparent(i) = i ≥ 4
 
 """
     children_and_grandchildren(maxlen, i)
@@ -189,7 +189,7 @@ end
 
 """
     popmin!(h::BinaryMinMaxHeap) -> min
-                        
+
 Remove the minimum value from the heap.
 """
 function popmin!(h::BinaryMinMaxHeap)
@@ -204,19 +204,19 @@ function popmin!(h::BinaryMinMaxHeap)
     return x
 end
 
-                        
+
 """
     popmin!(h::BinaryMinMaxHeap, k::Integer) -> vals
-                        
+
 Remove up to the `k` smallest values from the heap.
 """
-@inline function popmin!(h::BinaryMinMaxHeap, k::Integer) 
+@inline function popmin!(h::BinaryMinMaxHeap, k::Integer)
     return [popmin!(h) for _ in 1:min(length(h), k)]
 end
 
 """
     popmax!(h::BinaryMinMaxHeap) -> max
-                        
+
 Remove the maximum value from the heap.
 """
 function popmax!(h::BinaryMinMaxHeap)
@@ -228,55 +228,54 @@ function popmax!(h::BinaryMinMaxHeap)
         @inbounds valtree[i] = y
         _minmax_heap_trickle_down!(valtree, i)
     end
-    return x    
+    return x
 end
 
 """
     popmax!(h::BinaryMinMaxHeap, k::Integer) -> vals
-                        
+
 Remove up to the `k` largest values from the heap.
 """
-@inline function popmax!(h::BinaryMinMaxHeap, k::Integer) 
-    return [popmax!(h) for _ in 1:min(length(h), k)]                    
+@inline function popmax!(h::BinaryMinMaxHeap, k::Integer)
+    return [popmax!(h) for _ in 1:min(length(h), k)]
 end
-                        
-                        
+
+
 function push!(h::BinaryMinMaxHeap, v)
-    valtree = h.valtree        
+    valtree = h.valtree
     push!(valtree, v)
     _minmax_heap_bubble_up!(valtree, length(valtree))
 end
 
 """
     top(h::BinaryMinMaxHeap)
-                        
+
 Get the top (minimum) of the heap.
 """
 @inline top(h::BinaryMinMaxHeap) = minimum(h)
 
-@inline function minimum(h::BinaryMinMaxHeap) 
+@inline function minimum(h::BinaryMinMaxHeap)
     valtree = h.valtree
     !isempty(h) || throw(ArgumentError("heap must be non-empty"))
     return @inbounds h.valtree[1]
 end
 
-@inline function maximum(h::BinaryMinMaxHeap) 
+@inline function maximum(h::BinaryMinMaxHeap)
     valtree = h.valtree
     !isempty(h) || throw(ArgumentError("heap must be non-empty"))
     return @inbounds maximum(valtree[1:min(end, 3)])
 end
-                        
+
 empty!(h::BinaryMinMaxHeap) = (empty!(h.valtree); h)
-                        
+
 
 """
     popall!(h::BinaryMinMaxHeap, ::Ordering = Forward)
-                        
+
 Remove and return all the elements of `h` according to
-the given ordering. Default is `Forward` (smallest to 
+the given ordering. Default is `Forward` (smallest to
 largest).
 """
 popall!(h::BinaryMinMaxHeap) = popall!(h, Forward)
 popall!(h::BinaryMinMaxHeap, ::ForwardOrdering) = popmin!(h, length(h))
 popall!(h::BinaryMinMaxHeap, ::ReverseOrdering) = popmax!(h, length(h))
-
diff --git a/src/heaps/mutable_binary_heap.jl b/src/heaps/mutable_binary_heap.jl
index 1d9c2f4..ef79931 100644
--- a/src/heaps/mutable_binary_heap.jl
+++ b/src/heaps/mutable_binary_heap.jl
@@ -165,25 +165,25 @@ mutable struct MutableBinaryHeap{VT, Comp} <: AbstractMutableHeap{VT,Int}
         new{VT, Comp}(Comp(), nodes, node_map)
     end
 
-    function MutableBinaryHeap{VT, Comp}(xs::AbstractVector{VT}) where {VT, Comp} 
+    function MutableBinaryHeap{VT, Comp}(xs::AbstractVector{VT}) where {VT, Comp}
         nodes, node_map = _make_mutable_binary_heap(Comp(), VT, xs)
         new{VT, Comp}(Comp(), nodes, node_map)
     end
 end
-                            
+
 const MutableBinaryMinHeap{T} = MutableBinaryHeap{T, LessThan}
 const MutableBinaryMaxHeap{T} = MutableBinaryHeap{T, GreaterThan}
-                            
+
 MutableBinaryMinHeap(xs::AbstractVector{T}) where T = MutableBinaryMinHeap{T}(xs)
 MutableBinaryMaxHeap(xs::AbstractVector{T}) where T = MutableBinaryMaxHeap{T}(xs)
 
 # deprecated constructors
-                            
+
 @deprecate mutable_binary_minheap(::Type{T}) where {T} MutableBinaryMinHeap{T}()
 @deprecate mutable_binary_minheap(xs::AbstractVector{T}) where {T} MutableBinaryMinHeap(xs)
 @deprecate mutable_binary_maxheap(::Type{T}) where {T} MutableBinaryMaxHeap{T}()
 @deprecate mutable_binary_maxheap(xs::AbstractVector{T}) where {T} MutableBinaryMaxHeap(xs)
-    
+
 
 function show(io::IO, h::MutableBinaryHeap)
     print(io, "MutableBinaryHeap(")
@@ -265,8 +265,8 @@ end
 """
     delete!{T}(h::MutableBinaryHeap{T}, i::Int)
 
-Deletes the element with handle `i` from heap `h` . 
-"""     
+Deletes the element with handle `i` from heap `h` .
+"""
 function delete!(h::MutableBinaryHeap{T}, i::Int) where T
      nd_id = h.node_map[i]
     _binary_heap_pop!(h.comparer, h.nodes, h.node_map, nd_id)
diff --git a/src/multi_dict.jl b/src/multi_dict.jl
index ad85118..7ac05b1 100644
--- a/src/multi_dict.jl
+++ b/src/multi_dict.jl
@@ -27,7 +27,7 @@ function multi_dict_with_eltype(kvs, ::Type{Tuple{K,V}}) where {K,V}
 end
 multi_dict_with_eltype(kvs, t) = MultiDict{Any,Any}(kvs)
 
-MultiDict(ps::Pair{K,V}...) where {K,V<:AbstractArray} = MultiDict{K, eltype(V)}(ps)
+
 MultiDict(kv::AbstractArray{Pair{K,V}}) where {K,V}  = MultiDict(kv...)
 function MultiDict(ps::Pair{K,V}...) where {K,V}
     md = MultiDict{K,V}()
@@ -56,20 +56,16 @@ empty!(d::MultiDict) = (empty!(d.d); d)
 
 function insert!(d::MultiDict{K,V}, k, v) where {K,V}
     if !haskey(d.d, k)
-        d.d[k] = isa(v, AbstractArray) ? eltype(v)[] : V[]
-    end
-    if isa(v, AbstractArray)
-        append!(d.d[k], v)
-    else
-        push!(d.d[k], v)
+        d.d[k] = V[]
     end
+    push!(d.d[k], v)
     return d
 end
 
 function in(pr::(Tuple{Any,Any}), d::MultiDict{K,V}) where {K,V}
     k = convert(K, pr[1])
     v = get(d,k,Base.secret_table_token)
-    (v !== Base.secret_table_token) && (isa(pr[2], AbstractArray) ? v == pr[2] : pr[2] in v)
+    (v !== Base.secret_table_token) && (pr[2] in v)
 end
 
 function pop!(d::MultiDict, key, default)
diff --git a/src/priorityqueue.jl b/src/priorityqueue.jl
index 7a02f81..38efea8 100644
--- a/src/priorityqueue.jl
+++ b/src/priorityqueue.jl
@@ -16,11 +16,11 @@ priorities, with the addition of a `dequeue!` function to remove the
 lowest priority element.
 
 ```jldoctest
-julia> a = PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward)
+julia> PriorityQueue(Base.Order.Forward, "a" => 2, "b" => 3, "c" => 1)
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
   "c" => 1
-  "b" => 3
   "a" => 2
+  "b" => 3
 ```
 """
 struct PriorityQueue{K,V,O<:Ordering} <: AbstractDict{K,V}
@@ -218,15 +218,15 @@ Insert the a key `k` into a priority queue `pq` with priority `v`.
 ```jldoctest
 julia> a = PriorityQueue(PriorityQueue("a"=>1, "b"=>2, "c"=>3))
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
-  "c" => 3
-  "b" => 2
   "a" => 1
+  "b" => 2
+  "c" => 3
 
 julia> enqueue!(a, "d"=>4)
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 4 entries:
-  "c" => 3
-  "b" => 2
   "a" => 1
+  "b" => 2
+  "c" => 3
   "d" => 4
 ```
 """
@@ -257,19 +257,19 @@ enqueue!(pq::PriorityQueue{K,V}, kv) where {K,V} = enqueue!(pq, Pair{K,V}(kv.fir
 Remove and return the lowest priority key from a priority queue.
 
 ```jldoctest
-julia> a = PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward)
+julia> a = PriorityQueue(Base.Order.Forward, ["a" => 2, "b" => 3, "c" => 1])
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
   "c" => 1
-  "b" => 3
   "a" => 2
+  "b" => 3
 
 julia> dequeue!(a)
 "c"
 
 julia> a
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 2 entries:
-  "b" => 3
   "a" => 2
+  "b" => 3
 ```
 """
 function dequeue!(pq::PriorityQueue)
@@ -297,19 +297,19 @@ end
 Remove and return a the lowest priority key and value from a priority queue as a pair.
 
 ```jldoctest
-julia> a = PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward)
+julia> a = PriorityQueue(Base.Order.Forward, "a" => 2, "b" => 3, "c" => 1)
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
   "c" => 1
-  "b" => 3
   "a" => 2
+  "b" => 3
 
 julia> dequeue_pair!(a)
 "c" => 1
 
 julia> a
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 2 entries:
-  "b" => 3
   "a" => 2
+  "b" => 3
 ```
 """
 function dequeue_pair!(pq::PriorityQueue)
@@ -338,10 +338,10 @@ Delete the mapping for the given key in a priority queue, and return the priorit
 julia> q = PriorityQueue(Base.Order.Forward, "a"=>2, "b"=>3, "c"=>1)
 PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
   "c" => 1
-  "b" => 3
   "a" => 2
+  "b" => 3
 julia> delete!(q, "b")
-DataStructures.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 2 entries:
+PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 2 entries:
   "c" => 1
   "a" => 2
 ```
@@ -381,7 +381,7 @@ function merge!(combine::Function, d::AbstractDict, other::PriorityQueue)
     return d
 end
 
-# Opaque not to be exported. 
+# Opaque not to be exported.
 mutable struct _PQIteratorState{K, V, O <: Ordering}
     pq::PriorityQueue{K, V, O}
     _PQIteratorState{K, V, O}(pq::PriorityQueue{K, V, O}) where {K, V, O <: Ordering} = new(pq)
@@ -400,7 +400,7 @@ _iterate(pq::PriorityQueue, ::Nothing) = nothing
 iterate(pq::PriorityQueue, ::Nothing) = nothing
 
 function iterate(pq::PriorityQueue, ordered::Bool=true)
-    if ordered 
+    if ordered
         isempty(pq) && return nothing
         state = _PQIteratorState(PriorityQueue(copy(pq.xs), pq.o, copy(pq.index)))
         return dequeue_pair!(state.pq), state
@@ -413,6 +413,5 @@ function iterate(pq::PriorityQueue, state::_PQIteratorState)
     isempty(state.pq) && return nothing
     return dequeue_pair!(state.pq), state
 end
-    
-iterate(pq::PriorityQueue, i) = _iterate(pq, iterate(pq.index, i))
 
+iterate(pq::PriorityQueue, i) = _iterate(pq, iterate(pq.index, i))
diff --git a/src/queue.jl b/src/queue.jl
index feb5d55..5fe6606 100644
--- a/src/queue.jl
+++ b/src/queue.jl
@@ -36,8 +36,12 @@ Removes an element from the front of the queue `s` and returns it.
 """
 dequeue!(s::Queue) = popfirst!(s.store)
 
+empty!(s::Queue) = (empty!(s.store); s)
+
 # Iterators
 
 iterate(q::Queue, s...) = iterate(q.store, s...)
 
 reverse_iter(q::Queue) = reverse_iter(q.store)
+
+==(x::Queue, y::Queue) = x.store == y.store
diff --git a/src/robin_dict.jl b/src/robin_dict.jl
index 4581f4e..f7e539e 100644
--- a/src/robin_dict.jl
+++ b/src/robin_dict.jl
@@ -91,7 +91,7 @@ end
 hash_key(key) = (hash(key)%UInt32) | 0x80000000
 desired_index(hash, sz) = (hash & (sz - 1)) + 1
 
-function calculate_distance(h::RobinDict{K, V}, index) where {K, V} 
+function calculate_distance(h::RobinDict{K, V}, index) where {K, V}
     @assert isslotfilled(h, index)
     sz = length(h.keys)
     @inbounds index_init = desired_index(h.hashes[index], sz)
@@ -102,7 +102,7 @@ end
 function rh_insert!(h::RobinDict{K, V}, key::K, val::V) where {K, V}
     # table full
     @assert h.count != length(h.keys)
-    
+
     ckey, cval, chash = key, val, hash_key(key)
     sz = length(h.keys)
     index_init = desired_index(chash, sz)
@@ -125,7 +125,7 @@ function rh_insert!(h::RobinDict{K, V}, key::K, val::V) where {K, V}
         probe_current += 1
         index_curr = (index_curr & (sz - 1)) + 1
     end
-    
+
     @inbounds if isslotfilled(h, index_curr) && isequal(h.keys[index_curr], ckey)
         h.vals[index_curr] = cval
         return index_curr
@@ -138,9 +138,9 @@ function rh_insert!(h::RobinDict{K, V}, key::K, val::V) where {K, V}
     @inbounds h.vals[index_curr] = cval
     @inbounds h.keys[index_curr] = ckey
     @inbounds h.hashes[index_curr] = chash
-    
+
     @assert probe_current >= 0
-    
+
     if h.idxfloor == 0
         h.idxfloor = index_curr
     else
@@ -152,7 +152,7 @@ end
 function rh_insert_for_rehash!(h_new::RobinDict{K, V}, key::K, val::V, hash::UInt32) where {K, V}
     # table full
     @assert h_new.count != length(h_new.keys)
-    
+
     ckey, cval, chash = key, val, hash
     sz = length(h_new.keys)
     index_init = desired_index(chash, sz)
@@ -183,9 +183,9 @@ function rh_insert_for_rehash!(h_new::RobinDict{K, V}, key::K, val::V, hash::UIn
     @inbounds h_new.vals[index_curr] = cval
     @inbounds h_new.keys[index_curr] = ckey
     @inbounds h_new.hashes[index_curr] = chash
-    
+
     @assert probe_current >= 0
-    
+
     if h_new.idxfloor == 0
         h_new.idxfloor = index_curr
     else
@@ -289,7 +289,7 @@ function empty!(h::RobinDict{K,V}) where {K, V}
     h.idxfloor = 0
     return h
 end
- 
+
 function rh_search(h::RobinDict{K, V}, key::K) where {K, V}
     sz = length(h.keys)
     chash = hash_key(key)
@@ -358,7 +358,7 @@ end
 
 function _get!(default::Callable, h::RobinDict{K,V}, key::K) where V where K
     index = rh_search(h, key)
-    
+
     index > 0 && return h.vals[index]
 
     v = convert(V, default())
@@ -415,7 +415,7 @@ end
 get(::Function, collection, key)
 
 function get(default::Callable, h::RobinDict{K,V}, key0) where {K, V}
-    key = convert(K, key0) 
+    key = convert(K, key0)
     index = rh_search(h, key)
     @inbounds return (index < 0) ? default() : h.vals[index]::V
 end
@@ -439,7 +439,7 @@ julia> haskey(D, 'c')
 false
 ```
 """
-haskey(h::RobinDict, key) = (rh_search(h, key) > 0) 
+haskey(h::RobinDict, key) = (rh_search(h, key) > 0)
 in(key, v::KeySet{<:Any, <:RobinDict}) = (rh_search(v.dict, key) >= 0)
 
 """
@@ -462,7 +462,7 @@ julia> getkey(D, 'd', 'a')
 ```
 """
 function getkey(h::RobinDict{K,V}, key0, default) where {K, V}
-    key = convert(K, key0) 
+    key = convert(K, key0)
     index = rh_search(h, key)
     @inbounds return (index < 0) ? default : h.keys[index]::K
 end
@@ -480,12 +480,12 @@ function rh_delete!(h::RobinDict{K, V}, index) where {K, V}
             break
         end
     end
-    #index0 represents the position before which we have to shift backwards 
-    
+    #index0 represents the position before which we have to shift backwards
+
     # the backwards shifting algorithm
     curr = index
     next = (index & (sz - 1)) + 1
-    
+
     @inbounds while next != index0
         h.vals[curr] = h.vals[next]
         h.keys[curr] = h.keys[next]
@@ -493,14 +493,14 @@ function rh_delete!(h::RobinDict{K, V}, index) where {K, V}
         curr = next
         next = (next & (sz-1)) + 1
     end
-    
+
     #curr is at the last position, reset back to normal
     isbitstype(K) || isbitsunion(K) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.keys, curr-1)
     isbitstype(V) || isbitsunion(V) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.vals, curr-1)
     @inbounds h.hashes[curr] = 0x0
 
     h.count -= 1
-    # this is necessary because key at idxfloor might get deleted 
+    # this is necessary because key at idxfloor might get deleted
     h.idxfloor = get_next_filled(h, h.idxfloor)
     return h
 end
@@ -512,7 +512,7 @@ function _pop!(h::RobinDict, index)
 end
 
 function pop!(h::RobinDict{K, V}, key0) where {K, V}
-    key = convert(K, key0) 
+    key = convert(K, key0)
     index = rh_search(h, key)
     return index > 0 ? _pop!(h, index) : throw(KeyError(key))
 end
@@ -542,7 +542,7 @@ julia> pop!(d, "e", 4)
 pop!(collection, key, default)
 
 function pop!(h::RobinDict{K, V}, key0, default) where {K, V}
-    key = convert(K, key0) 
+    key = convert(K, key0)
     index = rh_search(h, key)
     return index > 0 ? _pop!(h, index) : default
 end
@@ -574,7 +574,7 @@ RobinDict{String,Int64} with 1 entry:
 ```
 """
 function delete!(h::RobinDict{K, V}, key0) where {K, V}
-    key = convert(K, key0) 
+    key = convert(K, key0)
     index = rh_search(h, key)
     if index > 0
         rh_delete!(h, index)
diff --git a/src/sorted_dict.jl b/src/sorted_dict.jl
index 09cb26a..d0eea4e 100644
--- a/src/sorted_dict.jl
+++ b/src/sorted_dict.jl
@@ -84,7 +84,7 @@ SortedDict{K,D}(ps::Pair...) where {K,D} = SortedDict{K,D,ForwardOrdering}(Forwa
     SortedDict(o, k1=>v1, k2=>v2, ...)
 
 Construct a `SortedDict` from the given pairs with the specified
-ordering `o`. The key type and value type are inferred from the 
+ordering `o`. The key type and value type are inferred from the
 given pairs.
 """
 SortedDict(o::Ordering, ps::Pair...) = SortedDict(o, ps)
diff --git a/src/sparse_int_set.jl b/src/sparse_int_set.jl
new file mode 100644
index 0000000..d964fa9
--- /dev/null
+++ b/src/sparse_int_set.jl
@@ -0,0 +1,250 @@
+const INT_PER_PAGE = div(ccall(:jl_getpagesize, Clong, ()), sizeof(Int))
+# we use this to mark pages not in use, it must never be written to.
+const NULL_INT_PAGE = Vector{Int}()
+
+mutable struct SparseIntSet
+    packed ::Vector{Int}
+    reverse::Vector{Vector{Int}}
+    counters::Vector{Int}  # counts the number of real elements in each page of reverse.
+end
+
+SparseIntSet() = SparseIntSet(Int[], Vector{Int}[], Int[])
+
+SparseIntSet(indices) = union!(SparseIntSet(), indices)
+
+eltype(::Type{SparseIntSet}) = Int
+
+empty(::SparseIntSet) = SparseIntSet()
+
+function empty!(s::SparseIntSet)
+    empty!(s.packed)
+    empty!(s.reverse)
+    empty!(s.counters)
+    return s
+end
+
+isempty(s::SparseIntSet) = isempty(s.packed)
+
+copy(s::SparseIntSet) = copy!(SparseIntSet(), s)
+
+function copy!(to::SparseIntSet, from::SparseIntSet)
+    to.packed = copy(from.packed)
+    #we want to keep the null pages === NULL_INT_PAGE
+    resize!(to.reverse, length(from.reverse))
+    for i in eachindex(from.reverse)
+        page = from.reverse[i]
+        if page === NULL_INT_PAGE
+            to.reverse[i] = NULL_INT_PAGE
+        else
+            to.reverse[i] = copy(from.reverse[i])
+        end
+    end
+    to.counters = copy(from.counters)
+    return to
+end
+
+function pageid_offset(s::SparseIntSet, i)
+    pageid = div(i - 1, INT_PER_PAGE) + 1
+    return pageid, (i - 1) & (INT_PER_PAGE - 1) + 1
+end
+
+function in(i, s::SparseIntSet)
+    pageid, offset = pageid_offset(s, i)
+    if pageid > length(s.reverse)
+        return false
+    else
+        page = @inbounds s.reverse[pageid]
+        return page !== NULL_INT_PAGE &&  @inbounds page[offset] != 0
+    end
+end
+
+length(s::SparseIntSet) = length(s.packed)
+
+@inline function push!(s::SparseIntSet, i::Integer)
+    i <= 0 && throw(DomainError("Only positive Ints allowed."))
+
+    pageid, offset = pageid_offset(s, i)
+    pages = s.reverse
+    plen = length(pages)
+
+    if pageid > plen
+        # Create new null pages up to pageid and fresh (zero-filled) one at pageid
+        sizehint!(pages, pageid)
+        sizehint!(s.counters, pageid)
+        for i in 1:pageid - plen - 1
+            push!(pages, NULL_INT_PAGE)
+            push!(s.counters, 0)
+        end
+        push!(pages, zeros(Int, INT_PER_PAGE))
+        push!(s.counters, 0)
+    elseif pages[pageid] === NULL_INT_PAGE
+        #assign a page to previous null page
+        pages[pageid] = zeros(Int, INT_PER_PAGE)
+    end
+    page = pages[pageid]
+    if page[offset] == 0
+        @inbounds page[offset] = length(s) + 1
+        @inbounds s.counters[pageid] += 1
+        push!(s.packed, i)
+        return s
+    end
+    return s
+end
+
+@inline function push!(s::SparseIntSet, is::Integer...)
+    for i in is
+        push!(s, i)
+    end
+    return s
+end
+
+@inline Base.@propagate_inbounds function pop!(s::SparseIntSet)
+    if isempty(s)
+        throw(ArgumentError("Cannot pop an empty set."))
+    end
+    id = pop!(s.packed)
+    pageid, offset = pageid_offset(s, id)
+    @inbounds s.reverse[pageid][offset] = 0
+    @inbounds s.counters[pageid] -= 1
+    cleanup!(s, pageid)
+    return id
+end
+
+@inline Base.@propagate_inbounds function pop!(s::SparseIntSet, id::Integer)
+    id < 0 && throw(ArgumentError("Int to pop needs to be positive."))
+
+    @boundscheck if !in(id, s)
+        throw(BoundsError(s, id))
+    end
+    @inbounds begin
+        packed_endid = s.packed[end]
+        from_page, from_offset = pageid_offset(s, id)
+        to_page, to_offset = pageid_offset(s, packed_endid)
+
+        packed_id = s.reverse[from_page][from_offset]
+        s.packed[packed_id] = packed_endid
+        s.reverse[to_page][to_offset] = s.reverse[from_page][from_offset]
+        s.reverse[from_page][from_offset] = 0
+        s.counters[from_page] -= 1
+        pop!(s.packed)
+    end
+    cleanup!(s, from_page)
+    return id
+end
+
+@inline function cleanup!(s::SparseIntSet, pageid::Int)
+    if s.counters[pageid] == 0
+        s.reverse[pageid] = NULL_INT_PAGE
+    end
+end
+
+@inline function pop!(s::SparseIntSet, id::Integer, default)
+    id < 0 && throw(ArgumentError("Int to pop needs to be positive."))
+    return in(id, s) ? (@inbounds pop!(s, id)) : default
+end
+popfirst!(s::SparseIntSet) = pop!(s, first(s))
+
+@inline iterate(set::SparseIntSet, args...) = iterate(set.packed, args...)
+
+last(s::SparseIntSet) = isempty(s) ? throw(ArgumentError("Empty set has no last element.")) : last(s.packed)
+
+union(s::SparseIntSet, ns) = union!(copy(s), ns)
+function union!(s::SparseIntSet, ns)
+    for n in ns
+        push!(s, n)
+    end
+    return s
+end
+
+intersect(s1::SparseIntSet) = copy(s1)
+intersect(s1::SparseIntSet, ss...) = intersect(s1, intersect(ss...))
+function intersect(s1::SparseIntSet, ns)
+    s = SparseIntSet()
+    for n in ns
+        n in s1 && push!(s, n)
+    end
+    return s
+end
+
+intersect!(s1::SparseIntSet, ss...) = intersect!(s1, intersect(ss...))
+
+#Is there a more performant way to do this?
+intersect!(s1::SparseIntSet, ns) = copy!(s1, intersect(s1, ns))
+
+setdiff(s::SparseIntSet, ns) = setdiff!(copy(s), ns)
+function setdiff!(s::SparseIntSet, ns)
+    for n in ns
+        pop!(s, n, nothing)
+    end
+    return s
+end
+
+function ==(s1::SparseIntSet, s2::SparseIntSet)
+    length(s1) != length(s2) && return false
+    return all(in(s1), s2)
+end
+
+issubset(a::SparseIntSet, b::SparseIntSet) = isequal(a, intersect(a, b))
+
+<(a::SparseIntSet, b::SparseIntSet) = ( a<=b ) && !isequal(a, b)
+<=(a::SparseIntSet, b::SparseIntSet) = issubset(a, b)
+
+function findfirst_packed_id(i, s::SparseIntSet)
+    pageid, offset = pageid_offset(s, i)
+    if pageid > length(s.counters) || s.counters[pageid] == 0
+        return 0
+    end
+    @inbounds id = s.reverse[pageid][offset]
+    return id
+end
+
+collect(s::SparseIntSet) = copy(s.packed)
+
+struct ZippedSparseIntSetIterator{VT,IT}
+    valid_sets::VT
+    shortest_set::SparseIntSet
+    excluded_sets::IT
+    function ZippedSparseIntSetIterator(valid_sets::SparseIntSet...; exclude::NTuple{N, SparseIntSet}=()) where{N}
+        shortest = valid_sets[findmin(map(length, valid_sets))[2]]
+        new{typeof(valid_sets), NTuple{N, SparseIntSet}}(valid_sets, shortest, exclude)
+    end
+end
+
+Base.zip(s::SparseIntSet...;kwargs...) = ZippedSparseIntSetIterator(s...;kwargs...)
+
+length(it::ZippedSparseIntSetIterator) = length(it.shortest_set)
+
+# we know it is not in_excluded, as there are no excluded
+@inline in_excluded(id, it::ZippedSparseIntSetIterator{VT,Tuple{}}) where {VT} = false
+
+@inline function in_excluded(id, it)
+    for e in it.excluded_sets
+        if id in e
+            return true
+        end
+    end
+    return false
+end
+
+@inline function in_valid(id, it)
+    for e in it.valid_sets
+        if !in(id, e)
+            return false
+        end
+    end
+    return true
+end
+
+@inline function iterate(it::ZippedSparseIntSetIterator, state=1)
+    iterator_length = length(it)
+    if state > iterator_length
+        return nothing
+    end
+    for i in state:iterator_length
+        @inbounds id = it.shortest_set.packed[i]
+        if in_valid(id, it) && !in_excluded(id, it)
+            return map(x->findfirst_packed_id(id, x), it.valid_sets), i + 1
+        end
+    end
+    return nothing
+end
diff --git a/src/stack.jl b/src/stack.jl
index 0be6e02..cd8d1ef 100644
--- a/src/stack.jl
+++ b/src/stack.jl
@@ -25,3 +25,5 @@ empty!(s::Stack) = (empty!(s.store); s)
 iterate(st::Stack, s...) = iterate(reverse_iter(st.store), s...)
 
 reverse_iter(s::Stack{T}) where {T} = DequeIterator{T}(s.store)
+
+==(x::Stack, y::Stack) = x.store == y.store


Test patch:
diff --git a/test/runtests.jl b/test/runtests.jl
index 23d4b0c..5376366 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -8,6 +8,7 @@ import DataStructures: IntSet
 @test [] == detect_ambiguities(Base, Core, DataStructures)
 
 tests = ["int_set",
+         "sparse_int_set",
          "deque",
          "circ_deque",
          "sorted_containers",
@@ -26,9 +27,9 @@ tests = ["int_set",
          "multi_dict",
          "circular_buffer",
          "sorting",
-         "priority_queue", 
-         "fenwick", 
-         "robin_dict"
+         "priority_queue",
+         "fenwick",
+         "robin_dict",
         ]
 
 if length(ARGS) > 0
diff --git a/test/test_accumulator.jl b/test/test_accumulator.jl
index 2a83c64..119efac 100644
--- a/test/test_accumulator.jl
+++ b/test/test_accumulator.jl
@@ -3,7 +3,7 @@
 @testset "Accumulators" begin
 
     ct = counter(String)
-    
+
     @testset "Core Functionality" begin
         @assert isa(ct, Accumulator{String,Int})
 
@@ -174,12 +174,12 @@
 
         @test_throws BoundsError nsmallest(counter("a"),2)
     end
-    
+
     @testset "reset!" begin
         ct = counter("abbbcddddda") # ['d'=>5, 'b'=>3, 'a'=>2, 'c'=>1]
         @test reset!(ct, 'b') == 3
         @test ct == counter("acddddda")
-        
+
         @test reset!(ct, 'x') == 0
     end
 
@@ -187,60 +187,57 @@
         orig = counter("aabbbcccc")
         dup = copy(orig)
         @test orig == dup
-        
+
         # Modifying copy should not modify original
         inc!(orig, 'a')
         @test orig != dup
     end
-    
+
     @testset "Multiset" begin
         @testset "issubset" begin
             @test issubset(counter([1,2,3]), counter([1,2,3]))
             @test !issubset(counter([1,2,3,4]), counter([1,2,3]))
             @test issubset(counter([1,2]), counter([1,2,3]))
-            
+
             @test issubset(counter([1,2,3]), counter([1,2,3,3]))
             @test !issubset(counter([1,2,3,3]), counter([1,2,3]))
         end
-        
+
         @testset "setdiff" begin
             @test setdiff(counter([1,2,3]), counter([2, 4])) == counter([3, 1])
             @test setdiff(counter([1,2,3]), counter([2,2,4])) == counter([3, 1])
             @test setdiff(counter([1,2,2,2,3]), counter([2,2,4])) == counter([1,2,3])
-            
+
             nonmultiset = counter(Dict([('a',-10), ('b',20)]))
             @test_throws DataStructures.MultiplicityException setdiff(counter("aabbcc"), nonmultiset)
         end
-        
+
         @testset "union" begin
             @test ∪(counter([1,2,3]), counter([1,2,3])) == counter([1,2,3])
             @test ∪(counter([1,2,3]), counter([1,2,2,3])) == counter([1,2,2,3])
             @test ∪(counter([1,3]), counter([2,2])) == counter([1,2,2,3])
             @test ∪(counter([1,2,3]), counter(Int[])) == counter([1,2,3])
-            
+
             nonmultiset = counter(Dict([('a',-10), ('b',20)]))
             @test_throws DataStructures.MultiplicityException (counter("aabbcc") ∪ nonmultiset)
             @test_throws DataStructures.MultiplicityException (nonmultiset ∪ counter("aabbcc"))
         end
- 
+
         @testset "intersect" begin
             @test ∩(counter([1,2,3]), counter([1,2,3])) == counter([1,2,3])
             @test ∩(counter([1,2,3]), counter([1,2,2,3])) == counter([1,2,3])
             @test ∩(counter([1,3]), counter([2,2])) == counter(Int[])
             @test ∩(counter([1,2,3]), counter(Int[])) == counter(Int[])
-            
-            
+
+
             nonmultiset = counter(Dict([('a',-10), ('b',20)]))
             @test_throws DataStructures.MultiplicityException (counter("aabbcc") ∩ nonmultiset)
             @test_throws DataStructures.MultiplicityException (nonmultiset ∩ counter("aabbcc"))
         end
 
 
-    
+
 
     end
 
 end # @testset Accumulators
-
-
-
diff --git a/test/test_circ_deque.jl b/test/test_circ_deque.jl
index 7dfc08a..90f96ee 100644
--- a/test/test_circ_deque.jl
+++ b/test/test_circ_deque.jl
@@ -65,7 +65,7 @@
             @test popfirst!(D) === i
         end
     end
-    
+
     @testset "pushfirst! works on an empty deque" begin
         # Test that pushfirst! works on an empty deque, and that front/back give the right answer
         D = CircularDeque{Int}(5)
diff --git a/test/test_circular_buffer.jl b/test/test_circular_buffer.jl
index f31b2cf..3064c0d 100644
--- a/test/test_circular_buffer.jl
+++ b/test/test_circular_buffer.jl
@@ -6,19 +6,21 @@
             @test length(cb) == 0
             @test capacity(cb) == 5
             @test_throws BoundsError first(cb)
+            @test_throws BoundsError last(cb)
             @test isempty(cb) == true
             @test isfull(cb) == false
             @test eltype(cb) == Int
             @test eltype(typeof(cb)) == Int
         end
-        
+
         @testset "With 1 element" begin
             push!(cb, 1)
             @test length(cb) == 1
             @test capacity(cb) == 5
             @test isfull(cb) == false
+            @test first(cb) == last(cb)
         end
-        
+
         @testset "Appending many elements" begin
             append!(cb, 2:8)
             @test length(cb) == capacity(cb)
@@ -27,7 +29,7 @@
             @test isfull(cb) == true
             @test convert(Array, cb) == Int[4,5,6,7,8]
         end
-            
+
         @testset "getindex" begin
             @test cb[1] == 4
             @test cb[2] == 5
@@ -38,20 +40,22 @@
             @test_throws BoundsError cb[3:6]
             @test cb[3:4] == Int[6,7]
             @test cb[[1,5]] == Int[4,8]
+            @test first(cb) == 4
+            @test last(cb) == 8
         end
-        
+
         @testset "setindex" begin
             cb[3] = 999
             @test convert(Array, cb) == Int[4,5,999,7,8]
         end
     end
-    
+
     @testset "other constructor" begin
         cb = CircularBuffer(10)
         @test length(cb) == 0
         @test typeof(cb) <: CircularBuffer{Any}
     end
-    
+
     @testset "pushfirst" begin
         cb = CircularBuffer{Int}(5)  # New, empty one for full test coverage
         for i in -5:5
@@ -63,7 +67,7 @@
             @test arr[idx] == n
         end
     end
-    
+
     @testset "Issue 429" begin
         cb = CircularBuffer{Int}(5)
         map(x -> pushfirst!(cb, x), 1:8)
@@ -81,7 +85,7 @@
         pushfirst!(cb, 2)
         @test cb == [2, 1]
     end
-    
+
     @testset "empty!" begin
         cb = CircularBuffer{Int}(5)
         push!(cb, 13)
@@ -101,7 +105,7 @@
         @test isempty(cb)
         @test_throws ArgumentError pop!(cb)
     end
-    
+
     @testset "popfirst!" begin
         cb = CircularBuffer{Int}(5)
         for i in 0:5    # one extra to force wraparound
@@ -114,7 +118,7 @@
         @test isempty(cb)
         @test_throws ArgumentError popfirst!(cb)
     end
-    
+
     @testset "fill!" begin
         @testset "fill an empty buffer" begin
             cb = CircularBuffer{Int}(3)
diff --git a/test/test_default_dict.jl b/test/test_default_dict.jl
index cec9282..3409f06 100644
--- a/test/test_default_dict.jl
+++ b/test/test_default_dict.jl
@@ -198,7 +198,7 @@ import DataStructures: DefaultDictBase
         @testset "issue #216" begin
             @test DataStructures.isordered(DefaultOrderedDict{Int, String})
         end
-    
+
     end
 
 end
diff --git a/test/test_deque.jl b/test/test_deque.jl
index 4597eb1..b651091 100644
--- a/test/test_deque.jl
+++ b/test/test_deque.jl
@@ -39,10 +39,10 @@
 
     @testset "Core Functionality" begin
         n = 10
-        
+
         @testset "push back / pop back" begin
             q = Deque{Int}(3)
-            
+
             @testset "push back" begin
                 for i = 1 : n
                     push!(q, i)
diff --git a/test/test_disjoint_set.jl b/test/test_disjoint_set.jl
index 3eec1ab..468df55 100644
--- a/test/test_disjoint_set.jl
+++ b/test/test_disjoint_set.jl
@@ -114,7 +114,7 @@
             @test find_root(a,"a") == union!(a,"b","c")
             union!(a,"c","d")
             # Now they should be in same set, and a is transitively connected to d
-            @test in_same_set(a,"a", "d") 
+            @test in_same_set(a,"a", "d")
             # Root element should thus be same for all:
             @test all(find_root(a,first(elems)) .== map(x->find_root(a,x),elems))
 
diff --git a/test/test_fenwick.jl b/test/test_fenwick.jl
index 7a89b93..6e563b2 100644
--- a/test/test_fenwick.jl
+++ b/test/test_fenwick.jl
@@ -5,13 +5,13 @@
         @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)
         @test f3[1] == 1.2
         @test length(f3) == length(arr)
     end
-    
+
     @testset "Point update and Point queries" begin
         f1 = FenwickTree{Int}(10)
         inc!(f1, 10, 5)
@@ -23,17 +23,17 @@
         @test prefixsum(f1, 10) == 12
         @test prefixsum(f1, 5) == 7
         @test prefixsum(f1, 4) == 0
-        
+
         dec!(f1, 7, 2)
         @test prefixsum(f1, 8) == 5
         @test prefixsum(f1, 6) == 7
-        
+
         incdec!(f1, 2, 6, 3)
         @test prefixsum(f1, 3) == 3
         @test prefixsum(f1, 7) == 5
-        
+
         @test_throws ArgumentError inc!(f1, 11)
         @test_throws ArgumentError inc!(f1, 0)
     end
-    
+
 end
\ No newline at end of file
diff --git a/test/test_int_set.jl b/test/test_int_set.jl
index 60805b2..de2828d 100644
--- a/test/test_int_set.jl
+++ b/test/test_int_set.jl
@@ -78,7 +78,7 @@ import DataStructures: IntSet
     @testset "complement! / pop!" begin
         c1 = complement!(IntSet())
         s1 = IntSet([1,2,3])
-        
+
         pop!(c1, 1)
         pop!(c1, 2)
         pop!(c1, 3)
diff --git a/test/test_minmax_heap.jl b/test/test_minmax_heap.jl
index 031b9f1..e8a7716 100644
--- a/test/test_minmax_heap.jl
+++ b/test/test_minmax_heap.jl
@@ -3,7 +3,7 @@ using DataStructures: _make_binary_minmax_heap, is_minmax_heap, children_and_gra
 using Base.Order: Forward, Reverse
 
 @testset "Binary MinMax Heaps" begin
-    
+
     @testset "is_minmax_heap tests" begin
         mmheap = [0, 10, 9, 2, 3, 4, 5]
         @test is_minmax_heap(mmheap)
@@ -20,10 +20,10 @@ using Base.Order: Forward, Reverse
         @test eltype(typeof(h)) == Int
         @test sizehint!(h, 100) === h
     end
-    
+
     @testset "make heap tests" begin
         vs = [10, 4, 6, 1, 16, 2, 20, 17, 13, 5]
-        
+
         @testset "make from array tests" begin
             h = BinaryMinMaxHeap(vs)
             @test length(h) == 10
@@ -32,7 +32,7 @@ using Base.Order: Forward, Reverse
             @test maximum(h) == 20
             @test is_minmax_heap(h.valtree)
         end
-        
+
         @testset "make from random arrays tests" begin
             for i = 1:20
                 A = rand(50)
@@ -40,13 +40,13 @@ using Base.Order: Forward, Reverse
                 @test is_minmax_heap(vtree)
             end
         end
-        
+
         @testset "push! tests" begin
             h = BinaryMinMaxHeap{Int}()
-            
+
             @test length(h) == 0
             @test isempty(h)
-            
+
             push!(h, 1)
             @test top(h) == 1
             push!(h, 2)
@@ -65,7 +65,7 @@ using Base.Order: Forward, Reverse
             end
         end
     end
-    
+
     @testset "pop! tests" begin
         @testset "popmin! tests" begin
             h = BinaryMinMaxHeap([1])
@@ -103,7 +103,7 @@ using Base.Order: Forward, Reverse
             @test maximum(h) == 2
         end
     end
-    
+
     @testset "empty!" begin
         h = BinaryMinMaxHeap([1, 4, 3, 10, 2])
         ret = empty!(h)
@@ -120,7 +120,7 @@ using Base.Order: Forward, Reverse
             @test popall!(h) == sorted_A
             @test isempty(h)
             @test length(h) == 0
-            
+
             h = BinaryMinMaxHeap(A)
             @test popmin!(h, 10) == sorted_A[1:10]
             @test !isempty(h)
@@ -133,24 +133,24 @@ using Base.Order: Forward, Reverse
             @test popall!(h, Reverse) == sorted_A
             @test length(h) == 0
             @test isempty(h)
-            
+
             h = BinaryMinMaxHeap(A)
             @test popmax!(h, 10) == sorted_A[1:10]
             @test length(h) == 40
             @test !isempty(h)
         end
     end
-    
+
     @testset "type conversion" begin
         h = BinaryMinMaxHeap{Float64}()
         push!(h, 3.)
         push!(h, 5)
         push!(h, Rational(4, 8))
         push!(h, Complex(10.1, 0.0))
-        
+
         @test h.valtree == [0.5, 10.1, 3.0, 5.0]
     end
-    
+
     @testset "children_and_grandchildren tests" begin
         @test children_and_grandchildren(1, 1) == Int[]
         @test children_and_grandchildren(2, 1) == [2]
@@ -158,17 +158,17 @@ using Base.Order: Forward, Reverse
         @test children_and_grandchildren(7, 1) == [2, 4, 5, 3, 6, 7]
         @test children_and_grandchildren(10, 2) == [4, 8, 9, 5, 10]
     end
-    
+
     @testset "throw errors tests" begin
         h = BinaryMinMaxHeap{Int}()
         @test_throws ArgumentError pop!(h)
         @test_throws ArgumentError popmin!(h)
-        
+
         @test_throws ArgumentError popmax!(h)
-        
+
         @test_throws ArgumentError top(h)
         @test_throws ArgumentError minimum(h)
         @test_throws ArgumentError maximum(h)
-        
+
     end
 end
diff --git a/test/test_multi_dict.jl b/test/test_multi_dict.jl
index 6024536..91b9d93 100644
--- a/test/test_multi_dict.jl
+++ b/test/test_multi_dict.jl
@@ -12,9 +12,9 @@
         PVS = 1 => [1.0]
         PV = 1 => 1.0
         @test eltype(MultiDict{Char,Int}()) === Pair{Char,Vector{Int}}
-        @test isa(MultiDict(PVS), MultiDict{Int,Float64})
-        @test isa(MultiDict(PVS, PVS), MultiDict{Int,Float64})
-        @test isa(MultiDict([PVS, PVS]), MultiDict{Int,Float64})
+        @test isa(MultiDict(PVS), MultiDict{Int,Array{Float64,1}})
+        @test isa(MultiDict(PVS, PVS), MultiDict{Int,Array{Float64,1}})
+        @test isa(MultiDict([PVS, PVS]), MultiDict{Int,Array{Float64,1}})
         @test isa(MultiDict(PV), MultiDict{Int,Float64})
         @test isa(MultiDict(PV, PV), MultiDict{Int,Float64})
         @test isa(MultiDict([PV, PV]), MultiDict{Int,Float64})
@@ -30,7 +30,9 @@
 
         @test insert!(d, 'a', 1) == MultiDict{Char,Int}([('a', [1])])
         @test getindex(d, 'a') == [1]
-        @test insert!(d, 'a', [2,3]) == MultiDict{Char,Int}([('a', [1,2,3])])
+        @test_throws MethodError insert!(d, 'a', [2,3]) == MultiDict{Char,Int}([('a', [1,2,3])])
+        @test insert!(d, 'a', 2) == MultiDict{Char,Int}([('a', [1,2])])
+        @test insert!(d, 'a', 3) == MultiDict{Char,Int}([('a', [1,2, 3])])
         @test getindex(d, 'a') == [1,2,3]
 
         @test_throws KeyError d['c'] == 1
@@ -60,8 +62,7 @@
         @testset "in" begin
             @test in(('c', 1), d)
             @test in(('a', 1), d)
-            @test in(('c', [1]), d)
-            @test in(('a', [1,2,3]), d)
+            @test in(('a', 2), d)
         end
 
         @testset "isempty / empty!" begin
@@ -78,7 +79,7 @@
             @test pop!(d, 'a') == 1
             @test !haskey(d, 'a')
             @test pop!(d, 'b', 0) == 0
-        end 
+        end
     end
 
     @testset "delete!" begin
@@ -95,14 +96,10 @@
 
     @testset "push!" begin
         d = MultiDict{Char,Int}()
-        @test push!(d, ('a',[1])) == MultiDict{Char,Int}([('a', [1])])
-        @test push!(d, ('a',[1])) == MultiDict{Char,Int}([('a', [1,1])])
-        empty!(d)
         @test push!(d, ('a',1)) == MultiDict{Char,Int}([('a', [1])])
         @test push!(d, ('a',1)) == MultiDict{Char,Int}([('a', [1,1])])
-
         empty!(d)
-        @test push!(d,'a'=>[1]) == MultiDict{Char,Int}([('a', [1])])
+        @test push!(d,'a'=>1) == MultiDict{Char,Int}([('a', [1])])
         @test push!(d, 'a'=>1) == MultiDict{Char,Int}([('a', [1,1])])
 
         @testset "get!" begin
@@ -114,14 +111,16 @@
     end
 
     @testset "special functions: count, enumerateall" begin
-        d = MultiDict{Char,Int}()
+        #not appending arrays to one array, using array of arrays
+        d = MultiDict{Char,Array{Int,1}}()
         @test count(d) == 0
         for i in 1:15
-            insert!(d, rand('a':'f'), rand()>0.5 ? rand(1:10) : rand(1:10, rand(1:3)))
+            insert!(d, rand('a':'f'), rand()>0.5 ? [rand(1:10)] : rand(1:10, rand(1:3)))
         end
         @test 15 <= count(d) <=45
         @test size(d) == (length(d), count(d))
 
+        #= --- broken phlavenk ----
         allvals = [kv for kv in enumerateall(d)]
         @test length(allvals) == count(d)
         @test all(kv->in(kv,d), enumerateall(d))
@@ -129,6 +128,7 @@
         # @test length(d) == 15
         # @test length(values(d)) == 15
         # @test length(keys(d)) <= 6
+        --- broken phlavenk ---- =#
     end
 
 end # @testset MultiDict
diff --git a/test/test_mutable_binheap.jl b/test/test_mutable_binheap.jl
index 14a403e..395e5ad 100644
--- a/test/test_mutable_binheap.jl
+++ b/test/test_mutable_binheap.jl
@@ -113,7 +113,7 @@ end
 
         # test pop!
         @test isequal(extract_all!(hmin), [1, 2, 3, 4, 7, 8, 9, 10, 14, 16])
-        @test isempty(hmin)    
+        @test isempty(hmin)
     end
 
     @testset "hmax / push! / pop!" begin
@@ -168,7 +168,7 @@ end
         @test pop!(h) == 2
         @test isequal(heap_values(h), [7, 10])
         @test isequal(list_values(h), [10, 7])
-        
+
     end
 
     @testset "test delete!" begin
@@ -254,7 +254,7 @@ end
         update!(h, 2, 20)
         @test isequal(heap_values(h), [0.5, 10.1, 3.0, 20.0])
     end
-    
+
     # test deprecated constructors
     @testset "deprecated constructors" begin
         @test_deprecated mutable_binary_minheap(Int)
@@ -262,6 +262,6 @@ end
         @test_deprecated mutable_binary_maxheap(Int)
         @test_deprecated mutable_binary_maxheap([1., 2., 3.])
     end
-    
+
 
 end # @testset MutableBinheap
diff --git a/test/test_queue.jl b/test/test_queue.jl
index d689a44..146155e 100644
--- a/test/test_queue.jl
+++ b/test/test_queue.jl
@@ -43,6 +43,34 @@
         end
     end
 
+    @testset "==" begin
+        t = Queue{Int}()
+        s = Queue{Int}()
+
+        @test s == t
+        enqueue!(s, 10)
+        @test s != t
+        enqueue!(t, 10)
+        @test s == t
+        enqueue!(t, 20)
+        @test s != t
+
+        @testset "different types" begin
+            r = Queue{Float32}()
+            enqueue!(r, 10)
+            @test s == r
+        end
+    end
+
+    @testset "emptyness" begin
+        s = Queue{Int}()
+        enqueue!(s, 1)
+        enqueue!(s, 3)
+        @test !isempty(s)
+        empty!(s)
+        @test isempty(s)
+    end
+
     @testset "iter should return a FIFO collection" begin
         q = Queue{Int}(10)
         n = 100
diff --git a/test/test_robin_dict.jl b/test/test_robin_dict.jl
index 82cf7a3..06a7b18 100644
--- a/test/test_robin_dict.jl
+++ b/test/test_robin_dict.jl
@@ -82,7 +82,7 @@ end
 	        @test k in [3, 8, 6]
 	    end
 	end
-    
+
     let y = RobinDict{Any, Int}(3=>3, 5=>5, "8"=>8, 6=>6)
         pop!(y, "8")
         for k in keys(y)
@@ -112,7 +112,7 @@ end
 @testset "Filter function" begin
     _d = RobinDict("a"=>0)
     @test isa([k for k in filter(x->length(x)==1, collect(keys(_d)))], Vector{String})
-    
+
     h = RobinDict{Int, Int}()
     for i in 1:100
         h[i] = i
@@ -238,7 +238,7 @@ end
     @test isequal(RobinDict(missing=>1), RobinDict(missing=>1))
 end
 
-@testset "get!" begin 
+@testset "get!" begin
     f(x) = x^2
     d = RobinDict(8=>19)
     @test get!(d, 8, 5) == 19
@@ -346,14 +346,14 @@ end
 @testset "get_idxfloor" begin
     h = RobinDict()
     @test get_idxfloor(h) == 0
-    
+
     h["a"] = 1
     h[2] = "b"
     @test h.idxfloor == get_idxfloor(h)
     pop!(h)
     @test h.idxfloor == get_idxfloor(h)
     pop!(h)
-    @test h.idxfloor == get_idxfloor(h) == 0 
+    @test h.idxfloor == get_idxfloor(h) == 0
 end
 
 @testset "invariants" begin
@@ -361,7 +361,7 @@ end
     for i in 1:300
         h1[i] = i
     end
-    
+
     for i in 1:length(h1.keys)
         if isslotfilled(h1, i)
             @test hash_key(h1.keys[i]) == h1.hashes[i]
@@ -372,7 +372,7 @@ end
     for i in 1:300
         h2[rand()] = rand()
     end
-    
+
     for i in 1:length(h2.keys)
         if isslotfilled(h2, i)
             @test hash_key(h2.keys[i]) == h2.hashes[i]
@@ -383,7 +383,7 @@ end
     for i in 1:300
         h3[randstring()] = i
     end
-    
+
     for i in 1:length(h3.keys)
         if isslotfilled(h3, i)
             @test hash_key(h3.keys[i]) == h3.hashes[i]
@@ -424,4 +424,4 @@ end
         h[i] = i+1
     end
     check_invariants(h)
-end 
\ No newline at end of file
+end
\ No newline at end of file
diff --git a/test/test_sorted_containers.jl b/test/test_sorted_containers.jl
index 6981218..cc815e6 100644
--- a/test/test_sorted_containers.jl
+++ b/test/test_sorted_containers.jl
@@ -1637,14 +1637,14 @@ end
 @testset "SortedContainers" begin
     @test testSortedDictBasic()
     @test testSortedDictMethods()
-    @test testSortedDictLoops()    
+    @test testSortedDictLoops()
     @test testSortedDictOrderings()
     @test testSortedMultiDict()
     @test testSortedSet()
     @test testSortedDictConstructors()
     @test testSortedMultiDictConstructors()
 
-    
+
     # test all the errors of sorted containers
     m = SortedDict(Dict("a" => 6, "bb" => 9))
     @test_throws KeyError println(m["b"])
@@ -1690,6 +1690,6 @@ end
     @test_throws ArgumentError ((2,5) in m1)
 
 
-    
-    
+
+
 end
diff --git a/test/test_sparse_int_set.jl b/test/test_sparse_int_set.jl
new file mode 100644
index 0000000..9947c2e
--- /dev/null
+++ b/test/test_sparse_int_set.jl
@@ -0,0 +1,189 @@
+using DataStructures, Test
+import DataStructures: SparseIntSet
+
+@testset "SparseIntSet" begin
+    @testset "Construction, collect" begin
+        data_in = (1,5,100)
+        s = SparseIntSet(data_in)
+        data_out = collect(s)
+        @test all(map(d->in(d,data_out), data_in))
+        @test length(data_out) == length(data_in)
+    end
+
+    @testset "eltype, empty" begin
+        @test eltype(SparseIntSet()) == Int
+        @test eltype(typeof(SparseIntSet())) == Int
+        @test isequal(empty(SparseIntSet([1,2,3])), SparseIntSet())
+    end
+
+    @testset "Core Functionality" begin
+        s = SparseIntSet([1,2,10,20,200,300,1000,10000,10002])
+        @test last(s) == 10002
+        @test first(s) == 1
+        @test length(s) == 9
+        @test pop!(s) == 10002
+        @test length(s) == 8
+        @test popfirst!(s) == 1
+        @test length(s) == 7
+        @test !in(1,s)
+        @test !in(10002,s)
+        @test in(10000,s)
+        @test_throws ArgumentError first(SparseIntSet())
+        @test_throws ArgumentError last(SparseIntSet())
+        t = copy(s)
+        s = SparseIntSet()
+        push!(s, 1, 2, 100)
+        @test 1 in s
+        @test !(3 in s)
+        @test 2 in s
+        @test 100 in s
+        @test !(101 in s)
+        @test !(1000 in s)
+        @test first(s) == 1
+        @test last(s) == 100
+        @test s == SparseIntSet([1, 2, 100])
+        push!(s, 1000)
+        @test [i for i in s] == [1, 2, 100, 1000]
+        @test pop!(s) == 1000
+        @test s == SparseIntSet([1, 2, 100])
+        push!(s, 5000)
+        push!(s, 2000)
+        pop!(s, 5000)
+        @test s.reverse[end] === DataStructures.NULL_INT_PAGE
+        b = 1:1000
+        s = SparseIntSet(b)
+        @test collect(s) == collect(b)
+        @test length(s) == length(b)
+        @test pop!(s, 100) == 100
+        @test_throws BoundsError pop!(s, 100)
+        @test pop!(s, 100, 1) == 1
+        @test pop!(s, 99, 1) == 99
+        @test !in(500000, s)
+        @test !in(99, s)
+    end
+
+    @testset "setdiff / symdiff" begin
+        @test setdiff(SparseIntSet([1, 2, 3, 4]), SparseIntSet([2, 4, 5, 6])) == SparseIntSet([1, 3])
+    end
+
+    @testset "setdiff!" begin
+        s2 = SparseIntSet([1, 2, 3, 4])
+        setdiff!(s2, SparseIntSet([2, 4, 5, 6]))
+
+        @test s2 == SparseIntSet([1, 3])
+    end
+
+    @testset "issue #7851" begin
+        @test_throws DomainError SparseIntSet(-1)
+        @test !(-1 in SparseIntSet(1:10))
+    end
+    @testset "Copy, copy!, empty" begin
+        s1 = SparseIntSet([1,2,3])
+        s2 = empty(s1)
+        push!(s2, 10000)
+        @test !in(10000, s1)
+        copy!(s2, s1)
+        @test !in(10000, s2)
+        push!(s2, 10000)
+        @test !in(10000, s1)
+        s3 = copy(s2)
+        push!(s3, 1000)
+        @test !in(1000, s2)
+        pop!(s3, 1000)
+        pop!(s2, 10000)
+        @test in(10000, s3)
+        pop!(s3, 10000)
+        @test s3 == s2 == s1
+        @test collect(s3) == collect(s2) == [1,2,3]
+
+
+    end
+
+    @testset "Push, union" begin
+        # Push, union
+        s1 = SparseIntSet()
+        @test_throws DomainError push!(s1, -1)
+        push!(s1, 1, 10, 100, 1000)
+        @test collect(s1) == [1, 10, 100, 1000]
+        push!(s1, 606)
+        @test collect(s1) == [1, 10, 100, 1000, 606]
+        s2 = SparseIntSet()
+        @test s2 === union!(s2, s1)
+        s3 = SparseIntSet([1, 10, 100])
+        union!(s3, [1, 606, 1000])
+        s4 = union(SparseIntSet([1, 100, 1000]), SparseIntSet([10, 100, 606]))
+        @test s1 == s2 == s3 == s4
+    end
+
+    @testset "pop!, delete!" begin
+        s = SparseIntSet(1:2:10)
+        @test pop!(s, 1) == 1
+        @test !(1 in s)
+        @test_throws BoundsError pop!(s, 1)
+        @test_throws ArgumentError pop!(s, -1)
+        @test_throws ArgumentError pop!(s, -1, 1)
+        @test pop!(s, 1, 0) == 0
+        is = copy(s.packed)
+        for i in is; pop!(s, i); end
+        @test isempty(s)
+        push!(s, 1:2:10...)
+        @test pop!(s) == 9
+        @test pop!(s) == 7
+        @test popfirst!(s) == 1
+        @test popfirst!(s) == 5
+        @test collect(s) == [3]
+        empty!(s)
+        @test isempty(s)
+    end
+
+    @testset "Intersect" begin
+        @test isempty(intersect(SparseIntSet()))
+        @test isempty(intersect(SparseIntSet(1:10), SparseIntSet()))
+        @test isempty(intersect(SparseIntSet(), SparseIntSet(1:10)))
+
+        @test intersect(SparseIntSet([1,2,3])) == SparseIntSet([1,2,3])
+
+        @test intersect(SparseIntSet(1:7), SparseIntSet(3:10)) ==
+              intersect(SparseIntSet(3:10), SparseIntSet(1:7)) == SparseIntSet(3:7)
+
+        @test intersect!(SparseIntSet(1:10), SparseIntSet(1:4), 1:5, [1,2,10]) == SparseIntSet(1:2)
+    end
+
+    @testset "Setdiff" begin
+        s1 = SparseIntSet(1:100)
+        setdiff!(s1, SparseIntSet(1:2:100))
+        s2 = setdiff(SparseIntSet(1:100), SparseIntSet(1:2:100))
+        @test s1 == s2 == SparseIntSet(2:2:100)
+
+        s1 = SparseIntSet(1:10)
+        s2 = SparseIntSet([1:2; 6:100])
+        @test setdiff(s1, s2) == setdiff(s1, [1:2; 6:100]) == SparseIntSet(3:5)
+    end
+
+    @testset "Subsets, equality" begin
+        @test SparseIntSet(2:2:10) < SparseIntSet(1:10)
+        @test !(SparseIntSet(2:2:10) < SparseIntSet(2:2:10))
+        @test SparseIntSet(2:2:10) <= SparseIntSet(2:10)
+        @test SparseIntSet(2:2:10) <= SparseIntSet(2:2:10)
+    end
+    @testset "zip" begin
+    	a = SparseIntSet([1,2,3,5, 6, 9, 12, 24])
+    	b = SparseIntSet([6, 12, 24, 1000, 2000, 3000])
+    	c = SparseIntSet(2:2:100)
+    	d = SparseIntSet(6:3:100)
+    	e = SparseIntSet((6, 12))
+    	s1 = 0
+    	it = zip(a, b, c, d, e)
+    	for (ia, ib, ic, id, ie) in it
+	    	s1 += a.packed[ia] + b.packed[ib] + c.packed[ic] + d.packed[id] + e.packed[ie]
+	    end
+	    @test s1 == 5*(6+12)
+    	s1 = 0
+    	it = zip(a, b, c, d, exclude=(e,))
+    	for (ia, ib, ic, id) in it
+	    	s1 += a.packed[ia] + b.packed[ib] + c.packed[ic] + d.packed[id]
+	    end
+	    @test s1 == 4*24
+	end
+
+end
diff --git a/test/test_stack.jl b/test/test_stack.jl
index 60460e4..9963c54 100644
--- a/test/test_stack.jl
+++ b/test/test_stack.jl
@@ -40,6 +40,25 @@
         end
     end
 
+    @testset "==" begin
+        s = Stack{Int}()
+        t = Stack{Int}()
+
+        @test s == t
+        push!(s, 10)
+        @test s != t
+        push!(t, 10)
+        @test s == t
+        push!(t, 20)
+        @test s != t
+
+        @testset "different types" begin
+            r = Stack{Float32}()
+            push!(r, 10)
+            @test s == r
+        end
+    end
+
     @testset "empty!" begin
         s = Stack{Int}(1)
         push!(s, 10)