extern crate bloock_smt;
use crate::h256_rocksdb_blake2b::common;
use bloock_merge::hash_algorithms::blake2b::Blake2b;
use bloock_smt::tree::SparseMerkleTree;
use bloock_storage::kv::kv_rocks::RocksDB as Database;
use bloock_types::bytes::h256::H256;
use bloock_storage::kv::KeyValue;

/* add_leaves() ========= ========= =========  */
#[test]
fn test_add_leaves_root() {
    let mut db = common::init_rocksdb("add_leaves_root_smt");
    common::init_tree_2_4(&mut db);
    let mut root_key = [
        122, 252, 138, 54, 248, 253, 151, 142, 83, 210, 35, 173, 157, 102, 32, 117, 35, 213, 168,
        147, 185, 161, 178, 126, 231, 110, 118, 87, 90, 141, 63, 203,
    ];
    let mut smt: SparseMerkleTree<H256, Database, Blake2b> =
        SparseMerkleTree::<H256, Database, Blake2b>::load(root_key, &mut db).unwrap();
    assert!(
        smt.add_leaves(vec![[1; 32], [3; 32]]).is_ok(),
        "Error inserting leaves"
    );
    root_key = [
        247, 96, 160, 255, 87, 220, 171, 242, 100, 95, 251, 247, 89, 2, 87, 248, 178, 40, 14, 42,
        7, 194, 187, 255, 206, 83, 201, 77, 77, 218, 202, 56,
    ];
    let root = smt.get_root().as_ref().unwrap();
    assert_eq!(root, &root_key);
    assert_eq!(
        db.get(&root_key).unwrap().unwrap(),
        vec![
            2u8, 0, 0, 0, 5, 2, 133, 208, 120, 69, 162, 40, 130, 46, 46, 254, 28, 136, 89, 158,
            165, 48, 235, 39, 248, 108, 182, 231, 186, 170, 158, 92, 85, 142, 181, 212, 239, 72, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            4, 4
        ],
        "Root has different value in the database."
    );
    assert_eq!(
        db.get(&[
            133, 208, 120, 69, 162, 40, 130, 46, 46, 254, 28, 136, 89, 158, 165, 48, 235, 39, 248,
            108, 182, 231, 186, 170, 158, 92, 85, 142, 181, 212, 239, 72
        ])
        .unwrap()
        .unwrap(),
        [
            2, 0, 5, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 55, 204, 95, 10, 183, 75, 225, 169, 26, 216, 79, 149, 29,
            195, 120, 173, 46, 167, 91, 31, 187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226,
            120
        ],
        "Node 1_2_3 has different value in the database."
    );
    assert_eq!(
        db.get(&[
            55, 204, 95, 10, 183, 75, 225, 169, 26, 216, 79, 149, 29, 195, 120, 173, 46, 167, 91,
            31, 187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226, 120
        ])
        .unwrap()
        .unwrap(),
        [
            2, 0, 6, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
        ],
        "Node 2_3 has different value in the database."
    );
    assert_eq!(
        db.get(&[1; 32]).unwrap().unwrap(),
        [1, 0, 6],
        "Leaf 1 has different value in the database."
    );
    assert_eq!(
        db.get(&[4; 32]).unwrap().unwrap(),
        [1, 0, 5],
        "Leaf 1 has different value in the database."
    );
    common::delete_folder("add_leaves_root_smt")
}

#[test]
fn test_add_leaves_no_root_leaf() {
    let mut db = common::init_rocksdb("add_leaves_no_root_leaf_smt");
    let smt: SparseMerkleTree<H256, Database, Blake2b> =
        SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, Some(vec![[1; 32]]))
            .expect("Unable to create new SMT.");
    let root = smt.get_root().as_ref().unwrap();
    assert_eq!(root, &[1; 32]);
    assert_eq!(
        db.get(&[1; 32]).expect("Error in DB").unwrap(),
        vec![1, 0, 0]
    );
    common::delete_folder("add_leaves_no_root_leaf_smt")
}

#[test]
fn test_add_leaves_no_root_bulk() {
    let mut db = common::init_rocksdb("add_leaves_no_root_bulk");
    let mut smt: SparseMerkleTree<H256, Database, Blake2b> =
        SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, None).unwrap();
    assert!(
        smt.add_leaves(vec![[1; 32], [2; 32], [3; 32], [4; 32]])
            .is_ok(),
        "Error inserting leaves"
    );
    let root_key = [
        247, 96, 160, 255, 87, 220, 171, 242, 100, 95, 251, 247, 89, 2, 87, 248, 178, 40, 14, 42,
        7, 194, 187, 255, 206, 83, 201, 77, 77, 218, 202, 56,
    ];
    let root = smt.get_root().as_ref().unwrap();
    assert_eq!(root, &root_key);
    assert_eq!(
        db.get(&root_key).unwrap().unwrap(),
        vec![
            2u8, 0, 0, 0, 5, 1, 133, 208, 120, 69, 162, 40, 130, 46, 46, 254, 28, 136, 89, 158,
            165, 48, 235, 39, 248, 108, 182, 231, 186, 170, 158, 92, 85, 142, 181, 212, 239, 72, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            4, 4
        ],
        "Root has different value in the database."
    );
    assert_eq!(
        db.get(&[
            133, 208, 120, 69, 162, 40, 130, 46, 46, 254, 28, 136, 89, 158, 165, 48, 235, 39, 248,
            108, 182, 231, 186, 170, 158, 92, 85, 142, 181, 212, 239, 72
        ])
        .unwrap()
        .unwrap(),
        [
            2, 0, 5, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 55, 204, 95, 10, 183, 75, 225, 169, 26, 216, 79, 149, 29,
            195, 120, 173, 46, 167, 91, 31, 187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226,
            120
        ],
        "Node 1_2_3 has different value in the database."
    );
    assert_eq!(
        db.get(&[
            55, 204, 95, 10, 183, 75, 225, 169, 26, 216, 79, 149, 29, 195, 120, 173, 46, 167, 91,
            31, 187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226, 120
        ])
        .unwrap()
        .unwrap(),
        [
            2, 0, 6, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
        ],
        "Node 2_3 has different value in the database."
    );
    assert_eq!(
        db.get(&[1; 32]).unwrap().unwrap(),
        [1, 0, 6],
        "Leaf 1 has different value in the database."
    );
    assert_eq!(
        db.get(&[4; 32]).unwrap().unwrap(),
        [1, 0, 5],
        "Leaf 1 has different value in the database."
    );
    common::delete_folder("add_leaves_no_root_bulk")
}

