persy 1.8.0

use super::nodes::{Leaf, Node, TreeNodeRef, Value};
use crate::{
    id::RecRef,
    index::{config::ValueMode, tree::PosRef},
};
use rand::random;

fn random_pointer() -> TreeNodeRef {
    RecRef::new(random::<u64>(), random::<u32>())
}

#[test]
fn single_node_add_test() {
    let val1 = random_pointer();
    let val2 = random_pointer();
    let val3 = random_pointer();
    let val4 = random_pointer();
    let val5 = random_pointer();
    let val6 = random_pointer();
    let mut node = Node::new_from_split(val1, &[(0, val2)]);
    let pos = node.find(&2).pos;
    node.add(pos, &2, val3);
    let pos = node.find(&5).pos;
    node.add(pos, &5, val4);
    let pos = node.find(&6).pos;
    node.add(pos, &6, val5);
    let pos = node.find(&4).pos;
    node.add(pos, &4, val6);

    let found = node.find(&4);
    assert_eq!(found.pos, 3);
    //If i search for 4 i get the one on the left of 4 so the value of 2 that is val3
    assert_eq!(found.node_ref, val6);

    let found = node.find(&5);
    assert_eq!(found.pos, 4);
    //If i search for 5 i get the one on the left of 5 so the value of 4 that is val6
    assert_eq!(found.node_ref, val4);

    let found = node.find(&3);
    //If i search for a value that do not exist i get the position of the value at is right
    //that is value 4 position 2
    assert_eq!(found.pos, 2);
    //If i search for 3 i get the value at the left of 4 that is val3
    assert_eq!(found.node_ref, val3);
}

#[test]
fn single_leaf_insert_test() {
    let mut leaf = Leaf::new();
    for n in 0..50 {
        leaf.insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }
    let res = leaf.find(&10);
    assert_eq!(Ok((10, Value::Single(10))), res);

    let res = leaf.find(&60);
    assert_eq!(Err(50), res);
}

#[test]
fn single_leaf_cluster_insert_test() {
    let mut leaf = Leaf::new();
    leaf.insert_or_update(&10, &1, ValueMode::Cluster, "aa")
        .expect("insert is ok");
    leaf.insert_or_update(&10, &2, ValueMode::Cluster, "aa")
        .expect("insert is ok");
    let res = leaf.find(&10);
    assert_eq!(Ok((10, Value::Cluster(vec![1, 2]))), res);
}

#[test]
fn leaf_cluster_remove_test() {
    let mut leaf = Leaf::new();
    leaf.insert_or_update(&10, &1, ValueMode::Cluster, "aa")
        .expect("insert is ok");
    leaf.insert_or_update(&10, &2, ValueMode::Cluster, "aa")
        .expect("insert is ok");
    assert!(leaf.remove(&10, &Some(2)));
    let res = leaf.find(&10);
    assert_eq!(Ok((10, Value::Single(1))), res);
}

#[test]
fn leaf_cluster_remove_not_exist_value_test() {
    let mut leaf = Leaf::new();
    leaf.insert_or_update(&10, &1, ValueMode::Cluster, "aa")
        .expect("insert is ok");
    leaf.insert_or_update(&10, &2, ValueMode::Cluster, "aa")
        .expect("insert is ok");
    assert!(!leaf.remove(&10, &Some(10)));
    let res = leaf.find(&10);
    assert_eq!(Ok((10, Value::Cluster(vec![1, 2]))), res);
}

#[test]
fn leaf_single_delete_not_exist_value_test() {
    let mut leaf = Leaf::new();
    leaf.insert_or_update(&10, &1, ValueMode::Exclusive, "aa")
        .expect("insert is ok");
    assert!(!leaf.remove(&10, &Some(10)));
    let res = leaf.find(&10);
    assert_eq!(Ok((10, Value::Single(1))), res);
}

#[test]
fn leaf_duplicate_key_test() {
    let mut leaf = Leaf::new();
    leaf.insert_or_update(&10, &1, ValueMode::Exclusive, "aa")
        .expect("insert is ok");
    let res = leaf.insert_or_update(&10, &2, ValueMode::Exclusive, "aa");
    assert!(res.is_err());
}

#[test]
fn test_leaf_split() {
    let mut leaf = Leaf::new();

    for n in 0..103 {
        leaf.insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }

    let res = leaf.split(21);
    assert_eq!(leaf.len(), 21);
    assert_eq!(res[0].1.len(), 21);
    assert_eq!(res[1].1.len(), 21);
    assert_eq!(res[2].1.len(), 21);
    assert_eq!(res[3].1.len(), 19);
}

