#include #include #include #include // C++20 三方比較演算子

namespace calx {

    // 前方宣言
    class Float;

    /**
     * @brief 多倍長有理数クラス
     *
     * 任意精度の有理数 (分子/分母) を表現するクラス。
     * 分母は常に正、分母子は常に約分済みの状態を維持する。
     * 内部で Int クラスを使用する。
     */
    class Rational {
    private:
        Int numerator_;     // 分子
        Int denominator_;   // 分母 (常に正, 約分済み)

    public:
        // --- コンストラクタ ---
        Rational();
        explicit Rational(int num, int den = 1);
        explicit Rational(const Int& num);
        Rational(const Int& num, const Int& den, bool doReduce = true);
        Rational(Int&& num, Int&& den, bool doReduce = true);
        Rational(const Rational& other);
        Rational(Rational&& other) noexcept;
        explicit Rational(std::string_view str, int base = 10);
        explicit Rational(double value);
        explicit Rational(float value);
        explicit Rational(const Float& value);

        ~Rational() = default;

        // --- アクセサ ---
        [[nodiscard]] const Int& numerator() const { return numerator_; }
        [[nodiscard]] const Int& denominator() const { return denominator_; }

        // --- 代入 ---
        Rational& operator=(const Rational& other);
        Rational& operator=(Rational&& other) noexcept;
        Rational& operator=(int value);
        Rational& operator=(double value);
        Rational& operator=(float value);
        Rational& operator=(const Int& value);

        // --- 比較演算子 ---
        friend std::partial_ordering operator<=>(const Rational& lhs, const Rational& rhs);
        friend bool operator==(const Rational& lhs, const Rational& rhs);
        friend std::partial_ordering operator<=>(const Rational& lhs, const Int& rhs);
        friend bool operator==(const Rational& lhs, const Int& rhs);
        friend std::partial_ordering operator<=>(const Rational& lhs, int rhs);
        friend bool operator==(const Rational& lhs, int rhs);

        // --- 単項演算子 ---
        const Rational& operator+() const& { return *this; }
        Rational&& operator+() && { return std::move(*this); }
        [[nodiscard]] Rational operator-() const&;
        [[nodiscard]] Rational operator-() &&;

        // --- インクリメント/デクリメント ---
        Rational& operator++();
        [[nodiscard]] Rational operator++(int);
        Rational& operator--();
        [[nodiscard]] Rational operator--(int);

        // --- 四則演算 (Rational <-> Rational) ---
        friend Rational operator+(const Rational& lhs, const Rational& rhs);
        friend Rational operator-(const Rational& lhs, const Rational& rhs);
        friend Rational operator*(const Rational& lhs, const Rational& rhs);
        friend Rational operator/(const Rational& lhs, const Rational& rhs);
        friend Rational operator%(const Rational& lhs, const Rational& rhs);

        // --- 四則演算 (Rational <-> Int) ---
        friend Rational operator+(const Rational& lhs, const Int& rhs);
        friend Rational operator+(const Int& lhs, const Rational& rhs);
        friend Rational operator-(const Rational& lhs, const Int& rhs);
        friend Rational operator-(const Int& lhs, const Rational& rhs);
        friend Rational operator*(const Rational& lhs, const Int& rhs);
        friend Rational operator*(const Int& lhs, const Rational& rhs);
        friend Rational operator/(const Rational& lhs, const Int& rhs);
        friend Rational operator/(const Int& lhs, const Rational& rhs);

        // --- 四則演算 (Rational <-> int) ---
        friend Rational operator+(const Rational& lhs, int rhs);
        friend Rational operator+(int lhs, const Rational& rhs);
        friend Rational operator-(const Rational& lhs, int rhs);
        friend Rational operator-(int lhs, const Rational& rhs);
        friend Rational operator*(const Rational& lhs, int rhs);
        friend Rational operator*(int lhs, const Rational& rhs);
        friend Rational operator/(const Rational& lhs, int rhs);
        friend Rational operator/(int lhs, const Rational& rhs);

        // --- 複合代入 ---
        Rational& operator+=(const Rational& rhs);
        Rational& operator-=(const Rational& rhs);
        Rational& operator*=(const Rational& rhs);
        Rational& operator/=(const Rational& rhs);
        Rational& operator+=(const Int& rhs);
        Rational& operator-=(const Int& rhs);
        Rational& operator*=(const Int& rhs);
        Rational& operator/=(const Int& rhs);
        Rational& operator+=(int rhs);
        Rational& operator-=(int rhs);
        Rational& operator*=(int rhs);
        Rational& operator/=(int rhs);

        // --- 冪乗 ---
        [[nodiscard]] Rational pow(int exponent) const;

        // --- シフト (2の冪による乗除) ---
        [[nodiscard]] Rational operator<<(int n) const;
        [[nodiscard]] Rational operator>>(int n) const;

