edgevec/hnsw/

graph.rs

#![allow(clippy::cast_possible_truncation)]
#![allow(clippy::cast_precision_loss)]
#![allow(clippy::cast_sign_loss)]
#![allow(clippy::missing_errors_doc)]
#![allow(clippy::missing_panics_doc)]

use super::config::HnswConfig;
use super::neighbor::NeighborPool;
use crate::storage::VectorStorage;
use bytemuck::{Pod, Zeroable};
use rand::{Rng, SeedableRng};
use rand_chacha::ChaCha8Rng;
use serde::{Deserialize, Serialize};
use std::borrow::Cow;
use std::vec::Vec;
use thiserror::Error;

/// Unique identifier for a vector in the database.
///
/// # Size
/// 8 bytes, aligned to 8
///
/// # Invariants
/// - IDs are never reused (monotonically increasing)
/// - ID 0 is reserved (invalid sentinel)
///
/// # Safety
/// Derives `Pod` and `Zeroable` for safe byte casting via bytemuck.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Pod, Zeroable)]
#[repr(transparent)]
pub struct VectorId(pub u64);

impl VectorId {
    /// Sentinel value indicating "no vector"
    pub const INVALID: Self = VectorId(0);

    /// First valid ID
    pub const FIRST: Self = VectorId(1);
}

/// Internal node identifier within HNSW graph.
///
/// # Size
/// 4 bytes, aligned to 4
///
/// # Invariants
/// - `NodeId` corresponds 1:1 with `VectorId` (lower 32 bits)
/// - `NodeId` 0xFFFFFFFF is reserved (invalid sentinel)
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[repr(transparent)]
pub struct NodeId(pub u32);

impl NodeId {
    /// Sentinel value indicating invalid node
    pub const INVALID: Self = NodeId(u32::MAX);
}

/// Represents a layer level in the HNSW graph.
///
/// Layer 0 is the base layer containing all nodes.
/// Higher layers contain a subset of nodes for faster navigation.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
#[allow(dead_code)]
pub struct Layer(pub u8);

/// Errors that can occur during graph operations.
#[derive(Error, Debug, Clone, PartialEq, Eq)]
pub enum GraphError {
    /// The graph has reached its maximum node capacity (`u32::MAX`).
    #[error("node capacity exceeded")]
    CapacityExceeded,

    /// The provided `VectorId` is invalid (e.g., sentinel value).
    #[error("invalid vector id")]
    InvalidVectorId,

    /// Neighbor data is corrupted or offset is out of bounds.
    #[error("neighbor data corrupted")]
    NeighborError,

    /// Node ID is out of bounds.
    #[error("node id out of bounds")]
    NodeIdOutOfBounds,

    /// Configuration mismatch with storage.
    #[error("config dimension mismatch: expected {expected}, got {actual}")]
    ConfigMismatch {
        /// Expected dimensions.
        expected: u32,
        /// Actual dimensions in config.
        actual: u32,
    },

    /// Query vector has wrong dimensions.
    #[error("dimension mismatch: expected {expected}, got {actual}")]
    DimensionMismatch {
        /// Expected dimensions.
        expected: usize,
        /// Actual dimensions.
        actual: usize,
    },

    /// Storage operation failed.
    #[error("storage error: {0}")]
    Storage(String),

    /// Invalid configuration parameter.
    #[error("invalid config: {0}")]
    InvalidConfig(String),
}

/// Result of a compaction operation.
///
/// Returned by [`HnswIndex::compact()`] to provide metrics about the operation.
///
/// # Fields
///
/// * `tombstones_removed` - Number of deleted vectors removed
/// * `new_size` - Size of the new index (live vectors only)
/// * `duration_ms` - Time taken for the operation in milliseconds
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CompactionResult {
    /// Number of tombstones (deleted vectors) removed during compaction.
    pub tombstones_removed: usize,
    /// New index size after compaction (live vectors only).
    pub new_size: usize,
    /// Time taken for the compaction operation in milliseconds.
    pub duration_ms: u64,
}

/// A node in the HNSW graph with its adjacency information.
///
/// # Layout
///
/// Total size: 16 bytes
/// Alignment: 8 bytes
///
/// # Fields
///
/// - `vector_id`: 8 bytes
/// - `neighbor_offset`: 4 bytes
/// - `neighbor_len`: 2 bytes
/// - `max_layer`: 1 byte
/// - `deleted`: 1 byte (soft delete flag, v0.3.0)
///
/// # Soft Delete (v0.3.0)
///
/// The `deleted` field enables O(1) soft delete. Deleted nodes remain in
/// the graph for routing but are excluded from search results.
/// - `deleted = 0`: Node is live (default)
/// - `deleted = 1`: Node is deleted (tombstone)
///
/// # Safety
///
/// Derives `Pod` and `Zeroable` for safe byte casting via bytemuck.
/// The `#[repr(C)]` ensures deterministic layout for serialization.
/// All fields are primitive types with no padding gaps.
#[derive(Clone, Copy, Debug, Serialize, Deserialize, Pod, Zeroable)]
#[repr(C)]
pub struct HnswNode {
    /// The vector ID this node represents
    pub vector_id: VectorId,

    /// Offset into COMPRESSED neighbor pool
    pub neighbor_offset: u32,

    /// Length of neighbor data in bytes (Allocated Capacity)
    pub neighbor_len: u16,

    /// The maximum layer this node appears in
    pub max_layer: u8,

    /// Soft delete flag: 0 = live, 1 = deleted (v0.3.0)
    /// This field replaces the padding byte from v0.2.x.
    pub deleted: u8,
}

/// The HNSW Graph structure managing layers and nodes.
///
/// # Memory
///
/// Uses a flattened representation for cache efficiency.
/// Nodes are stored in a contiguous vector.
///
/// # Soft Delete (v0.3.0)
///
/// Supports soft delete via tombstone marking. Deleted nodes remain
/// in the graph for routing but are excluded from search results.
/// Use `compact()` to reclaim space from deleted nodes.
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct HnswIndex {
    /// Algorithm configuration
    pub config: HnswConfig,

    /// Node metadata (fixed-size per node)
    pub(crate) nodes: Vec<HnswNode>,

    /// Compressed neighbor lists
    pub(crate) neighbors: NeighborPool,

    /// Entry point (highest layer node)
    pub(crate) entry_point: Option<NodeId>,

    /// Maximum layer in the graph
    pub(crate) max_layer: u8,

    /// Level probability multiplier (1/ln(M))
    pub(crate) level_mult: f32,

    /// Deterministic RNG state
    rng: ChaCha8Rng,

    /// Count of soft-deleted vectors (v0.3.0)
    /// This tracks the number of nodes with `deleted = 1`.
    #[serde(default)]
    pub(crate) deleted_count: usize,

    /// Compaction threshold ratio (v0.3.0)
    /// When tombstone_ratio() exceeds this value, needs_compaction() returns true.
    /// Default: 0.3 (30% tombstones triggers compaction recommendation)
    #[serde(default = "default_compaction_threshold")]
    compaction_threshold: f64,
}

/// Default compaction threshold (30%)
fn default_compaction_threshold() -> f64 {
    0.3
}

