db/radixtree/tests/prefix_test.rs

use radixtree::RadixTree;
use std::collections::HashMap;
use tempfile::tempdir;

#[test]
fn test_list() -> Result<(), radixtree::Error> {
    // Create a temporary directory for the test
    let temp_dir = tempdir().expect("Failed to create temp directory");
    let db_path = temp_dir.path().to_str().unwrap();
    
    // Create a new radix tree
    let mut tree = RadixTree::new(db_path, true)?;

    // Insert keys with various prefixes
    let test_data: HashMap<&str, &str> = [
        ("apple", "fruit1"),
        ("application", "software1"),
        ("apply", "verb1"),
        ("banana", "fruit2"),
        ("ball", "toy1"),
        ("cat", "animal1"),
        ("car", "vehicle1"),
        ("cargo", "shipping1"),
    ].iter().cloned().collect();

    // Set all test data
    for (key, value) in &test_data {
        tree.set(key, value.as_bytes().to_vec())?;
    }

    // Test prefix 'app' - should return apple, application, apply
    let app_keys = tree.list("app")?;
    assert_eq!(app_keys.len(), 3);
    assert!(app_keys.contains(&"apple".to_string()));
    assert!(app_keys.contains(&"application".to_string()));
    assert!(app_keys.contains(&"apply".to_string()));

    // Test prefix 'ba' - should return banana, ball
    let ba_keys = tree.list("ba")?;
    assert_eq!(ba_keys.len(), 2);
    assert!(ba_keys.contains(&"banana".to_string()));
    assert!(ba_keys.contains(&"ball".to_string()));

    // Test prefix 'car' - should return car, cargo
    let car_keys = tree.list("car")?;
    assert_eq!(car_keys.len(), 2);
    assert!(car_keys.contains(&"car".to_string()));
    assert!(car_keys.contains(&"cargo".to_string()));

    // Test prefix 'z' - should return empty list
    let z_keys = tree.list("z")?;
    assert_eq!(z_keys.len(), 0);

    // Test empty prefix - should return all keys
    let all_keys = tree.list("")?;
    assert_eq!(all_keys.len(), test_data.len());
    for key in test_data.keys() {
        assert!(all_keys.contains(&key.to_string()));
    }

    // Test exact key as prefix - should return just that key
    let exact_key = tree.list("apple")?;
    assert_eq!(exact_key.len(), 1);
    assert_eq!(exact_key[0], "apple");

    Ok(())
}

#[test]
fn test_list_with_deletion() -> Result<(), radixtree::Error> {
    // Create a temporary directory for the test
    let temp_dir = tempdir().expect("Failed to create temp directory");
    let db_path = temp_dir.path().to_str().unwrap();
    
    // Create a new radix tree
    let mut tree = RadixTree::new(db_path, true)?;

    // Set keys with common prefixes
    tree.set("test1", b"value1".to_vec())?;
    tree.set("test2", b"value2".to_vec())?;
    tree.set("test3", b"value3".to_vec())?;
    tree.set("other", b"value4".to_vec())?;

    // Initial check
    let test_keys = tree.list("test")?;
    assert_eq!(test_keys.len(), 3);
    assert!(test_keys.contains(&"test1".to_string()));
    assert!(test_keys.contains(&"test2".to_string()));
    assert!(test_keys.contains(&"test3".to_string()));

    // Delete one key
    tree.delete("test2")?;

    // Check after deletion
    let test_keys_after = tree.list("test")?;
    assert_eq!(test_keys_after.len(), 2);
    assert!(test_keys_after.contains(&"test1".to_string()));
    assert!(!test_keys_after.contains(&"test2".to_string()));
    assert!(test_keys_after.contains(&"test3".to_string()));

    // Check all keys
    let all_keys = tree.list("")?;
    assert_eq!(all_keys.len(), 3);
    assert!(all_keys.contains(&"other".to_string()));

    Ok(())
}

#[test]
fn test_list_edge_cases() -> Result<(), radixtree::Error> {
    // Create a temporary directory for the test
    let temp_dir = tempdir().expect("Failed to create temp directory");
    let db_path = temp_dir.path().to_str().unwrap();
    
    // Create a new radix tree
    let mut tree = RadixTree::new(db_path, true)?;

    // Test with empty tree
    let empty_result = tree.list("any")?;
    assert_eq!(empty_result.len(), 0);

    // Set a single key
    tree.set("single", b"value".to_vec())?;

    // Test with prefix that's longer than any key
    let long_prefix = tree.list("singlelonger")?;
    assert_eq!(long_prefix.len(), 0);

    // Test with partial prefix match
    let partial = tree.list("sing")?;
    assert_eq!(partial.len(), 1);
    assert_eq!(partial[0], "single");

    // Test with very long keys
    let long_key1 = "a".repeat(100) + "key1";
    let long_key2 = "a".repeat(100) + "key2";

    tree.set(&long_key1, b"value1".to_vec())?;
    tree.set(&long_key2, b"value2".to_vec())?;

    let long_prefix_result = tree.list(&"a".repeat(100))?;
    assert_eq!(long_prefix_result.len(), 2);
    assert!(long_prefix_result.contains(&long_key1));
    assert!(long_prefix_result.contains(&long_key2));

    Ok(())
}

#[test]
fn test_list_performance() -> Result<(), radixtree::Error> {
    // Create a temporary directory for the test
    let temp_dir = tempdir().expect("Failed to create temp directory");
    let db_path = temp_dir.path().to_str().unwrap();
    
    // Create a new radix tree
    let mut tree = RadixTree::new(db_path, true)?;

    // Insert a large number of keys with different prefixes
    let prefixes = ["user", "post", "comment", "like", "share"];

    // Set 100 keys for each prefix (500 total)
    for prefix in &prefixes {
        for i in 0..100 {
            let key = format!("{}_{}", prefix, i);
            tree.set(&key, format!("value_{}", key).as_bytes().to_vec())?;
        }
    }

    // Test retrieving by each prefix
    for prefix in &prefixes {
        let keys = tree.list(prefix)?;
        assert_eq!(keys.len(), 100);

        // Verify all keys have the correct prefix
        for key in &keys {
            assert!(key.starts_with(prefix));
        }
    }

    // Test retrieving all keys
    let all_keys = tree.list("")?;
    assert_eq!(all_keys.len(), 500);

    Ok(())
}