<?php
/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2026  Chris Pollett chris@pollett.org
 *
 * LICENSE:
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * END LICENSE
 *
 * @author Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
namespace seekquarry\yioop\tests;

use seekquarry\yioop\library\av_processing\Fft;
use seekquarry\yioop\library\UnitTest;

/**
 * Checks that turning a run of numbers into the tones that make it up
 * gives the same answer as working each tone out one at a time.
 *
 * Working one tone out at a time is the definition, so it is what the
 * fast way has to agree with. The fast way is checked at the four
 * lengths Opus uses, at a length that is a prime, and at lengths that
 * need each of the ways of splitting, since a fault in one way of
 * splitting would otherwise hide behind the others.
 *
 * @author Chris Pollett
 */
class FftTest extends UnitTest
{
    /**
     * How close the fast way has to come to the definition, allowing
     * for rounding as the numbers are added up
     */
    const CLOSE_ENOUGH = 1e-9;
    /**
     * The lengths Opus works in
     */
    const OPUS_LENGTHS = [60, 120];
    /**
     * The longest length Opus works in. Working every tone of it out
     * one at a time takes long enough to be worth avoiding, so it is
     * checked at a few tones rather than all of them.
     */
    const LONGER_OPUS_LENGTHS = [240, 480];
    /**
     * Which tones of that longest length to check
     */
    const SAMPLED_TONES = [0, 1, 2, 37, 239, 240, 478, 479];
    /**
     * A starting point for the made up numbers, so a failing case
     * fails the same way every time
     */
    const SEED = 20260803;
    /**
     * Sets the made up numbers off from the same place every run
     */
    public function setUp()
    {
        mt_srand(self::SEED);
    }
    /**
     * Nothing needs clearing away after these cases
     */
    public function tearDown()
    {
    }
    /**
     * Works out the tones one at a time, which is the definition the
     * fast way has to agree with
     *
     * @param array $across the sideways part of each number
     * @param array $up the upward part of each number
     * @param bool $backwards whether to go the other way
     * @return array the tones, as sideways and upward parts
     */
    public function oneAtATime($across, $up, $backwards)
    {
        $size = count($across);
        $out_across = [];
        $out_up = [];
        $sign = $backwards ? 2.0 : -2.0;
        for ($i = 0; $i < $size; $i++) {
            $total_across = 0.0;
            $total_up = 0.0;
            for ($j = 0; $j < $size; $j++) {
                $angle = $sign * M_PI * $i * $j / $size;
                $total_across += $across[$j] * cos($angle) -
                    $up[$j] * sin($angle);
                $total_up += $across[$j] * sin($angle) +
                    $up[$j] * cos($angle);
            }
            $out_across[] = $total_across;
            $out_up[] = $total_up;
        }
        return [$out_across, $out_up];
    }
    /**
     * Makes up a run of numbers to work on
     *
     * @param int $size how long a run to make
     * @return array the sideways and upward parts
     */
    public function madeUpRun($size)
    {
        $across = [];
        $up = [];
        for ($i = 0; $i < $size; $i++) {
            $across[] = mt_rand(-1000, 1000) / 1000.0;
            $up[] = mt_rand(-1000, 1000) / 1000.0;
        }
        return [$across, $up];
    }
    /**
     * How far the fast way strays from the definition at one length
     *
     * @param int $size how long a run to try
     * @param bool $backwards whether to go the other way
     * @return float the largest difference found
     */
    public function strayAt($size, $backwards)
    {
        list($across, $up) = $this->madeUpRun($size);
        list($want_across, $want_up) = $this->oneAtATime($across, $up,
            $backwards);
        $got_across = $across;
        $got_up = $up;
        Fft::forSize($size)->run($got_across, $got_up, $backwards);
        $stray = 0.0;
        for ($i = 0; $i < $size; $i++) {
            $stray = max($stray, abs($want_across[$i] - $got_across[$i]),
                abs($want_up[$i] - $got_up[$i]));
        }
        return $stray;
    }
    /**
     * At the four lengths Opus works in, the fast way should agree
     * with the definition both ways round
     */
    public function opusLengthsTestCase()
    {
        foreach (self::OPUS_LENGTHS as $size) {
            $this->assertTrue($this->strayAt($size, false) <
                self::CLOSE_ENOUGH, "length $size going forward");
            $this->assertTrue($this->strayAt($size, true) <
                self::CLOSE_ENOUGH, "length $size going back");
        }
    }
    /**
     * At the longer lengths Opus works in, a scattering of tones
     * should match what working those tones out one at a time gives
     */
    public function longerOpusLengthsTestCase()
    {
        foreach (self::LONGER_OPUS_LENGTHS as $size) {
            $this->checkSampledTones($size);
        }
    }
    /**
     * Checks a few tones of one length against the definition, rather
     * than every tone, since working out every tone of a long run
     * costs more than the whole rest of these cases together
     *
     * @param int $size how long a run to check
     */
    public function checkSampledTones($size)
    {
        list($across, $up) = $this->madeUpRun($size);
        $got_across = $across;
        $got_up = $up;
        Fft::forSize($size)->run($got_across, $got_up);
        $stray = 0.0;
        foreach (self::SAMPLED_TONES as $tone) {
            if ($tone >= $size) {
                continue;
            }
            $total_across = 0.0;
            $total_up = 0.0;
            for ($j = 0; $j < $size; $j++) {
                $angle = -2.0 * M_PI * $tone * $j / $size;
                $total_across += $across[$j] * cos($angle) -
                    $up[$j] * sin($angle);
                $total_up += $across[$j] * sin($angle) +
                    $up[$j] * cos($angle);
            }
            $stray = max($stray, abs($total_across - $got_across[$tone]),
                abs($total_up - $got_up[$tone]));
        }
        $this->assertTrue($stray < self::CLOSE_ENOUGH,
            "length $size matches the definition where checked");
    }
    /**
     * Each way of splitting should be right on its own, so lengths are
     * tried that need one way and not the others
     */
    public function eachWayOfSplittingTestCase()
    {
        $lengths = [2, 3, 4, 5, 8, 9, 16, 25, 27];
        foreach ($lengths as $size) {
            $this->assertTrue($this->strayAt($size, false) <
                self::CLOSE_ENOUGH, "length $size going forward");
        }
    }
    /**
     * A length that will not split at all has to be handled by the
     * definition itself, and should still come out right
     */
    public function lengthThatWillNotSplitTestCase()
    {
        foreach ([7, 11, 13, 17] as $size) {
            $this->assertTrue($this->strayAt($size, false) <
                self::CLOSE_ENOUGH, "prime length $size");
        }
    }
    /**
     * Going one way and then the other should give back what was
     * started with, once the growth the second pass adds is taken off
     */
    public function thereAndBackTestCase()
    {
        foreach ([60, 120, 480] as $size) {
            list($across, $up) = $this->madeUpRun($size);
            $there_across = $across;
            $there_up = $up;
            $plan = Fft::forSize($size);
            $plan->run($there_across, $there_up, false);
            $plan->run($there_across, $there_up, true);
            $stray = 0.0;
            for ($i = 0; $i < $size; $i++) {
                $stray = max($stray,
                    abs($across[$i] - $there_across[$i] / $size),
                    abs($up[$i] - $there_up[$i] / $size));
            }
            $this->assertTrue($stray < self::CLOSE_ENOUGH,
                "length $size came back as it went in");
        }
    }
    /**
     * A run of the same number over and over is made of one steady
     * tone and nothing else, which is a check that does not depend on
     * the definition being worked out again
     */
    public function steadyRunIsOneToneTestCase()
    {
        $size = 120;
        $across = array_fill(0, $size, 2.5);
        $up = array_fill(0, $size, 0.0);
        Fft::forSize($size)->run($across, $up);
        $this->assertTrue(abs($across[0] - 2.5 * $size) <
            self::CLOSE_ENOUGH, "the steady part holds the whole of it");
        $rest = 0.0;
        for ($i = 1; $i < $size; $i++) {
            $rest = max($rest, abs($across[$i]), abs($up[$i]));
        }
        $this->assertTrue($rest < self::CLOSE_ENOUGH,
            "no other tone is present");
    }
    /**
     * Working out how to handle a length is done once and kept, since
     * doing it again for every stretch of a recording would cost more
     * than the transform itself
     */
    public function workingOutIsKeptTestCase()
    {
        $first = Fft::forSize(480);
        $second = Fft::forSize(480);
        $this->assertTrue($first === $second,
            "the same length gives back the same working out");
        $this->assertEqual(Fft::splitUp(480), [[4, 120], [4, 30], [2, 15],
            [3, 5], [5, 1]], "480 splits by fours first, then the rest");
        $this->assertEqual(Fft::splitUp(60), [[4, 15], [3, 5], [5, 1]],
            "60 splits into a four, a three and a five");
    }
}
