diff options
| -rw-r--r-- | src/openvic-simulation/types/GapDeque.hpp | 936 | ||||
| -rw-r--r-- | src/openvic-simulation/utility/Utility.hpp | 3 |
2 files changed, 939 insertions, 0 deletions
diff --git a/src/openvic-simulation/types/GapDeque.hpp b/src/openvic-simulation/types/GapDeque.hpp new file mode 100644 index 0000000..7bf51af --- /dev/null +++ b/src/openvic-simulation/types/GapDeque.hpp @@ -0,0 +1,936 @@ +#pragma once + +// Based heavily on +// https://github.com/slavenf/sfl-library/blob/2c6f464f5101caa39640d765002907e29b5b3acd/include/sfl/segmented_vector.hpp +// modified to suit OpenVic's purposes +// +// Copyright (c) 2022 Slaven Falandys +// +// This software is provided 'as-is', without any express or implied +// warranty. In no event will the authors be held liable for any damages +// arising from the use of this software. +// +// Permission is granted to anyone to use this software for any purpose, +// including commercial applications, and to alter it and redistribute it +// freely, subject to the following restrictions: +// +// 1. The origin of this software must not be misrepresented; you must not +// claim that you wrote the original software. If you use this software +// in a product, an acknowledgment in the product documentation would be +// appreciated but is not required. +// 2. Altered source versions must be plainly marked as such, and must not be +// misrepresented as being the original software. +// 3. This notice may not be removed or altered from any source distribution. +// + +#include <algorithm> +#include <concepts> +#include <cstddef> +#include <cstdlib> +#include <iterator> +#include <memory> +#include <optional> +#include <type_traits> + +#include "openvic-simulation/utility/Utility.hpp" + +namespace OpenVic { + namespace detail { + template<typename T, typename Value> + concept GapDequeAddValue = utility::any_of<T, const Value&, Value&&>; + template<typename T, typename Iterator> + concept GapDequeEraseIt = utility::any_of<T, Iterator, const Iterator>; + } + + template<typename T, typename Value> + concept GapDequeStorage = requires(const T& ct, T& t, const Value& ref_val, Value&& rval) { + { ct.has_value() } -> std::same_as<bool>; + { t.value() } -> std::same_as<Value&>; + { ct.value() } -> std::same_as<const Value&>; + { t.emplace(ref_val) } -> std::same_as<Value&>; + { t.emplace(std::move(rval)) } -> std::same_as<Value&>; + { t.reset() } -> std::same_as<void>; + { T() } -> std::same_as<T>; + { T(std::move(rval)) } -> std::same_as<T>; + }; + + template< + typename ValueType, + GapDequeStorage<ValueType> StorageType, // std::iterator_traits<Iter>::value_type + typename Pointer, // std::iterator_traits<Iter>::pointer + typename Reference, // std::iterator_traits<Iter>::reference + typename DifferenceType, // std::iterator_traits<Iter>::difference_type + typename BlockPointer, // Non-const pointer to block. + typename ElementPointer, // Non-const pointer to element. + std::size_t BlockSize> + class GapDequeIterator { + template<typename, typename, typename, typename, typename, typename, typename, std::size_t> + friend class GapDequeIterator; + + template<typename, std::size_t, typename, typename> + friend class GapDeque; + + public: + using value_type = StorageType; + using pointer = Pointer; + using reference = Reference; + using difference_type = DifferenceType; + using iterator_category = std::bidirectional_iterator_tag; + + static constexpr std::integral_constant<std::size_t, BlockSize> block_size {}; + + private: + using block_pointer = BlockPointer; + using element_pointer = ElementPointer; + + block_pointer _block; + element_pointer _element; + + public: + GapDequeIterator() {} + GapDequeIterator(const GapDequeIterator& other) noexcept : _block(other._block), _element(other._element) {} + template<std::convertible_to<Pointer> OtherPointer, typename OtherReference> + GapDequeIterator(const GapDequeIterator< + ValueType, StorageType, OtherPointer, OtherReference, DifferenceType, BlockPointer, ElementPointer, + BlockSize>& other) noexcept + : _block(other._block), _element(other._element) {} + + GapDequeIterator& operator=(const GapDequeIterator& other) noexcept { + _block = other._block; + _element = other._element; + return *this; + } + + [[nodiscard]] reference operator*() { + return (*_element).value(); + } + + [[nodiscard]] pointer operator->() { + return &_element.value(); + } + + GapDequeIterator& operator++() { + increment_once(); + return *this; + } + + GapDequeIterator operator++(int) { + auto temp = *this; + increment_once(); + return temp; + } + + GapDequeIterator& operator--() { + decrement_once(); + return *this; + } + + GapDequeIterator operator--(int) { + auto temp = *this; + decrement_once(); + return temp; + } + + // GapDequeIterator& operator+=(difference_type n) { + // advance(n); + // return *this; + // } + + // GapDequeIterator& operator-=(difference_type n) { + // advance(-n); + // return *this; + // } + + // [[nodiscard]] GapDequeIterator operator+(difference_type n) const { + // auto temp = *this; + // temp.advance(n); + // return temp; + // } + + // [[nodiscard]] GapDequeIterator operator-(difference_type n) const { + // auto temp = *this; + // temp.advance(-n); + // return temp; + // } + + // [[nodiscard]] reference operator[](difference_type n) const { + // auto temp = *this; + // temp.advance(n); + // return *temp; + // } + + [[nodiscard]] friend GapDequeIterator operator+(difference_type n, const GapDequeIterator& it) { + return it + n; + } + + [[nodiscard]] friend difference_type operator-(const GapDequeIterator& x, const GapDequeIterator& y) { + return (x._block - y._block) * difference_type(block_size()) + (x._element - *x._block) - (y._element - *y._block); + } + + [[nodiscard]] friend bool operator==(const GapDequeIterator& x, const GapDequeIterator& y) { + return x._element == y._element; + } + + [[nodiscard]] friend bool operator!=(const GapDequeIterator& x, const GapDequeIterator& y) { + return !(x == y); + } + + [[nodiscard]] friend bool operator<(const GapDequeIterator& x, const GapDequeIterator& y) { + return (x._block == y._block) ? (x._element < y._element) : (x._block < y._block); + } + + [[nodiscard]] friend bool operator>(const GapDequeIterator& x, const GapDequeIterator& y) { + return y < x; + } + + [[nodiscard]] friend bool operator<=(const GapDequeIterator& x, const GapDequeIterator& y) { + return !(y < x); + } + + [[nodiscard]] friend bool operator>=(const GapDequeIterator& x, const GapDequeIterator& y) { + return !(x < y); + } + + private: + GapDequeIterator(block_pointer block, element_pointer elem) noexcept : _block(block), _element(elem) {} + + void increment_once() noexcept { + do { + ++_element; + if (_element == *_block + block_size()) { + ++_block; + _element = *_block; + } + } while (_element && !_element->has_value()); + } + + void decrement_once() noexcept { + do { + if (_element == *_block) { + --_block; + _element = *_block + block_size(); + } + --_element; + } while (_element && !_element->has_value()); + } + + // Ignores has_value check + void advance(difference_type n) noexcept { + const difference_type offset = n + (_element - *_block); + + if (offset >= 0 && offset < difference_type(block_size())) { + _element += n; + } else { + const difference_type _block_offset = + offset > 0 ? offset / difference_type(block_size()) : -difference_type((-offset - 1) / block_size()) - 1; + + _block += _block_offset; + + _element = *_block + (offset - _block_offset * difference_type(block_size())); + } + } + }; + + template< + typename T, std::size_t BlockSize, GapDequeStorage<T> Storage = std::optional<T>, + class Allocator = std::allocator<Storage>> + class GapDeque { + static_assert(BlockSize > 0, _OV_STR(BlockSize) " must be greater than zero."); + + public: + struct Iterator; + using value_type = T; + using storage_type = Storage; + using allocator_type = Allocator; + using allocator_traits = std::allocator_traits<allocator_type>; + using size_type = typename allocator_traits::size_type; + using difference_type = typename allocator_traits::difference_type; + using reference = value_type&; + using const_reference = const value_type&; + using pointer = value_type*; + using const_pointer = const value_type*; + using storage_pointer = typename allocator_traits::pointer; + using const_storage_pointer = typename allocator_traits::const_pointer; + + static constexpr std::integral_constant<std::size_t, BlockSize> block_size {}; + + private: + using block_allocator = typename allocator_traits::template rebind_alloc<pointer>; + using block_pointer = typename allocator_traits::pointer; + + public: + using iterator = GapDequeIterator< + value_type, storage_type, storage_pointer, reference, difference_type, block_pointer, pointer, block_size>; + using const_iterator = GapDequeIterator< + value_type, storage_type, const_storage_pointer, const_reference, difference_type, block_pointer, pointer, + block_size>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + + static_assert( + std::is_same<typename Allocator::value_type, storage_type>::value, + _OV_STR(Allocator::value_type) " must be same as " _OV_STR(OpenVic::GapDeque::storage_type) "." + ); + + GapDeque() {} + + [[nodiscard]] allocator_type get_allocator() const { + return _data.ref_to_alloc(); + } + + [[nodiscard]] reference front() { + return *_data._front; + } + [[nodiscard]] reference back() { + auto temp = _data._last; + --temp; + return *temp; + } + + [[nodiscard]] const_reference front() const { + return *_data._front; + } + [[nodiscard]] const_reference back() const { + auto temp = _data._last; + --temp; + return *temp; + } + + [[nodiscard]] iterator begin() { + return _data._first; + } + [[nodiscard]] iterator end() { + return _data._last; + } + + [[nodiscard]] const_iterator begin() const { + return _data._first; + } + [[nodiscard]] const_iterator end() const { + return _data._last; + } + + [[nodiscard]] const_iterator cbegin() const { + return _data._first; + } + [[nodiscard]] const_iterator cend() const { + return _data._last; + } + + [[nodiscard]] reverse_iterator rbegin() { + return reverse_iterator(end()); + } + [[nodiscard]] reverse_iterator rend() { + return reverse_iterator(begin()); + } + + [[nodiscard]] const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + [[nodiscard]] const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + + [[nodiscard]] const_reverse_iterator crbegin() const { + return const_reverse_iterator(end()); + } + [[nodiscard]] const_reverse_iterator crend() const { + return const_reverse_iterator(begin()); + } + + [[nodiscard]] bool empty() const { + return _data._last == _data._first; + } + [[nodiscard]] size_type size() const { + return _data._last - _data._first; + } + [[nodiscard]] size_type capacity() const { + return _data._end - _data._first; + } + [[nodiscard]] size_type max_size() const { + return std::min<size_type>( + allocator_traits::max_size(_data.ref_to_alloc()), + std::numeric_limits<difference_type>::max() / sizeof(value_type) + ); + } + + void clear() { + erase(begin(), end()); + } + + void clear_and_shrink() { + destroy(_data.ref_to_alloc(), _data._first, _data._last); + _data._last = _data._first; + _data._first_invalid = begin(); + } + + private: + iterator set(const_iterator pos, detail::GapDequeAddValue<value_type> auto value) { + iterator p(pos._block, pos._element); + if (_data._first_invalid > p) { + while (_data._first_invalid._element->has_value()) { + _data._first_invalid.advance(1); + } + } + if constexpr (std::is_rvalue_reference_v<decltype(value)>) { + return p._element->emplace(std::move(value)); + } else { + return p._element->emplace(value); + } + } + + /*iterator insert(const_iterator pos, detail::GapDequeAddValue<value_type> auto value) { + if constexpr (std::is_rvalue_reference_v<decltype(value)>) { + if (!pos._element->has_value()) { + return set(pos, std::move(value)); + } + return emplace(pos, std::move(value)); + } else { + if (!pos._element->has_value()) { + return set(pos, value); + } + return emplace(pos, value); + } + }*/ + + template<class... Args> + iterator emplace(const_iterator pos, Args&&... args) { + iterator p(pos._block, pos._element); + + if (_data._last == _data._end) { + const size_type offset = pos - cbegin(); + + grow_storage(1); + + p = nth(offset); + } + + if (p == _data._last) { + GapDeque::construct_at(_data.ref_to_alloc(), _data._last._element, std::forward<Args>(args)...); + + ++_data._last; + } else { + // The order of operations is critical. First we will construct + // temporary value because arguments `args...` can contain + // reference to element in this container and after that + // we will move elements and insert new element. + + temporary_value temp(_data.ref_to_alloc(), std::forward<Args>(args)...); + + GapDeque::construct_at(_data.ref_to_alloc(), _data._last._element, std::move(*(_data._last - 1))); + + ++_data._last; + + std::move_backward(p, _data._last - 2, _data._last - 1); + + *p = std::move(temp.value()); + } + + return p; + } + + public: + iterator erase(detail::GapDequeEraseIt<iterator> auto pos) { + assert(cbegin() <= pos && pos < cend()); + iterator p(pos._block, pos._element); + if (p < _data._first_invalid) { + _data._first_invalid = p; + } + p._element->reset(); + p--; + return p; + } + template<detail::GapDequeEraseIt<iterator> it> + iterator erase(it first, it last) { + assert(cbegin() <= first && first <= last && last <= cend()); + iterator p(first._block, first._element); + if (first == last) { + return p; + } + + if (p < _data._first_invalid) { + _data._first_invalid = p; + } + + while (p <= last) { + p._element->reset(); + p++; + } + p--; + return p; + } + + void shrink_erased() { + iterator p = begin(); + size_type empty_count = 0; + while (p != end()) { + if (!p._element->has_value()) { + empty_count++; + } else { + const difference_type dist = std::distance(p - empty_count, p); + if (p + dist < _data._last) { + std::move(p + dist, _data._last, p); + } + + iterator new_last = _data._last - dist; + + GapDeque::destroy(_data.ref_to_alloc(), new_last, _data._last); + + _data._last = new_last; + } + p = p.advance(1); + } + + _data._first_invalid = end(); + } + + template<typename... Args> + reference emplace_back(Args&&... args) { + return *emplace(cend(), std::forward<Args>(args)...); + } + + void pop_back() { + assert(!empty()); + iterator p = end(); + p--; + if (_data._first_invalid > p) { + _data._first_invalid = p; + } + if (p) { + p._element->reset(); + } + } + + void push_back(detail::GapDequeAddValue<value_type> auto value) { + if constexpr (std::is_rvalue_reference_v<decltype(value)>) { + if (_data._first_invalid != end()) { + set(_data._first_invalid, std::move(value)); + return; + } + emplace(cend(), std::move(value)); + } else { + if (_data._first_invalid != end()) { + set(_data._first_invalid, value); + return; + } + emplace(cend(), value); + } + } + + void reserve(size_type new_cap) { + const size_type _capacity = capacity(); + if (new_cap > _capacity) { + grow_storage(new_cap - _capacity); + } + } + + // void resize(size_type n) { + // const size_type s = size(); + + // if (n > s) { + // const size_type delta = n - s; + + // const size_type c = capacity(); + + // if (n > c) { + // grow_storage(n - c); + // } + + // _data._last = GapDeque::uninitialized_default_construct_n(_data.ref_to_alloc(), _data._last, delta); + // } else if (n < s) { + // iterator new_last = nth(n); + + // GapDeque::destroy(_data.ref_to_alloc(), new_last, _data._last); + + // _data._last = new_last; + // } + // } + + void shrink_to_fit() { + { + auto new_block_last = _data._last._block + 1; + + destroy_segments(new_block_last, _data._block_last); + + _data._block_last = new_block_last; + + _data._end._block = _data._block_last - 1; + _data._end._element = *(_data._block_last - 1) + (block_size() - 1); + } + + // Shrink table. + { + const size_type table_capacity = _data._block_end - _data._block_first; + + const size_type table_size = _data._block_last - _data._block_first; + + const size_type new_table_capacity = std::max(min_table_capacity(), table_size); + + const size_type n = _data._last._block - _data._first._block; + const size_type m = _data._end._block - _data._first._block; + + // Allocate new table. No effects if allocation fails. + block_pointer new_block_first = allocate_table(new_table_capacity); + block_pointer new_block_last = new_block_first; + block_pointer new_block_end = new_block_first + new_table_capacity; + + // Copy pointers (noexcept). + new_block_last = std::copy(_data._block_first, _data._block_last, new_block_first); + + // Deallocate old table (noexcept). + deallocate_table(_data._block_first, table_capacity); + + // Update pointers (noexcept). + _data._block_first = new_block_first; + _data._block_last = new_block_last; + _data._block_end = new_block_end; + + // Update iterators (noexcept). + _data._first._block = new_block_first; + _data._last._block = new_block_first + n; + _data._end._block = new_block_first + m; + } + } + + void swap(GapDeque& other) noexcept { + assert(allocator_traits::propagate_on_container_swap::value || _data.ref_to_alloc() == other._data.ref_to_alloc()); + + if (this == &other) { + return; + } + + using std::swap; + + if (allocator_traits::propagate_on_container_swap::value) { + swap(_data.ref_to_alloc(), other._data.ref_to_alloc()); + } + + swap(_data, other._data); + } + + private: + struct BlockData { + block_pointer _block_first; + block_pointer _block_last; + block_pointer _block_end; + + iterator _first; + iterator _last; + iterator _end; + + iterator _first_invalid; + }; + + struct Data : BlockData, allocator_type { + Data() noexcept(std::is_nothrow_default_constructible<allocator_type>::value) : allocator_type() {} + + Data(const allocator_type& alloc) noexcept(std::is_nothrow_copy_constructible<allocator_type>::value) + : allocator_type(alloc) {} + + Data(allocator_type&& other) noexcept(std::is_nothrow_move_constructible<allocator_type>::value) + : allocator_type(std::move(other)) {} + + allocator_type& ref_to_alloc() noexcept { + return *this; + } + + const allocator_type& ref_to_alloc() const noexcept { + return *this; + } + } _data; + + [[nodiscard]] reference operator[](size_type index) { + assert(index < size()); + + const auto i = index / block_size(); + const auto j = index - i * block_size(); + + return *(*(_data._block_first + i) + j); + } + [[nodiscard]] const_reference operator[](size_type index) const { + assert(index < size()); + + const auto i = index / block_size(); + const auto j = index - i * block_size(); + + return *(*(_data._block_first + i) + j); + } + + [[nodiscard]] iterator nth(size_type pos) noexcept { + assert(pos <= size()); + + const auto i = pos / block_size(); + const auto j = pos - i * block_size(); + + const auto block = _data._block_first + i; + const auto element = *block + j; + + return iterator(block, element); + } + + [[nodiscard]] const_iterator nth(size_type pos) const noexcept { + assert(pos <= size()); + + const auto i = pos / block_size(); + const auto j = pos - i * block_size(); + + const auto block = _data._block_first + i; + const auto element = *block + j; + + return iterator(block, element); + } + + template<typename AddrT> + static constexpr AddrT* to_address(AddrT* p) noexcept { + static_assert(!std::is_function<AddrT>::value, "not a function pointer"); + return p; + } + + template<typename Pointer> + static constexpr auto to_address(const Pointer& p) noexcept -> typename std::pointer_traits<Pointer>::element_type* { + return GapDeque::to_address(p.operator->()); + } + + template<typename Alloc, typename Size> + static auto allocate(Alloc& a, Size n) -> typename std::allocator_traits<Alloc>::pointer { + if (n != 0) { + return std::allocator_traits<Alloc>::allocate(a, n); + } + return nullptr; + } + + template<typename Alloc, typename Pointer, typename Size> + static void deallocate(Alloc& a, Pointer p, Size n) noexcept { + if (p != nullptr) { + std::allocator_traits<Alloc>::deallocate(a, p, n); + } + } + + template<typename Alloc, typename Pointer, typename... Args> + static void construct_at(Alloc& a, Pointer p, Args&&... args) { + std::allocator_traits<Alloc>::construct(a, GapDeque::to_address(p), std::forward<Args>(args)...); + } + + template<typename Alloc, typename Pointer> + static void destroy_at(Alloc& a, Pointer p) noexcept { + std::allocator_traits<Alloc>::destroy(a, GapDeque::to_address(p)); + } + + template<typename Alloc, typename ForwardIt> + static void destroy(Alloc& a, ForwardIt first, ForwardIt last) noexcept { + while (first != last) { + GapDeque::destroy_at(a, std::addressof(*first)); + ++first; + } + } + + template<typename Alloc, typename ForwardIt, typename Size> + static void destroy_n(Alloc& a, ForwardIt first, Size n) noexcept { + while (n > 0) { + GapDeque::destroy_at(a, std::addressof(*first)); + ++first; + --n; + } + } + + template<typename Alloc, typename ForwardIt, typename Size> + static ForwardIt uninitialized_default_construct_n(Alloc& a, ForwardIt first, Size n) { + ForwardIt curr = first; + if (true) { + while (n > 0) { + GapDeque::construct_at(a, std::addressof(*curr)); + ++curr; + --n; + } + return curr; + } + if (false) { + GapDeque::destroy(a, first, curr); + // SFL_RETHROW; + } + } + + block_pointer allocate_table(size_type n) { + block_allocator block_alloc(_data.ref_to_alloc()); + return GapDeque::allocate(block_alloc, n); + } + + /// Deallocates table at `p`. + /// Does not deallocates segments, it only deallocates memory used by table. + /// + void deallocate_table(block_pointer p, size_type n) noexcept { + block_allocator block_alloc(_data.ref_to_alloc()); + GapDeque::deallocate(block_alloc, p, n); + } + + /// Allocates a segment and returns pointer to it. + /// Does not construct elements, it only allocates memory for segment. + /// + pointer allocate_segment() { + return GapDeque::allocate(_data.ref_to_alloc(), block_size()); + } + + /// Deallocates segments at `p`. + /// Does not destroy elements, it only deallocates memory used by segment. + /// + void deallocate_segment(pointer p) noexcept { + GapDeque::deallocate(_data.ref_to_alloc(), p, block_size()); + } + + /// Allocates segments in table in range [first, last). + /// Does not construct elements, it only allocates memory for segments. + /// + void construct_segments(block_pointer first, block_pointer last) { + block_pointer curr = first; + + if (true) { + while (curr != last) { + *curr = allocate_segment(); + ++curr; + } + } + if (false) { + destroy_segments(first, curr); + // SFL_RETHROW; + } + } + + /// Destroys segments in table in range [first, last). + /// Does not destroy elements, it only deallocates memory used by segments. + /// + void destroy_segments(block_pointer first, block_pointer last) noexcept { + while (first != last) { + deallocate_segment(*first); + ++first; + } + } + + static constexpr size_type min_table_capacity() noexcept { + return 8; + } + + static constexpr double table_grow_factor() noexcept { + return 1.5; + } + + void construct_storage(size_type num_elements) { + if (num_elements > max_size()) { + std::abort(); + // SFL_DTL::throw_length_error("sfl::segmented_vector::construct_storage"); + } + + const size_type num_segments = num_elements / block_size() + 1; + + const size_type table_capacity = std::max(min_table_capacity(), num_segments); + + _data._block_first = allocate_table(table_capacity); + _data._block_last = _data._block_first + num_segments; + _data._block_end = _data._block_first + table_capacity; + + if (true) { + construct_segments(_data._block_first, _data._block_last); + + _data._first._block = _data._block_first; + _data._first._element = *_data._block_first; + + _data._last = _data._first; + + _data._end._block = _data._block_last - 1; + _data._end._element = *(_data._block_last - 1) + (block_size() - 1); + } + if (false) { + deallocate_table(_data._block_first, table_capacity); + // SFL_RETHROW; + } + } + + void grow_storage(size_type num_additional_elements) { + if (max_size() - capacity() < num_additional_elements) { + std::abort(); + // SFL_DTL::throw_length_error("sfl::segmented_vector::grow_storage"); + } + + const size_type num_additional_segments = num_additional_elements / block_size() + 1; + + const size_type available_table_capacity = _data._block_end - _data._block_last; + + // Grow table if neccessary. + if (num_additional_segments > available_table_capacity) { + const size_type table_capacity = _data._block_end - _data._block_first; + + const size_type table_size = _data._block_last - _data._block_first; + + const size_type new_table_capacity = + std::max<size_type>(table_capacity * table_grow_factor(), table_size + num_additional_segments); + + const size_type n = _data._last._block - _data._first._block; + const size_type m = _data._end._block - _data._first._block; + + // Allocate new table. No effects if allocation fails. + block_pointer new_block_first = allocate_table(new_table_capacity); + block_pointer new_block_last = new_block_first; + block_pointer new_block_end = new_block_first + new_table_capacity; + + // Copy pointers (noexcept). + new_block_last = std::copy(_data._block_first, _data._block_last, new_block_first); + + // Deallocate old table (noexcept). + deallocate_table(_data._block_first, table_capacity); + + // Update pointers (noexcept). + _data._block_first = new_block_first; + _data._block_last = new_block_last; + _data._block_end = new_block_end; + + // Update iterators (noexcept). + _data._first._block = new_block_first; + _data._last._block = new_block_first + n; + _data._end._block = new_block_first + m; + } + + auto new_block_last = _data._block_last + num_additional_segments; + + // No effects in allocation fails. + construct_segments(_data._block_last, new_block_last); + + _data._block_last = new_block_last; + + _data._end._block = _data._block_last - 1; + _data._end._element = *(_data._block_last - 1) + (block_size() - 1); + } + + void destroy_storage() noexcept { + destroy_segments(_data._block_first, _data._block_last); + deallocate_table(_data._block_first, _data._block_end - _data._block_first); + } + + void initialize_empty() { + construct_storage(0); + } + + class temporary_value { + private: + allocator_type& _alloc; + + alignas(storage_type) unsigned char _buffer[sizeof(storage_type)]; + + value_type* buffer() { + return reinterpret_cast<storage_type*>(_buffer)->value(); + } + + public: + template<typename... Args> + explicit temporary_value(allocator_type& a, Args&&... args) : _alloc(a) { + GapDeque::construct_at(_alloc, buffer(), std::forward<Args>(args)...); + } + + ~temporary_value() { + GapDeque::destroy_at(_alloc, buffer()); + } + + storage_type& value() { + return *buffer(); + } + }; + }; +} diff --git a/src/openvic-simulation/utility/Utility.hpp b/src/openvic-simulation/utility/Utility.hpp index 8180e55..1b4a632 100644 --- a/src/openvic-simulation/utility/Utility.hpp +++ b/src/openvic-simulation/utility/Utility.hpp @@ -72,6 +72,9 @@ namespace OpenVic::utility { } } + template<typename T, typename... Compare> + concept any_of = (std::same_as<T, Compare> || ...); + template<typename T, template<typename...> class Z> struct is_specialization_of : std::false_type {}; |