Custom compare and merge functions for Merkle search tree0.0.1

7 files changed, 231 insertions, 111 deletions

diff --git a/lib/app/chat.ex b/lib/app/chat.ex
index 85f5265..e28e896 100644
--- a/lib/app/chat.ex
+++ b/lib/app/chat.ex
@@ -49,7 +49,7 @@ defmodule SApp.Chat do
           }
         }
       :redundant ->
-        exit(:normal)
+        exit(:redundant)
     end
   end
 
@@ -171,7 +171,14 @@ defmodule SApp.Chat do
   end
 
   defp msg_cmp({ts1, nick1, msg1}, {ts2, nick2, msg2}) do
-    SData.MerkleList.cmp_ts_str({ts1, nick1<>"|"<>msg1}, 
-                                   {ts2, nick2<>"|"<>msg2})
+    cond do
+      ts1 > ts2 -> :after
+      ts1 < ts2 -> :before
+      nick1 > nick2 -> :after
+      nick1 < nick2 -> :before
+      msg1 > msg2 -> :after
+      msg1 < msg2 -> :before
+      true -> :duplicate
+    end
   end 
 end
diff --git a/lib/data/data.ex b/lib/data/data.ex
index 428957c..c2c659d 100644
--- a/lib/data/data.ex
+++ b/lib/data/data.ex
@@ -1,6 +1,13 @@
 defmodule SData do
   @moduledoc """
   Utility functions
+
+  Compare functions are functions that compares stored items and provides a total order.
+  They must return:
+    - `:after` if the first argument is more recent
+    - `:duplicate` if the two items are the same
+    - `:before` if the first argument is older
+  These functions must only return :duplicate for equal items.
   """
 
   @doc """
@@ -11,4 +18,32 @@ defmodule SData do
     :crypto.hash(algo, (:erlang.term_to_binary term))
   end
 
+  @doc"""
+    Compare function for arbitrary terms using the Erlang order
+  """
+  def cmp_term(a, b) do
+    cond do
+      a > b -> :after
+      a < b -> :before
+      a == b -> :duplicate
+    end
+  end
+
+  @doc"""
+    Compare function for timestamped strings
+  """
+  def cmp_ts_str({ts1, str1}, {ts2, str2}) do
+    cond do
+      ts1 > ts2 -> :after
+      ts1 < ts2 -> :before
+      str1 > str2 -> :after
+      str1 < str2 -> :before
+      true -> :duplicate
+    end
+  end
+
+  @doc"""
+    Merge function for nils
+  """
+  def merge_true(true, true), do: true
 end
diff --git a/lib/data/merklelist.ex b/lib/data/merklelist.ex
index 357f336..9b44ee8 100644
--- a/lib/data/merklelist.ex
+++ b/lib/data/merklelist.ex
@@ -14,11 +14,7 @@ defmodule SData.MerkleList do
   @doc"""
   Create a Merkle list store.
 
-  `cmp` is a function that compares stored items and provides a total order.
-  It must return:
-    - `:after` if the first argument is more recent
-    - `:duplicate` if the two items are the same
-    - `:before` if the first argument is older
+  `cmp` is a compare function that respects the interface defined in module `SData`.
   """
   def new(cmp) do
     root_item = :root
@@ -144,17 +140,4 @@ defmodule SData.MerkleList do
         end
     end
   end
-
-  @doc"""
-    Compare function for timestamped strings
-  """
-  def cmp_ts_str({ts1, str1}, {ts2, str2}) do
-    cond do
-      ts1 > ts2 -> :after
-      ts1 < ts2 -> :before
-      str1 == str2 -> :duplicate
-      str1 > str2 -> :after
-      str1 < str2 -> :before
-    end
-  end
 end
diff --git a/lib/data/merklesearchtree.ex b/lib/data/merklesearchtree.ex
index 963653e..0554f82 100644
--- a/lib/data/merklesearchtree.ex
+++ b/lib/data/merklesearchtree.ex
@@ -7,8 +7,8 @@ defmodule SData.MerkleSearchTree do
       level,
       hash_of_node | nil,
       [ 
-        { k_low_bound, v, hash_of_node | nil },
-        { k_low_bound, v, hash_of_node | nil },
+        { item_low_bound, hash_of_node | nil },
+        { item_low_bound, hash_of_node | nil },
         ...
       }
     }
@@ -16,8 +16,22 @@ defmodule SData.MerkleSearchTree do
 
   alias SData.PageStore, as: Store
 
-  defstruct [:root, :store]
+  @doc"""
+  Create a new Merkle search tree.
 
