23 #ifndef GUL14_SLIDINGBUFFER_H_
24 #define GUL14_SLIDINGBUFFER_H_
169 template<
typename ElementT, std::size_t fixed_capacity = 0u,
170 typename Container =
typename std::conditional_t<(fixed_capacity >= 1u),
171 std::array<ElementT, fixed_capacity>,
172 std::vector<ElementT>>
250 Container storage_{ };
265 decrease_idx(idx_end_);
282 increase_idx(idx_begin_);
301 storage_[idx_end_] = in;
303 increase_idx(idx_end_);
305 increase_idx(idx_begin_);
306 else if (idx_end_ == idx_begin_)
315 storage_[idx_end_] = std::move(in);
317 increase_idx(idx_end_);
319 increase_idx(idx_begin_);
320 else if (idx_end_ == idx_begin_)
339 decrease_idx(idx_begin_);
342 decrease_idx(idx_end_);
343 else if (idx_end_ == idx_begin_)
346 storage_[idx_begin_] = in;
354 decrease_idx(idx_begin_);
357 decrease_idx(idx_end_);
358 else if (idx_end_ == idx_begin_)
361 storage_[idx_begin_] = std::move(in);
378 return (idx >= capacity()) ? storage_[idx - capacity()] : storage_[idx];
388 return (idx >= capacity()) ? storage_[idx - capacity()] : storage_[idx];
404 auto const s = size();
406 throw std::out_of_range(
gul14::cat(
"SlidingBuffer::", __func__,
407 ": idx (which is ", idx,
") >= this->size() (which is ", s,
")"));
409 return operator[](idx);
417 auto const s = size();
419 throw std::out_of_range(
gul14::cat(
"SlidingBuffer::", __func__,
420 ": idx (which is ", idx,
") >= this->size() (which is ", s,
")"));
422 return operator[](idx);
433 return storage_[idx_begin_];
441 return storage_[idx_begin_];
453 return storage_[capacity() - 1];
455 return storage_[idx_end_ - 1];
464 return storage_[capacity() - 1];
466 return storage_[idx_end_ - 1];
481 if (idx_end_ >= idx_begin_)
482 return idx_end_ - idx_begin_;
484 return idx_end_ + capacity() - idx_begin_;
496 return (fixed_capacity > 0) ? fixed_capacity : storage_.size();
526 std::fill(storage_.begin(), storage_.end(),
value_type{});
550 static_assert(fixed_capacity == 0u,
551 "resize() only possible if the underlying container is resizable");
552 change_capacity(new_capacity, shrink_behavior);
561 static_assert(fixed_capacity == 0u,
562 "reserve() only possible if the underlying container is resizable");
563 change_capacity(size, shrink_behavior);
573 return (not full_) and (idx_begin_ == idx_end_);
583 auto friend operator<< (std::ostream& s,
586 auto const size = buffer.size();
588 for (
auto i =
size_type{ 0 }; i < size; ++i)
589 s << buffer[i] <<
" ";
633 template <
typename BufferPo
inter>
641 BufferPointer buffer_;
679 auto previous = *
this;
717 auto previous = *
this;
742 return lhs.position_ - rhs.position_;
746 auto operator*() const noexcept -> typename std::conditional_t<
747 std::is_const<std::remove_pointer_t<BufferPointer>>::value,
750 return (*buffer_)[position_];
754 auto operator->() const noexcept -> typename std::conditional_t<
755 std::is_const<std::remove_pointer_t<BufferPointer>>::value,
758 return &(*buffer_)[position_];
763 std::is_const<std::remove_pointer_t<BufferPointer>>::value,
766 return *(*
this + offs);
778 return lhs.position_ == rhs.position_;
790 return not(lhs == rhs);
800 return lhs.position_ > rhs.position_;
808 return lhs.position_ < rhs.position_;
819 return lhs.position_ >= rhs.position_;
830 return lhs.position_ <= rhs.position_;
857 return std::make_reverse_iterator(end());
886 return std::make_reverse_iterator(begin());
906 return std::make_reverse_iterator(cend());
930 return std::make_reverse_iterator(cbegin());
934 void decrease_idx(
size_t &idx) noexcept
937 idx = capacity() - 1;
942 void increase_idx(
size_t &idx) noexcept
946 if (idx >= capacity())
967 auto const old_capacity = capacity();
968 auto const old_size = size();
972 if (new_capacity == old_capacity)
977 if (new_capacity == 0) {
988 if (new_capacity > old_capacity) {
990 std::rotate(storage_.begin(), storage_.begin() + idx_begin_, storage_.end());
991 storage_.resize(new_capacity);
1000 if (old_size < new_capacity) {
1002 std::rotate(storage_.begin(), storage_.begin() + idx_begin_, storage_.end());
1003 storage_.resize(new_capacity);
1005 idx_end_ = old_size;
1009 auto new_front = idx_begin_;
1010 if (shrink_behavior == ShrinkBehavior::keep_back_elements)
1011 new_front = (idx_end_ + old_capacity - new_capacity) % old_capacity;
1013 std::rotate(storage_.begin(), storage_.begin() + new_front, storage_.end());
1014 storage_.resize(new_capacity);
1065 template<
typename ElementT, std::size_t fixed_capacity = 0u,
1066 typename Container =
typename std::conditional_t<(fixed_capacity >= 1u),
1067 std::array<ElementT, fixed_capacity>,
1068 std::vector<ElementT>>
1116 if (not full_ and (idx_end_ == 0 or idx_end_ >= idx_begin_))
1117 return storage_.begin() + idx_begin_;
1119 return storage_.begin();
1136 if (not full_ and (idx_end_ == 0 or idx_end_ >= idx_begin_))
1137 return storage_.cbegin() + idx_begin_;
1139 return storage_.cbegin();
1161 if (full_ or idx_begin_ != 0)
1162 return storage_.end();
1164 return storage_.begin() + idx_end_;
1181 if (full_ or idx_begin_ != 0)
1182 return storage_.cend();
1184 return storage_.cbegin() + idx_end_;
1197 return std::make_reverse_iterator(end());
1210 return std::make_reverse_iterator(cend());
1220 return std::make_reverse_iterator(begin());
1231 return std::make_reverse_iterator(cbegin());
1255 static_assert(fixed_capacity == 0u,
1256 "resize() only possible if the underlying container is resizable");
1267 auto const old_capacity = capacity();
1269 auto const right_align =
1270 (shrink_behavior == ShrinkBehavior::keep_front_elements)
1271 and (new_capacity > 0)
1272 and (new_capacity != old_capacity)
1275 and (idx_begin_ != 0);
1277 if (not right_align)
1278 return this->change_capacity(new_capacity, shrink_behavior);
1282 if (new_capacity > old_capacity) {
1283 storage_.resize(new_capacity);
1284 std::move_backward(storage_.begin() + idx_begin_,
1285 storage_.begin() + old_capacity, storage_.end());
1286 idx_begin_ += new_capacity - old_capacity;
1292 full_ = (this->size() >= new_capacity);
1293 auto const required_shift = std::min(old_capacity - new_capacity, idx_begin_);
1294 std::rotate(storage_.begin(), storage_.begin() + required_shift, storage_.end());
1295 idx_begin_ -= required_shift;
1296 storage_.resize(new_capacity);
1305 static_assert(fixed_capacity == 0u,
1306 "reserve() only possible if the underlying container is resizable");
1307 resize(size, shrink_behavior);
Declaration of the overload set for cat() and of the associated class ConvertingStringView.
A variant of SlidingBuffer that exposes the underlying container through its iterator interface.
Definition: SlidingBuffer.h:1070
typename Container::reverse_iterator reverse_iterator
Iterator to an element in reversed container.
Definition: SlidingBuffer.h:1077
auto end() const noexcept -> const_iterator
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:1168
auto begin() noexcept -> iterator
Return an iterator to the first occupied element of the underlying container.
Definition: SlidingBuffer.h:1114
auto resize(size_type new_capacity, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container.
Definition: SlidingBuffer.h:1253
auto cend() const noexcept -> const_iterator
Return a constant iterator to the element following the last element in the used space of the underly...
Definition: SlidingBuffer.h:1179
auto reserve(size_type size, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container (identical to resize()).
Definition: SlidingBuffer.h:1303
typename Container::const_iterator const_iterator
Iterator to a const element.
Definition: SlidingBuffer.h:1075
auto begin() const noexcept -> const_iterator
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:1123
auto cbegin() const noexcept -> const_iterator
Return a constant iterator to the first occupied element of the underlying container.
Definition: SlidingBuffer.h:1134
auto rbegin() noexcept -> reverse_iterator
Return a reverse iterator to the first used element of the reversed underlying container.
Definition: SlidingBuffer.h:1195
auto end() noexcept -> iterator
Return an iterator to the element following the last element in the used space of the underlying cont...
Definition: SlidingBuffer.h:1159
auto crend() const noexcept -> const_reverse_iterator
Return a constant iterator to the last element of the reversed underlying container.
Definition: SlidingBuffer.h:1229
auto rend() noexcept -> reverse_iterator
Return an iterator to the last element of the reversed underlying container.
Definition: SlidingBuffer.h:1218
typename Container::iterator iterator
Iterator to an element.
Definition: SlidingBuffer.h:1073
auto crbegin() const noexcept -> const_reverse_iterator
Return a constant reverse iterator to the first used element of the reversed underlying container.
Definition: SlidingBuffer.h:1208
typename Container::const_reverse_iterator const_reverse_iterator
Iterator to a const element in reversed container.
Definition: SlidingBuffer.h:1079
Iterator of the SlidingBuffer container.
Definition: SlidingBuffer.h:635
ElementT value_type
The type "pointed to" by the iterator.
Definition: SlidingBuffer.h:649
friend auto operator+(difference_type d, const SlidingBufferIterator &it) noexcept -> SlidingBufferIterator
Add an integer and an iterator.
Definition: SlidingBuffer.h:701
friend auto operator+(const SlidingBufferIterator &it, difference_type d) noexcept -> SlidingBufferIterator
Add an integer to an iterator.
Definition: SlidingBuffer.h:693
auto operator->() const noexcept -> typename std::conditional_t< std::is_const< std::remove_pointer_t< BufferPointer >>::value, const_pointer, pointer >
Access member of element pointed to by the iterator.
Definition: SlidingBuffer.h:754
auto operator++(int) noexcept -> SlidingBufferIterator
Post-increment iterator by one position.
Definition: SlidingBuffer.h:677
friend auto operator>=(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> bool
Determine if the left iterator refers to position that is greater than or equal to than the right one...
Definition: SlidingBuffer.h:816
auto operator++() noexcept -> SlidingBufferIterator &
Pre-increment iterator by one position.
Definition: SlidingBuffer.h:670
auto operator--(int) noexcept -> SlidingBufferIterator
Post-decrement iterator by one position.
Definition: SlidingBuffer.h:715
std::ptrdiff_t difference_type
Distance between iterators is represented as this type.
Definition: SlidingBuffer.h:651
value_type & reference
This type represents a reference-to-value_type.
Definition: SlidingBuffer.h:655
friend auto operator>(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> bool
Determine if the left iterator refers to a greater position than the right one.
Definition: SlidingBuffer.h:797
auto operator+=(difference_type d) noexcept -> SlidingBufferIterator &
Increase iterator by a given number of positions.
Definition: SlidingBuffer.h:685
std::random_access_iterator_tag iterator_category
Defines the category of the iterator.
Definition: SlidingBuffer.h:647
auto operator[](difference_type offs) noexcept -> typename std::conditional_t< std::is_const< std::remove_pointer_t< BufferPointer >>::value, const_reference, reference >
Dereference the iterator at a certain index offset.
Definition: SlidingBuffer.h:762
auto operator--() noexcept -> SlidingBufferIterator &
Pre-decrement iterator by one position.
Definition: SlidingBuffer.h:708
friend auto operator-(const SlidingBufferIterator &it, difference_type d) noexcept -> SlidingBufferIterator
Subtract an integer from an iterator.
Definition: SlidingBuffer.h:731
SlidingBufferIterator(BufferPointer buff, size_type num=0) noexcept
Create an iterator pointing into a SlidingBuffer.
Definition: SlidingBuffer.h:663
value_type * pointer
This type represents a pointer-to-value_type.
Definition: SlidingBuffer.h:653
friend auto operator-(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> difference_type
Subtract two iterators.
Definition: SlidingBuffer.h:739
friend auto operator==(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> bool
Compare two iterators for equality.
Definition: SlidingBuffer.h:775
auto operator*() const noexcept -> typename std::conditional_t< std::is_const< std::remove_pointer_t< BufferPointer >>::value, const_reference, reference >
Access element pointed to by the iterator.
Definition: SlidingBuffer.h:746
auto operator-=(difference_type d) noexcept -> SlidingBufferIterator &
Decrease iterator by a given number of positions.
Definition: SlidingBuffer.h:723
friend auto operator!=(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> bool
Compare two iterators for inequality.
Definition: SlidingBuffer.h:787
A circular data buffer of (semi-)fixed capacity to which elements can be added at the front or at the...
Definition: SlidingBuffer.h:174
auto push_front(const value_type &in) -> void
Insert one element at the front of the buffer; if it is full, an element at the back is dropped to ma...
Definition: SlidingBuffer.h:337
typename Container::size_type size_type
Unsigned integer type (usually std::size_t)
Definition: SlidingBuffer.h:183
auto filled() const noexcept -> bool
Return true if the buffer is completely filled with elements.
Definition: SlidingBuffer.h:507
auto cbegin() const noexcept -> const_iterator
Return a read-only iterator to the first element of the container.
Definition: SlidingBuffer.h:894
auto size() const noexcept -> size_type
Return the number of elements in the container, i.e.
Definition: SlidingBuffer.h:476
auto operator[](size_type idx) const noexcept -> const_reference
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:384
std::reverse_iterator< const_iterator > const_reverse_iterator
Iterator to a const element in reversed container.
Definition: SlidingBuffer.h:201
auto change_capacity(size_type new_capacity, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Change the underlying container's capacity.
Definition: SlidingBuffer.h:965
auto cend() const noexcept -> const_iterator
Return a read-only iterator to the element following the last element of the container.
Definition: SlidingBuffer.h:916
SlidingBuffer(SlidingBuffer &&) noexcept(std::is_nothrow_move_constructible< container_type >::value)=default
Default move constructor.
SlidingBuffer(SlidingBuffer const &)=default
Default copy constructor.
auto at(const size_type idx) noexcept(false) -> reference
Access an element in the buffer by index with bounds checking.
Definition: SlidingBuffer.h:402
auto pop_front() -> void
Remove the first element from the buffer.
Definition: SlidingBuffer.h:280
auto reserve(size_type size, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container (identical to resize()).
Definition: SlidingBuffer.h:559
auto crend() const noexcept -> const_reverse_iterator
Return a read-only iterator to the element following the last element of the reversed container.
Definition: SlidingBuffer.h:928
Container container_type
Type of the underlying container (e.g. std::array<value_type, ..>)
Definition: SlidingBuffer.h:179
auto push_back(value_type &&in) -> void
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:313
typename Container::const_reference const_reference
Reference to a constant element.
Definition: SlidingBuffer.h:189
auto end() noexcept -> iterator
Return an iterator to the element following the last element of the container.
Definition: SlidingBuffer.h:866
auto rbegin() noexcept -> reverse_iterator
Return an iterator to the first element of the reversed container.
Definition: SlidingBuffer.h:855
typename Container::const_pointer const_pointer
Pointer to a constant element.
Definition: SlidingBuffer.h:193
SlidingBuffer()=default
Construct an empty sliding buffer.
typename Container::difference_type difference_type
Signed integer type (usually std::ptrdiff_t)
Definition: SlidingBuffer.h:185
auto operator[](size_type idx) noexcept -> reference
Access an element in the buffer by index without bounds checking.
Definition: SlidingBuffer.h:374
std::reverse_iterator< iterator > reverse_iterator
Iterator to an element in reversed container.
Definition: SlidingBuffer.h:199
auto front() noexcept -> reference
Return the foremost element (the one with index 0).
Definition: SlidingBuffer.h:431
auto empty() const noexcept -> bool
Check if the buffer contains no elements, i.e.
Definition: SlidingBuffer.h:571
auto front() const noexcept -> const_reference
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:439
ElementT value_type
Type of the elements in the underlying container.
Definition: SlidingBuffer.h:181
auto clear() -> void
Empty the buffer.
Definition: SlidingBuffer.h:519
auto resize(size_type new_capacity, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container.
Definition: SlidingBuffer.h:548
auto begin() const noexcept -> const_iterator
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:845
auto rend() noexcept -> reverse_iterator
Return an iterator to the element following the last element of the reversed container.
Definition: SlidingBuffer.h:884
constexpr auto capacity() const noexcept -> size_type
Return the maximum possible number of elements in the container.
Definition: SlidingBuffer.h:494
auto push_front(value_type &&in) -> void
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:352
typename Container::reference reference
Reference to an element.
Definition: SlidingBuffer.h:187
auto at(const size_type idx) const noexcept(false) -> const_reference
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:415
auto pop_back() -> void
Remove the last element from the buffer.
Definition: SlidingBuffer.h:263
auto crbegin() const noexcept -> const_reverse_iterator
Return a read-only iterator to the first element of the reversed container.
Definition: SlidingBuffer.h:904
auto back() const noexcept -> const_reference
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:461
auto begin() noexcept -> iterator
Return an iterator to the first element of the container.
Definition: SlidingBuffer.h:839
typename Container::pointer pointer
Pointer to an element.
Definition: SlidingBuffer.h:191
auto back() noexcept -> reference
Return the backmost element (the one with the highest valid index).
Definition: SlidingBuffer.h:450
auto end() const noexcept -> const_iterator
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: SlidingBuffer.h:872
auto push_back(const value_type &in) -> void
Insert one element at the end of the buffer; if it is full, an element at the front is dropped to mak...
Definition: SlidingBuffer.h:299
Definition of macros used internally by GUL.
Namespace gul14 contains all functions and classes of the General Utility Library.
Definition: doxygen.h:26
ShrinkBehavior
Determine how a SlidingBuffer handles decreases of its size.
Definition: SlidingBuffer.h:59
std::string cat()
Efficiently concatenate an arbitrary number of strings and numbers.
Definition: cat.h:90