// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// SboWords.hpp
// Word array with small-buffer optimization
// Used inside the Int class as a replacement for std::vector<uint64_t>

#ifndef SANGI_SBO_WORDS_HPP
#define SANGI_SBO_WORDS_HPP

#include <cstdint>
#include <cstddef>
#include <cstring>
#include <algorithm>
#include <iterator>

namespace sangi {

    /**
     * @brief uint64_t array with SBO (Small Buffer Optimization)
     *
     * Stores up to 9 words (576 bits) in an inline buffer and avoids
     * heap allocation in that range.
     * Provides an interface compatible with std::vector<uint64_t>.
     *
     * Reason for choosing 9 words: when adding two 512-bit (8-word) values,
     * a carry may make the result 9 words. Keep that case within the SBO.
     *
     * Layout (96 bytes):
     *   m_inline[9]  : 72 bytes
     *   m_data       :  8 bytes (-> m_inline or heap)
     *   m_size       :  8 bytes
     *   m_capacity   :  8 bytes
     */
    class SboWords {
    public:
        static constexpr size_t INLINE_CAP = 9;

        using value_type = uint64_t;
        using iterator = uint64_t*;
        using const_iterator = const uint64_t*;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;

        // ----------------------------------------------------------------
        // Constructors / destructor
        // ----------------------------------------------------------------

        SboWords() noexcept
            : m_data(m_inline), m_size(0), m_capacity(INLINE_CAP) {}

        SboWords(const SboWords& other)
            : m_size(other.m_size) {
            if (other.m_size <= INLINE_CAP) {
                m_data = m_inline;
                m_capacity = INLINE_CAP;
            } else {
                m_data = new uint64_t[other.m_size];
                m_capacity = other.m_size;
            }
            std::memcpy(m_data, other.m_data, m_size * sizeof(uint64_t));
        }

        SboWords(SboWords&& other) noexcept
            : m_size(other.m_size) {
            if (other.is_inline()) {
                // Copy the inline data
                m_data = m_inline;
                m_capacity = INLINE_CAP;
                std::memcpy(m_inline, other.m_inline, m_size * sizeof(uint64_t));
            } else {
                // Steal the heap pointer
                m_data = other.m_data;
                m_capacity = other.m_capacity;
                other.m_data = other.m_inline;
            }
            other.m_size = 0;
            other.m_capacity = INLINE_CAP;
        }

        ~SboWords() {
            if (!is_inline()) {
                delete[] m_data;
            }
        }

        // ----------------------------------------------------------------
        // Assignment operators
        // ----------------------------------------------------------------

        SboWords& operator=(const SboWords& other) {
            if (this == &other) return *this;

            if (other.m_size <= m_capacity) {
                // Fits in the existing buffer
                std::memcpy(m_data, other.m_data, other.m_size * sizeof(uint64_t));
                m_size = other.m_size;
            } else {
                // A new buffer is needed
                uint64_t* new_data = new uint64_t[other.m_size];
                std::memcpy(new_data, other.m_data, other.m_size * sizeof(uint64_t));
                if (!is_inline()) delete[] m_data;
                m_data = new_data;
                m_size = other.m_size;
                m_capacity = other.m_size;
            }
            return *this;
        }

        SboWords& operator=(SboWords&& other) noexcept {
            if (this == &other) return *this;

            if (!is_inline()) delete[] m_data;

            m_size = other.m_size;
            if (other.is_inline()) {
                m_data = m_inline;
                m_capacity = INLINE_CAP;
                std::memcpy(m_inline, other.m_inline, m_size * sizeof(uint64_t));
            } else {
                m_data = other.m_data;
                m_capacity = other.m_capacity;
                other.m_data = other.m_inline;
            }
            other.m_size = 0;
            other.m_capacity = INLINE_CAP;
            return *this;
        }

        // ----------------------------------------------------------------
        // Size / capacity
        // ----------------------------------------------------------------

        constexpr size_t size() const noexcept { return m_size; }
        constexpr bool empty() const noexcept { return m_size == 0; }
        size_t capacity() const noexcept { return m_capacity; }

        // ----------------------------------------------------------------
        // Element access
        // ----------------------------------------------------------------

        uint64_t* data() noexcept { return m_data; }
        const uint64_t* data() const noexcept { return m_data; }

        uint64_t& operator[](size_t i) { return m_data[i]; }
        const uint64_t& operator[](size_t i) const { return m_data[i]; }

        uint64_t& back() { return m_data[m_size - 1]; }
        const uint64_t& back() const { return m_data[m_size - 1]; }

        // ----------------------------------------------------------------
        // Iterators
        // ----------------------------------------------------------------

        iterator begin() noexcept { return m_data; }
        iterator end() noexcept { return m_data + m_size; }
        const_iterator begin() const noexcept { return m_data; }
        const_iterator end() const noexcept { return m_data + m_size; }

        reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
        reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
        const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
        const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }

        // ----------------------------------------------------------------
        // Modification operations
        // ----------------------------------------------------------------

        void clear() noexcept {
            m_size = 0;
        }

