From c4eeb0db2219e63801ce566b7724e849c74e0fed Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Mon, 16 Jun 2025 11:49:45 +0200
Subject: Remove `src/merkle` folder

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

(limited to 'src/merkletree.rs')

diff --git a/src/merkletree.rs b/src/merkletree.rs
new file mode 100644
index 0000000..6173c2f
--- /dev/null
+++ b/src/merkletree.rs
@@ -0,0 +1,174 @@
+//! Provides the MerkleTree structure and associated methods for creating and interacting
+//! with binary Merkle trees using custom hashers.
+
+use crate::{hasher::Hasher, node::Node};
+
+/// A binary Merkle tree implementation.
+///
+/// Merkle trees are hash-based data structures used for secure and efficient data verification.
+/// Each leaf node contains the hash of a data item, and each internal node contains the hash
+/// of the concatenation of its children's hashes.
+#[derive(Debug)]
+pub struct MerkleTree {
+    /// Leaf nodes at the base of the tree (may include a duplicate for even pairing).
+    leaves: Vec<Node>,
+    /// Height of the tree (number of levels including root).
+    height: usize,
+    /// Root node of the Merkle tree.
+    root: Node,
+}
+
+impl MerkleTree {
+    /// Creates a new `MerkleTree` from a collection of data items and a hash function.
+    ///
+    /// # Arguments
+    ///
+    /// * `hasher` - A reference to an implementation of the `Hasher` trait.
+    /// * `data` - A vector of values to be converted into leaf nodes.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the `data` vector is empty.
+    ///
+    /// # Notes
+    ///
+    /// If the number of leaf nodes is odd, the last node is duplicated to ensure all internal
+    /// nodes have exactly two children.
+    pub fn new<I, T>(hasher: &dyn Hasher, data: I) -> Self
+    where
+        I: IntoIterator<Item = T>,
+        T: AsRef<[u8]>,
+    {
+        let owned_data: Vec<T> = data.into_iter().collect();
+        let data_slices: Vec<&[u8]> = owned_data.iter().map(|item| item.as_ref()).collect();
+
+        assert!(
+            !data_slices.is_empty(),
+            "Merkle Tree requires at least one element"
+        );
+
+        let mut leaves: Vec<Node> = data_slices
+            .iter()
+            .map(|x| Node::new_leaf(hasher, x))
+            .collect();
+
+        if leaves.len() % 2 != 0 {
+            leaves.push(leaves[leaves.len() - 1].clone());
+        }
+
+        Self::build(hasher, leaves)
+    }
+
+    /// Constructs the internal nodes of the tree from the leaves upward and computes the root.
+    fn build(hasher: &dyn Hasher, mut nodes: Vec<Node>) -> Self {
+        let leaves = nodes.clone();
+        let mut height = 0;
+
+        while nodes.len() > 1 {
+            if nodes.len() % 2 != 0 {
+                // duplicate last node to make the count even
+                nodes.push(nodes[nodes.len() - 1].clone());
+            }
+
+            let mut next_level = Vec::new();
+            for pair in nodes.chunks(2) {
+                let (left, right) = (pair[0].clone(), pair[1].clone());
+
+                next_level.push(Node::new_internal(hasher, left, right));
+            }
+            nodes = next_level;
+            height += 1;
+        }
+
+        let root = nodes.remove(0);
+
+        MerkleTree {
+            leaves,
+            height: height + 1,
+            root,
+        }
+    }
+
+    /// Returns the height (number of levels) of the tree.
+    pub fn height(&self) -> usize {
+        self.height
+    }
+
+    /// Returns true if the tree has no leaves (should never happen if `new()` was used).
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Returns the number of leaf nodes in the tree.
+    pub fn len(&self) -> usize {
+        self.leaves.len()
+    }
+
+    /// Returns the root node of the tree.
+    pub fn root(&self) -> Node {
+        self.root.clone()
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::hasher::*;
+
+    use super::*;
+
+    #[test]
+    fn test_merkle_tree_with_default_hasher() {
+        let data = &["hello".as_bytes(), "world".as_bytes()];
+        let tree = MerkleTree::new(&DummyHasher, data);
+
+        assert_eq!(tree.height(), 2);
+        assert_eq!(tree.root().hash(), "0xc0ff3");
+    }
+
+    #[test]
+    #[cfg(feature = "sha256")]
+    fn test_merkle_tree_hashing() {
+        let data = &["hello".as_bytes(), "world".as_bytes()];
+        let tree = MerkleTree::new(&SHA256Hasher, data);
+
+        assert_eq!(tree.height(), 2);
+        assert_eq!(
+            tree.root().hash(),
+            "15e178b71fae8849ee562c9cc0d7ea322fba6cd495411329d47234479167cc8b"
+        );
+    }
+
+    #[test]
+    #[cfg(feature = "sha256")]
+    fn test_merkle_tree_single_leaf() {
+        let data = &["hello".as_bytes()];
+        let tree = MerkleTree::new(&SHA256Hasher, data);
+
+        assert_eq!(tree.height(), 2);
+        assert_eq!(tree.len(), 2);
+        assert_eq!(
+            tree.root().hash(),
+            "286d189fda11bf4e906b6973a173009f47ede16532f1bae726223f8ee155d73b"
+        );
+    }
+
+    #[test]
+    #[cfg(feature = "sha256")]
+    fn test_merkle_tree_with_10_elements() {
+        let inputs = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"];
+        let data: Vec<&[u8]> = inputs.iter().map(|s| s.as_bytes()).collect();
+
+        let tree = MerkleTree::new(&SHA256Hasher, &data);
+
+        assert_eq!(tree.height(), 5); // 10 elements padded to 16 → log2(16) + 1 = 5
+
+        // You can print the root hash if you're unsure what it should be:
+        println!("Merkle root hash: {}", tree.root().hash());
+
+        // If you know the expected hash, use:
+        assert_eq!(
+            tree.root().hash(),
+            "9da1ff0dfa79217bdbea9ec96407b1e693646cc493f64059fa27182a37cadf94"
+        );
+    }
+}
-- 
cgit v1.2.3-71-g8e6c