INSTINCT Code Coverage Report

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