        void resize(size_t n) {
            if (n <= m_size) {
                m_size = n;
                return;
            }
            ensure_capacity(n);
            // Zero-initialize the new elements
            std::memset(m_data + m_size, 0, (n - m_size) * sizeof(uint64_t));
            m_size = n;
        }

        // resize variant that skips zero-initialization (for callers that overwrite all elements)
        void resize_uninitialized(size_t n) {
            if (n <= m_capacity) {
                m_size = n;
                return;
            }
            ensure_capacity(n);
            m_size = n;
        }

        void resize(size_t n, uint64_t val) {
            if (n <= m_size) {
                m_size = n;
                return;
            }
            ensure_capacity(n);
            // Initialize new elements with val
            for (size_t i = m_size; i < n; ++i) {
                m_data[i] = val;
            }
            m_size = n;
        }

        void push_back(uint64_t val) {
            if (m_size == m_capacity) {
                grow(m_size + 1);
            }
            m_data[m_size++] = val;
        }

        void pop_back() noexcept {
            --m_size;
        }

        template<typename InputIt>
        void assign(InputIt first, InputIt last) {
            size_t n = static_cast<size_t>(std::distance(first, last));
            ensure_capacity(n);
            // When InputIt is a pointer, use memcpy
            if constexpr (std::is_same_v<InputIt, const uint64_t*> ||
                          std::is_same_v<InputIt, uint64_t*>) {
                std::memcpy(m_data, first, n * sizeof(uint64_t));
            } else {
                uint64_t* dst = m_data;
                for (auto it = first; it != last; ++it) {
                    *dst++ = *it;
                }
            }
            m_size = n;
        }

        iterator erase(iterator first, iterator last) {
            if (first == last) return first;
            size_t erased = static_cast<size_t>(last - first);
            size_t tail = static_cast<size_t>(end() - last);
            if (tail > 0) {
                std::memmove(first, last, tail * sizeof(uint64_t));
            }
            m_size -= erased;
            return first;
        }

        // ----------------------------------------------------------------
        // swap
        // ----------------------------------------------------------------

        void swap(SboWords& other) noexcept {
            // Both inline
            if (is_inline() && other.is_inline()) {
                uint64_t tmp[INLINE_CAP];
                size_t max_sz = std::max(m_size, other.m_size);
                std::memcpy(tmp, m_inline, max_sz * sizeof(uint64_t));
                std::memcpy(m_inline, other.m_inline, max_sz * sizeof(uint64_t));
                std::memcpy(other.m_inline, tmp, max_sz * sizeof(uint64_t));
                std::swap(m_size, other.m_size);
                return;
            }

            // Both on the heap
            if (!is_inline() && !other.is_inline()) {
                std::swap(m_data, other.m_data);
                std::swap(m_size, other.m_size);
                std::swap(m_capacity, other.m_capacity);
                return;
            }

            // One inline, the other on the heap
            SboWords& inl = is_inline() ? *this : other;
            SboWords& heap = is_inline() ? other : *this;

            uint64_t tmp_inline[INLINE_CAP];
            size_t tmp_size = inl.m_size;
            std::memcpy(tmp_inline, inl.m_inline, tmp_size * sizeof(uint64_t));

            // Move the heap side's pointer into the inline side
            inl.m_data = heap.m_data;
            inl.m_size = heap.m_size;
            inl.m_capacity = heap.m_capacity;

            // Copy the inline side's data to the heap side
            heap.m_data = heap.m_inline;
            heap.m_size = tmp_size;
            heap.m_capacity = INLINE_CAP;
            std::memcpy(heap.m_inline, tmp_inline, tmp_size * sizeof(uint64_t));
        }

        // ----------------------------------------------------------------
        // Comparison
        // ----------------------------------------------------------------

        bool operator==(const SboWords& other) const noexcept {
            if (m_size != other.m_size) return false;
            return std::memcmp(m_data, other.m_data, m_size * sizeof(uint64_t)) == 0;
        }

        bool operator!=(const SboWords& other) const noexcept {
            return !(*this == other);
        }

    private:
        uint64_t  m_inline[INLINE_CAP]; // 72 bytes (9 × 8)
        uint64_t* m_data;               //  8 bytes
        size_t    m_size;               //  8 bytes
        size_t    m_capacity;           //  8 bytes
        // Total: 96 bytes

        bool is_inline() const noexcept {
            return m_data == m_inline;
        }

        void ensure_capacity(size_t required) {
            if (required <= m_capacity) return;
            grow(required);
        }

        void grow(size_t min_cap) {
            // Growth rate: max(1.5x current capacity, min_cap)
            size_t new_cap = std::max(min_cap, m_capacity + m_capacity / 2);
            uint64_t* new_data = new uint64_t[new_cap];
            std::memcpy(new_data, m_data, m_size * sizeof(uint64_t));
            if (!is_inline()) delete[] m_data;
            m_data = new_data;
            m_capacity = new_cap;
        }
    };

} // namespace sangi

#endif // SANGI_SBO_WORDS_HPP