#[test]
fn test_add_leaves_bulk_root() {
    let mut db = common::init_rocksdb("add_leaves_bulk_root");

    let mut sparse =
        SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, Some(vec![[2; 32], [4; 32]]))
            .unwrap();

    sparse.add_leaves(vec![[1; 32], [3; 32]]).unwrap();

    let key_1_4: H256 = [
        247, 96, 160, 255, 87, 220, 171, 242, 100, 95, 251, 247, 89, 2, 87, 248, 178, 40, 14, 42,
        7, 194, 187, 255, 206, 83, 201, 77, 77, 218, 202, 56,
    ];
    let value_1_4: Vec<u8> = vec![
        2u8, 0, 0, 0, 5, 2, 133, 208, 120, 69, 162, 40, 130, 46, 46, 254, 28, 136, 89, 158, 165,
        48, 235, 39, 248, 108, 182, 231, 186, 170, 158, 92, 85, 142, 181, 212, 239, 72, 4, 4, 4, 4,
        4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
    ];

    let key_1_3: H256 = [
        133, 208, 120, 69, 162, 40, 130, 46, 46, 254, 28, 136, 89, 158, 165, 48, 235, 39, 248, 108,
        182, 231, 186, 170, 158, 92, 85, 142, 181, 212, 239, 72,
    ];
    let value_1_3: Vec<u8> = vec![
        2u8, 0, 5u8, 0, 1u8, 1u8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 55, 204, 95, 10, 183, 75, 225, 169, 26, 216, 79, 149, 29,
        195, 120, 173, 46, 167, 91, 31, 187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226, 120,
    ];

    let key_2_3: H256 = [
        55, 204, 95, 10, 183, 75, 225, 169, 26, 216, 79, 149, 29, 195, 120, 173, 46, 167, 91, 31,
        187, 141, 101, 53, 137, 34, 143, 106, 45, 167, 226, 120,
    ];
    let value_2_3: Vec<u8> = vec![
        2u8, 0, 6u8, 0, 1u8, 2u8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
    ];

    assert_eq!(
        key_1_4,
        sparse.get_root().unwrap(),
        "Root has unexpected key."
    );

    assert_eq!(
        sparse.get_datasource().get(&key_1_4).unwrap().unwrap(),
        value_1_4,
        "Value difference between root value and expected value in base case with 2 leaves."
    );
    assert_eq!(
        sparse.get_datasource().get(&key_1_3).unwrap().unwrap(),
        value_1_3,
        "Value 1_3"
    );
    assert_eq!(
        sparse.get_datasource().get(&key_2_3).unwrap().unwrap(),
        value_2_3,
        "Value 2_3"
    );
    assert_eq!(
        sparse.get_datasource().get(&[1u8; 32]).unwrap().unwrap(),
        vec![1, 0, 6],
        "Leaf 1"
    );
    assert_eq!(
        sparse.get_datasource().get(&[2u8; 32]).unwrap().unwrap(),
        vec![1, 0, 7],
        "Leaf 2"
    );
    assert_eq!(
        sparse.get_datasource().get(&[3u8; 32]).unwrap().unwrap(),
        vec![1, 0, 7],
        "Leaf 3"
    );
    assert_eq!(
        sparse.get_datasource().get(&[4u8; 32]).unwrap().unwrap(),
        vec![1, 0, 5],
        "Leaf 4"
    );
    common::delete_folder("add_leaves_bulk_root")
}

