15791628916

Committed 21 Jun 2025 03:28AM UTC coverage: 94.579% (-0.1%) from 94.725%

Build # 15791628916

Build Type

Pull #12

github

Committed by

web-flow

Commit Message

Merge af3ccbf83 into ce0622484

Pull Request Pull Request #12: Rework node add/remove

Run Details

194 of 263 new or added lines in 5 files covered. (73.76%)

6 existing lines in 1 file now uncovered.

6543 of 6918 relevant lines covered (94.58%)

38.68 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.88

/src/matrix/bit_map_matrix.rs

use crate::{
    containers::maps::MapTrait,
    graph::{Graph, GraphError, GraphWithMutableNodes, NodeIndex},
};

/// A bit-packed adjacency matrix with arbitrary node indices
///
/// This struct combines a [`crate::matrix::bit_matrix::BitMatrix`] for efficient edge storage with an index map
/// that allows arbitrary node indices. It provides the same memory efficiency as
/// BitMatrix while supporting non-contiguous node identifiers.
pub struct BitMapMatrix<const N: usize, const R: usize, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    bitmap: super::bit_matrix::BitMatrix<N, R>,
    index_map: M,
    phantom: core::marker::PhantomData<NI>,
}

impl<const N: usize, const R: usize, NI, M> BitMapMatrix<N, R, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    /// Creates a new BitMapMatrix with the given bitmap and index mapping
    ///
    /// Validates that all indices in the index_map are within valid bounds for the BitMatrix.
    /// BitMatrix supports node indices in the range 0..8*N.
    pub fn new(
        bitmap: super::bit_matrix::BitMatrix<N, R>,
        index_map: M,
    ) -> Result<Self, GraphError<NI>> {
        // BitMatrix supports indices in range 0..8*N
        let max_valid_index = 8 * N;
        for (node, idx) in index_map.iter() {
            if *idx >= max_valid_index {
                return Err(GraphError::IndexOutOfBounds(*idx, *node));
            }
        }
        Ok(Self::new_unchecked(bitmap, index_map))
    }

    /// Creates a new BitMapMatrix with the given bitmap and index mapping without bounds checking
    ///
    /// # Safety
    /// The caller must ensure that all indices in the index_map are within valid bounds
    /// for the BitMatrix (0..8*N).
    pub fn new_unchecked(bitmap: super::bit_matrix::BitMatrix<N, R>, index_map: M) -> Self {
        Self {
            bitmap,
            index_map,
            phantom: core::marker::PhantomData,
        }
    }
}

impl<const N: usize, const R: usize, NI, M> Graph<NI> for BitMapMatrix<N, R, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    type Error = GraphError<NI>;

    fn iter_nodes(&self) -> Result<impl Iterator<Item = NI>, Self::Error> {
        Ok(self.index_map.iter().map(|(&k, _)| k))
    }

    fn contains_node(&self, node: NI) -> Result<bool, Self::Error> {
        Ok(self.index_map.contains_key(&node))
    }

    /// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
    ///
    /// TODO: Store back-index ?
    fn iter_edges(&self) -> Result<impl Iterator<Item = (NI, NI)>, Self::Error> {
        Ok(self
            .index_map
            .iter()
            .flat_map(move |(&from_node, &from_idx)| {
                self.index_map
                    .iter()
                    .filter_map(move |(&to_node, &to_idx)| {
                        if self.bitmap.get(from_idx, to_idx) {
                            Some((from_node, to_node))
                        } else {
                            None
                        }
                    })
            }))
    }

    /// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
    ///
    /// TODO: Store back-index ?
    fn outgoing_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {
        // Fast direct lookup of matrix index for this node
        let matrix_idx = self.index_map.get(&node).copied();

        // Get outgoing edges from bitmap, using usize::MAX as fallback (will be filtered out)
        // Note: BitMatrix::get handles out-of-bounds indices safely by returning false,
        // and the filter below ensures we don't return edges for non-existent nodes.
        // The map_err is needed to convert GraphError<usize> to GraphError<NI> for the trait implementation.
        let outgoing = self
            .bitmap
            .outgoing_edges(matrix_idx.unwrap_or(usize::MAX))
            .map_err(|_| GraphError::NodeNotFound(node))?;

        // Map matrix indices back to node indices by checking all nodes
        Ok(outgoing
            .filter(move |_| matrix_idx.is_some()) // Filter out everything if node doesn't exist
            .filter_map(move |target_idx| {
                self.index_map
                    .iter()
                    .find(|(_, &idx)| idx == target_idx)
                    .map(|(&node, _)| node)
            }))
    }

    /// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
    ///
    /// TODO: Store back-index ?
    fn incoming_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {
        // Fast direct lookup of matrix index for this node
        let matrix_idx = self.index_map.get(&node).copied();

        // Get incoming edges from bitmap, using 0 as fallback (will be filtered out)
        let incoming = self
            .bitmap
            .incoming_edges(matrix_idx.unwrap_or(usize::MAX))
            .map_err(|_| GraphError::NodeNotFound(node))?;

        // Map matrix indices back to node indices by checking all nodes
        Ok(incoming
            .filter(move |_| matrix_idx.is_some()) // Filter out everything if node doesn't exist
            .filter_map(move |source_idx| {
                self.index_map
                    .iter()
                    .find(|(_, &idx)| idx == source_idx)
                    .map(|(&node, _)| node)
            }))
    }
}

