23 #ifndef GUL14_SLIDINGBUFFER_H_
24 #define GUL14_SLIDINGBUFFER_H_
176 template<
typename ElementT, std::size_t fixed_capacity = 0u,
177 typename Container =
typename std::conditional_t<(fixed_capacity >= 1u),
178 std::array<ElementT, fixed_capacity>,
179 std::vector<ElementT>>
257 Container storage_{ };
272 decrease_idx(idx_end_);
289 increase_idx(idx_begin_);
308 storage_[idx_end_] = in;
310 increase_idx(idx_end_);
312 increase_idx(idx_begin_);
313 else if (idx_end_ == idx_begin_)
322 storage_[idx_end_] = std::move(in);
324 increase_idx(idx_end_);
326 increase_idx(idx_begin_);
327 else if (idx_end_ == idx_begin_)
346 decrease_idx(idx_begin_);
349 decrease_idx(idx_end_);
350 else if (idx_end_ == idx_begin_)
353 storage_[idx_begin_] = in;
361 decrease_idx(idx_begin_);
364 decrease_idx(idx_end_);
365 else if (idx_end_ == idx_begin_)
368 storage_[idx_begin_] = std::move(in);
385 return (idx >= capacity()) ? storage_[idx - capacity()] : storage_[idx];
395 return (idx >= capacity()) ? storage_[idx - capacity()] : storage_[idx];
411 auto const s = size();
413 throw std::out_of_range(
gul14::cat(
"SlidingBuffer::", __func__,
414 ": idx (which is ", idx,
") >= this->size() (which is ", s,
")"));
416 return operator[](idx);
424 auto const s = size();
426 throw std::out_of_range(
gul14::cat(
"SlidingBuffer::", __func__,
427 ": idx (which is ", idx,
") >= this->size() (which is ", s,
")"));
429 return operator[](idx);
440 return storage_[idx_begin_];
448 return storage_[idx_begin_];
460 return storage_[capacity() - 1];
462 return storage_[idx_end_ - 1];
471 return storage_[capacity() - 1];
473 return storage_[idx_end_ - 1];
488 if (idx_end_ >= idx_begin_)
489 return idx_end_ - idx_begin_;
491 return idx_end_ + capacity() - idx_begin_;
503 return (fixed_capacity > 0) ? fixed_capacity : storage_.size();
533 std::fill(storage_.begin(), storage_.end(),
value_type{});
557 static_assert(fixed_capacity == 0u,
558 "resize() only possible if the underlying container is resizable");
559 change_capacity(new_capacity, shrink_behavior);
568 static_assert(fixed_capacity == 0u,
569 "reserve() only possible if the underlying container is resizable");
570 change_capacity(size, shrink_behavior);
580 return (not full_) and (idx_begin_ == idx_end_);
590 auto friend operator<< (std::ostream& s,
593 auto const size = buffer.size();
595 for (
auto i =
size_type{ 0 }; i < size; ++i)
596 s << buffer[i] <<
" ";
640 template <
typename BufferPo
inter>
648 BufferPointer buffer_;
686 auto previous = *
this;
724 auto previous = *
this;
749 return lhs.position_ - rhs.position_;
753 auto operator*() const noexcept -> typename std::conditional_t<
754 std::is_const<std::remove_pointer_t<BufferPointer>>::value,
757 return (*buffer_)[position_];
761 auto operator->() const noexcept -> typename std::conditional_t<
762 std::is_const<std::remove_pointer_t<BufferPointer>>::value,
765 return &(*buffer_)[position_];
770 std::is_const<std::remove_pointer_t<BufferPointer>>::value,
773 return *(*
this + offs);
785 return lhs.position_ == rhs.position_;
797 return not(lhs == rhs);
807 return lhs.position_ > rhs.position_;
815 return lhs.position_ < rhs.position_;
826 return lhs.position_ >= rhs.position_;
837 return lhs.position_ <= rhs.position_;
864 return std::make_reverse_iterator(end());
893 return std::make_reverse_iterator(begin());
913 return std::make_reverse_iterator(cend());
937 return std::make_reverse_iterator(cbegin());
941 void decrease_idx(
size_t &idx) noexcept
944 idx = capacity() - 1;
949 void increase_idx(
size_t &idx) noexcept
953 if (idx >= capacity())
974 auto const old_capacity = capacity();
975 auto const old_size = size();
979 if (new_capacity == old_capacity)
984 if (new_capacity == 0) {
995 if (new_capacity > old_capacity) {
997 std::rotate(storage_.begin(), storage_.begin() + idx_begin_, storage_.end());
998 storage_.resize(new_capacity);
1000 idx_end_ = old_size;
1007 if (old_size < new_capacity) {
1009 std::rotate(storage_.begin(), storage_.begin() + idx_begin_, storage_.end());
1010 storage_.resize(new_capacity);
1012 idx_end_ = old_size;
1016 auto new_front = idx_begin_;
1017 if (shrink_behavior == ShrinkBehavior::keep_back_elements)
1018 new_front = (idx_end_ + old_capacity - new_capacity) % old_capacity;
1020 std::rotate(storage_.begin(), storage_.begin() + new_front, storage_.end());
1021 storage_.resize(new_capacity);
1072 template<
typename ElementT, std::size_t fixed_capacity = 0u,
1073 typename Container =
typename std::conditional_t<(fixed_capacity >= 1u),
1074 std::array<ElementT, fixed_capacity>,
1075 std::vector<ElementT>>
1123 if (not full_ and (idx_end_ == 0 or idx_end_ >= idx_begin_))
1124 return storage_.begin() + idx_begin_;
1126 return storage_.begin();
1143 if (not full_ and (idx_end_ == 0 or idx_end_ >= idx_begin_))
1144 return storage_.cbegin() + idx_begin_;
1146 return storage_.cbegin();
1168 if (full_ or idx_begin_ != 0)
1169 return storage_.end();
1171 return storage_.begin() + idx_end_;
1188 if (full_ or idx_begin_ != 0)
1189 return storage_.cend();
1191 return storage_.cbegin() + idx_end_;
1204 return std::make_reverse_iterator(end());
1217 return std::make_reverse_iterator(cend());
1227 return std::make_reverse_iterator(begin());
1238 return std::make_reverse_iterator(cbegin());
1262 static_assert(fixed_capacity == 0u,
1263 "resize() only possible if the underlying container is resizable");
1274 auto const old_capacity = capacity();
1276 auto const right_align =
1277 (shrink_behavior == ShrinkBehavior::keep_front_elements)
1278 and (new_capacity > 0)
1279 and (new_capacity != old_capacity)
1282 and (idx_begin_ != 0);
1284 if (not right_align)
1285 return this->change_capacity(new_capacity, shrink_behavior);
1289 if (new_capacity > old_capacity) {
1290 storage_.resize(new_capacity);
1291 std::move_backward(storage_.begin() + idx_begin_,
1292 storage_.begin() + old_capacity, storage_.end());
1293 idx_begin_ += new_capacity - old_capacity;
1299 full_ = (this->size() >= new_capacity);
1300 auto const required_shift = std::min(old_capacity - new_capacity, idx_begin_);
1301 std::rotate(storage_.begin(), storage_.begin() + required_shift, storage_.end());
1302 idx_begin_ -= required_shift;
1303 storage_.resize(new_capacity);
1312 static_assert(fixed_capacity == 0u,
1313 "reserve() only possible if the underlying container is resizable");
1314 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:1077
typename Container::reverse_iterator reverse_iterator
Iterator to an element in reversed container.
Definition: SlidingBuffer.h:1084
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:1175
auto begin() noexcept -> iterator
Return an iterator to the first occupied element of the underlying container.
Definition: SlidingBuffer.h:1121
auto resize(size_type new_capacity, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container.
Definition: SlidingBuffer.h:1260
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:1186
auto reserve(size_type size, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container (identical to resize()).
Definition: SlidingBuffer.h:1310
typename Container::const_iterator const_iterator
Iterator to a const element.
Definition: SlidingBuffer.h:1082
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:1130
auto cbegin() const noexcept -> const_iterator
Return a constant iterator to the first occupied element of the underlying container.
Definition: SlidingBuffer.h:1141
auto rbegin() noexcept -> reverse_iterator
Return a reverse iterator to the first used element of the reversed underlying container.
Definition: SlidingBuffer.h:1202
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:1166
auto crend() const noexcept -> const_reverse_iterator
Return a constant iterator to the last element of the reversed underlying container.
Definition: SlidingBuffer.h:1236
auto rend() noexcept -> reverse_iterator
Return an iterator to the last element of the reversed underlying container.
Definition: SlidingBuffer.h:1225
typename Container::iterator iterator
Iterator to an element.
Definition: SlidingBuffer.h:1080
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:1215
typename Container::const_reverse_iterator const_reverse_iterator
Iterator to a const element in reversed container.
Definition: SlidingBuffer.h:1086
Iterator of the SlidingBuffer container.
Definition: SlidingBuffer.h:642
ElementT value_type
The type "pointed to" by the iterator.
Definition: SlidingBuffer.h:656
friend auto operator+(difference_type d, const SlidingBufferIterator &it) noexcept -> SlidingBufferIterator
Add an integer and an iterator.
Definition: SlidingBuffer.h:708
friend auto operator+(const SlidingBufferIterator &it, difference_type d) noexcept -> SlidingBufferIterator
Add an integer to an iterator.
Definition: SlidingBuffer.h:700
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:761
auto operator++(int) noexcept -> SlidingBufferIterator
Post-increment iterator by one position.
Definition: SlidingBuffer.h:684
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:823
auto operator++() noexcept -> SlidingBufferIterator &
Pre-increment iterator by one position.
Definition: SlidingBuffer.h:677
auto operator--(int) noexcept -> SlidingBufferIterator
Post-decrement iterator by one position.
Definition: SlidingBuffer.h:722
std::ptrdiff_t difference_type
Distance between iterators is represented as this type.
Definition: SlidingBuffer.h:658
value_type & reference
This type represents a reference-to-value_type.
Definition: SlidingBuffer.h:662
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:804
auto operator+=(difference_type d) noexcept -> SlidingBufferIterator &
Increase iterator by a given number of positions.
Definition: SlidingBuffer.h:692
std::random_access_iterator_tag iterator_category
Defines the category of the iterator.
Definition: SlidingBuffer.h:654
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:769
auto operator--() noexcept -> SlidingBufferIterator &
Pre-decrement iterator by one position.
Definition: SlidingBuffer.h:715
friend auto operator-(const SlidingBufferIterator &it, difference_type d) noexcept -> SlidingBufferIterator
Subtract an integer from an iterator.
Definition: SlidingBuffer.h:738
SlidingBufferIterator(BufferPointer buff, size_type num=0) noexcept
Create an iterator pointing into a SlidingBuffer.
Definition: SlidingBuffer.h:670
value_type * pointer
This type represents a pointer-to-value_type.
Definition: SlidingBuffer.h:660
friend auto operator-(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> difference_type
Subtract two iterators.
Definition: SlidingBuffer.h:746
friend auto operator==(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> bool
Compare two iterators for equality.
Definition: SlidingBuffer.h:782
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:753
auto operator-=(difference_type d) noexcept -> SlidingBufferIterator &
Decrease iterator by a given number of positions.
Definition: SlidingBuffer.h:730
friend auto operator!=(const SlidingBufferIterator &lhs, const SlidingBufferIterator &rhs) noexcept -> bool
Compare two iterators for inequality.
Definition: SlidingBuffer.h:794
A circular data buffer of (semi-)fixed capacity to which elements can be added at the front or at the...
Definition: SlidingBuffer.h:181
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:344
typename Container::size_type size_type
Unsigned integer type (usually std::size_t)
Definition: SlidingBuffer.h:190
auto filled() const noexcept -> bool
Return true if the buffer is completely filled with elements.
Definition: SlidingBuffer.h:514
auto cbegin() const noexcept -> const_iterator
Return a read-only iterator to the first element of the container.
Definition: SlidingBuffer.h:901
auto size() const noexcept -> size_type
Return the number of elements in the container, i.e.
Definition: SlidingBuffer.h:483
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:391
std::reverse_iterator< const_iterator > const_reverse_iterator
Iterator to a const element in reversed container.
Definition: SlidingBuffer.h:208
auto change_capacity(size_type new_capacity, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Change the underlying container's capacity.
Definition: SlidingBuffer.h:972
auto cend() const noexcept -> const_iterator
Return a read-only iterator to the element following the last element of the container.
Definition: SlidingBuffer.h:923
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:409
auto pop_front() -> void
Remove the first element from the buffer.
Definition: SlidingBuffer.h:287
auto reserve(size_type size, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container (identical to resize()).
Definition: SlidingBuffer.h:566
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:935
Container container_type
Type of the underlying container (e.g. std::array<value_type, ..>)
Definition: SlidingBuffer.h:186
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:320
typename Container::const_reference const_reference
Reference to a constant element.
Definition: SlidingBuffer.h:196
auto end() noexcept -> iterator
Return an iterator to the element following the last element of the container.
Definition: SlidingBuffer.h:873
auto rbegin() noexcept -> reverse_iterator
Return an iterator to the first element of the reversed container.
Definition: SlidingBuffer.h:862
typename Container::const_pointer const_pointer
Pointer to a constant element.
Definition: SlidingBuffer.h:200
SlidingBuffer()=default
Construct an empty sliding buffer.
typename Container::difference_type difference_type
Signed integer type (usually std::ptrdiff_t)
Definition: SlidingBuffer.h:192
auto operator[](size_type idx) noexcept -> reference
Access an element in the buffer by index without bounds checking.
Definition: SlidingBuffer.h:381
std::reverse_iterator< iterator > reverse_iterator
Iterator to an element in reversed container.
Definition: SlidingBuffer.h:206
auto front() noexcept -> reference
Return the foremost element (the one with index 0).
Definition: SlidingBuffer.h:438
auto empty() const noexcept -> bool
Check if the buffer contains no elements, i.e.
Definition: SlidingBuffer.h:578
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:446
ElementT value_type
Type of the elements in the underlying container.
Definition: SlidingBuffer.h:188
auto clear() -> void
Empty the buffer.
Definition: SlidingBuffer.h:526
auto resize(size_type new_capacity, ShrinkBehavior shrink_behavior=ShrinkBehavior::keep_front_elements) -> void
Resize the container.
Definition: SlidingBuffer.h:555
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:852
auto rend() noexcept -> reverse_iterator
Return an iterator to the element following the last element of the reversed container.
Definition: SlidingBuffer.h:891
constexpr auto capacity() const noexcept -> size_type
Return the maximum possible number of elements in the container.
Definition: SlidingBuffer.h:501
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:359
typename Container::reference reference
Reference to an element.
Definition: SlidingBuffer.h:194
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:422
auto pop_back() -> void
Remove the last element from the buffer.
Definition: SlidingBuffer.h:270
auto crbegin() const noexcept -> const_reverse_iterator
Return a read-only iterator to the first element of the reversed container.
Definition: SlidingBuffer.h:911
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:468
auto begin() noexcept -> iterator
Return an iterator to the first element of the container.
Definition: SlidingBuffer.h:846
typename Container::pointer pointer
Pointer to an element.
Definition: SlidingBuffer.h:198
auto back() noexcept -> reference
Return the backmost element (the one with the highest valid index).
Definition: SlidingBuffer.h:457
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:879
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:306
ShrinkBehavior
Determine how a SlidingBuffer handles decreases of its size.
Definition: SlidingBuffer.h:66
std::string cat()
Efficiently concatenate an arbitrary number of strings and numbers.
Definition: cat.h:97
Definition of macros used internally by GUL.
Namespace gul14 contains all functions and classes of the General Utility Library.
Definition: doxygen.h:26