24296210049

Committed 12 Apr 2026 01:49AM UTC coverage: 66.827% (-0.05%) from 66.877%

Build # 24296210049

Build Type

push

github

Committed by

vigna

Commit Message

Clippy hapy

Coverage Stats

6674 of 9987 relevant lines covered (66.83%)

47792805.58 hits per line

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

92.86

/webgraph/src/utils/ragged_array.rs

/*
 * SPDX-FileCopyrightText: 2025 Tommaso Fontana
 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

/// A [ragged array] that can be only appended to.
///
/// [ragged array]: https://en.wikipedia.org/wiki/Ragged_array
///
/// This structure keeps track of a list of vectors of different lengths in a
/// compact form: a vector of values contains all the values concatenated, and
/// a vector of offsets contains the starting index of each vector in the
/// values list.
///
/// We support appending new vectors, indexing to retrieve existing vectors,
/// clearing the array while preserving allocated memory, and shrinking the
/// allocated memory.
///
/// # Examples
///
/// ```
/// use webgraph::utils::RaggedArray;
///
/// let mut ragged = RaggedArray::new();
/// ragged.push(vec![1, 2, 3]);
/// ragged.push(vec![4, 5]);
/// assert_eq!(ragged.len(), 2);
/// assert_eq!(&ragged[0], &[1, 2, 3]);
/// assert_eq!(&ragged[1], &[4, 5]);
/// ragged.push(vec![]);
/// assert_eq!(ragged.len(), 3);
/// assert_eq!(ragged.num_values(), 5);
/// assert_eq!(&ragged[2], &[]);
/// ragged.clear();
/// assert_eq!(ragged.len(), 0);
/// ```
#[derive(Debug, Clone)]
pub struct RaggedArray<T> {
    /// The first offset is always zero, and offsets contains one more element
    /// than the number of vectors.
    offsets: Vec<usize>,
    /// The concatenation of all vectors.
    values: Vec<T>,
}

impl<T> Default for RaggedArray<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> RaggedArray<T> {
    /// Creates a new empty ragged array.
    pub fn new() -> Self {
        Self {
            offsets: vec![0],
            values: Vec::new(),
        }
    }

    /// Adds a vector, provided as an [`IntoIterator`], to the ragged array.
    pub fn push(&mut self, values: impl IntoIterator<Item = T>) {
        self.values.extend(values);
        self.offsets.push(self.values.len());
    }

    /// Resets the ragged array to an empty state, preserving allocated memory.
    pub fn clear(&mut self) {
        self.offsets.truncate(1);
        self.values.clear();
    }

    /// Gets the number of vectors in the ragged array.
    pub fn len(&self) -> usize {
        self.offsets.len() - 1
    }

    /// Returns `true` if the ragged array contains no vectors.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Shrinks the capacity of the vectors of values and offsets to fit their
    /// current length.
    pub fn shrink_to_fit(&mut self) {
        self.offsets.shrink_to_fit();
        self.values.shrink_to_fit();
    }

    /// Shrinks the capacity of the vector of values to `min_capacity`, or to
    /// the [overall number of values] if it is greater.
    ///
    /// Note that this method does not affect the offsets capacity.
    ///
    /// [overall number of values]: Self::num_values
    pub fn shrink_values_to(&mut self, min_capacity: usize) {
        self.values.shrink_to(min_capacity);
    }

    /// Returns the capacity of the vector storing values.
    pub fn values_capacity(&self) -> usize {
        self.values.capacity()
    }

    /// Returns the overall number of values in the ragged array.
    pub fn num_values(&self) -> usize {
        self.values.len()
    }
}

impl<T> core::ops::Index<usize> for RaggedArray<T> {
    type Output = [T];
    /// Retrieves the vector at the given index.
    fn index(&self, row: usize) -> &Self::Output {
        let start = self.offsets[row];
        let end = self.offsets[row + 1];
        &self.values[start..end]
    }
}

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

    #[test]
    fn test_new_array_is_empty() {
        let matrix: RaggedArray<i32> = RaggedArray::new();
        assert_eq!(matrix.len(), 0);
    }

    #[test]
    fn test_push_rows_and_indexing() {
        let mut matrix = RaggedArray::new();
        matrix.push(vec![1, 2, 3]);
        matrix.push(vec![4, 5]);
        assert_eq!(matrix.len(), 2);
        assert_eq!(&matrix[0], &[1, 2, 3]);
        assert_eq!(&matrix[1], &[4, 5]);
    }

    #[test]
    fn test_ragged_rows_and_empty_rows() {
        let mut matrix = RaggedArray::new();
        matrix.push(vec![1]);
        matrix.push(vec![]);
        matrix.push(vec![2, 3, 4]);
        assert_eq!(matrix.len(), 3);
        assert_eq!(&matrix[0], &[1]);
        assert_eq!(&matrix[1], &[]);
        assert_eq!(&matrix[2], &[2, 3, 4]);
    }

    #[test]
    fn test_clear_and_reuse() {
        let mut matrix = RaggedArray::new();
        matrix.push(vec![1, 2]);
        matrix.push(vec![3]);
        assert_eq!(matrix.len(), 2);
        matrix.clear();
        assert_eq!(matrix.len(), 0);
        matrix.push(vec![10, 20]);
        matrix.push(vec![]);
        matrix.push(vec![30]);
        assert_eq!(matrix.len(), 3);
        assert_eq!(&matrix[0], &[10, 20]);
        assert_eq!(&matrix[1], &[]);
        assert_eq!(&matrix[2], &[30]);
    }

    #[test]
    #[should_panic]
    fn test_index_out_of_bounds() {
        let mut matrix = RaggedArray::new();
        matrix.push(vec![1]);
        let _ = &matrix[1];
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Tommaso Fontana
3	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	/// A [ragged array] that can be only appended to.
9	///
10	/// [ragged array]: https://en.wikipedia.org/wiki/Ragged_array
11	///
12	/// This structure keeps track of a list of vectors of different lengths in a
13	/// compact form: a vector of values contains all the values concatenated, and
14	/// a vector of offsets contains the starting index of each vector in the
15	/// values list.
16	///
17	/// We support appending new vectors, indexing to retrieve existing vectors,
18	/// clearing the array while preserving allocated memory, and shrinking the
19	/// allocated memory.
20	///
21	/// # Examples
22	///
23	/// ```
24	/// use webgraph::utils::RaggedArray;
25	///
26	/// let mut ragged = RaggedArray::new();
27	/// ragged.push(vec![1, 2, 3]);
28	/// ragged.push(vec![4, 5]);
29	/// assert_eq!(ragged.len(), 2);
30	/// assert_eq!(&ragged[0], &[1, 2, 3]);
31	/// assert_eq!(&ragged[1], &[4, 5]);
32	/// ragged.push(vec![]);
33	/// assert_eq!(ragged.len(), 3);
34	/// assert_eq!(ragged.num_values(), 5);
35	/// assert_eq!(&ragged[2], &[]);
36	/// ragged.clear();
37	/// assert_eq!(ragged.len(), 0);
38	/// ```
39	#[derive(Debug, Clone)]
40	pub struct RaggedArray<T> {
41	/// The first offset is always zero, and offsets contains one more element
42	/// than the number of vectors.
43	offsets: Vec<usize>,
44	/// The concatenation of all vectors.
45	values: Vec<T>,
46	}
47
48	impl<T> Default for RaggedArray<T> {
49	fn default() -> Self {	×
50	Self::new()	×
51	}
52	}
53
54	impl<T> RaggedArray<T> {
55	/// Creates a new empty ragged array.
56	pub fn new() -> Self {	2,332,830✔
57	Self {
58	offsets: vec![0],	2,332,830✔
59	values: Vec::new(),	2,332,830✔
60	}
61	}
62
63	/// Adds a vector, provided as an [`IntoIterator`], to the ragged array.
64	pub fn push(&mut self, values: impl IntoIterator<Item = T>) {	96,893,147✔
65	self.values.extend(values);	290,679,441✔
66	self.offsets.push(self.values.len());	387,572,588✔
67	}
68
69	/// Resets the ragged array to an empty state, preserving allocated memory.
70	pub fn clear(&mut self) {	27,177,423✔
71	self.offsets.truncate(1);	54,354,846✔
72	self.values.clear();	54,354,846✔
73	}
74
75	/// Gets the number of vectors in the ragged array.
76	pub fn len(&self) -> usize {	9✔
77	self.offsets.len() - 1	9✔
78	}
79
80	/// Returns `true` if the ragged array contains no vectors.
81	pub fn is_empty(&self) -> bool {	2✔
82	self.len() == 0	2✔
83	}
84
85	/// Shrinks the capacity of the vectors of values and offsets to fit their
86	/// current length.
87	pub fn shrink_to_fit(&mut self) {	1✔
88	self.offsets.shrink_to_fit();	2✔
89	self.values.shrink_to_fit();	2✔
90	}
91
92	/// Shrinks the capacity of the vector of values to `min_capacity`, or to
93	/// the [overall number of values] if it is greater.
94	///
95	/// Note that this method does not affect the offsets capacity.
96	///
97	/// [overall number of values]: Self::num_values
98	pub fn shrink_values_to(&mut self, min_capacity: usize) {	69✔
99	self.values.shrink_to(min_capacity);	207✔
100	}
101
102	/// Returns the capacity of the vector storing values.
103	pub fn values_capacity(&self) -> usize {	27,177,491✔
104	self.values.capacity()	54,354,982✔
105	}
106
107	/// Returns the overall number of values in the ragged array.
108	pub fn num_values(&self) -> usize {	27,177,424✔
109	self.values.len()	54,354,848✔
110	}
111	}
112
113	impl<T> core::ops::Index<usize> for RaggedArray<T> {
114	type Output = [T];
115	/// Retrieves the vector at the given index.
116	fn index(&self, row: usize) -> &Self::Output {	465,666,381✔
117	let start = self.offsets[row];	931,332,762✔
118	let end = self.offsets[row + 1];	931,332,762✔
119	&self.values[start..end]	931,332,762✔
120	}
121	}
122
123	#[cfg(test)]
124	mod tests {
125	use super::*;
126
127	#[test]
128	fn test_new_array_is_empty() {
129	let matrix: RaggedArray<i32> = RaggedArray::new();
130	assert_eq!(matrix.len(), 0);
131	}
132
133	#[test]
134	fn test_push_rows_and_indexing() {
135	let mut matrix = RaggedArray::new();
136	matrix.push(vec![1, 2, 3]);
137	matrix.push(vec![4, 5]);
138	assert_eq!(matrix.len(), 2);
139	assert_eq!(&matrix[0], &[1, 2, 3]);
140	assert_eq!(&matrix[1], &[4, 5]);
141	}
142
143	#[test]
144	fn test_ragged_rows_and_empty_rows() {
145	let mut matrix = RaggedArray::new();
146	matrix.push(vec![1]);
147	matrix.push(vec![]);
148	matrix.push(vec![2, 3, 4]);
149	assert_eq!(matrix.len(), 3);
150	assert_eq!(&matrix[0], &[1]);
151	assert_eq!(&matrix[1], &[]);
152	assert_eq!(&matrix[2], &[2, 3, 4]);
153	}
154
155	#[test]
156	fn test_clear_and_reuse() {
157	let mut matrix = RaggedArray::new();
158	matrix.push(vec![1, 2]);
159	matrix.push(vec![3]);
160	assert_eq!(matrix.len(), 2);
161	matrix.clear();
162	assert_eq!(matrix.len(), 0);
163	matrix.push(vec![10, 20]);
164	matrix.push(vec![]);
165	matrix.push(vec![30]);
166	assert_eq!(matrix.len(), 3);
167	assert_eq!(&matrix[0], &[10, 20]);
168	assert_eq!(&matrix[1], &[]);
169	assert_eq!(&matrix[2], &[30]);
170	}
171
172	#[test]
173	#[should_panic]
174	fn test_index_out_of_bounds() {
175	let mut matrix = RaggedArray::new();
176	matrix.push(vec![1]);
177	let _ = &matrix[1];
178	}
179	}

vigna / webgraph-rs / 24296210049

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