A simple implementation of Merkel Tree with sha256

MerkelTreeDemo.java

package org.jiacheo.awesome.blockchain;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import org.apache.commons.codec.digest.DigestUtils;
import org.jiacheo.awesome.p2p.cmd.codec.JsonUtil;

/**
 * merkel tree simple implement.
 *
 * @author jiacheo
 */
public class MerkelTreeDemo {

  public static void main(String[] args) throws Exception {
    String[] testData = new String[]{"1", "2", "3", "4", "5"};
//    String[] testData = new String[]{"I","2","3","4"};
    MerkelTree merkelTree = new MerkelTree();
    for (String test : testData) {
      merkelTree.addLeaf(DigestUtils.sha256Hex(test));
    }
    merkelTree.buildToRoot();
    System.out.println(JsonUtil.toJson(merkelTree.getRoot()));
    System.out.println(JsonUtil.toJson(merkelTree.getFullTree()));
  }

  static class MerkelTree {

    private List<Node> leafs = new LinkedList<>();
    private List<Node> fullTree = new LinkedList<>();
    private Node root;

    private boolean hasBuilt = false;

    public void addLeaf(String hash) {
      Node node = new Node(hash, true, false);
      addLeaf(node);
    }

    //note: this function is not thread-safe
    private void addLeaf(Node node) {
      if(hasBuilt) {
        throw new RuntimeException("An already built merkel tree could not add any leaf");
      }
      leafs.add(node);
    }

    public List<Node> getFullTree() {
      return fullTree;
    }

    private void padding(List<Node> nodeList) throws Exception {
      nodeList.add((Node)(nodeList.get(nodeList.size() - 1).clone()));
    }

    //note: this function is not thread-safe
    public void buildToRoot() throws Exception {
      int size = leafs.size();
      //if leaves count is odd,  must get padding
      if ((size & 0x00000001) == 1) {
        padding(leafs);
      }
      fullTree.addAll(leafs);
      int i = 0;
      List<Node> temp = new LinkedList<>();
      Iterator<Node> iterator = leafs.iterator();
      int iteratorSize = leafs.size();

      //if iteratorSize is 1, we get the root node.
      while (iteratorSize != 1) {
        String hash = "";
        while (iterator.hasNext()) {
          Node next = iterator.next();
          hash += next.hash;
          if (i == 1) {
            String parentHash = DigestUtils.sha256Hex(hash);
            temp.add(new Node(parentHash, false, false));
            hash = "";
          }
          i = (i + 1) % 2;
        }

        int tempSize = temp.size();
        if (tempSize > 1 && (tempSize & 0x00000001) == 1) {
          //a non-root odd-count middle node list must get padding
          padding(temp);
        }
        iterator = temp.iterator();
        iteratorSize = temp.size();
        fullTree.addAll(temp);
        if (iteratorSize > 1) {
          temp = new LinkedList<>();
        }
      }
      root = fullTree.get(fullTree.size() - 1);
      root.isRoot = true;
      hasBuilt = true;
    }

    public Node getRoot() {
      return root;
    }

    static class Node implements Cloneable {

      public String hash;
      public boolean isLeaf;
      public boolean isRoot;

      Node(String hash, boolean isLeaf, boolean isRoot) {
        this.hash = hash;
        this.isLeaf = isLeaf;
        this.isRoot = isRoot;
      }

      @Override
      public String toString() {
        return "Node{" +
          "hash='" + hash + '\'' +
          ", isLeaf=" + isLeaf +
          ", isRoot=" + isRoot +
          '}';
      }

      @Override
      public Object clone() throws CloneNotSupportedException {
        Node node = new Node(this.hash, this.isLeaf, this.isRoot);
        return node;
      }
    }

  }

}