INSTINCT Code Coverage Report

Directory: src/
File: util/Container/ScrollingBuffer.hpp
Date: 2025-06-02 15:19:59
Exec Total Coverage
Lines: 257 268 95.9%
Functions: 224 250 89.6%
Branches: 179 243 73.7%
Line Branch Exec Source
1 // This file is part of INSTINCT, the INS Toolkit for Integrated
2 // Navigation Concepts and Training by the Institute of Navigation of
3 // the University of Stuttgart, Germany.
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public
6 // License, v. 2.0. If a copy of the MPL was not distributed with this
7 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
8
9 /// @file ScrollingBuffer.hpp
10 /// @brief A buffer which is overwriting itself from the start when full
11 /// @author T. Topp (topp@ins.uni-stuttgart.de)
12 /// @date 2021-01-09
13
14 #pragma once
15
16 #include <vector>
17 #include <string>
18 #include <iostream>
19 #include <fmt/ostream.h>
20
21 namespace NAV
22 {
23
24 /// @brief A buffer which is overwriting itself from the start when full
25 /// @tparam T Type of data stored in the buffer
26 /// @tparam _Padding The padding are empty values at the start of the buffer to prevent overriding the start value in multithreaded applications
27 template<class T, size_t _Padding = 0>
28 class ScrollingBuffer
29 {
30 public:
31 // ###########################################################################################################
32 // Constructors
33 // ###########################################################################################################
34
35 /// @brief Reserves space for the buffer but does not fill the buffer with values
36 /// @param[in] maxSize The maximum size of the scrolling buffer
37 26514 explicit ScrollingBuffer(size_t maxSize = 0)
38
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 18 times.
 26514 : _infiniteBuffer(maxSize == 0), _maxSize(maxSize + _Padding), _dataStart(_Padding), _dataEnd(_infiniteBuffer ? 0 : _Padding)
39 {
40
1/2
✓ Branch 1 taken 14643 times.
✗ Branch 2 not taken.
 26514 _data.reserve(maxSize + _Padding);
41
1/2
✓ Branch 1 taken 14643 times.
✗ Branch 2 not taken.
 26514 _data.resize(_Padding);
42 26514 }
43
44 /// @brief Constructs a new container with the contents of the initializer list init.
45 /// @param[in] init initializer list to initialize the elements of the container with
46 2 ScrollingBuffer(std::initializer_list<T> init)
47 2 : _infiniteBuffer(init.size() == 0), _maxSize(init.size())
48 {
49
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 _data.reserve(init.size());
50
51
2/2
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 2 times.
 7 for (auto& val : init)
52 {
53
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 push_back(val);
54 }
55 2 }
56
57 // ###########################################################################################################
58 // Element access
59 // ###########################################################################################################
60
61 /// @brief Returns a reference to the element at specified location pos, with bounds checking.
62 /// If pos is not within the range of the container, an exception of type std::out_of_range is thrown.
63 /// @param[in] pos position of the element to return
64 /// @return Reference to the requested element.
65 2375463 T& at(size_t pos)
66 {
67 // Cast the const away and reuse the implementation below
68 2375463 return const_cast<T&>(static_cast<const ScrollingBuffer&>(*this).at(pos)); // NOLINT(cppcoreguidelines-pro-type-const-cast)
69 }
70
71 /// @brief Returns a reference to the element at specified location pos, with bounds checking.
72 /// If pos is not within the range of the container, an exception of type std::out_of_range is thrown.
73 /// @param[in] pos position of the element to return
74 /// @return Reference to the requested element.
75 53015393 [[nodiscard]] const T& at(size_t pos) const
76 {
77
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 51852604 times.
 53015393 if (!(pos < size()))
78 {
79
7/14
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 16 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 16 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 16 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 16 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 16 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 16 times.
✗ Branch 22 not taken.
 32 throw std::out_of_range("ScrollingBuffer::at: pos (which is "
80 + std::to_string(pos) + ") >= this->size() (which is " + std::to_string(size()) + ")");
81 }
82
83 // start/end
84 // |
85 // 8 9 3 4 5 6 7
86 // at(0) = 3, at(4) = 7, at(5) = 8
87
2/2
✓ Branch 0 taken 647488 times.
✓ Branch 1 taken 51205116 times.
 53015361 if (_dataStart + pos >= _maxSize)
88 {
89 938194 return _data.at(_dataStart + pos - _maxSize);
90 }
91
92 52077167 return _data.at(_dataStart + pos);
93 }
94
95 /// @brief Returns a reference to the first element in the container.
96 /// Calling front on an empty container is undefined.
97 /// @return reference to the first element
98 587226 T& front()
99 {
100 // Cast the const away and reuse the implementation below (don't repeat yourself)
101 587226 return const_cast<T&>(static_cast<const ScrollingBuffer&>(*this).front()); // NOLINT(cppcoreguidelines-pro-type-const-cast)
102 }
103
104 /// @brief Returns a reference to the first element in the container.
105 /// Calling front on an empty container is undefined.
106 /// @return Reference to the first element
107 1168518 [[nodiscard]] const T& front() const
108 {
109 1168518 return _data.at(_dataStart);
110 }
111
112 /// @brief Returns a reference to the last element in the container.
113 /// Calling back on an empty container causes undefined behavior.
114 /// @return Reference to the last element.
115 6609466 T& back()
116 {
117 6609466 return const_cast<T&>(static_cast<const ScrollingBuffer&>(*this).back()); // NOLINT(cppcoreguidelines-pro-type-const-cast)
118 }
119
120 /// @brief Returns a reference to the last element in the container.
121 /// Calling back on an empty container causes undefined behavior.Reference to the last element.
122 /// @return Reference to the last element.
123 7888015 [[nodiscard]] const T& back() const
124 {
125
2/2
✓ Branch 0 taken 971643 times.
✓ Branch 1 taken 6625623 times.
 7888015 if (_dataEnd == 0)
126 {
127 1117003 return _data.back();
128 }
129
130 6771012 return _data.at(_dataEnd - 1);
131 }
132
133 // ###########################################################################################################
134 // Iterators
135 // ###########################################################################################################
136
137 /// @brief Iterator
138 class Iterator
139 {
140 public:
141 using iterator_category = std::forward_iterator_tag; ///< To categorize the iteration direction
142 using difference_type = std::ptrdiff_t; ///< Signed integer type (usually std::ptrdiff_t)
143 using value_type = T; ///< T
144 using pointer = T*; ///< value_type*
145 using reference = T&; ///< value_type&
146
147 /// @brief Constructor
148 /// @param[in] buffer Mutable reference to the buffer of the iterator
149 /// @param[in] index Iterator index inside the buffer (counted from the start)
150 1162672 explicit Iterator(ScrollingBuffer& buffer, size_t index = 0)
151 1162672 : buffer(buffer), index(index) {}
152
153 /// @brief Returns a reference to the current element.
154 1162609 reference operator*() const { return buffer.at(index); }
155 /// @brief Returns a pointer to the current element.
156 5 pointer operator->() { return &buffer.at(index); }
157
158 /// @brief Advances the iterator.
159 871978 Iterator& operator++()
160 {
161
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 871961 times.
 871978 if (index == buffer.size()) { return *this; }
162 871978 index++;
163 871978 return *this;
164 }
165 /// @brief Advances the iterator.
166 26 Iterator operator++(int)
167 {
168 26 Iterator tmp = *this;
169 26 operator++();
170 26 return tmp;
171 }
172
173 /// @brief Equality comparison operator
174 /// @param[in] lhs Left-hand side
175 /// @param[in] rhs Right-hand side
176 /// @return True if elements are equal
177
3/4
✓ Branch 0 taken 1453271 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 290662 times.
✓ Branch 3 taken 1162609 times.
 1453288 friend bool operator==(const Iterator& lhs, const Iterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
178 /// @brief Inequality comparison operator
179 /// @param[in] lhs Left-hand side
180 /// @param[in] rhs Right-hand side
181 /// @return False if elements are equal
182 1453286 friend bool operator!=(const Iterator& lhs, const Iterator& rhs) { return !(lhs == rhs); };
183
184 private:
185 ScrollingBuffer& buffer; ///< Reference to the buffer
186 size_t index; ///< Iterator index inside the buffer (counted from the start)
187 };
188
189 /// @brief Returns an iterator to the first element of the vector.
190 ///
191 /// If the buffer is empty, the returned iterator will be equal to end().
192 581326 Iterator begin() { return Iterator(*this, 0); }
193 /// @brief Returns an iterator to the element following the last element of the vector.
194 ///
195 /// This element acts as a placeholder; attempting to access it results in undefined behavior.
196 581346 Iterator end() { return Iterator(*this, size()); }
197
198 /// Const iterator
199 class ConstIterator
200 {
201 public:
202 using iterator_category = std::forward_iterator_tag; ///< To categorize the iteration direction
203 using difference_type = std::ptrdiff_t; ///< Signed integer type (usually std::ptrdiff_t)
204 using value_type = T; ///< T
205 using pointer = const T*; ///< value_type*
206 using reference = const T&; ///< value_type&
207
208 /// @brief Constructor
209 /// @param[in] buffer Immutable reference to the buffer of the iterator
210 /// @param[in] index Iterator index inside the buffer (counted from the start)
211 62 explicit ConstIterator(const ScrollingBuffer& buffer, size_t index = 0)
212 62 : buffer(buffer), index(index) {}
213
214 /// @brief Returns a reference to the current element.
215 20 reference operator*() const { return buffer.at(index); }
216 /// @brief Returns a pointer to the current element.
217 5 pointer operator->() { return &buffer.at(index); }
218
219 /// @brief Advances the iterator.
220 42 const ConstIterator& operator++()
221 {
222
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 21 times.
 42 if (index == buffer.size()) { return *this; }
223 42 index++;
224 42 return *this;
225 }
226 /// @brief Advances the iterator.
227 26 ConstIterator operator++(int)
228 {
229 26 ConstIterator tmp = *this;
230 26 operator++();
231 26 return tmp;
232 }
233
234 /// @brief Equality comparison operator
235 /// @param[in] lhs Left-hand side
236 /// @param[in] rhs Right-hand side
237 /// @return True if elements are equal
238
3/4
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 21 times.
 56 friend bool operator==(const ConstIterator& lhs, const ConstIterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
239 /// @brief Inequality comparison operator
240 /// @param[in] lhs Left-hand side
241 /// @param[in] rhs Right-hand side
242 /// @return False if elements are equal
243 54 friend bool operator!=(const ConstIterator& lhs, const ConstIterator& rhs) { return !(lhs == rhs); };
244
245 private:
246 const ScrollingBuffer& buffer; ///< Reference to the buffer
247 size_t index; ///< Iterator index inside the buffer (counted from the start)
248 };
249
250 /// @brief Returns an iterator to the first element of the vector.
251 ///
252 /// If the buffer is empty, the returned iterator will be equal to end().
253 3 [[nodiscard]] ConstIterator begin() const { return ConstIterator(*this, 0); }
254 /// @brief Returns an iterator to the element following the last element of the vector.
255 ///
256 /// This element acts as a placeholder; attempting to access it results in undefined behavior.
257 3 [[nodiscard]] ConstIterator end() const { return ConstIterator(*this, size()); }
258 /// @brief Returns an iterator to the first element of the vector.
259 ///
260 /// If the buffer is empty, the returned iterator will be equal to end().
261 12 [[nodiscard]] ConstIterator cbegin() const { return ConstIterator(*this, 0); }
262 /// @brief Returns an iterator to the element following the last element of the vector.
263 ///
264 /// This element acts as a placeholder; attempting to access it results in undefined behavior.
265 38 [[nodiscard]] ConstIterator cend() const { return ConstIterator(*this, size()); }
266
267 /// Reverse Iterator
268 class ReverseIterator
269 {
270 public:
271 using iterator_category = std::forward_iterator_tag; ///< To categorize the iteration direction
272 using difference_type = std::ptrdiff_t; ///< Signed integer type (usually std::ptrdiff_t)
273 using value_type = T; ///< T
274 using pointer = T*; ///< value_type*
275 using reference = T&; ///< value_type&
276
277 /// @brief Constructor
278 /// @param[in] buffer Mutable reference to the buffer of the iterator
279 /// @param[in] index Iterator index inside the buffer (counted from the non-reversed start)
280 52 explicit ReverseIterator(ScrollingBuffer& buffer, int64_t index = 0)
281 52 : buffer(buffer), index(index) {}
282
283 /// @brief Returns a reference to the current element.
284 13 reference operator*() const { return buffer.at(static_cast<size_t>(index)); }
285 /// @brief Returns a pointer to the current element.
286 5 pointer operator->() { return &buffer.at(static_cast<size_t>(index)); }
287
288 /// @brief Advances the iterator.
289 34 ReverseIterator& operator++()
290 {
291
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
 34 if (index < 0) { return *this; }
292 34 index--;
293 34 return *this;
294 }
295 /// @brief Advances the iterator.
296 26 ReverseIterator operator++(int)
297 {
298 26 ReverseIterator tmp = *this;
299 26 operator++();
300 26 return tmp;
301 }
302
303 /// @brief Equality comparison operator
304 /// @param[in] lhs Left-hand side
305 /// @param[in] rhs Right-hand side
306 /// @return True if elements are equal
307
3/4
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 13 times.
 34 friend bool operator==(const ReverseIterator& lhs, const ReverseIterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
308 /// @brief Inequality comparison operator
309 /// @param[in] lhs Left-hand side
310 /// @param[in] rhs Right-hand side
311 /// @return False if elements are equal
312 32 friend bool operator!=(const ReverseIterator& lhs, const ReverseIterator& rhs) { return !(lhs == rhs); };
313
314 private:
315 ScrollingBuffer& buffer; ///< Reference to the buffer
316 int64_t index; ///< Iterator index inside the buffer (counted from the non-reversed start)
317 };
318
319 /// @brief Returns a reverse iterator to the first element of the reversed vector.
320 ///
321 /// It corresponds to the last element of the non-reversed vector.
322 /// If the vector is empty, the returned iterator is equal to rend().
323 16 ReverseIterator rbegin() { return ReverseIterator(*this, static_cast<int64_t>(size()) - 1); }
324 /// @brief Returns a reverse iterator to the element following the last element of the reversed vector.
325 ///
326 /// It corresponds to the element preceding the first element of the non-reversed vector.
327 /// This element acts as a placeholder, attempting to access it results in undefined behavior.
328 36 ReverseIterator rend() { return ReverseIterator(*this, -1); }
329
330 /// Const reverse iterator
331 class ConstReverseIterator
332 {
333 public:
334 using iterator_category = std::forward_iterator_tag; ///< To categorize the iteration direction
335 using difference_type = std::ptrdiff_t; ///< Signed integer type (usually std::ptrdiff_t)
336 using value_type = T; ///< T
337 using pointer = const T*; ///< value_type*
338 using reference = const T&; ///< value_type&
339
340 /// @brief Constructor
341 /// @param[in] buffer Immutable reference to the buffer of the iterator
342 /// @param[in] index Iterator index inside the buffer (counted from the non-reversed start)
343 46 explicit ConstReverseIterator(const ScrollingBuffer& buffer, int64_t index = 0)
344 46 : buffer(buffer), index(index) {}
345
346 /// @brief Returns a reference to the current element.
347 10 reference operator*() const { return buffer.at(static_cast<size_t>(index)); }
348 /// @brief Returns a pointer to the current element.
349 5 pointer operator->() { return &buffer.at(static_cast<size_t>(index)); }
350
351 /// @brief Advances the iterator.
352 26 const ConstReverseIterator& operator++()
353 {
354
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 26 if (index < 0) { return *this; }
355 26 index--;
356 26 return *this;
357 }
358 /// @brief Advances the iterator.
359 26 ConstReverseIterator operator++(int)
360 {
361 26 ConstReverseIterator tmp = *this;
362 26 operator++();
363 26 return tmp;
364 }
365
366 /// @brief Equality comparison operator
367 /// @param[in] lhs Left-hand side
368 /// @param[in] rhs Right-hand side
369 /// @return True if elements are equal
370
3/4
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 13 times.
 34 friend bool operator==(const ConstReverseIterator& lhs, const ConstReverseIterator& rhs) { return &lhs.buffer == &rhs.buffer && lhs.index == rhs.index; };
371 /// @brief Inequality comparison operator
372 /// @param[in] lhs Left-hand side
373 /// @param[in] rhs Right-hand side
374 /// @return False if elements are equal
375 32 friend bool operator!=(const ConstReverseIterator& lhs, const ConstReverseIterator& rhs) { return !(lhs == rhs); };
376
377 private:
378 const ScrollingBuffer& buffer; ///< Reference to the buffer
379 int64_t index; ///< Iterator index inside the buffer (counted from the non-reversed start)
380 };
381
382 /// @brief Returns a reverse iterator to the first element of the reversed vector.
383 ///
384 /// It corresponds to the last element of the non-reversed vector.
385 /// If the vector is empty, the returned iterator is equal to rend().
386 [[nodiscard]] ConstReverseIterator rbegin() const { return ConstReverseIterator(*this, static_cast<int64_t>(size()) - 1); }
387 /// @brief Returns a reverse iterator to the element following the last element of the reversed vector.
388 ///
389 /// It corresponds to the element preceding the first element of the non-reversed vector.
390 /// This element acts as a placeholder, attempting to access it results in undefined behavior.
391 [[nodiscard]] ConstReverseIterator rend() const { return ConstReverseIterator(*this, -1); }
392 /// @brief Returns a reverse iterator to the first element of the reversed vector.
393 ///
394 /// It corresponds to the last element of the non-reversed vector.
395 /// If the vector is empty, the returned iterator is equal to rend().
396 12 [[nodiscard]] ConstReverseIterator crbegin() const { return ConstReverseIterator(*this, static_cast<int64_t>(size()) - 1); }
397 /// @brief Returns a reverse iterator to the element following the last element of the reversed vector.
398 ///
399 /// It corresponds to the element preceding the first element of the non-reversed vector.
400 /// This element acts as a placeholder, attempting to access it results in undefined behavior.
401 34 [[nodiscard]] ConstReverseIterator crend() const { return ConstReverseIterator(*this, -1); }
402
403 // ###########################################################################################################
404 // Capacity
405 // ###########################################################################################################
406
407 /// @brief Checks if the container has no elements
408 8822149 [[nodiscard]] bool empty() const
409 {
410 8822149 return size() == 0;
411 }
412
413 /// @brief Checks if the container is full (never full when infinite buffer)
414 6485613 [[nodiscard]] bool full() const
415 {
416
3/4
✓ Branch 0 taken 6194914 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 584157 times.
✓ Branch 4 taken 5610757 times.
 6485613 return !_infiniteBuffer && _maxSize - _Padding == size();
417 }
418
419 /// @brief Returns the number of elements in the container
420 98546772 [[nodiscard]] size_t size() const
421 {
422
4/4
✓ Branch 0 taken 89923460 times.
✓ Branch 1 taken 4843657 times.
✓ Branch 2 taken 17927106 times.
✓ Branch 3 taken 71996354 times.
 98546772 if (_dataStart == _Padding && _dataEnd == _Padding) // Buffer empty or full and not scrolled
423 {
424 19816761 return _data.size() - _Padding;
425 }
426
2/2
✓ Branch 0 taken 71996231 times.
✓ Branch 1 taken 4843780 times.
 78730011 if (_dataStart < _dataEnd) // not scrolled buffer
427 {
428 71996423 return _dataEnd - _dataStart;
429 }
430
431 // scrolled buffer
432 6733588 return _maxSize - (_dataStart - _dataEnd);
433 }
434
435 /// @brief Increase the capacity of the vector to a value that's greater or equal to new_cap.
436 /// @param new_cap New capacity of the vector, in number of elements
437 ✗ void reserve(size_t new_cap)
438 {
439 ✗ _data.reserve(new_cap);
440 ✗ }
441
442 /// @brief Returns the number of elements that can be held in currently allocated storage
443 925192 [[nodiscard]] size_t capacity() const
444 {
445
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 634316 times.
 925192 return _infiniteBuffer ? 0 : (_maxSize - _Padding);
446 }
447
448 // ###########################################################################################################
449 // Modifiers
450 // ###########################################################################################################
451
452 /// @brief Erases all elements from the container. After this call, size() returns zero.
453 35476 void clear()
454 {
455 35476 _data.clear();
456 35476 _dataStart = _Padding;
457
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 35476 _dataEnd = _infiniteBuffer ? 0 : _Padding;
458
459
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 35484 for (size_t i = 0; i < _Padding; i++)
460 {
461
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 _data.push_back({});
462 }
463 35476 }
464
465 /// @brief Appends the given element value to the end of the container.
466 /// @param[in] value the value of the element to append
467 6536283 void push_back(const T& value)
468 {
469
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 6245217 times.
 6536283 if (_infiniteBuffer) // The buffer should grow when adding new values
470 {
471 78 _data.push_back(value);
472 78 _maxSize = _data.size();
473 }
474
2/2
✓ Branch 1 taken 5611003 times.
✓ Branch 2 taken 634214 times.
 6536205 else if (_data.size() < _maxSize) // The real buffer is smaller than the allowed buffer size
475 {
476 5611251 _data.push_back(value);
477 5611251 _dataEnd = (_dataEnd + 1) % _maxSize;
478 }
479 else // The real buffer as large as or bigger than the allowed buffer size, so we have to scroll the buffer
480 {
481 924954 _data.at(_dataEnd) = value;
482
2/2
✓ Branch 2 taken 340707 times.
✓ Branch 3 taken 293507 times.
 924954 if (size() >= capacity())
483 {
484 // "5, 6, _, _, 2, 3, 4"
485 // "5, 6, 7, _, 2, 3, 4"
486 631434 _dataStart = (_dataStart + 1) % _maxSize;
487 }
488 924954 _dataEnd = (_dataEnd + 1) % _maxSize;
489 }
490 6536283 }
491
492 /// @brief Removes the first element of the container
493 293548 void pop_front()
494 {
495
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 293521 times.
 293548 if (empty())
496 {
497 ✗ return;
498 }
499
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 293520 times.
 293548 if (size() == 1)
500 {
501 2 clear();
502 2 return;
503 }
504
505
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 293519 times.
 293546 if (_infiniteBuffer)
506 {
507
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 2 _data.erase(_data.begin());
508 2 _maxSize = _data.size();
509 }
510 else
511 {
512 // se e s e s s e se
513 // 5, 6, 2, 3, 4 // 5, 6, _, _, 2, 3, 4 // 5, 6, X, X, 2, 3, 4 // X, 6, 7, 8, 9, 10, X // 5, 6, 7, 4
514 // e s e s e s s e s e
515 // 5, 6, _, 3, 4 // 5, 6, _, _, _, 3, 4 // 5, 6, _, X, X, 3, 4 // X, X, 7, 8, 9, 10, _ // 5, 6, 7, _
516
517
1/2
✓ Branch 2 taken 293494 times.
✗ Branch 3 not taken.
 293544 front() = {}; // Set to default in case shared_ptr is stored
518 293544 _dataStart = (_dataStart + 1) % _maxSize;
519 }
520 }
521
522 /// @brief Removes the last element of the container
523 22 void pop_back()
524 {
525
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 11 times.
 22 if (empty())
526 {
527 ✗ return;
528 }
529
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 10 times.
 22 if (size() == 1)
530 {
531 2 clear();
532 2 return;
533 }
534
535
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 9 times.
 20 if (_infiniteBuffer)
536 {
537 2 _data.pop_back();
538 2 _maxSize = _data.size();
539 }
540 else
541 {
542 18 back() = {}; // Set to default in case shared_ptr is stored
543
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 7 times.
 18 _dataEnd = _dataEnd == 0 ? _maxSize - 1 : (_dataEnd - 1);
544 }
545 }
546
547 /// @brief Resizes the buffer to the specified size
548 /// @param[in] targetSize The new buffer size (0 for infinite buffer)
549 2717 void resize(size_t targetSize)
550 {
551
2/2
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 2529 times.
 2717 if (targetSize == 0) // Buffer should grow indefinitely when adding new values
552 {
553 146 _infiniteBuffer = true;
554
555
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 65 times.
 146 if (isScrolled()) // Buffer is scrolled and needs to be sorted in order of insertion
556 {
557 // se e s e s s e
558 // 5, 6, 2, 3, 4 // 5, 6, _, _, 2, 3, 4 // 5, 6, X, X, 2, 3, 4 // X, 6, 7, 8, 9, 10, X
559 // 2, 3, 4, 5, 6 // 2, 3, 4, 5, 6, _, _ // X, X, 2, 3, 4, 5, 6 // X, X, 6, 7, 8, 9, 10
560 16 std::vector<T> to_vector;
561
562
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 7 times.
 16 if (_dataEnd > _dataStart)
563 {
564
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 4 std::copy(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)), _data.end(),
565 std::back_inserter(to_vector));
566 2 _maxSize = _dataEnd;
567 }
568
569
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
 64 std::copy(std::next(_data.begin(), std::max(static_cast<int>(_dataStart - _Padding), 0)),
570 16 std::next(_data.begin(), static_cast<int64_t>(std::max(_dataEnd, _maxSize))),
571 std::back_inserter(to_vector));
572
573
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 2 times.
 16 if (int64_t elementsFront = std::min(static_cast<int64_t>(_dataEnd), static_cast<int64_t>(_dataStart - _Padding));
574 elementsFront > 0)
575 {
576
2/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
 24 std::copy(_data.begin(), std::next(_data.begin(), elementsFront),
577 std::back_inserter(to_vector));
578 }
579 16 _data.swap(to_vector);
580
581 16 _maxSize = _data.size();
582
583 16 _dataStart = _Padding;
584 16 _dataEnd = 0;
585 16 }
586 }
587 else // Buffer should have scrolling behaviour when adding new values
588 {
589 2571 _infiniteBuffer = false;
590
591
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 2510 times.
 2571 if (_maxSize - _Padding > targetSize) // We make the buffer smaller
592 {
593
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 13 times.
 38 if (!isScrolled()) // Buffer is not scrolled, so shrinking removes the values from the front of the buffer
594 {
595 12 size_t elementsToDelete = _maxSize - _Padding - targetSize;
596
597 24 if (size_t emptyAtTheBack = _maxSize - _dataEnd;
598
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 12 size_t emptyAtTheBackToDelete = std::min(emptyAtTheBack, elementsToDelete))
599 {
600 // 1, 2, 3, _, _, // X, X, 1, 2, 3, _, _,
601 // 1, 2, 3, _, // X, X, 1, 2, 3, _,
602 12 _maxSize -= emptyAtTheBackToDelete;
603 12 _dataEnd %= _maxSize; // NOLINT(clang-analyzer-core.DivideZero) // this lint is wrong, even when wrapped by `if(_maxSize != 0)` appearing
604 12 elementsToDelete -= emptyAtTheBackToDelete;
605 // 1, 2, 3, // X, X, 1, 2, 3,
606 }
607
608 // 1, 2, 3,
609 // 2, 3,
610
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
 12 if (elementsToDelete)
611 {
612
1/2
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
 8 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart)),
613 8 std::next(_data.begin(), static_cast<int64_t>(_dataStart + elementsToDelete)));
614 4 _maxSize -= elementsToDelete;
615 }
616 }
617 else // Buffer is scrolled, so the correct values have to be erased from the buffer when shrinking
618 {
619 // 5, 6, _, _, 2, 3, 4, // 5, 6, _, _, X, X, 2, 3, 4,
620 // 6, // 6, X, X
621
622 // 6, 7, 3, 4, 5, // 5, 6, X, X, 2, 3, 4
623 // 6, 7, 4, 5, // 5, 6, X, X, 3, 4
624
625 // X, 6, 7, 8, 9, 10, X
626 // X, 9, 10, X
627
628 26 size_t elementsToDelete = _maxSize - _Padding - targetSize;
629
630 26 if (size_t emptyInBetween = static_cast<size_t>(std::max(static_cast<int>(_dataStart - _Padding - _dataEnd), 0));
631
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 11 times.
 26 size_t emptyInBetweenToDelete = std::min(emptyInBetween, elementsToDelete))
632 {
633 // 5, 6, _, _, 2, 3, 4, // 5, 6, _, _, X, X, 2, 3, 4,
634
1/2
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
 8 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
635 8 std::next(_data.begin(), static_cast<int64_t>(_dataEnd + emptyInBetweenToDelete)));
636 // 5, 6, _, 2, 3, 4, // 5, 6, _, X, X, 2, 3, 4,
637 4 _dataStart -= emptyInBetweenToDelete;
638 4 _maxSize -= emptyInBetweenToDelete;
639 4 elementsToDelete -= emptyInBetweenToDelete;
640 }
641
642 // s e
643 // X , 6, 7 , 8 , 9, 10, X
644 // X(8), 9, 10, X(7)
645 26 if (size_t paddingAtTheEnd = static_cast<size_t>(std::max(static_cast<int>(_Padding - _dataStart), 0));
646
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 10 times.
 26 size_t paddingAtTheEndToDelete = std::min(paddingAtTheEnd, elementsToDelete))
647 {
648
1/2
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 12 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
649 12 std::next(_data.begin(), static_cast<int64_t>(_dataEnd + paddingAtTheEndToDelete)));
650 6 _maxSize -= paddingAtTheEndToDelete;
651 6 _dataStart += paddingAtTheEndToDelete;
652 6 _dataEnd %= _maxSize;
653 6 elementsToDelete -= paddingAtTheEndToDelete;
654 }
655 // e s
656 // X, X, 6, 7 , 8 , 9, 10
657 // X, X, 7 , 8 , 9, 10
658
659
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12 times.
 26 if (size_t elementsAtTheBack = _maxSize - _dataStart - (_dataEnd > _dataStart ? _maxSize - _dataEnd : 0);
660
2/2
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 2 times.
 26 size_t elementsAtTheBackToDelete = std::min(elementsAtTheBack, elementsToDelete))
661 {
662 // 5, 6, 2, 3, 4, // 5, 6, X, X, 2, 3, 4,
663
1/2
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
 44 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart - _Padding)),
664 44 std::next(_data.begin(), static_cast<int64_t>(_dataStart - _Padding + elementsAtTheBackToDelete)));
665 // 5, 6, 4, // 5, 6, X, X, 4,
666 // 5, 6, // 5, 6, X, X,
667 22 _maxSize -= elementsAtTheBackToDelete;
668 22 _dataStart %= _maxSize;
669
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 22 if (_dataEnd > _maxSize)
670 {
671 ✗ _dataEnd -= elementsToDelete;
672 }
673 22 _dataEnd %= _maxSize;
674 22 elementsToDelete -= elementsAtTheBackToDelete;
675 }
676
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 9 times.
 26 if (elementsToDelete)