        // --- 状態判定 ---
        [[nodiscard]] bool isNegative() const { return numerator_.isNegative(); }
        [[nodiscard]] bool isNonPositive() const { return numerator_.isNegative() || numerator_.isZero(); }
        [[nodiscard]] bool isZero() const { return numerator_.isZero() && denominator_.isNormal(); }
        [[nodiscard]] bool isNonZero() const { return !isZero(); }
        [[nodiscard]] bool isNonNegative() const { return !numerator_.isNegative(); }
        [[nodiscard]] bool isPositive() const { return numerator_.isPositive(); }
        [[nodiscard]] bool isOne() const { return numerator_ == denominator_ && denominator_.isNormal(); }
        [[nodiscard]] bool isInteger() const { return !isNaN() && denominator_.isOne(); }
        [[nodiscard]] bool isNaN() const { return numerator_.isNaN() || denominator_.isNaN(); }

        // --- 便利関数 ---
        [[nodiscard]] Rational doubled() const;
        [[nodiscard]] Rational halved() const;

        /// 逆数を返す (分子と分母をスワップ)。O(1)。
        /// ゼロの逆数は NaN (分母=0) を返す。
        [[nodiscard]] Rational reciprocal() const {
            if (isZero() || isNaN()) return Rational(Int(0), Int(0), false);
            // 符号を分子に保持: 分母が負なら符号反転
            if (numerator_.isNegative()) {
                return Rational(-denominator_, -numerator_, false);
            }
            return Rational(denominator_, numerator_, false);
        }

        // --- swap ---
        friend void swap(Rational& a, Rational& b) noexcept;

        // --- 約分 ---
        bool reduce();

        // --- 変換 ---
        explicit operator int() const;
        explicit operator float() const;
        explicit operator double() const;
        [[nodiscard]] double toDouble() const;
        [[nodiscard]] float toFloat() const;
        [[nodiscard]] Float toMpFloat(int precision = 0) const;
        [[nodiscard]] std::string toString(int base = 10) const;
        [[nodiscard]] std::string toDecimal(int digits = 20) const;

        // --- 連分数 ---
        [[nodiscard]] std::vector toContinuedFraction() const;
        [[nodiscard]] static Rational fromContinuedFraction(const std::vector & cf);

        // --- ストリーム ---
        friend std::ostream& operator<<(std::ostream& os, const Rational& r);
        friend std::istream& operator>>(std::istream& is, Rational& r);
    };

    // --- フリー関数 ---
    [[nodiscard]] Rational abs(const Rational& x);
    [[nodiscard]] Int floor(const Rational& x);
    [[nodiscard]] Int ceil(const Rational& x);
    [[nodiscard]] Int trunc(const Rational& x);
    [[nodiscard]] Int round(const Rational& x);
    [[nodiscard]] Rational square(const Rational& x);
    [[nodiscard]] Int height(const Rational& x);
    [[nodiscard]] Rational conj(const Rational& x);
    [[nodiscard]] Rational gcd(const Rational& x, const Rational& y);

    // --- ユーティリティ関数 ---
    [[nodiscard]] Rational inv(const Rational& x);
    [[nodiscard]] int sgn(const Rational& x);
    [[nodiscard]] Rational frac(const Rational& x);
    [[nodiscard]] Rational mediant(const Rational& a, const Rational& b);

    // --- 有理数復元 (FLINT-23) ---
    // a mod m から p/q (|p| ≤ N, 0 < q ≤ D) を復元
    [[nodiscard]] Rational reconstructRational(const Int& a, const Int& m,
                                               const Int& N, const Int& D);

    // --- 調和数 (FLINT-24) ---
    // H_n = 1 + 1/2 + ... + 1/n (正確な有理数)
    [[nodiscard]] Rational harmonicNumber(unsigned int n);

    // --- デデキント和 (FLINT-25) ---
    // s(h,k) = Σ_{i=1}^{k-1} ((i/k))((hi/k))
    [[nodiscard]] Rational dedekindSum(const Int& h, const Int& k);

    // --- 有理数列挙 (FLINT-26) ---
    // Stern-Brocot 順 (高さ昇順) で次の正有理数
    [[nodiscard]] Rational nextMinimal(const Rational& x);
    // Calkin-Wilf 列で次の正有理数
    [[nodiscard]] Rational nextCalkinWilf(const Rational& x);

    // --- ファレイ近傍 (FLINT-27) ---
    // Farey 数列 F_Q における左右近傍 (left, right)
    [[nodiscard]] std::pair fareyNeighbors(
        const Rational& x, const Int& Q);
    // 開区間 (a, b) 内の最小高さ有理数
    [[nodiscard]] Rational simplestBetween(const Rational& a, const Rational& b);

    // --- 有理数の mod (FLINT-29) ---
    // (p/q) mod m = p * q^{-1} mod m (q と m は互いに素)
    [[nodiscard]] Int mod(const Rational& x, const Int& m);

    // --- 大指数冪乗 (FLINT-30) ---
    // 指数が Int (多倍長) の冪乗
    [[nodiscard]] Rational pow(const Rational& x, const Int& exponent);

} // namespace calx

#endif // CALX_RATIONAL_BASE_HPP