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
|
#!/usr/bin/env ruby
$: << File.expand_path('../../../lib', __FILE__)
require 'concurrent-edge'
Channel = Concurrent::Channel
## A Tour of Go: Equivalent Binary Trees
# https://tour.golang.org/concurrency/8
Tree = Struct.new(:value, :left, :right)
def new_tree(n, size = 10)
values = [*1..size].collect{|i| i * n }.sample(size)
root = Tree.new(values.shift)
inserter = ->(current, new) do
if new.value <= current.value
if current.left.nil?
current.left = new
else
inserter.call(current.left, new)
end
else
if current.right.nil?
current.right = new
else
inserter.call(current.right, new)
end
end
end
while value = values.shift do
inserter.call(root, Tree.new(value))
end
root
end
def walk(tree, channel)
_walk = ->(t, ch) do
return unless t
_walk.call(t.left, ch)
ch << t.value
_walk.call(t.right, ch)
end
_walk.call(tree, channel)
channel.close
end
def same(t1, t2)
ch1 = Channel.new
ch2 = Channel.new
Channel.go { walk(t1, ch1) }
Channel.go { walk(t2, ch2) }
ch1.each do |v|
return false unless v == ~ch2
end
return true
end
puts same(new_tree(1), new_tree(1))
puts same(new_tree(1), new_tree(2))
__END__
true
false
|