#[test]
fn test_add_leaves_equal_greater_node() {
    let mut db = common::init_rocksdb("add_leaves_equal_greater");
    common::init_tree_16_17_21_23_64(&mut db);

    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [
            203, 197, 171, 39, 105, 168, 72, 106, 219, 225, 165, 168, 110, 180, 75, 11, 119, 25,
            249, 182, 108, 160, 53, 128, 56, 71, 215, 136, 26, 188, 46, 124,
        ],
        &mut db,
    )
    .unwrap();

    smt.add_leaves(vec![[19; 32], [18; 32]]).unwrap();

    let key_18_19 = [
        254, 175, 138, 202, 188, 25, 18, 17, 250, 83, 44, 20, 135, 126, 89, 100, 9, 193, 95, 50,
        30, 176, 251, 139, 86, 172, 29, 172, 59, 198, 224, 98,
    ];
    let value_18_19: Vec<u8> = vec![
        2u8, 0, 6, 0, 1u8, 18u8, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
        18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19,
        19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
        19, 19,
    ];

    let key_16_19 = [
        9, 58, 39, 206, 156, 24, 76, 57, 216, 225, 205, 69, 228, 12, 178, 33, 37, 22, 211, 130, 26,
        20, 62, 206, 39, 218, 146, 78, 137, 181, 166, 144,
    ];
    let value_16_19: Vec<u8> = vec![
        2u8, 0, 5, 0, 1u8, 16u8, 216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242,
        115, 144, 90, 222, 43, 170, 181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41,
        254, 175, 138, 202, 188, 25, 18, 17, 250, 83, 44, 20, 135, 126, 89, 100, 9, 193, 95, 50,
        30, 176, 251, 139, 86, 172, 29, 172, 59, 198, 224, 98,
    ];

    let key_16_23 = [
        125, 80, 39, 107, 108, 36, 146, 181, 136, 69, 60, 53, 143, 147, 137, 220, 136, 23, 177, 72,
        135, 120, 236, 18, 3, 213, 110, 146, 151, 72, 81, 202,
    ];
    let value_16_23: Vec<u8> = vec![
        2u8, 0, 1, 0, 4u8, 16u8, 9, 58, 39, 206, 156, 24, 76, 57, 216, 225, 205, 69, 228, 12, 178,
        33, 37, 22, 211, 130, 26, 20, 62, 206, 39, 218, 146, 78, 137, 181, 166, 144, 29, 28, 117,
        19, 193, 4, 119, 184, 34, 211, 116, 134, 231, 0, 248, 78, 17, 225, 23, 40, 9, 4, 114, 96,
        116, 87, 170, 228, 3, 87, 184, 203,
    ];

    let key_16_64 = [
        39u8, 133, 28, 191, 142, 131, 194, 12, 232, 43, 171, 199, 198, 84, 241, 85, 240, 219, 224,
        56, 176, 58, 193, 221, 141, 126, 24, 53, 58, 146, 84, 210,
    ];
    let value_16_64: Vec<u8> = vec![
        2u8, 0, 0, 0, 1, 16, 125, 80, 39, 107, 108, 36, 146, 181, 136, 69, 60, 53, 143, 147, 137,
        220, 136, 23, 177, 72, 135, 120, 236, 18, 3, 213, 110, 146, 151, 72, 81, 202, 64, 64, 64,
        64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
        64, 64, 64, 64, 64, 64,
    ];

    let key_16_17 = [
        216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242, 115, 144, 90, 222, 43, 170,
        181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41,
    ];

    let value_16_17 = vec![
        2u8, 0, 6, 0, 1, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
        16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
        17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
        17,
    ];

    let key_21_23 = [
        29, 28, 117, 19, 193, 4, 119, 184, 34, 211, 116, 134, 231, 0, 248, 78, 17, 225, 23, 40, 9,
        4, 114, 96, 116, 87, 170, 228, 3, 87, 184, 203,
    ];
    let value_21_23 = vec![
        2u8, 0, 5, 0, 1, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
        21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 23, 23, 23, 23, 23, 23, 23, 23,
        23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
        23,
    ];

    let value_18 = vec![1, 0, 7];
    let value_19 = vec![1, 0, 7];

    assert_eq!(
        smt.get_root().unwrap(),
        key_16_64,
        "Keys difference between merged key and expected in base case with 2 leaves."
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_64).unwrap().unwrap(),
        value_16_64,
        "Value difference between merged value and expected in root."
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_17).unwrap().unwrap(),
        value_16_17,
        "16-17"
    );
    assert_eq!(
        smt.get_datasource().get(&key_18_19).unwrap().unwrap(),
        value_18_19,
        "18-19"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_19).unwrap().unwrap(),
        value_16_19,
        "16-19"
    );
    assert_eq!(
        smt.get_datasource().get(&key_21_23).unwrap().unwrap(),
        value_21_23,
        "21-23"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_23).unwrap().unwrap(),
        value_16_23,
        "16-23"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_64).unwrap().unwrap(),
        value_16_64,
        "16-23"
    );
    assert_eq!(
        smt.get_datasource().get(&[18; 32]).unwrap().unwrap(),
        value_18,
        ""
    );
    assert_eq!(
        smt.get_datasource().get(&[19; 32]).unwrap().unwrap(),
        value_19,
        ""
    );
    common::delete_folder("add_leaves_equal_greater")
}

#[test]
fn test_add_leaves_equal_greater_lower_leaf() {
    let mut db = common::init_rocksdb("add_leaves_equal_greater_lower_leaf");
    common::init_tree_16_17_21_23_64(&mut db);

    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [
            203, 197, 171, 39, 105, 168, 72, 106, 219, 225, 165, 168, 110, 180, 75, 11, 119, 25,
            249, 182, 108, 160, 53, 128, 56, 71, 215, 136, 26, 188, 46, 124,
        ],
        &mut db,
    )
    .unwrap();

    smt.add_leaves(vec![[20; 32], [22; 32]]).unwrap();

    let key_16_17 = [
        216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242, 115, 144, 90, 222, 43, 170,
        181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41,
    ];
    let value_16_17: Vec<u8> = vec![
        2u8, 0, 5, 0, 2, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
        16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
        17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
        17,
    ];

    let key_20_21 = [
        165, 79, 132, 220, 212, 21, 88, 124, 253, 135, 176, 188, 73, 104, 215, 222, 20, 80, 151,
        227, 93, 149, 121, 13, 93, 25, 232, 20, 72, 118, 124, 106,
    ];
    let value_20_21: Vec<u8> = vec![
        2u8, 0, 6, 0, 1, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
        20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21,
        21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
        21,
    ];

    let key_22_23 = [
        249, 35, 194, 248, 56, 74, 25, 129, 77, 241, 27, 193, 49, 85, 134, 161, 240, 254, 39, 17,
        149, 131, 110, 174, 170, 68, 3, 16, 211, 251, 169, 69,
    ];
    let value_22_23: Vec<u8> = vec![
        2u8, 0, 6, 0, 1, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
        22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
        23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
        23,
    ];

    let key_20_23 = [
        67, 138, 11, 210, 73, 29, 70, 254, 187, 235, 176, 163, 56, 100, 148, 235, 123, 163, 226,
        241, 101, 21, 118, 151, 194, 29, 165, 44, 227, 163, 16, 43,
    ];
    let value_20_23: Vec<u8> = vec![
        2u8, 0, 5, 0, 1, 21, 165, 79, 132, 220, 212, 21, 88, 124, 253, 135, 176, 188, 73, 104, 215,
        222, 20, 80, 151, 227, 93, 149, 121, 13, 93, 25, 232, 20, 72, 118, 124, 106, 249, 35, 194,
        248, 56, 74, 25, 129, 77, 241, 27, 193, 49, 85, 134, 161, 240, 254, 39, 17, 149, 131, 110,
        174, 170, 68, 3, 16, 211, 251, 169, 69,
    ];

    let key_16_23 = [
        225, 26, 0, 195, 73, 122, 52, 183, 65, 228, 122, 112, 134, 100, 139, 186, 28, 178, 45, 92,
        232, 133, 51, 85, 64, 106, 10, 3, 101, 38, 234, 65,
    ];
    let value_16_23: Vec<u8> = vec![
        2u8, 0, 1, 0, 4, 16, 216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242, 115,
        144, 90, 222, 43, 170, 181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41, 67,
        138, 11, 210, 73, 29, 70, 254, 187, 235, 176, 163, 56, 100, 148, 235, 123, 163, 226, 241,
        101, 21, 118, 151, 194, 29, 165, 44, 227, 163, 16, 43,
    ];

    let key_16_64 = [
        200, 6, 197, 162, 16, 51, 195, 217, 178, 78, 33, 187, 115, 166, 48, 128, 96, 87, 211, 179,
        193, 238, 201, 15, 126, 62, 125, 40, 173, 0, 38, 182,
    ];

    let value_16_64 = vec![
        2, 0, 0, 0, 1, 16, 225, 26, 0, 195, 73, 122, 52, 183, 65, 228, 122, 112, 134, 100, 139,
        186, 28, 178, 45, 92, 232, 133, 51, 85, 64, 106, 10, 3, 101, 38, 234, 65, 64, 64, 64, 64,
        64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
        64, 64, 64, 64, 64,
    ];

    let leaf20 = vec![1, 0, 7];

    let leaf22 = vec![1, 0, 7];

    assert_eq!(
        smt.get_root().unwrap(),
        key_16_64,
        "Keys difference between merged key and expected in base case with 2 leaves."
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_64).unwrap().unwrap(),
        value_16_64,
        "root value difference"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_17).unwrap().unwrap(),
        value_16_17,
        "G"
    );
    assert_eq!(
        smt.get_datasource().get(&key_20_21).unwrap().unwrap(),
        value_20_21,
        "20-21"
    );
    assert_eq!(
        smt.get_datasource().get(&key_22_23).unwrap().unwrap(),
        value_22_23,
        "22-23"
    );
    assert_eq!(
        smt.get_datasource().get(&key_20_23).unwrap().unwrap(),
        value_20_23,
        "20-23"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_17).unwrap().unwrap(),
        value_16_17,
        "16-17"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_23).unwrap().unwrap(),
        value_16_23,
        "16-23"
    );
    assert_eq!(
        smt.get_datasource().get(&[20; 32]).unwrap().unwrap(),
        leaf20,
        ""
    );
    assert_eq!(
        smt.get_datasource().get(&[22; 32]).unwrap().unwrap(),
        leaf22,
        ""
    );
    common::delete_folder("add_leaves_equal_greater_lower_leaf");
}