impl HnswIndex {
    /// Creates a new empty HNSW graph.
    ///
    /// # Arguments
    ///
    /// * `config` - HNSW configuration parameters.
    /// * `storage` - Vector storage to validate against.
    ///
    /// # Errors
    ///
    /// Returns `GraphError::ConfigMismatch` if storage dimensions differ from config.
    /// Returns `GraphError::InvalidConfig` if configuration parameters are invalid (e.g., M <= 1).
    pub fn new(config: HnswConfig, storage: &VectorStorage) -> Result<Self, GraphError> {
        if config.dimensions != storage.dimensions() {
            return Err(GraphError::ConfigMismatch {
                expected: storage.dimensions(),
                actual: config.dimensions,
            });
        }

        if config.m <= 1 {
            return Err(GraphError::InvalidConfig(format!(
                "m must be > 1, got {}",
                config.m
            )));
        }
        if config.m0 < config.m {
            return Err(GraphError::InvalidConfig(format!(
                "m0 must be >= m, got {} < {}",
                config.m0, config.m
            )));
        }

        // Calculate level multiplier: m_l = 1 / ln(M)
        let m_float = config.m as f32;
        let level_mult = if m_float > 1.0 {
            1.0 / m_float.ln()
        } else {
            0.0
        };

        // Initialize RNG with a default seed for determinism.
        let rng = ChaCha8Rng::seed_from_u64(42);

        Ok(Self {
            config,
            nodes: Vec::new(),
            neighbors: NeighborPool::new(),
            entry_point: None,
            max_layer: 0,
            level_mult,
            rng,
            deleted_count: 0, // v0.3.0: No deleted nodes initially
            compaction_threshold: default_compaction_threshold(), // v0.3.0: Default 30%
        })
    }

    /// Generates a random level for a new node.
    ///
    /// Formula: `floor(-ln(uniform(0,1)) * m_l)`
    /// Clamped to `max_level` (e.g. 16) to prevent memory explosion.
    #[must_use]
    pub fn get_random_level(&mut self) -> u8 {
        // Generate uniform(0, 1)
        let r: f32 = self.rng.gen_range(f32::EPSILON..=1.0);
        let level = (-r.ln() * self.level_mult).floor();

        // Safety cap (e.g. 16)
        if level > 16.0 {
            16
        } else {
            level as u8
        }
    }

    /// Adds a node to the graph.
    ///
    /// # Arguments
    ///
    /// * `vector_id` - The external vector identifier
    /// * `max_layer` - The maximum layer for this node
    ///
    /// # Returns
    ///
    /// The new `NodeId` assigned to this node, or a `GraphError`.
    pub fn add_node(&mut self, vector_id: VectorId, max_layer: u8) -> Result<NodeId, GraphError> {
        if vector_id == VectorId::INVALID {
            return Err(GraphError::InvalidVectorId);
        }

        // Safety limit for NodeId
        if self.nodes.len() >= u32::MAX as usize {
            return Err(GraphError::CapacityExceeded);
        }

        let node = HnswNode {
            vector_id,
            neighbor_offset: 0,
            neighbor_len: 0,
            max_layer,
            deleted: 0, // Live node (v0.3.0)
        };

        #[allow(clippy::cast_possible_truncation)]
        let id = NodeId(self.nodes.len() as u32);
        self.nodes.push(node);

        // Update max layer if needed
        if max_layer > self.max_layer {
            self.max_layer = max_layer;
        }

        Ok(id)
    }

    /// Sets the neighbors for a node.
    ///
    /// # Arguments
    /// * `node_id` - The node to update.
    /// * `neighbors` - The list of neighbor IDs.
    pub fn set_neighbors(
        &mut self,
        node_id: NodeId,
        neighbors: &[NodeId],
    ) -> Result<(), GraphError> {
        if node_id.0 as usize >= self.nodes.len() {
            return Err(GraphError::InvalidVectorId);
        }

        // Convert NodeId to u32 for encoding
        let neighbor_u32s: Vec<u32> = neighbors.iter().map(|n| n.0).collect();
        let encoded = NeighborPool::encode_neighbors(&neighbor_u32s);

        // Alloc new space
        let (offset, capacity) = self.neighbors.alloc(encoded.len())?;

        // Write data
        let start = offset as usize;
        let end = start + encoded.len();
        self.neighbors.buffer[start..end].copy_from_slice(&encoded);

        // Update node and free old
        let node = &mut self.nodes[node_id.0 as usize];

        // Free old slot if it existed
        if node.neighbor_len > 0 {
            self.neighbors.free(node.neighbor_offset, node.neighbor_len);
        }

        node.neighbor_offset = offset;
        node.neighbor_len = capacity; // Store allocated capacity

        Ok(())
    }

    /// Retrieves a node by its ID.
    #[must_use]
    pub fn get_node(&self, id: NodeId) -> Option<&HnswNode> {
        if id == NodeId::INVALID {
            return None;
        }
        self.nodes.get(id.0 as usize)
    }

    /// Retrieves the neighbors for a node.
    pub fn get_neighbors(&self, node: &HnswNode) -> Result<Vec<NodeId>, GraphError> {
        let start = node.neighbor_offset as usize;
        // Read up to allocated capacity
        let end = start + node.neighbor_len as usize;

        if end > self.neighbors.buffer.len() {
            return Err(GraphError::NeighborError);
        }

        let slice = &self.neighbors.buffer[start..end];
        let raw_neighbors = NeighborPool::decode_neighbors(slice);

        // Convert back to NodeId
        let neighbors = raw_neighbors.into_iter().map(NodeId).collect();
        Ok(neighbors)
    }

    /// Retrieves the neighbors for a specific layer.
    pub fn get_neighbors_layer(
        &self,
        node: &HnswNode,
        layer: u8,
    ) -> Result<Vec<NodeId>, GraphError> {
        let start = node.neighbor_offset as usize;
        let end = start + node.neighbor_len as usize;

        if end > self.neighbors.buffer.len() {
            return Err(GraphError::NeighborError);
        }

        let slice = &self.neighbors.buffer[start..end];
        let raw_neighbors = NeighborPool::decode_layer(slice, layer);

        // Convert back to NodeId
        let neighbors = raw_neighbors.into_iter().map(NodeId).collect();
        Ok(neighbors)
    }

