INSTINCT Code Coverage Report

Directory: src/
File: util/Container/ScrollingBuffer.hpp
Date: 2025-02-07 16:54:41
Exec Total Coverage
Lines: 239 249 96.0%
Functions: 227 252 90.1%
Branches: 163 223 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
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 26816 explicit ScrollingBuffer(size_t maxSize = 0)
38
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 18 times.
 26816 : _infiniteBuffer(maxSize == 0), _maxSize(maxSize + _Padding), _dataStart(_Padding), _dataEnd(_infiniteBuffer ? 0 : _Padding)
39 {
40
1/2
✓ Branch 1 taken 14673 times.
✗ Branch 2 not taken.
 26816 _data.reserve(maxSize + _Padding);
41
1/2
✓ Branch 1 taken 14673 times.
✗ Branch 2 not taken.
 26816 _data.resize(_Padding);
42 26816 }
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 2325518 T& at(size_t pos)
66 {
67 // Cast the const away and reuse the implementation below
68 2325518 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 52965496 [[nodiscard]] const T& at(size_t pos) const
76 {
77
2/2
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 51802685 times.
 52965496 if (!(pos < size()))
78 {
79
7/14
✓ Branch 3 taken 12 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 12 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 12 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 12 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 12 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 12 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 12 times.
✗ Branch 22 not taken.
 24 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 647476 times.
✓ Branch 1 taken 51155209 times.
 52965472 if (_dataStart + pos >= _maxSize)
88 {
89 938182 return _data.at(_dataStart + pos - _maxSize);
90 }
91
92 52027290 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 496764 T& front()
99 {
100 // Cast the const away and reuse the implementation below (don't repeat yourself)
101 496764 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 1078080 [[nodiscard]] const T& front() const
108 {
109 1078080 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 7346876 T& back()
116 {
117 7346876 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 8969090 [[nodiscard]] const T& back() const
124 {
125
6/6
✓ Branch 1 taken 1826981 times.
✓ Branch 2 taken 5608584 times.
✓ Branch 3 taken 1222414 times.
✓ Branch 4 taken 604567 times.
✓ Branch 5 taken 6830998 times.
✓ Branch 6 taken 604567 times.
 8969090 if (_data.size() < _maxSize || _dataEnd == 0)
126 {
127 7908034 return _data.back();
128 }
129
130 1061056 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 1162708 explicit Iterator(ScrollingBuffer& buffer, size_t index = 0)
151 1162708 : buffer(buffer), index(index) {}
152
153 /// @brief Returns a reference to the current element.
154 1162645 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 872002 Iterator& operator++()
160 {
161
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 871985 times.
 872002 if (index == buffer.size()) { return *this; }
162 872002 index++;
163 872002 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 1453313 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 290668 times.
✓ Branch 3 taken 1162645 times.
 1453330 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 1453328 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 581344 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 581364 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 8127247 [[nodiscard]] bool empty() const
409 {
410 8127247 return size() == 0;
411 }
412
413 /// @brief Checks if the container is full (never full when infinite buffer)
414 6485593 [[nodiscard]] bool full() const
415 {
416
3/4
✓ Branch 0 taken 6194907 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 584168 times.
✓ Branch 4 taken 5610739 times.
 6485593 return !_infiniteBuffer && _maxSize - _Padding == size();
417 }
418
419 /// @brief Returns the number of elements in the container
420 98058221 [[nodiscard]] size_t size() const
421 {
422
4/4
✓ Branch 0 taken 89856893 times.
✓ Branch 1 taken 4274319 times.
✓ Branch 2 taken 17860625 times.
✓ Branch 3 taken 71996268 times.
 98058221 if (_dataStart == _Padding && _dataEnd == _Padding) // Buffer empty or full and not scrolled
423 {
424 20057865 return _data.size() - _Padding;
425 }
426
2/2
✓ Branch 0 taken 71996111 times.
✓ Branch 1 taken 4274476 times.
 78000356 if (_dataStart < _dataEnd) // not scrolled buffer
427 {
428 71996232 return _dataEnd - _dataStart;
429 }
430
431 // scrolled buffer
432 6004124 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 1078260 [[nodiscard]] size_t capacity() const
444 {
445
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 685865 times.
 1078260 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 45690 void clear()
454 {
455 45690 _data.clear();
456 45710 _dataStart = _Padding;
457
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 45710 _dataEnd = _infiniteBuffer ? 0 : _Padding;
458
459
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 45718 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 45710 }
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 6689397 void push_back(const T& value)
468 {
469
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 6296779 times.
 6689397 if (_infiniteBuffer) // The buffer should grow when adding new values
470 {
471 60 _data.push_back(value);
472 60 _maxSize = _data.size();
473 }
474
2/2
✓ Branch 1 taken 5610998 times.
✓ Branch 2 taken 685781 times.
 6689337 else if (_data.size() < _maxSize) // The real buffer is smaller than the allowed buffer size
475 {
476 5611275 _data.push_back(value);
477 5611275 _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 1078062 _data.at(_dataEnd) = value;
482
2/2
✓ Branch 2 taken 392277 times.
✓ Branch 3 taken 293504 times.
 1078062 if (size() >= capacity())
483 {
484 // "5, 6, _, _, 2, 3, 4"
485 // "5, 6, 7, _, 2, 3, 4"
486 784554 _dataStart = (_dataStart + 1) % _maxSize;
487 }
488 1078062 _dataEnd = (_dataEnd + 1) % _maxSize;
489 }
490 6689397 }
491
492 /// @brief Removes the first element of the container
493 293518 void pop_front()
494 {
495
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 293518 times.
 293518 if (empty())
496 {
497 ✗ return;
498 }
499
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 293517 times.
 293518 if (size() == 1)
500 {
501 1 clear();
502 1 return;
503 }
504
505
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 293516 times.
 293517 if (_infiniteBuffer)
506 {
507
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 1 _data.erase(_data.begin());
508 1 _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 293516 _dataStart = (_dataStart + 1) % _maxSize;
517 }
518 }
519
520 /// @brief Resizes the buffer to the specified size
521 /// @param[in] targetSize The new buffer size (0 for infinite buffer)
522 2938 void resize(size_t targetSize)
523 {
524
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 2600 times.
 2938 if (targetSize == 0) // Buffer should grow indefinitely when adding new values
525 {
526 156 _infiniteBuffer = true;
527
528
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 70 times.
 156 if (isScrolled()) // Buffer is scrolled and needs to be sorted in order of insertion
529 {
530 // se e s e s s e
531 // 5, 6, 2, 3, 4 // 5, 6, _, _, 2, 3, 4 // 5, 6, X, X, 2, 3, 4 // X, 6, 7, 8, 9, 10, X
532 // 2, 3, 4, 5, 6 // 2, 3, 4, 5, 6, _, _ // X, X, 2, 3, 4, 5, 6 // X, X, 6, 7, 8, 9, 10
533 16 std::vector<T> to_vector;
534
535
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 7 times.
 16 if (_dataEnd > _dataStart)
536 {
537
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(),
538 std::back_inserter(to_vector));
539 2 _maxSize = _dataEnd;
540 }
541
542
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)),
543 16 std::next(_data.begin(), static_cast<int64_t>(std::max(_dataEnd, _maxSize))),
544 std::back_inserter(to_vector));
545
546
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));
547 elementsFront > 0)
548 {
549
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),
550 std::back_inserter(to_vector));
551 }
552 16 _data.swap(to_vector);
553
554 16 _maxSize = _data.size();
555
556 16 _dataStart = _Padding;
557 16 _dataEnd = 0;
558 16 }
559 }
560 else // Buffer should have scrolling behaviour when adding new values
561 {
562 2782 _infiniteBuffer = false;
563
564
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 2581 times.
 2782 if (_maxSize - _Padding > targetSize) // We make the buffer smaller
565 {
566
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
567 {
568 12 size_t elementsToDelete = _maxSize - _Padding - targetSize;
569
570 24 if (size_t emptyAtTheBack = _maxSize - _dataEnd;
571
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 12 size_t emptyAtTheBackToDelete = std::min(emptyAtTheBack, elementsToDelete))
572 {
573 // 1, 2, 3, _, _, // X, X, 1, 2, 3, _, _,
574 // 1, 2, 3, _, // X, X, 1, 2, 3, _,
575 12 _maxSize -= emptyAtTheBackToDelete;
576 12 _dataEnd %= _maxSize; // NOLINT(clang-analyzer-core.DivideZero) // this lint is wrong, even when wrapped by `if(_maxSize != 0)` appearing
577 12 elementsToDelete -= emptyAtTheBackToDelete;
578 // 1, 2, 3, // X, X, 1, 2, 3,
579 }
580
581 // 1, 2, 3,
582 // 2, 3,
583
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
 12 if (elementsToDelete)
584 {
585
1/2
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
 8 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart)),
586 8 std::next(_data.begin(), static_cast<int64_t>(_dataStart + elementsToDelete)));
587 4 _maxSize -= elementsToDelete;
588 }
589 }
590 else // Buffer is scrolled, so the correct values have to be erased from the buffer when shrinking
591 {
592 // 5, 6, _, _, 2, 3, 4, // 5, 6, _, _, X, X, 2, 3, 4,
593 // 6, // 6, X, X
594
595 // 6, 7, 3, 4, 5, // 5, 6, X, X, 2, 3, 4
596 // 6, 7, 4, 5, // 5, 6, X, X, 3, 4
597
598 // X, 6, 7, 8, 9, 10, X
599 // X, 9, 10, X
600
601 26 size_t elementsToDelete = _maxSize - _Padding - targetSize;
602
603 26 if (size_t emptyInBetween = static_cast<size_t>(std::max(static_cast<int>(_dataStart - _Padding - _dataEnd), 0));
604
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 11 times.
 26 size_t emptyInBetweenToDelete = std::min(emptyInBetween, elementsToDelete))
605 {
606 // 5, 6, _, _, 2, 3, 4, // 5, 6, _, _, X, X, 2, 3, 4,
607
1/2
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
 8 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
608 8 std::next(_data.begin(), static_cast<int64_t>(_dataEnd + emptyInBetweenToDelete)));
609 // 5, 6, _, 2, 3, 4, // 5, 6, _, X, X, 2, 3, 4,
610 4 _dataStart -= emptyInBetweenToDelete;
611 4 _maxSize -= emptyInBetweenToDelete;
612 4 elementsToDelete -= emptyInBetweenToDelete;
613 }
614
615 // s e
616 // X , 6, 7 , 8 , 9, 10, X
617 // X(8), 9, 10, X(7)
618 26 if (size_t paddingAtTheEnd = static_cast<size_t>(std::max(static_cast<int>(_Padding - _dataStart), 0));
619
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 10 times.
 26 size_t paddingAtTheEndToDelete = std::min(paddingAtTheEnd, elementsToDelete))
620 {
621
1/2
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 12 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
622 12 std::next(_data.begin(), static_cast<int64_t>(_dataEnd + paddingAtTheEndToDelete)));
623 6 _maxSize -= paddingAtTheEndToDelete;
624 6 _dataStart += paddingAtTheEndToDelete;
625 6 _dataEnd %= _maxSize;
626 6 elementsToDelete -= paddingAtTheEndToDelete;
627 }
628 // e s
629 // X, X, 6, 7 , 8 , 9, 10
630 // X, X, 7 , 8 , 9, 10
631
632
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12 times.
 26 if (size_t elementsAtTheBack = _maxSize - _dataStart - (_dataEnd > _dataStart ? _maxSize - _dataEnd : 0);
633
2/2
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 2 times.
 26 size_t elementsAtTheBackToDelete = std::min(elementsAtTheBack, elementsToDelete))