#[test]
fn test_node_split() {
    let mut node = Node::new_from_split(random_pointer(), &[(0, random_pointer())]);
    for n in 1..103 {
        let pos = node.find(&n).pos;
        node.add(pos, &n, random_pointer());
    }

    let res = node.split(21);
    assert_eq!(node.len(), 21);
    assert_eq!(node.pointers.len(), 21);
    assert_eq!(node.keys.len(), 20);
    assert_eq!(res[0].1.len(), 21);
    assert_eq!(res[0].1.pointers.len(), 21);
    assert_eq!(res[0].1.keys.len(), 20);
    assert_eq!(res[1].1.len(), 21);
    assert_eq!(res[1].1.pointers.len(), 21);
    assert_eq!(res[1].1.keys.len(), 20);
    assert_eq!(res[2].1.len(), 21);
    assert_eq!(res[2].1.pointers.len(), 21);
    assert_eq!(res[2].1.keys.len(), 20);
    assert_eq!(res[3].1.len(), 20);
    assert_eq!(res[3].1.pointers.len(), 20);
    assert_eq!(res[3].1.keys.len(), 19);
}

#[test]
fn test_remove_from_leaf() {
    let mut leaf = Leaf::new();
    for n in 0..50 {
        leaf.insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }
    assert!(leaf.remove(&10, &Some(10)));
    assert!(!leaf.remove(&100, &Some(100)));
    assert_eq!(leaf.len(), 49);
    let res = leaf.find(&10);
    assert_eq!(Err(10), res);
}

#[test]
fn test_remove_from_node() {
    //TODO: check why the remove of 10 make to point to 9
    let mut node = Node::new_from_split(random_pointer(), &[(0, random_pointer())]);
    let mut keep = None;
    for n in 1..50 {
        let pos = node.find(&n).pos;
        let point = random_pointer();
        if n == 9 {
            keep = Some(point);
        }
        node.add(pos, &n, point);
    }
    node.remove_key(&10);
    assert_eq!(node.len(), 50);
    let res = node.find(&10);
    assert_eq!(PosRef::new(&9, 10, keep.unwrap()), res);
}

#[test]
fn test_merge_leaf() {
    let mut leaf = Leaf::new();
    let mut leaf2 = Leaf::new();
    for n in 0..20 {
        leaf.insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }

    for n in 20..40 {
        leaf2
            .insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }
    leaf.merge_right(&20, &mut leaf2);
    assert_eq!(leaf.len(), 40);
    assert_eq!(leaf2.len(), 0);
    let res = leaf.find(&35);
    assert_eq!(res, Ok((35, Value::Single(35))));

    let mut leaf = Leaf::new();
    let mut leaf2 = Leaf::new();
    for n in 20..40 {
        leaf.insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }

    for n in 0..20 {
        leaf2
            .insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }
    leaf.merge_left(&mut leaf2);
    assert_eq!(leaf.len(), 40);
    assert_eq!(leaf2.len(), 0);
    let res = leaf.find(&35);
    assert_eq!(res, Ok((35, Value::Single(35))));
}

#[test]
fn test_merge_nodes() {
    let mut node = Node::new_from_split(random_pointer(), &[(0, random_pointer())]);
    for n in 1..20 {
        let pos = node.find(&n).pos;
        let point = random_pointer();
        node.add(pos, &n, point);
    }

    let mut node2 = Node::new_from_split(random_pointer(), &[(21, random_pointer())]);
    node2.prev = Some(20);
    let mut keep = None;
    for n in 22..40 {
        let pos = node2.find(&n).pos;
        let point = random_pointer();
        if n == 26 {
            keep = Some(point);
        }
        node2.add(pos, &n, point);
    }

    node.merge_right(node2.get_prev().clone().as_ref().unwrap(), &mut node2);
    assert_eq!(node.len(), 41);
    assert_eq!(node2.len(), 0);
    let res = node.find(&26);
    assert_eq!(PosRef::new(&26, 27, keep.unwrap()), res);

    let mut node = Node::new_from_split(random_pointer(), &[(21, random_pointer())]);
    let mut keep = None;
    for n in 22..40 {
        let pos = node.find(&n).pos;
        let point = random_pointer();
        if n == 26 {
            keep = Some(point);
        }
        node.add(pos, &n, point);
    }

    let mut node2 = Node::new_from_split(random_pointer(), &[(0, random_pointer())]);
    for n in 1..20 {
        let pos = node2.find(&n).pos;
        let point = random_pointer();
        node2.add(pos, &n, point);
    }

    node.merge_left(20, &mut node2);
    assert_eq!(node.len(), 41);
    assert_eq!(node2.len(), 0);
    let res = node.find(&26);
    assert_eq!(PosRef::new(&26, 27, keep.unwrap()), res);
}