#[test]
fn test_add_leaves_equal_greater_lower_combined() {
    let mut db = common::init_rocksdb("add_leaves_equal_greater_lower_combined");
    common::init_tree_16_17_21_23_64(&mut db);

    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [
            203, 197, 171, 39, 105, 168, 72, 106, 219, 225, 165, 168, 110, 180, 75, 11, 119, 25,
            249, 182, 108, 160, 53, 128, 56, 71, 215, 136, 26, 188, 46, 124,
        ],
        &mut db,
    )
    .unwrap();

    smt.add_leaves(vec![[19; 32], [18; 32], [20; 32], [22; 32]])
        .unwrap();

    let key_18_19 = [
        254, 175, 138, 202, 188, 25, 18, 17, 250, 83, 44, 20, 135, 126, 89, 100, 9, 193, 95, 50,
        30, 176, 251, 139, 86, 172, 29, 172, 59, 198, 224, 98,
    ];
    let value_18_19: Vec<u8> = vec![
        2u8, 0, 6, 0, 1u8, 18u8, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
        18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19,
        19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
        19, 19,
    ];

    let key_16_19 = [
        9, 58, 39, 206, 156, 24, 76, 57, 216, 225, 205, 69, 228, 12, 178, 33, 37, 22, 211, 130, 26,
        20, 62, 206, 39, 218, 146, 78, 137, 181, 166, 144,
    ];
    let value_16_19: Vec<u8> = vec![
        2u8, 0, 5, 0, 1u8, 16u8, 216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242,
        115, 144, 90, 222, 43, 170, 181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41,
        254, 175, 138, 202, 188, 25, 18, 17, 250, 83, 44, 20, 135, 126, 89, 100, 9, 193, 95, 50,
        30, 176, 251, 139, 86, 172, 29, 172, 59, 198, 224, 98,
    ];

    let key_20_21 = [
        165, 79, 132, 220, 212, 21, 88, 124, 253, 135, 176, 188, 73, 104, 215, 222, 20, 80, 151,
        227, 93, 149, 121, 13, 93, 25, 232, 20, 72, 118, 124, 106,
    ];
    let value_20_21: Vec<u8> = vec![
        2u8, 0, 6, 0, 1, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
        20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21,
        21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
        21,
    ];

    let key_22_23 = [
        249, 35, 194, 248, 56, 74, 25, 129, 77, 241, 27, 193, 49, 85, 134, 161, 240, 254, 39, 17,
        149, 131, 110, 174, 170, 68, 3, 16, 211, 251, 169, 69,
    ];
    let value_22_23: Vec<u8> = vec![
        2u8, 0, 6, 0, 1, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
        22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
        23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
        23,
    ];

    let key_20_23 = [
        67, 138, 11, 210, 73, 29, 70, 254, 187, 235, 176, 163, 56, 100, 148, 235, 123, 163, 226,
        241, 101, 21, 118, 151, 194, 29, 165, 44, 227, 163, 16, 43,
    ];
    let value_20_23: Vec<u8> = vec![
        2u8, 0, 5, 0, 1, 21, 165, 79, 132, 220, 212, 21, 88, 124, 253, 135, 176, 188, 73, 104, 215,
        222, 20, 80, 151, 227, 93, 149, 121, 13, 93, 25, 232, 20, 72, 118, 124, 106, 249, 35, 194,
        248, 56, 74, 25, 129, 77, 241, 27, 193, 49, 85, 134, 161, 240, 254, 39, 17, 149, 131, 110,
        174, 170, 68, 3, 16, 211, 251, 169, 69,
    ];

    let key_16_23 = [
        170, 56, 2, 151, 51, 191, 250, 117, 199, 230, 204, 2, 33, 177, 66, 69, 66, 234, 186, 15,
        251, 71, 153, 147, 28, 217, 76, 69, 61, 162, 81, 33,
    ];
    let value_16_23: Vec<u8> = vec![
        2u8, 0, 1, 0, 4u8, 16, 9, 58, 39, 206, 156, 24, 76, 57, 216, 225, 205, 69, 228, 12, 178,
        33, 37, 22, 211, 130, 26, 20, 62, 206, 39, 218, 146, 78, 137, 181, 166, 144, 67, 138, 11,
        210, 73, 29, 70, 254, 187, 235, 176, 163, 56, 100, 148, 235, 123, 163, 226, 241, 101, 21,
        118, 151, 194, 29, 165, 44, 227, 163, 16, 43,
    ];

    let key_16_64 = [
        167, 210, 129, 92, 191, 178, 91, 54, 174, 110, 165, 234, 129, 24, 39, 209, 164, 41, 219,
        75, 106, 251, 86, 226, 61, 255, 143, 192, 208, 47, 90, 25,
    ];
    let value_16_64: Vec<u8> = vec![
        2u8, 0, 0, 0, 1, 16, 170, 56, 2, 151, 51, 191, 250, 117, 199, 230, 204, 2, 33, 177, 66, 69,
        66, 234, 186, 15, 251, 71, 153, 147, 28, 217, 76, 69, 61, 162, 81, 33, 64, 64, 64, 64, 64,
        64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
        64, 64, 64, 64,
    ];

    let key_16_17 = [
        216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242, 115, 144, 90, 222, 43, 170,
        181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41,
    ];

    let value_16_17 = vec![
        2u8, 0, 6, 0, 1, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
        16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
        17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
        17,
    ];

    let value_18 = vec![1, 0, 7];
    let value_19 = vec![1, 0, 7];

    let leaf20 = vec![1, 0, 7];

    let leaf22 = vec![1, 0, 7];

    assert_eq!(
        smt.get_root().unwrap(),
        key_16_64,
        "Keys difference between merged key and expected in base case with 2 leaves."
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_64).unwrap().unwrap(),
        value_16_64,
        "Value difference between merged value and expected in root."
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_17).unwrap().unwrap(),
        value_16_17,
        "16-17"
    );
    assert_eq!(
        smt.get_datasource().get(&key_18_19).unwrap().unwrap(),
        value_18_19,
        "18-19"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_19).unwrap().unwrap(),
        value_16_19,
        "16-19"
    );
    assert_eq!(
        smt.get_datasource().get(&key_20_21).unwrap().unwrap(),
        value_20_21,
        "21-22"
    );
    assert_eq!(
        smt.get_datasource().get(&key_20_23).unwrap().unwrap(),
        value_20_23,
        "20-23"
    );
    assert_eq!(
        smt.get_datasource().get(&key_22_23).unwrap().unwrap(),
        value_22_23,
        "21-22"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_23).unwrap().unwrap(),
        value_16_23,
        "16-23"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_64).unwrap().unwrap(),
        value_16_64,
        "16-23"
    );
    assert_eq!(
        smt.get_datasource().get(&[18; 32]).unwrap().unwrap(),
        value_18,
        "18"
    );
    assert_eq!(
        smt.get_datasource().get(&[19; 32]).unwrap().unwrap(),
        value_19,
        "19"
    );
    assert_eq!(
        smt.get_datasource().get(&[20; 32]).unwrap().unwrap(),
        leaf20,
        "20"
    );
    assert_eq!(
        smt.get_datasource().get(&[22; 32]).unwrap().unwrap(),
        leaf22,
        "22"
    );

    common::delete_folder("add_leaves_equal_greater_lower_combined");
}

