<commit_before>/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.math.transform;

import org.apache.commons.math.MathRuntimeException;
import org.apache.commons.math.analysis.UnivariateFunction;
import org.apache.commons.math.exception.util.LocalizedFormats;

/**
 * Implements the <a href="http://www.archive.chipcenter.com/dsp/DSP000517F1.html">Fast Hadamard Transform</a> (FHT).
 * Transformation of an input vector x to the output vector y.
 * <p>In addition to transformation of real vectors, the Hadamard transform can
 * transform integer vectors into integer vectors. However, this integer transform
 * cannot be inverted directly. Due to a scaling factor it may lead to rational results.
 * As an example, the inverse transform of integer vector (0, 1, 0, 1) is rational
 * vector (1/2, -1/2, 0, 0).</p>
 * @version $Id$
 * @since 2.0
 */
public class FastHadamardTransformer implements RealTransformer {

    /** {@inheritDoc} */
    public double[] transform(double[] f)
        throws IllegalArgumentException {
        return fht(f);
    }

    /** {@inheritDoc} */
    public double[] transform(UnivariateFunction f,
                              double min, double max, int n)
        throws IllegalArgumentException {
        return fht(FastFourierTransformer.sample(f, min, max, n));
    }

    /** {@inheritDoc} */
    public double[] inverseTransform(double[] f)
    throws IllegalArgumentException {
        return FastFourierTransformer.scaleArray(fht(f), 1.0 / f.length);
   }

    /** {@inheritDoc} */
    public double[] inverseTransform(UnivariateFunction f,
                                     double min, double max, int n)
        throws IllegalArgumentException {
        final double[] unscaled =
            fht(FastFourierTransformer.sample(f, min, max, n));
        return FastFourierTransformer.scaleArray(unscaled, 1.0 / n);
    }

    /**
     * Transform the given real data set.
     * <p>The integer transform cannot be inverted directly, due to a scaling
     * factor it may lead to double results.</p>
     * @param f the integer data array to be transformed (signal)
     * @return the integer transformed array (spectrum)
     * @throws IllegalArgumentException if any parameters are invalid
     */
    public int[] transform(int[] f)
        throws IllegalArgumentException {
        return fht(f);
    }