    /// Returns the number of nodes in the graph.
    #[must_use]
    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }

    /// Returns the entry point node ID, if any.
    #[must_use]
    pub fn entry_point(&self) -> Option<NodeId> {
        self.entry_point
    }

    /// Sets the entry point node ID.
    pub fn set_entry_point(&mut self, id: NodeId) {
        self.entry_point = Some(id);
    }

    /// Returns the current maximum layer in the graph.
    #[must_use]
    pub fn max_layer(&self) -> u8 {
        self.max_layer
    }

    // ============================================================================
    // Soft Delete API (W16.2 - RFC-001)
    // ============================================================================

    /// Get mutable reference to a node by VectorId.
    ///
    /// # Complexity
    ///
    /// * Time: O(n) linear scan
    /// * Space: O(1)
    fn get_node_mut(&mut self, vector_id: VectorId) -> Result<&mut HnswNode, GraphError> {
        self.nodes
            .iter_mut()
            .find(|n| n.vector_id == vector_id)
            .ok_or(GraphError::InvalidVectorId)
    }

    /// Get immutable reference to a node by VectorId.
    ///
    /// # Complexity
    ///
    /// * Time: O(n) linear scan
    /// * Space: O(1)
    fn get_node_by_vector_id(&self, vector_id: VectorId) -> Result<&HnswNode, GraphError> {
        self.nodes
            .iter()
            .find(|n| n.vector_id == vector_id)
            .ok_or(GraphError::InvalidVectorId)
    }

    /// Mark a vector as deleted (soft delete).
    ///
    /// The vector remains in the graph for routing but is excluded from
    /// search results. Space is reclaimed via `compact()`.
    ///
    /// # Arguments
    ///
    /// * `vector_id` - The ID of the vector to delete
    ///
    /// # Returns
    ///
    /// * `Ok(true)` - Vector was deleted
    /// * `Ok(false)` - Vector was already deleted
    /// * `Err(InvalidVectorId)` - Vector ID not found
    ///
    /// # Complexity
    ///
    /// * Time: **O(n)** for VectorId → Node lookup via linear scan,
    ///   plus O(1) for setting the deleted byte
    /// * Space: O(1)
    ///
    /// **Note:** The O(n) lookup is a known limitation in v0.3.0.
    /// A HashMap<VectorId, NodeId> index could provide O(1) lookup
    /// but is deferred to v0.4.0 to avoid scope creep.
    ///
    /// # Thread Safety (RFC-001 Design)
    ///
    /// This method requires `&mut self`, which means Rust's borrow checker
    /// prevents concurrent access at compile time. This is intentional:
    ///
    /// * Search (`&self`) and delete (`&mut self`) cannot run concurrently
    /// * No atomics or locks needed - safety is enforced by the type system
    /// * See RFC-001 Section 6.4 "Design Decisions" for rationale
    ///
    /// # Persistence
    ///
    /// **IMPORTANT:** Delete operations are in-memory only until `save()` is called.
    /// If the process crashes before `save()`, the delete will be lost.
    ///
    /// # Example
    ///
    /// ```ignore
    /// let deleted = index.soft_delete(VectorId(42))?;
    /// assert!(deleted);
    /// assert!(index.is_deleted(VectorId(42))?);
    /// ```
    pub fn soft_delete(&mut self, vector_id: VectorId) -> Result<bool, GraphError> {
        let node = self.get_node_mut(vector_id)?;

        if node.deleted != 0 {
            return Ok(false); // Already deleted
        }

        node.deleted = 1;
        self.deleted_count += 1;
        Ok(true)
    }

    /// Check if a vector is marked as deleted.
    ///
    /// # Arguments
    ///
    /// * `vector_id` - The ID of the vector to check
    ///
    /// # Returns
    ///
    /// * `Ok(true)` - Vector is deleted
    /// * `Ok(false)` - Vector is live
    /// * `Err(InvalidVectorId)` - Vector ID not found
    ///
    /// # Complexity
    ///
    /// * Time: O(n) for lookup + O(1) for check
    /// * Space: O(1)
    pub fn is_deleted(&self, vector_id: VectorId) -> Result<bool, GraphError> {
        let node = self.get_node_by_vector_id(vector_id)?;
        Ok(node.deleted != 0)
    }

    /// Get the count of deleted (tombstoned) vectors.
    ///
    /// # Returns
    ///
    /// Number of vectors marked as deleted.
    #[must_use]
    pub fn deleted_count(&self) -> usize {
        self.deleted_count
    }

    /// Get the ratio of deleted vectors to total vectors.
    ///
    /// # Returns
    ///
    /// A value between 0.0 and 1.0 representing the tombstone ratio.
    /// Returns 0.0 if the index is empty.
    #[must_use]
    pub fn tombstone_ratio(&self) -> f64 {
        let total = self.node_count();
        if total == 0 {
            return 0.0;
        }
        self.deleted_count as f64 / total as f64
    }

    /// Get count of live (non-deleted) vectors.
    ///
    /// # Returns
    ///
    /// Number of vectors that are not marked as deleted.
    #[must_use]
    pub fn live_count(&self) -> usize {
        self.node_count().saturating_sub(self.deleted_count)
    }

    /// Maximum multiplier for adjusted_k to prevent excessive over-fetching.
    ///
    /// At 90%+ tombstones, we cap at 10x the original k to bound memory usage.
    /// Beyond this ratio, compaction should be triggered.
    pub const MAX_ADJUSTED_K_MULTIPLIER: usize = 10;

    /// Calculate adjusted k to compensate for tombstones.
    ///
    /// When the index has deleted vectors, we over-fetch to ensure
    /// we can return k live results after filtering. This method
    /// calculates how many candidates to fetch internally so that
    /// after filtering out deleted vectors, we likely have k results.
    ///
    /// # Formula
    ///
    /// `adjusted_k = k * total / live`
    ///
    /// This is equivalent to `k / (1 - tombstone_ratio)` but uses
    /// integer arithmetic for precision.
    ///
    /// # Caps
    ///
    /// The result is capped at `k * MAX_ADJUSTED_K_MULTIPLIER` (default 10x)
    /// to prevent excessive fetching at very high tombstone ratios.
    ///
    /// # Examples
    ///
    /// * 0% tombstones: k = k (no adjustment)
    /// * 10% tombstones: k → ~1.11x
    /// * 30% tombstones: k → ~1.43x
    /// * 50% tombstones: k → 2x
    /// * 90%+ tombstones: k → 10x (capped)
    ///
    /// # Thread Safety
    ///
    /// This method reads `deleted_count` and `node_count()` which may change
    /// if the index is mutated. Per RFC-001, the API uses `&mut self` for
    /// mutations, so concurrent read+write is prevented by Rust's borrow checker.
    /// The design accepts eventual consistency for soft delete semantics.
    ///
    /// # Arguments
    ///
    /// * `k` - The requested number of results
    ///
    /// # Returns
    ///
    /// The adjusted k value to use for internal search operations.
    /// This value is always >= k (unless capped by live_count).
    #[must_use]
    pub fn adjusted_k(&self, k: usize) -> usize {
        // Fast path: no tombstones
        if self.deleted_count == 0 {
            return k;
        }

        let total = self.node_count();
        let live = self.live_count();

        // Edge case: all deleted
        // This also prevents division by zero in the calculation below.
        if live == 0 {
            return k; // Will return empty results anyway
        }

        // Integer arithmetic: adjusted = k * total / live
        // Use saturating ops to prevent overflow
        let adjusted = k.saturating_mul(total) / live;

        // Cap at MAX_ADJUSTED_K_MULTIPLIER to prevent excessive over-fetching
        // Note: We don't cap at total because adjusted_k controls the internal
        // search effort (ef parameter), not the final result count.
        let max_by_multiplier = k.saturating_mul(Self::MAX_ADJUSTED_K_MULTIPLIER);
        adjusted.min(max_by_multiplier)
    }

    /// Marks a vector as deleted in the storage (legacy API).
    ///
    /// **DEPRECATED:** Use `soft_delete()` instead for RFC-001 compliant soft delete.
    /// This method delegates to storage and does not update `deleted_count`.
    ///
    /// # Arguments
    ///
    /// * `id` - The vector ID to delete.
    /// * `storage` - The vector storage to update.
    ///
    /// # Returns
    ///
    /// `true` if the vector was active and is now deleted.
    /// `false` if it was already deleted.
    #[deprecated(since = "0.3.0", note = "Use soft_delete() instead")]
    pub fn delete_in_storage(&self, id: VectorId, storage: &mut VectorStorage) -> bool {
        storage.mark_deleted(id)
    }

    /// DEBUG: Print memory stats
    pub fn log_stats(&self) {
        println!("Index Stats:");
        println!("  Node Count: {}", self.nodes.len());
        println!("  Neighbor Buffer Len: {}", self.neighbors.buffer.len());
        println!(
            "  Neighbor Buffer Cap: {}",
            self.neighbors.buffer.capacity()
        );
        println!("  Total Memory Usage: {} bytes", self.memory_usage());
        // bucket stats are internal to NeighborPool
    }

    /// Returns the approximate memory usage in bytes.
    #[must_use]
    pub fn memory_usage(&self) -> usize {
        let nodes_size = self.nodes.capacity() * std::mem::size_of::<HnswNode>();
        let neighbors_size = self.neighbors.memory_usage();

        std::mem::size_of::<Self>() + nodes_size + neighbors_size
    }

    // ========================================================================
    // Compaction API (W16.4 - RFC-001)
    // ========================================================================

    /// Check if compaction is recommended.
    ///
    /// Returns `true` if the tombstone ratio exceeds the configured threshold
    /// (default 30%). When this returns true, calling `compact()` is
    /// recommended to reclaim space and maintain search performance.
    ///
    /// # Thread Safety
    ///
    /// This method is **not thread-safe**. `HnswIndex` is `!Send` and must be
    /// accessed from a single thread. For concurrent use, create separate index
    /// instances (e.g., via Web Workers in WASM).
    ///
    /// # Example
    ///
    /// ```ignore
    /// if index.needs_compaction() {
    ///     let (new_index, new_storage, result) = index.compact(&storage)?;
    ///     index = new_index;
    ///     storage = new_storage;
    /// }
    /// ```
    #[must_use]
    pub fn needs_compaction(&self) -> bool {
        self.tombstone_ratio() > self.compaction_threshold
    }

    /// Set the compaction threshold.
    ///
    /// When `tombstone_ratio()` exceeds this value, `needs_compaction()`
    /// returns true.
    ///
    /// # Arguments
    ///
    /// * `ratio` - Tombstone ratio threshold (0.01 to 0.99)
    ///
    /// # Default
    ///
    /// Default is 0.3 (30%). Lower values trigger compaction more often
    /// but maintain better search performance.
    ///
    /// # Clamping
    ///
    /// Values outside [0.01, 0.99] are clamped to that range.
    pub fn set_compaction_threshold(&mut self, ratio: f64) {
        self.compaction_threshold = ratio.clamp(0.01, 0.99);
    }

    /// Get the current compaction threshold.
    ///
    /// # Returns
    ///
    /// The ratio at which `needs_compaction()` returns true.
    #[must_use]
    pub fn compaction_threshold(&self) -> f64 {
        self.compaction_threshold
    }

    /// Get a compaction warning message if compaction is recommended.
    ///
    /// Returns `Some(message)` if the tombstone ratio exceeds the threshold,
    /// or `None` if compaction is not needed.
    ///
    /// # Example
    ///
    /// ```ignore
    /// if let Some(warning) = index.compaction_warning() {
    ///     log::warn!("{}", warning);
    /// }
    /// ```
    #[must_use]
    pub fn compaction_warning(&self) -> Option<String> {
        if self.needs_compaction() {
            Some(format!(
                "Compaction recommended: tombstone ratio {:.1}% exceeds threshold {:.1}%. \
                 Call compact() to rebuild index without tombstones.",
                self.tombstone_ratio() * 100.0,
                self.compaction_threshold * 100.0
            ))
        } else {
            None
        }
    }

    /// Compact the index by rebuilding without tombstones.
    ///
    /// This operation creates a NEW index and NEW storage containing only
    /// live (non-deleted) vectors. The original index and storage are NOT
    /// modified, allowing the caller to replace them atomically.
    ///
    /// # Important: Vector ID Remapping
    ///
    /// Due to storage design constraints, vector IDs are remapped during
    /// compaction. New IDs are assigned sequentially starting from 1.
    /// If you need to track the mapping, use the returned index to query
    /// by position or content.
    ///
    /// # Returns
    ///
    /// Returns `(new_index, new_storage, result)` tuple. The caller MUST
    /// replace BOTH their index and storage references:
    ///
    /// ```ignore
    /// let (new_index, new_storage, result) = old_index.compact(&old_storage)?;
    /// println!("Removed {} tombstones in {}ms", result.tombstones_removed, result.duration_ms);
    /// // Now use new_index and new_storage, old ones will be dropped
    /// index = new_index;
    /// storage = new_storage;
    /// ```
    ///
    /// # Algorithm
    ///
    /// 1. Collect all live vectors (non-deleted)
    /// 2. Create a new empty index and storage with the same config
    /// 3. Re-insert all live vectors using regular insert()
    /// 4. Return the new pair
    ///
    /// # Performance
    ///
    /// * Time: O(n log n) where n = live vector count
    /// * Space: 2x index size during compaction (temporary)
    ///
    /// # Memory Safety
    ///
    /// * Returns new pair — no storage/index mismatch possible
    /// * On failure, original index/storage unchanged (caller keeps refs)
    /// * Old index/storage are NOT modified — caller drops when ready
    ///
    /// # Warning
    ///
    /// This is a blocking operation. For WASM, consider running
    /// during idle time or on user action.
    pub fn compact(
        &self,
        storage: &VectorStorage,
    ) -> Result<(HnswIndex, VectorStorage, CompactionResult), GraphError> {
        use std::time::Instant;
        let start = Instant::now();

        let original_deleted = self.deleted_count;
        let original_total = self.node_count();

        // Fast path: no tombstones — return copy
        if original_deleted == 0 {
            // Clone manually since VectorStorage doesn't implement Clone
            let config = self.config.clone();
            let mut new_storage = VectorStorage::new(&config, None);
            let mut new_index = HnswIndex::new(config, &new_storage)?;
            new_index.compaction_threshold = self.compaction_threshold;

            // Re-insert all vectors (this is a rebuild, but preserves order)
            for node in &self.nodes {
                let vec = storage.get_vector(node.vector_id);
                new_index.insert(&vec, &mut new_storage)?;
            }

            return Ok((
                new_index,
                new_storage,
                CompactionResult {
                    tombstones_removed: 0,
                    new_size: original_total,
                    duration_ms: 0,
                },
            ));
        }

        // Collect live vectors' data
        let live_vectors: Vec<Vec<f32>> = self
            .nodes
            .iter()
            .filter(|node| node.deleted == 0)
            .map(|node| {
                let vec = storage.get_vector(node.vector_id);
                vec.into_owned()
            })
            .collect();

        let new_size = live_vectors.len();

        // Build new index AND new storage with same config
        let config = self.config.clone();
        let mut new_storage = VectorStorage::new(&config, None);
        let mut new_index = HnswIndex::new(config, &new_storage)?;

        // Copy compaction threshold from original
        new_index.compaction_threshold = self.compaction_threshold;

        // Re-insert all live vectors (IDs will be remapped)
        for vector in live_vectors {
            new_index.insert(&vector, &mut new_storage)?;
        }

        let duration_ms = start.elapsed().as_millis() as u64;

        Ok((
            new_index,
            new_storage,
            CompactionResult {
                tombstones_removed: original_deleted,
                new_size,
                duration_ms,
            },
        ))
    }

    /// Insert a vector with a specific ID (validation only).
    ///
    /// This method validates that the specified ID doesn't conflict with
    /// existing IDs, then delegates to the standard `insert()` method.
    ///
    /// **Important:** Due to storage design constraints where VectorIds must
    /// match storage slot indices, the returned VectorId is the one assigned
    /// by storage, NOT the requested ID. The `id` parameter is only used
    /// for duplicate validation.
    ///
    /// For actual ID preservation during compaction, the storage would need
    /// to support sparse ID assignment, which is not currently implemented.
    ///
    /// # Arguments
    ///
    /// * `id` - The specific VectorId to validate (not actually used)
    /// * `vector` - The vector data (must match configured dimensions)
    /// * `storage` - Mutable reference to vector storage
    ///
    /// # Returns
    ///
    /// The VectorId assigned by storage (sequential).
    ///
    /// # Errors
    ///
    /// * `InvalidVectorId` - If ID already exists in index or is the sentinel value
    /// * `DimensionMismatch` - If vector dimensions don't match config
    /// * `Storage` - If storage operation fails
    pub fn insert_with_id(
        &mut self,
        id: VectorId,
        vector: &[f32],
        storage: &mut VectorStorage,
    ) -> Result<VectorId, GraphError> {
        // Validate ID is not sentinel
        if id == VectorId::INVALID {
            return Err(GraphError::InvalidVectorId);
        }

        // Validate ID doesn't already exist
        if self.nodes.iter().any(|n| n.vector_id == id) {
            return Err(GraphError::InvalidVectorId);
        }

        // Validate dimensions
        if vector.len() != self.config.dimensions as usize {
            return Err(GraphError::DimensionMismatch {
                expected: self.config.dimensions as usize,
                actual: vector.len(),
            });
        }

        // Delegate to regular insert (which handles all the graph connection logic)
        self.insert(vector, storage)
    }
}