impl<const N: usize, const R: usize, NI, M> GraphWithMutableNodes<NI> for BitMapMatrix<N, R, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    fn add_node(&mut self, node: NI) -> Result<(), Self::Error> {
        // Check if node already exists
        if self.index_map.contains_key(&node) {
            return Err(GraphError::DuplicateNode(node));
        }

        // Find an unused matrix index (BitMatrix supports 0..8*N)
        let max_index = 8 * N;
        let unused_index = (0..max_index)
            .find(|&idx| !self.index_map.iter().any(|(_, &used_idx)| used_idx == idx))
            .ok_or(GraphError::OutOfCapacity)?;

        // Insert the new node mapping
        self.index_map
            .insert(node, unused_index)
            .map_err(|_| GraphError::OutOfCapacity)?;

        Ok(())
    }

    fn remove_node(&mut self, node: NI) -> Result<(), Self::Error> {
        // Check if node exists
        if !self.index_map.contains_key(&node) {
            return Err(GraphError::NodeNotFound(node));
        }

        // Check if node has incoming edges
        if self.incoming_edges(node)?.next().is_some() {
            return Err(GraphError::NodeHasIncomingEdges(node));
        }

        // Remove the node mapping (bit matrix position becomes available for reuse)
        self.index_map.remove(&node);
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::containers::maps::staticdict::Dictionary;
    use crate::tests::{collect, collect_sorted};

    #[test]
    fn test_bit_map_matrix_basic() {
        // Create a simple 2x2 bit matrix with edges: 0->0, 0->1, 1->0
        let bits = [
            [0b00000011u8], // Row 0: edges to nodes 0 and 1
            [0b00000001u8], // Row 1: edge to node 0
            [0b00000000u8], // Row 2: no edges
            [0b00000000u8], // Row 3: no edges
            [0b00000000u8], // Row 4: no edges
            [0b00000000u8], // Row 5: no edges
            [0b00000000u8], // Row 6: no edges
            [0b00000000u8], // Row 7: no edges
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Map custom node IDs 'A','B' to matrix indices 0,1
        let mut index_map = Dictionary::<char, usize, 8>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test node iteration
        let mut nodes = ['\0'; 8];
        let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice.len(), 2);

        // Check both nodes are present (order may vary)
        assert!(nodes_slice.contains(&'A'));
        assert!(nodes_slice.contains(&'B'));

        // Test contains_node
        assert!(bit_map_matrix.contains_node('A').unwrap());
        assert!(bit_map_matrix.contains_node('B').unwrap());
        assert!(!bit_map_matrix.contains_node('C').unwrap());

        // Test outgoing edges
        let mut outgoing_a = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('A').unwrap(), &mut outgoing_a);
        assert_eq!(outgoing_slice.len(), 2); // A->A, A->B

        let mut outgoing_b = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('B').unwrap(), &mut outgoing_b);
        assert_eq!(outgoing_slice, &['A']); // B->A
    }

    #[test]
    fn test_bit_map_matrix_empty() {
        // Empty bitmap
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Empty index map
        let index_map = Dictionary::<u32, usize, 8>::new();
        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Should have no nodes
        assert_eq!(bit_map_matrix.iter_nodes().unwrap().count(), 0);

        // Should have no edges
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);

        // Should not contain any nodes
        assert!(!bit_map_matrix.contains_node(42).unwrap());
    }

    #[test]
    fn test_bit_map_matrix_nonexistent_node() {
        let bits = [
            [0b00000001u8], // Row 0: edge to node 0
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        let mut index_map = Dictionary::<u32, usize, 8>::new();
        index_map.insert(100, 0).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test outgoing edges for non-existent node should return empty iterator
        assert_eq!(bit_map_matrix.outgoing_edges(999).unwrap().count(), 0);

        // Test incoming edges for non-existent node should return empty iterator
        assert_eq!(bit_map_matrix.incoming_edges(999).unwrap().count(), 0);
    }

    #[test]
    fn test_bit_map_matrix_incoming_edges() {
        // Create a matrix with edges: A->A, A->B, B->A
        let bits = [
            [0b00000011u8], // Row 0: edges to nodes 0 and 1 (A->A, A->B)
            [0b00000001u8], // Row 1: edge to node 0 (B->A)
            [0b00000000u8], // Row 2: no edges
            [0b00000000u8], // Row 3: no edges
            [0b00000000u8], // Row 4: no edges
            [0b00000000u8], // Row 5: no edges
            [0b00000000u8], // Row 6: no edges
            [0b00000000u8], // Row 7: no edges
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Map custom node IDs 'A','B' to matrix indices 0,1
        let mut index_map = Dictionary::<char, usize, 8>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test incoming edges to A (should be from A and B)
        let mut incoming_a = ['\0'; 8];
        let incoming_slice = collect(bit_map_matrix.incoming_edges('A').unwrap(), &mut incoming_a);
        assert_eq!(incoming_slice.len(), 2); // A->A, B->A
        assert!(incoming_slice.contains(&'A'));
        assert!(incoming_slice.contains(&'B'));

        // Test incoming edges to B (should be from A only)
        let mut incoming_b = ['\0'; 8];
        let incoming_slice = collect(bit_map_matrix.incoming_edges('B').unwrap(), &mut incoming_b);
        assert_eq!(incoming_slice, &['A']); // A->B
    }

    #[test]
    fn test_bit_map_matrix_outgoing_edges_bounds() {
        // Create a matrix with edges: A->A, A->B
        let bits = [
            [0b00000011u8], // Row 0: edges to nodes 0 and 1 (A->A, A->B)
            [0b00000000u8], // Row 1: no edges
            [0b00000000u8], // Row 2: no edges
            [0b00000000u8], // Row 3: no edges
            [0b00000000u8], // Row 4: no edges
            [0b00000000u8], // Row 5: no edges
            [0b00000000u8], // Row 6: no edges
            [0b00000000u8], // Row 7: no edges
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);

        // Map custom node IDs 'A','B' to matrix indices 0,1
        let mut index_map = Dictionary::<char, usize, 8>::new();
        index_map.insert('A', 0).unwrap();
        index_map.insert('B', 1).unwrap();

        let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        // Test outgoing edges for non-existent node with usize::MAX fallback
        // This should not panic and should return an empty iterator
        let mut outgoing = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('C').unwrap(), &mut outgoing);
        assert_eq!(outgoing_slice.len(), 0);

        // Test outgoing edges for non-existent node with 0 fallback
        // This should also not panic and should return an empty iterator
        let mut outgoing = ['\0'; 8];
        let outgoing_slice = collect(bit_map_matrix.outgoing_edges('D').unwrap(), &mut outgoing);
        assert_eq!(outgoing_slice.len(), 0);
    }

    #[test]
    fn test_add_node_to_empty_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let index_map = Dictionary::<u32, usize, 10>::new();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node(42).unwrap();

        let mut nodes = [0u32; 2];
        let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[42]);
        assert_eq!(bit_map_matrix.outgoing_edges(42).unwrap().count(), 0);
    }

    #[test]
    fn test_add_node_to_existing_bit_matrix() {
        let bits = [
            [0b00000001u8], // Row 0: edge to node 0 (self-loop)
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
            [0b00000000u8],
        ];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<char, usize, 10>::new();
        index_map.insert('A', 0).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node('B').unwrap();

        let mut nodes = ['\0'; 4];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &['A', 'B']);
        assert_eq!(bit_map_matrix.outgoing_edges('B').unwrap().count(), 0);
        assert_eq!(bit_map_matrix.outgoing_edges('A').unwrap().count(), 1);
    }

    #[test]
    fn test_add_duplicate_node_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 8>::new();
        index_map.insert(100, 0).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        let result = bit_map_matrix.add_node(100);
        assert!(matches!(result, Err(GraphError::DuplicateNode(100))));

        let mut nodes = [0u32; 2];
        let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[100]);
    }

    #[test]
    fn test_add_node_capacity_exceeded_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 8>::new();
        for i in 0..8 {
            index_map.insert(i as u32, i).unwrap();
        }

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();

        let result = bit_map_matrix.add_node(999);
        assert!(matches!(result, Err(GraphError::OutOfCapacity)));

        let mut nodes = [0u32; 10];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[0, 1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_add_multiple_nodes_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let index_map = Dictionary::<char, usize, 10>::new();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node('X').unwrap();
        bit_map_matrix.add_node('Y').unwrap();
        bit_map_matrix.add_node('Z').unwrap();

        let mut nodes = ['\0'; 4];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &['X', 'Y', 'Z']);
        assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);
    }

    #[test]
    fn test_add_node_fills_gaps_bit_matrix() {
        let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];
        let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);
        let mut index_map = Dictionary::<u32, usize, 10>::new();
        index_map.insert(10, 0).unwrap();
        index_map.insert(30, 2).unwrap();
        index_map.insert(50, 4).unwrap();

        let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();
        bit_map_matrix.add_node(20).unwrap();

        let mut nodes = [0u32; 6];
        let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);
        assert_eq!(nodes_slice, &[10, 20, 30, 50]);
    }
}

