Custom compare and merge functions for Merkle search tree0.0.1

3 files changed, 73 insertions, 13 deletions

diff --git a/test/conn_test.exs b/test/conn_test.exs
index d2431d7..275f6dd 100644
--- a/test/conn_test.exs
+++ b/test/conn_test.exs
@@ -56,10 +56,7 @@ defmodule ShardTest.Conn do
     GenServer.cast(pid1, {:chat_send, "test msg 1"})
     GenServer.cast(pid2, {:chat_send, "test msg 2"})
 
-    receive do after 100 -> nil end
-    {:ok, pid3} = DynamicSupervisor.start_child(Shard.DynamicSupervisor, {SApp.Chat, "test"})
-    receive do after 100 -> nil end
-    assert not Process.alive?(pid3)
+    {:error, :redundant} = DynamicSupervisor.start_child(Shard.DynamicSupervisor, {SApp.Chat, "test"})
   end
 
 end
diff --git a/test/mkllst_test.exs b/test/mkllst_test.exs
index ac13795..68dacf3 100644
--- a/test/mkllst_test.exs
+++ b/test/mkllst_test.exs
@@ -5,7 +5,7 @@ defmodule ShardTest.MklLst do
   test "merkle list" do
     alias SData.MerkleList, as: ML
 
-    mkl = ML.new(&ML.cmp_ts_str/2)
+    mkl = ML.new(&SData.cmp_ts_str/2)
 
     {:ok, [], nil} = ML.read(mkl)
 
diff --git a/test/mst_test.exs b/test/mst_test.exs
index 6615b6e..73b4f63 100644
--- a/test/mst_test.exs
+++ b/test/mst_test.exs
@@ -4,16 +4,16 @@ defmodule ShardTest.MST do
   doctest Shard.Application
 
   test "merkle search tree 1" do
-    y = Enum.reduce(0..1000, MST.new(),
-                    fn i, acc -> MST.insert(acc, i, i) end)
+    y = Enum.reduce(0..1000, %MST{},
+                    fn i, acc -> MST.insert(acc, i) end)
 
 
-    z = Enum.reduce(Enum.shuffle(0..1000), MST.new(),
-                    fn i, acc -> MST.insert(acc, i, 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) == i
-      assert MST.get(z, i) == i
+      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
@@ -30,10 +30,12 @@ defmodule ShardTest.MST do
               {h, SData.term_hash h}
             end
 
-    y = Enum.reduce(items, MST.new(),
+    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.new(),
+    z = Enum.reduce(Enum.shuffle(items), %MST{merge: merge},
                     fn {k, v}, acc -> MST.insert(acc, k, v) end)
 
     for {k, v} <- items do
@@ -45,4 +47,65 @@ defmodule ShardTest.MST do
     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
+  end
 end