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

1 files changed, 55 insertions, 5 deletions

diff --git a/lib/data/merklesearchtree.ex b/lib/data/merklesearchtree.ex
index b751a08..3676244 100644
--- a/lib/data/merklesearchtree.ex
+++ b/lib/data/merklesearchtree.ex
@@ -96,7 +96,7 @@ defmodule SData.MerkleSearchTree do
     if hash == nil do
       {nil, nil, store}
     else
-      %Page{ level: level, low: low, list: lst } = Store.get(store, hash)
+      %Page{ level: level, low: low, list: lst } = Store.get(store, hash) || Store.get(s.store, hash)
       store = Store.free(store, hash)
       [ { k0, _, _} | _ ] = lst
       case s.cmp.(key, k0) do
@@ -189,7 +189,11 @@ defmodule SData.MerkleSearchTree do
   end
 
   @doc"""
-    Merge values from another MST in this MST
+  Merge values from another MST in this MST.
+
+  The merge is not symmetrical in the sense that:
+  - new pages are added in the store of the first argument
+  - the callback is called for all items found in the second argument and not the first
   """
   def merge(to, from, callback \\ fn _, _ -> nil end) do
     { store, root } = merge_aux(to, from, to.store, to.root, from.root, callback)
@@ -198,6 +202,7 @@ defmodule SData.MerkleSearchTree do
 
   defp merge_aux(s1, s2, store, r1, r2, callback) do
     case {r1, r2} do
+      _ when r1 == r2 -> { store, r1 }
       {_, nil} ->
         { store, r1 }
       {nil, _} ->
@@ -205,9 +210,54 @@ defmodule SData.MerkleSearchTree do
         rec_callback(store, r2, callback)
         { store, r2 }
       _ ->
-        IO.puts("not implemented: complex merge step")
-        #TODO
-        { store, r1 }
+        %Page{ level: level1, low: low1, list: lst1 } = Store.get(store, r1)
+        %Page{ level: level2, low: low2, list: lst2 } = Store.get(store, r2) || Store.get(s2.store, r2)
+        { level, low1, lst1, low2, lst2 } = cond do
+          level1 == level2 -> {level1, low1, lst1, low2, lst2}
+          level1 > level2 ->  {level1, low1, lst1, r2, []}
+          level2 > level1 ->  {level2, r1, [], low2, lst2}
+        end
+        { store, low, lst } = merge_aux_rec(s1, s2, store, low1, lst1, low2, lst2, callback)
+        page = %Page{ level: level, low: low, list: lst }
+        {hash, store} = Store.put(store, page)
+        {store, hash}
+    end
+  end
+
+  defp merge_aux_rec(s1, s2, store, low1, lst1, low2, lst2, callback) do
+    case {lst1, lst2} do
+      { [], [] } ->
+        {store, hash} = merge_aux(s1, s2, store, low1, low2, callback)
+        {store, hash, []}
+      { [], [ {k, v, r} | rst2 ] } ->
+        {low1l, low1h, store} = split(s1, store, low1, k)
+        {store, newlow} = merge_aux(s1, s2, store, low1l, low2, callback)
+        {store, newr, newrst} = merge_aux_rec(s1, s2, store, low1h, [], r, rst2, callback)
+        {store, newlow, [ {k, v, newr} | newrst ]}
+      { [ {k, v, r} | rst1 ], [] } ->
+        {low2l, low2h, store} = split(s2, store, low2, k)
+        {store, newlow} = merge_aux(s1, s2, store, low1, low2l, callback)
+        {store, newr, newrst} = merge_aux_rec(s1, s2, store, r, rst1, low2h, [], callback)
+        {store, newlow, [ {k, v, newr} | newrst ]}
+      { [ {k1, v1, r1} | rst1 ], [ {k2, v2, r2} | rst2 ] } ->
+        case s1.cmp.(k1, k2) do
+          :before ->
+            {low2l, low2h, store} = split(s2, store, low2, k1)
+            {store, newlow} = merge_aux(s1, s2, store, low1, low2l, callback)
+            {store, newr, newrst} = merge_aux_rec(s1, s2, store, r1, rst1, low2h, lst2, callback)
+            {store, newlow, [ {k1, v1, newr} | newrst ]}
+          :after ->
+            {low1l, low1h, store} = split(s1, store, low1, k2)
+            {store, newlow} = merge_aux(s1, s2, store, low1l, low2, callback)
+            callback.(k2, v2)
+            {store, newr, newrst} = merge_aux_rec(s1, s2, store, low1h, lst1, r2, rst2, callback)
+            {store, newlow, [ {k2, v2, newr} | newrst ]}
+          :duplicate ->
+            {store, newlow} = merge_aux(s1, s2, store, low1, low2, callback)
+            newv = s1.merge.(v1, v2) ## TODO: callback here ??
+            {store, newr, newrst} = merge_aux_rec(s1, s2, store, r1, rst1, r2, rst2, callback)
+            {store, newlow, [ {k1, newv, newr} | newrst ]}
+        end
     end
   end