    /**
     * The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.
     * <br>
     * Requires <b>Nlog2N = n2</b><sup>n</sup> additions.
     * <br>
     * <br>
     * <b><u>Short Table of manual calculation for N=8:</u></b>
     * <ol>
     * <li><b>x</b> is the input vector we want to transform</li>
     * <li><b>y</b> is the output vector which is our desired result</li>
     * <li>a and b are just helper rows</li>
     * </ol>
     * <pre>
     * <code>
     * +----+----------+---------+----------+
     * | <b>x</b>  |    <b>a</b>     |    <b>b</b>    |    <b>y</b>     |
     * +----+----------+---------+----------+
     * | x<sub>0</sub> | a<sub>0</sub>=x<sub>0</sub>+x<sub>1</sub> | b<sub>0</sub>=a<sub>0</sub>+a<sub>1</sub> | y<sub>0</sub>=b<sub>0</sub>+b<sub>1</sub> |
     * +----+----------+---------+----------+
     * | x<sub>1</sub> | a<sub>1</sub>=x<sub>2</sub>+x<sub>3</sub> | b<sub>0</sub>=a<sub>2</sub>+a<sub>3</sub> | y<sub>0</sub>=b<sub>2</sub>+b<sub>3</sub> |
     * +----+----------+---------+----------+
     * | x<sub>2</sub> | a<sub>2</sub>=x<sub>4</sub>+x<sub>5</sub> | b<sub>0</sub>=a<sub>4</sub>+a<sub>5</sub> | y<sub>0</sub>=b<sub>4</sub>+b<sub>5</sub> |
     * +----+----------+---------+----------+
     * | x<sub>3</sub> | a<sub>3</sub>=x<sub>6</sub>+x<sub>7</sub> | b<sub>0</sub>=a<sub>6</sub>+a<sub>7</sub> | y<sub>0</sub>=b<sub>6</sub>+b<sub>7</sub> |
     * +----+----------+---------+----------+
     * | x<sub>4</sub> | a<sub>0</sub>=x<sub>0</sub>-x<sub>1</sub> | b<sub>0</sub>=a<sub>0</sub>-a<sub>1</sub> | y<sub>0</sub>=b<sub>0</sub>-b<sub>1</sub> |
     * +----+----------+---------+----------+
     * | x<sub>5</sub> | a<sub>1</sub>=x<sub>2</sub>-x<sub>3</sub> | b<sub>0</sub>=a<sub>2</sub>-a<sub>3</sub> | y<sub>0</sub>=b<sub>2</sub>-b<sub>3</sub> |
     * +----+----------+---------+----------+
     * | x<sub>6</sub> | a<sub>2</sub>=x<sub>4</sub>-x<sub>5</sub> | b<sub>0</sub>=a<sub>4</sub>-a<sub>5</sub> | y<sub>0</sub>=b<sub>4</sub>-b<sub>5</sub> |
     * +----+----------+---------+----------+
     * | x<sub>7</sub> | a<sub>3</sub>=x<sub>6</sub>-x<sub>7</sub> | b<sub>0</sub>=a<sub>6</sub>-a<sub>7</sub> | y<sub>0</sub>=b<sub>6</sub>-b<sub>7</sub> |
     * +----+----------+---------+----------+
     * </code>
     * </pre>
     *
     * <b><u>How it works</u></b>
     * <ol>
     * <li>Construct a matrix with N rows and n+1 columns<br>   <b>hadm[n+1][N]</b>
     * <br><i>(If I use [x][y] it always means [row-offset][column-offset] of a Matrix with n rows and m columns. Its entries go from M[0][0] to M[n][m])</i></li>
     * <li>Place the input vector <b>x[N]</b> in the first column of the matrix <b>hadm</b></li>
     * <li>The entries of the submatrix D<sub>top</sub> are calculated as follows.
     * <br>D<sub>top</sub> goes from entry [0][1] to [N/2-1][n+1].
     * <br>The columns of D<sub>top</sub> are the pairwise mutually exclusive sums of the previous column
     * </li>
     * <li>The entries of the submatrix D<sub>bottom</sub> are calculated as follows.
     * <br>D<sub>bottom</sub> goes from entry [N/2][1] to [N][n+1].
     * <br>The columns of D<sub>bottom</sub> are the pairwise differences of the previous column
     * </li>
     * <li>How D<sub>top</sub> and D<sub>bottom</sub> you can understand best with the example for N=8 above.
     * <li>The output vector y is now in the last column of <b>hadm</b></li>
     * <li><i>Algorithm from: http://www.archive.chipcenter.com/dsp/DSP000517F1.html</i></li>
     * </ol>
     * <br>
     * <b><u>Visually</u></b>
     * <pre>
     *        +--------+---+---+---+-----+---+
     *        |   0    | 1 | 2 | 3 | ... |n+1|
     * +------+--------+---+---+---+-----+---+
     * |0     | x<sub>0</sub>     |       /\            |
     * |1     | x<sub>1</sub>     |       ||            |
     * |2     | x<sub>2</sub>     |   <= D<sub>top</sub>  =>       |<commit_msg>Formatting (MATH-677).<commit_after>/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.math.transform;

import org.apache.commons.math.MathRuntimeException;
import org.apache.commons.math.analysis.UnivariateFunction;
import org.apache.commons.math.exception.util.LocalizedFormats;

/**
 * Implements the <a href="http://www.archive.chipcenter.com/dsp/DSP000517F1.html">Fast Hadamard Transform</a> (FHT).
 * Transformation of an input vector x to the output vector y.
 * <p>In addition to transformation of real vectors, the Hadamard transform can
 * transform integer vectors into integer vectors. However, this integer transform
 * cannot be inverted directly. Due to a scaling factor it may lead to rational results.
 * As an example, the inverse transform of integer vector (0, 1, 0, 1) is rational
 * vector (1/2, -1/2, 0, 0).</p>
 * @version $Id$
 * @since 2.0
 */
public class FastHadamardTransformer implements RealTransformer {

