INSTINCT Code Coverage Report


Directory: src/
File: util/Container/ScrollingBuffer.hpp
Date: 2025-06-06 13:17:47
Exec Total Coverage
Lines: 257 268 95.9%
Functions: 224 250 89.6%
Branches: 181 247 73.3%

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