15665053732

Committed 15 Jun 2025 04:12PM UTC coverage: 93.713% (+4.5%) from 89.24%

Build # 15665053732

Build Type

Pull #8

github

Committed by

kaidokert

Commit Message

EdgeValue arrays

Pull Request Pull Request #8: No ref graphs

Run Details

3389 of 3461 new or added lines in 26 files covered. (97.92%)

41 existing lines in 7 files now uncovered.

5128 of 5472 relevant lines covered (93.71%)

44.53 hits per line

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

95.43

/src/matrix/bit_map_matrix.rs

use crate::{
    containers::maps::MapTrait,
    graph::{Graph, GraphError, 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, NI, M>
where
    NI: NodeIndex,
    M: MapTrait<NI, usize>,
{
    bitmap: super::bit_matrix::BitMatrix<N>,
    index_map: M,
    phantom: core::marker::PhantomData<NI>,
}

impl<const N: usize, NI, M> BitMapMatrix<N, 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>,
        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>, index_map: M) -> Self {
        Self {
            bitmap,
            index_map,
            phantom: core::marker::PhantomData,
        }
    }
}

impl<const N: usize, NI, M> Graph<NI> for BitMapMatrix<N, 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 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
                        }
                    })
            }))
    }

    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 0 as fallback (will be filtered out)
        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)
            }))
    }

    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)
            }))
    }

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

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

    #[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(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);
        index_map.insert('B', 1);

        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(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(bits);

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

        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(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);
        index_map.insert('B', 1);

        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
    }
}

