Repository: TheAlgorithms/Java
Pull request #2964 (2022-02-24 11:20:25)

Issue/2963 - Refactoring and added 12 Junit tests
### **Describe your change:**

- [x] Add an algorithm?
- [x] Refactoring
- [x] Added 12 Junit tests

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/maths/FFT.java b/src/main/java/com/thealgorithms/maths/FFT.java
index 374d3fca..41184e09 100644
--- a/src/main/java/com/thealgorithms/maths/FFT.java
+++ b/src/main/java/com/thealgorithms/maths/FFT.java
@@ -175,31 +175,17 @@ public class FFT {
      * https://www.geeksforgeeks.org/iterative-fast-fourier-transformation-polynomial-multiplication/
      * https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
      * https://cp-algorithms.com/algebra/fft.html
-     *
-     * @param x The discrete signal which is then converted to the FFT or the
+     *  @param x The discrete signal which is then converted to the FFT or the
      * IFFT of signal x.
      * @param inverse True if you want to find the inverse FFT.
+     * @return
      */
-    public static void fft(ArrayList<Complex> x, boolean inverse) {
+    public static ArrayList<Complex> fft(ArrayList<Complex> x, boolean inverse) {
         /* Pad the signal with zeros if necessary */
         paddingPowerOfTwo(x);
         int N = x.size();
-
-        /* Find the log2(N) */
-        int log2N = 0;
-        while ((1 << log2N) < N) {
-            log2N++;
-        }
-
-        /* Swap the values of the signal with bit-reversal method */
-        int reverse;
-        for (int i = 0; i < N; i++) {
-            reverse = reverseBits(i, log2N);
-            if (i < reverse) {
-                Collections.swap(x, i, reverse);
-            }
-        }
-
+        int log2N = findLog2(N);
+        x = fftBitReversal(N,log2N,x);
         int direction = inverse ? -1 : 1;
 
         /* Main loop of the algorithm */
@@ -217,14 +203,40 @@ public class FFT {
                 }
             }
         }
+        x = inverseFFT(N,inverse,x);
+        return x;
+    }
+
+    /* Find the log2(N) */
+    public static int findLog2(int N){
+        int log2N = 0;
+        while ((1 << log2N) < N) {
+            log2N++;
+        }
+        return log2N;
+    }
+
+    /* Swap the values of the signal with bit-reversal method */
+    public static ArrayList<Complex> fftBitReversal(int N, int log2N, ArrayList<Complex> x){
+        int reverse;
+        for (int i = 0; i < N; i++) {
+            reverse = reverseBits(i, log2N);
+            if (i < reverse) {
+                Collections.swap(x, i, reverse);
+            }
+        }
+        return x;
+    }
 
