-
-
Save emdeeeks/f09fa76e5d6025452c05561a19a97ffe 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