/// Trait for providing vector data by ID.
pub trait VectorProvider {
    /// Returns the vector data for a given ID.
    fn get_vector(&self, id: VectorId) -> Cow<'_, [f32]>;

    /// Returns true if the vector is marked as deleted.
    fn is_deleted(&self, id: VectorId) -> bool {
        let _ = id;
        false
    }

    /// Returns the quantized vector data for a given ID, if available.
    ///
    /// # Returns
    ///
    /// * `Some(&[u8])` - If the provider supports direct quantized access.
    /// * `None` - If not supported or data is not quantized.
    fn get_quantized_vector(&self, id: VectorId) -> Option<&[u8]> {
        let _ = id;
        None
    }

    /// Quantizes a query vector into the provided output buffer.
    ///
    /// # Arguments
    ///
    /// * `query` - The query vector in f32.
    /// * `output` - buffer to write quantized data into.
    ///
    /// # Returns
    ///
    /// * `Some(&[u8])` - The quantized slice (borrowed from output).
    /// * `None` - If quantization is not supported.
    fn quantize_query<'a>(&self, query: &[f32], output: &'a mut Vec<u8>) -> Option<&'a [u8]> {
        let _ = query;
        let _ = output;
        None
    }
}

// ============================================================================
// Batch Insertion Implementation (W11.1 - RFC 0001 v1.1)
// ============================================================================