    /** {@inheritDoc} */
    public double[] transform(double[] f)
        throws IllegalArgumentException {
        return fht(f);
    }

    /** {@inheritDoc} */
    public double[] transform(UnivariateFunction f,
                              double min, double max, int n)
        throws IllegalArgumentException {
        return fht(FastFourierTransformer.sample(f, min, max, n));
    }

    /** {@inheritDoc} */
    public double[] inverseTransform(double[] f)
    throws IllegalArgumentException {
        return FastFourierTransformer.scaleArray(fht(f), 1.0 / f.length);
   }

    /** {@inheritDoc} */
    public double[] inverseTransform(UnivariateFunction f,
                                     double min, double max, int n)
        throws IllegalArgumentException {
        final double[] unscaled =
            fht(FastFourierTransformer.sample(f, min, max, n));
        return FastFourierTransformer.scaleArray(unscaled, 1.0 / n);
    }

    /**
     * Transform the given real data set.
     * <p>The integer transform cannot be inverted directly, due to a scaling
     * factor it may lead to double results.</p>
     * @param f the integer data array to be transformed (signal)
     * @return the integer transformed array (spectrum)
     * @throws IllegalArgumentException if any parameters are invalid
     */
    public int[] transform(int[] f)
        throws IllegalArgumentException {
        return fht(f);
    }

