embed-avl 0.4.0

use super::*;
use captains_log::logfn;
use pointers::CloneablePointer;
use rstest::*;
use std::boxed::Box;
use std::fmt::Debug;
use std::rc::Rc;
use std::sync::Arc;

#[logfn]
#[rstest]
#[case(IntAvlTree::<Box<IntAvlNode>>::new())]
#[case(IntAvlTree::<Arc<IntAvlNode>>::new())]
#[case(IntAvlTree::<Rc<IntAvlNode>>::new())]
fn test_into_iter<P>(#[case] mut tree: IntAvlTree<P>, setup_log: ())
where
    P: SmartPointer<Target = IntAvlNode> + Deref<Target = IntAvlNode> + Debug,
{
    reset_alive_count();
    let _new_node = IntAvlTree::<P>::new_node;
    {
        for i in 0..100 {
            tree.add_int_node(_new_node(i));
        }
        assert_eq!(tree.len(), 100);
        let mut i = 0;
        for node in tree.0 {
            assert_eq!(node.value, i);
            i += 1;
        }
        assert_eq!(i, 100);
    }
    assert_eq!(alive_count(), 0);
}

#[logfn]
#[rstest]
#[case(IntAvlTree::<Box<IntAvlNode>>::new())]
#[case(IntAvlTree::<Arc<IntAvlNode>>::new())]
#[case(IntAvlTree::<Rc<IntAvlNode>>::new())]
fn test_into_iter_drop_early<P>(#[case] mut tree: IntAvlTree<P>, setup_log: ())
where
    P: SmartPointer<Target = IntAvlNode> + Deref<Target = IntAvlNode> + Debug,
{
    reset_alive_count();
    let _new_node = IntAvlTree::<P>::new_node;
    {
        for i in 0..100 {
            tree.add_int_node(_new_node(i));
        }
        assert_eq!(tree.len(), 100);
        let mut i = 0;
        let stop = fastrand::i64(1..100);
        println!("test stop at {stop}");
        for node in tree.0 {
            assert_eq!(node.value, i);
            i += 1;
            if i == stop {
                break;
            }
        }
    }
    assert_eq!(alive_count(), 0);
}

#[logfn]
#[rstest]
#[case(IntAvlTree::<Box<IntAvlNode>>::new())]
#[case(IntAvlTree::<Arc<IntAvlNode>>::new())]
#[case(IntAvlTree::<Rc<IntAvlNode>>::new())]
fn test_into_iter_rev<P>(#[case] mut tree: IntAvlTree<P>, setup_log: ())
where
    P: SmartPointer<Target = IntAvlNode> + Deref<Target = IntAvlNode> + Debug,
{
    reset_alive_count();
    let _new_node = IntAvlTree::<P>::new_node;
    {
        for i in 0..100 {
            tree.add_int_node(_new_node(i));
        }
        assert_eq!(tree.len(), 100);
        let mut i = 100;
        for node in tree.0.into_iter_rev() {
            i -= 1;
            assert_eq!(node.value, i);
        }
        assert_eq!(i, 0);
    }
    assert_eq!(alive_count(), 0);
}

#[logfn]
#[rstest]
#[case(IntAvlTree::<Box<IntAvlNode>>::new())]
#[case(IntAvlTree::<Arc<IntAvlNode>>::new())]
#[case(IntAvlTree::<Rc<IntAvlNode>>::new())]
fn test_into_iter_rev_drop_early<P>(#[case] mut tree: IntAvlTree<P>, setup_log: ())
where
    P: SmartPointer<Target = IntAvlNode> + Deref<Target = IntAvlNode> + Debug,
{
    reset_alive_count();
    let _new_node = IntAvlTree::<P>::new_node;
    {
        for i in 0..100 {
            tree.add_int_node(_new_node(i));
        }
        assert_eq!(tree.len(), 100);
        let mut i = 100;
        let stop = fastrand::i64(1..100);
        println!("test stop at {stop}");
        for node in tree.0.into_iter_rev() {
            i -= 1;
            assert_eq!(node.value, i);
            if i <= stop {
                break;
            }
        }
    }
    assert_eq!(alive_count(), 0);
}

#[logfn]
#[rstest]
#[case(IntAvlTree::<Box<IntAvlNode>>::new())]
#[case(IntAvlTree::<Arc<IntAvlNode>>::new())]
#[case(IntAvlTree::<Rc<IntAvlNode>>::new())]
fn test_iter<P>(#[case] mut tree: IntAvlTree<P>, setup_log: ())
where
    P: SmartPointer<Target = IntAvlNode> + Deref<Target = IntAvlNode> + Debug,
{
    reset_alive_count();
    let _new_node = IntAvlTree::<P>::new_node;
    {
        for i in 0..100 {
            tree.add_int_node(_new_node(i));
        }
        assert_eq!(tree.len(), 100);

        let mut count = 0;
        for (i, node) in tree.iter().enumerate() {
            assert_eq!(node.value as usize, i);
            count += 1;
        }
        assert_eq!(count, 100);

        let mut count = 0;
        for (i, node) in tree.iter_rev().enumerate() {
            assert_eq!(node.value as usize, 100 - i - 1);
            count += 1;
        }
        assert_eq!(count, 100);
        drop(tree);
    }
    assert_eq!(alive_count(), 0);
}

/// Test AvlIter::next_ref() with Arc by cloning each node during iteration.
/// Verifies that reference counting works correctly and all references are properly cleaned up.
#[logfn]
#[rstest]
#[case(IntAvlTree::<Arc<IntAvlNode>>::new())]
#[case(IntAvlTree::<Rc<IntAvlNode>>::new())]
fn test_next_ref_clone_arc<P>(#[case] mut tree: IntAvlTree<P>, setup_log: ())
where
    P: SmartPointer<Target = IntAvlNode>
        + CloneablePointer
        + Deref<Target = IntAvlNode>
        + Clone
        + Debug,
{
    reset_alive_count();
    let _new_node = IntAvlTree::<P>::new_node;
    {
        let n = 50;
        for i in 0..n {
            tree.add_int_node(_new_node(i as i64));
        }
        assert_eq!(tree.len(), n);
        // Each node created once
        assert_eq!(alive_count(), n);

        // Iterate using next_ref() and clone each Arc during iteration
        let mut cloned_nodes: Vec<P> = Vec::with_capacity(n);
        let mut iter = tree.iter();
        while let Some(arc) = iter.next() {
            cloned_nodes.push(arc.clone_ref());
        }
        for (i, node) in cloned_nodes.iter().enumerate() {
            assert_eq!(node.value as usize, i);
        }

        // After cloning, we have tree refs + cloned refs
        assert_eq!(alive_count(), n);

        // Verify all cloned values are correct
        for (i, arc) in cloned_nodes.iter().enumerate() {
            assert_eq!(arc.value as usize, i);
        }
        // Drop all cloned references
        drop(cloned_nodes);
        // Only tree refs remain
        assert_eq!(alive_count(), n);

        // Validate tree structure is intact
        tree.validate_tree();

        // Drop the tree
        drop(tree);
    }
    // All nodes dropped, alive count should be 0
    assert_eq!(alive_count(), 0);
}

/// Test AvlIter::next_ref() reverse iteration with Arc cloning.
#[logfn]
#[rstest]
#[case(IntAvlTree::<Arc<IntAvlNode>>::new())]
#[case(IntAvlTree::<Rc<IntAvlNode>>::new())]
fn test_next_ref_clone_rev<P>(#[case] mut tree: IntAvlTree<P>, setup_log: ())
where
    P: SmartPointer<Target = IntAvlNode>
        + CloneablePointer
        + Deref<Target = IntAvlNode>
        + Clone
        + Debug,
{
    reset_alive_count();
    let _new_node = IntAvlTree::<P>::new_node;
    {
        let n = 30;
        for i in 0..n {
            tree.add_int_node(_new_node(i as i64));
        }
        assert_eq!(tree.len(), n);
        assert_eq!(alive_count(), n);

        let mut cloned_nodes: Vec<P> = Vec::with_capacity(n);
        let mut iter = tree.iter_rev();
        while let Some(arc) = iter.next() {
            cloned_nodes.push(arc.clone_ref());
        }

        // Reverse order: last element first
        for (i, arc) in cloned_nodes.iter().enumerate() {
            assert_eq!(arc.value as usize, n - 1 - i);
        }

        drop(cloned_nodes);
        assert_eq!(alive_count(), n);

        drop(tree);
    }
    assert_eq!(alive_count(), 0);
}