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

// FactoredInteger.hpp
// 因子表現クラス — 整数を素因数の積として保持
// lib++20 因子表現.h からの移植 (2026-03-13)
//
// 設計:
//   - 各因子 (factor) とその冪 (exponent) のペアを保持
//   - 乗除算を因子レベルで実行 (展開せずに保持)
//   - GCD/LCM が O(素因数数) で計算可能
//   - expand() で全因子を掛け合わせた値を取得
//   - 和形式 (additive) もサポート

#pragma once

#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
#include <cassert>

namespace sangi {

// ================================================================
// FactoredInteger<T> クラス
// ================================================================

template<typename T>
class FactoredInteger {
private:
    std::vector<T> factors_;      // 因数
    std::vector<int> exponents_;  // 冪指数
    bool additive_;               // true: 和形式 (Σ f_i^e_i), false: 積形式 (Π f_i^e_i)

public:
    // ============================================================
    // コンストラクタ
    // ============================================================

    /// デフォルト: 空 (積形式 = 1, 和形式 = 0)
    FactoredInteger() : additive_(false) {}

    /// 指定個数の因子を確保
    explicit FactoredInteger(size_t n, bool additive = false)
        : factors_(n), exponents_(n, 1), additive_(additive)
    {
        T identity = additive ? T(0) : T(1);
        int defaultExp = additive ? 1 : 0;
        std::fill(factors_.begin(), factors_.end(), identity);
        std::fill(exponents_.begin(), exponents_.end(), defaultExp);
    }

    /// 因子と冪のペアのリストから構築 (積形式)
    FactoredInteger(std::initializer_list<std::pair<T, int>> pairs)
        : additive_(false)
    {
        for (const auto& [f, e] : pairs) {
            factors_.push_back(f);
            exponents_.push_back(e);
        }
    }

    // ============================================================
    // アクセサ
    // ============================================================

    /// 因子の数
    [[nodiscard]] size_t size() const { return factors_.size(); }

    /// 空か
    [[nodiscard]] bool empty() const { return factors_.empty(); }

    /// 和形式か
    [[nodiscard]] bool isAdditive() const { return additive_; }

    /// i 番目の因子
    [[nodiscard]] const T& factor(size_t i) const { return factors_[i]; }
    [[nodiscard]] T& factor(size_t i) { return factors_[i]; }

    /// i 番目の冪指数
    [[nodiscard]] int exponent(size_t i) const { return exponents_[i]; }
    [[nodiscard]] int& exponent(size_t i) { return exponents_[i]; }

    /// operator[] で因子にアクセス
    [[nodiscard]] const T& operator[](size_t i) const { return factors_[i]; }
    [[nodiscard]] T& operator[](size_t i) { return factors_[i]; }

    // ============================================================
    // 因子の追加・削除
    // ============================================================

    /// 因子 f を冪 e で追加
    void addFactor(const T& f, int e = 1) {
        // 既存の因子と一致するものがあればマージ
        for (size_t i = 0; i < factors_.size(); ++i) {
            if (factors_[i] == f) {
                exponents_[i] += e;
                return;
            }
        }
        factors_.push_back(f);
        exponents_.push_back(e);
    }

    /// 冪が 0 の因子を除去
    void removeZeroExponents() {
        size_t j = 0;
        for (size_t i = 0; i < factors_.size(); ++i) {
            if (exponents_[i] != 0) {
                if (j != i) {
                    factors_[j] = std::move(factors_[i]);
                    exponents_[j] = exponents_[i];
                }
                ++j;
            }
        }
        factors_.resize(j);
        exponents_.resize(j);
    }

    /// 要素数を変更
    void resize(size_t n) {
        size_t old = factors_.size();
        factors_.resize(n);
        exponents_.resize(n);
        if (n > old) {
            T identity = additive_ ? T(0) : T(1);
            int defaultExp = additive_ ? 1 : 0;
            for (size_t i = old; i < n; ++i) {
                factors_[i] = identity;
                exponents_[i] = defaultExp;
            }
        }
    }

    // ============================================================
    // 展開 (値の計算)
    // ============================================================

    /// 全因子を掛け合わせた (または足し合わせた) 値を返す
    [[nodiscard]] T expand() const {
        if (additive_) {
            T result = T(0);
            for (size_t i = 0; i < factors_.size(); ++i) {
                T term = factors_[i];
                for (int j = 1; j < exponents_[i]; ++j)
                    term *= factors_[i];
                result += term;
            }
            return result;
        } else {
            T result = T(1);
            for (size_t i = 0; i < factors_.size(); ++i) {
                for (int j = 0; j < exponents_[i]; ++j)
                    result *= factors_[i];
            }
            return result;
        }
    }

    // ============================================================
    // 乗除算 (因子レベル)
    // ============================================================