#[test]
fn test_add_leaves_lower_node() {
    let mut db = common::init_rocksdb("add_leaves_lower");
    common::init_tree_16_17_21_23_64(&mut db);

    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [
            203, 197, 171, 39, 105, 168, 72, 106, 219, 225, 165, 168, 110, 180, 75, 11, 119, 25,
            249, 182, 108, 160, 53, 128, 56, 71, 215, 136, 26, 188, 46, 124,
        ],
        &mut db,
    )
    .unwrap();

    smt.add_leaves(vec![[2; 32], [4; 32], [5; 32], [7; 32]])
        .unwrap();

    let key_16_23 = [
        163, 168, 111, 103, 194, 21, 246, 188, 40, 182, 250, 229, 27, 215, 241, 7, 220, 174, 149,
        245, 117, 2, 222, 141, 72, 90, 114, 75, 114, 247, 244, 151,
    ];

    // base

    let value_16_23: Vec<u8> = vec![
        2u8, 0, 3, 0, 2, 16, 216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242, 115,
        144, 90, 222, 43, 170, 181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41, 29,
        28, 117, 19, 193, 4, 119, 184, 34, 211, 116, 134, 231, 0, 248, 78, 17, 225, 23, 40, 9, 4,
        114, 96, 116, 87, 170, 228, 3, 87, 184, 203,
    ];

    let key_4_5 = [
        174, 66, 21, 33, 54, 225, 22, 162, 62, 106, 212, 114, 63, 47, 98, 43, 46, 151, 34, 213,
        120, 170, 133, 198, 252, 110, 253, 209, 199, 7, 118, 20,
    ];
    let value_4_5: Vec<u8> = vec![
        2u8, 0, 6, 0, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
        4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
        5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    ];

    let key_4_7 = [
        107, 192, 221, 173, 4, 39, 143, 248, 125, 68, 76, 79, 210, 118, 27, 181, 108, 238, 245, 74,
        212, 231, 87, 227, 92, 107, 155, 211, 217, 106, 227, 128,
    ];
    let value_4_7: Vec<u8> = vec![
        2u8, 0, 5, 0, 1, 4, 174, 66, 21, 33, 54, 225, 22, 162, 62, 106, 212, 114, 63, 47, 98, 43,
        46, 151, 34, 213, 120, 170, 133, 198, 252, 110, 253, 209, 199, 7, 118, 20, 7, 7, 7, 7, 7,
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    ];

    let key_2_7 = [
        154, 98, 94, 248, 69, 233, 88, 219, 219, 173, 18, 103, 148, 93, 37, 96, 14, 163, 246, 12,
        189, 101, 101, 93, 193, 195, 200, 88, 244, 164, 16, 41,
    ];
    let value_2_7: Vec<u8> = vec![
        2u8, 0, 3, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 107, 192, 221, 173, 4, 39, 143, 248, 125, 68, 76, 79, 210, 118, 27,
        181, 108, 238, 245, 74, 212, 231, 87, 227, 92, 107, 155, 211, 217, 106, 227, 128,
    ];

    let key_2_23 = [
        157, 4, 253, 44, 102, 38, 115, 237, 206, 47, 50, 40, 205, 227, 81, 239, 186, 236, 130, 23,
        250, 206, 148, 128, 143, 99, 146, 114, 26, 202, 216, 63,
    ];
    let value_2_23: Vec<u8> = vec![
        2u8, 0, 1, 0, 2, 2, 154, 98, 94, 248, 69, 233, 88, 219, 219, 173, 18, 103, 148, 93, 37, 96,
        14, 163, 246, 12, 189, 101, 101, 93, 193, 195, 200, 88, 244, 164, 16, 41, 163, 168, 111,
        103, 194, 21, 246, 188, 40, 182, 250, 229, 27, 215, 241, 7, 220, 174, 149, 245, 117, 2,
        222, 141, 72, 90, 114, 75, 114, 247, 244, 151,
    ];

    let key_2_64 = [
        164, 86, 43, 68, 136, 236, 253, 232, 248, 202, 238, 137, 24, 30, 116, 212, 251, 45, 61,
        150, 134, 74, 153, 31, 3, 182, 3, 23, 40, 92, 243, 247,
    ];
    let value_2_64: Vec<u8> = vec![
        2u8, 0, 0, 0, 1, 16, 157, 4, 253, 44, 102, 38, 115, 237, 206, 47, 50, 40, 205, 227, 81,
        239, 186, 236, 130, 23, 250, 206, 148, 128, 143, 99, 146, 114, 26, 202, 216, 63, 64, 64,
        64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
        64, 64, 64, 64, 64, 64, 64,
    ];

    let leaf2 = vec![1, 0, 5];
    let leaf4 = vec![1, 0, 7];
    let leaf5 = vec![1, 0, 7];
    let leaf7 = vec![1, 0, 6];

    assert_eq!(
        smt.get_root().unwrap(),
        key_2_64,
        "Keys difference between merged key and expected in base case with 2 leaves."
    );
    assert_eq!(
        smt.get_datasource().get(&key_2_64).unwrap().unwrap(),
        value_2_64,
        "root value difference"
    );
    assert_eq!(
        smt.get_datasource().get(&key_2_23).unwrap().unwrap(),
        value_2_23,
        "A"
    );
    assert_eq!(
        smt.get_datasource().get(&key_2_7).unwrap().unwrap(),
        value_2_7,
        "B"
    );
    assert_eq!(
        smt.get_datasource().get(&key_4_7).unwrap().unwrap(),
        value_4_7,
        "C"
    );
    assert_eq!(
        smt.get_datasource().get(&key_4_5).unwrap().unwrap(),
        value_4_5,
        "D"
    );
    assert_eq!(
        smt.get_datasource().get(&[2; 32]).unwrap().unwrap(),
        leaf2,
        "E"
    );
    assert_eq!(
        smt.get_datasource().get(&[4; 32]).unwrap().unwrap(),
        leaf4,
        "F"
    );
    assert_eq!(
        smt.get_datasource().get(&[5; 32]).unwrap().unwrap(),
        leaf5,
        "G"
    );
    assert_eq!(
        smt.get_datasource().get(&[7; 32]).unwrap().unwrap(),
        leaf7,
        ""
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_23).unwrap().unwrap(),
        value_16_23,
        ""
    );

    common::delete_folder("add_leaves_lower");
}