#[test]
fn test_split_merge_nodes() {
    let mut node = Node::new_from_split(random_pointer(), &[(0, random_pointer())]);
    for n in 1..150 {
        let pos = node.find(&n).pos;
        let point = random_pointer();
        node.add(pos, &n, point);
    }

    let mut res = node.split(21);
    assert_eq!(res.len(), 7);
    assert_eq!(node.len(), 19);
    let mut node2 = res.remove(0).1;
    assert_eq!(node.get_next().unwrap(), 18);
    assert_eq!(node2.get_next().unwrap(), 37);
    assert_eq!(node2.get_prev().unwrap(), 18);
    let node3 = res.remove(0).1;
    assert_eq!(node3.get_next().unwrap(), 56);
    assert_eq!(node3.get_prev().unwrap(), 37);
    node.merge_right(node2.get_prev().clone().as_ref().unwrap(), &mut node2);
    assert_eq!(node.len(), 38);
    assert_eq!(node2.len(), 0);
    assert!(node.get_prev().is_none());
    assert_eq!(node.get_next().unwrap(), 37);

    let mut node = res.remove(0).1;
    assert_eq!(node.get_prev().unwrap(), 56);
    assert_eq!(node.get_next().unwrap(), 75);
    let mut node2 = res.remove(0).1;
    assert_eq!(node2.get_prev().unwrap(), 75);
    assert_eq!(node2.get_next().unwrap(), 94);
    node.merge_right(node2.get_prev().clone().as_ref().unwrap(), &mut node2);
    assert_eq!(node.len(), 38);
    assert_eq!(node2.len(), 0);
    assert_eq!(node.get_prev().unwrap(), 56);
    assert_eq!(node.get_next().unwrap(), 94);

    let mut node3 = res.remove(0).1;
    node3.merge_left(node3.get_prev().unwrap(), &mut node);
    assert_eq!(node3.get_prev().unwrap(), 94);
    assert_eq!(node3.get_next().unwrap(), 113);
}

#[test]
fn test_split_merge_leaves() {
    let mut leaf = Leaf::new();
    for n in 0..150 {
        leaf.insert_or_update(&n, &n, ValueMode::Replace, "aa")
            .expect("insert is ok");
    }

    let mut res = leaf.split(21);
    assert_eq!(res.len(), 7);
    assert_eq!(leaf.len(), 19);
    let mut leaf2 = res.remove(0).1;
    assert_eq!(leaf.get_next().unwrap(), 19);
    assert_eq!(leaf2.get_next().unwrap(), 38);
    assert_eq!(leaf2.get_prev().unwrap(), 19);
    let leaf3 = res.remove(0).1;
    assert_eq!(leaf3.get_next().unwrap(), 57);
    assert_eq!(leaf3.get_prev().unwrap(), 38);
    leaf.merge_right(leaf2.get_prev().clone().as_ref().unwrap(), &mut leaf2);
    assert_eq!(leaf.len(), 38);
    assert_eq!(leaf2.len(), 0);
    assert!(leaf.get_prev().is_none());
    assert_eq!(leaf.get_next().unwrap(), 38);

    let mut leaf = res.remove(0).1;
    assert_eq!(leaf.get_prev().unwrap(), 57);
    assert_eq!(leaf.get_next().unwrap(), 76);
    let mut leaf2 = res.remove(0).1;
    assert_eq!(leaf2.get_prev().unwrap(), 76);
    assert_eq!(leaf2.get_next().unwrap(), 95);
    leaf.merge_right(leaf2.get_prev().clone().as_ref().unwrap(), &mut leaf2);
    assert_eq!(leaf.len(), 38);
    assert_eq!(leaf2.len(), 0);
    assert_eq!(leaf.get_prev().unwrap(), 57);
    assert_eq!(leaf.get_next().unwrap(), 95);

    let mut leaf3 = res.remove(0).1;
    leaf3.merge_left(&mut leaf);
    assert_eq!(leaf3.get_prev().unwrap(), 95);
    assert_eq!(leaf3.get_next().unwrap(), 114);
}