Packages
inplace
0.7.0
0.7.12
0.7.11
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
test/adt/sparse_set_test.exs
defmodule InPlace.SparseSetTest do
use ExUnit.Case
alias InPlace.{SparseSet, Array}
test "new/1, delete/2, undelete/1" do
domain_size = 100
set = SparseSet.new(domain_size)
assert SparseSet.size(set) == domain_size
refute SparseSet.empty?(set)
assert Enum.all?(1..SparseSet.size(set), fn el -> SparseSet.member?(set, el) end)
## Deletion
random_order = Enum.shuffle(1..domain_size)
assert Enum.all?(random_order, fn el ->
size_before = SparseSet.size(set)
SparseSet.delete(set, el)
(size_before == SparseSet.size(set) + 1)
&& assert_inverse(set)
end)
assert SparseSet.size(set) == 0
assert SparseSet.empty?(set)
refute SparseSet.delete(set, Enum.random(1..domain_size))
## Undeletion
Enum.all?(1..domain_size, fn _ ->
size_before = SparseSet.size(set)
SparseSet.undelete(set)
(size_before == SparseSet.size(set) - 1)
&& assert_inverse(set)
end)
assert SparseSet.size(set) == domain_size
refute SparseSet.undelete(set)
end
test "get/2, mapper" do
domain_size = 100
set = SparseSet.new(domain_size, mapper: fn _set, el -> 2 * el end)
random_el = Enum.random(1..domain_size)
assert SparseSet.get(set, random_el) == 2 * random_el
end
test "iteration (reduce)" do
domain_size = 100
set = SparseSet.new(domain_size)
mapset = MapSet.new(1..domain_size)
assert mapset == MapSet.new(SparseSet.to_list(set))
mapset_copy = SparseSet.reduce(set, MapSet.new, fn el, acc -> MapSet.put(acc, el) end)
assert mapset == mapset_copy
## reduce with {:halt, _}
partial_set = SparseSet.reduce(set, MapSet.new(), fn el, acc ->
if el == div(domain_size, 2) do
{:halt, acc}
else
MapSet.put(acc, el)
end
end)
assert MapSet.size(partial_set) == div(domain_size, 2)
end
test "iteration (each)" do
size = 10
arr = Array.new(10, 0)
assert Array.to_list(arr) == List.duplicate(0, size)
set = SparseSet.new(size)
SparseSet.each(set, fn idx -> Array.put(arr, idx, 1) end)
assert Array.to_list(arr) == List.duplicate(1, size)
end
defp assert_inverse(%{dom: dom, idom: idom, dom_size: dom_size} = set) do
SparseSet.size(set) == 0 ||
Enum.all?(1..dom_size, fn idx ->
Array.get(idom,
Array.get(dom, idx)
) == idx
end)
end
end