677 {
678 // 5, 6, // 5, 6, X, X,
679
1/2
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
 16 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart)),
680 16 std::next(_data.begin(), static_cast<int64_t>(std::min(_dataStart + elementsToDelete, _maxSize - _Padding))));
681 // 6, // 6, X, X
682 8 _maxSize -= elementsToDelete;
683
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 8 if (_dataEnd >= elementsToDelete)
684 {
685 4 _dataEnd -= elementsToDelete;
686 }
687 }
688 }
689 }
690
2/2
✓ Branch 0 taken 2459 times.
✓ Branch 1 taken 51 times.
 2533 else if (_maxSize - _Padding < targetSize) // We make the buffer bigger
691 {
692 // 1, 2, 3, _, _, // X, X, 0, 1, 2, 3, _, _
693 // 1, 2, 3, _, _, _, _, // X, X, 0, 1, 2, 3, _, _, _, _
694
2/2
✓ Branch 1 taken 2448 times.
✓ Branch 2 taken 11 times.
 2482 if (!isScrolled()) // Buffer not scrolled, so we can simply reserve more space
695 {
696 2460 _maxSize = targetSize + _Padding;
697 2460 _data.reserve(_maxSize);
698
2/2
✓ Branch 0 taken 2446 times.
✓ Branch 1 taken 2 times.
 2460 if (_dataEnd == 0) { _dataEnd = _data.size(); }
699 }
700 // se e s s e
701 // 6, 7, 3, 4, 5, // 5, 6, X, X, 2, 3, 4 // X, 6, 7, 8, 9, 10, X
702 // 6, 7, _, 3, 4, 5, // 5, 6, _, X, X, 2, 3, 4 // X, 6, 7, 8, 9, 10, _, _, X
703 else // (_dataStart != 0) // Buffer scrolled, so we need to copy the values to the correct positions
704 {
705
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 8 times.
 22 if (_dataEnd == 0) // Buffer actually not scrolled
706 {
707 6 _maxSize = targetSize + _Padding;
708
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 _data.reserve(_maxSize);
709 6 _dataEnd = _data.size();
710 6 return;
711 }
712
713
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 _data.resize(targetSize + _Padding);
714
715 16 auto copy_backward = [](auto first, auto last, auto d_last) { // Needed, as MacOS with C++23 does not support std::copy_backward
716
4/10
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✓ Branch 5 taken 4 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 18 times.
✓ Branch 14 taken 4 times.
 42 while (first != last)
717 {
718 34 *(--d_last) = *(--last);
719 }
720 };
721
722
0/2
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 copy_backward(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
723 16 std::next(_data.begin(), static_cast<int64_t>(_maxSize)),
724 8 std::next(_data.begin(), static_cast<int64_t>(targetSize + _Padding)));
725
726 16 auto diff = targetSize + _Padding - _maxSize;
727
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1 times.
 16 if (_dataStart >= _dataEnd)
728 {
729 14 _dataStart += diff;
730 }
731
732 16 _maxSize = targetSize + _Padding;
733 }
734 }
735 }
736 }
737
738 // ###########################################################################################################
739 // Other
740 // ###########################################################################################################
741
742 /// @brief Returns the largest value in the buffer
743 [[nodiscard]] T max() const
744 {
745 T currentMax = front();
746 for (size_t i = 0; i < _data.size(); i++)
747 {
748 if (i >= _dataStart || i < _dataEnd)
749 {
750 currentMax = std::max(currentMax, _data.at(i));
751 }
752 }
753 return currentMax;
754 }
755
756 /// @brief Returns the smallest value in the buffer
757 [[nodiscard]] T min() const
758 {
759 T currentMin = front();
760 for (size_t i = 0; i < _data.size(); i++)
761 {
762 if (i >= _dataStart || i < _dataEnd)
763 {
764 currentMin = std::min(currentMin, _data.at(i));
765 }
766 }
767 return currentMin;
768 }
769
770 /// @brief Returns the data index of the first element in the buffer
771 184 [[nodiscard]] int offset() const
772 {
773 184 return static_cast<int>(_dataStart);
774 }
775
776 /// @brief Returns a pointer to the raw data array (not in scrolled order)
777 ✗ [[nodiscard]] const T* data() const
778 {
779 ✗ return _data.data();
780 }
781
782 /// @brief Returns a pointer to the raw data array (not in scrolled order)
783 18 [[nodiscard]] T* data()
784 {
785 18 return _data.data();
786 }
787
788 /// @brief Returns whether the buffer is infinite and growing
789 ✗ [[nodiscard]] bool isInfiniteBuffer() const
790 {
791 ✗ return _infiniteBuffer;
792 }
793
794 /// @brief Converts the raw buffer to a string
795 576 [[nodiscard]] std::string getRawString() const
796 {
797 // Scrolled
798 // e s
799 // 5, 6, _, _, X, 2, 3, 4
800
801 // se
802 // 5, 6, 2, 3, 4
803
804 // s e
805 // _, 6, _, _, _
806
807 // Not scrolled
808 // s e
809 // X, X, 0, 1, 2, 3, _, _
810
811 // s e
812 // X, 6, 7, 8, 9, 10, _, _, X
813
814 // s e
815 // 6, X, X,
816
817 // s e
818 // 6, _, X, X,
819
820 // se
821 // X, X, _, _, _,
822
823 576 std::string out;
824
825
2/2
✓ Branch 0 taken 1777 times.
✓ Branch 1 taken 288 times.
 4130 for (int i = 0; static_cast<size_t>(i) < _maxSize; i++) // X, 6, 7, 8, 9, 10, _, _, X
826 {
827
4/4
✓ Branch 0 taken 1490 times.
✓ Branch 1 taken 287 times.
✓ Branch 2 taken 1302 times.
✓ Branch 3 taken 188 times.
 3554 if ((i >= static_cast<int>(_dataStart - _Padding) && static_cast<size_t>(i) < _dataStart)
828
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 1541 times.
 3178 || (static_cast<size_t>(i) >= _dataStart + _maxSize - _Padding))
829 {
830
1/2
✓ Branch 1 taken 236 times.
✗ Branch 2 not taken.
 472 out += "X"; // padding
831 }
832
1/2
✓ Branch 1 taken 1541 times.
✗ Branch 2 not taken.
 3082 else if (bool scrolled = isScrolled();
833 3082 static_cast<size_t>(i) >= _data.size()
834
8/8
✓ Branch 0 taken 1062 times.
✓ Branch 1 taken 252 times.
✓ Branch 2 taken 704 times.
✓ Branch 3 taken 358 times.
✓ Branch 4 taken 694 times.
✓ Branch 5 taken 10 times.
✓ Branch 6 taken 623 times.
✓ Branch 7 taken 71 times.
 2628 || (scrolled && static_cast<size_t>(i) >= _dataEnd && (static_cast<int>(_dataStart - _Padding) < 0 || i < static_cast<int>(_dataStart - _Padding)))
835
8/8
✓ Branch 0 taken 981 times.
✓ Branch 1 taken 252 times.
✓ Branch 2 taken 183 times.
✓ Branch 3 taken 798 times.
✓ Branch 4 taken 156 times.
✓ Branch 5 taken 27 times.
✓ Branch 6 taken 142 times.
✓ Branch 7 taken 14 times.
 2466 || (scrolled && _dataStart < _dataEnd && (static_cast<size_t>(i) < _dataStart || static_cast<size_t>(i) >= _dataEnd))
836
10/10
✓ Branch 0 taken 1314 times.
✓ Branch 1 taken 227 times.
✓ Branch 3 taken 1180 times.
✓ Branch 4 taken 12 times.
✓ Branch 5 taken 240 times.
✓ Branch 6 taken 940 times.
✓ Branch 7 taken 14 times.
✓ Branch 8 taken 226 times.
✓ Branch 9 taken 363 times.
✓ Branch 10 taken 1178 times.
 5710 || (_data.size() > 1 && !scrolled && static_cast<size_t>(i) >= _dataEnd))
837 {
838
1/2
✓ Branch 1 taken 363 times.
✗ Branch 2 not taken.
 726 out += "_"; // empty
839 }
840 else
841 {
842
4/7
✓ Branch 1 taken 1178 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 64 times.
✓ Branch 5 taken 1114 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 64 times.
✗ Branch 8 not taken.
 2356 out += std::to_string(_data.at(static_cast<size_t>(i)));
843 }
844
2/2
✓ Branch 0 taken 1491 times.
✓ Branch 1 taken 286 times.
 3554 if (static_cast<size_t>(i) != _maxSize - 1)
845 {
846
1/2
✓ Branch 1 taken 1491 times.
✗ Branch 2 not taken.
 2982 out += ", ";
847 }
848 }
849 576 return out;
850 ✗ }
851
852 /// @brief Prints the buffer to the output stream
853 /// @param[in, out] os The output stream to print to
854 /// @param[in] buffer The buffer to print
855 /// @return The output stream given as parameter
856 3 friend std::ostream& operator<<(std::ostream& os, const ScrollingBuffer<T, _Padding>& buffer)
857 {
858
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 6 os << fmt::format("{}", fmt::join(buffer, ", "));
859 3 return os;
860 }
861
862 private:
863 /// A Flag whether the buffer is currently growing every time when values are inserted or if it is overwriting itself from the start when full
864 bool _infiniteBuffer{ false };
865 /// The maximum amount of objects to store in the buffer before overwriting itself when full
866 /// When _infiniteBuffer == true, then this corresponds to m_data.size()
867 size_t _maxSize;
868 /// The index of the first element in the scrolling buffer (0 if the buffer is empty)
869 size_t _dataStart{ 0 };
870 /// The index one after the last element (0 if the buffer is empty)
871 size_t _dataEnd{ 0 };
872 /// The data storage object
873 std::vector<T> _data;
874
875 /// @brief Checks if the buffer is scrolled
876 4092 [[nodiscard]] bool isScrolled() const
877 {
878
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2436 times.
 4092 if (_data.size() == 1) { return false; }
879
880 // e s
881 // 5, 6, _, _, X, 2, 3, 4
882
883 // se
884
3/6
✓ Branch 0 taken 2436 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 2436 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2436 times.
 4074 if (_dataEnd == 0 && !empty()) // 1, 2, 3, 4
885 {
886 382 return true;
887 }
888
889 3692 return _dataEnd < _dataStart
890
2/4
✓ Branch 0 taken 2436 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2436 times.
 3692 || (_dataStart != _Padding);
891
892 // se // se
893 // 5, 6, 2, 3, 4 // X, X, _, _, _
894
895 // s e
896 // X, 0, 1, 2, 3, _, _, X // Scrolled
897 // s e
898 // X, X, 0, 1, 2, 3, _, _ // Not scrolled
899 }
900 };
901
902 } // namespace NAV
903
904 #ifndef DOXYGEN_IGNORE
905
906 template<class T, size_t _Padding>
907 struct fmt::formatter<NAV::ScrollingBuffer<T, _Padding>> : ostream_formatter
908 {};
909
910 #endif
911