+  This structure can be used as a set with only true keys,
+  or as a map if a merge function is given.
+
+  `cmp` is a compare function for keys as defined in module `SData`.
+
+  `merge` is a function for merging two items that have the same key.
+  """
+  defstruct root: nil,
+            store: SData.LocalStore.new,
+            cmp: &SData.cmp_term/2,
+            merge: &SData.merge_true/2
+
+          
   defmodule Page do
     defstruct [:level, :low, :list]
   end
@@ -34,17 +48,10 @@ defmodule SData.MerkleSearchTree do
   end
 
 
-  def new(store \\ nil) do
-    store = store || SData.LocalStore.new
-    %SData.MerkleSearchTree{
-      root:  nil,
-      store: store
-    }
-  end
 
-  def insert(state, key, value) do
+  def insert(state, key, value \\ true) do
     level = calc_level(key)
-    {hash, store} = insert_at(state.store, state.root, key, level, value)
+    {hash, store} = insert_at(state, state.store, state.root, key, level, value)
     %{ state | root: hash, store: store }
   end
 
@@ -52,7 +59,7 @@ defmodule SData.MerkleSearchTree do
     # TODO
   end
 
-  defp insert_at(store, root, key, level, value) do
+  defp insert_at(s, store, root, key, level, value) do
     {new_page, store} = if root == nil do
       { %Page{ level: level, low: nil, list: [ { key, value, nil } ] }, store }
     else
@@ -60,46 +67,48 @@ defmodule SData.MerkleSearchTree do
       [ { k0, _, _} | _ ] = lst
       cond do
         plevel < level ->
-          {low, high, store} = split(store, root, key)
+          {low, high, store} = split(s, store, root, key)
           { %Page{ level: level, low: low, list: [ { key, value, high } ] }, store }
         plevel == level ->
           store = Store.free(store, root)
-          if key < k0 do
-            {low2a, low2b, store} = split(store, low, key)
-            { %Page{ level: level, low: low2a, list: [ { key, value, low2b } | lst] }, store }
-          else
-            {new_lst, store} = aux_insert_after_first(store, lst, key, value)
-            { %Page{ level: plevel, low: low, list: new_lst }, store }
+          case s.cmp.(key, k0) do
+            :before ->
+              {low2a, low2b, store} = split(s, store, low, key)
+              { %Page{ level: level, low: low2a, list: [ { key, value, low2b } | lst] }, store }
+            _ ->
+              {new_lst, store} = aux_insert_after_first(s, store, lst, key, value)
+              { %Page{ level: plevel, low: low, list: new_lst }, store }
           end
         plevel > level ->
           store = Store.free(store, root)
-          if key < k0 do
-            {new_low, store} = insert_at(store, low, key, level, value)
-            { %Page{ level: plevel, low: new_low, list: lst }, store }
-          else 
-            {new_lst, store} = aux_insert_sub_after_first(store, lst, key, level, value)
-            { %Page{ level: plevel, low: low, list: new_lst }, store }
+          case s.cmp.(key, k0) do
+            :before ->
+              {new_low, store} = insert_at(s, store, low, key, level, value)
+              { %Page{ level: plevel, low: new_low, list: lst }, store }
+            :after ->
+              {new_lst, store} = aux_insert_sub_after_first(s, store, lst, key, level, value)
+              { %Page{ level: plevel, low: low, list: new_lst }, store }
           end
       end
     end
     Store.put(store, new_page)    # returns {hash, store}
   end
 
-  defp split(store, hash, key) do
+  defp split(s, store, hash, key) do
     if hash == nil do
       {nil, nil, store}
     else
       %Page{ level: level, low: low, list: lst } = Store.get(store, hash)
       store = Store.free(store, hash)
       [ { k0, _, _} | _ ] = lst
-      cond do
-        key < k0 ->
-          {lowlow, lowhi, store} = split(store, low, key)
+      case s.cmp.(key, k0) do
+        :before ->
+          {lowlow, lowhi, store} = split(s, store, low, key)
           newp2 = %Page{ level: level, low: lowhi, list: lst }
           {newp2h, store} = Store.put(store, newp2)
           {lowlow, newp2h, store}
-        key > k0 ->
-          {lst1, p2, store} = split_aux(store, lst, key, level)
+        :after ->
+          {lst1, p2, store} = split_aux(s, store, lst, key, level)
           newp1 = %Page{ level: level, low: low, list: lst1}
           {newp1h, store} = Store.put(store, newp1)
           {newp1h, p2, store}
@@ -107,79 +116,105 @@ defmodule SData.MerkleSearchTree do
     end
   end
 
-  defp split_aux(store, lst, key, level) do
+  defp split_aux(s, store, lst, key, level) do
     case lst do
-      [ {k1, _, _} | _ ] when k1 == key ->
-        raise "Bad logic"
       [ {k1, v1, r1} ] ->
-        {r1l, r1h, store} = split(store, r1, key)
+        if s.cmp.(k1, key) == :duplicate do
+          raise "Bad logic"
+        end
+        {r1l, r1h, store} = split(s, store, r1, key)
         { [{k1, v1, r1l}], r1h, store }
-      [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2->
-        {r1l, r1h, store} = split(store, r1, key)
-        p2 = %Page{ level: level, low: r1h, list: [ {k2, v2, r2} | rst ] }
-        {p2h, store} = Store.put(store, p2)
-        { [{k1, v1, r1l}], p2h, store }
-      [ fst | rst ] ->
-        {rst2, hi, store} = split_aux(store, rst, key, level)
-        { [ fst | rst2 ], hi, store }
+      [ {k1, v1, r1} = fst, {k2, v2, r2} = rst1 | rst ] ->
+        case s.cmp.(key, k2) do
+          :before ->
+            {r1l, r1h, store} = split(s, store, r1, key)
+            p2 = %Page{ level: level, low: r1h, list: [ {k2, v2, r2} | rst ] }
+            {p2h, store} = Store.put(store, p2)
+            { [{k1, v1, r1l}], p2h, store }
+          :after ->
+            {rst2, hi, store} = split_aux(s, store, [rst1 | rst], key, level)
+            { [ fst | rst2 ], hi, store }
+          :duplicate ->
+            raise "Bad logic"
+        end
     end
   end
 
-  defp aux_insert_after_first(store, lst, key, value) do
+  defp aux_insert_after_first(s, store, lst, key, value) do
     case lst do
-      [ {k1, _old_value, r1} | rst ] when k1 == key ->
-        { [ {k1, value, r1} | rst ], store }
       [ {k1, v1, r1} ] ->
-        {r1a, r1b, new_store} = split(store, r1, key)
-        { [ {k1, v1, r1a}, {key, value, r1b} ], new_store }
-      [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2->
-        {r1a, r1b, new_store} = split(store, r1, key)
-        { [ {k1, v1, r1a}, {key, value, r1b}, {k2, v2, r2} | rst ], new_store }
-      [ fst | rst ] ->
-        {rst2, new_store} = aux_insert_after_first(store, rst, key, value)
-        { [ fst | rst2 ], new_store }
+        case s.cmp.(k1, key) do
+          :duplicate ->
+            { [ {k1, s.merge.(v1, value), r1} ], store }
+          :before ->
+            {r1a, r1b, new_store} = split(s, store, r1, key)
+            { [ {k1, v1, r1a}, {key, value, r1b} ], new_store }
+        end
+      [ {k1, v1, r1} = fst, {k2, v2, r2} = rst1 | rst ] ->
+        case s.cmp.(k1, key) do
+          :duplicate ->
+            { [ {k1, s.merge.(v1, value), r1}, rst1 | rst ], store }
+          :before ->
+            case s.cmp.(k2, key) do
+              :after ->
+                {r1a, r1b, new_store} = split(s, store, r1, key)
+                { [ {k1, v1, r1a}, {key, value, r1b}, {k2, v2, r2} | rst ], new_store }
+              _ ->
+                {rst2, new_store} = aux_insert_after_first(s, store, [rst1 | rst], key, value)
+                { [ fst | rst2 ], new_store }
+            end
+        end
+      end
     end
-  end
 
-  defp aux_insert_sub_after_first(store, lst, key, level, value) do
+  defp aux_insert_sub_after_first(s, store, lst, key, level, value) do
     case lst do
-      [ {k1, _, _} | _ ] when k1 == key ->
-        raise "Bad logic"
       [ {k1, v1, r1} ] ->
-        {r1new, store_new} = insert_at(store, r1, key, level, value)
+        if s.cmp.(k1, key) == :duplicate do
+          raise "Bad logic"
+        end
+        {r1new, store_new} = insert_at(s, store, r1, key, level, value)
         { [{k1, v1, r1new}], store_new }
-      [ {k1, v1, r1}, {k2, v2, r2} | rst ] when key < k2->
-        {r1new, store_new} = insert_at(store, r1, key, level, value)
-        { [{k1, v1, r1new}, {k2, v2, r2} | rst], store_new }
-      [ fst | rst ] ->
-        {rst2, new_store} = aux_insert_sub_after_first(store, rst, key, level, value)
-        { [ fst | rst2 ], new_store }
+      [ {k1, v1, r1} = fst, {k2, _, _} = rst1 | rst ] ->
+        if s.cmp.(k1, key) == :duplicate do
+          raise "Bad logic"
+        end
+        case s.cmp.(key, k2) do
+          :before ->
+            {r1new, store_new} = insert_at(s, store, r1, key, level, value)
+            { [{k1, v1, r1new}, rst1 | rst], store_new }
+          _ ->
+            {rst2, new_store} = aux_insert_sub_after_first(s, store, [rst1 |rst], key, level, value)
+            { [ fst | rst2 ], new_store }
+        end
     end
   end
 
   def get(state, key) do
-    get(state.store, state.root, key)
+    get(state, state.store, state.root, key)
   end
 
-  defp get(store, root, key) do
+  defp get(s, store, root, key) do
     case root do
       nil -> nil
       _ ->
         %Page{ level: _, low: low, list: lst } = Store.get(store, root)
-        get_aux(store, low, lst, key)
+        get_aux(s, store, low, lst, key)
     end
   end
 
-  defp get_aux(store, low, lst, key) do
+  defp get_aux(s, store, low, lst, key) do
     case lst do
       [] ->
-        get(store, low, key)
-      [ {k, v, _} | _ ] when key == k ->
-        v
-      [ {k, _, _} | _ ] when key < k ->
-        get(store, low, key)
-      [ {k, _, low2} | rst ] when key > k ->
-        get_aux(store, low2, rst, key)
+        get(s, store, low, key)
+      [ {k, v, low2} | rst ] ->
+        case s.cmp.(key, k) do
+          :duplicate -> v
+          :before ->
+            get(s, store, low, key)
+          :after -> 
+            get_aux(s, store, low2, rst, key)
+        end
     end
   end
 
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