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

// SboWords.hpp
// Small Buffer Optimization 付きワード配列
// std::vector<uint64_t> の代替として Int クラス内部で使用

#ifndef CALX_SBO_WORDS_HPP
#define CALX_SBO_WORDS_HPP

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

namespace calx {

    /**
     * @brief SBO (Small Buffer Optimization) 付き uint64_t 配列
     *
     * 9 words (576-bit) 以下はインラインバッファに格納し、
     * heap allocation を回避する。
     * std::vector<uint64_t> と互換のインターフェースを提供。
     *
     * 9 words にする理由: 512-bit (8 words) 同士の加算結果が
     * 桁上がりで 9 words になっても SBO 内に収まるようにする。
     *
     * レイアウト (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>;

        // ----------------------------------------------------------------
        // コンストラクタ・デストラクタ
        // ----------------------------------------------------------------

        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()) {
                // インラインデータはコピー
                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;
        }

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

        // ----------------------------------------------------------------
        // 代入演算子
        // ----------------------------------------------------------------

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

            if (other.m_size <= m_capacity) {
                // 既存バッファに収まる
                std::memcpy(m_data, other.m_data, other.m_size * sizeof(uint64_t));
                m_size = other.m_size;
            } else {
                // 新しいバッファが必要
                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;
        }

        // ----------------------------------------------------------------
        // サイズ・容量
        // ----------------------------------------------------------------

        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; }

        // ----------------------------------------------------------------
        // 要素アクセス
        // ----------------------------------------------------------------

        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]; }

        // ----------------------------------------------------------------
        // イテレータ
        // ----------------------------------------------------------------

        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()); }

        // ----------------------------------------------------------------
        // 変更操作
        // ----------------------------------------------------------------

        void clear() noexcept {
            m_size = 0;
        }

        void resize(size_t n) {
            if (n <= m_size) {
                m_size = n;
                return;
            }
            ensure_capacity(n);
            // 新規要素をゼロ初期化
            std::memset(m_data + m_size, 0, (n - m_size) * sizeof(uint64_t));
            m_size = n;
        }

        // ゼロ初期化をスキップする resize (呼び出し元が全要素を上書きする場合用)
        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);
            // 新規要素を 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);
            // InputIt がポインタの場合は 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 {
            // 両方インライン
            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;
            }

            // 両方ヒープ
            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;
            }

            // 片方インライン、片方ヒープ
            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));

            // ヒープ側のポインタをインライン側に移動
            inl.m_data = heap.m_data;
            inl.m_size = heap.m_size;
            inl.m_capacity = heap.m_capacity;

            // インライン側のデータをヒープ側にコピー
            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));
        }

        // ----------------------------------------------------------------
        // 比較
        // ----------------------------------------------------------------

        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) {
            // 成長率: 現容量の 1.5 倍 or 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 calx

#endif // CALX_SBO_WORDS_HPP