Created
May 7, 2018 00:54
-
-
Save earlonrails/7a3d7f0ca5c9e8deae125761f121e1c5 to your computer and use it in GitHub Desktop.
Merkle tree in ruby
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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