-        /* Divide by N if we want the inverse FFT */
+    /* Divide by N if we want the inverse FFT */
+    public static ArrayList<Complex> inverseFFT(int N, boolean inverse, ArrayList<Complex> x ){
         if (inverse) {
             for (int i = 0; i < x.size(); i++) {
                 Complex z = x.get(i);
                 x.set(i, z.divide(N));
             }
         }
+        return x;
     }
 
     /**
diff --git a/src/main/java/com/thealgorithms/maths/Gaussian.java b/src/main/java/com/thealgorithms/maths/Gaussian.java
index 75450654..823e6a99 100644
--- a/src/main/java/com/thealgorithms/maths/Gaussian.java
+++ b/src/main/java/com/thealgorithms/maths/Gaussian.java
@@ -38,7 +38,7 @@ public class Gaussian {
         return mat;
     }
 
-    // calcilate the x_1, x_2,... values of the gaussian and save it in an arraylist.
+    // calculate the x_1, x_2,... values of the gaussian and save it in an arraylist.
     public static ArrayList<Double> valueOfGaussian(int mat_size, double[][] x, double[][] mat) {
         ArrayList<Double> answerArray = new ArrayList<Double>();
         int i, j;


Test patch:
diff --git a/src/test/java/com/thealgorithms/maths/FFTTest.java b/src/test/java/com/thealgorithms/maths/FFTTest.java
new file mode 100644
index 00000000..fcdf64ab
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/FFTTest.java
@@ -0,0 +1,147 @@
+package com.thealgorithms.maths;
+import org.junit.jupiter.api.Test;
+import java.util.ArrayList;
+import static org.junit.jupiter.api.Assertions.*;
+
+class FFTTest {
+
+    // Testing the simple function getReal
+    @Test
+    void getRealtest()
+    {
+        FFT.Complex complex = new FFT.Complex(1.0,1.0);
+        assertEquals(1.0,complex.getReal());
+    }
+
+    // Testing the simple function getImaginary
+    @Test
+    void getImaginaryTest()
+    {
+        FFT.Complex complex = new FFT.Complex();
+        assertEquals(0.0,complex.getImaginary());
+    }
+
+    // Testing the function add, assertEqual test
+    @Test
+    void addTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(1.0,1.0);
+        FFT.Complex complex2 = new FFT.Complex(2.0,2.0);
+        double add = complex1.add(complex2).getReal();
+        assertEquals(3.0,add);
+    }
+
+    // Testing the function add, assertNotEqual test
+    @Test
+    void addFalseTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(1.0,1.0);
+        FFT.Complex complex2 = new FFT.Complex(2.0,2.0);
+        double add = complex1.add(complex2).getReal();
+        assertNotEquals(2.0,add);
+    }
+
+    // Testing the function substract, assertEqual test
+    @Test
+    void subtractTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
+        FFT.Complex complex2 = new FFT.Complex(1.0,1.0);
+        double sub = complex1.subtract(complex2).getReal();
+        assertEquals(1.0,sub);
+    }
+
+    // Testing the function multiply complex, assertEqual test
+    @Test
+    void multiplyWithComplexTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
+        FFT.Complex complex2 = new FFT.Complex(1.0,1.0);
+        double multiReal = complex1.multiply(complex2).getReal();
+        double multiImg = complex1.multiply(complex2).getImaginary();
+        assertEquals(0.0,multiReal);
+        assertEquals(4.0,multiImg);
+    }
+
+    // Testing the function multiply scalar, assertEqual test
+    @Test
+    void multiplyWithScalarTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
+
+        double multiReal = complex1.multiply(2).getReal();
+        double multiImg = complex1.multiply(3).getImaginary();
+        assertEquals(4.0,multiReal);
+        assertEquals(6.0,multiImg);
+    }
+
+    // Testing the function conjugate, assertEqual test
+    @Test
+    void conjugateTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
+        double conReal = complex1.conjugate().getReal();
+        double conImg = complex1.conjugate().getImaginary();
+        assertEquals(2.0,conReal);
+        assertEquals(-2.0,conImg);
+    }
+
+    // Testing the function abs, assertEqual test
+    @Test
+    void abs()
+    {
+        FFT.Complex complex1 = new FFT.Complex(2.0,3.0);
+        double abs = complex1.abs();
+        assertEquals(Math.sqrt(13),abs);
+    }
+
+    // Testing the function divide complex, assertEqual test.
+    @Test
+    void divideWithComplexTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
+        FFT.Complex complex2 = new FFT.Complex(1.0,2.0);
+        double divReal = complex1.divide(complex2).getReal();
+        double divImg = complex1.divide(complex2).getImaginary();
+        assertEquals(1.2,divReal);
+        assertEquals(-0.4,divImg);
+    }
+
+    // Testing the function divide scalar, assertEqual test.
+    @Test
+    void divideWithScalarTest()
+    {
+        FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
+        double divReal = complex1.divide(2).getReal();
+        double divImg = complex1.divide(2).getImaginary();
+        assertEquals(1,divReal);
+        assertEquals(1,divImg);
+    }
+
+    // Testing the function fft, assertEqual test.
+    // https://scistatcalc.blogspot.com/2013/12/fft-calculator.html used this link to
+    // ensure the result
+    @Test
+    void fft()
+    {
+        ArrayList<FFT.Complex> arr = new ArrayList<FFT.Complex>();
+        FFT.Complex complex1 = new FFT.Complex(2.0,2.0);
+        FFT.Complex complex2 = new FFT.Complex(1.0,3.0);
+        FFT.Complex complex3 = new FFT.Complex(3.0,1.0);
+        FFT.Complex complex4 = new FFT.Complex(2.0,2.0);
+
+        arr.add(complex1);
+        arr.add(complex2);
+        arr.add(complex3);
+        arr.add(complex4);
+        arr = FFT.fft(arr,false);
+        double realV1= arr.get(0).getReal();
+        double realV2= arr.get(2).getReal();
+        double imgV1 = arr.get(0).getImaginary();
+        double imgV2 = arr.get(2).getImaginary();
+        assertEquals(8.0,realV1);
+        assertEquals(2.0,realV2);
+        assertEquals(8.0, imgV1);
+        assertEquals(-2.0,imgV2);
+    }
+}