use crate::batch::BatchInsertable;
use crate::error::BatchError;
use std::collections::HashSet;

impl HnswIndex {
    /// Returns the configured dimensionality of the index.
    #[must_use]
    pub fn dimensions(&self) -> u32 {
        self.config.dimensions
    }

    /// Returns the current number of nodes in the index.
    #[must_use]
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Returns true if the index contains no nodes.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// Returns the maximum capacity of the index (u32::MAX nodes).
    #[must_use]
    pub const fn capacity(&self) -> usize {
        u32::MAX as usize
    }

    /// Checks if a vector ID already exists in the index.
    ///
    /// Returns `true` if the ID exists, `false` otherwise.
    #[must_use]
    pub fn contains_id(&self, id: u64) -> bool {
        self.nodes.iter().any(|n| n.vector_id.0 == id)
    }

    /// Checks if a vector contains invalid floating-point values.
    ///
    /// Returns `Some(reason)` if invalid, `None` if valid.
    fn validate_vector(vector: &[f32]) -> Option<String> {
        for (i, &val) in vector.iter().enumerate() {
            if val.is_nan() {
                return Some(format!("NaN at index {i}"));
            }
            if val.is_infinite() {
                return Some(format!("Infinity at index {i}"));
            }
        }
        None
    }
}

impl BatchInsertable for HnswIndex {
    /// Inserts multiple vectors in a single batch operation.
    ///
    /// This is the full implementation per RFC 0001 v1.2.
    ///
    /// # Algorithm
    ///
    /// 1. Collect iterator to Vec (required for progress tracking)
    /// 2. Pre-validate first vector's dimensionality (fail-fast)
    /// 3. Check capacity constraints
    /// 4. Iterate through vectors with progress callbacks
    /// 5. Actually insert vectors into HNSW graph via storage
    /// 6. Handle errors according to best-effort semantics
    ///
    /// # Error Handling
    ///
    /// - **Fatal errors** (abort immediately):
    ///   - DimensionMismatch on first vector
    ///   - CapacityExceeded
    ///   - InternalError (HNSW invariant violated)
    ///
    /// - **Non-fatal errors** (skip and continue):
    ///   - DuplicateId (within batch or existing in index)
    ///   - InvalidVector (NaN, Inf)
    ///   - DimensionMismatch on subsequent vectors
    fn batch_insert<I, F>(
        &mut self,
        vectors: I,
        storage: &mut VectorStorage,
        mut progress_callback: Option<F>,
    ) -> Result<Vec<u64>, BatchError>
    where
        I: IntoIterator<Item = (u64, Vec<f32>)>,
        F: FnMut(usize, usize),
    {
        // Step 1: Collect iterator to Vec for progress tracking
        let batch: Vec<(u64, Vec<f32>)> = vectors.into_iter().collect();
        let total = batch.len();

        // Early return for empty batch
        if total == 0 {
            return Ok(vec![]);
        }

        // Step 2: Pre-validate first vector's dimensionality (fail-fast)
        let expected_dim = self.config.dimensions as usize;
        let (first_id, first_vec) = &batch[0];
        if first_vec.len() != expected_dim {
            return Err(BatchError::DimensionMismatch {
                expected: expected_dim,
                actual: first_vec.len(),
                vector_id: *first_id,
            });
        }

        // Step 3: Check capacity constraints
        let current_count = self.nodes.len();
        if current_count.saturating_add(total) > self.capacity() {
            return Err(BatchError::CapacityExceeded {
                current: current_count,
                max: self.capacity(),
            });
        }

        // Track IDs we've seen in this batch to detect duplicates within the batch
        let mut seen_ids: HashSet<u64> = HashSet::with_capacity(total);

        // Track successfully inserted IDs
        let mut inserted_ids: Vec<u64> = Vec::with_capacity(total);

        // Step 4: Initial progress callback (0%)
        if let Some(ref mut callback) = progress_callback {
            callback(0, total);
        }

        // Calculate progress intervals (every 10%)
        let progress_interval = if total >= 10 { total / 10 } else { 1 };

        // Step 5: Process each vector
        for (id, vector) in batch {
            // Check for duplicate ID within this batch
            if !seen_ids.insert(id) {
                // Duplicate within batch - skip (non-fatal)
                continue;
            }

            // Check for ID 0 (reserved sentinel)
            if id == 0 {
                // Skip invalid ID (non-fatal)
                continue;
            }

            // Check for duplicate ID in existing index [M1 fix]
            if self.contains_id(id) {
                // Duplicate in existing index - skip (non-fatal)
                continue;
            }

            // Validate dimensionality
            if vector.len() != expected_dim {
                // Skip dimension mismatch (non-fatal after first vector)
                continue;
            }

            // Validate vector data (NaN, Inf)
            if Self::validate_vector(&vector).is_some() {
                // Skip invalid vector (non-fatal)
                continue;
            }

            // Step 6: Actually insert the vector into the HNSW graph [C1 fix]
            match self.insert(&vector, storage) {
                Ok(assigned_id) => {
                    // Use the ID assigned by the insert method
                    inserted_ids.push(assigned_id.0);
                }
                Err(e) => {
                    // Internal error during HNSW insertion - this is fatal
                    return Err(BatchError::InternalError {
                        message: format!("HNSW insert failed for vector {id}: {e}"),
                    });
                }
            }

            // Progress callback at intervals [M3 fix: report inserted count]
            let inserted_count = inserted_ids.len();
            if inserted_count % progress_interval == 0 || inserted_count == 1 {
                if let Some(ref mut callback) = progress_callback {
                    callback(inserted_count, total);
                }
            }
        }

        // Final progress callback (100%)
        if let Some(ref mut callback) = progress_callback {
            callback(inserted_ids.len(), total);
        }

        Ok(inserted_ids)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_send_sync() {
        fn assert_send_sync<T: Send + Sync>() {}
        assert_send_sync::<HnswIndex>();
    }

    #[test]
    fn test_initialization() {
        let config = HnswConfig::new(128);
        // Create storage with matching dimensions
        let storage = VectorStorage::new(&config, None);

        let index = HnswIndex::new(config.clone(), &storage).unwrap();

        assert_eq!(index.node_count(), 0);
        assert_eq!(index.entry_point(), None);
        assert_eq!(index.max_layer(), 0);
    }

    #[test]
    fn test_dimension_mismatch() {
        let config_idx = HnswConfig::new(128);
        let config_store = HnswConfig::new(64);
        let storage = VectorStorage::new(&config_store, None);

        let result = HnswIndex::new(config_idx, &storage);
        assert!(matches!(
            result,
            Err(GraphError::ConfigMismatch {
                expected: 64,
                actual: 128
            })
        ));
    }

    #[test]
    fn test_layer_distribution() {
        // Geometric distribution test
        // m=16 => m_l = 1/ln(16) ≈ 0.36
        // Prob(level > 0) = e^(-1/m_l) = 1/M = 1/16
        // We can't strictly test randomness without huge samples, but we can sanity check.
        let config = HnswConfig::new(128);
        let storage = VectorStorage::new(&config, None);
        let mut index = HnswIndex::new(config, &storage).unwrap();

        let mut levels = vec![0u8; 1000];
        for l in levels.iter_mut() {
            *l = index.get_random_level();
        }

        // Level 0 should be most common
        let l0_count = levels.iter().filter(|&&l| l == 0).count();
        assert!(
            l0_count > 800,
            "Level 0 should be dominant (expected ~93% for M=16)"
        );

        // Max level shouldn't be crazy
        let max = *levels.iter().max().unwrap();
        assert!(max < 16, "Level should be reasonable");
    }

    #[test]
    fn test_neighbor_roundtrip() {
        let config = HnswConfig::new(128);
        let storage = VectorStorage::new(&config, None);
        let mut index = HnswIndex::new(config, &storage).unwrap();

        let id1 = index.add_node(VectorId(1), 0).unwrap();
        let id2 = index.add_node(VectorId(2), 0).unwrap();
        let id3 = index.add_node(VectorId(3), 0).unwrap();

        // Neighbors: [2, 3]
        let neighbors = vec![id2, id3];
        index.set_neighbors(id1, &neighbors).unwrap();

        {
            let node1 = index.get_node(id1).unwrap();
            let retrieved = index.get_neighbors(node1).unwrap();
            assert_eq!(retrieved, neighbors);
        } // Drop node1 borrow

        // Update neighbors: [3] (shrink)
        let neighbors2 = vec![id3];
        index.set_neighbors(id1, &neighbors2).unwrap();

        {
            let node1 = index.get_node(id1).unwrap();
            let retrieved2 = index.get_neighbors(node1).unwrap();
            assert_eq!(retrieved2, neighbors2);
        }

        // Check if free list got populated (cannot check directly as NeighborPool is private,
        // but we can trust neighbor.rs tests for internal logic)
    }

    // ============================================================
    // BATCH INSERT TESTS (W11.1 - RFC 0001 v1.2)
    // ============================================================

    mod batch_insert_tests {
        use super::*;
        use crate::batch::BatchInsertable;

        fn create_test_index_and_storage(dim: u32) -> (HnswIndex, VectorStorage) {
            let config = HnswConfig::new(dim);
            let storage = VectorStorage::new(&config, None);
            let index = HnswIndex::new(config, &storage).unwrap();
            (index, storage)
        }

        #[test]
        fn test_batch_insert_empty() {
            let (mut index, mut storage) = create_test_index_and_storage(128);
            let vectors: Vec<(u64, Vec<f32>)> = vec![];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            assert!(result.is_ok());
            assert!(result.unwrap().is_empty());
            // [M2 fix] Verify graph state
            assert_eq!(index.node_count(), 0);
        }

        #[test]
        fn test_batch_insert_single_vector() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            let vectors = vec![(1u64, vec![1.0, 2.0, 3.0, 4.0])];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 1);
            // [M2 fix] Verify graph state - node was actually inserted
            assert_eq!(index.node_count(), 1);
        }

