import hashlib
from typing import List, Tuple, Any


class MerkleLedger:
    def __init__(self):
        self._leaves: List[bytes] = []

    def add_entry(self, data: Any) -> int:
        b = str(data).encode("utf-8")
        self._leaves.append(b)
        return len(self._leaves) - 1

    def _hash(self, data: bytes) -> bytes:
        return hashlib.sha256(data).digest()

    def root(self) -> bytes:
        if not self._leaves:
            return b""
        nodes = [self._hash(l) for l in self._leaves]
        while len(nodes) > 1:
            new_nodes: List[bytes] = []
            for i in range(0, len(nodes), 2):
                left = nodes[i]
                right = nodes[i + 1] if i + 1 < len(nodes) else left
                new_nodes.append(self._hash(left + right))
            nodes = new_nodes
        return nodes[0]

    def get_proof(self, index: int) -> List[Tuple[str, str]]:
        # Return a simple list of (hash_hex, side) for verification
        if index < 0 or index >= len(self._leaves):
            return []
        path: List[Tuple[str, str]] = []
        # Build a simple merkle tree on the fly for proof generation
        level = [self._hash(l) for l in self._leaves]
        idx = index
        while len(level) > 1:
            next_level: List[bytes] = []
            for i in range(0, len(level), 2):
                left = level[i]
                right = level[i + 1] if i + 1 < len(level) else left
                combined = self._hash(left + right)
                next_level.append(combined)
                if i == idx or i + 1 == idx:
                    sibling = right if i == idx else left
                    side = "right" if i == idx else "left"
                    path.append((sibling.hex(), side))
                    idx = len(next_level) - 1
            level = next_level
        return path

    def verify_proof(self, leaf_index: int, data: Any, proof: List[Tuple[str, str]], root: bytes) -> bool:
        current = hashlib.sha256(str(data).encode("utf-8")).digest()
        idx = leaf_index
        for p_hash_hex, side in proof:
            sibling = bytes.fromhex(p_hash_hex)
            if side == "right":
                current = hashlib.sha256(current + sibling).digest()
            else:
                current = hashlib.sha256(sibling + current).digest()
        return current == root