634 {
635 // 5, 6, 2, 3, 4, // 5, 6, X, X, 2, 3, 4,
636
1/2
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
 44 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart - _Padding)),
637 44 std::next(_data.begin(), static_cast<int64_t>(_dataStart - _Padding + elementsAtTheBackToDelete)));
638 // 5, 6, 4, // 5, 6, X, X, 4,
639 // 5, 6, // 5, 6, X, X,
640 22 _maxSize -= elementsAtTheBackToDelete;
641 22 _dataStart %= _maxSize;
642
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 22 if (_dataEnd > _maxSize)
643 {
644 ✗ _dataEnd -= elementsToDelete;
645 }
646 22 _dataEnd %= _maxSize;
647 22 elementsToDelete -= elementsAtTheBackToDelete;
648 }
649
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 9 times.
 26 if (elementsToDelete)
650 {
651 // 5, 6, // 5, 6, X, X,
652
1/2
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
 16 _data.erase(std::next(_data.begin(), static_cast<int64_t>(_dataStart)),
653 16 std::next(_data.begin(), static_cast<int64_t>(std::min(_dataStart + elementsToDelete, _maxSize - _Padding))));
654 // 6, // 6, X, X
655 8 _maxSize -= elementsToDelete;
656
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 8 if (_dataEnd >= elementsToDelete)
657 {
658 4 _dataEnd -= elementsToDelete;
659 }
660 }
661 }
662 }
663
2/2
✓ Branch 0 taken 2435 times.
✓ Branch 1 taken 146 times.
 2744 else if (_maxSize - _Padding < targetSize) // We make the buffer bigger