#[test]
fn test_add_leaves_greater_node() {
    let mut db = common::init_rocksdb("add_leaves_greater_node");
    common::init_tree_16_17_21_23_64(&mut db);

    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [
            203, 197, 171, 39, 105, 168, 72, 106, 219, 225, 165, 168, 110, 180, 75, 11, 119, 25,
            249, 182, 108, 160, 53, 128, 56, 71, 215, 136, 26, 188, 46, 124,
        ],
        &mut db,
    )
    .unwrap();

    smt.add_leaves(vec![[36; 32], [38; 32], [40; 32]]).unwrap();
    let key_16_23 = [
        163, 168, 111, 103, 194, 21, 246, 188, 40, 182, 250, 229, 27, 215, 241, 7, 220, 174, 149,
        245, 117, 2, 222, 141, 72, 90, 114, 75, 114, 247, 244, 151,
    ];
    let value_16_23: Vec<u8> = vec![
        2u8, 0, 2, 0, 3, 16, 216, 160, 227, 86, 193, 131, 252, 204, 119, 250, 167, 151, 242, 115,
        144, 90, 222, 43, 170, 181, 116, 169, 138, 243, 20, 255, 122, 207, 123, 244, 211, 41, 29,
        28, 117, 19, 193, 4, 119, 184, 34, 211, 116, 134, 231, 0, 248, 78, 17, 225, 23, 40, 9, 4,
        114, 96, 116, 87, 170, 228, 3, 87, 184, 203,
    ];

    let key_36_38 = [
        237, 64, 188, 119, 101, 29, 186, 142, 4, 116, 47, 58, 175, 61, 162, 226, 129, 18, 236, 159,
        126, 177, 207, 219, 96, 4, 10, 119, 106, 31, 0, 213,
    ];
    let value_36_38: Vec<u8> = vec![
        2u8, 0, 4, 0, 2, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
        36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 38, 38, 38, 38, 38, 38, 38,
        38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38,
        38,
    ];

    let key_36_40 = [
        150, 158, 184, 55, 20, 183, 161, 61, 70, 79, 122, 109, 135, 245, 86, 138, 170, 48, 74, 149,
        212, 209, 253, 214, 181, 120, 163, 49, 234, 217, 179, 204,
    ];
    let value_36_40: Vec<u8> = vec![
        2u8, 0, 2, 0, 2, 36, 237, 64, 188, 119, 101, 29, 186, 142, 4, 116, 47, 58, 175, 61, 162,
        226, 129, 18, 236, 159, 126, 177, 207, 219, 96, 4, 10, 119, 106, 31, 0, 213, 40, 40, 40,
        40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
        40, 40, 40, 40, 40, 40,
    ];

    let key_16_40 = [
        83, 27, 202, 112, 78, 24, 221, 210, 70, 57, 21, 174, 83, 192, 78, 198, 18, 163, 66, 218,
        253, 209, 190, 205, 165, 228, 43, 40, 63, 117, 91, 14,
    ];
    let value_16_40: Vec<u8> = vec![
        2u8, 0, 1, 0, 1, 16, 163, 168, 111, 103, 194, 21, 246, 188, 40, 182, 250, 229, 27, 215,
        241, 7, 220, 174, 149, 245, 117, 2, 222, 141, 72, 90, 114, 75, 114, 247, 244, 151, 150,
        158, 184, 55, 20, 183, 161, 61, 70, 79, 122, 109, 135, 245, 86, 138, 170, 48, 74, 149, 212,
        209, 253, 214, 181, 120, 163, 49, 234, 217, 179, 204,
    ];

    let key_16_64 = [
        35, 209, 213, 105, 108, 19, 197, 99, 187, 231, 253, 55, 211, 5, 220, 28, 198, 20, 52, 38,
        83, 125, 34, 0, 142, 214, 168, 100, 28, 144, 1, 49,
    ];
    let value_16_64: Vec<u8> = vec![
        2u8, 0, 0, 0, 1, 16, 83, 27, 202, 112, 78, 24, 221, 210, 70, 57, 21, 174, 83, 192, 78, 198,
        18, 163, 66, 218, 253, 209, 190, 205, 165, 228, 43, 40, 63, 117, 91, 14, 64, 64, 64, 64,
        64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
        64, 64, 64, 64, 64,
    ];

    let leaf36 = vec![1, 0, 6];
    let leaf38 = vec![1, 0, 6];
    let leaf40 = vec![1, 0, 4];

    assert_eq!(
        smt.get_root().unwrap(),
        key_16_64,
        "Keys difference between merged key and expected in base case with 2 leaves."
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_64).unwrap().unwrap(),
        value_16_64,
        "root value difference"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_40).unwrap().unwrap(),
        value_16_40,
        "A"
    );
    assert_eq!(
        smt.get_datasource().get(&key_16_23).unwrap().unwrap(),
        value_16_23,
        "B"
    );
    assert_eq!(
        smt.get_datasource().get(&key_36_40).unwrap().unwrap(),
        value_36_40,
        "C"
    );
    assert_eq!(
        smt.get_datasource().get(&key_36_38).unwrap().unwrap(),
        value_36_38,
        "D"
    );
    assert_eq!(
        smt.get_datasource().get(&[36; 32]).unwrap().unwrap(),
        leaf36,
        "E"
    );
    assert_eq!(
        smt.get_datasource().get(&[38; 32]).unwrap().unwrap(),
        leaf38,
        "F"
    );
    assert_eq!(
        smt.get_datasource().get(&[40; 32]).unwrap().unwrap(),
        leaf40,
        ""
    );
    common::delete_folder("add_leaves_greater_node");
}

