1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
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
|
