20724877148

Committed 05 Jan 2026 06:16PM UTC coverage: 62.048% (-0.02%) from 62.07%

Build # 20724877148

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #160 from progval/patch-2

Fix typo in docstring

Run Details

5441 of 8769 relevant lines covered (62.05%)

43310641.57 hits per line

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

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

vigna / webgraph-rs / 20724877148

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