664 {
665 // 1, 2, 3, _, _, // X, X, 0, 1, 2, 3, _, _
666 // 1, 2, 3, _, _, _, _, // X, X, 0, 1, 2, 3, _, _, _, _
667
2/2
✓ Branch 1 taken 2428 times.
✓ Branch 2 taken 7 times.
 2452 if (!isScrolled()) // Buffer not scrolled, so we can simply reserve more space
668 {
669 2438 _maxSize = targetSize + _Padding;
670 2438 _data.reserve(_maxSize);
671 }
672 // se e s s e
673 // 6, 7, 3, 4, 5, // 5, 6, X, X, 2, 3, 4 // X, 6, 7, 8, 9, 10, X
674 // 6, 7, _, 3, 4, 5, // 5, 6, _, X, X, 2, 3, 4 // X, 6, 7, 8, 9, 10, _, _, X
675 else // (_dataStart != 0) // Buffer scrolled, so we need to copy the values to the correct positions
676 {
677
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 14 _data.resize(targetSize + _Padding);
678
679 14 auto copy_backward = [](auto first, auto last, auto d_last) { // Needed, as MacOS with C++23 does not support std::copy_backward
680
4/10
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✓ Branch 5 taken 4 times.
✓ Branch 7 taken 9 times.
✓ Branch 8 taken 3 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
 32 while (first != last)
681 {
682 25 *(--d_last) = *(--last);
683 }
684 };
685
686
0/2
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 34 copy_backward(std::next(_data.begin(), static_cast<int64_t>(_dataEnd)),
687 14 std::next(_data.begin(), static_cast<int64_t>(_maxSize)),
688 8 std::next(_data.begin(), static_cast<int64_t>(targetSize + _Padding)));
689
690 14 auto diff = targetSize + _Padding - _maxSize;
691
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1 times.
 14 if (_dataStart >= _dataEnd)
692 {
693 12 _dataStart += diff;
694 }
695
696 14 _maxSize = targetSize + _Padding;
697 }
698 }
699 }
700 2938 }
701
702 // ###########################################################################################################
703 // Other
704 // ###########################################################################################################
705
706 /// @brief Returns the largest value in the buffer
707 [[nodiscard]] T max() const
708 {
709 T currentMax = front();
710 for (size_t i = 0; i < _data.size(); i++)
711 {
712 if (i >= _dataStart || i < _dataEnd)
713 {
714 currentMax = std::max(currentMax, _data.at(i));
715 }
716 }
717 return currentMax;
718 }
719
720 /// @brief Returns the smallest value in the buffer
721 [[nodiscard]] T min() const
722 {
723 T currentMin = front();
724 for (size_t i = 0; i < _data.size(); i++)
725 {
726 if (i >= _dataStart || i < _dataEnd)
727 {
728 currentMin = std::min(currentMin, _data.at(i));
729 }
730 }
731 return currentMin;
732 }
733
734 /// @brief Returns the data index of the first element in the buffer
735 146 [[nodiscard]] int offset() const
736 {
737 146 return static_cast<int>(_dataStart);
738 }
739
740 /// @brief Returns a pointer to the raw data array (not in scrolled order)
741 ✗ [[nodiscard]] const T* data() const
742 {
743 ✗ return _data.data();
744 }
745
746 /// @brief Returns a pointer to the raw data array (not in scrolled order)
747 14 [[nodiscard]] T* data()
748 {
749 14 return _data.data();
750 }
751
752 /// @brief Returns whether the buffer is infinite and growing
753 ✗ [[nodiscard]] bool isInfiniteBuffer() const
754 {
755 ✗ return _infiniteBuffer;
756 }
757
758 /// @brief Converts the raw buffer to a string
759 436 [[nodiscard]] std::string getRawString() const
760 {
761 // Scrolled
762 // e s
763 // 5, 6, _, _, X, 2, 3, 4
764
765 // se
766 // 5, 6, 2, 3, 4
767
768 // s e
769 // _, 6, _, _, _
770
771 // Not scrolled
772 // s e
773 // X, X, 0, 1, 2, 3, _, _
774
775 // s e
776 // X, 6, 7, 8, 9, 10, _, _, X
777
778 // s e
779 // 6, X, X,
780
781 // s e
782 // 6, _, X, X,
783
784 // se
785 // X, X, _, _, _,
786
787 436 std::string out;
788
789
2/2
✓ Branch 0 taken 1268 times.
✓ Branch 1 taken 218 times.
 2972 for (int i = 0; static_cast<size_t>(i) < _maxSize; i++) // X, 6, 7, 8, 9, 10, _, _, X
790 {
791
4/4
✓ Branch 0 taken 1048 times.
✓ Branch 1 taken 220 times.
✓ Branch 2 taken 860 times.
✓ Branch 3 taken 188 times.
 2536 if ((i >= static_cast<int>(_dataStart - _Padding) && static_cast<size_t>(i) < _dataStart)
792
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 1040 times.
 2160 || (static_cast<size_t>(i) >= _dataStart + _maxSize - _Padding))
793 {
794
1/2
✓ Branch 1 taken 228 times.
✗ Branch 2 not taken.
 456 out += "X"; // padding
795 }
796
3/4
✓ Branch 1 taken 1040 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 808 times.
✓ Branch 4 taken 232 times.
 2080 else if (bool scrolled = isScrolled();
797
6/6
✓ Branch 0 taken 556 times.
✓ Branch 1 taken 252 times.
✓ Branch 2 taken 552 times.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 504 times.
✓ Branch 5 taken 48 times.
 1616 (scrolled && static_cast<size_t>(i) >= _dataEnd && (static_cast<int>(_dataStart - _Padding) < 0 || i < static_cast<int>(_dataStart - _Padding)))
798
8/8
✓ Branch 0 taken 756 times.
✓ Branch 1 taken 232 times.
✓ Branch 2 taken 92 times.
✓ Branch 3 taken 664 times.
✓ Branch 4 taken 88 times.
✓ Branch 5 taken 4 times.
✓ Branch 6 taken 80 times.
✓ Branch 7 taken 8 times.
 1976 || (scrolled && _dataStart < _dataEnd && (static_cast<size_t>(i) < _dataStart || static_cast<size_t>(i) >= _dataEnd))
799
4/4
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 744 times.
✓ Branch 2 taken 132 times.
✓ Branch 3 taken 100 times.
 1952 || (!scrolled && static_cast<size_t>(i) >= _dataEnd))
800 {
801
1/2
✓ Branch 1 taken 196 times.
✗ Branch 2 not taken.
 392 out += "_"; // empty
802 }
803 else
804 {
805
4/7
✓ Branch 1 taken 844 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 52 times.
✓ Branch 5 taken 792 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 52 times.
✗ Branch 8 not taken.
 1688 out += std::to_string(_data.at(static_cast<size_t>(i)));
806 }
807
2/2
✓ Branch 0 taken 1052 times.
✓ Branch 1 taken 216 times.
 2536 if (static_cast<size_t>(i) != _maxSize - 1)
808 {
809
1/2
✓ Branch 1 taken 1052 times.
✗ Branch 2 not taken.
 2104 out += ", ";
810 }
811 }
812 436 return out;
813 ✗ }
814
815 /// @brief Prints the buffer to the output stream
816 /// @param[in, out] os The output stream to print to
817 /// @param[in] buffer The buffer to print
818 /// @return The output stream given as parameter
819 3 friend std::ostream& operator<<(std::ostream& os, const ScrollingBuffer<T, _Padding>& buffer)
820 {
821
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, ", "));
822 3 return os;
823 }
824
825 private:
826 /// 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
827 bool _infiniteBuffer{ false };
828 /// The maximum amount of objects to store in the buffer before overwriting itself when full
829 /// When _infiniteBuffer == true, then this corresponds to m_data.size()
830 size_t _maxSize;
831 /// The index of the first element in the scrolling buffer (0 if the buffer is empty)
832 size_t _dataStart{ 0 };
833 /// The index one after the last element (0 if the buffer is empty)
834 size_t _dataEnd{ 0 };
835 /// The data storage object
836 std::vector<T> _data;
837
838 /// @brief Checks if the buffer is scrolled
839 3572 [[nodiscard]] bool isScrolled() const
840 {
841 // e s
842 // 5, 6, _, _, X, 2, 3, 4
843
844 // se
845
3/6
✓ Branch 0 taken 2418 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 2418 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2418 times.
 3572 if (_dataEnd == 0 && !empty()) // 1, 2, 3, 4
846 {
847 291 return true;
848 }
849
850 3281 return _dataEnd < _dataStart
851
2/4
✓ Branch 0 taken 2418 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2418 times.
 3281 || (_dataStart != _Padding);
852
853 // se // se
854 // 5, 6, 2, 3, 4 // X, X, _, _, _
855
856 // s e
857 // X, 0, 1, 2, 3, _, _, X // Scrolled
858 // s e
859 // X, X, 0, 1, 2, 3, _, _ // Not scrolled
860 }
861 };
862
863 } // namespace NAV
864
865 #ifndef DOXYGEN_IGNORE
866
867 template<class T, size_t _Padding>
868 struct fmt::formatter<NAV::ScrollingBuffer<T, _Padding>> : ostream_formatter
869 {};
870
871 #endif
872