    /**
     * The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.
     * <br>
     * Requires <b>Nlog2N = n2</b><sup>n</sup> additions.
     * <br>
     * <br>
     * <b><u>Short Table of manual calculation for N=8:</u></b>
     * <ol>
     * <li><b>x</b> is the input vector we want to transform</li>
     * <li><b>y</b> is the output vector which is our desired result</li>
     * <li>a and b are just helper rows</li>
     * </ol>
     * <table border="1" align="center">
     * <tr>
     *     <th>x</th>
     *     <th>a</th>
     *     <th>b</th>
     *     <th>y</th>
     * </tr>
     * <tr>
     *     <td>x<sub>0</sub></td>
     *     <td>a<sub>0</sub> = x<sub>0</sub> + x<sub>1</sub></td>
     *     <td>b<sub>0</sub> = a<sub>0</sub> + a<sub>1</sub></td>
     *     <td>y<sub>0</sub> = b<sub>0</sub >+ b<sub>1</sub></td>
     * </tr>
     * <tr>
     *     <td>x<sub>1</sub></td>
     *     <td>a<sub>1</sub> = x<sub>2</sub> + x<sub>3</sub></td>
     *     <td>b<sub>0</sub> = a<sub>2</sub> + a<sub>3</sub></td>
     *     <td>y<sub>0</sub> = b<sub>2</sub> + b<sub>3</sub></td>
     * </tr>
     * <tr>
     *     <td>x<sub>2</sub></td>
     *     <td>a<sub>2</sub> = x<sub>4</sub> + x<sub>5</sub></td>
     *     <td>b<sub>0</sub> = a<sub>4</sub> + a<sub>5</sub></td>
     *     <td>y<sub>0</sub> = b<sub>4</sub> + b<sub>5</sub></td>
     * </tr>
     * <tr>
     *     <td>x<sub>3</sub></td>
     *     <td>a<sub>3</sub> = x<sub>6</sub> + x<sub>7</sub></td>
     *     <td>b<sub>0</sub> = a<sub>6</sub> + a<sub>7</sub></td>
     *     <td>y<sub>0</sub> = b<sub>6</sub> + b<sub>7</sub></td>
     * </tr>
     * <tr>
     *     <td>x<sub>4</sub></td>
     *     <td>a<sub>0</sub> = x<sub>0</sub> - x<sub>1</sub></td>
     *     <td>b<sub>0</sub> = a<sub>0</sub> - a<sub>1</sub></td>
     *     <td>y<sub>0</sub> = b<sub>0</sub> - b<sub>1</sub></td>
     * </tr>
     * <tr>
     *     <td>x<sub>5</sub></td>
     *     <td>a<sub>1</sub> = x<sub>2</sub> - x<sub>3</sub></td>
     *     <td>b<sub>0</sub> = a<sub>2</sub> - a<sub>3</sub></td>
     *     <td>y<sub>0</sub> = b<sub>2</sub> - b<sub>3</sub></td>
     * </tr>
     * <tr>
     *     <td>x<sub>6</sub></td>
     *     <td>a<sub>2</sub> = x<sub>4</sub> - x<sub>5</sub></td>
     *     <td>b<sub>0</sub> = a<sub>4</sub> - a<sub>5</sub></td>
     *     <td>y<sub>0</sub> = b<sub>4</sub> - b<sub>5</sub></td>
     * </tr>
     * <tr>
     *     <td>x<sub>7</sub></td>
     *     <td>a<sub>3</sub> = x<sub>6</sub> - x<sub>7</sub></td>
     *     <td>b<sub>0</sub> = a<sub>6</sub> - a<sub>7</sub></td>
     *     <td>y<sub>0</sub> = b<sub>6</sub> - b<sub>7</sub></td>
     * </tr>
     * </table>
     *
     * <b><u>How it works</u></b>
     * <ol>
     * <li>Construct a matrix with N rows and n+1 columns<br>   <b>hadm[n+1][N]</b>
     * <br><i>(If I use [x][y] it always means [row-offset][column-offset] of a Matrix with n rows and m columns. Its entries go from M[0][0] to M[n][m])</i></li>
     * <li>Place the input vector <b>x[N]</b> in the first column of the matrix <b>hadm</b></li>
     * <li>The entries of the submatrix D<sub>top</sub> are calculated as follows.
     * <br>D<sub>top</sub> goes from entry [0][1] to [N/2-1][n+1].
     * <br>The columns of D<sub>top</sub> are the pairwise mutually exclusive sums of the previous column
     * </li>
     * <li>The entries of the submatrix D<sub>bottom</sub> are calculated as follows.
     * <br>D<sub>bottom</sub> goes from entry [N/2][1] to [N][n+1].
     * <br>The columns of D<sub>bottom</sub> are the pairwise differences of the previous column
     * </li>
     * <li>How D<sub>top</sub> and D<sub>bottom</sub> you can understand best with the example for N=8 above.
     * <li>The output vector y is now in the last column of <b>hadm</b></li>
     * <li><i>Algorithm from: http://www.archive.chipcenter.com/dsp/DSP000517F1.html</i></li>
     * </ol>
     * <br>
     * <b><u>Visually</u></b>
     * <table border="1" align="center">
     * <tr>
     *     <td>0</td>
     *     <td>1</td>
     *     <td>2</td>
     *     <td>3</td>
     *     <td>...</td>
     *     <td>n + 1</td>
     * </tr>
     * <tr>
     *     <td>0</td>
     *     <td>x<sub>0</sub></td>
     *     <td colspan="5">&uarr;</td>
     * </tr>
     * </table>
     * <pre>
     *        +--------+---+---+---+-----+---+
     *        |   0    | 1 | 2 | 3 | ... |n+1|
     * +------+--------+---+---+---+-----+---+
     * |0     | x<sub>0</sub>     |       /\            |
     * |1     | x<sub>1</sub>     |       ||            |
     * |2     | x<sub>2</sub>     |   <= D<sub>top</sub>  =>       |
{'fraction_non_alphanumeric': 0.21546440358321547, 'fraction_numerical': 0.019869333872162727, 'mean_word_length': 2.317247542448615, 'pattern_counts': {'":': 0, '<': 647, '<?xml version=': 0, '>': 647, 'https://': 0, 'lorem ipsum': 0, 'www.': 6, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7153248', 'n_tokens_mistral': 5441, 'n_tokens_neox': 5322, 'n_words': 1234}