Implement merge for Merkle search tree, not yet working over network

1 files changed, 47 insertions, 1 deletions

diff --git a/test/mst_test.exs b/test/mst_test.exs
index 7fe340e..cf5a898 100644
--- a/test/mst_test.exs
+++ b/test/mst_test.exs
@@ -111,7 +111,7 @@ defmodule ShardTest.MST do
     MST.last(y, nil, 10)
   end
 
-  test "merkle search tree 5" do
+  test "merkle search tree 5: MST.last" do
     y = Enum.reduce(0..1000, %MST{},
                     fn i, acc -> MST.insert(acc, i) end)
 
@@ -128,4 +128,50 @@ defmodule ShardTest.MST do
     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
+
 end