<?php

declare(strict_types=1);

namespace App\Domain\QrCode\ValueObject;

/**
 * Repräsentiert ein Polynom im Galois-Feld für Reed-Solomon-Berechnungen
 */
class Polynomial
{
    private array $coefficients;

    public function __construct(
        private readonly GaloisField $field,
        array $coefficients
    ) {
        // Entferne führende Nullen
        $this->coefficients = $this->removeLeadingZeros($coefficients);

        // Leeres Polynom = [0]
        if (empty($this->coefficients)) {
            $this->coefficients = [0];
        }
    }

    /**
     * Entfernt führende Nullen aus dem Koeffizienten-Array
     */
    private function removeLeadingZeros(array $coefficients): array
    {
        $i = 0;
        while ($i < count($coefficients) - 1 && $coefficients[$i] === 0) {
            $i++;
        }

        return array_slice($coefficients, $i);
    }

    /**
     * Liefert die Koeffizienten des Polynoms
     */
    public function getCoefficients(): array
    {
        return $this->coefficients;
    }

    /**
     * Liefert den Grad des Polynoms
     */
    public function getDegree(): int
    {
        return count($this->coefficients) - 1;
    }

    /**
     * Wertet das Polynom an der Stelle x aus
     */
    public function evaluateAt(int $x): int
    {
        if ($x === 0) {
            // f(0) ist der letzte Koeffizient
            return $this->coefficients[count($this->coefficients) - 1];
        }

        $result = 0;
        $degree = $this->getDegree();

        for ($i = 0; $i <= $degree; $i++) {
            // result = result * x + coef[i]
            $term = $this->field->multiply(
                $result,
                $x
            );
            $result = $this->field->add($term, $this->coefficients[$i]);
        }

        return $result;
    }

    /**
     * Addiert zwei Polynome
     */
    public function add(Polynomial $other): Polynomial
    {
        if ($this->isZero()) {
            return $other;
        }

        if ($other->isZero()) {
            return $this;
        }

        $thisCoeffs = $this->coefficients;
        $otherCoeffs = $other->getCoefficients();

        $resultLength = max(count($thisCoeffs), count($otherCoeffs));
        $result = array_fill(0, $resultLength, 0);

        // Addiere die Koeffizienten
        for ($i = 0; $i < count($thisCoeffs); $i++) {
            $result[$i + ($resultLength - count($thisCoeffs))] = $thisCoeffs[$i];
        }

        for ($i = 0; $i < count($otherCoeffs); $i++) {
            $idx = $i + ($resultLength - count($otherCoeffs));
            $result[$idx] = $this->field->add($result[$idx], $otherCoeffs[$i]);
        }

        return new Polynomial($this->field, $result);
    }

    /**
     * Multipliziert zwei Polynome
     */
    public function multiply(Polynomial $other): Polynomial
    {
        if ($this->isZero() || $other->isZero()) {
            return new Polynomial($this->field, [0]);
        }

        $thisCoeffs = $this->coefficients;
        $otherCoeffs = $other->getCoefficients();

        $resultLength = count($thisCoeffs) + count($otherCoeffs) - 1;
        $result = array_fill(0, $resultLength, 0);

        // Multipliziere die Koeffizienten
        for ($i = 0; $i < count($thisCoeffs); $i++) {
            for ($j = 0; $j < count($otherCoeffs); $j++) {
                $idx = $i + $j;
                $product = $this->field->multiply($thisCoeffs[$i], $otherCoeffs[$j]);
                $result[$idx] = $this->field->add($result[$idx], $product);
            }
        }

        return new Polynomial($this->field, $result);
    }

    /**
     * Multipliziert das Polynom mit einem Skalar
     */
    public function multiplyByScalar(int $scalar): Polynomial
    {
        if ($scalar === 0) {
            return new Polynomial($this->field, [0]);
        }

        if ($scalar === 1) {
            return $this;
        }

        $result = [];
        foreach ($this->coefficients as $coefficient) {
            $result[] = $this->field->multiply($coefficient, $scalar);
        }

        return new Polynomial($this->field, $result);
    }

    /**
     * Dividiert ein Polynom durch ein anderes und gibt Quotient und Rest zurück
     */
    public function divideAndRemainder(Polynomial $other): array
    {
        if ($other->isZero()) {
            throw new \DivisionByZeroError('Division by zero polynomial');
        }

        if ($this->isZero()) {
            return [
                'quotient' => new Polynomial($this->field, [0]),
                'remainder' => new Polynomial($this->field, [0])
            ];
        }

        if ($this->getDegree() < $other->getDegree()) {
            return [
                'quotient' => new Polynomial($this->field, [0]),
                'remainder' => $this
            ];
        }

        $quotientCoeffs = array_fill(0, $this->getDegree() - $other->getDegree() + 1, 0);
        $remainderCoeffs = $this->coefficients;

        $denomLeadingTerm = $other->getCoefficients()[0];

        for ($i = 0; $i <= $this->getDegree() - $other->getDegree(); $i++) {
            if ($remainderCoeffs[$i] === 0) {
                continue;
            }

            $quotientCoeffs[$i] = $this->field->divide($remainderCoeffs[$i], $denomLeadingTerm);

            for ($j = 0; $j <= $other->getDegree(); $j++) {
                $idx = $i + $j;
                $product = $this->field->multiply($quotientCoeffs[$i], $other->getCoefficients()[$j]);
                $remainderCoeffs[$idx] = $this->field->subtract($remainderCoeffs[$idx], $product);
            }
        }

        // Extrahiere den Rest
        $remainderDegree = $other->getDegree() - 1;
        $remainder = array_slice($remainderCoeffs, count($remainderCoeffs) - $remainderDegree - 1);

        return [
            'quotient' => new Polynomial($this->field, $quotientCoeffs),
            'remainder' => new Polynomial($this->field, $remainder)
        ];
    }

    /**
     * Prüft, ob das Polynom das Nullpolynom ist
     */
    public function isZero(): bool
    {
        return count($this->coefficients) === 1 && $this->coefficients[0] === 0;
    }

    /**
     * Erzeugt ein Generatorpolynom für Reed-Solomon-Codes
     */
    public static function buildGenerator(GaloisField $field, int $degree): Polynomial
    {
        // g(x) = (x-α^0)(x-α^1)...(x-α^(degree-1))
        $generator = new Polynomial($field, [1]); // Beginne mit g(x) = 1

        for ($i = 0; $i < $degree; $i++) {
            // Faktor (x-α^i)
            $factor = new Polynomial($field, [
                1, // x^1
                $field->power(2, $i) // -α^i (In GF(2^m) ist -a = a)
            ]);
            $generator = $generator->multiply($factor);
        }

        return $generator;
    }
}