#[test]
fn test_add_leaves_moving_root_as_with_rollback(){
    let mut db = common::init_rocksdb("add_leaves_moving_root_as_with_rollback");
    let leaf0_value = vec![1u8, 0, 0];
    db.put(&[0u8;32], &leaf0_value);
    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [0u8;32],
        &mut db,
    )
        .unwrap();
    smt.add_leaves(vec![[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]]).unwrap();
    smt.add_leaves(vec![[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]).unwrap();
    drop(smt);

    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [0u8;32],
        &mut db,
    )
        .unwrap();

    smt.add_leaves(vec![[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]]).unwrap();

    common::delete_folder("add_leaves_moving_root_as_with_rollback");
}

#[test]
fn test_add_leaves_moving_leaf_as_with_rollback(){
    let mut db = common::init_rocksdb("add_leaves_moving_leaf_as_with_rollback");
    let leaf0_value = vec![1u8, 0, 0];
    db.put(&[0u8;32], &leaf0_value);
    db.put(&[255u8;32], &leaf0_value);
    db.put(&[69;32], &vec![0, 0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255,
                           255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
                           255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255]);
    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [69u8;32],
        &mut db,
    )
        .unwrap();
    smt.add_leaves(vec![[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]]).unwrap();
    smt.add_leaves(vec![[0u8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]).unwrap();
    drop(smt);

    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::load(
        [69u8;32],
        &mut db,
    )
        .unwrap();
    smt.add_leaves(vec![[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]]).unwrap();
    drop(smt);

    common::delete_folder("add_leaves_moving_leaf_as_with_rollback");
}

/* goMAAAD() ========= ========= =========  */

#[test]
//#[ignore]
fn test_full_go_mad() {
    pub use hex;
    use rand::Rng;
    use std::convert::TryInto;
    let mut rng = rand::thread_rng();
    let charset: &[u8] = b"ABCDEF0123456789";
    let n_iterations: usize = 10;
    let n_insertions: usize = 10;
    let n_leaves_per_ins: usize = 10;
    for _ in 0..n_iterations {
        let mut leaves_all = vec![];
        let mut db = common::init_rocksdb("full_go_mad");
        let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, None).unwrap();
        for i in 0..n_insertions {
            let mut leaves: Vec<H256> = Vec::<H256>::new();
            for _ in 0..n_leaves_per_ins {
                let leaf: [u8; 32] = hex::decode(
                    (0..64)
                        .map(|_| {
                            let idx = rng.gen_range(0, charset.len());
                            charset[idx] as char
                        })
                        .collect::<String>(),
                )
                .unwrap()[0..32]
                    .try_into()
                    .expect("Impossible error!");

                leaves.push(leaf);
                leaves_all.push(leaf);
            }

            println!("\n({:?}) All leaves: {:?}", i, leaves_all);

            println!("\nAdd leaves");
            match smt.add_leaves(leaves.clone()) {
                Ok(_) => {}
                Err(e) => panic!("{:?} => {:?}", e.to_string(), i),
            }

            println!("Leaves proof");
            let proof = match smt.get_multiproof(leaves) {
                Ok(p) => p,
                Err(e) => panic!(e.to_string()),
            };

            println!("Leaves verify");
            assert_eq!(proof.verify(&smt.get_root().unwrap()), true, "falserino");

            println!("All leaves proof");
            let proof = match smt.get_multiproof(leaves_all.clone()) {
                Ok(p) => p,
                Err(e) => panic!(e.to_string()),
            };

            println!("All leaves verify\n");
            assert_eq!(proof.verify(&smt.get_root().unwrap()), true, "false");
        }

        common::delete_folder("full_go_mad");
    }
}

