RADDataStructures.h

Go to the documentation of this file.

 
#pragma once
 
#include <RADCore/RADLicenseGate.h>
 
#include <algorithm>
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace RADData {
 
    namespace Detail {
        constexpr size_t nextPowerOfTwo(size_t value) {
            if (value <= 2) return 2;
            --value;
            for (size_t shift = 1; shift < sizeof(size_t) * 8; shift <<= 1) {
                value |= value >> shift;
            }
            return value + 1;
        }
    }
 
    template<typename T>
    class RADArrayView {
    public:
        RADArrayView() = default;
        RADArrayView(T* data, size_t size) : data_(data), size_(size) {}
        template<typename Container>
        explicit RADArrayView(Container& container) : data_(container.data()), size_(container.size()) {}
 
        T* data() const { return data_; }
        size_t size() const { return size_; }
        bool empty() const { return size_ == 0; }
        T& operator[](size_t index) const { return data_[index]; }
        T* begin() const { return data_; }
        T* end() const { return data_ + size_; }
 
    private:
        T* data_ = nullptr;
        size_t size_ = 0;
    };
 
    using RADByteArrayView = RADArrayView<uint8_t>;
    using RADConstByteArrayView = RADArrayView<const uint8_t>;
 
    class RADByteArray {
    public:
        RADByteArray() = default;
        explicit RADByteArray(size_t count) : bytes_(count) {}
        RADByteArray(const void* data, size_t size) { append(data, size); }
 
        size_t size() const { return bytes_.size(); }
        bool empty() const { return bytes_.empty(); }
        uint8_t* data() { return bytes_.data(); }
        const uint8_t* data() const { return bytes_.data(); }
        uint8_t& operator[](size_t index) { return bytes_[index]; }
        const uint8_t& operator[](size_t index) const { return bytes_[index]; }
        void clear() { bytes_.clear(); }
        void reserve(size_t capacity) { bytes_.reserve(capacity); }
        void append(uint8_t byte) { bytes_.push_back(byte); }
        void append(const void* data, size_t size) {
            if (!data || size == 0) return;
            const auto* first = static_cast<const uint8_t*>(data);
            bytes_.insert(bytes_.end(), first, first + size);
        }
        RADByteArrayView view() { return RADByteArrayView(bytes_.data(), bytes_.size()); }
        RADConstByteArrayView view() const { return RADConstByteArrayView(bytes_.data(), bytes_.size()); }
        const std::vector<uint8_t>& vector() const { return bytes_; }
 
    private:
        std::vector<uint8_t> bytes_;
    };
 
    class RADMonotonicArena {
    public:
        explicit RADMonotonicArena(size_t capacity = 65536) : storage_(capacity) {}
        void* allocate(size_t size, size_t alignment = alignof(std::max_align_t)) {
            size_t current = offset_;
            const size_t aligned = (current + alignment - 1) & ~(alignment - 1);
            if (aligned + size > storage_.size()) {
                storage_.resize(std::max(storage_.size() * 2, aligned + size));
            }
            offset_ = aligned + size;
            return storage_.data() + aligned;
        }
        void reset() { offset_ = 0; }
        size_t used() const { return offset_; }
        size_t capacity() const { return storage_.size(); }
 
    private:
        std::vector<uint8_t> storage_;
        size_t offset_ = 0;
    };
 
    class RADFixedPool {
    public:
        RADFixedPool(size_t blockSize, size_t blockCount)
            : blockSize_(Detail::nextPowerOfTwo(std::max(blockSize, sizeof(std::max_align_t)))),
              storage_((blockSize_ * blockCount + sizeof(std::max_align_t) - 1) / sizeof(std::max_align_t)),
              freeList_(nullptr) {
            auto* base = reinterpret_cast<uint8_t*>(storage_.data());
            for (size_t i = 0; i < blockCount; ++i) {
                auto* block = base + i * blockSize_;
                *reinterpret_cast<uint8_t**>(block) = freeList_;
                freeList_ = block;
            }
        }
 
        void* allocate() {
            if (!freeList_) return nullptr;
            uint8_t* block = freeList_;
            freeList_ = *reinterpret_cast<uint8_t**>(freeList_);
            return block;
        }
 
        void deallocate(void* ptr) {
            if (!ptr) return;
            auto* block = static_cast<uint8_t*>(ptr);
            *reinterpret_cast<uint8_t**>(block) = freeList_;
            freeList_ = block;
        }
 
        size_t blockSize() const { return blockSize_; }
 
    private:
        size_t blockSize_ = 0;
        std::vector<std::max_align_t> storage_;
        uint8_t* freeList_ = nullptr;
    };
 
    template<typename T>
    class RADMonotonicAllocator {
    public:
        using value_type = T;
 
        template<typename U>
        struct rebind {
            using other = RADMonotonicAllocator<U>;
        };
 
        RADMonotonicAllocator() = default;
        explicit RADMonotonicAllocator(RADMonotonicArena* arena) : arena_(arena) {}
        template<typename U>
        RADMonotonicAllocator(const RADMonotonicAllocator<U>& other) : arena_(other.arena()) {}
 
        T* allocate(size_t n) {
            if (!arena_) return std::allocator<T>{}.allocate(n);
            return static_cast<T*>(arena_->allocate(sizeof(T) * n, alignof(T)));
        }
        void deallocate(T* ptr, size_t n) {
            if (!arena_) std::allocator<T>{}.deallocate(ptr, n);
        }
        RADMonotonicArena* arena() const { return arena_; }
 
        template<typename U> friend class RADMonotonicAllocator;
 
    private:
        RADMonotonicArena* arena_ = nullptr;
    };
 
    template<typename T, typename U>
    bool operator==(const RADMonotonicAllocator<T>& lhs, const RADMonotonicAllocator<U>& rhs) {
        return lhs.arena() == rhs.arena();
    }
 
    template<typename T, typename U>
    bool operator!=(const RADMonotonicAllocator<T>& lhs, const RADMonotonicAllocator<U>& rhs) {
        return !(lhs == rhs);
    }
 
    template<typename T, size_t Alignment = alignof(T)>
    class RADAlignedAllocator {
    public:
        using value_type = T;
 
        template<typename U>
        struct rebind {
            using other = RADAlignedAllocator<U, Alignment>;
        };
 
        T* allocate(size_t n) {
            void* ptr = nullptr;
            if (posix_memalign(&ptr, Alignment, sizeof(T) * n) != 0) {
                throw std::bad_alloc();
            }
            return static_cast<T*>(ptr);
        }
        void deallocate(T* ptr, size_t) { std::free(ptr); }
    };
 
    template<typename T, size_t A, typename U, size_t B>
    bool operator==(const RADAlignedAllocator<T, A>&, const RADAlignedAllocator<U, B>&) {
        return A == B;
    }
 
    template<typename T, size_t A, typename U, size_t B>
    bool operator!=(const RADAlignedAllocator<T, A>& lhs, const RADAlignedAllocator<U, B>& rhs) {
        return !(lhs == rhs);
    }
 
    template <typename T, typename Alloc = std::allocator<T>>
    class RADVector {
    public:
        using value_type = T;
        using allocator_type = Alloc;
        using size_type = size_t;
        using reference = T&;
        using const_reference = const T&;
        using pointer = T*;
        using const_pointer = const T*;
        using iterator = T*;
        using const_iterator = const T*;
 
        RADVector() = default;
 
        explicit RADVector(size_t count, const T& value = T()) {
            resize(count, value);
        }
 
        RADVector(std::initializer_list<T> values) {
            reserve(values.size());
            for (const auto& value : values) push_back(value);
        }
 
        RADVector(const RADVector& other) {
            reserve(other.size_);
            for (const auto& value : other) push_back(value);
        }
 
        RADVector(RADVector&& other) noexcept
            : data_(other.data_),
              size_(other.size_),
              capacity_(other.capacity_),
              allocator_(std::move(other.allocator_)) {
            other.data_ = nullptr;
            other.size_ = 0;
            other.capacity_ = 0;
        }
 
        RADVector& operator=(const RADVector& other) {
            if (this == &other) return *this;
            clear();
            reserve(other.size_);
            for (const auto& value : other) push_back(value);
            return *this;
        }
 
        RADVector& operator=(RADVector&& other) noexcept {
            if (this == &other) return *this;
            destroyStorage();
            data_ = other.data_;
            size_ = other.size_;
            capacity_ = other.capacity_;
            allocator_ = std::move(other.allocator_);
            other.data_ = nullptr;
            other.size_ = 0;
            other.capacity_ = 0;
            return *this;
        }
 
        ~RADVector() {
            destroyStorage();
        }
 
        iterator begin() noexcept { return data_; }
        const_iterator begin() const noexcept { return data_; }
        const_iterator cbegin() const noexcept { return data_; }
        iterator end() noexcept { return data_ + size_; }
        const_iterator end() const noexcept { return data_ + size_; }
        const_iterator cend() const noexcept { return data_ + size_; }
 
        bool empty() const noexcept { return size_ == 0; }
        size_t size() const noexcept { return size_; }
        size_t capacity() const noexcept { return capacity_; }
        T* data() noexcept { return data_; }
        const T* data() const noexcept { return data_; }
 
        T& operator[](size_t index) noexcept { return data_[index]; }
        const T& operator[](size_t index) const noexcept { return data_[index]; }
 
        T& at(size_t index) {
            if (index >= size_) throw std::out_of_range("RADVector::at");
            return data_[index];
        }
 
        const T& at(size_t index) const {
            if (index >= size_) throw std::out_of_range("RADVector::at");
            return data_[index];
        }
 
        T& front() noexcept { return data_[0]; }
        const T& front() const noexcept { return data_[0]; }
        T& back() noexcept { return data_[size_ - 1]; }
        const T& back() const noexcept { return data_[size_ - 1]; }
 
        void reserve(size_t newCapacity) {
            if (newCapacity <= capacity_) return;
            reallocate(newCapacity);
        }
 
        void shrink_to_fit() {
            if (size_ == capacity_) return;
            if (size_ == 0) {
                destroyStorage();
                return;
            }
            reallocate(size_);
        }
 
        void resize(size_t newSize) {
            if (newSize < size_) {
                destroyRange(newSize, size_);
                size_ = newSize;
                return;
            }
            reserveForSize(newSize);
            for (; size_ < newSize; ++size_) {
                std::allocator_traits<Alloc>::construct(allocator_, data_ + size_);
            }
        }
 
        void resize(size_t newSize, const T& value) {
            if (newSize < size_) {
                destroyRange(newSize, size_);
                size_ = newSize;
                return;
            }
            reserveForSize(newSize);
            for (; size_ < newSize; ++size_) {
                std::allocator_traits<Alloc>::construct(allocator_, data_ + size_, value);
            }
        }
 
        template <typename... Args>
        T& emplace_back(Args&&... args) {
            reserveForSize(size_ + 1);
            std::allocator_traits<Alloc>::construct(
                allocator_, data_ + size_, std::forward<Args>(args)...);
            return data_[size_++];
        }
 
        void push_back(const T& value) { emplace_back(value); }
        void push_back(T&& value) { emplace_back(std::move(value)); }
 
        void pop_back() {
            if (size_ == 0) return;
            --size_;
            std::allocator_traits<Alloc>::destroy(allocator_, data_ + size_);
        }
 
        iterator erase(const_iterator position) {
            const size_t index = static_cast<size_t>(position - data_);
            if (index >= size_) return end();
            for (size_t i = index; i + 1 < size_; ++i) {
                data_[i] = std::move(data_[i + 1]);
            }
            pop_back();
            return data_ + index;
        }
 
        void clear() noexcept {
            destroyRange(0, size_);
            size_ = 0;
        }
 
    private:
        void reserveForSize(size_t desired) {
            if (desired <= capacity_) return;
            const size_t grown = capacity_ == 0 ? 8 : capacity_ + capacity_ / 2;
            reallocate(std::max(desired, grown));
        }
 
        void reallocate(size_t newCapacity) {
            T* newData = std::allocator_traits<Alloc>::allocate(allocator_, newCapacity);
            size_t constructed = 0;
            try {
                for (; constructed < size_; ++constructed) {
                    std::allocator_traits<Alloc>::construct(
                        allocator_, newData + constructed,
                        std::move_if_noexcept(data_[constructed]));
                }
            } catch (...) {
                for (size_t i = 0; i < constructed; ++i) {
                    std::allocator_traits<Alloc>::destroy(allocator_, newData + i);
                }
                std::allocator_traits<Alloc>::deallocate(allocator_, newData, newCapacity);
                throw;
            }
            destroyRange(0, size_);
            if (data_) std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
            data_ = newData;
            capacity_ = newCapacity;
        }
 
        void destroyRange(size_t first, size_t last) noexcept {
            for (size_t i = first; i < last; ++i) {
                std::allocator_traits<Alloc>::destroy(allocator_, data_ + i);
            }
        }
 
        void destroyStorage() noexcept {
            clear();
            if (data_) {
                std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
                data_ = nullptr;
                capacity_ = 0;
            }
        }
 
        T* data_ = nullptr;
        size_t size_ = 0;
        size_t capacity_ = 0;
        Alloc allocator_;
    };
 
    template <typename T, size_t InlineN = 8, typename Alloc = std::allocator<T>>
    class RADSmallVector {
    public:
        using iterator = T*;
        using const_iterator = const T*;
 
        RADSmallVector()
            : data_(inlineData()), capacity_(InlineN) {}
 
        RADSmallVector(std::initializer_list<T> values)
            : RADSmallVector() {
            reserve(values.size());
            for (const auto& value : values) push_back(value);
        }
 
        RADSmallVector(const RADSmallVector& other)
            : RADSmallVector() {
            reserve(other.size_);
            for (const auto& value : other) push_back(value);
        }
 
        RADSmallVector(RADSmallVector&& other) noexcept
            : RADSmallVector() {
            if (other.usingInline()) {
                for (auto& value : other) push_back(std::move(value));
                other.clear();
            } else {
                data_ = other.data_;
                size_ = other.size_;
                capacity_ = other.capacity_;
                other.data_ = other.inlineData();
                other.size_ = 0;
                other.capacity_ = InlineN;
            }
        }
 
        RADSmallVector& operator=(const RADSmallVector& other) {
            if (this == &other) return *this;
            clear();
            reserve(other.size_);
            for (const auto& value : other) push_back(value);
            return *this;
        }
 
        RADSmallVector& operator=(RADSmallVector&& other) noexcept {
            if (this == &other) return *this;
            destroyHeapStorage();
            data_ = inlineData();
            size_ = 0;
            capacity_ = InlineN;
            if (other.usingInline()) {
                for (auto& value : other) push_back(std::move(value));
                other.clear();
            } else {
                data_ = other.data_;
                size_ = other.size_;
                capacity_ = other.capacity_;
                other.data_ = other.inlineData();
                other.size_ = 0;
                other.capacity_ = InlineN;
            }
            return *this;
        }
 
        ~RADSmallVector() {
            destroyHeapStorage();
        }
 
        iterator begin() noexcept { return data_; }
        const_iterator begin() const noexcept { return data_; }
        iterator end() noexcept { return data_ + size_; }
        const_iterator end() const noexcept { return data_ + size_; }
        bool empty() const noexcept { return size_ == 0; }
        size_t size() const noexcept { return size_; }
        size_t capacity() const noexcept { return capacity_; }
        bool usingInlineStorage() const noexcept { return usingInline(); }
        T* data() noexcept { return data_; }
        const T* data() const noexcept { return data_; }
        T& operator[](size_t index) noexcept { return data_[index]; }
        const T& operator[](size_t index) const noexcept { return data_[index]; }
        T& back() noexcept { return data_[size_ - 1]; }
        const T& back() const noexcept { return data_[size_ - 1]; }
 
        void reserve(size_t newCapacity) {
            if (newCapacity <= capacity_) return;
            reallocate(newCapacity);
        }
 
        template <typename... Args>
        T& emplace_back(Args&&... args) {
            if (size_ == capacity_) {
                reallocate(capacity_ + capacity_ / 2 + 1);
            }
            new (data_ + size_) T(std::forward<Args>(args)...);
            return data_[size_++];
        }
 
        void push_back(const T& value) { emplace_back(value); }
        void push_back(T&& value) { emplace_back(std::move(value)); }
 
        void pop_back() {
            if (size_ == 0) return;
            data_[--size_].~T();
        }
 
        void clear() noexcept {
            for (size_t i = 0; i < size_; ++i) data_[i].~T();
            size_ = 0;
        }
 
    private:
        using Storage = std::aligned_storage_t<sizeof(T), alignof(T)>;
 
        T* inlineData() noexcept {
            return reinterpret_cast<T*>(inlineStorage_);
        }
 
        const T* inlineData() const noexcept {
            return reinterpret_cast<const T*>(inlineStorage_);
        }
 
        bool usingInline() const noexcept {
            return data_ == inlineData();
        }
 
        void reallocate(size_t newCapacity) {
            T* newData = std::allocator_traits<Alloc>::allocate(allocator_, newCapacity);
            size_t constructed = 0;
            try {
                for (; constructed < size_; ++constructed) {
                    new (newData + constructed) T(std::move_if_noexcept(data_[constructed]));
                }
            } catch (...) {
                for (size_t i = 0; i < constructed; ++i) newData[i].~T();
                std::allocator_traits<Alloc>::deallocate(allocator_, newData, newCapacity);
                throw;
            }
            clear();
            if (!usingInline()) {
                std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
            }
            data_ = newData;
            size_ = constructed;
            capacity_ = newCapacity;
        }
 
        void destroyHeapStorage() noexcept {
            clear();
            if (!usingInline()) {
                std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
                data_ = inlineData();
                capacity_ = InlineN;
            }
        }
 
        Storage inlineStorage_[InlineN == 0 ? 1 : InlineN];
        T* data_;
        size_t size_ = 0;
        size_t capacity_;
        Alloc allocator_;
    };
 
    template <typename T, typename Alloc = std::allocator<T>>
    class RADRingBuffer {
    public:
        explicit RADRingBuffer(size_t capacity = 16) {
            reserve(capacity);
        }
 
        ~RADRingBuffer() {
            clear();
            if (data_) std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
        }
 
        RADRingBuffer(const RADRingBuffer& other) {
            reserve(other.capacity_);
            for (const auto& value : other) push_back(value);
        }
 
        RADRingBuffer& operator=(const RADRingBuffer& other) {
            if (this == &other) return *this;
            clear();
            reserve(other.capacity_);
            for (const auto& value : other) push_back(value);
            return *this;
        }
 
        RADRingBuffer(RADRingBuffer&& other) noexcept
            : data_(other.data_),
              capacity_(other.capacity_),
              mask_(other.mask_),
              head_(other.head_),
              size_(other.size_),
              allocator_(std::move(other.allocator_)) {
            other.data_ = nullptr;
            other.capacity_ = 0;
            other.mask_ = 0;
            other.head_ = 0;
            other.size_ = 0;
        }
 
        RADRingBuffer& operator=(RADRingBuffer&& other) noexcept {
            if (this == &other) return *this;
            clear();
            if (data_) std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
            data_ = other.data_;
            capacity_ = other.capacity_;
            mask_ = other.mask_;
            head_ = other.head_;
            size_ = other.size_;
            allocator_ = std::move(other.allocator_);
            other.data_ = nullptr;
            other.capacity_ = 0;
            other.mask_ = 0;
            other.head_ = 0;
            other.size_ = 0;
            return *this;
        }
 
        class iterator {
        public:
            using iterator_category = std::forward_iterator_tag;
            using value_type = T;
            using difference_type = std::ptrdiff_t;
            using pointer = T*;
            using reference = T&;
 
            iterator(RADRingBuffer* owner, size_t offset) : owner_(owner), offset_(offset) {}
            T& operator*() const { return (*owner_)[offset_]; }
            iterator& operator++() { ++offset_; return *this; }
            bool operator!=(const iterator& other) const { return offset_ != other.offset_; }
 
        private:
            RADRingBuffer* owner_;
            size_t offset_;
        };
 
        class const_iterator {
        public:
            using iterator_category = std::forward_iterator_tag;
            using value_type = T;
            using difference_type = std::ptrdiff_t;
            using pointer = const T*;
            using reference = const T&;
 
            const_iterator(const RADRingBuffer* owner, size_t offset) : owner_(owner), offset_(offset) {}
            const T& operator*() const { return (*owner_)[offset_]; }
            const_iterator& operator++() { ++offset_; return *this; }
            bool operator!=(const const_iterator& other) const { return offset_ != other.offset_; }
 
        private:
            const RADRingBuffer* owner_;
            size_t offset_;
        };
 
        iterator begin() noexcept { return iterator(this, 0); }
        iterator end() noexcept { return iterator(this, size_); }
        const_iterator begin() const noexcept { return const_iterator(this, 0); }
        const_iterator end() const noexcept { return const_iterator(this, size_); }
 
        bool empty() const noexcept { return size_ == 0; }
        size_t size() const noexcept { return size_; }
        size_t capacity() const noexcept { return capacity_; }
 
        T& operator[](size_t index) noexcept { return data_[physical(index)]; }
        const T& operator[](size_t index) const noexcept { return data_[physical(index)]; }
        T& front() noexcept { return (*this)[0]; }
        const T& front() const noexcept { return (*this)[0]; }
        T& back() noexcept { return (*this)[size_ - 1]; }
        const T& back() const noexcept { return (*this)[size_ - 1]; }
 
        void reserve(size_t requestedCapacity) {
            const size_t newCapacity = Detail::nextPowerOfTwo(requestedCapacity);
            if (newCapacity <= capacity_) return;
            T* newData = std::allocator_traits<Alloc>::allocate(allocator_, newCapacity);
            size_t constructed = 0;
            try {
                for (; constructed < size_; ++constructed) {
                    std::allocator_traits<Alloc>::construct(
                        allocator_, newData + constructed,
                        std::move_if_noexcept((*this)[constructed]));
                }
            } catch (...) {
                for (size_t i = 0; i < constructed; ++i) {
                    std::allocator_traits<Alloc>::destroy(allocator_, newData + i);
                }
                std::allocator_traits<Alloc>::deallocate(allocator_, newData, newCapacity);
                throw;
            }
            clear();
            if (data_) std::allocator_traits<Alloc>::deallocate(allocator_, data_, capacity_);
            data_ = newData;
            capacity_ = newCapacity;
            mask_ = capacity_ - 1;
            head_ = 0;
            size_ = constructed;
        }
 
        template <typename... Args>
        T& emplace_back(Args&&... args) {
            if (size_ == capacity_) reserve(capacity_ * 2);
            const size_t index = physical(size_);
            std::allocator_traits<Alloc>::construct(
                allocator_, data_ + index, std::forward<Args>(args)...);
            ++size_;
            return data_[index];
        }
 
        template <typename... Args>
        T& emplace_front(Args&&... args) {
            if (size_ == capacity_) reserve(capacity_ * 2);
            head_ = (head_ - 1) & mask_;
            std::allocator_traits<Alloc>::construct(
                allocator_, data_ + head_, std::forward<Args>(args)...);
            ++size_;
            return data_[head_];
        }
 
        void push_back(const T& value) { emplace_back(value); }
        void push_back(T&& value) { emplace_back(std::move(value)); }
        void push_front(const T& value) { emplace_front(value); }
        void push_front(T&& value) { emplace_front(std::move(value)); }
 
        void pop_front() {
            if (empty()) return;
            std::allocator_traits<Alloc>::destroy(allocator_, data_ + head_);
            head_ = (head_ + 1) & mask_;
            --size_;
        }
 
        void pop_back() {
            if (empty()) return;
            const size_t index = physical(size_ - 1);
            std::allocator_traits<Alloc>::destroy(allocator_, data_ + index);
            --size_;
        }
 
        void clear() noexcept {
            for (size_t i = 0; i < size_; ++i) {
                std::allocator_traits<Alloc>::destroy(allocator_, data_ + physical(i));
            }
            head_ = 0;
            size_ = 0;
        }
 
    private:
        size_t physical(size_t logical) const noexcept {
            return (head_ + logical) & mask_;
        }
 
        T* data_ = nullptr;
        size_t capacity_ = 0;
        size_t mask_ = 0;
        size_t head_ = 0;
        size_t size_ = 0;
        Alloc allocator_;
    };
 
    template <typename T, typename Alloc = std::allocator<T>>
    class RADQueue {
    public:
        explicit RADQueue(size_t capacity = 16) : buffer_(capacity) {}
        bool empty() const noexcept { return buffer_.empty(); }
        size_t size() const noexcept { return buffer_.size(); }
        T& front() noexcept { return buffer_.front(); }
        const T& front() const noexcept { return buffer_.front(); }
        void push(const T& value) { buffer_.push_back(value); }
        void push(T&& value) { buffer_.push_back(std::move(value)); }
        template <typename... Args> T& emplace(Args&&... args) {
            return buffer_.emplace_back(std::forward<Args>(args)...);
        }
        void pop() { buffer_.pop_front(); }
        void clear() { buffer_.clear(); }
 
    private:
        RADRingBuffer<T, Alloc> buffer_;
    };
 
    template <typename T, typename Alloc = std::allocator<T>>
    class RADStack {
    public:
        bool empty() const noexcept { return values_.empty(); }
        size_t size() const noexcept { return values_.size(); }
        T& top() noexcept { return values_.back(); }
        const T& top() const noexcept { return values_.back(); }
        void push(const T& value) { values_.push_back(value); }
        void push(T&& value) { values_.push_back(std::move(value)); }
        template <typename... Args> T& emplace(Args&&... args) {
            return values_.emplace_back(std::forward<Args>(args)...);
        }
        void pop() { values_.pop_back(); }
        void clear() { values_.clear(); }
 
    private:
        RADVector<T, Alloc> values_;
    };
 
    template <typename T>
    class RADSpscQueue {
    public:
        explicit RADSpscQueue(size_t capacity)
            : capacity_(Detail::nextPowerOfTwo(capacity + 1)),
              mask_(capacity_ - 1),
              storage_(std::make_unique<Slot[]>(capacity_)) {}
 
        ~RADSpscQueue() {
            while (!empty()) {
                const size_t head = head_.load(std::memory_order_relaxed);
                storage_[head].ptr()->~T();
                head_.store((head + 1) & mask_, std::memory_order_relaxed);
            }
        }
 
        RADSpscQueue(const RADSpscQueue&) = delete;
        RADSpscQueue& operator=(const RADSpscQueue&) = delete;
 
        bool empty() const noexcept {
            return head_.load(std::memory_order_acquire) == tail_.load(std::memory_order_acquire);
        }
 
        size_t capacity() const noexcept { return capacity_ - 1; }
 
        bool try_push(const T& value) {
            return emplace(value);
        }
 
        bool try_push(T&& value) {
            return emplace(std::move(value));
        }
 
        template <typename... Args>
        bool emplace(Args&&... args) {
            const size_t tail = tail_.load(std::memory_order_relaxed);
            const size_t next = (tail + 1) & mask_;
            if (next == head_.load(std::memory_order_acquire)) return false;
            new (storage_[tail].ptr()) T(std::forward<Args>(args)...);
            tail_.store(next, std::memory_order_release);
            return true;
        }
 
        bool try_pop(T& out) {
            const size_t head = head_.load(std::memory_order_relaxed);
            if (head == tail_.load(std::memory_order_acquire)) return false;
            T* value = storage_[head].ptr();
            out = std::move(*value);
            value->~T();
            head_.store((head + 1) & mask_, std::memory_order_release);
            return true;
        }
 
    private:
        struct Slot {
            alignas(T) unsigned char bytes[sizeof(T)];
            T* ptr() noexcept { return reinterpret_cast<T*>(bytes); }
        };
 
        const size_t capacity_;
        const size_t mask_;
        std::unique_ptr<Slot[]> storage_;
        std::atomic<size_t> head_{0};
        std::atomic<size_t> tail_{0};
    };
 
    template <typename K, typename V, typename Hash = std::hash<K>, typename Eq = std::equal_to<K>>
    class RADFlatHashMap {
    public:
        using value_type = std::pair<K, V>;
 
    private:
        enum class State : uint8_t { Empty, Occupied, Deleted };
        struct Entry {
            State state = State::Empty;
            std::optional<value_type> value;
        };
        struct InsertSlot {
            size_t index;
            bool found;
        };
 
        static constexpr size_t npos = std::numeric_limits<size_t>::max();
 
    public:
        RADFlatHashMap() {
            rehash(16);
        }
 
        explicit RADFlatHashMap(size_t capacity) {
            rehash(capacity);
        }
 
        RADFlatHashMap(const RADFlatHashMap& other) {
            rehash(other.capacity_);
            for (const auto& value : other) insert(value.first, value.second);
        }
 
        RADFlatHashMap& operator=(const RADFlatHashMap& other) {
            if (this == &other) return *this;
            clear();
            delete[] entries_;
            entries_ = nullptr;
            capacity_ = 0;
            mask_ = 0;
            tombstones_ = 0;
            rehash(other.capacity_);
            for (const auto& value : other) insert(value.first, value.second);
            return *this;
        }
 
        RADFlatHashMap(RADFlatHashMap&& other) noexcept
            : entries_(other.entries_),
              capacity_(other.capacity_),
              mask_(other.mask_),
              size_(other.size_),
              tombstones_(other.tombstones_),
              hasher_(std::move(other.hasher_)),
              eq_(std::move(other.eq_)) {
            other.entries_ = nullptr;
            other.capacity_ = 0;
            other.mask_ = 0;
            other.size_ = 0;
            other.tombstones_ = 0;
        }
 
        RADFlatHashMap& operator=(RADFlatHashMap&& other) noexcept {
            if (this == &other) return *this;
            clear();
            delete[] entries_;
            entries_ = other.entries_;
            capacity_ = other.capacity_;
            mask_ = other.mask_;
            size_ = other.size_;
            tombstones_ = other.tombstones_;
            hasher_ = std::move(other.hasher_);
            eq_ = std::move(other.eq_);
            other.entries_ = nullptr;
            other.capacity_ = 0;
            other.mask_ = 0;
            other.size_ = 0;
            other.tombstones_ = 0;
            return *this;
        }
 
        ~RADFlatHashMap() {
            clear();
            delete[] entries_;
        }
 
        class iterator {
        public:
            iterator(Entry* entry, Entry* end) : entry_(entry), end_(end) { skip(); }
            value_type& operator*() const { return *entry_->value; }
            value_type* operator->() const { return &*entry_->value; }
            iterator& operator++() { ++entry_; skip(); return *this; }
            bool operator!=(const iterator& other) const { return entry_ != other.entry_; }
 
        private:
            void skip() {
                while (entry_ != end_ && entry_->state != State::Occupied) ++entry_;
            }
            Entry* entry_;
            Entry* end_;
        };
 
        class const_iterator {
        public:
            const_iterator(const Entry* entry, const Entry* end) : entry_(entry), end_(end) { skip(); }
            const value_type& operator*() const { return *entry_->value; }
            const value_type* operator->() const { return &*entry_->value; }
            const_iterator& operator++() { ++entry_; skip(); return *this; }
            bool operator!=(const const_iterator& other) const { return entry_ != other.entry_; }
 
        private:
            void skip() {
                while (entry_ != end_ && entry_->state != State::Occupied) ++entry_;
            }
            const Entry* entry_;
            const Entry* end_;
        };
 
        iterator begin() noexcept { return iterator(entries_, entries_ + capacity_); }
        iterator end() noexcept { return iterator(entries_ + capacity_, entries_ + capacity_); }
        const_iterator begin() const noexcept { return const_iterator(entries_, entries_ + capacity_); }
        const_iterator end() const noexcept { return const_iterator(entries_ + capacity_, entries_ + capacity_); }
 
        bool empty() const noexcept { return size_ == 0; }
        size_t size() const noexcept { return size_; }
        size_t capacity() const noexcept { return capacity_; }
 
        void clear() noexcept {
            if (!entries_) return;
            for (size_t i = 0; i < capacity_; ++i) {
                if (entries_[i].state == State::Occupied) entries_[i].value.reset();
                entries_[i].state = State::Empty;
            }
            size_ = 0;
            tombstones_ = 0;
        }
 
        bool contains(const K& key) const {
            return findIndex(key) != npos;
        }
 
        V* find(const K& key) {
            const size_t index = findIndex(key);
            return index == npos ? nullptr : &entries_[index].value->second;
        }
 
        const V* find(const K& key) const {
            const size_t index = findIndex(key);
            return index == npos ? nullptr : &entries_[index].value->second;
        }
 
        std::pair<iterator, bool> insert(const K& key, const V& value) {
            return emplace(key, value);
        }
 
        template <typename KeyArg, typename ValueArg>
        std::pair<iterator, bool> emplace(KeyArg&& key, ValueArg&& value) {
            ensureCapacity();
            InsertSlot slot = findInsertSlot(key);
            if (slot.found) {
                entries_[slot.index].value->second = std::forward<ValueArg>(value);
                return {iterator(entries_ + slot.index, entries_ + capacity_), false};
            }
            if (entries_[slot.index].state == State::Deleted) --tombstones_;
            entries_[slot.index].state = State::Occupied;
            entries_[slot.index].value.emplace(
                std::forward<KeyArg>(key), std::forward<ValueArg>(value));
            ++size_;
            return {iterator(entries_ + slot.index, entries_ + capacity_), true};
        }
 
        V& operator[](const K& key) {
            return emplace(key, V{}).first->second;
        }
 
        bool erase(const K& key) {
            const size_t index = findIndex(key);
            if (index == npos) return false;
            entries_[index].value.reset();
            entries_[index].state = State::Deleted;
            --size_;
            ++tombstones_;
            return true;
        }
 
        void reserve(size_t desired) {
            if (desired * 10 < capacity_ * 7) return;
            rehash(desired * 2);
        }
 
    private:
        void ensureCapacity() {
            if ((size_ + tombstones_ + 1) * 10 >= capacity_ * 7) {
                rehash(capacity_ * 2);
            }
        }
 
        void rehash(size_t requestedCapacity) {
            const size_t newCapacity = Detail::nextPowerOfTwo(std::max<size_t>(16, requestedCapacity));
            Entry* oldEntries = entries_;
            const size_t oldCapacity = capacity_;
            entries_ = new Entry[newCapacity];
            capacity_ = newCapacity;
            mask_ = newCapacity - 1;
            size_ = 0;
            tombstones_ = 0;
            if (!oldEntries) return;
            for (size_t i = 0; i < oldCapacity; ++i) {
                if (oldEntries[i].state == State::Occupied) {
                    emplace(std::move(oldEntries[i].value->first), std::move(oldEntries[i].value->second));
                    oldEntries[i].value.reset();
                }
            }
            delete[] oldEntries;
        }
 
        size_t findIndex(const K& key) const {
            if (!entries_) return npos;
            size_t index = hasher_(key) & mask_;
            for (;;) {
                const Entry& entry = entries_[index];
                if (entry.state == State::Empty) return npos;
                if (entry.state == State::Occupied && eq_(entry.value->first, key)) return index;
                index = (index + 1) & mask_;
            }
        }
 
        template <typename KeyArg>
        InsertSlot findInsertSlot(const KeyArg& key) const {
            size_t index = hasher_(key) & mask_;
            size_t firstDeleted = npos;
            for (;;) {
                const Entry& entry = entries_[index];
                if (entry.state == State::Empty) {
                    return {firstDeleted == npos ? index : firstDeleted, false};
                }
                if (entry.state == State::Deleted) {
                    if (firstDeleted == npos) firstDeleted = index;
                } else if (eq_(entry.value->first, key)) {
                    return {index, true};
                }
                index = (index + 1) & mask_;
            }
        }
 
        Entry* entries_ = nullptr;
        size_t capacity_ = 0;
        size_t mask_ = 0;
        size_t size_ = 0;
        size_t tombstones_ = 0;
        Hash hasher_;
        Eq eq_;
    };
 
    template <typename K, typename Hash = std::hash<K>, typename Eq = std::equal_to<K>>
    class RADFlatHashSet {
    public:
        bool empty() const noexcept { return map_.empty(); }
        size_t size() const noexcept { return map_.size(); }
        void clear() noexcept { map_.clear(); }
        void reserve(size_t desired) { map_.reserve(desired); }
        bool contains(const K& key) const { return map_.contains(key); }
        bool insert(const K& key) { return map_.insert(key, Empty{}).second; }
        bool erase(const K& key) { return map_.erase(key); }
 
    private:
        struct Empty {};
        RADFlatHashMap<K, Empty, Hash, Eq> map_;
    };
 
    template <typename T, typename Alloc = std::allocator<T>>
    class RADList {
        struct Node;
 
    public:
        RADList() = default;
 
        RADList(std::initializer_list<T> values) {
            for (const auto& value : values) push_back(value);
        }
 
        RADList(const RADList& other) {
            for (const auto& value : other) push_back(value);
        }
 
        RADList& operator=(const RADList& other) {
            if (this == &other) return *this;
            clear();
            for (const auto& value : other) push_back(value);
            return *this;
        }
 
        RADList(RADList&& other) noexcept
            : head_(other.head_), tail_(other.tail_), size_(other.size_) {
            other.head_ = nullptr;
            other.tail_ = nullptr;
            other.size_ = 0;
        }
 
        RADList& operator=(RADList&& other) noexcept {
            if (this == &other) return *this;
            clear();
            head_ = other.head_;
            tail_ = other.tail_;
            size_ = other.size_;
            other.head_ = nullptr;
            other.tail_ = nullptr;
            other.size_ = 0;
            return *this;
        }
 
        ~RADList() {
            clear();
        }
 
        class iterator {
        public:
            iterator(Node* node) : node_(node) {}
            T& operator*() const { return node_->value; }
            T* operator->() const { return &node_->value; }
            iterator& operator++() { node_ = node_->next; return *this; }
            iterator& operator--() { node_ = node_->prev; return *this; }
            bool operator!=(const iterator& other) const { return node_ != other.node_; }
            bool operator==(const iterator& other) const { return node_ == other.node_; }
 
        private:
            friend class RADList;
            Node* node_;
        };
 
        class const_iterator {
        public:
            const_iterator(const Node* node) : node_(node) {}
            const T& operator*() const { return node_->value; }
            const T* operator->() const { return &node_->value; }
            const_iterator& operator++() { node_ = node_->next; return *this; }
            bool operator!=(const const_iterator& other) const { return node_ != other.node_; }
 
        private:
            const Node* node_;
        };
 
        iterator begin() noexcept { return iterator(head_); }
        iterator end() noexcept { return iterator(nullptr); }
        const_iterator begin() const noexcept { return const_iterator(head_); }
        const_iterator end() const noexcept { return const_iterator(nullptr); }
        bool empty() const noexcept { return size_ == 0; }
        size_t size() const noexcept { return size_; }
        T& front() noexcept { return head_->value; }
        const T& front() const noexcept { return head_->value; }
        T& back() noexcept { return tail_->value; }
        const T& back() const noexcept { return tail_->value; }
 
        template <typename... Args>
        T& emplace_back(Args&&... args) {
            Node* node = new Node(std::forward<Args>(args)...);
            node->prev = tail_;
            if (tail_) tail_->next = node;
            else head_ = node;
            tail_ = node;
            ++size_;
            return node->value;
        }
 
        template <typename... Args>
        T& emplace_front(Args&&... args) {
            Node* node = new Node(std::forward<Args>(args)...);
            node->next = head_;
            if (head_) head_->prev = node;
            else tail_ = node;
            head_ = node;
            ++size_;
            return node->value;
        }
 
        void push_back(const T& value) { emplace_back(value); }
        void push_back(T&& value) { emplace_back(std::move(value)); }
        void push_front(const T& value) { emplace_front(value); }
        void push_front(T&& value) { emplace_front(std::move(value)); }
 
        void pop_front() {
            if (!head_) return;
            Node* node = head_;
            head_ = head_->next;
            if (head_) head_->prev = nullptr;
            else tail_ = nullptr;
            delete node;
            --size_;
        }
 
        void pop_back() {
            if (!tail_) return;
            Node* node = tail_;
            tail_ = tail_->prev;
            if (tail_) tail_->next = nullptr;
            else head_ = nullptr;
            delete node;
            --size_;
        }
 
        iterator erase(iterator it) {
            Node* node = it.node_;
            if (!node) return end();
            Node* next = node->next;
            if (node->prev) node->prev->next = node->next;
            else head_ = node->next;
            if (node->next) node->next->prev = node->prev;
            else tail_ = node->prev;
            delete node;
            --size_;
            return iterator(next);
        }
 
        void clear() noexcept {
            Node* node = head_;
            while (node) {
                Node* next = node->next;
                delete node;
                node = next;
            }
            head_ = nullptr;
            tail_ = nullptr;
            size_ = 0;
        }
 
    private:
        struct Node {
            template <typename... Args>
            explicit Node(Args&&... args) : value(std::forward<Args>(args)...) {}
            T value;
            Node* prev = nullptr;
            Node* next = nullptr;
        };
 
        Node* head_ = nullptr;
        Node* tail_ = nullptr;
        size_t size_ = 0;
    };
 
} // namespace RADData