1	use crate::{
2	containers::maps::MapTrait,
3	graph::{Graph, GraphError, 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, NI, M>
12	where
13	NI: NodeIndex,
14	M: MapTrait<NI, usize>,
15	{
16	bitmap: super::bit_matrix::BitMatrix<N>,
17	index_map: M,
18	phantom: core::marker::PhantomData<NI>,
19	}
20
21	impl<const N: usize, NI, M> BitMapMatrix<N, 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(	5✔
31	bitmap: super::bit_matrix::BitMatrix<N>,	5✔
32	index_map: M,	5✔
33	) -> Result<Self, GraphError<NI>> {	5✔
34	// BitMatrix supports indices in range 0..8*N	5✔
35	let max_valid_index = 8 * N;	5✔
36	for (node, idx) in index_map.iter() {	13✔
37	if *idx >= max_valid_index {	13✔
NEW 38	return Err(GraphError::IndexOutOfBounds(idx, node));	×
39	}	13✔
40	}
41	Ok(Self::new_unchecked(bitmap, index_map))	5✔
42	}	5✔
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>, index_map: M) -> Self {	5✔
50	Self {	5✔
51	bitmap,	5✔
52	index_map,	5✔
53	phantom: core::marker::PhantomData,	5✔
54	}	5✔
55	}	5✔
56	}
57
58	impl<const N: usize, NI, M> Graph<NI> for BitMapMatrix<N, 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> {	2✔
66	Ok(self.index_map.iter().map(\|(&k, _)\| k))	2✔
67	}	2✔
68
69	fn iter_edges(&self) -> Result<impl Iterator<Item = (NI, NI)>, Self::Error> {	1✔
70	Ok(self	1✔
71	.index_map	1✔
72	.iter()	1✔
73	.flat_map(move \|(&from_node, &from_idx)\| {	1✔
NEW 74	self.index_map	×
NEW 75	.iter()	×
NEW 76	.filter_map(move \|(&to_node, &to_idx)\| {	×
NEW 77	if self.bitmap.get(from_idx, to_idx) {	×
NEW 78	Some((from_node, to_node))	×
79	} else {
NEW 80	None	×
81	}
NEW 82	})	×
83	}))	1✔
84	}	1✔
85
86	fn outgoing_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {	48✔
87	// Fast direct lookup of matrix index for this node	48✔
88	let matrix_idx = self.index_map.get(&node).copied();	48✔
89
90	// Get outgoing edges from bitmap, using 0 as fallback (will be filtered out)
91	let outgoing = self	48✔
92	.bitmap	48✔
93	.outgoing_edges(matrix_idx.unwrap_or(usize::MAX))	48✔
94	.map_err(\|_\| GraphError::NodeNotFound(node))?;	48✔
95
96	// Map matrix indices back to node indices by checking all nodes
97	Ok(outgoing	48✔
98	.filter(move \|_\| matrix_idx.is_some()) // Filter out everything if node doesn't exist	48✔
99	.filter_map(move \|target_idx\| {	48✔
100	self.index_map	42✔
101	.iter()	42✔
102	.find(\|(_, &idx)\| idx == target_idx)	136✔
103	.map(\|(&node, _)\| node)	42✔
104	}))	48✔
105	}	48✔
106
107	fn incoming_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {	3✔
108	// Fast direct lookup of matrix index for this node	3✔
109	let matrix_idx = self.index_map.get(&node).copied();	3✔
110
111	// Get incoming edges from bitmap, using 0 as fallback (will be filtered out)
112	let incoming = self	3✔
113	.bitmap	3✔
114	.incoming_edges(matrix_idx.unwrap_or(usize::MAX))	3✔
115	.map_err(\|_\| GraphError::NodeNotFound(node))?;	3✔
116
117	// Map matrix indices back to node indices by checking all nodes
118	Ok(incoming	3✔
119	.filter(move \|_\| matrix_idx.is_some()) // Filter out everything if node doesn't exist	3✔
120	.filter_map(move \|source_idx\| {	3✔
121	self.index_map	3✔
122	.iter()	3✔
123	.find(\|(_, &idx)\| idx == source_idx)	4✔
124	.map(\|(&node, _)\| node)	3✔
125	}))	3✔
126	}	3✔
127
128	fn contains_node(&self, node: NI) -> Result<bool, Self::Error> {	22✔
129	Ok(self.index_map.contains_key(&node))	22✔
130	}	22✔
131	}
132
133	#[cfg(test)]
134	mod tests {
135	use super::*;
136	use crate::containers::maps::staticdict::Dictionary;
137	use crate::tests::collect;
138
139	#[test]
140	fn test_bit_map_matrix_basic() {	1✔
141	// Create a simple 2x2 bit matrix with edges: 0->0, 0->1, 1->0	1✔
142	let bits = [	1✔
143	[0b00000011u8], // Row 0: edges to nodes 0 and 1	1✔
144	[0b00000001u8], // Row 1: edge to node 0	1✔
145	[0b00000000u8], // Row 2: no edges	1✔
146	[0b00000000u8], // Row 3: no edges	1✔
147	[0b00000000u8], // Row 4: no edges	1✔
148	[0b00000000u8], // Row 5: no edges	1✔
149	[0b00000000u8], // Row 6: no edges	1✔
150	[0b00000000u8], // Row 7: no edges	1✔
151	];	1✔
152	let bitmap = super::super::bit_matrix::BitMatrix::new(bits);	1✔
153		1✔
154	// Map custom node IDs 'A','B' to matrix indices 0,1	1✔
155	let mut index_map = Dictionary::<char, usize, 8>::new();	1✔
156	index_map.insert('A', 0);	1✔
157	index_map.insert('B', 1);	1✔
158		1✔
159	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
160		1✔
161	// Test node iteration	1✔
162	let mut nodes = ['\0'; 8];	1✔
163	let nodes_slice = collect(bit_map_matrix.iter_nodes().unwrap(), &mut nodes);	1✔
164	assert_eq!(nodes_slice.len(), 2);	1✔
165
166	// Check both nodes are present (order may vary)
167	assert!(nodes_slice.contains(&'A'));	1✔
168	assert!(nodes_slice.contains(&'B'));	1✔
169
170	// Test contains_node
171	assert!(bit_map_matrix.contains_node('A').unwrap());	1✔
172	assert!(bit_map_matrix.contains_node('B').unwrap());	1✔
173	assert!(!bit_map_matrix.contains_node('C').unwrap());	1✔
174
175	// Test outgoing edges
176	let mut outgoing_a = ['\0'; 8];	1✔
177	let outgoing_slice = collect(bit_map_matrix.outgoing_edges('A').unwrap(), &mut outgoing_a);	1✔
178	assert_eq!(outgoing_slice.len(), 2); // A->A, A->B	1✔
179
180	let mut outgoing_b = ['\0'; 8];	1✔
181	let outgoing_slice = collect(bit_map_matrix.outgoing_edges('B').unwrap(), &mut outgoing_b);	1✔
182	assert_eq!(outgoing_slice, &['A']); // B->A	1✔
183	}	1✔
184
185	#[test]
186	fn test_bit_map_matrix_empty() {	1✔
187	// Empty bitmap	1✔
188	let bits = [[0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8], [0u8]];	1✔
189	let bitmap = super::super::bit_matrix::BitMatrix::new(bits);	1✔
190		1✔
191	// Empty index map	1✔
192	let index_map = Dictionary::<u32, usize, 8>::new();	1✔
193	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
194		1✔
195	// Should have no nodes	1✔
196	assert_eq!(bit_map_matrix.iter_nodes().unwrap().count(), 0);	1✔
197
198	// Should have no edges
199	assert_eq!(bit_map_matrix.iter_edges().unwrap().count(), 0);	1✔
200
201	// Should not contain any nodes
202	assert!(!bit_map_matrix.contains_node(42).unwrap());	1✔
203	}	1✔
204
205	#[test]
206	fn test_bit_map_matrix_nonexistent_node() {	1✔
207	let bits = [	1✔
208	[0b00000001u8], // Row 0: edge to node 0	1✔
209	[0b00000000u8],	1✔
210	[0b00000000u8],	1✔
211	[0b00000000u8],	1✔
212	[0b00000000u8],	1✔
213	[0b00000000u8],	1✔
214	[0b00000000u8],	1✔
215	[0b00000000u8],	1✔
216	];	1✔
217	let bitmap = super::super::bit_matrix::BitMatrix::new(bits);	1✔
218		1✔
219	let mut index_map = Dictionary::<u32, usize, 8>::new();	1✔
220	index_map.insert(100, 0);	1✔
221		1✔
222	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
223		1✔
224	// Test outgoing edges for non-existent node should return empty iterator	1✔
225	assert_eq!(bit_map_matrix.outgoing_edges(999).unwrap().count(), 0);	1✔
226
227	// Test incoming edges for non-existent node should return empty iterator
228	assert_eq!(bit_map_matrix.incoming_edges(999).unwrap().count(), 0);	1✔
229	}	1✔
230
231	#[test]
232	fn test_bit_map_matrix_incoming_edges() {	1✔
233	// Create a matrix with edges: A->A, A->B, B->A	1✔
234	let bits = [	1✔
235	[0b00000011u8], // Row 0: edges to nodes 0 and 1 (A->A, A->B)	1✔
236	[0b00000001u8], // Row 1: edge to node 0 (B->A)	1✔
237	[0b00000000u8], // Row 2: no edges	1✔
238	[0b00000000u8], // Row 3: no edges	1✔
239	[0b00000000u8], // Row 4: no edges	1✔
240	[0b00000000u8], // Row 5: no edges	1✔
241	[0b00000000u8], // Row 6: no edges	1✔
242	[0b00000000u8], // Row 7: no edges	1✔
243	];	1✔
244	let bitmap = super::super::bit_matrix::BitMatrix::new(bits);	1✔
245		1✔
246	// Map custom node IDs 'A','B' to matrix indices 0,1	1✔
247	let mut index_map = Dictionary::<char, usize, 8>::new();	1✔
248	index_map.insert('A', 0);	1✔
249	index_map.insert('B', 1);	1✔
250		1✔
251	let bit_map_matrix = BitMapMatrix::new(bitmap, index_map).unwrap();	1✔
252		1✔
253	// Test incoming edges to A (should be from A and B)	1✔
254	let mut incoming_a = ['\0'; 8];	1✔
255	let incoming_slice = collect(bit_map_matrix.incoming_edges('A').unwrap(), &mut incoming_a);	1✔
256	assert_eq!(incoming_slice.len(), 2); // A->A, B->A	1✔
257	assert!(incoming_slice.contains(&'A'));	1✔
258	assert!(incoming_slice.contains(&'B'));	1✔
259
260	// Test incoming edges to B (should be from A only)
261	let mut incoming_b = ['\0'; 8];	1✔
262	let incoming_slice = collect(bit_map_matrix.incoming_edges('B').unwrap(), &mut incoming_b);	1✔
263	assert_eq!(incoming_slice, &['A']); // A->B	1✔
264	}	1✔
265	}

kaidokert / heapless-graphs-rs / 15665053732

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