1	use crate::{
2	containers::maps::MapTrait,
3	graph::{Graph, GraphError, GraphWithMutableNodes, NodeIndex},
4	};
5
6	/// A bit-packed adjacency matrix with arbitrary node indices
7	///
8	/// This struct combines a [`crate::matrix::bit_matrix::BitMatrix`] for efficient edge storage with an index map
9	/// that allows arbitrary node indices. It provides the same memory efficiency as
10	/// BitMatrix while supporting non-contiguous node identifiers.
11	pub struct BitMapMatrix<const N: usize, const R: usize, NI, M>
12	where
13	NI: NodeIndex,
14	M: MapTrait<NI, usize>,
15	{
16	bitmap: super::bit_matrix::BitMatrix<N, R>,
17	index_map: M,
18	phantom: core::marker::PhantomData<NI>,
19	}
20
21	impl<const N: usize, const R: usize, NI, M> BitMapMatrix<N, R, NI, M>
22	where
23	NI: NodeIndex,
24	M: MapTrait<NI, usize>,
25	{
26	/// Creates a new BitMapMatrix with the given bitmap and index mapping
27	///
28	/// Validates that all indices in the index_map are within valid bounds for the BitMatrix.
29	/// BitMatrix supports node indices in the range 0..8*N.
30	pub fn new(	12✔
31	bitmap: super::bit_matrix::BitMatrix<N, R>,	12✔
32	index_map: M,	12✔
33	) -> Result<Self, GraphError<NI>> {	12✔
34	// BitMatrix supports indices in range 0..8*N	12✔
35	let max_valid_index = 8 * N;	12✔
36	for (node, idx) in index_map.iter() {	28✔
37	if *idx >= max_valid_index {	28✔
38	return Err(GraphError::IndexOutOfBounds(idx, node));	×
39	}	28✔
40	}
41	Ok(Self::new_unchecked(bitmap, index_map))	12✔
42	}	12✔
43
44	/// Creates a new BitMapMatrix with the given bitmap and index mapping without bounds checking
45	///
46	/// # Safety
47	/// The caller must ensure that all indices in the index_map are within valid bounds
48	/// for the BitMatrix (0..8*N).
49	pub fn new_unchecked(bitmap: super::bit_matrix::BitMatrix<N, R>, index_map: M) -> Self {	12✔
50	Self {	12✔
51	bitmap,	12✔
52	index_map,	12✔
53	phantom: core::marker::PhantomData,	12✔
54	}	12✔
55	}	12✔
56	}
57
58	impl<const N: usize, const R: usize, NI, M> Graph<NI> for BitMapMatrix<N, R, NI, M>
59	where
60	NI: NodeIndex,
61	M: MapTrait<NI, usize>,
62	{
63	type Error = GraphError<NI>;
64
65	fn iter_nodes(&self) -> Result<impl Iterator<Item = NI>, Self::Error> {	8✔
66	Ok(self.index_map.iter().map(\|(&k, _)\| k))	21✔
67	}	8✔
68
69	fn contains_node(&self, node: NI) -> Result<bool, Self::Error> {	22✔
70	Ok(self.index_map.contains_key(&node))	22✔
71	}	22✔
72
73	/// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
74	///
75	/// TODO: Store back-index ?
76	fn iter_edges(&self) -> Result<impl Iterator<Item = (NI, NI)>, Self::Error> {	2✔
77	Ok(self	2✔
78	.index_map	2✔
79	.iter()	2✔
80	.flat_map(move \|(&from_node, &from_idx)\| {	3✔
81	self.index_map	3✔
82	.iter()	3✔
83	.filter_map(move \|(&to_node, &to_idx)\| {	9✔
84	if self.bitmap.get(from_idx, to_idx) {	9✔
85	Some((from_node, to_node))	×
86	} else {
87	None	9✔
88	}
89	})	9✔
90	}))	3✔
91	}	2✔
92
93	/// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
94	///
95	/// TODO: Store back-index ?
96	fn outgoing_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {	53✔
97	// Fast direct lookup of matrix index for this node	53✔
98	let matrix_idx = self.index_map.get(&node).copied();	53✔
99
100	// Get outgoing edges from bitmap, using usize::MAX as fallback (will be filtered out)
101	// Note: BitMatrix::get handles out-of-bounds indices safely by returning false,
102	// and the filter below ensures we don't return edges for non-existent nodes.
103	// The map_err is needed to convert GraphError<usize> to GraphError<NI> for the trait implementation.
104	let outgoing = self	53✔
105	.bitmap	53✔
106	.outgoing_edges(matrix_idx.unwrap_or(usize::MAX))	53✔
107	.map_err(\|_\| GraphError::NodeNotFound(node))?;	53✔
108
109	// Map matrix indices back to node indices by checking all nodes
110	Ok(outgoing	53✔
111	.filter(move \|_\| matrix_idx.is_some()) // Filter out everything if node doesn't exist	53✔
112	.filter_map(move \|target_idx\| {	53✔
113	self.index_map	43✔
114	.iter()	43✔
115	.find(\|(_, &idx)\| idx == target_idx)	138✔
116	.map(\|(&node, _)\| node)	43✔
117	}))	53✔
118	}	53✔
119
120	/// Note: Uses linear search for backindexing matrix indices to NI, this is slow.
121	///
122	/// TODO: Store back-index ?
123	fn incoming_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {	3✔
124	// Fast direct lookup of matrix index for this node	3✔
125	let matrix_idx = self.index_map.get(&node).copied();	3✔
126
127	// Get incoming edges from bitmap, using 0 as fallback (will be filtered out)
128	let incoming = self	3✔
129	.bitmap	3✔
130	.incoming_edges(matrix_idx.unwrap_or(usize::MAX))	3✔
131	.map_err(\|_\| GraphError::NodeNotFound(node))?;	3✔
132
133	// Map matrix indices back to node indices by checking all nodes
134	Ok(incoming	3✔
135	.filter(move \|_\| matrix_idx.is_some()) // Filter out everything if node doesn't exist	3✔
136	.filter_map(move \|source_idx\| {	3✔
137	self.index_map	3✔
138	.iter()	3✔
139	.find(\|(_, &idx)\| idx == source_idx)	4✔
140	.map(\|(&node, _)\| node)	3✔
141	}))	3✔
142	}	3✔
143	}
144
145	impl<const N: usize, const R: usize, NI, M> GraphWithMutableNodes<NI> for BitMapMatrix<N, R, NI, M>
146	where
147	NI: NodeIndex,
148	M: MapTrait<NI, usize>,
149	{
150	fn add_node(&mut self, node: NI) -> Result<(), Self::Error> {	8✔
151	// Check if node already exists	8✔
152	if self.index_map.contains_key(&node) {	8✔
153	return Err(GraphError::DuplicateNode(node));	1✔
154	}	7✔
155		7✔
156	// Find an unused matrix index (BitMatrix supports 0..8*N)	7✔
157	let max_index = 8 * N;	7✔
158	let unused_index = (0..max_index)	7✔
159	.find(\|&idx\| !self.index_map.iter().any(\|(_, &used_idx)\| used_idx == idx))	49✔
160	.ok_or(GraphError::OutOfCapacity)?;	7✔
161
162	// Insert the new node mapping
163	self.index_map	6✔
164	.insert(node, unused_index)	6✔
165	.map_err(\|_\| GraphError::OutOfCapacity)?;	6✔
166
167	Ok(())	6✔
168	}	8✔
169
NEW 170	fn remove_node(&mut self, node: NI) -> Result<(), Self::Error> {	×
NEW 171	// Check if node exists	×
NEW 172	if !self.index_map.contains_key(&node) {	×
NEW 173	return Err(GraphError::NodeNotFound(node));	×
NEW 174	}	×
NEW 175		×
NEW 176	// Check if node has incoming edges	×
NEW 177	if self.incoming_edges(node)?.next().is_some() {	×
NEW 178	return Err(GraphError::NodeHasIncomingEdges(node));	×
NEW 179	}	×
NEW 180		×
NEW 181	// Remove the node mapping (bit matrix position becomes available for reuse)	×
NEW 182	self.index_map.remove(&node);	×
NEW 183	Ok(())	×
NEW 184	}	×
185	}
186
187	#[cfg(test)]
188	mod tests {
189	use super::*;
190	use crate::containers::maps::staticdict::Dictionary;
191	use crate::tests::{collect, collect_sorted};
192
193	#[test]
194	fn test_bit_map_matrix_basic() {	1✔
195	// Create a simple 2x2 bit matrix with edges: 0->0, 0->1, 1->0	1✔
196	let bits = [	1✔
197	[0b00000011u8], // Row 0: edges to nodes 0 and 1	1✔
198	[0b00000001u8], // Row 1: edge to node 0	1✔
199	[0b00000000u8], // Row 2: no edges	1✔
200	[0b00000000u8], // Row 3: no edges	1✔
201	[0b00000000u8], // Row 4: no edges	1✔
202	[0b00000000u8], // Row 5: no edges	1✔
203	[0b00000000u8], // Row 6: no edges	1✔
204	[0b00000000u8], // Row 7: no edges	1✔
205	];	1✔
206	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
207		1✔
208	// Map custom node IDs 'A','B' to matrix indices 0,1	1✔
209	let mut index_map = Dictionary::<char, usize, 8>::new();	1✔
210	index_map.insert('A', 0).unwrap();	1✔
211	index_map.insert('B', 1).unwrap();	1✔
212		1✔
213	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
214		1✔
215	// Test node iteration	1✔
216	let mut nodes = ['\0'; 8];	1✔
217	let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
218	assert_eq!(nodes_slice.len(), 2);	1✔
219
220	// Check both nodes are present (order may vary)
221	assert!(nodes_slice.contains(&'A'));	1✔
222	assert!(nodes_slice.contains(&'B'));	1✔
223
224	// Test contains_node
225	assert!(bit_map_matrix.contains_node('A').unwrap());	1✔
226	assert!(bit_map_matrix.contains_node('B').unwrap());	1✔
227	assert!(!bit_map_matrix.contains_node('C').unwrap());	1✔
228
229	// Test outgoing edges
230	let mut outgoing_a = ['\0'; 8];	1✔
231	let outgoing_slice = collect(bit_map_matrix.outgoing_edges('A').unwrap(), &mut outgoing_a);	1✔
232	assert_eq!(outgoing_slice.len(), 2); // A->A, A->B	1✔
233
234	let mut outgoing_b = ['\0'; 8];	1✔
235	let outgoing_slice = collect(bit_map_matrix.outgoing_edges('B').unwrap(), &mut outgoing_b);	1✔
236	assert_eq!(outgoing_slice, &['A']); // B->A	1✔
237	}	1✔
238
239	#[test]
240	fn test_bit_map_matrix_empty() {	1✔
241	// Empty bitmap	1✔
242	let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];	1✔
243	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
244		1✔
245	// Empty index map	1✔
246	let index_map = Dictionary::<u32, usize, 8>::new();	1✔
247	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
248		1✔
249	// Should have no nodes	1✔
250	assert_eq!(bit_map_matrix.iter_nodes().unwrap().count(), 0);	1✔
251
252	// Should have no edges
253	assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);	1✔
254
255	// Should not contain any nodes
256	assert!(!bit_map_matrix.contains_node(42).unwrap());	1✔
257	}	1✔
258
259	#[test]
260	fn test_bit_map_matrix_nonexistent_node() {	1✔
261	let bits = [	1✔
262	[0b00000001u8], // Row 0: edge to node 0	1✔
263	[0b00000000u8],	1✔
264	[0b00000000u8],	1✔
265	[0b00000000u8],	1✔
266	[0b00000000u8],	1✔
267	[0b00000000u8],	1✔
268	[0b00000000u8],	1✔
269	[0b00000000u8],	1✔
270	];	1✔
271	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
272		1✔
273	let mut index_map = Dictionary::<u32, usize, 8>::new();	1✔
274	index_map.insert(100, 0).unwrap();	1✔
275		1✔
276	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
277		1✔
278	// Test outgoing edges for non-existent node should return empty iterator	1✔
279	assert_eq!(bit_map_matrix.outgoing_edges(999).unwrap().count(), 0);	1✔
280
281	// Test incoming edges for non-existent node should return empty iterator
282	assert_eq!(bit_map_matrix.incoming_edges(999).unwrap().count(), 0);	1✔
283	}	1✔
284
285	#[test]
286	fn test_bit_map_matrix_incoming_edges() {	1✔
287	// Create a matrix with edges: A->A, A->B, B->A	1✔
288	let bits = [	1✔
289	[0b00000011u8], // Row 0: edges to nodes 0 and 1 (A->A, A->B)	1✔
290	[0b00000001u8], // Row 1: edge to node 0 (B->A)	1✔
291	[0b00000000u8], // Row 2: no edges	1✔
292	[0b00000000u8], // Row 3: no edges	1✔
293	[0b00000000u8], // Row 4: no edges	1✔
294	[0b00000000u8], // Row 5: no edges	1✔
295	[0b00000000u8], // Row 6: no edges	1✔
296	[0b00000000u8], // Row 7: no edges	1✔
297	];	1✔
298	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
299		1✔
300	// Map custom node IDs 'A','B' to matrix indices 0,1	1✔
301	let mut index_map = Dictionary::<char, usize, 8>::new();	1✔
302	index_map.insert('A', 0).unwrap();	1✔
303	index_map.insert('B', 1).unwrap();	1✔
304		1✔
305	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
306		1✔
307	// Test incoming edges to A (should be from A and B)	1✔
308	let mut incoming_a = ['\0'; 8];	1✔
309	let incoming_slice = collect(bit_map_matrix.incoming_edges('A').unwrap(), &mut incoming_a);	1✔
310	assert_eq!(incoming_slice.len(), 2); // A->A, B->A	1✔
311	assert!(incoming_slice.contains(&'A'));	1✔
312	assert!(incoming_slice.contains(&'B'));	1✔
313
314	// Test incoming edges to B (should be from A only)
315	let mut incoming_b = ['\0'; 8];	1✔
316	let incoming_slice = collect(bit_map_matrix.incoming_edges('B').unwrap(), &mut incoming_b);	1✔
317	assert_eq!(incoming_slice, &['A']); // A->B	1✔
318	}	1✔
319
320	#[test]
321	fn test_bit_map_matrix_outgoing_edges_bounds() {	1✔
322	// Create a matrix with edges: A->A, A->B	1✔
323	let bits = [	1✔
324	[0b00000011u8], // Row 0: edges to nodes 0 and 1 (A->A, A->B)	1✔
325	[0b00000000u8], // Row 1: no edges	1✔
326	[0b00000000u8], // Row 2: no edges	1✔
327	[0b00000000u8], // Row 3: no edges	1✔
328	[0b00000000u8], // Row 4: no edges	1✔
329	[0b00000000u8], // Row 5: no edges	1✔
330	[0b00000000u8], // Row 6: no edges	1✔
331	[0b00000000u8], // Row 7: no edges	1✔
332	];	1✔
333	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
334		1✔
335	// Map custom node IDs 'A','B' to matrix indices 0,1	1✔
336	let mut index_map = Dictionary::<char, usize, 8>::new();	1✔
337	index_map.insert('A', 0).unwrap();	1✔
338	index_map.insert('B', 1).unwrap();	1✔
339		1✔
340	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
341		1✔
342	// Test outgoing edges for non-existent node with usize::MAX fallback	1✔
343	// This should not panic and should return an empty iterator	1✔
344	let mut outgoing = ['\0'; 8];	1✔
345	let outgoing_slice = collect(bit_map_matrix.outgoing_edges('C').unwrap(), &mut outgoing);	1✔
346	assert_eq!(outgoing_slice.len(), 0);	1✔
347
348	// Test outgoing edges for non-existent node with 0 fallback
349	// This should also not panic and should return an empty iterator
350	let mut outgoing = ['\0'; 8];	1✔
351	let outgoing_slice = collect(bit_map_matrix.outgoing_edges('D').unwrap(), &mut outgoing);	1✔
352	assert_eq!(outgoing_slice.len(), 0);	1✔
353	}	1✔
354
355	#[test]
356	fn test_add_node_to_empty_bit_matrix() {	1✔
357	let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];	1✔
358	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
359	let index_map = Dictionary::<u32, usize, 10>::new();	1✔
360		1✔
361	let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
362	bit_map_matrix.add_node(42).unwrap();	1✔
363		1✔
364	let mut nodes = [0u32; 2];	1✔
365	let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
366	assert_eq!(nodes_slice, &[42]);	1✔
367	assert_eq!(bit_map_matrix.outgoing_edges(42).unwrap().count(), 0);	1✔
368	}	1✔
369
370	#[test]
371	fn test_add_node_to_existing_bit_matrix() {	1✔
372	let bits = [	1✔
373	[0b00000001u8], // Row 0: edge to node 0 (self-loop)	1✔
374	[0b00000000u8],	1✔
375	[0b00000000u8],	1✔
376	[0b00000000u8],	1✔
377	[0b00000000u8],	1✔
378	[0b00000000u8],	1✔
379	[0b00000000u8],	1✔
380	[0b00000000u8],	1✔
381	];	1✔
382	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
383	let mut index_map = Dictionary::<char, usize, 10>::new();	1✔
384	index_map.insert('A', 0).unwrap();	1✔
385		1✔
386	let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
387	bit_map_matrix.add_node('B').unwrap();	1✔
388		1✔
389	let mut nodes = ['\0'; 4];	1✔
390	let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
391	assert_eq!(nodes_slice, &['A', 'B']);	1✔
392	assert_eq!(bit_map_matrix.outgoing_edges('B').unwrap().count(), 0);	1✔
393	assert_eq!(bit_map_matrix.outgoing_edges('A').unwrap().count(), 1);	1✔
394	}	1✔
395
396	#[test]
397	fn test_add_duplicate_node_bit_matrix() {	1✔
398	let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];	1✔
399	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
400	let mut index_map = Dictionary::<u32, usize, 8>::new();	1✔
401	index_map.insert(100, 0).unwrap();	1✔
402		1✔
403	let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
404		1✔
405	let result = bit_map_matrix.add_node(100);	1✔
406	assert!(matches!(result, Err(GraphError::DuplicateNode(100))));	1✔
407
408	let mut nodes = [0u32; 2];	1✔
409	let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
410	assert_eq!(nodes_slice, &[100]);	1✔
411	}	1✔
412
413	#[test]
414	fn test_add_node_capacity_exceeded_bit_matrix() {	1✔
415	let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];	1✔
416	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
417	let mut index_map = Dictionary::<u32, usize, 8>::new();	1✔
418	for i in 0..8 {	9✔
419	index_map.insert(i as u32, i).unwrap();	8✔
420	}	8✔
421
422	let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
423		1✔
424	let result = bit_map_matrix.add_node(999);	1✔
425	assert!(matches!(result, Err(GraphError::OutOfCapacity)));	1✔
426
427	let mut nodes = [0u32; 10];	1✔
428	let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
429	assert_eq!(nodes_slice, &[0, 1, 2, 3, 4, 5, 6, 7]);	1✔
430	}	1✔
431
432	#[test]
433	fn test_add_multiple_nodes_bit_matrix() {	1✔
434	let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];	1✔
435	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
436	let index_map = Dictionary::<char, usize, 10>::new();	1✔
437		1✔
438	let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
439	bit_map_matrix.add_node('X').unwrap();	1✔
440	bit_map_matrix.add_node('Y').unwrap();	1✔
441	bit_map_matrix.add_node('Z').unwrap();	1✔
442		1✔
443	let mut nodes = ['\0'; 4];	1✔
444	let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
445	assert_eq!(nodes_slice, &['X', 'Y', 'Z']);	1✔
446	assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);	1✔
447	}	1✔
448
449	#[test]
450	fn test_add_node_fills_gaps_bit_matrix() {	1✔
451	let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];	1✔
452	let bitmap = super::super::bit_matrix::BitMatrix::new_unchecked(bits);	1✔
453	let mut index_map = Dictionary::<u32, usize, 10>::new();	1✔
454	index_map.insert(10, 0).unwrap();	1✔
455	index_map.insert(30, 2).unwrap();	1✔
456	index_map.insert(50, 4).unwrap();	1✔
457		1✔
458	let mut bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
459	bit_map_matrix.add_node(20).unwrap();	1✔
460		1✔
461	let mut nodes = [0u32; 6];	1✔
462	let nodes_slice = collect_sorted(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
463	assert_eq!(nodes_slice, &[10, 20, 30, 50]);	1✔
464	}	1✔
465	}

kaidokert / heapless-graphs-rs / 15791628916

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous