GCC Code Coverage Report

Directory: src/oiseau/
File: src/oiseau/utils/jagged_array.hpp
Date: 2026-04-16 00:52:28
Exec Total Coverage
Lines: 174 175 99.4%
Functions: 61 61 100.0%
Branches: 119 198 60.1%
Line Branch Exec Source
1 // Copyright (C) 2025 Tiago V. L. Amorim (@tiagovla)
2 //
3 // This file is part of oiseau (https://github.com/tiagovla/oiseau)
4 //
5 // SPDX-License-Identifier: GPL-3.0-or-later
6
7 #pragma once
8
9 #include <algorithm> // For std::copy, std::move, std::next
10 #include <initializer_list> // For std::initializer_list
11 #include <iostream> // For std::ostream and operator<<
12 #include <iterator> // For std::iterator related tags
13 #include <span> // For std::span
14 #include <stdexcept> // For std::out_of_range
15 #include <string> // For std::to_string in error messages
16 #include <vector>
17
18 namespace oiseau::utils {
19
20 template <typename T>
21 class JaggedArray;
22
23 template <typename T>
24 std::ostream& operator<<(std::ostream& os, const JaggedArray<T>& arr);
25
26 template <typename T>
27 class JaggedArray {
28 private:
29 std::vector<T> m_data;
30 std::vector<std::size_t> m_row_offsets;
31
32 192 void check_row_bounds(std::size_t r_idx, const char* func_name) const {
33
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 92 times.
 192 if (r_idx >= num_rows()) {
34
6/12
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 4 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 4 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 4 times.
✗ Branch 15 not taken.
✓ Branch 17 taken 4 times.
✗ Branch 18 not taken.
 48 throw std::out_of_range(std::string(func_name) + " - Row index (" + std::to_string(r_idx) +
35
3/6
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 4 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
 32 ") out of bounds for " + std::to_string(num_rows()) + " rows.");
36 }
37 184 }
38
39 5 void check_row_insert_bounds(std::size_t r_idx, const char* func_name) const {
40
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 4 times.
 5 if (r_idx > num_rows()) {
41
4/8
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
 4 throw std::out_of_range(std::string(func_name) + " - Row index for insertion (" +
42
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 4 std::to_string(r_idx) + ") out of bounds for " +
43
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 4 std::to_string(num_rows()) + " rows.");
44 }
45 4 }
46
47 58 static std::size_t get_total_elements_hint(
48 const std::initializer_list<std::initializer_list<T>>& il) {
49 58 std::size_t total = 0;
50
2/2
✓ Branch 3 taken 77 times.
✓ Branch 4 taken 29 times.
 212 for (const auto& inner : il) total += inner.size();
51 58 return total;
52 }
53 1 static std::size_t get_total_elements_hint(const std::initializer_list<std::vector<T>>& il) {
54 1 std::size_t total = 0;
55
2/2
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 1 times.
 4 for (const auto& inner : il) total += inner.size();
56 1 return total;
57 }
58
59 public:
60
1/2
✓ Branch 3 taken 23 times.
✗ Branch 4 not taken.
 46 JaggedArray() { m_row_offsets.push_back(0); }
61
62
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 2 explicit JaggedArray(std::size_t num_r) : m_row_offsets(num_r + 1, 0) {}
63
64 58 JaggedArray(std::initializer_list<std::initializer_list<T>> il) {
65
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 58 m_row_offsets.push_back(0);
66 58 std::size_t current_offset = 0;
67
1/2
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
 58 m_data.reserve(get_total_elements_hint(il));
68
2/2
✓ Branch 2 taken 77 times.
✓ Branch 3 taken 29 times.
 212 for (const auto& inner_list : il) {
69
1/2
✓ Branch 4 taken 77 times.
✗ Branch 5 not taken.
 308 m_data.insert(m_data.end(), inner_list.begin(), inner_list.end());
70 154 current_offset += inner_list.size();
71
1/2
✓ Branch 1 taken 77 times.
✗ Branch 2 not taken.
 154 m_row_offsets.push_back(current_offset);
72 }
73 58 }
74
75 1 JaggedArray(std::initializer_list<std::vector<T>> il) {
76
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 m_row_offsets.push_back(0);
77 1 std::size_t current_offset = 0;
78
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 m_data.reserve(get_total_elements_hint(il));
79
2/2
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 1 times.
 4 for (const auto& row_vec : il) {
80
1/2
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 6 m_data.insert(m_data.end(), row_vec.begin(), row_vec.end());
81 3 current_offset += row_vec.size();
82
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 m_row_offsets.push_back(current_offset);
83 }
84 1 }
85
86
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 JaggedArray(const JaggedArray& other) = default;
87 1 JaggedArray(JaggedArray&& other) noexcept = default;
88 2 JaggedArray& operator=(const JaggedArray& other) = default;
89 1 JaggedArray& operator=(JaggedArray&& other) noexcept = default;
90
91 368 std::size_t num_rows() const noexcept {
92
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 182 times.
 368 if (m_row_offsets.empty()) return 0;
93 364 return m_row_offsets.size() - 1;
94 }
95
96 52 std::size_t num_cols(std::size_t r_idx) const {
97 52 check_row_bounds(r_idx, "num_cols");
98 50 return m_row_offsets[r_idx + 1] - m_row_offsets[r_idx];
99 }
100
101 32 std::size_t total_elements() const noexcept { return m_data.size(); }
102
103 5 std::span<T> operator[](std::size_t r_idx) {
104
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 3 times.
 5 if (r_idx >= num_rows()) {
105
4/8
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 2 times.
✗ Branch 12 not taken.
 2 throw std::out_of_range("JaggedArray::operator[] - Row index (" + std::to_string(r_idx) +
106 ") out of bounds.");
107 }
108 3 std::size_t start_offset = m_row_offsets[r_idx];
109 3 std::size_t length = m_row_offsets[r_idx + 1] - start_offset;
110 3 return std::span<T>(m_data.data() + start_offset, length);
111 }
112
113 10 std::span<const T> operator[](std::size_t r_idx) const {
114
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 4 times.
 10 if (r_idx >= num_rows()) {
115
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 8 throw std::out_of_range("JaggedArray::operator[] const - Row index (" +
116
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 8 std::to_string(r_idx) + ") out of bounds.");
117 }
118 8 std::size_t start_offset = m_row_offsets[r_idx];
119 8 std::size_t length = m_row_offsets[r_idx + 1] - start_offset;
120 8 return std::span<const T>(m_data.data() + start_offset, length);
121 }
122
123 110 T& at(std::size_t r_idx, std::size_t c_idx) {
124 110 check_row_bounds(r_idx, "at (row)");
125 108 std::size_t start_offset = m_row_offsets[r_idx];
126 108 std::size_t row_len = m_row_offsets[r_idx + 1] - start_offset;
127
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 53 times.
 108 if (c_idx >= row_len) {
128
4/8
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
 8 throw std::out_of_range("JaggedArray::at - Column index (" + std::to_string(c_idx) +
129
4/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 8 ") out of bounds for row " + std::to_string(r_idx) + " with length " +
130
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 8 std::to_string(row_len) + ".");
131 }
132 106 return m_data[start_offset + c_idx];
133 }
134
135 2 const T& at(std::size_t r_idx, std::size_t c_idx) const {
136 2 check_row_bounds(r_idx, "at (row)");
137 2 std::size_t start_offset = m_row_offsets[r_idx];
138 2 std::size_t row_len = m_row_offsets[r_idx + 1] - start_offset;
139
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (c_idx >= row_len) {
140
4/8
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
 4 throw std::out_of_range("JaggedArray::at - Column index (" + std::to_string(c_idx) +
141
4/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 4 ") out of bounds for row " + std::to_string(r_idx) + " with length " +
142
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 4 std::to_string(row_len) + ".");
143 }
144 1 return m_data[start_offset + c_idx];
145 }
146
147 5 void add_row(std::initializer_list<T> il) {
148
1/2
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 10 m_data.insert(m_data.end(), il.begin(), il.end());
149
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 m_row_offsets.push_back(m_data.size());
150 5 }
151
152 1 void add_row(const std::vector<T>& new_row_data) {
153
1/2
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 2 m_data.insert(m_data.end(), new_row_data.begin(), new_row_data.end());
154
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 m_row_offsets.push_back(m_data.size());
155 1 }
156
157 1 void add_row(std::vector<T>&& new_row_data) {
158
1/2
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 2 m_data.insert(m_data.end(), std::make_move_iterator(new_row_data.begin()),
159 std::make_move_iterator(new_row_data.end()));
160
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 m_row_offsets.push_back(m_data.size());
161 1 new_row_data.clear();
162 1 }
163
164 5 void insert_row(std::size_t r_idx, std::initializer_list<T> il) {
165 5 check_row_insert_bounds(r_idx, "insert_row");
166
167 4 std::size_t insert_data_pos = m_row_offsets[r_idx];
168 4 std::size_t new_row_len = il.size();
169
170
1/2
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 12 m_data.insert(m_data.begin() + insert_data_pos, il.begin(), il.end());
171
1/2
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
 16 m_row_offsets.insert(m_row_offsets.begin() + r_idx + 1, m_row_offsets[r_idx] + new_row_len);
172
173
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 4 times.
 10 for (std::size_t i = r_idx + 2; i < m_row_offsets.size(); ++i) {
174 6 m_row_offsets[i] += new_row_len;
175 }
176 4 }
177
178 void insert_row(std::size_t r_idx, const std::vector<T>& new_row_data) {
179 check_row_insert_bounds(r_idx, "insert_row");
180
181 std::size_t insert_data_pos = m_row_offsets[r_idx];
182 std::size_t new_row_len = new_row_data.size();
183
184 m_data.insert(m_data.begin() + insert_data_pos, new_row_data.begin(), new_row_data.end());
185 m_row_offsets.insert(m_row_offsets.begin() + r_idx + 1, m_row_offsets[r_idx] + new_row_len);
186 for (std::size_t i = r_idx + 2; i < m_row_offsets.size(); ++i) {
187 m_row_offsets[i] += new_row_len;
188 }
189 }
190
191 6 void remove_row(std::size_t r_idx) {
192 6 check_row_bounds(r_idx, "remove_row");
193
194 5 std::size_t start_data_pos = m_row_offsets[r_idx];
195 5 std::size_t end_data_pos = m_row_offsets[r_idx + 1];
196 5 std::size_t removed_len = end_data_pos - start_data_pos;
197
198
1/2
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
 25 m_data.erase(m_data.begin() + start_data_pos, m_data.begin() + end_data_pos);
199
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 20 m_row_offsets.erase(m_row_offsets.begin() + r_idx + 1);
200
201
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 5 times.
 9 for (std::size_t i = r_idx + 1; i < m_row_offsets.size(); ++i) {
202 4 m_row_offsets[i] -= removed_len;
203 }
204 5 }
205
206 void add_element(std::size_t r_idx, const T& value) {
207 check_row_bounds(r_idx, "add_element");
208
209 std::size_t insert_data_pos = m_row_offsets[r_idx + 1];
210 m_data.insert(m_data.begin() + insert_data_pos, value);
211
212 for (std::size_t i = r_idx + 1; i < m_row_offsets.size(); ++i) {
213 m_row_offsets[i] += 1;
214 }
215 }
216
217 7 void add_element(std::size_t r_idx, T&& value) {
218 7 check_row_bounds(r_idx, "add_element");
219
220 6 std::size_t insert_data_pos = m_row_offsets[r_idx + 1];
221
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 24 m_data.insert(m_data.begin() + insert_data_pos, std::move(value));
222
2/2
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 6 times.
 17 for (std::size_t i = r_idx + 1; i < m_row_offsets.size(); ++i) {
223 11 m_row_offsets[i] += 1;
224 }
225 6 }
226
227 3 void clear() noexcept {
228 3 m_data.clear();
229 3 m_row_offsets.assign(1, 0);
230 3 }
231
232 26 bool is_empty() const noexcept { return num_rows() == 0; }
233
234 template <bool IsConstIter>
235 class RowIterator {
236 public:
237 using iterator_category = std::random_access_iterator_tag;
238 using difference_type = std::ptrdiff_t;
239 using value_type =
240 typename std::conditional<IsConstIter, std::span<const T>, std::span<T>>::type;
241 using pointer = value_type*;
242 using reference = value_type;
243
244 using ParentArrayPtr =
245 typename std::conditional<IsConstIter, const JaggedArray<T>*, JaggedArray<T>*>::type;
246
247 private:
248 ParentArrayPtr m_parent_array;
249 std::size_t m_current_row_idx;
250
251 public:
252 34 RowIterator(ParentArrayPtr parent, std::size_t r_idx)
253 34 : m_parent_array(parent), m_current_row_idx(r_idx) {}
254
255 26 reference operator*() const {
256
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 11 times.
 26 if (m_current_row_idx == m_parent_array->num_rows()) {
257 if constexpr (IsConstIter) {
258 ✗ return std::span<const T>();
259 } else {
260 4 return std::span<T>();
261 }
262 }
263 // CORRECTED: Accessing members without trailing underscore
264 22 std::size_t start_offset = m_parent_array->m_row_offsets[m_current_row_idx];
265 22 std::size_t length = m_parent_array->m_row_offsets[m_current_row_idx + 1] - start_offset;
266
267 if constexpr (IsConstIter) {
268 6 return std::span<const T>(m_parent_array->m_data.data() + start_offset, length);
269 } else {
270 16 return std::span<T>(m_parent_array->m_data.data() + start_offset, length);
271 }
272 }
273
274 14 RowIterator& operator++() {
275 14 ++m_current_row_idx;
276 14 return *this;
277 }
278 RowIterator operator++(int) {
279 RowIterator tmp = *this;
280 ++(*this);
281 return tmp;
282 }
283 1 RowIterator& operator--() {
284 1 --m_current_row_idx;
285 1 return *this;
286 }
287 RowIterator operator--(int) {
288 RowIterator tmp = *this;
289 --(*this);
290 return tmp;
291 }
292
293 2 RowIterator& operator+=(difference_type n) {
294 2 m_current_row_idx += n;
295 2 return *this;
296 }
297 1 RowIterator operator+(difference_type n) const {
298 1 RowIterator temp = *this;
299 1 temp += n;
300 1 return temp;
301 }
302 friend RowIterator operator+(difference_type n, const RowIterator& iter) { return iter + n; }
303
304 RowIterator& operator-=(difference_type n) {
305 m_current_row_idx -= n;
306 return *this;
307 }
308 RowIterator operator-(difference_type n) const {
309 RowIterator temp = *this;
310 temp -= n;
311 return temp;
312 }
313 1 difference_type operator-(const RowIterator& other) const {
314 1 return static_cast<difference_type>(m_current_row_idx) -
315 1 static_cast<difference_type>(other.m_current_row_idx);
316 }
317
318 reference operator[](difference_type n) const { return *(*this + n); }
319
320 30 bool operator==(const RowIterator& other) const {
321
3/4
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 9 times.
 30 return m_parent_array == other.m_parent_array && m_current_row_idx == other.m_current_row_idx;
322 }
323 24 bool operator!=(const RowIterator& other) const { return !(*this == other); }
324 bool operator<(const RowIterator& other) const {
325 return m_current_row_idx < other.m_current_row_idx;
326 }
327 bool operator>(const RowIterator& other) const { return other < *this; }
328 bool operator<=(const RowIterator& other) const { return !(other < *this); }
329 bool operator>=(const RowIterator& other) const { return !(*this < other); }
330 };
331
332 using iterator = RowIterator<false>;
333 using const_iterator = RowIterator<true>;
334
335 7 iterator begin() { return iterator(this, 0); }
336 6 iterator end() { return iterator(this, num_rows()); }
337
338 1 const_iterator begin() const { return const_iterator(this, 0); }
339 1 const_iterator end() const { return const_iterator(this, num_rows()); }
340 1 const_iterator cbegin() const { return const_iterator(this, 0); }
341 1 const_iterator cend() const { return const_iterator(this, num_rows()); }
342
343 friend std::ostream& operator<< <>(std::ostream& os, const JaggedArray<T>& arr);
344 };
345
346 template <typename T>
347 4 std::ostream& operator<<(std::ostream& os, const JaggedArray<T>& arr) {
348 4 os << "JaggedArray (" << arr.num_rows() << " rows, " << arr.total_elements()
349 4 << " total elements):\n";
350
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
 4 if (arr.is_empty()) {
351 2 os << " (empty)\n";
352 2 return os;
353 }
354
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 1 times.
 8 for (std::size_t i = 0; i < arr.num_rows(); ++i) {
355
6/12
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 3 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 3 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 3 times.
✗ Branch 17 not taken.
 6 os << " [" << i << "] (" << arr.num_cols(i) << " elements): {";
356
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 std::span<const T> current_row_span = arr[i];
357
2/2
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 3 times.
 16 for (std::size_t j = 0; j < current_row_span.size(); ++j) {
358
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 10 os << current_row_span[j];
359
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 2 times.
 10 if (j < current_row_span.size() - 1) {
360
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 os << ", ";
361 }
362 }
363
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 os << "}\n";
364 }
365 2 return os;
366 }
367
368 } // namespace oiseau::utils
369