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

// IntFactorTable.hpp
// Prime factor table (Sieve of Eratosthenes, recording the largest prime factor)

#ifndef SANGI_INT_FACTOR_TABLE_HPP
#define SANGI_INT_FACTOR_TABLE_HPP

#include "IntBase.hpp"
#include <vector>
#include <string>

namespace sangi {

/**
 * @brief Prime factor table (largest-prime-factor version)
 *
 * Uses the Sieve of Eratosthenes to build a table recording the largest
 * prime factor of each integer. Recording the largest prime factor (LPF)
 * instead of the smallest prime factor (SPF) has the following advantages:
 *
 * 1. **Faster sieve construction**: unconditional overwrite, no branching
 * 2. **Faster factorization**: dividing by larger primes first shrinks
 *    the digit count more quickly
 * 3. **Simpler code**: no checks needed
 *
 * Algorithm:
 *   - For prime p, unconditionally overwrite table[m] = p for every multiple m
 *   - Processed in increasing prime order, so the largest prime factor remains
 *     at the end
 *
 * Usage example:
 *   IntFactorTable table(10000);  // Build the factor table up to 10000
 *   int lpf = table[360];          // 360 = 2^3 * 3^2 * 5 -> lpf = 5
 *   auto factors = table.factorize(Int(360));  // {{2,3}, {3,2}, {5,1}}
 */
class IntFactorTable {
private:
    std::vector<uint32_t> table_;  // Stores odd numbers only (even numbers are always prime factor 2)
    int max_value_;                // Maximum value of the table

public:
    /**
     * @brief Constructor (builds the table)
     *
     * @param max_value Maximum value of the table (default: 1000000 = 1M)
     *
     * Builds the prime factor table up to max_value.
     * Construction takes O(n log log n) time.
     *
     * Memory usage:
     *   - max_value = 1000:       about 2KB
     *   - max_value = 1000000:    about 2MB
     *   - max_value = 100000000:  about 200MB
     */
    explicit IntFactorTable(int max_value = 1000000);

    /**
     * @brief Get the maximum value of the table
     */
    int maxValue() const { return max_value_; }

    /**
     * @brief Get the largest prime factor of the given integer
     *
     * @param n Integer (0 <= n <= max_value)
     * @return Largest prime factor (0 when n is prime; a special value for n = 0,1)
     *
     * Return value:
     *   - n = 0 or n = 1: 0
     *   - n is prime: 0
     *   - n is composite: largest prime factor
     *   - n is even (n > 2): 2, or the largest odd prime factor
     *
     * Note: returns 0 when n > max_value (out of range)
     */
    int operator[](int n) const;

    /**
     * @brief Factorize the given integer into primes
     *
     * @param n Integer to factorize
     * @return Vector of (prime, exponent) pairs {{p1, e1}, {p2, e2}, ...}
     *         ordered by p1 < p2 < ... (ascending)
     *
     * Examples:
     *   factorize(Int(360)) -> {{2,3}, {3,2}, {5,1}}  (360 = 2^3 * 3^2 * 5)
     *   factorize(Int(17))  -> {{17,1}}  (prime)
     *   factorize(Int(1))   -> {}  (empty)
     *   factorize(Int(0))   -> {{0,1}}  (special case)
     *
     * Special cases:
     *   - n = 0: {{0, 1}}
     *   - n = 1: {} (empty vector)
     *   - n < 0: returns the factorization of |n|
     *   - n > max_value: parts beyond the table are factorized by trial division
     *   - n.isNaN(): {} (empty)
     *   - n.isInfinite(): {} (empty)
     */
    std::vector<std::pair<Int, int>> factorize(const Int& n) const;

    /**
     * @brief Save the table to a file
     *
     * @param filename File name (default: "FactorTable.dat")
     * @return true on success, false on failure
     *
     * Saved in binary format:
     *   1. max_value (4 bytes)
     *   2. table size (4 bytes)
     *   3. table contents (uint32_t x size)
     */
    bool saveToFile(const std::string& filename = "FactorTable.dat") const;

    /**
     * @brief Load the table from a file
     *
     * @param filename File name (default: "FactorTable.dat")
     * @return true on success, false on failure
     *
     * Fails if the file does not exist or its size does not match.
     */
    bool loadFromFile(const std::string& filename = "FactorTable.dat");

private:
    /**
     * @brief Build the table using the Sieve of Eratosthenes (LPF version)
     *
     * Algorithm:
     *   for p = 3 to sqrt(max_value) step 2:
     *       if table[p] == 0:  // p is prime
     *           for m = p^2 to max_value step 2*p:
     *               table[m] = p  // unconditional overwrite (no condition check)
     *
     * Difference from the smallest-prime-factor (SPF) version:
     *   - SPF: if (table[m] == 0) table[m] = p;  // requires a check
     *   - LPF: table[m] = p;                     // no check needed
     */
    void buildTable();

    /**
     * @brief Convert an odd-number index to the index in the internal array
     *
     * @param n Odd number
     * @return Index in the internal array
     *
     * Because only odd numbers are stored, use the index obtained by
     * dividing n by 2.
     * Example: n=3 -> index=1, n=5 -> index=2, n=7 -> index=3
     */
    size_t oddIndex(int n) const {
        return static_cast<size_t>(n >> 1);
    }
};

} // namespace sangi

#endif // SANGI_INT_FACTOR_TABLE_HPP