    /// 積形式同士の乗算: 因子をマージ
    [[nodiscard]] FactoredInteger operator*(const FactoredInteger& rhs) const {
        assert(!additive_ && !rhs.additive_);
        FactoredInteger result = *this;
        for (size_t i = 0; i < rhs.factors_.size(); ++i) {
            result.addFactor(rhs.factors_[i], rhs.exponents_[i]);
        }
        return result;
    }

    /// 積形式同士の除算: 冪指数を減算
    [[nodiscard]] FactoredInteger operator/(const FactoredInteger& rhs) const {
        assert(!additive_ && !rhs.additive_);
        FactoredInteger result = *this;
        for (size_t i = 0; i < rhs.factors_.size(); ++i) {
            result.addFactor(rhs.factors_[i], -rhs.exponents_[i]);
        }
        return result;
    }

    FactoredInteger& operator*=(const FactoredInteger& rhs) {
        return *this = *this * rhs;
    }
    FactoredInteger& operator/=(const FactoredInteger& rhs) {
        return *this = *this / rhs;
    }

    // ============================================================
    // GCD / LCM (因子レベル — O(因子数))
    // ============================================================

    /// 因子表現同士の GCD: 共通因子の冪の min
    [[nodiscard]] friend FactoredInteger gcd(const FactoredInteger& a,
                                              const FactoredInteger& b) {
        assert(!a.additive_ && !b.additive_);
        FactoredInteger result;
        for (size_t i = 0; i < a.factors_.size(); ++i) {
            for (size_t j = 0; j < b.factors_.size(); ++j) {
                if (a.factors_[i] == b.factors_[j]) {
                    int minExp = std::min(a.exponents_[i], b.exponents_[j]);
                    if (minExp > 0)
                        result.addFactor(a.factors_[i], minExp);
                    break;
                }
            }
        }
        return result;
    }

    /// 因子表現同士の LCM: 全因子の冪の max
    [[nodiscard]] friend FactoredInteger lcm(const FactoredInteger& a,
                                              const FactoredInteger& b) {
        assert(!a.additive_ && !b.additive_);
        FactoredInteger result = a;
        for (size_t j = 0; j < b.factors_.size(); ++j) {
            bool found = false;
            for (size_t i = 0; i < result.factors_.size(); ++i) {
                if (result.factors_[i] == b.factors_[j]) {
                    result.exponents_[i] = std::max(result.exponents_[i],
                                                     b.exponents_[j]);
                    found = true;
                    break;
                }
            }
            if (!found) {
                result.addFactor(b.factors_[j], b.exponents_[j]);
            }
        }
        return result;
    }

    // ============================================================
    // べき乗
    // ============================================================

    /// 全冪指数を n 倍
    [[nodiscard]] FactoredInteger pow(int n) const {
        FactoredInteger result = *this;
        for (auto& e : result.exponents_)
            e *= n;
        return result;
    }

    // ============================================================
    // 比較
    // ============================================================

    [[nodiscard]] bool operator==(const FactoredInteger& rhs) const {
        if (additive_ != rhs.additive_) return false;
        if (factors_.size() != rhs.factors_.size()) return false;
        // 同じ因子集合かチェック (順序不問)
        std::vector<bool> matched(rhs.factors_.size(), false);
        for (size_t i = 0; i < factors_.size(); ++i) {
            bool found = false;
            for (size_t j = 0; j < rhs.factors_.size(); ++j) {
                if (!matched[j] && factors_[i] == rhs.factors_[j]
                    && exponents_[i] == rhs.exponents_[j]) {
                    matched[j] = true;
                    found = true;
                    break;
                }
            }
            if (!found) return false;
        }
        return true;
    }

    [[nodiscard]] bool operator!=(const FactoredInteger& rhs) const {
        return !(*this == rhs);
    }

    // ============================================================
    // 文字列変換
    // ============================================================

    [[nodiscard]] std::string toString() const {
        if (factors_.empty()) {
            return additive_ ? "0" : "1";
        }

        std::ostringstream oss;
        for (size_t i = 0; i < factors_.size(); ++i) {
            if (i > 0) {
                oss << (additive_ ? " + " : " * ");
            }
            oss << "(" << factors_[i] << ")";
            if (exponents_[i] != 1) {
                oss << "^" << exponents_[i];
            }
        }
        return oss.str();
    }

    friend std::ostream& operator<<(std::ostream& os, const FactoredInteger& fi) {
        return os << fi.toString();
    }
};

// ================================================================
// 型特性
// ================================================================

template<typename T>
struct is_factored_integer : std::false_type {};

template<typename T>
struct is_factored_integer<FactoredInteger<T>> : std::true_type {};

template<typename T>
inline constexpr bool is_factored_integer_v = is_factored_integer<T>::value;

} // namespace sangi