Skip to content

Instantly share code, notes, and snippets.

@earlonrails
Created May 7, 2018 00:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save earlonrails/7a3d7f0ca5c9e8deae125761f121e1c5 to your computer and use it in GitHub Desktop.
Save earlonrails/7a3d7f0ca5c9e8deae125761f121e1c5 to your computer and use it in GitHub Desktop.
Merkle tree in ruby
#!/usr/bin/env ruby
class Merkle
attr_accessor :key, :parent, :left, :right
def initialize(array, parent = nil)
@parent = parent
@key = array.join
load(array)
end
def load(array)
return if (array.length < 2)
mid = (array.length / 2).floor
if (mid != 1 && mid % 2 != 0)
mid += 1
end
@left = Merkle.new(array[0..(mid - 1)], self)
@right = Merkle.new(array[mid..-1], self)
end
end
require 'minitest/autorun'
describe Merkle do
describe "#new" do
describe "works with 2" do
before do
@m = Merkle.new(['a', 'b'])
end
it "should have 2 nodes" do
@m.key.must_equal("ab")
@m.left.key.must_equal("a")
@m.right.key.must_equal("b")
@m.right.parent.key.must_equal("ab")
end
end
describe "works with 6" do
before do
@m = Merkle.new(['a', 'b', 'c', 'd', 'e', 'f'])
end
it "should have 6 nodes" do
@m.key.must_equal("abcdef")
@m.left.key.must_equal("abcd")
@m.left.left.key.must_equal("ab")
@m.left.left.left.key.must_equal("a")
@m.right.key.must_equal("ef")
@m.right.right.key.must_equal("f")
end
end
describe "works with 11" do
before do
@m = Merkle.new(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k'])
end
it "should have 11 nodes" do
@m.key.must_equal("abcdefghijk")
@m.left.key.must_equal("abcdef")
@m.left.left.key.must_equal("abcd")
@m.left.left.left.key.must_equal("ab")
@m.left.left.left.left.key.must_equal("a")
@m.right.key.must_equal("ghijk")
@m.right.right.key.must_equal("ijk")
@m.right.right.right.key.must_equal("jk")
@m.right.right.right.right.key.must_equal("k")
end
end
describe "works with 12" do
before do
@m = Merkle.new(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l'])
end
it "should have 12 nodes" do
@m.key.must_equal("abcdefghijkl")
@m.left.key.must_equal("abcdef")
@m.left.left.key.must_equal("abcd")
@m.left.left.left.key.must_equal("ab")
@m.left.left.left.left.key.must_equal("a")
@m.right.key.must_equal("ghijkl")
@m.right.right.key.must_equal("kl")
@m.right.right.right.key.must_equal("l")
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment