From 04891bbcaac75e887d57844548b61141cb6ebc07 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Fri, 13 Jun 2025 13:29:29 +0200
Subject: Init

---
 src/merkle/merkletree.rs | 67 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)
 create mode 100644 src/merkle/merkletree.rs

(limited to 'src/merkle/merkletree.rs')

diff --git a/src/merkle/merkletree.rs b/src/merkle/merkletree.rs
new file mode 100644
index 0000000..58a7c75
--- /dev/null
+++ b/src/merkle/merkletree.rs
@@ -0,0 +1,67 @@
+use crate::{hasher::Hasher, merkle::node::Node};
+
+#[derive(Debug)]
+pub struct MerkleTree {
+    leafs: Vec<Node>,
+    height: usize,
+    root: Node,
+}
+
+impl MerkleTree {
+    pub fn new<T: ToString>(hasher: &dyn Hasher, data: Vec<T>) -> Self {
+        assert!(
+            !data.is_empty(),
+            "Merkle Tree requires at least one element"
+        );
+
+        let mut leafs: Vec<Node> = data
+            .into_iter()
+            .map(|x| Node::new_leaf(hasher, x))
+            .collect();
+        if leafs.len() % 2 != 0 {
+            leafs.push(leafs[leafs.len() - 1].clone());
+        }
+
+        Self::build(hasher, leafs)
+    }
+
+    fn build(hasher: &dyn Hasher, mut nodes: Vec<Node>) -> Self {
+        let leafs = nodes.clone();
+        let mut height = 0;
+
+        while nodes.len() > 1 {
+            let mut next_level = Vec::new();
+            for pair in nodes.chunks(2) {
+                let left = pair[0].clone();
+                let right = if pair.len() == 2 {
+                    pair[1].clone()
+                } else {
+                    left.clone()
+                };
+                next_level.push(Node::new_internal(hasher, left, right));
+            }
+            nodes = next_level;
+            height += 1;
+        }
+
+        let root = nodes.remove(0);
+
+        MerkleTree {
+            leafs,
+            height: height + 1,
+            root,
+        }
+    }
+
+    pub fn height(&self) -> usize {
+        self.height
+    }
+
+    pub fn len(&self) -> usize {
+        self.leafs.len()
+    }
+
+    pub fn root(&self) -> Node {
+        self.root.clone()
+    }
+}
-- 
cgit v1.2.3-71-g8e6c