path: root/test/mst_test.exs

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
  end
end