        #[test]
        fn test_batch_insert_multiple_vectors() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0, 4.0]),
                (2u64, vec![5.0, 6.0, 7.0, 8.0]),
                (3u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 3);
            // [M2 fix] Verify graph state - all 3 nodes inserted
            assert_eq!(index.node_count(), 3);
        }

        #[test]
        fn test_batch_insert_dimension_mismatch_first_vector() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            // First vector has wrong dimension (3 instead of 4)
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0]), // Wrong!
                (2u64, vec![5.0, 6.0, 7.0, 8.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            assert!(result.is_err());
            match result.unwrap_err() {
                BatchError::DimensionMismatch {
                    expected,
                    actual,
                    vector_id,
                } => {
                    assert_eq!(expected, 4);
                    assert_eq!(actual, 3);
                    assert_eq!(vector_id, 1);
                }
                _ => panic!("Expected DimensionMismatch error"),
            }
            // [M2 fix] Verify no vectors were inserted on fatal error
            assert_eq!(index.node_count(), 0);
        }

        #[test]
        fn test_batch_insert_dimension_mismatch_later_vector_skipped() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            // Second vector has wrong dimension - should be skipped
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0, 4.0]),
                (2u64, vec![5.0, 6.0, 7.0]), // Wrong, but not first
                (3u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            // Should succeed with partial results
            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 2);
            // [M2 fix] Verify only 2 nodes inserted (one skipped)
            assert_eq!(index.node_count(), 2);
        }

        #[test]
        fn test_batch_insert_duplicate_id_within_batch() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            // Duplicate IDs within the batch
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0, 4.0]),
                (1u64, vec![5.0, 6.0, 7.0, 8.0]), // Duplicate!
                (2u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            // Should succeed, skipping the duplicate
            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 2);
            // [M2 fix] Verify graph state
            assert_eq!(index.node_count(), 2);
        }

        #[test]
        fn test_batch_insert_duplicate_id_in_existing_index() {
            // [M1 fix] Test duplicate check against existing index
            let (mut index, mut storage) = create_test_index_and_storage(4);

            // First batch
            let vectors1 = vec![(1u64, vec![1.0, 2.0, 3.0, 4.0])];
            let result1 = index.batch_insert(vectors1, &mut storage, None::<fn(usize, usize)>);
            assert!(result1.is_ok());
            assert_eq!(index.node_count(), 1);

            // Second batch with duplicate ID
            let vectors2 = vec![
                (1u64, vec![5.0, 6.0, 7.0, 8.0]), // Duplicate of existing!
                (2u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];
            let result2 = index.batch_insert(vectors2, &mut storage, None::<fn(usize, usize)>);

            // Should succeed, skipping the duplicate
            assert!(result2.is_ok());
            let ids = result2.unwrap();
            assert_eq!(ids.len(), 1); // Only ID 2 was inserted
            assert_eq!(index.node_count(), 2); // Total 2 nodes now
        }

        #[test]
        fn test_batch_insert_invalid_vector_nan() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0, 4.0]),
                (2u64, vec![f32::NAN, 6.0, 7.0, 8.0]), // NaN!
                (3u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            // Should succeed, skipping the NaN vector
            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 2);
            // [M2 fix] Verify graph state
            assert_eq!(index.node_count(), 2);
        }

        #[test]
        fn test_batch_insert_invalid_vector_infinity() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0, 4.0]),
                (2u64, vec![f32::INFINITY, 6.0, 7.0, 8.0]), // Infinity!
                (3u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            // Should succeed, skipping the Infinity vector
            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 2);
            // [M2 fix] Verify graph state
            assert_eq!(index.node_count(), 2);
        }

        #[test]
        fn test_batch_insert_invalid_vector_neg_infinity() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0, 4.0]),
                (2u64, vec![f32::NEG_INFINITY, 6.0, 7.0, 8.0]), // Neg Infinity!
                (3u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            // Should succeed, skipping the NegInfinity vector
            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 2);
            // [M2 fix] Verify graph state
            assert_eq!(index.node_count(), 2);
        }

        #[test]
        fn test_batch_insert_id_zero_skipped() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            // ID 0 is reserved sentinel
            let vectors = vec![
                (0u64, vec![1.0, 2.0, 3.0, 4.0]), // Reserved!
                (1u64, vec![5.0, 6.0, 7.0, 8.0]),
                (2u64, vec![9.0, 10.0, 11.0, 12.0]),
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            // Should succeed, skipping ID 0
            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 2);
            // [M2 fix] Verify graph state
            assert_eq!(index.node_count(), 2);
        }

        #[test]
        fn test_batch_insert_progress_callback_called() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            let vectors: Vec<(u64, Vec<f32>)> =
                (1..=10).map(|i| (i as u64, vec![i as f32; 4])).collect();

            let mut progress_calls: Vec<(usize, usize)> = vec![];

            let result = index.batch_insert(
                vectors,
                &mut storage,
                Some(|current, total| {
                    progress_calls.push((current, total));
                }),
            );

            assert!(result.is_ok());
            // [M2 fix] Verify all 10 nodes inserted
            assert_eq!(index.node_count(), 10);

            // Should have called progress at 0% and at intervals
            assert!(!progress_calls.is_empty());

            // First call should be (0, 10)
            assert_eq!(progress_calls[0], (0, 10));

            // Last call should report inserted count (10, 10)
            let last = progress_calls.last().unwrap();
            assert_eq!(*last, (10, 10));
        }

        #[test]
        fn test_batch_insert_progress_callback_single_vector() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            let vectors = vec![(1u64, vec![1.0, 2.0, 3.0, 4.0])];

            let mut progress_calls: Vec<(usize, usize)> = vec![];

            let result = index.batch_insert(
                vectors,
                &mut storage,
                Some(|current, total| {
                    progress_calls.push((current, total));
                }),
            );

            assert!(result.is_ok());
            // [M2 fix] Verify 1 node inserted
            assert_eq!(index.node_count(), 1);

            // Should have at least two calls: 0% and 100%
            assert!(progress_calls.len() >= 2);
            assert_eq!(progress_calls[0], (0, 1));
            assert!(progress_calls.contains(&(1, 1)));
        }

        #[test]
        fn test_batch_insert_mixed_errors() {
            let (mut index, mut storage) = create_test_index_and_storage(4);
            // Mix of valid and invalid vectors
            let vectors = vec![
                (1u64, vec![1.0, 2.0, 3.0, 4.0]),      // Valid
                (2u64, vec![f32::NAN, 2.0, 3.0, 4.0]), // NaN - skip
                (3u64, vec![3.0, 3.0, 3.0]),           // Wrong dim - skip
                (1u64, vec![4.0, 4.0, 4.0, 4.0]),      // Duplicate - skip
                (0u64, vec![5.0, 5.0, 5.0, 5.0]),      // Reserved ID - skip
                (4u64, vec![6.0, 6.0, 6.0, 6.0]),      // Valid
            ];

            let result = index.batch_insert(vectors, &mut storage, None::<fn(usize, usize)>);

            assert!(result.is_ok());
            let ids = result.unwrap();
            assert_eq!(ids.len(), 2);
            // [M2 fix] Verify graph state
            assert_eq!(index.node_count(), 2);
        }

        #[test]
        fn test_helper_dimensions() {
            let (index, _storage) = create_test_index_and_storage(128);
            assert_eq!(index.dimensions(), 128);
        }

        #[test]
        fn test_helper_len_empty() {
            let (index, _storage) = create_test_index_and_storage(128);
            assert_eq!(index.len(), 0);
            assert!(index.is_empty());
        }

        #[test]
        fn test_helper_capacity() {
            let (index, _storage) = create_test_index_and_storage(128);
            assert_eq!(index.capacity(), u32::MAX as usize);
        }

        #[test]
        fn test_helper_contains_id() {
            let (mut index, mut storage) = create_test_index_and_storage(4);

            // Initially empty
            assert!(!index.contains_id(1));

            // Insert via single insert
            let _ = index.insert(&[1.0, 2.0, 3.0, 4.0], &mut storage);

            // Now the first ID should exist (insert assigns sequential IDs starting at 1)
            assert!(index.node_count() == 1);
        }

        #[test]
        fn test_validate_vector_valid() {
            let vector = vec![1.0, 2.0, 3.0, 4.0];
            assert!(HnswIndex::validate_vector(&vector).is_none());
        }

        #[test]
        fn test_validate_vector_nan() {
            let vector = vec![1.0, f32::NAN, 3.0, 4.0];
            let result = HnswIndex::validate_vector(&vector);
            assert!(result.is_some());
            assert!(result.unwrap().contains("NaN"));
        }

        #[test]
        fn test_validate_vector_infinity() {
            let vector = vec![1.0, f32::INFINITY, 3.0, 4.0];
            let result = HnswIndex::validate_vector(&vector);
            assert!(result.is_some());
            assert!(result.unwrap().contains("Infinity"));
        }
    }

    // ============================================================
    // SOFT DELETE TESTS (W16.2 - RFC-001)
    // ============================================================

    mod delete_tests {
        use super::*;

        fn create_test_index() -> (HnswIndex, VectorStorage) {
            let config = HnswConfig::new(4);
            let storage = VectorStorage::new(&config, None);
            let index = HnswIndex::new(config, &storage).unwrap();
            (index, storage)
        }

        #[test]
        fn test_soft_delete_marks_node() {
            let (mut index, mut storage) = create_test_index();
            let vec = vec![1.0, 2.0, 3.0, 4.0];
            let id = index.insert(&vec, &mut storage).unwrap();

            assert!(!index.is_deleted(id).unwrap());
            assert!(index.soft_delete(id).unwrap());
            assert!(index.is_deleted(id).unwrap());
        }

        #[test]
        fn test_soft_delete_idempotent() {
            let (mut index, mut storage) = create_test_index();
            let vec = vec![1.0, 2.0, 3.0, 4.0];
            let id = index.insert(&vec, &mut storage).unwrap();

            assert!(index.soft_delete(id).unwrap()); // First: true
            assert!(!index.soft_delete(id).unwrap()); // Second: false
            assert_eq!(index.deleted_count(), 1); // Still 1
        }

        #[test]
        fn test_soft_delete_nonexistent_fails() {
            let (mut index, _storage) = create_test_index();
            let result = index.soft_delete(VectorId(999));
            assert!(result.is_err());
            assert!(matches!(result.unwrap_err(), GraphError::InvalidVectorId));
        }

        #[test]
        fn test_deleted_count() {
            let (mut index, mut storage) = create_test_index();

            // Insert 3 vectors
            let id1 = index.insert(&[1.0, 0.0, 0.0, 0.0], &mut storage).unwrap();
            let id2 = index.insert(&[0.0, 1.0, 0.0, 0.0], &mut storage).unwrap();
            let _id3 = index.insert(&[0.0, 0.0, 1.0, 0.0], &mut storage).unwrap();

            assert_eq!(index.deleted_count(), 0);
            assert_eq!(index.node_count(), 3);

            // Delete 2
            index.soft_delete(id1).unwrap();
            index.soft_delete(id2).unwrap();

            assert_eq!(index.deleted_count(), 2);
            assert_eq!(index.live_count(), 1);
        }

        #[test]
        fn test_tombstone_ratio() {
            let (mut index, mut storage) = create_test_index();

            // Empty index
            assert_eq!(index.tombstone_ratio(), 0.0);

            // Insert 4 vectors
            let mut ids = Vec::new();
            for i in 0..4 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            assert_eq!(index.tombstone_ratio(), 0.0);

            // Delete 1 of 4 = 25%
            index.soft_delete(ids[0]).unwrap();
            assert!((index.tombstone_ratio() - 0.25).abs() < 0.01);

            // Delete 2 of 4 = 50%
            index.soft_delete(ids[1]).unwrap();
            assert!((index.tombstone_ratio() - 0.50).abs() < 0.01);
        }

        #[test]
        fn test_is_deleted_nonexistent_fails() {
            let (index, _storage) = create_test_index();
            let result = index.is_deleted(VectorId(999));
            assert!(result.is_err());
            assert!(matches!(result.unwrap_err(), GraphError::InvalidVectorId));
        }

        #[test]
        fn test_live_count() {
            let (mut index, mut storage) = create_test_index();

            // Insert 5
            let mut ids = Vec::new();
            for i in 0..5 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete 2
            index.soft_delete(ids[0]).unwrap();
            index.soft_delete(ids[1]).unwrap();

            assert_eq!(index.node_count(), 5);
            assert_eq!(index.deleted_count(), 2);
            assert_eq!(index.live_count(), 3);
        }

        #[test]
        fn test_get_node_by_vector_id_helper() {
            let (mut index, mut storage) = create_test_index();
            let id = index.insert(&[1.0, 2.0, 3.0, 4.0], &mut storage).unwrap();

            // Should find existing node
            let node = index.get_node_by_vector_id(id);
            assert!(node.is_ok());
            assert_eq!(node.unwrap().vector_id, id);

            // Should fail for non-existent
            let bad = index.get_node_by_vector_id(VectorId(999));
            assert!(bad.is_err());
        }

        #[test]
        fn test_deleted_field_is_zero_by_default() {
            let (mut index, mut storage) = create_test_index();
            let id = index.insert(&[1.0, 2.0, 3.0, 4.0], &mut storage).unwrap();

            let node = index.get_node_by_vector_id(id).unwrap();
            assert_eq!(node.deleted, 0);
        }

        #[test]
        fn test_deleted_field_set_to_one_after_delete() {
            let (mut index, mut storage) = create_test_index();
            let id = index.insert(&[1.0, 2.0, 3.0, 4.0], &mut storage).unwrap();

            index.soft_delete(id).unwrap();

            let node = index.get_node_by_vector_id(id).unwrap();
            assert_eq!(node.deleted, 1);
        }

        #[test]
        fn test_delete_invalid_vector_id_zero() {
            let (mut index, _storage) = create_test_index();
            // VectorId(0) is INVALID sentinel
            let result = index.soft_delete(VectorId(0));
            assert!(result.is_err());
        }

        // ============================================================
        // ADJUSTED K TESTS (W16.3)
        // ============================================================

        #[test]
        fn test_adjusted_k_no_tombstones() {
            let (index, _storage) = create_test_index();
            // No deletions -> k unchanged
            assert_eq!(index.adjusted_k(10), 10);
            assert_eq!(index.adjusted_k(1), 1);
            assert_eq!(index.adjusted_k(100), 100);
        }

        #[test]
        fn test_adjusted_k_with_tombstones() {
            let (mut index, mut storage) = create_test_index();

            // Insert 10 vectors
            let mut ids = Vec::new();
            for i in 0..10 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete 5 of 10 = 50% tombstones
            for i in 0..5 {
                index.soft_delete(ids[i]).unwrap();
            }

            // 50% tombstones → 2x multiplier
            // adjusted_k(10) = ceil(10 / 0.5) = 20
            let adjusted = index.adjusted_k(10);
            assert!(
                adjusted >= 18 && adjusted <= 22,
                "Expected ~20, got {adjusted}"
            );
        }

        #[test]
        fn test_adjusted_k_capped_at_10x() {
            let (mut index, mut storage) = create_test_index();

            // Insert 100 vectors
            let mut ids = Vec::new();
            for i in 0..100 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete 95 of 100 = 95% tombstones
            for i in 0..95 {
                index.soft_delete(ids[i]).unwrap();
            }

            // Should cap at 10x, not 20x
            let adjusted = index.adjusted_k(10);
            assert_eq!(adjusted, 100, "Should be capped at 10x (100)");
        }

        #[test]
        fn test_adjusted_k_10_percent_tombstones() {
            let (mut index, mut storage) = create_test_index();

            // Insert 10 vectors
            let mut ids = Vec::new();
            for i in 0..10 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete 1 of 10 = 10% tombstones
            index.soft_delete(ids[0]).unwrap();

            // 10% tombstones → 1.11x multiplier
            // adjusted_k(10) = ceil(10 / 0.9) = ceil(11.11) = 12
            let adjusted = index.adjusted_k(10);
            assert!(
                adjusted >= 11 && adjusted <= 13,
                "Expected ~12, got {adjusted}"
            );
        }

        // ============================================================
        // BOUNDARY VALUE TESTS (m3 fix)
        // ============================================================

        #[test]
        fn test_adjusted_k_boundary_zero_tombstones() {
            let (mut index, mut storage) = create_test_index();

            // Insert vectors but delete none (0% tombstones)
            for i in 0..10 {
                index.insert(&[i as f32; 4], &mut storage).unwrap();
            }

            // 0% tombstones → no adjustment
            assert_eq!(index.adjusted_k(5), 5);
            assert_eq!(index.adjusted_k(10), 10);
            assert_eq!(index.tombstone_ratio(), 0.0);
        }

        #[test]
        fn test_adjusted_k_boundary_50_percent() {
            let (mut index, mut storage) = create_test_index();

            let mut ids = Vec::new();
            for i in 0..10 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete exactly 5 of 10 = 50%
            for i in 0..5 {
                index.soft_delete(ids[i]).unwrap();
            }

            // 50% tombstones → 2x
            // adjusted_k(10) = 10 * 10 / 5 = 20
            let adjusted = index.adjusted_k(10);
            assert_eq!(adjusted, 20, "50% tombstones should give 2x");
            assert!((index.tombstone_ratio() - 0.5).abs() < 0.01);
        }

        #[test]
        fn test_adjusted_k_boundary_90_percent() {
            let (mut index, mut storage) = create_test_index();

            let mut ids = Vec::new();
            for i in 0..10 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete 9 of 10 = 90%
            for i in 0..9 {
                index.soft_delete(ids[i]).unwrap();
            }

            // 90% tombstones → 10x
            // adjusted_k(10) = 10 * 10 / 1 = 100
            // Capped at 10x multiplier = 100
            let adjusted = index.adjusted_k(10);
            assert_eq!(adjusted, 100, "90% tombstones should give 10x (capped)");
            assert!((index.tombstone_ratio() - 0.9).abs() < 0.01);
        }

        #[test]
        fn test_adjusted_k_boundary_all_deleted() {
            let (mut index, mut storage) = create_test_index();

            let mut ids = Vec::new();
            for i in 0..5 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete all = 100% tombstones
            for id in &ids {
                index.soft_delete(*id).unwrap();
            }

            // All deleted → returns k (search will return empty anyway)
            let adjusted = index.adjusted_k(10);
            assert_eq!(adjusted, 10, "All deleted should return original k");
            assert_eq!(index.live_count(), 0);
            assert!((index.tombstone_ratio() - 1.0).abs() < 0.01);
        }

        #[test]
        fn test_adjusted_k_large_k_small_index() {
            let (mut index, mut storage) = create_test_index();

            // Insert only 5 vectors
            let mut ids = Vec::new();
            for i in 0..5 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete 2 = 40% tombstones
            index.soft_delete(ids[0]).unwrap();
            index.soft_delete(ids[1]).unwrap();

            // Request k=100, but only 5 vectors in index
            // adjusted_k(100) = 100 * 5 / 3 ≈ 166
            // Capped at 10x = 1000
            // Note: adjusted_k controls internal effort, not final result count
            let adjusted = index.adjusted_k(100);
            assert!(
                adjusted >= 166 && adjusted <= 168,
                "Should compute ~166 for 40% tombstones, got {adjusted}"
            );
        }

        #[test]
        fn test_adjusted_k_uses_constant() {
            // Verify MAX_ADJUSTED_K_MULTIPLIER is used
            assert_eq!(HnswIndex::MAX_ADJUSTED_K_MULTIPLIER, 10);
        }

        #[test]
        fn test_adjusted_k_integer_precision() {
            // Test that integer arithmetic doesn't lose precision
            let (mut index, mut storage) = create_test_index();

            let mut ids = Vec::new();
            for i in 0..100 {
                let id = index.insert(&[i as f32; 4], &mut storage).unwrap();
                ids.push(id);
            }

            // Delete 33 of 100 = 33%
            for i in 0..33 {
                index.soft_delete(ids[i]).unwrap();
            }

            // adjusted_k(10) = 10 * 100 / 67 = 14.925... → 14
            let adjusted = index.adjusted_k(10);
            // Should be close to 15 (1.49x)
            assert!(
                adjusted >= 14 && adjusted <= 16,
                "33% tombstones: expected ~15, got {adjusted}"
            );
        }
    }
}