aboutsummaryrefslogtreecommitdiff
path: root/test/mst_test.exs
diff options
context:
space:
mode:
Diffstat (limited to 'test/mst_test.exs')
-rw-r--r--test/mst_test.exs197
1 files changed, 0 insertions, 197 deletions
diff --git a/test/mst_test.exs b/test/mst_test.exs
deleted file mode 100644
index c1758ad..0000000
--- a/test/mst_test.exs
+++ /dev/null
@@ -1,197 +0,0 @@
-defmodule ShardTest.MST do
- use ExUnit.Case
- alias SData.MerkleSearchTree, as: MST
- doctest Shard.Application
-
- test "merkle search tree 1" do
- y = Enum.reduce(0..1000, %MST{},
- fn i, acc -> MST.insert(acc, i) end)
-
-
- z = Enum.reduce(Enum.shuffle(0..1000), %MST{},
- fn i, acc -> MST.insert(acc, i) end)
-
- for i <- 0..1000 do
- assert MST.get(y, i) == true
- assert MST.get(z, i) == true
- end
- assert MST.get(y, 9999) == nil
- assert MST.get(z, -1001) == nil
- assert MST.get(z, 1.01) == nil
-
- IO.puts "y.root: #{y.root|>Base.encode16}"
- IO.puts "z.root: #{z.root|>Base.encode16}"
- assert y.root == z.root
- end
-
- test "merkle search tree 2" do
- items = for i <- 0..1000 do
- h = SData.term_hash i
- {h, SData.term_hash h}
- end
-
- merge = fn a, b -> if a > b do a else b end end
-
- y = Enum.reduce(items, %MST{merge: merge},
- fn {k, v}, acc -> MST.insert(acc, k, v) end)
-
- z = Enum.reduce(Enum.shuffle(items), %MST{merge: merge},
- fn {k, v}, acc -> MST.insert(acc, k, v) end)
-
- for {k, v} <- items do
- assert MST.get(y, k) == v
- assert MST.get(z, k) == v
- end
-
- IO.puts "y.root: #{y.root|>Base.encode16}"
- IO.puts "z.root: #{z.root|>Base.encode16}"
- assert y.root == z.root
- end
-
- test "merkle search tree 3" do
- merge = fn a, b -> if a > b do a else b end end
-
- y = Enum.reduce(0..1000, %MST{merge: merge},
- fn i, acc -> MST.insert(acc, i, i) end)
- y = Enum.reduce(0..1000, y,
- fn i, acc -> MST.insert(acc, i, i + 2 * rem(i, 2) - 1) end)
-
-
- z = Enum.reduce(Enum.shuffle(0..1000), %MST{merge: merge},
- fn i, acc -> MST.insert(acc, i, i) end)
- z = Enum.reduce(Enum.shuffle(0..1000), z,
- fn i, acc -> MST.insert(acc, i, i + 2 * rem(i, 2) - 1) end)
-
- for i <- 0..1000 do
- val = if rem(i, 2) == 1 do i+1 else i end
- assert MST.get(y, i) == val
- assert MST.get(z, i) == val
- end
- assert MST.get(y, 9999) == nil
- assert MST.get(z, -1001) == nil
- assert MST.get(z, 1.01) == nil
-
- IO.puts "y.root: #{y.root|>Base.encode16}"
- IO.puts "z.root: #{z.root|>Base.encode16}"
- assert y.root == z.root
- end
-
- test "merkle search tree 4" do
- items = for i <- 0..1000 do
- h = SData.term_hash i
- {h, SData.term_hash h}
- end
-
- cmp = fn {a1, b1}, {a2, b2} ->
- cond do
- a1 < a2 -> :before
- a1 > a2 -> :after
- b1 > b2 -> :before
- b1 < b2 -> :after
- true -> :duplicate
- end
- end
-
- y = Enum.reduce(items, %MST{cmp: cmp},
- fn {a, b}, acc -> MST.insert(acc, {a, b}) end)
-
- z = Enum.reduce(Enum.shuffle(items), %MST{cmp: cmp},
- fn {a, b}, acc -> MST.insert(acc, {a, b}) end)
-
- for {k, v} <- items do
- assert MST.get(y, {k, v}) == true
- assert MST.get(z, {k, v}) == true
- end
- assert MST.get(z, {"foo", "bar"}) == nil
-
- IO.puts "y.root: #{y.root|>Base.encode16}"
- IO.puts "z.root: #{z.root|>Base.encode16}"
- assert y.root == z.root
-
- MST.last(y, nil, 10)
- end
-
- test "merkle search tree 5: MST.last" do
- y = Enum.reduce(0..1000, %MST{},
- fn i, acc -> MST.insert(acc, i) end)
-
- assert(MST.last(y, nil, 2) == [{999, true}, {1000, true}])
- assert(MST.last(y, 42, 2) == [{40, true}, {41, true}])
-
- stuff = for i <- 100..199, do: {i, true}
- assert MST.last(y, 200, 100) == stuff
-
- stuff = for i <- 200..299, do: {i, true}
- assert MST.last(y, 300, 100) == stuff
-
- stuff = for i <- 200..499, do: {i, true}
- assert MST.last(y, 500, 300) == stuff
- end
-
- test "merkle search tree 6: MST.merge" do
- y = Enum.reduce([1, 2, 42], %MST{}, fn i, acc -> MST.insert(acc, i) end)
- z = Enum.reduce([2, 12], %MST{}, fn i, acc -> MST.insert(acc, i) end)
-
- IO.puts "y: "
- MST.dump y
- IO.puts "z: "
- MST.dump z
-
- mg1 = MST.merge(y, z)
- IO.puts "mg1: "
- MST.dump mg1
-
- mg2 = MST.merge(y, z)
- IO.puts "mg2: "
- MST.dump mg2
- assert mg1.root == mg2.root
- end
-
- test "merkle search tree 7: MST.merge" do
- items1 = (for i <- 1..1000, do: i*2+40)
- items2 = (for i <- 1..1000, do: i*3)
-
- y = Enum.reduce(items1, %MST{}, fn i, acc -> MST.insert(acc, i) end)
- z = Enum.reduce(items2, %MST{}, fn i, acc -> MST.insert(acc, i) end)
-
- IO.puts "(merge) y.root: #{y.root|>Base.encode16}"
- IO.puts "(merge) z.root: #{z.root|>Base.encode16}"
-
- mg1 = MST.merge(y, z)
- IO.puts "(merge) mg1.root: #{mg1.root|>Base.encode16}"
-
- mg2 = MST.merge(y, z)
- IO.puts "(merge) mg2.root: #{mg2.root|>Base.encode16}"
-
- assert mg1.root == mg2.root
-
- items1t = (for i <- items1, do: {i, true})
- items2t = (for i <- items2, do: {i, true})
- assert MST.last(y, nil, 1000) == items1t
- assert MST.last(z, nil, 1000) == items2t
-
- all_items = (items1t ++ items2t) |> Enum.sort |> Enum.uniq
- assert MST.last(mg1, nil, 2000) == all_items
- end
-
- test "merkle search tree 8: MST.merge callback" do
- items1 = (for i <- 1..1000, do: i*2+40)
- items2 = (for i <- 1..1000, do: i*3)
-
- y = Enum.reduce(items1, %MST{}, fn i, acc -> MST.insert(acc, i) end)
- z = Enum.reduce(items2, %MST{}, fn i, acc -> MST.insert(acc, i) end)
-
- {:ok, cb_called} = Agent.start_link fn -> [] end
-
- cb = fn i, true -> Agent.update(cb_called, fn x -> [i | x] end) end
- mg = MST.merge(y, z, cb)
-
- cb_vals = Agent.get cb_called, &(&1)
- expected = MapSet.difference(MapSet.new(items2), MapSet.new(items1))
- |> MapSet.to_list
- |> Enum.sort
- |> Enum.reverse
- assert expected == cb_vals
- end
-
-end
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-26 06:56:24 +0000