import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.List;

class MerkleNode {
    private String hash;
    private MerkleNode left;
    private MerkleNode right;

    public MerkleNode(String hash) {
        this.hash = hash;
        this.left = null;
        this.right = null;
    }

    public String getHash() {
        return hash;
    }

    public MerkleNode getLeft() {
        return left;
    }

    public void setLeft(MerkleNode left) {
        this.left = left;
    }

    public MerkleNode getRight() {
        return right;
    }

    public void setRight(MerkleNode right) {
        this.right = right;
    }
}

public class MerkleTree {
    private MerkleNode root;

    public MerkleTree(List<String> data) {
        this.root = buildTree(data);
    }

    public MerkleNode getRoot() {
        return root;
    }

    private MerkleNode buildTree(List<String> data) {
        List<MerkleNode> nodes = new ArrayList<>();

        for (String value : data) {
            String hash = calculateHash(value);
            nodes.add(new MerkleNode(hash));
        }

        while (nodes.size() > 1) {
            List<MerkleNode> tempNodes = new ArrayList<>();

            for (int i = 0; i < nodes.size(); i += 2) {
                MerkleNode left = nodes.get(i);
                MerkleNode right = (i + 1 < nodes.size()) ? nodes.get(i + 1) : null;
                String concatHash = left.getHash() + ((right != null) ? right.getHash() : "");
                String parentHash = calculateHash(concatHash);
                MerkleNode parent = new MerkleNode(parentHash);
                parent.setLeft(left);
                parent.setRight(right);
                tempNodes.add(parent);
            }

            nodes = tempNodes;
        }

        return nodes.get(0);
    }

    private String calculateHash(String data) {
        try {
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] hash = digest.digest(data.getBytes(StandardCharsets.UTF_8));
            StringBuilder hexString = new StringBuilder();

            for (byte b : hash) {
                String hex = Integer.toHexString(0xff & b);
                if (hex.length() == 1) {
                    hexString.append('0');
                }
                hexString.append(hex);
            }

            return hexString.toString();
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }

        return null;
    }

    public static void main(String[] args) {
        List<String> data = new ArrayList<>();
        data.add("Comment 1");
        data.add("Comment 2");
        data.add("Comment 3");
        data.add("Comment 4");
        data.add("Private Key");
        data.add("Like Count");

        MerkleTree merkleTree = new MerkleTree(data);
        MerkleNode root = merkleTree.getRoot();

        printMerkleTree(root, 0);
    }

    private static void printMerkleTree(MerkleNode root, int level) {
        if (root == null) {
            return;
        }

        for (int i = 0; i < level; i++) {
            System.out.print("  ");
        }

        System.out.println("|-- " + root.getHash());

        printMerkleTree(root.getLeft(), level + 1);
        printMerkleTree(root.getRight(), level + 1);
    }
}
/*这个程序定义了一个MerkleNode类表示梅克尔树中的节点，并提供了用于获取哈希值和子节点的方法。MerkleTree类构建了梅克尔树，并提供了获取根节点的方法。程序中的calculateHash方法使用SHA-256算法计算数据的哈希值。

在main方法中，创建一个包含评论索引、评论哈希、私钥签名和点赞数的数据列表，并使用该数据构建一个梅克尔树。然后，打印出整个梅克尔树的结构。*/