#[test]
fn test_debug_gomad_1() {
    let mut db = common::init_rocksdb("debug_gomad");
    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, None).unwrap();
    let add_leaves_result = smt.add_leaves(vec![
        [
            222, 158, 7, 230, 21, 214, 163, 217, 187, 134, 106, 95, 94, 109, 206, 199, 97, 223, 46,
            216, 193, 249, 88, 240, 81, 203, 170, 72, 160, 78, 145, 54,
        ],
        [
            199, 34, 213, 223, 85, 137, 24, 27, 113, 148, 198, 129, 1, 233, 240, 50, 94, 99, 126,
            7, 81, 101, 121, 213, 160, 239, 78, 117, 240, 135, 233, 84,
        ],
    ]);
    assert!(
        add_leaves_result.is_ok(),
        "Error adding the first 2 leaves..."
    );
    assert!(
        smt.add_leaves(vec![
            [
                187, 183, 141, 168, 35, 74, 225, 139, 175, 3, 130, 205, 171, 179, 224, 221, 238,
                62, 48, 229, 74, 56, 94, 22, 251, 115, 129, 77, 219, 70, 27, 51
            ],
            [
                211, 13, 242, 75, 65, 171, 225, 251, 124, 97, 241, 104, 190, 21, 228, 245, 243,
                130, 159, 5, 124, 41, 11, 239, 77, 4, 63, 79, 102, 231, 247, 134
            ]
        ])
        .is_ok(),
        "Error adding the second 2 leaves"
    );
    common::delete_folder("debug_gomad");
}

#[test]
fn test_debug_gomad_2() {
    let mut db = common::init_rocksdb("debug_gomad_2");
    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, None).unwrap();
    assert!(
        smt.add_leaves(vec![
            [
                72, 171, 137, 91, 139, 222, 210, 198, 201, 98, 229, 25, 1, 123, 223, 135, 77, 29,
                106, 158, 204, 198, 208, 115, 31, 35, 19, 81, 102, 61, 26, 141
            ],
            [
                72, 69, 113, 162, 52, 157, 209, 73, 182, 30, 210, 30, 45, 247, 232, 191, 60, 8, 82,
                222, 128, 119, 7, 105, 217, 35, 166, 80, 24, 40, 167, 117
            ]
        ])
        .is_ok(),
        "Error adding the second 2 leaves"
    );
    common::delete_folder("debug_gomad_2");
}

#[test]
fn test_debug_gomad_3() {
    let mut db = common::init_rocksdb("debug_gomad_3");
    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, None).unwrap();
    let all_leaves = vec![
        [
            44, 136, 77, 73, 132, 207, 181, 118, 237, 175, 174, 107, 199, 37, 71, 250, 207, 221,
            246, 30, 145, 113, 179, 165, 238, 110, 180, 214, 230, 140, 148, 229,
        ],
        [
            44, 53, 46, 154, 71, 99, 92, 28, 31, 48, 156, 63, 160, 206, 0, 145, 41, 181, 203, 90,
            70, 21, 164, 68, 166, 178, 94, 117, 173, 251, 65, 185,
        ],
    ];
    assert!(
        smt.add_leaves(all_leaves.clone()).is_ok(),
        "Error adding the first 2 leaves."
    );
    println!("All leaves proof");
    let proof = smt
        .get_multiproof(all_leaves)
        .expect("Error getting multiproof.");

    println!("All leaves verify\n");
    assert_eq!(proof.verify(&smt.get_root().unwrap()), true, "false");
    common::delete_folder("debug_gomad_3");
}

#[test]
fn test_debug_gomad_4() {
    let mut db = common::init_rocksdb("debug_gomad_4");
    let mut smt = SparseMerkleTree::<H256, Database, Blake2b>::new(&mut db, None).unwrap();
    let all_leaves = vec![
        [
            146, 24, 214, 150, 198, 156, 6, 36, 194, 6, 91, 70, 123, 222, 208, 172, 170, 196, 77,
            107, 19, 89, 4, 171, 222, 13, 22, 90, 224, 80, 48, 159,
        ],
        [
            137, 68, 96, 83, 56, 167, 214, 125, 33, 235, 141, 193, 223, 123, 247, 97, 25, 130, 157,
            201, 202, 255, 52, 50, 52, 60, 221, 153, 210, 194, 38, 129,
        ],
        [
            146, 117, 244, 103, 45, 14, 0, 229, 126, 6, 2, 24, 250, 139, 240, 12, 220, 237, 245,
            101, 53, 243, 129, 21, 132, 118, 83, 72, 24, 156, 17, 5,
        ],
        [
            217, 86, 86, 233, 10, 10, 201, 17, 239, 151, 26, 135, 193, 161, 160, 154, 34, 149, 5,
            20, 203, 238, 88, 198, 172, 230, 26, 85, 153, 28, 146, 22,
        ],
    ];
    assert!(
        smt.add_leaves(vec![
            [
                146, 24, 214, 150, 198, 156, 6, 36, 194, 6, 91, 70, 123, 222, 208, 172, 170, 196,
                77, 107, 19, 89, 4, 171, 222, 13, 22, 90, 224, 80, 48, 159,
            ],
            [
                137, 68, 96, 83, 56, 167, 214, 125, 33, 235, 141, 193, 223, 123, 247, 97, 25, 130,
                157, 201, 202, 255, 52, 50, 52, 60, 221, 153, 210, 194, 38, 129,
            ]
        ])
        .is_ok(),
        "Error adding the first 2 leaves."
    );
    assert!(
        smt.add_leaves(vec![
            [
                146, 117, 244, 103, 45, 14, 0, 229, 126, 6, 2, 24, 250, 139, 240, 12, 220, 237,
                245, 101, 53, 243, 129, 21, 132, 118, 83, 72, 24, 156, 17, 5,
            ],
            [
                217, 86, 86, 233, 10, 10, 201, 17, 239, 151, 26, 135, 193, 161, 160, 154, 34, 149,
                5, 20, 203, 238, 88, 198, 172, 230, 26, 85, 153, 28, 146, 22,
            ]
        ])
        .is_ok(),
        "Error adding the last 2 leaves."
    );
    println!("All leaves proof");
    let proof = smt
        .get_multiproof(all_leaves)
        .expect("Error getting multiproof.");

    println!("All leaves verify\n");
    assert_eq!(proof.verify(&smt.get_root().unwrap()), true, "false");
    common::delete_folder("debug_gomad_4");
}